发现推理长度最优值由任务状态追踪难度决定，而非复杂度总量。
Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length?
- 用确定性有限自动机建模任务复杂度，量化推理步数与状态空间。
- 不同模型下均存在使正确率最高的最优推理长度。
- 长推理更适用于需追踪复杂状态的任务，而非状态空间大的任务。
大型语言模型在推理时常受益于显式思维链，但尚不清楚这些额外推理标记对应何种任务难度。为此，我们使用确定性有限自动机（DFAs）构建分析框架，通过可度量的属性（如运行长度和状态空间大小）刻画任务复杂度。实验表明，在不同任务和模型规模下，均存在一个使正确答案概率最大化的最优推理标记数量。进一步分析发现，任务对应的DFA运行长度（即隐含状态追踪需求）越长，所需推理长度也越长；而状态空间大小（即决策复杂度）则无显著影响。该结果揭示了预测最优推理长度的可行性：通过预判并筛选出非最优长度的输出，可稳定提升模型准确率。
原文摘要 · Abstract (English)
Large language models (LLMs) often benefit from verbalized reasoning at inference time, but it remains unclear which aspects of task difficulty these extra reasoning tokens address. To investigate this question, we formalize a framework using deterministic finite automata (DFAs). DFAs offer a formalism through which we can characterize task complexity through measurable properties such as run length (number of reasoning steps required) and state-space size (decision complexity). We first show that across different tasks and models of different sizes and training paradigms, there exists an optimal amount of reasoning tokens such that the probability of producing a correct solution is maximized. We then investigate which properties of complexity govern this critical length: we find that task instances with longer corresponding underlying DFA runs (i.e. demand greater latent state-tracking requirements) correlate with longer reasoning lengths, but, surprisingly, that DFA size (i.e. state-space complexity) does not. We then demonstrate an implication of these findings: being able to predict the optimal number of reasoning tokens for new problems and filtering out non-optimal length answers results in consistent accuracy improvements.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。