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

arXiv: https://arxiv.org/abs/2603.22784 · HTML: https://mlsanity.com/paper/2603.22784/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 14 of its 18 references that are in the map.
- First posted on arXiv 24 Mar 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 14 of 14)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Generalized Interpolating Discrete Diffusion](https://mlsanity.com/paper/2503.04482/) (2025)
- [Ensembling Large Language Models with Process Reward-Guided Tree Search for Better Complex Reasoning](https://mlsanity.com/paper/2412.15797/) (2024)
- [Recursive Self-Aggregation Unlocks Deep Thinking in Large Language Models](https://mlsanity.com/paper/2509.26626/) (2025)
- [Step Back to Leap Forward: Self-Backtracking for Boosting Reasoning of Language Models](https://mlsanity.com/paper/2502.04404/) (2025)
- [Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking](https://mlsanity.com/paper/2510.03149/) (2025)
- [Value-Guided Search for Efficient Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.17373/) (2025)
- [On the Query Complexity of Verifier-Assisted Language Generation](https://mlsanity.com/paper/2502.12123/) (2025)
- [Markov Chains with Rewinding](https://mlsanity.com/paper/2602.16028/) (2026)

## Abstract (arXiv)

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.