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.

本研究解决了大型语言模型在推理时所需额外推理标记的任务难度特征不明确的问题。我们通过确定性有限自动机(DFA)构建框架，发现推理步骤所需的合理长度与任务的潜在状态追踪需求有关，而与状态空间复杂性无关。这一发现使我们能够预测新问题的最佳推理标记数量，从而提高准确性。

批判性思维：哪些复杂性影响最佳推理长度？