# Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length?

**Authors:** Celine Lee, Alexander M. Rush, Keyon Vafa  
**arXiv:** [2504.01935](https://arxiv.org/abs/2504.01935)  
**Date:** 2025-04-02  
**Summary page:** https://www.summarizepaper.com/en/paper/2504.01935v1/

## Key points

- <Deterministic Finite Automata>: The use of DFAs in analyzing optimal reasoning lengths.
- <Task Structure>: How task structure affects optimal reasoning lengths.
- <Optimal Reasoning Lengths>: Identification and significance of optimal reasoning lengths.
- <COT-RL Training>: Comparison between models trained using COT-RL and non-COT-RL methods.
- <DFA-Based Framework>: Utilization of DFA formalism in characterizing task complexity and identifying critical reasoning lengths.

## Summary

In this study, the researchers utilized deterministic finite automata (DFAs) to analyze the impact of task structure on optimal reasoning lengths in Large Language Models (LLMs). The framework established through DFA formalism allowed for the characterization of task complexity based on measurable properties such as run length and state-space size. The findings revealed that there exists an optimal number of reasoning tokens that maximizes the probability of producing correct solutions across various tasks and models. One key observation was that accuracy tends to decline after surpassing the critical reasoning length, a phenomenon also noted in previous studies. <Deterministic Finite Automata>: The use of DFAs in analyzing optimal reasoning lengths. <Task Structure>: How task structure affects optimal reasoning lengths. <Optimal Reasoning Lengths>: Identification and significance of optimal reasoning lengths. <COT-RL Training>: Comparison between models trained using COT-RL and non-COT-RL methods. <DFA-Based Framework>: Utilization of DFA formalism in characterizing task complexity and identifying critical reasoning lengths. While DFA theory suggests models could theoretically maintain correctness with indefinite reasoning steps, factors like redundant reasoning, backtracking, or generation noise may lead to deviations from optimal performance. Furthermore, models trained using chain-of-thought reinforcement learning (COT-RL) exhibited longer reasoning chains and higher accuracy compared to non-COT-RL counterparts. Future research could explore how COT-RL training influences model-generated reasoning lengths and their alignment with optimal values indicated by DFA run length. The study also highlighted the challenge of extending the DFA framework to complex tasks like CRUXEval, which involve large implicit program states. By investigating alternate DFA representations for different tasks and assessing their impact on optimal reasoning lengths and overall performance, insights into effective prompting and inference strategies could be gained. Additionally, future work may focus on developing advanced predictors of critical length beyond linear regression models. Utilizing LLM-based methods incorporating textual descriptions or minimal demonstrations could enhance the practical usability of critical length-based filtering across diverse reasoning scenarios. In conclusion, this paper contributes a comprehensive analysis of how task structural properties influence optimal test-time reasoning in LLMs using a DFA-based framework. The empirical findings shed light on the importance of identifying critical reasoning lengths for improved model performance across various tasks and training paradigms.