acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning theory
Keywords:
Markov chains, Hitting time, Markov chians with Rewinding

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_a1cCOpenReview ↗
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 OPTOPT 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
  1. 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.

  2. The experiments do not directly validate the central theoretical claims. The theory characterizes Algorithm 1 under exact OPTOPT 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

    P(x)∝exp⁡(−O^(x)).P(x)\propto \exp(-\hat O(x)).

    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 OPTOPT 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.

  3. 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 P(x,⋅)P(x,\cdot) 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 g∼P(x,⋅)g\sim P(x,\cdot) assumed by the theory.

  4. Several inconsistencies should be corrected.

    • Lemma 4.4 says “with probability δ\delta” instead of “with probability at least 1−δ1-\delta.”
    • In the proof of Theorem 1.1, “x∗x^* is changed to SS” should be “changed to gg.”
    • Definition 4.2 appears to use O(x)O(x) where O(x∗)O(x^*) is intended.

    The threshold argument in Theorem 4.5 appears to require revision. Under condition (4), both estimates can have error 0.10.1, so their difference may have error up to 0.20.2. Algorithm 3 switches when

    Xg<Xx∗−0.5.X_g<X_{x^*}-0.5.

    Therefore, guaranteed acceptance requires

    O(g)<O(x∗)−0.7,O(g)<O(x^*)-0.7,

    not merely O(g)<O(x∗)−0.5O(g)<O(x^*)-0.5.

    It seems the proof could potentially be repaired by using c=0.7c=0.7, which would change the constant factor but not obviously the asymptotic result. However, the current argument does not justify the stated 2OPT(x0)2OPT(x_0) step bound.

Questions for authors

Could the authors compare Algorithms 1, 3, and 4 on synthetic chains where exact OPTOPT 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 O^(x)\hat O(x)? 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 OPT(x)OPT(x)?

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 P(x,⋅)P(x,\cdot)?.

2 comments

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]E[T]. It does not establish that Algorithm 1 maximizes Pr⁡(T≤B)\Pr(T\le B) for every budget BB. For the latter objective, the best decision can depend on the remaining budget.

For example, consider a chain where rr transitions to the target zz with probability 0.40.4 and to bb with probability 0.60.6, followed by deterministic transitions b→c→zb\to c\to z. Here, O(r)=2.2O(r)=2.2 and O(b)=2O(b)=2, so Algorithm 1 continues from bb after observing it. Its success probability within two steps is 0.40.4. Rewinding to rr after the first failure instead gives success probability 1−0.62=0.641-0.6^2=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 11 and 44. Algorithm 1 remains an exact-oracle reference. We also vary softmax temperature and whether scores are cached or refreshed.

At 3232 generated transitions, averaged over the ten chains, Algorithm 1 achieves 97.6%97.6\% success with exact values, compared with 95.5%95.5\% for Algorithm 4. Under noise of scale 11, softmax improves success from 60.6%60.6\% for cached noisy greedy to 85.2%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 44, 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)u(s), rather than calibrated estimates of O(s)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 DD 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.

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.

Reviewer_7wZhOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This work formulates the hitting times in Marvov chains as a model of verifier-guided test-time computation, and provides an algorithm that optimally converge to the target state. The algorithm can either resample from any previously observed state, or continue to generate new states. The main contributions are: 1. given access to the optimal hitting time function a greedy non-branching rule is optimal (Thm 1.1, Thm 3.3); 2. on a path chain with an absorbing dead state, rewinding needs 2n2n steps, while restart-only strategies need Ω(2n)\Omega(2^n); 3. With independent Laplace-noisy queries of OO, a thresholded variant reaches zz at cost O(λ2O(x0)log⁡O(x0))O(\lambda^2 O(x_0)\log O(x_0)) (Thm 4.5). With adversarial (1±ε)(1\pm\varepsilon)-multiplicative errors, any algorithm needs exp⁡(O(x0))\exp(O(x_0)) steps (Thm 4.6).

Critical strengths

The question that "what is the optimal way to spend a budget when you can rewind?" is well posed. The caterpillar structure is elegant. The fixed-point characterization with the Dijkstra-like algorithm (Cor 3.5, Alg 2) is a nice self-contained result. Code is released.

Critical weaknesses

My main concern is that the headline claims are considerably broader than what is proved and tested.

  • "A theoretical framework for LLM test-time computation" / "we fully characterize the optimal strategy." -- The characterization assumes exact access to O(⋅)O(\cdot), or full knowledge of PP and zz. But OO is the value function of the very problem being solved, so it is unsurprising that acting greedily on the exact value function is optimal. The real contribution is the structural statement that one minimizer suffices. For an LLM, PP is unknown and estimating OO is the whole difficulty. Section 3 is therefore a planning result, not a test-time inference result. Additionally, Alg 2 needs PP over all of Ω\Omega, which for token prefixes is of size ∣A∣H|\mathcal A|^H.

  • Thm 3.3 only shows that an optimal non-branching algorithm exists. When OO has ties, rewinding to any minimizer is equally optimal, so branching optimal strategies exist too. The claim should read "there exists an optimal strategy that…".

  • "Our framework generalizes VGB". This is an overstatement. VGB (Rohatgi et al., 2025) aims to sample from a verifier-tilted distribution, with robustness guarantees. It does not minimize hitting time. In VGB, a move to the parent generates no new state. In this model, every step draws a fresh state from P(xt′,⋅)P(x_{t'},\cdot). Furthermore, VGB’s kernel is reweighted by the verifier, so embedding it changes PP itself.

  • In Theorem 4.5, With ∣X−O∣≤1/10|X-O|\le 1/10 and the rule Xg<Xx∗−1/2X_g < X_{x^\ast}-1/2, replacement is guaranteed only when O(g)<O(x∗)−0.7O(g) < O(x^\ast)-0.7. The proof instead asserts that the stable algorithm "replaces x∗x^\ast by gg when g∈Lg\in L", where L={O(g)<O(x∗)−1/2}L=\{O(g)<O(x^\ast)-1/2\}. Children with O(g)∈[O(x∗)−0.7, O(x∗)−0.5)O(g)\in[O(x^\ast)-0.7,\,O(x^\ast)-0.5) may not be replaced. The step "combining the two implies O′′(x)≤O′(x)O''(x)\le O'(x)" needs O′(y)≤O′(x)O'(y)\le O'(x) for y∈My\in M. This is neither shown nor true in general. O′O' need not be monotone in OO. Lemma 4.3 only gives O′(y)≤(1+ε)O(y)O'(y)\le(1+\varepsilon)O(y), while O(y)O(y) can be arbitrarily close to O(x)O(x).

  • The proof of THeorem 4.6 establishes Ω(Δεd)=Ω(2d)\Omega(\Delta^{\varepsilon d})=\Omega(2^d) with O(x0)=10⋅21/εdO(x_0)=10\cdot 2^{1/\varepsilon}d. That is exp⁡(O(x0)ln⁡2/(10⋅21/ε))\exp\big(O(x_0)\ln 2/(10\cdot 2^{1/\varepsilon})\big), not the Ω(2O(x0))\Omega(2^{O(x_0)}) claimed in the proof. The constant in the exponent decays exponentially in 1/ε1/\varepsilon, so the bound is weakest exactly in the accurate-verifier regime. Please state this dependence explicitly. "Partially observable Markov chain" is never defined. What does the algorithm know: PP, the tree, zz?

  • Alg 4 is neither Alg 1 nor Alg 3. It samples a parent from all observed states via a softmax, so the explored tree is not a caterpillar, despite Fig. 1b. No guarantee is given for it. Alg 3, the only algorithm with a noisy-oracle guarantee, is never evaluated. Alg 4 is essentially stochastic best-first search over the frontier, a standard heuristic, and its only link to the theory is "prefer smaller O^\hat O". Thus, I think the experiments do not test the theory, and the comparisons are not matched. Additionally, there are no ablations: temperature, number of children, Algorithm 1 vs. 4, or verifier quality.

  • There is a lingering confusion with the notation of OPT/O/opt(⋅\cdot). Alg 1 uses opt(⋅)\mathrm{opt}(\cdot) while the text uses OO/OPT\mathsf{OPT}. This reduces readability.

Questions for authors

Though I believe this paper needs serious rewriting before it becomes ready for publication, it has technical flaws and experiment mismatches. But I have a few additional questions for the authors. I list them below:

  • The model comes from Azarmehr et al. (2026). Can you please state exactly which results in Sections 3–4 are new relative to that paper?
  • Can you fix both gaps in Thm 4.5 and address the relative-noise case, where children can have O(g)≫O(x0)O(g)\gg O(x_0) or O(g)=∞O(g)=\infty?
  • What stopping criterion does CaT use in crosswords, and is ground truth involved?
  • Can anything be proved about Alg 4, for example a bound relative to OPT under Laplace noise, or as the temperature goes to 0?
1 comment

We thank the reviewer for a careful read and many helpful comments. We have clarified the paper's scope.

We agree that Section 3 provides a structural planning characterization whose implementation assumes exact value access. We also explicitly state that Algorithm 2 requires the full transition matrix and will run in linear time in the number of states, which is exponential in the token horizon. The LLM connection motivates the model and the practical heuristic used to estimate O(.); it does not imply that Algorithm 2 is computationally feasible for LLM state spaces.

Theorems 4.5 and 4.6 have been revised to avoid the error, and we have removed discussion about the VGB, as its kernel changes over time and does not connect to this result.

We have added experiments on syntactic Markov chains. The experiments support picking the minimum when scores are accurate, and keeping some exploration when scores are noisy.

Q1: Azarmehr et al. define the Markov chain with rewinding model and study the state identification problem: that is, given two candidates A and B and some observations of the Markov chain (let's say sink and non-sink), identify the starting state? We, on the other hand, in the same model, study the hitting time algorithm for a given target state.

Q2: We have replaced the proof of Theorem 4.5 with a direct drift argument that avoids both gaps identified by the reviewer. We directly account for the estimation errors in the acceptance decision. The mean-median estimates bound the expected absolute difference of the two estimation errors by 1/101/10. Together with the exact-value identity from Corollary 3.5, this gives an expected decrease in the optimal hitting-time value of at least 2/52/5 per iteration. Consequently, E[T]≤(5/2)O(x0).E[T] \le (5/2) O(x_0). For the relative-noise case, we agree that the value of a newly generated child need not be bounded by the value of the initial state. The original corollary therefore did not justify its evaluation-cost bound. We have removed that corollary and restricted the revised theorem to a common, state-independent noise scale. We also explicitly assume that every reachable state has finite optimal hitting time, so states with O(g)=∞O(g)=\infty are outside this theorem. These changes correct the scope of the result; we do not claim to have established the relative-noise extension.

Q3: We have a parameter set = 20, which is the number of times we run the for loop; after that, we stop.

Q4: We have added an analysis of Algorithm 4 in Appendix D. For a finite chain with nn states, if all score errors are almost surely bounded by η\eta, we prove

\frac{OPT}{1-2\eta-\tau\log n}, \qquad 2\eta+\tau\log n<1.$$ In particular, with exact scores,

OPT \le E[T_\tau] \le\frac{OPT}{1-\tau\log n}.

Thus Algorithm 4’s expected hitting time converges to $OPT$ as the temperature tends to zero. For independent Laplace observations, however, decreasing the temperature need not recover optimal performance. We give a three-state counterexample, $r\to g\to z$, with $OPT=2$, for which Algorithm 4 has infinite expected hitting time whenever $0<\tau\le\lambda$, where $\lambda$ is the Laplace scale. An unlucky cached score can make the useful state extremely unlikely to be selected, even though the algorithm eventually succeeds almost surely. This rules out a general finite approximation guarantee in that regime.
Reviewer_RERGOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies target hitting time in a finite, fully observable Markov chain where an algorithm may resume sampling from any previously observed state. Its central result shows that, given exact optimal remaining hitting times O(s)O(s), an optimal strategy always expands a state with the smallest O(s)O(s); the resulting search tree has a caterpillar structure. The paper also gives an algorithm to compute these values, studies the benefit of rewinding and noisy value estimates, and proposes a practical softmax search heuristic, CaT, evaluated on Game of 24 and crosswords.

Critical strengths

1, The exact-oracle result is a clean and potentially useful characterization of optimal search in the stated model.

2, The Dijkstra-like computation of O(s)O(s) and the exponential separation illustrating the value of rewinding add substance to the theoretical contribution.

3, The practical search rule is simple, and the reported success rates and token counts are promising.

Critical weaknesses

1. The state-dependent-noise claim in Theorem 4.5 appears unsupported.

Definition 4.1, Lemma 4.4, and the proof of Theorem 4.5 use a common Laplace noise scale lambda. The “in particular” statement instead assumes a state-dependent scale lambda(s) = alpha * O(s), but the proof substitutes lambda = alpha * O(x_0) for every queried state. Algorithm 3 also estimates the value of newly sampled states, whose O(s) may be arbitrarily larger than O(x_0).

For example, let x_0 transition with equal probability to the target z or a state y. From y, the probability of reaching z is q < 1/2; otherwise it remains at y. Rewinding gives O(x_0) = 2, whereas O(y) = 1/q. If Algorithm 3 samples y, its stated mean–median procedure estimates O(y) to fixed absolute accuracy under noise scale alpha/q. The required number of samples grows with (alpha/q)^2, although the claimed bound depends only on the fixed value O(x_0) = 2. Please explain what assumption or algorithmic step controls this cost, or revise the corollary. This concern does not by itself refute the exact-oracle result in Theorem 1.1.

2. The practical CaT algorithm is not covered by the main theorem.

Theorem 1.1 proves optimality for Algorithm 1, which always expands a state with the smallest exact remaining hitting time. The experimental Algorithm 4 instead samples from all observed states using a softmax over LLM-generated estimates. It can repeatedly expand different branches and need not produce a caterpillar tree. Neither Theorem 1.1 nor the analysis of Algorithm 3 gives Algorithm 4 an optimality or approximation guarantee.

The paper also does not establish that the LLM scores estimate O(s) with the independence and Laplace error assumed in Section 4.1. Please separate the proved properties of Algorithm 1 from claims about practical CaT, and provide evidence identifying which component of Algorithm 4 produces the empirical gain.

3. The experimental comparisons need fair controls.

For Game of 24, the paper reports 81% success for CaT and 74% for ToT on 100 problems, but does not provide paired per-problem outcomes or uncertainty estimates. The aggregate rates alone do not allow the claimed significance to be checked. CaT also uses best-of-two runs.

For crosswords, the full-solve rates correspond to only 3/20 versus 1/20 puzzles. The reported 20-step ToT comparator comes from another work rather than a clearly matched rerun. The paper further states that ToT cannot stop upon discovering a valid solution; please explain why both methods could not use the same success check and stopping rule. A comparison with matched token budgets, stopping criteria, and paired outcomes would make the empirical claim more convincing.

4. The experimental comparisons do not isolate the source of CaT's gains.

The evaluation uses one language model, two reasoning tasks, and primarily compares CaT with ToT. It does not isolate the effects of rewinding, LLM-based state scoring, softmax parent selection, and—in Game of 24—best-of-two independent runs. Consequently, the reported gains do not show which part of the proposed method is responsible.

A focused comparison on the existing tasks would be valuable: use the same model, prompts, stopping rule, and total token budget to compare CaT against (i) greedy selection of the lowest-scored observed state, (ii) uniform selection among observed states, and (iii) ToT with the same number of independent runs. These controls would test whether the softmax rewinding rule improves search beyond simpler ways of using the same computation cost.

Questions for authors

See the weakness part.

1 comment

We thank the reviewer for the feedback on the paper and suggestions for further experiments.

Regarding the gap in the state-dependent noise, the counterexample correctly shows that the noise scale at the initial state does not need to control the scale at every newly generated state. We have removed the noise corollary and explicitly restricted the positive result to a common, state-independent Laplace scale. We have also replaced the previous proof with a direct drift argument.

About the distinction between the theoretical algorithms and practical CaT, we added controlled synthetic experiments in Appendix C. We use ten finite Markov chains with known transition probabilities and compute the exact values of O(s)O(s) using Algorithm 2. We then compare Algorithms 1, 3, and 4 with greedy, uniform, breadth-first, and beam-search baselines, using exact scores and independent Laplace noise. Our cached noisy greedy baseline follows Algorithm 1, but replaces each exact value with one noisy evaluation that is stored and reused throughout the run. Algorithm 4 uses the same observation and caching model, but samples among all observed states using softmax. This comparison studies the effect of parent selection while keeping the scoring procedure fixed. If a useful child receives an unfavorable cached score, greedy may repeatedly reject it, whereas softmax can still select and expand it. With exact scores, Algorithm 1 achieves 97.6%97.6\% success within 3232 generated transitions, compared with 95.5%95.5\% for softmax. With independent Laplace noise of scale 11, softmax improves success from 60.6%60.6\% for cached noisy greedy to 85.2%85.2\%. At noise scale 44, it improves success from 35.1%35.1\% to 42.8%42.8\%, although beam search performs better at 73.5%73.5\%. Thus, softmax helps relative to deterministic selection based on cached noisy scores, but its advantage depends on the noise level and the competing method. We also evaluate Algorithm 3, which achieves 97.3%97.3\% and 97.4%97.4\% success at the two noise scales through repeated evaluations. We report these evaluation costs separately, since equal generation budgets do not imply equal total computation. Additional experiments vary the softmax temperature and whether scores are reused or evaluated again.

Since the Markov chains corresponding to LLMs are huge, we cannot compute the hitting time and rely on the heuristic. This implies that we do not have exact access to the value of the hitting time and need to use algorithms that are designed to work with an approximation to this hitting time. What we find interesting is this decoupling of the problem into the rewinding algorithm and estimating the hitting time; how accurate we can find the hitting time will help us use the algorithm with a better theoretical guarantee.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.