Optimal Hitting Time in Markov Chains with Rewinding: A Theoretical Framework for LLM Test-Time Computation

We study the optimal hitting-time problem in Markov chains with rewinding [Azarmehr et al., 2026], motivated by verifier-guided test-time computation. Originally introduced in the study of lower bounds for sublinear-time graph algorithms, Markov chains with rewinding provide a natural model for the interaction between an algorithmic agent and randomness: 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. This model further extends value-guided backtracking [Rohatgi et al., 2025], which implements backtracking through a verifier-guided random walk on the tree of partial generations. Large language models (LLMs) can often produce substantially better outputs when allowed to use additional test-time computation through methods 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 test-time computation should be structured, or what constitutes an optimal use of budget. Many widely used test-time methods, including 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 fully characterize the optimal strategy in this model and show that it 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. We also construct Markov chains in which backtracking yields an exponential reduction in the number of generations, as well as instances in which adversarial verifier noise causes an exponential slowdown. Guided by the structure of the optimal strategy and these hard instances, we introduce a heuristic which we call 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.