Pith. sign in

REVIEW 4 major objections 6 minor 1 cited by

Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexity

T0 review · 4 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In a transformer trained from scratch on A* search traces, chain-of-thought length tracks training-data familiarity rather than problem difficulty, so long traces should not be read as thinking effort.

desk verdict A controlled small-scale negative result on CoT length vs. A* complexity, directionally plausible but under-quantified and over-extrapolated to R1. read the letter →

arxiv 2509.07339 v1 pith:N5Q5IOPQ submitted 2025-09-09 cs.AI

Vardhan Palod , Karthik Valmeekam , Kaya Stechly , Subbarao Kambhampati This is my paper · ORCID
classification cs.AI
keywords chain-of-thoughtintermediatetokengenerationA*traceimitationproblemcomplexitydistributionalshiftreasoningmodelspathfindingtest-timescaling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether the number of intermediate tokens a model emits before its answer tracks how hard the problem actually is, or how familiar the problem looks. To get a verifiable answer, the authors train a 380M-parameter transformer from scratch to imitate the step-by-step traces of A* search on 30×30 maze problems, where A*'s operation count is an exact ground-truth measure of complexity. They find that on trivial no-obstacle grids the model often runs to the 32k context limit without solving anything, and across maze generators with different structure the generated trace length and A* trace length correlate only loosely. The only cases with visible correlation are held-out problems drawn from the same generator as training, which the authors read as approximate recall rather than adaptive computation. The paper's conclusion is that for such models, longer traces should not be treated as evidence of more "thinking," and it extends this caution to large reasoning models whose long chains are popularly anthropomorphized.

What carries the argument

The key machinery is the derivational trace of A* search, linearized into tokens of the form 'create x y cG cH' and 'close x y cG cH' for each node creation and expansion. Because A*'s number of operations equals the length of this trace, the trace gives a precise, verifiable measure of problem complexity. Training a from-scratch transformer to imitate these traces creates a controlled setting in which the model's own generated trace length can be compared against the ground-truth complexity of each maze. The design also varies the maze-generation algorithm, producing training and test distributions with different structural distance, which lets the authors separate complexity effects from d

What would settle it

Take the same maze setup and train an identically sized transformer with reinforcement learning that rewards only the final plan's correctness, with no trace supervision, then measure the trace-length versus A*-operation-count correlation on out-of-distribution maze generators. A strong, monotone correlation across all generators would refute the claim that distributional distance, not complexity, controls trace length; a flat correlation would confirm it.

Watch

Extended reading notes

Core claim

The central claim is that intermediate token length in a transformer trained on derivational traces is not a reliable index of problem-adaptive computation. Using A* on grid mazes as a controlled setting, the authors define problem complexity as the number of A* operations, which is directly proportional to the ground-truth trace length. After training on 500,000 mazes from one generator, the model produces trace lengths that are only loosely correlated with A* trace lengths on held-out mazes from other generators; on obstacle-free grids it produces excessively long traces and frequently fails. Where correlation does appear, it is confined to instances close to the training distribution, lea

Load-bearing premise

The load-bearing premise is that a 380M-parameter model trained purely to imitate A* traces is a faithful stand-in for large reasoning models trained with reinforcement learning and preference alignment, so that findings about its trace lengths carry over to them.

Editorial extensions

If this is right

  • Trace length cannot be used as a proxy for problem difficulty when evaluating models on out-of-distribution inputs.
  • Observed "adaptive" reasoning lengths on in-distribution test sets may be an artifact of approximate recall, not evidence of computation that scales with difficulty.
  • Methods that aim to improve efficiency by shortening reasoning chains may be targeting a property that is not aligned with task complexity.
  • Anthropomorphic readings of intermediate tokens as "thinking effort" require additional evidence beyond trace length.
  • Evaluation of reasoning models should explicitly control distributional distance between training and test data.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension is to measure distributional distance quantitatively and test whether trace-length correlation degrades smoothly as distance grows; the paper demonstrates the phenomenon but does not fit such a curve.
  • The controlled small-scale result suggests that large reasoning models trained with reinforcement learning on final answers might behave differently, since RL can in principle select for concise or long traces; whether the same distributional-recall pattern survives RL post-training is an open question the paper does not settle.
  • If trace length reflects training priors, then cross-distribution benchmarks are the right setting for evaluating test-time scaling claims; in-distribution accuracy alone could mask non-adaptive trace generation.
  • An interventionist test follows: perturb the maze distribution while holding A* operation counts constant; if trace lengths track the perturbation rather than the counts, the recall explanation is confirmed.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper trains a ~380M-parameter decoder-only transformer from scratch on linearized A* traces for 30x30 grid-maze pathfinding, using Wilson-algorithm mazes as the training distribution. It then evaluates the model on held-out Wilson mazes, on mazes from four other generation algorithms (Kruskal, DFS, SF-Style, Drunkard), and on obstacle-free 'free-space' problems. The central claim is that the length of the model's generated intermediate tokens is only loosely correlated with the ground-truth A* trace length (a precise, verifiable measure of problem complexity), that the apparent correlation appears only for mazes close to the training distribution, and that this indicates approximate recall rather than problem-adaptive computation. The paper uses this to caution against interpreting long reasoning traces in systems such as DeepSeek R1 as evidence of 'thinking effort.'

Significance. If the central claim survives quantification, this is a useful controlled result. The setup has real strengths: problem complexity is external and verifiable via A* operation counts, the training procedure is fully specified and reproducible, and the 'model organism' framing is honest about the gap between small-scale trace-imitation models and large reasoning models. The paper addresses a timely and important question about whether CoT length is a reliable index of adaptive computation. However, the central claim currently rests on visual inspection of scatter plots; the design is capable of supporting a much stronger quantitative statement, and the missing statistics, censoring handling, and distributional-distance measure are the main obstacles. I would view the paper as making a credible qualitative case that needs additional quantitative rigor before the abstract's strong conclusions can be accepted.

major comments (4)
  1. [§4.1, Fig. 1a] The claim that 'there is very little correlation' is never operationalized. No Pearson/Spearman correlation, R², or confidence interval is reported for the free-space data or for any other maze family. This is load-bearing: Fig. 1a explicitly includes responses that hit the 32k context limit without producing a solution, and censored observations of this kind can substantially attenuate a true correlation. Moreover, only 5 of 100 free-space problems yield a valid plan, so any 'correlation' in that regime is computed over 5 points. Please report correlation coefficients with confidence intervals for each condition, treat truncated responses explicitly (e.g., exclude-and-analyze separately or use a censoring-aware analysis), and report the number of valid plans per condition. The y=x line also conflates correlation with calibration; a strong monotonic association need not lie on y=x if tok
  2. [§4.2, Figs. 1b and 2] The conclusion that correlation 'vanishes as distributional distance increases' is based on comparing exactly two maze families (Wilson vs. Searchformer-style) and no quantitative definition of distributional distance. The paper never measures distance between maze distributions, so the abstract's attribution of the effect to 'distributional distance from the training data' is not supported by a trend. Please (i) report correlation coefficients for all five OOD maze families, (ii) define a measurable distributional distance (e.g., wall density, loop density, graph-theoretic statistics, or solution-length distribution), and (iii) test whether correlation strength decreases monotonically with that distance, or at least present a nonparametric comparison across families. Without this, the central causal claim remains an interpretation of two selected scatter plots rather than a demonstrated
  3. [§1 and §5, transfer to R1] The paper's stated target is the interpretation of long traces in systems like DeepSeek R1, but the experiments use a 380M transformer trained from scratch by supervised imitation of A* traces, with no RL, no final-answer reward, and a domain-specific tokenizer. This is a legitimate model-organism design, but the leap from 'SFT trace imitation does not produce adaptive trace lengths' to 'R1's long traces are not thinking effort' is substantial. Please either (a) add an experiment in the same maze domain with RL or final-answer-reward training and show that the same loose correlation persists, or (b) explicitly restrict the conclusions to the SFT trace-imitation setting and adjust the abstract and Section 5 accordingly. The transfer assumption should be stated as an assumption, not as a consequence of the present experiments.
  4. [§4, data inclusion and validity] The manuscript does not specify whether the scatter plots include only semantically valid generated traces or all generations, and how failures are coded. Since a model that fails to solve a problem can still emit many tokens, mixing truncated and invalid responses into the same scatter can dominate the apparent relationship. The 'excessive length on trivial problems' finding, in particular, may be driven by degenerate repetition rather than by a calibrated length-difficulty relationship. Please report per-condition success rates, state inclusion criteria for scatter points, and analyze valid and invalid traces separately. This is needed to interpret the raw scatter plots and to assess the claim that trace length is not adaptive.
minor comments (6)
  1. [Title/header] The running title 'PERFORMATIVETHINKING?' is missing a space; should be 'PERFORMATIVE THINKING?'.
  2. [§3/§4.2] The maze-generation algorithm is referred to inconsistently as 'Searchformer-style' and 'SF-Style'. Use one name throughout.
  3. [§5] The phrase 'from-scratch computational complexity' is confusing; presumably 'from-scratch' modifies the model, not the complexity. Reword to avoid ambiguity.
  4. [Fig. 1a caption] The caption says 'Points at the top correspond to failures where the model generated tokens until reaching the 32k limit,' but the text does not say how many such points there are. A count or proportion would help.
  5. [§4.1] The phrase 'If there were a correlation, the generated trace lengths would closely match the ground-truth values' conflates correlation with calibration. Rephrase to distinguish correlation strength from agreement with the y=x line.
  6. [Appendix A.2] Training details are given, but there is no statement about code/data availability or a repository link. For reproducibility, please add this.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's empirical comparison uses an external A* trace-length benchmark, and the only in-distribution alignment is explicitly treated as approximate recall rather than independent evidence of adaptivity.

full rationale

The paper makes no formal derivation from inputs to conclusions; it is an empirical study. The model is trained from scratch to imitate A* traces on Wilson mazes, then evaluated on held-out mazes from other generators. The 'ground truth A* trace length' is an external, verifiable benchmark, not a parameter fitted to the model's outputs. The central negative finding—that trace length and A* trace length are loosely correlated OOD, and that the Wilson alignment reflects distributional proximity—is not forced by construction: the model could in principle have produced lengths matching A* trace lengths on OOD mazes if it had learned the algorithm, and the observed failure to do so is an empirical result. The in-distribution Wilson alignment is acknowledged in Section 4.2 as being due to the test instances being drawn from the training distribution ('approximate recall'), so the paper does not present a trained-in correlation as an independent confirmation of problem-adaptive computation. There are no self-citations used as load-bearing evidence, no uniqueness theorems imported from the authors, and no ansatz smuggled in via citation to prior work; the A* trace linearization is adopted from Lehnert et al. and Gandhi et al. as a methodological convention, not as a source of the conclusion. Concerns about missing correlation statistics and about whether a 380M supervised trace-imitation model transfers to DeepSeek R1 are external-validity or reporting issues, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to make a derivation work; this is an empirical study. The main postulates are domain assumptions about the model-organism setup and about how to operationalize problem complexity and distributional distance.

assumptions (4)
  • domain assumption A* with Manhattan distance on grid mazes is optimal, and its node-operation count is an appropriate formalization of problem difficulty.
    The paper equates problem difficulty with the number of A* operations (Section 3). This is a definitional choice, not proven equivalent to the actual computation required by the trained model.
  • domain assumption Small transformers trained from scratch on supervised A* traces are faithful model organisms for reasoning behavior of large models like R1.
    Invoked in Section 1 ('model organism' paradigm) and used in Sections 5-6 to draw conclusions about R1-style systems.
  • domain assumption Free-space problems with four layers of outer walls are trivial and should require minimal computation.
    Section 4.1 assumes these problems are the simplest case and uses their long traces to argue trace length is not adaptive.
  • domain assumption Maze-generation algorithm family is a sufficient proxy for distributional distance from training data.
    Sections 4.2 and 5 attribute correlation differences to distributional distance, but no distance measure is computed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexity." pith.science (2026). https://pith.science/paper/N5Q5IOPQ

@misc{pith2026250907339,
  author       = {Pith},
  title        = {Pith review of: Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N5Q5IOPQ}},
  note         = {Machine review of arXiv:2509.07339}
}
read the original abstract

Intermediate token generation (ITG), where a model produces output before the solution, has been proposed as a method to improve the performance of language models on reasoning tasks. While these reasoning traces or Chain of Thoughts (CoTs) are correlated with performance gains, the mechanisms underlying them remain unclear. A prevailing assumption in the community has been to anthropomorphize these tokens as "thinking", treating longer traces as evidence of higher problem-adaptive computation. In this work, we critically examine whether intermediate token sequence length reflects or correlates with problem difficulty. To do so, we train transformer models from scratch on derivational traces of the A* search algorithm, where the number of operations required to solve a maze problem provides a precise and verifiable measure of problem complexity. We first evaluate the models on trivial free-space problems, finding that even for the simplest tasks, they often produce excessively long reasoning traces and sometimes fail to generate a solution. We then systematically evaluate the model on out-of-distribution problems and find that the intermediate token length and ground truth A* trace length only loosely correlate. We notice that the few cases where correlation appears are those where the problems are closer to the training distribution, suggesting that the effect arises from approximate recall rather than genuine problem-adaptive computation. This suggests that the inherent computational complexity of the problem instance is not a significant factor, but rather its distributional distance from the training data. These results challenge the assumption that intermediate trace generation is adaptive to problem difficulty and caution against interpreting longer sequences in systems like R1 as automatically indicative of "thinking effort".

Figures

Figures reproduced from arXiv: 2509.07339 by the authors.

Figure 1
Figure 1. Comparison of generated intermediate token length (Y-axis) with ground-truth A* trace length (X-axis). The [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Comparison of trace length scatter plots for problems generated using Wilson and Searchformer Algorithms. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Example grid of a Free-space problem. It is a 30x30 grid with no obstacles in the inner grid. The start and [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Masked Distillation: Internalizing the Chain-of-Thought in Language Models

    cs.AI 2026-06 conditional novelty 5.0 of 10

    Masked distillation shows a student LLM can internalize its teacher's chain-of-thought on GSM8K but not on Countdown; emitting the last 30% of the trace as a 'suffix scaffold' recovers teacher-level accuracy with fewe...

Reference graph

Works this paper leans on

46 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [1]

    Training language models to reason efficiently, 2025.URL https://arxiv

    Daman Arora and Andrea Zanette. Training language models to reason efficiently, 2025.URL https://arxiv. org/abs/2502.04463

    arXiv 2025

  2. [2]

    Monitoring reasoning models for misbehavior and the risks of promoting obfuscation.arXiv preprint arXiv:2503.11926, 2025

    Bowen Baker, Joost Huizinga, Leo Gao, Zehao Dou, Melody Y Guan, Aleksander Madry, Wojciech Zaremba, Jakub Pachocki, and David Farhi. Monitoring reasoning models for misbehavior and the risks of promoting obfuscation.arXiv preprint arXiv:2503.11926, 2025

    arXiv 2025

  3. [3]

    Sparks of artificial general intelligence: Early experiments with gpt-4, 2023

    Sébastien Bubeck, Varun Chadrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4, 2023

    2023

  4. [4]

    Verithinker: Learning to verify makes reasoning model efficient.ArXiv, abs/2505.17941, 2025

    Zigeng Chen, Xinyin Ma, Gongfan Fang, Ruonan Yu, and Xinchao Wang. Verithinker: Learning to verify makes reasoning model efficient.ArXiv, abs/2505.17941, 2025

    arXiv 2025

  5. [5]

    Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars.arXiv preprint arXiv:2503.01307, 2025

    Kanishk Gandhi, Ayush Chakravarthy, Anikait Singh, Nathan Lile, and Noah D Goodman. Cognitive behaviors that enable self-improving reasoners, or, four habits of highly effective stars.arXiv preprint arXiv:2503.01307, 2025

    arXiv 2025

  6. [6]

    Stream of search (sos): Learning to search in language.arXiv preprint arXiv:2404.03683, 2024

    Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (sos): Learning to search in language.arXiv preprint arXiv:2404.03683, 2024

    arXiv 2024

  7. [7]

    Minillm: Knowledge distillation of large language models

    Yuxian Gu, Li Dong, Furu Wei, and Minlie Huang. Minillm: Knowledge distillation of large language models. arXiv preprint arXiv:2306.08543, 2023

    arXiv 2023

  8. [8]

    Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.arXiv preprint arXiv:2501.12948, 2025

    Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.arXiv preprint arXiv:2501.12948, 2025

    arXiv 2025

Show all 46 references
  1. [9]

    Don’t overthink it

    Michael Hassid, Gabriele Synnaeve, Yossi Adi, and Roy Schwartz. Don’t overthink it. preferring shorter thinking chains for improved llm reasoning.ArXiv, abs/2505.17813, 2025

    2025

  2. [10]

    Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes.arXiv preprint arXiv:2305.02301, 2023

    Cheng-Yu Hsieh, Chun-Liang Li, Chih-Kuan Yeh, Hootan Nakhost, Yasuhisa Fujii, Alexander Ratner, Ranjay Krishna, Chen-Yu Lee, and Tomas Pfister. Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes.arXiv preprint arXiv:23...

    2023 arXiv

  3. [11]

    Procedural dungeon generation: A drunkard’s walk in clojurescript

    jrheard. Procedural dungeon generation: A drunkard’s walk in clojurescript

  4. [12]

    On the shortest spanning subtree of a graph and the traveling salesman problem.Proceedings of the American Mathematical society, 7(1):48–50, 1956

    Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem.Proceedings of the American Mathematical society, 7(1):48–50, 1956

    1956

  5. [13]

    T\" ulu 3: Pushing frontiers in open language model post-training.arXiv preprint arXiv:2411.15124, 2024

    Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, et al. T\" ulu 3: Pushing frontiers in open language model post-training.arXiv preprint arXiv:2411.15124, 2024

    2024 arXiv

  6. [14]

    Beyond a*: Better planning with transformers via search dynamics bootstrapping.arXiv preprint arXiv:2402.14083, 2024

    Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mcvay, Michael Rabbat, and Yuan- dong Tian. Beyond a*: Better planning with transformers via search dynamics bootstrapping.arXiv preprint arXiv:2402.14083, 2024

    2024 arXiv

  7. [15]

    Llms can easily learn to reason from demonstrations structure, not content, is what matters!arXiv preprint arXiv:2502.07374, 2025

    Dacheng Li, Shiyi Cao, Tyler Griggs, Shu Liu, Xiangxi Mo, Eric Tang, Sumanth Hegde, Kourosh Hakhamaneshi, Shishir G Patil, Matei Zaharia, et al. Llms can easily learn to reason from demonstrations structure, not content, is what matters!arXiv preprint arXiv:2502.07374, 2025

    2025 arXiv

  8. [16]

    Aalc: Large language model efficient reasoning via adaptive accuracy-length control.ArXiv, abs/2506.20160, 2025

    Ruosen Li, Ziming Luo, Quan Zhang, Ruochen Li, Ben Zhou, Ali Payani, and Xinya Du. Aalc: Large language model efficient reasoning via adaptive accuracy-length control.ArXiv, abs/2506.20160, 2025

    2025 arXiv

  9. [17]

    Let’s verify step by step

    Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. InThe Twelfth International Conference on Learning Representations, 2023

    2023

  10. [18]

    Thought manipulation: External thought can be efficient for large reasoning models.ArXiv, abs/2504.13626, 2025

    Yule Liu, Jingyi Zheng, Zhen Sun, Zifan Peng, Wenhan Dong, Zeyang Sha, Shiwen Cui, Weiqiang Wang, and Xinlei He. Thought manipulation: External thought can be efficient for large reasoning models.ArXiv, abs/2504.13626, 2025

    2025 arXiv

  11. [19]

    s1: Simple test-time scaling.arXiv preprint arXiv:2501.19393, 2025

    Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. s1: Simple test-time scaling.arXiv preprint arXiv:2501.19393, 2025

    2025 arXiv

  12. [20]

    Show your work: Scratchpads for intermediate computation with language models

    Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. 2021. 5

    2021

  13. [21]

    Can transformers reason logically? a study in sat solving.arXiv preprint arXiv:2410.07432, 2024

    Leyan Pan, Vijay Ganesh, Jacob Abernethy, Chris Esposo, and Wenke Lee. Can transformers reason logically? a study in sat solving.arXiv preprint arXiv:2410.07432, 2024

    2024 arXiv

  14. [22]

    Let’s think dot by dot: Hidden computation in transformer language models.arXiv preprint arXiv:2404.15758, 2024

    Jacob Pfau, William Merrill, and Samuel R Bowman. Let’s think dot by dot: Hidden computation in transformer language models.arXiv preprint arXiv:2404.15758, 2024

    2024 arXiv

  15. [23]

    Grokking: Generalization beyond overfitting on small algorithmic datasets.arXiv preprint arXiv:2201.02177, 2022

    Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets.arXiv preprint arXiv:2201.02177, 2022

    2022 arXiv

  16. [24]

    Qwen2.5 technical report.arXiv preprint arXiv:2412.15115, 2024

    Qwen Team. Qwen2.5 technical report.arXiv preprint arXiv:2412.15115, 2024

    2024 arXiv

  17. [25]

    Sample more to think less: Group filtered policy optimization for concise reasoning, 2025

    Vaishnavi Shrivastava, Ahmed Awadallah, Vidhisha Balachandran, Shivam Garg, Harkirat Behl, and Dimitris Papailiopoulos. Sample more to think less: Group filtered policy optimization for concise reasoning, 2025

    2025

  18. [26]

    Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces

    DiJia Su, Sainbayar Sukhbaatar, Michael Rabbat, Yuandong Tian, and Qinqing Zheng. Dualformer: Controllable fast and slow thinking by learning with randomized reasoning traces. InThe Thirteenth International Conference on Learning Representations, 2024

    2024

  19. [27]

    Reinforcement learning in the era of llms: What is essential? what is needed? an rl perspective on rlhf, prompting, and beyond.arXiv preprint arXiv:2310.06147, 2023

    Hao Sun. Reinforcement learning in the era of llms: What is essential? what is needed? an rl perspective on rlhf, prompting, and beyond.arXiv preprint arXiv:2310.06147, 2023

    2023 arXiv

  20. [28]

    Depth-first search and linear graph algorithms.SIAM journal on computing, 1(2):146–160, 1972

    Robert Tarjan. Depth-first search and linear graph algorithms.SIAM journal on computing, 1(2):146–160, 1972

    1972

  21. [29]

    Grokked transformers are implicit reasoners: A mechanistic journey to the edge of generalization.arXiv preprint arXiv:2405.15071, 2024

    Boshi Wang, Xiang Yue, Yu Su, and Huan Sun. Grokked transformers are implicit reasoners: A mechanistic journey to the edge of generalization.arXiv preprint arXiv:2405.15071, 2024

    2024 arXiv

  22. [30]

    Chain-of-thought prompting elicits reasoning in large language models.Advances in neural information processing systems, 35:24824–24837, 2022

    Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models.Advances in neural information processing systems, 35:24824–24837, 2022

    2022

  23. [31]

    Generating random spanning trees more quickly than the cover time

    David Bruce Wilson. Generating random spanning trees more quickly than the cover time. InProceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 296–303, 1996

    1996

  24. [32]

    Chain of thought imitation with procedure cloning.Advances in Neural Information Processing Systems, 35:36366–36381, 2022

    Mengjiao Sherry Yang, Dale Schuurmans, Pieter Abbeel, and Ofir Nachum. Chain of thought imitation with procedure cloning.Advances in Neural Information Processing Systems, 35:36366–36381, 2022

    2022

  25. [33]

    Understanding aha moments: from external observations to internal mechanisms.arXiv preprint arXiv:2504.02956, 2025

    Shu Yang, Junchao Wu, Xin Chen, Yunze Xiao, Xinyi Yang, Derek F Wong, and Di Wang. Understanding aha moments: from external observations to internal mechanisms.arXiv preprint arXiv:2504.02956, 2025

    2025 arXiv

  26. [34]

    Dapo: An open-source llm reinforcement learning system at scale.arXiv preprint arXiv:2503.14476, 2025

    Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Tiantian Fan, Gaohong Liu, Lingjun Liu, Xin Liu, et al. Dapo: An open-source llm reinforcement learning system at scale.arXiv preprint arXiv:2503.14476, 2025

    2025 arXiv

  27. [35]

    Efficient rl training for reasoning models via length-aware optimization.ArXiv, abs/2505.12284, 2025

    Danlong Yuan, Tian Xie, Shaohan Huang, Zhuocheng Gong, Huishuai Zhang, Chong Luo, Furu Wei, and Dongyan Zhao. Efficient rl training for reasoning models via length-aware optimization.ArXiv, abs/2505.12284, 2025

    2025

  28. [36]

    Free process rewards without process labels.arXiv preprint arXiv:2412.01981, 2024

    Lifan Yuan, Wendi Li, Huayu Chen, Ganqu Cui, Ning Ding, Kaiyan Zhang, Bowen Zhou, Zhiyuan Liu, and Hao Peng. Free process rewards without process labels.arXiv preprint arXiv:2412.01981, 2024

    2024 arXiv

  29. [37]

    Star: Bootstrapping reasoning with reasoning

    Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476–15488, 2022

    2022

  30. [38]

    Automatic chain of thought prompting in large language models.arXiv preprint arXiv:2210.03493, 2022

    Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models.arXiv preprint arXiv:2210.03493, 2022

    2022 arXiv

  31. [39]

    The clock and the pizza: Two stories in mechanistic explanation of neural networks.Advances in neural information processing systems, 36:27223–27250, 2023

    Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas. The clock and the pizza: Two stories in mechanistic explanation of neural networks.Advances in neural information processing systems, 36:27223–27250, 2023

    2023

  32. [40]

    aha moment

    Hengguang Zhou, Xirui Li, Ruochen Wang, Minhao Cheng, Tianyi Zhou, and Cho-Jui Hsieh. R1-zero’s" aha moment" in visual reasoning on a 2b non-sft model.arXiv preprint arXiv:2503.05132, 2025. 6 A Appendix A.1 Maze Generation Algorithms We generate navigation problems using diver...

    2025 arXiv

  33. [41]

    Wilson’s algorithm generates uniform random mazes by performing loop-erased random walks from unvisited cells until they connect to the current maze [ 31]

    Wilson’s algorithm:This is the algorithm that we use to generate mazes for training models. Wilson’s algorithm generates uniform random mazes by performing loop-erased random walks from unvisited cells until they connect to the current maze [ 31]. Each walk removes any loops i...

  34. [42]

    This results in a fully connected maze without loops, though the maze distribution is not perfectly uniform

    Kruskal’s algorithm:Kruskal’s algorithm, originally proposed for finding a minimum spanning forest of an undirected edge-weighted graph [12], generates mazes by treating each cell as a node and randomly removing walls between unconnected regions, using a union–find structure t...

  35. [43]

    When it hits a dead-end (no unvisited neighbors), it backtracks until it finds a new direction to explore, repeating until all cells are visited and connected into a complete maze

    Randomized Depth-First Search algorithm:The randomized depth-first search (DFS) or recursive back- tracker algorithm generates mazes by carving a path forward until reaching a dead-end [28]. When it hits a dead-end (no unvisited neighbors), it backtracks until it finds a new d...

  36. [44]

    Drunkard’s Walk

    Drunkard’s Walk:We implement a version of the “Drunkard’s Walk” algorithm, as described by [11], and originally used for procedurally generating dungeons for top-down two-dimensional video games. Starting from a grid of solid walls, a random walk is performed, carving out the ...

  37. [45]

    Tasks are generated by exhaustive rejection sampling: first, randomly select a number between 30% and 50%

    Searchformer style generation:We also implement the random generation algorithm used in the Searchformer paper [14], though we use it for evaluation rather than training. Tasks are generated by exhaustive rejection sampling: first, randomly select a number between 30% and 50%....

  38. [46]

    In our case, we chose the number of levels of outer walls to be 4

    Free-space algorithm:In this algorithm, we first select the number of levels of outer walls. In our case, we chose the number of levels of outer walls to be 4. Within the inner grid, a start cell and a goal cell are then chosen randomly, with no walls placed in the inner grid....

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.