- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies verifier-guided test-time computation through fully observable Markov chains with rewinding. At each step, an algorithm may resume generation from any previously observed state, with the objective of minimizing the expected number of generated states before reaching a target. The main theoretical result shows that, given exact access to the optimal hitting time (OPT(x)), an optimal strategy is non-branching: it repeatedly samples from the current best state and replaces it whenever a newly generated state has smaller (OPT), producing a caterpillar-shaped exploration tree. The paper also gives a Dijkstra-like algorithm for computing (OPT), shows that rewinding can yield exponential savings, and studies independent Laplace noise and adversarial multiplicative noise. Empirically, a softmax-based heuristic, Caterpillar of Thoughts (CaT), is compared against Tree-of-Thoughts on Game of 24 and 5×5 crosswords.
Critical strengths
The paper provides a clean theoretical formulation and a simple structural characterization of optimal test-time computation. Modeling different inference-time strategies as rewinding policies over a common Markov chain is conceptually useful. The identity $ OPT(S)=\min_{x\in S}OPT(x) $ gives a clear message: under exact value information, maintaining multiple frontier states provides no benefit, and a width-one non-branching strategy is optimal.
The exact computation and noise analyses provide useful theoretical benchmarks. Algorithm 2 makes exactly computable on small chains, while the exponential separation between rewinding and non-rewinding search highlights the potential benefit of backtracking. The comparison between stochastic and adversarial verifier noise is also informative.
Critical weaknesses
-
The theoretical objective does not directly match the fixed-budget problem motivating the paper. The theory minimizes the expected number of steps required to eventually reach the target. However, the paper motivates test-time computation as a fixed-budget problem, and the experiments measure whether a solution is found within a fixed number of iterations.These are different objectives. A strategy with a smaller expected hitting time does not necessarily have a higher probability of success within a particular budget. Under a finite budget, the best decision may also depend on how much budget remains, whereas the optimal policy in Theorem 3.3 depends only on the current observed states. Therefore, the main theoretical result does not directly establish that the caterpillar strategy is optimal for the fixed-budget setting used in the experiments. It would be helpful to clarify this distinction or analyze the finite-budget objective directly.
-
The experiments do not directly validate the central theoretical claims. The theory characterizes Algorithm 1 under exact and Algorithm 3 under independent Laplace noise. However, neither algorithm is evaluated experimentally. Instead, Section 5 uses Algorithm 4, which samples a parent from all observed states according to
Unlike Algorithms 1 and 3, this procedure can branch at arbitrary nodes and does not generally produce a caterpillar.
The paper argues that this softmax variant is more robust to estimation error, but this claim is neither theoretically established nor directly evaluated. A simple synthetic experiment could compute exact using Algorithm 2, inject controlled noise, and compare Algorithms 1, 3, and 4 against BFS, beam search, or VGB. This would directly test when the caterpillar strategy is optimal, how it degrades under noise, and whether softmax branching actually improves robustness.
-
The verifier and transition models are substantially idealized relative to realistic LLM test-time computation. The positive noise result assumes repeated independent, unbiased Laplace observations. This is substantially stronger than what one would expect from LLM-based verifiers. Their errors can be systematically biased toward proxies such as plausibility or local consistency, and repeated evaluations of the same state are unlikely to be independent. Averaging may therefore reduce sampling variance without removing systematic error. More fundamentally, the Markov model assumes that once a state is selected, the next state is sampled from a fixed distribution that depends only on that state. Thus, the algorithm can decide where to rewind, but not change how generation proceeds from the selected state based on previous attempts. Many practical test-time methods instead use failed attempts, feedback, or revised prompts to modify subsequent generations. In such settings, the history itself can contain useful information, whereas Lemma 3.1 relies on transition probabilities being independent of that history. The experimental implementation also generates multiple children from a selected parent, with the number of children determined by the language model. It would be helpful to clarify how this procedure corresponds to the single-transition model assumed by the theory.
-
Several inconsistencies should be corrected.
- Lemma 4.4 says “with probability ” instead of “with probability at least .”
- In the proof of Theorem 1.1, “ is changed to ” should be “changed to .”
- Definition 4.2 appears to use where is intended.
The threshold argument in Theorem 4.5 appears to require revision. Under condition (4), both estimates can have error , so their difference may have error up to . Algorithm 3 switches when
Therefore, guaranteed acceptance requires
not merely .
It seems the proof could potentially be repaired by using , which would change the constant factor but not obviously the asymptotic result. However, the current argument does not justify the stated step bound.
Questions for authors
Could the authors compare Algorithms 1, 3, and 4 on synthetic chains where exact can be computed using Algorithm 2? This would directly test how the theoretically optimal caterpillar strategy behaves under estimation error and whether softmax branching actually improves robustness.
How exactly are the LLM evaluator scores converted into ? Are these scores intended to estimate the expected remaining hitting time or the probability that a state eventually leads to a correct answer? If the latter, why should they induce the same state ordering as ?
The theory minimizes expected hitting time, while the experiments evaluate success under a fixed iteration budget. Does the caterpillar optimality result still hold when the objective is to maximize the probability of reaching the target within a fixed budget?
Can the analysis be extended to more realistic verifier errors, such as biased or correlated estimates? More generally, what changes if repeated generations from the same state depend on previous failures or feedback rather than being independent samples from a fixed ?.
2 comments
Thank you for revising the proof and adding the controlled experiments in Appendix C. These changes address several errors I raised and clarify when softmax selection can help under noisy evaluations. My main concern remains the connection between the theoretical results and the LLM experiments. The new experiments use noisy estimates of the optimal hitting time, while the LLM tasks use heuristic scores. It is still unclear how much of the improvement on those tasks comes from the proposed selection rule. I therefore maintain my Weak Reject rating. I encourage the authors to strengthen this connection in a revision for a future submission.
Thank you for recognizing the structural characterization that we developed.
W1 and Q3:
These are different objectives. Theorem 1.1 minimizes the expected hitting time, E[T]. It does not establish that Algorithm 1 maximizes Pr(T≤B) for every budget B. For the latter objective, the best decision can depend on the remaining budget.
For example, consider a chain where r transitions to the target z with probability 0.4 and to b with probability 0.6, followed by deterministic transitions b→c→z. Here, O(r)=2.2 and O(b)=2, so Algorithm 1 continues from b after observing it. Its success probability within two steps is 0.4. Rewinding to r after the first failure instead gives success probability 1−0.62=0.64.
To examine this distinction experimentally, we added an exact finite-budget reference to the synthetic comparisons. It uses dynamic programming over the observed set and the remaining budget to maximize success probability. This allows us to compare Algorithm 1 with the optimal fixed-budget policy on the chosen chains. Their close performance in these examples is an empirical observation; our optimality guarantee remains specific to expected hitting time.
W2 and Q1. We added synthetic experiments in Appendix C to directly evaluate Algorithms 1, 3, and 4. We use ten finite Markov chains with known transition probabilities, compute exact rewinding values using Algorithm 2, and compare the algorithms with greedy, uniform, BFS, and beam-search baselines under exact scores and independent Laplace noise of scales 1 and 4. Algorithm 1 remains an exact-oracle reference. We also vary softmax temperature and whether scores are cached or refreshed.
At 32 generated transitions, averaged over the ten chains, Algorithm 1 achieves 97.6% success with exact values, compared with 95.5% for Algorithm 4. Under noise of scale 1, softmax improves success from 60.6% for cached noisy greedy to 85.2%. Cached noisy greedy follows Algorithm 1’s strict-improvement rule using one stored noisy score per state. Softmax uses the same observation and caching model but can select states despite unfavorable scores. Its advantage is conditional: at scale 4, beam search performs better. Algorithm 3 stays close to the exact reference through repeated evaluations, whose costs we report separately.
These experiments directly test the algorithms under controlled assumptions. Algorithm 4 may branch and does not inherit Algorithm 1’s optimality guarantee; the results support a conditional benefit of softmax selection rather than a general robustness claim for the LLM implementation.
W4. Errors mentioned have been addressed in the write-up.
Q2. The LLM scores are heuristic utilities, denoted by u(s), rather than calibrated estimates of O(s) or success probabilities. This is what ToT does as well.
Q4. Some extensions are possible under explicit error bounds. The drift proof for Algorithm 3 only needs the difference D between the two estimation errors to satisfy $ E[|D|\mid\text{history},x,g]\le\beta<\tfrac12. $ Under the same finite-value and fixed-transition assumptions, this gives
\frac{O(x_0)}{1/2-\beta}.$$ This permits some biased or correlated estimates, but averaging alone does not guarantee the required bound or remove systematic bias.