# The Illusion of Procedural Reasoning: Measuring Long-Horizon FSM Execution in LLMs

arXiv: https://arxiv.org/abs/2511.14777 · HTML: https://mlsanity.com/paper/2511.14777/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 5 of its 6 references that are in the map.
- First posted on arXiv 5 Nov 2025.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)

## Builds on (most cited first, 5 of 5)

- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs](https://mlsanity.com/paper/2509.09677/) (2025)
- [OMEGA: Can LLMs Reason Outside the Box in Math? Evaluating Exploratory, Compositional, and Transformative Generalization](https://mlsanity.com/paper/2506.18880/) (2025)
- [GSM-Infinite: How Do Your LLMs Behave over Infinitely Increasing Context Length and Reasoning Complexity?](https://mlsanity.com/paper/2502.05252/) (2025)
- [Bridging Reasoning to Learning: Unmasking Illusions using Complexity Out of Distribution Generalization](https://mlsanity.com/paper/2510.06274/) (2025)

## Built on by (most cited first, 3 of 3)

- [World-Model Collapse as a Phase Transition](https://mlsanity.com/paper/2606.31399/) (2026)
- [PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces](https://mlsanity.com/paper/2609.19883/) (2026)
- [Dude, Where's My State? Execution Information Requirements for Stateful Agents](https://mlsanity.com/paper/2609.32687/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have achieved remarkable results on tasks framed as reasoning problems, yet their true ability to perform procedural reasoning, executing multi-step, rule-based computations remains unclear. Unlike algorithmic systems, which can deterministically execute long-horizon symbolic procedures, LLMs often degrade under extended reasoning chains, but there is no controlled, interpretable benchmark to isolate and measure this collapse. We introduce Finite-State Machine (FSM) Execution as a minimal, fully interpretable framework for evaluating the procedural reasoning capacity of LLMs. In our setup, the model is given an explicit FSM definition and must execute it step-by-step given input actions, maintaining state consistency over multiple turns. This task requires no world knowledge, only faithful application of deterministic transition rules, making it a direct probe of the model's internal procedural fidelity. We measure both Turn Accuracy and Task Accuracy to disentangle immediate computation from cumulative state maintenance. Empirical results reveal systematic degradation as task horizon or branching complexity increases. Models perform significantly worse when rule retrieval involves high branching factors than when memory span is long. Larger models show improved local accuracy but remain brittle under multi-step reasoning unless explicitly prompted to externalize intermediate steps. FSM-based evaluation offers a transparent, complexity-controlled probe for diagnosing this failure mode and guiding the design of inductive biases that enable genuine long-horizon procedural competence. By grounding reasoning in measurable execution fidelity rather than surface correctness, this work helps establish a rigorous experimental foundation for understanding and improving the algorithmic reliability of LLMs.