Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models

Amir Azarmehr; Soheil Behnezhad; Alma Ghafari

cs.LGMar 24, 2026

Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models

Authors: Amir Azarmehr, Soheil Behnezhad, Alma Ghafari

Organizations: Northeastern University

Abstract

Large language models (LLMs) can often produce substantially better outputs when allowed to use additional test-time computation, such as sampling, chain of thought, backtracking, or revising partial solutions. Despite the growing empirical success of such techniques, there is limited theoretical understanding of how inference time computation should be structured, or what constitutes an optimal use of a fixed computation budget. We model test-time computation as an algorithm interacting with a Markov chain: at any point, the algorithm may resume generation from any previously observed state. That is, unlike standard Markov chains where the states are drawn passively, we allow the algorithm to backtrack to any previously observed state of the Markov chain at any time. Many of the existing test-time algorithms, such as Chain-of-Thought (CoT) (Wei et al., 2023), Tree-of-Thoughts (ToT) (Yao et al., 2023), or Best-of- $k$ (Brown et al., 2024) could be seen as specific algorithms in this model. We prove that while backtracking can reduce the number of generations exponentially, a very limited form of backtracking is theoretically sufficient. Namely, we show that the optimal algorithm always generates a caterpillar tree. That is, if we remove the leaves of the state tree generated by the optimal algorithm, we obtain a path. Motivated by our characterization of the optimal algorithm, we present Caterpillar of Thoughts (CaT), a new test-time computation algorithm, reducing the number of token/state generations. Our empirical evaluation shows that CaT, compared to ToT, achieves a better success rate while also reducing the number of token generations.

Figures & tables

Panel of Figure 1 — Figure 1: A Markov chain where rewinding is crucial, consisting of $n+1$ states $x_{0}\rightarrow x_{1}\rightarrow\ldots\rightarrow x_{n}$ on a path, and one dummy state $D$ . The arrows denote the transition probabilities. The first state on the path, $x_{0}$ , is the starting point of the algorithm, and the last state, $x_{n}$ , is the target state.

Panel of Figure 2 — Figure 2: This figure illustrates the tree explored by two different algorithms, with Figure 1 being the input Markov chain. White circles represent state $D$ , and green states represent the optimal path to the target state. The right side tree represents the explored tree by CaT, and the left side tree represents a BFS-like algorithm that expands without pruning the dummy state.

Method	Success Rate(%)	Avg. Tokens
Tree-of-Thoughts
( Yao et al., 2023 )	74	19.2k
CaT
(15 steps)	81	15.3k
CaT
(10 steps)	78	14.2k

Table 1: Performance comparison on the Game of 24 benchmark. Tree-of-Thoughts uses a beam size of

5

. The proposed method reports best of

2

runs, for maximum budget of iterations (steps) set to be

10

and

15

. By tokens in this table we mean sum of generated tokens and prompt tokens.

\Pr[x^{*}]\propto\exp(-\widehat{\mathsf{O}}(x^{*}))

Algorithm 4 Caterpillar of Thoughts (via softmax)

Figure 3: Illustration shows log linear relation between number of valid expressions and number of steps.

Method	Word Acc. (%)	Letter Acc. (%)	Games Solved (%)	Avg. Tokens
ToT ( Yao et al., 2023 )	39.5	64.8	5	73.4k
CaT ( This paper )	50.0	68.6	15	66.8k

Table 2: Performance on the

5\times 5

crossword benchmark: cost matched ToT vs. CaT.

Explore similar work

Sep 13, 2026

State of Thought Enables Endogenous Reasoning

Test-time compute has emerged as a major approach to improving the capabilities of Large Language Models (LLMs). However, existing test-time reasoning paradigms rely heavily on externally imposed control, either through fixed reasoning programs or through costly expansion in constrained search spaces, limiting both generalization and efficiency. We propose State of Thought (SoT), a new reasoning paradigm that enables endogenous reasoning in LLMs, with the model's internal reasoning state governing how reasoning unfolds. Concretely, SoT extracts a compact dynamics-geometric state from the model's internal information transfer and uses a 582-parameter controller on frozen backbones to selectively activate historical reasoning support useful under the current reasoning state, framing reasoning as a state-conditioned process over evidence rather than an externally prescribed token chain. Across quantitative (1.34x), general (1.62x), symbolic-and-code (1.76x), and long-context (2.51x) reasoning on 3 LLMs and 16 datasets, SoT consistently improves mean-baseline accuracy while reducing generated tokens by 62.6% and end-to-end latency by 44.6%. Across 2 VLM scales and 3 reasoning tasks, it improves mean accuracy by 3.8 points over reasoning baselines, with 74.9% fewer completion tokens and 73.5% lower latency than search-based methods. Under constrained access, SoT retains 38.2%/36.5% mean accuracy gains in training-free/embedding-only settings, while trajectory-only judging reaches 84.1% agreement across 3 API models. Together, endogenous state-driven reasoning provides a generalizable and efficient alternative.

Zhiren Gong, Yikun Hou, Zihao Zeng +3

College of Computing and Data Science, Nanyang Technological University, Singapore · Interdisciplinary Graduate Programme, Nanyang Technological University, Singapore · Information Science & Engineering, KTH Royal Institute of Technology, Sweden +1

Efficient Language Model Reasoning Implicit Reasoning in Language Models LLM Inference Acceleration

Ask PDF

Apr 12, 2026

When More Thinking Hurts: Overthinking in LLM Test-Time Compute Scaling

Scaling test-time compute through extended chains of thought has become a dominant paradigm for improving large language model reasoning. However, existing research implicitly assumes that longer thinking always yields better results. This assumption remains largely unexamined. We systematically investigate how the marginal utility of additional reasoning tokens changes as compute budgets increase. We find that marginal returns diminish substantially at higher budgets and that models exhibit ``overthinking'', where extended reasoning is associated with abandoning previously correct answers. Furthermore, we show that optimal thinking length varies across problem difficulty, suggesting that uniform compute allocation is suboptimal. Our cost-aware evaluation framework reveals that stopping at moderate budgets can reduce computation significantly while maintaining comparable accuracy.

Shu Zhou, Rui Ling, Junan Chen +3

Nanjing University · Baidu · Nanjing University of Finance & Economics

Overthinking in Language Models Test-Time Scaling Efficient Language Model Reasoning

Ask PDF

Aug 31, 2026

When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models

As pretraining scaling laws approach saturation, Test-Time Scaling (TTS) has emerged as an important direction for improving reasoning by allocating inference-time compute to a fixed model prior. Viewed at a high level, TTS reframes inference as search over a space of partial reasoning states. While Chain-of-Thought (CoT) exposes intermediate steps, common instantiations rely on single-trajectory decoding, limiting recovery from early errors and exploration. This survey systematizes recent progress in tree-search-based reasoning, viewing inference as instance-specific optimization rather than decoding. We trace the evolution from uninformed search to Monte Carlo Tree Search (MCTS), highlighting how sampling-based control supports principled exploration-exploitation trade-offs. To unify a fragmented literature, we introduce a Unified Design Space spanning search topology, evaluation signals, and control dynamics, and advocate a standardized compute-reporting abstraction to make compute-accuracy trade-offs explicit and comparable.

Jiaqi Wei, Xiang Zhang, Yuejin Yang +10

1Zhejiang University · 2Shanghai AI Laboratory · 4Fudan University +3

Inference-Time Search Inference-Time Scaling Monte Carlo Tree Search LLM Reasoning

Ask PDF