用有限状态机测试大模型的多步推理能力，发现其在长链条任务中会逐渐失效。
The Illusion of Procedural Reasoning: Measuring Long-Horizon FSM Execution in LLMs
- 设计可解释的有限状态机任务，让模型按规则逐步执行
- 模型在复杂分支下准确率显著下降，长记忆反而影响较小
- 提示外部化中间步骤可缓解失效，适合研究模型可靠性的人看
大型语言模型（LLMs）在以推理形式呈现的任务上表现优异，但其真实执行多步、规则驱动计算的能力尚不明确。与可确定性执行长程符号过程的算法系统不同，LLMs 在长时间推理链中常出现性能退化，却缺乏可控且可解释的基准来分离和测量这种退化。本文提出有限状态机（FSM）执行作为评估LLMs程序推理能力的最小、完全可解释框架。模型需根据给定的显式FSM定义，对输入动作进行逐步执行，并在多轮中保持状态一致性。该任务无需世界知识，仅要求忠实应用确定性转移规则，是直接探测模型内部程序保真度的探针。我们通过转次准确率（Turn Accuracy）和任务准确率（Task Accuracy）区分即时计算与累积状态维护能力。实证结果显示，随着任务视野或分支复杂度增加，模型表现系统性退化。当规则检索涉及高分支因子时，模型表现明显劣于长记忆场景。更大模型虽局部准确率提升，但在多步推理中仍脆弱，除非显式提示外部化中间步骤。基于FSM的评估提供了一种透明、复杂度可控的探针，用于诊断此失败模式并指导诱导偏置的设计，以实现真正的长程程序能力。通过将推理建立在可测量的执行保真度之上而非表面正确性，本工作为理解与提升LLMs的算法可靠性奠定了严谨实验基础。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。