Figure 1. Complete-solution sampling and intermediate-state reuse. Left: Independent sampling requires a successful complete run. The analyzed reuse loop preserves earlier accepted work, retries rejected candidates, and stops when a step’s budget is exhausted. Passing a check does not guarantee correctness. Right: An illustrative two-subproblem candidate-selection example, with SC denoting self-consistency, M M M the first-subproblem candidate budget, and B B B the continuation cap. Fractions count correct candidates among those shown; the example is not an experimental measurement or the single-state loop used in the proof.
Introduction
Many practical reasoning tasks require several distinct subproblems to be solved together. Solving each subproblem in isolation does not ensure that a model can solve the complete task [41 ] . With model weights fixed, a system can spend more computation at inference time to improve its chance of finding a solution. A system can generate more complete answers, compare candidates, or check intermediate work [5 , 37 , 19 ] . How this computation is allocated matters alongside how much is available [30 ] .
Under complete-solution sampling, all required subproblem answers must be correct in one run. One run may solve the first subproblem and another the second, while neither solves both. The sample pool contains correct answers to both subproblems, but no run has solved the complete task. As tasks get longer, more intermediate work can be lost when an attempt fails near the end. A restart retries the failed subproblem but repeats earlier work that may already be correct. Existing methods already use intermediate work: Least-to-Most prompting solves subproblems in sequence using earlier answers [45 ] , while Tree of Thoughts searches over partial reasoning states [38 ] .
A subproblem may contain several reasoning steps; our analysis uses steps whose intermediate states can be checked and retained. Consider a three-step calculation that derives a formula, substitutes the given values, and computes a final quantity. Suppose the first two steps are correct but the final calculation fails. A complete restart generates all three steps again. If the formula and substitution can be checked and retained, a new attempt can repeat only the final calculation. The retained results become the retry’s input.
The difficulty is deciding what can safely be kept. A check may reject a correct candidate or accept an incorrect one; benchmarks document the difficulty of identifying errors in intermediate reasoning [43 , 17 ] . An error passed forward may then affect later attempts, as studies of self-conditioning illustrate [29 ] . Even a correct intermediate answer may leave out assumptions or other information needed to continue. Atom of Thoughts constructs self-contained reasoning states [34 ] , while MEM1 learns to retain compact information across interaction steps [46 ] . Keeping a full reasoning trace instead supplies more context, but may also retain unchecked mistakes and increases the context to process. Checking itself consumes computation, so avoiding a restart does not by itself establish a saving. This report studies the conditions under which intermediate results can be reused reliably and the cost of doing so.
Recent search methods also avoid unnecessary branching: Chain-in-Tree continues routine steps sequentially and reuses generated children when branching is needed [18 ] . Process supervision evaluates intermediate reasoning [19 ] , and MAKER combines fine-grained decomposition with voting to execute long deterministic tasks [23 ] . MAKER derives near-linear expected computation under its voting model, including the cost of discarded responses. We consider finite local retries, where the first candidate to pass a check is retained and may carry an error into later steps.
The analyzed procedure checks each new result and retries from the last retained state after a rejection. It stops when every candidate within the local budget is rejected. For fixed generation and checking, retries reduce exhaustion without improving the reliability of accepted states. We give an attainable reliability bound and matching worst-case bounds on expected attempts. The work bound includes paths after an incorrect acceptance, where correct-prefix acceptance guarantees no longer apply. Exhaustion limits the work spent at frequently rejected states. Sufficient precision and acceptance probability yield linear expected attempts; total cost also includes checking and state processing.
We also report sampling experiments across eight reasoning models. Arithmetic tasks let us ask how much repeated attempts add beyond first-attempt accuracy. Pairs of mathematics problems let us compare candidate selection and the context supplied to the second subproblem: no first-subproblem context, its answer alone, or its reasoning and answer. The paired subproblems are mathematically separate. Their continuation prompts differ in both content and instructions, so the comparison concerns entire prompt configurations. Budget sweeps examine how success and generated tokens change when more computation is spent on first-subproblem candidates or subsequent continuations.
Across four DeepSeek models, second-subproblem success is 36.2% without first-subproblem context, 57.2% with its answer, and 58.3% with its reasoning and answer. Paired uncertainty is unavailable for these prompt comparisons. These scores include fallback continuations and measure success on the second subproblem, rather than joint success of both answers. Arithmetic results show that similar first-attempt accuracies can lead to very different coverage after repeated attempts. A separate EdgeBench study compares two curves for predicting later agent scores from early observations and observations of the same agents on other tasks (Zhu et al., [47 ] ).
Report overview.
(a) Reliability of reuse. We give an attainable trajectory bound and the exact accepted-state error threshold for a finite cap to guarantee target reliability.
(b) Expected work and checking cost. We bound worst-case expected work, including erroneous paths, and connect reliable completion to acceptance probability and attempt cost.
(c) Empirical findings. We compare retries, answer selection, retained context, and budget allocation across eight reasoning models, and evaluate two curves for predicting later agent scores.
Preliminaries
We first define complete-task success, the state passed between steps, and the sampling metrics. These definitions distinguish finding a complete answer from continuing successfully after an intermediate result.
Tasks, States, and Sampling Metrics
A composite task x 1 ⊕ x 2 x_1 \mathbin{\oplus} x_2 x 1 ⊕ x 2 presents two subproblems in one prompt and is correct only when both returned subproblem answers are correct. Let a ⋆ ( x ) a^\star(x) a ⋆ ( x ) be the target answer to x x x , with a ⋆ ( x 1 ⊕ x 2 ) = [ a ⋆ ( x 1 ) , a ⋆ ( x 2 ) ] a^\star(x_1 \mathbin{\oplus} x_2) = [a^\star(x_1), a^\star(x_2)] a ⋆ ( x 1 ⊕ x 2 ) = [ a ⋆ ( x 1 ) , a ⋆ ( x 2 )] . Let θ \theta θ denote the model parameters and p θ ( ⋅ ∣ s ) p_\theta(\cdot\mid s) p θ ( ⋅ ∣ s ) its distribution over generated text under a fixed decoding configuration and input context s s s . For a problem x x x , fix a decomposition into N ≥ 1 N \ge1 N ≥ 1 steps, where N N N counts the steps in this chosen decomposition. Write z t z_t z t for the text generated at step t ∈ { 1 , … , N } t \in\{1,\ldots,N\} t ∈ { 1 , … , N } and s t = [ x , z 1 , … , z t ] s_t = [x,z_1,\ldots,z_t] s t = [ x , z 1 , … , z t ] for the resulting state, with s 0 = x s_0 = x s 0 = x . Each step is sampled from p θ ( ⋅ ∣ s t − 1 ) p_\theta(\cdot\mid s_{t-1}) p θ ( ⋅ ∣ s t − 1 ) . For reuse, s t s_t s t denotes the state actually passed forward: task information plus retained generated text or extracted intermediate answers. The prompt specifies how this state is presented to the model. Correctness concerns the information carried forward; a correct extracted answer need not imply that discarded reasoning was correct. We call a task stepwise decomposable if it can be split into steps whose intermediate states admit a task-specific accept-or-reject check. A state is accepted if it passes the check; acceptance need not imply correctness. A stage groups steps, such as those used to solve one subproblem. Let y y y be the final answer extracted from a completed run and L L L its total number of generated tokens. The single-run metrics are:
A θ , 1 ( x ) = P ( y = a ⋆ ( x ) ) , C θ , 1 ( x ) = E [ L ] . (1) A_{\theta,1}(x) = P(y = a^\star(x)), \qquad C_{\theta,1}(x) = \mathbb{E}[L]. \tag*{(1)} A θ , 1 ( x ) = P ( y = a ⋆ ( x )) , C θ , 1 ( x ) = E [ L ] . (1)
For an integer K ≥ 1 K \ge1 K ≥ 1 , independent sampling draws K K K independent complete runs from the same distribution and counts success if any run returns the correct answer.
A θ , K ( x ) = 1 − ( 1 − A θ , 1 ( x ) ) K , C θ , K ( x ) = K C θ , 1 ( x ) . (2) A_{\theta,K}(x) = 1 - \left(1 - A_{\theta,1}(x)\right)^K, \qquad C_{\theta,K}(x) = K C_{\theta,1}(x). \tag*{(2)} A θ , K ( x ) = 1 − ( 1 − A θ , 1 ( x ) ) K , C θ , K ( x ) = K C θ , 1 ( x ) . (2)
Let δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) denote the target failure probability, so the desired reliability is 1 − δ 1-\delta 1 − δ .
Complete-Solution Sampling
In a common pool of composite runs, joint success implies that each subproblem is covered, while separately correct subproblem answers may occur in different runs (Prop. 2). If standalone and composite subproblem marginals agree at a 1 , a 2 ∈ ( 0 , 1 ) a_1,a_2 \in(0,1) a 1 , a 2 ∈ ( 0 , 1 ) , with independence within and across runs, then for K ≥ 2 K \ge2 K ≥ 2 ,
1 − ( 1 − a 1 a 2 ) K < [ 1 − ( 1 − a 1 ) K ] [ 1 − ( 1 − a 2 ) K ] . (3) 1 - \left(1-a_1a_2\right)^K < \left[1-\left(1-a_1\right)^K\right]\left[1-\left(1-a_2\right)^K\right]. \tag*{(3)} 1 − ( 1 − a 1 a 2 ) K < [ 1 − ( 1 − a 1 ) K ] [ 1 − ( 1 − a 2 ) K ] . (3)
One run must solve both subproblems, whereas separate coverage can use different runs. This sampling constraint also applies to other stochastic solvers; it does not equate token costs across prompt formats. Under the additional assumptions of exponentially declining complete-run accuracy and linear generation cost [41 ] , complete restarts require exponentially growing generation cost at fixed reliability. Appendix § 13 .8 gives the product comparison, numerical example, and scaling calculation. We next examine the reliability and cost of retaining intermediate work.
Reliability and Cost of State Reuse
The reuse loop maintains one accepted state at a time. We analyze the probability that every retained state is correct, the number of executed attempts, and the resulting computational cost.
Local Retries and Reliable Completion
At step t t t , generate a candidate from the retained state s t − 1 s_{t-1} s t − 1 and check the state to be passed forward. Let V t \mathcal{V}_t V t indicate acceptance and G t \mathcal{G}_t G t its correctness. Retain the first accepted state; if all R R R attempts are rejected, terminate the entire task. Conditional on the complete history at entry to each reached step, attempts are independent and identically distributed, including at incorrect inputs. Rejected candidates do not change the state or retry law; different steps may depend on earlier accepted results. Checking an extracted answer does not establish that a retained reasoning trace is also correct.
At a correct entry history s s s , let ρ t ( s ) \rho_t(s) ρ t ( s ) be the rejection probability and w t ( s ) w_t(s) w t ( s ) the probability of incorrect acceptance in one attempt. Assume ρ t ( s ) ≤ ρ ∈ [ 0 , 1 ) \rho_t(s) \le\rho\in[0, 1) ρ t ( s ) ≤ ρ ∈ [ 0 , 1 ) and accepted-state error α t ( s ) ≤ α ∈ [ 0 , 1 ) \alpha_t(s) \le\alpha\in[0, 1) α t ( s ) ≤ α ∈ [ 0 , 1 ) at every correct entry history. Conditioning on the first acceptance gives
α t ( R ; s ) = w t ( s ) 1 − ρ t ( s ) = α t ( s ) . (4) \alpha_t(R; s) = \frac{w_t(s)}{1-\rho_t(s)} = \alpha_t(s). \tag*{(4)} α t ( R ; s ) = 1 − ρ t ( s ) w t ( s ) = α t ( s ) . (4)
Accepted-state precision is 1 − α t ( s ) 1-\alpha_t(s) 1 − α t ( s ) ; it does not improve with R R R . The local trajectory fails if the retry budget is exhausted or an incorrect candidate is accepted:
β t ( R ; s ) = ρ t ( s ) R + ( 1 − ρ t ( s ) R ) α t ( s ) . (5) \begin{aligned}
\beta_t(R; s) &= \rho_t(s)^R \\
&\quad+ \left(1-\rho_t(s)^R\right)\alpha_t(s). \tag*{(5)}
\end{aligned} β t ( R ; s ) = ρ t ( s ) R + ( 1 − ρ t ( s ) R ) α t ( s ) . (5)
More retries reduce exhaustion; improving accepted-state precision requires a different generation or checking rule. Let H t H_t H t mean that the first t t t steps complete with every retained state correct, with H 0 H_0 H 0 certain. Assume H N H_N H N yields the target answer; later repair can also succeed outside H N H_N H N .
Theorem 1 (Trajectory reliability). Under the preceding assumptions,
Pr ( H N ) ≥ [ ( 1 − ρ R ) ( 1 − α ) ] N . (6) \Pr(H_N) \ge\left[(1-\rho^R)(1-\alpha)\right]^N. \tag*{(6)} Pr ( H N ) ≥ [ ( 1 − ρ R ) ( 1 − α ) ] N . (6) An admissible process attains equality for every N N N , R R R . For 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 , a finite common cap guarantees 1 − δ 1-\delta 1 − δ over this class if and only if
α < 1 − ( 1 − δ ) 1 / N . (7) \alpha< 1-(1-\delta)^{1/N}. \tag*{(7)} α < 1 − ( 1 − δ ) 1/ N . (7)
Each correct prefix advances correctly with conditional probability at least ( 1 − ρ R ) ( 1 − α ) (1-\rho^R)(1-\alpha) ( 1 − ρ R ) ( 1 − α ) ; the chain rule gives the product without independence between steps. A homogeneous process with irreversible errors after acceptance attains it. At equality in Eq. (7) , the target is approached only with unbounded retries; for ρ = 0 \rho=0 ρ = 0 , equality is allowed and one attempt suffices. This is a worst-case guarantee, not a necessary precision threshold for every system that can repair errors. Appendix § 13 .10.1 gives the proof, exact minimum cap, and the simpler sufficient allocation N α < δ N\alpha< \delta N α < δ used in Prop. 4.
Expected Work under the Stopping Rule
We measure work by W W W , the number of executed candidate attempts. The pathwise cap W ≤ N R W \le NR W ≤ N R reserves the full budget at every step. Actual work can be smaller because a step ends as soon as a candidate passes. Let P N , R \mathcal{P}_{N,R} P N , R contain all processes following the preceding retry and stopping rules for at most N N N steps, with arbitrary history-dependent rejection probabilities and no correctness requirement. If acceptance were at least h > 0 h > 0 h > 0 at every reached state, the geometric waiting-time bound would give E [ W ] ≤ N / h \mathbb{E}[W] \le N/h E [ W ] ≤ N / h directly. After an incorrect acceptance, the process may reach states where the correct-prefix acceptance bound no longer holds. The next theorem includes work at these states.
Theorem 2 (Worst-case expected attempts). For every pair of integers N N N , R ≥ 1 R \ge1 R ≥ 1 ,
sup P ∈ P N , R E P [ W ] = Θ ( N + N R log ( N + 1 ) ) , (8) \sup_{P \in\mathcal{P}_{N,R}} \mathbb{E}_{P}[W] = \Theta\left(N + \frac{NR}{\log(N+1)}\right), \tag*{(8)} P ∈ P N , R sup E P [ W ] = Θ ( N + log ( N + 1 ) N R ) , (8) with positive implicit constants independent of both the process length N N N and the retry cap R R R .
Frequently rejected states are expensive to leave but likely to exhaust the cap, ending the run. The proof uses this tradeoff to bound their expected visits; a homogeneous process gives the matching lower bound (Appendix § 13 .10.3). That lower bound concerns the unrestricted class, not every reliable process. The stopping pattern is related to classical start-up demonstration tests ([9 ] . Appendix § 13 .10.6 gives the exact dynamic recursion and separates this uniform bound from fixed-law waiting-time calculations. Together with Thm. 1, this yields reliable completion with an O ( log N ) O(\log N) O ( log N ) cap and linear expected work. Here the target failure probability is fixed, acceptance at correct prefixes has a positive constant lower bound, and accepted-state error decreases with chain length as specified in Cor. 1.
Example: reserved budget and executed work. For 100 steps, a cap of 12 attempts reserves at most 1,200 attempts. Suppose every reached state has rejection probability 1 / 2 1/2 1/2 , and every correct prefix has accepted-state error at most 0.0002. The reliability bound exceeds 0.956, while each reached step uses fewer than two attempts in expectation, giving fewer than 200 over the task. The probabilities in this example are hypothetical. The example distinguishes the reserved budget from expected work; Thm. 2 additionally permits arbitrary rejection probabilities after an incorrect acceptance.
Checking Precision and Computation
As a chain grows, the reliability bound requires a smaller error rate among accepted states. Reaching this precision may make checking more expensive or cause it to reject more candidates. Let h N h_N h N lower-bound acceptance probability at every correct prefix, and let g N g_N g N uniformly bound per-attempt cost, including generation, checking, and state processing at every reached state.
Corollary 1 (Precision, acceptance, and cost). Fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and c ∈ [ 0 , 1 ) c \in[0,1) c ∈ [ 0 , 1 ) . If correct prefixes have acceptance probability at least h N ∈ ( 0 , 1 ] h_N \in(0,1] h N ∈ ( 0 , 1 ] and accepted-state error at most c ε δ / N c\varepsilon\delta/N c ε δ / N , choose
R N = ⌈ 1 h N log N ( 1 − c ) δ ⌉ . (9) R_N = \left\lceil\frac{1}{h_N}\log\frac{N}{(1-c)\delta}\right\rceil. \tag*{(9)} R N = ⌈ h N 1 log ( 1 − c ) δ N ⌉ . (9) Then Pr ( H N ) ≥ 1 − δ \Pr(H_N) \ge1-\delta Pr ( H N ) ≥ 1 − δ and
E [ W ] = O ( N / h N ) , C v s r = O ( N g N / h N ) . (10) \mathbb{E}[W] = O(N/h_N), \qquad C_{\mathrm{vsr}} = O(Ng_N/h_N). \tag*{(10)} E [ W ] = O ( N / h N ) , C vsr = O ( N g N / h N ) . (10) The attempt order N / h N N/h_N N / h N is attained within this reliable class for this cap.
The cap controls exhaustion; Thm. 2 bounds all executed attempts, including those after an incorrect acceptance (Appendix § 13 .10.4). For constant h N h_N h N , expected attempts are linear, whereas the deterministic cost cap remains O ( N log N g N ) O(N \log N\, g_N) O ( N log N g N ) . Since W ≥ N 1 H N W \ge N\mathbf{1}_{H_N} W ≥ N 1 H N and E [ W ∣ H N ] ≤ E [ W ] / ( 1 − δ ) \mathbb{E}[W \mid H_N] \le\mathbb{E}[W]/(1-\delta) E [ W ∣ H N ] ≤ E [ W ] / ( 1 − δ ) , this conclusion is compatible with reliable completion, rather than relying only on cheap failures.
At a common precision target, the relevant cost scale is g N / h N g_N/h_N g N / h N . Under independent binary checks, requiring unanimity can make acceptance polynomially rare, yielding Θ ( N 1 + γ log N ) \Theta(N^{1+\gamma}\log N) Θ ( N 1 + γ log N ) expected cost for some γ > 0 \gamma> 0 γ > 0 when every check is executed. With an additional separation condition, majority checking keeps acceptance bounded away from zero and gives O ( N log N ) O(N \log N) O ( N log N ) expected cost (Hoeffding, [12 ] ). Appendix B.10.5 specifies the noise model and derives both cases; these repeatedly check one candidate rather than compare different answers by self-consistency.
The work bound relies on the execution rule: feedback-dependent retries or continuation after exhaustion can each use N R NR N R attempts. The experiments below use batch selection, multiple continuations, and fallback with different success criteria. They do not directly test these guarantees.
Experiments
We compare coverage across budgets, selection rules, and continuation prompts. The tasks cover composite mathematics, complete-answer arithmetic retries, and agent-score prediction.
Experimental Setup
Models and tasks. We evaluate DeepSeek-R1-Distill (1.5B, 7B, 8B, 14B) (Guo et al., [10 ] ), Qwen3-Thinking (4B, 30B-A3B) (Team, [33 ] ), and GPT-OSS (20B, 120B) (OpenAI, [26 ] ). LoRe-Compo contains 250 pairs of distinct-subject MATH500 problems, using each of the 500 subproblems once (Zhang et al., [41 ] ; Hendrycks et al., [11 ] ). The second subproblem is a separate mathematical problem that does not require the first answer. Arithmetic uses 50 problems for each base (7 or 10), operation (addition or multiplication), and digit count n ∈ { 1 , … , 10 } n \in\{1,\ldots,10\} n ∈ { 1 , … , 10 } , with 32 complete-answer attempts per problem.
Procedures and success criteria. Composite Pass@K K K requires both correct answers in one of K K K complete runs. The two-stage protocol instead generates M M M answers to x 1 x_1 x 1 , retains at most B B B candidates, and continues on x 2 x_2 x 2 . Oracle selects reference-matching answers; self-consistency (SC) uses the modal answer when its vote share reaches 0.5. If selection returns none, fallback candidates are retained for continuation. Both procedures generate whole subproblem answers without checking individual reasoning steps.
The reported second-subproblem success rate A 2 r e t A_2^{\mathrm{ret}} A 2 ret counts any correct answer to x 2 x_2 x 2 among the retained continuations, including fallbacks and regardless of x 1 x_1 x 1 correctness. Joint retained-path success would require both answers to be correct along one shared path, with all 250 pairs still in the denominator. Thus A 2 r e t A_2^{\mathrm{ret}} A 2 ret upper-bounds joint coverage but does not determine it. It measures coverage, not final-answer selection accuracy. The theoretical loop returns one first-accepted state and stops at exhaustion; the experimental protocol uses multiple continuations and fallback. Appendix C.2 defines these events.
Sampling, matching, and cost. All mathematical generations have a 10,240-token cap. A composite run shares this cap across two answers, whereas staged solving grants one cap per subproblem. LoRe-Compo uses family-specific decoding settings and direct prompt strings without model-specific chat templates. Decoding differs between Pass@1 and larger budgets, some Pass@1 values come from prior work, and cross-budget nesting is unspecified for the composite results. Answer matching uses numeric tolerance or normalized strings, with separate extraction rules for single and paired answers (Appendix C.1). We report recorded generated-token counts and success percentage points per thousand tokens. Equal attempt counts allow different generation budgets. The token counts exclude some checking and state processing costs and are not matched for whole-task reliability.
Complete-Solution Sampling on Composite Tasks
Table 2 reports joint composite Pass@K K K . The eight-model mean is 8.2% at K = 1 K = 1 K = 1 and 33.3% at the largest recorded budget (K = 32 K = 32 K = 32 for R1-1.5B and K = 128 K = 128 K = 128 otherwise). Coverage improves across these endpoint configurations, but the gains and model ordering vary. Qwen3-4B starts at 4.8%, below R1-8B at 13.2%, and reaches 38.0% compared with 37.2% at K = 128 K = 128 K = 128 . GPT-OSS-120B has the highest Pass@1 and Pass@128, at 19.6% and 38.4%. Model rankings depend on the sampling budget.
Table 2. Composite Pass@K K K under Independent Sampling. Success requires both correct answers in one of K K K complete runs. DeepSeek K = 1 K = 1 K = 1 values are from Zhang et al. [41 ] ; other cells are reported aggregates from this study. Superscripts give percentage-point changes from K = 1 K = 1 K = 1 ; dashes indicate unreported cells. Decoding varies with K K K , and cross-budget sample nesting is unspecified.
GPT-OSS-20B changes from 34.8% at K = 8 K = 8 K = 8 to 33.2% at K = 32 K = 32 K = 32 . Because nesting and decoding are not held fixed across all configurations, this decrease does not show that adding samples to an unchanged pool reduces coverage. The table reports how often a complete run answers both subproblems correctly. Measuring unused partial success requires the statistic in Appendix § 15 .§ 2 .
Candidate Selection and Retained Context
Intermediate-answer selection. Table 1 compares Oracle and SC at M = 8 M = 8 M = 8 , B = 4 B = 4 B = 4 using the same second-subproblem criterion. The four-DeepSeek SC mean is 57.9%; across all eight models, SC and Oracle differ by at most 1.6 percentage points. Here, Oracle and SC yield similar second-subproblem success despite using different selection rules. These scores include fallback continuations, so they do not show that the selectors retain equally accurate first answers. The subproblems are mathematically separate, so a wrong first answer need not prevent success on the second.
Table 1. Second-subproblem success after selection. A 2 r e t A_{2}^{\mathrm{ret}} A 2 ret counts a correct x 2 x_{2} x 2 answer on any retained path, including fallbacks, regardless of x 1 x_{1} x 1 correctness. Oracle and SC share M = 8 M = 8 M = 8 , B = 4 B = 4 B = 4 . This continuation metric differs from the complete-solution joint-success criterion in Table 2 .
The reported SC-to-Pass@8 generated-token ratios are approximately 1.01–1.12 for R1-1.5B, R1-7B, R1-14B, and GPT-OSS-20B, and 1.4–1.5 for the other models. These procedures use different success criteria, so the ratios cannot establish savings at matched whole-task success rates.
Continuation-prompt configurations. At the same continuation budget, the four-DeepSeek means are 36.2% for no_context, 57.2% for answer_only, and 58.3% for full_context (Table 3 ). The answer-only prompt scores 21.0 percentage points above no context; full context scores another 1.1 points higher. This small gap does not establish that the two prompts are equivalent. The answer-only mean matches the Oracle mean in Table 1 ; the SC mean reported above is a separate result. The available prompt-comparison summary does not identify the selector configuration.
Table 3. Context for the Second Subproblem. Four-DeepSeek means at the same continuation budget. A 2 r e t A^{\mathrm{ret}}_{2} A 2 ret counts second-subproblem success, including fallbacks. Change is the relative percentage increase over no_context. Strategies supply no first-subproblem context, its answer only, or its reasoning and answer.
The prompts differ in instructions as well as content; these scores compare complete configurations and do not isolate the contribution of the first answer. The answer-only protocol retains the same extracted answer assessed during selection, whereas full context also retains an unchecked reasoning trace truncated to fit the context budget.
How candidate and continuation budgets trade off. Table 4 compares four tested allocations. Its (8, 4) success column reproduces the Oracle column of Table 1 ; the aggregate table alone does not identify the selector used for every other allocation. The eight-model mean rises from 52.8% at 36.4K tokens for (4, 2) to 56.3% at 72.3K for (8, 4), a 3.5-point gain for approximately twice the generation. Moving to (16, 8) gives 57.4% at 144.5K, another 1.1 points for approximately twice the tokens again. The second budget expansion yields a smaller gain in success. We use (8, 4) as an intermediate reference; (4, 2) has higher success per thousand generated tokens.
Table 4. Budget Allocation Sweep. M M M is the first-subproblem candidate budget and B B B the cap retained for continuation. Succ. is second-subproblem success (%), including fallbacks, regardless of first-answer correctness. Tokens reports recorded counts; Eff. divides Succ. by Tokens in thousands. Average-row efficiencies divide mean success by mean tokens; they are not means of model-level efficiencies. Superscripts give percentage-point differences from (4, 2). Orange marks the reference configuration (8, 4), not an efficiency optimum; blue marks configurations with higher success and a larger measured token cost.
The intermediate allocations separate changes in candidate count from changes in continuation count. At B = 2 B = 2 B = 2 , increasing M M M from 4 to 8 raises mean success by 1.7 points, from 52.8% to 54.5%, for 27.0K additional tokens. At M = 8 M = 8 M = 8 , increasing B B B from 2 to 4 raises mean success by 1.8 points, from 54.5% to 56.3%, for 8.9K additional tokens. Increasing the continuation budget therefore gives a similar mean gain with fewer additional generated tokens in this comparison.
The model-level responses also vary. At M = 8 M = 8 M = 8 , raising B B B from 2 to 4 changes R1-8B from 44.8% to 51.2%, while GPT-OSS-120B stays at 62.4%. GPT-OSS-20B changes from 48.4% to 47.2%; without nested pools this cannot be attributed to keeping more candidates. Across (4, 2) to (8, 4), R1-8B gains 10.0 points, compared with 0.4 points each for R1-7B and GPT-OSS-120B. The gains therefore depend on both the model and the allocation of the sampling budget.
Resolution of the comparisons. With 250 pairs per model, one changed pair corresponds to 0.4 percentage points. The largest SC–Oracle difference is a net difference of four successful pairs. Paired uncertainty is unavailable for these comparisons and for the 1.1-point full-context increment, so we interpret the figures as descriptive comparisons of the evaluated configurations.
Finite-Budget Arithmetic Retries
The arithmetic experiments ask how many initially missed problems can be solved with more attempts. Here the candidate is an entire arithmetic answer, not a checked digit-level state. We write E ^ ( R ) \widehat{E}(R) E ( R ) for the fraction of problems with no correct answer among their first R R R attempts; empirical Pass@R R R is 1 − E ^ ( R ) 1-\widehat{E}(R) 1 − E ( R ) . The checkpoints use prefixes of the same pool of 32 complete-answer attempts.
Across 320 model–base–operation–digit conditions, 235 have no unsolved problems after 32 attempts and 85 have a nonzero unsolved fraction (Figure 2 ). All 80 Base 10 addition conditions have zero unsolved fraction; Base 7 multiplication has a mean of 0.40, with 33 of 80 conditions above 0.5. The dependence on digit count varies across models, including nonmonotonic behavior at low digit counts for GPT-OSS-120B. Large retry gains appear around Pass@1 values of 0.05–0.35 (Figure 3 ), where repeated attempts can cover many initially missed problems.
Figure 2. Unsolved Fraction after 32 Attempts. Each cell reports E ^ ( 32 ) \hat{E}(32) E ^ ( 32 ) , the fraction of 50 problems unsolved after 32 attempts; n n n is operand digit count. Panels show Base 10 addition/multiplication and Base 7 addition/multiplication. All Base 10 addition problems are solved; Base 7 multiplication has the largest mean unsolved fraction. For R1-7B, the latter rises from 0.06 at n = 3 n=3 n = 3 to 0.74 at n = 4 n=4 n = 4 . GPT-OSS-120B shows nonmonotonic behavior at low digit counts under the recorded sampling protocol.
Figure 3. Gain from Additional Attempts. Each point is a combination of model, base, operation, and digit count. The gain is Pass@32 minus Pass@1; the dashed line is its maximum 1 − P a s s @ 1 1-\mathrm{Pass}@1 1 − Pass @1 . Large observed gains occur around Pass@1 values of 0.05–0.35 in these evaluated arithmetic conditions.
First-attempt accuracy alone does not determine the gain from retries. On Base 7 addition at n = 3 n=3 n = 3 , R1-1.5B rises from Pass@1 of 0.08 to Pass@32 of 0.98, leaving E ^ ( 32 ) = 0.02 \widehat{E}(32)=0.02 E ( 32 ) = 0.02 . On Base 7 multiplication at n ≥ 7 n \ge7 n ≥ 7 , the same model has Pass@1 of zero and E ^ ( 32 ) = 1 \widehat{E}(32)=1 E ( 32 ) = 1 . R1-14B at n = 6 n=6 n = 6 on Base 7 multiplication starts at Pass@1 of 0.14 but solves 84% of the evaluated problems with the same total sampling budget of 32 complete-answer attempts (Figure 8 ).
Figure 8. First-Attempt Accuracy. For Base 7 multiplication, R1-14B (n = 6 n = 6 n = 6 ) has Pass@1=0.14 and E ^ ( 32 ) = 0.16 \hat{E}(32) = 0.16 E ^ ( 32 ) = 0.16 (84% solved within 32 attempts); R1-1.5B (n = 7 n = 7 n = 7 ) has Pass@1=0 and E ^ ( 32 ) = 1 \hat{E}(32) = 1 E ^ ( 32 ) = 1 .
A low Pass@1 can therefore accompany either substantial retry gains or no observed success within the available budget. The observations concern finite pools of complete answers: E ^ ( 32 ) > 0 \widehat{E}(32)>0 E ( 32 ) > 0 does not identify a permanent failure floor, and digit count is not the number of checked intermediate states. Appendix § 16 and Appendix § 17 give the curves, mixture fits, and token counts.
Agent Score Prediction
We also examine whether a repeated-attempt curve can predict later agent scores from early observations. The retry curve approaches a fitted score ceiling with diminishing gains; a sigmoid in log time provides an alternative model of bounded score growth (Appendix § 18 .§ 1 ).
EdgeBench (Zhu et al., [47 ] ) supplies complete observations at 2, 4, 6, 8, 10, and 12 hours for 252 task–model pairs across five models and 51 tasks. For each target pair, we fit its 2-hour and 4-hour scores using category-level priors from other tasks. Priors exclude all model trajectories of the target task.
Median relative errors for the retry and sigmoid curves are 3.8% and 3.9% at 6 hours, increasing to 10.7% and 10.9% at 12 hours. Relative-error summaries use 248 pairs with positive observed scores at each prediction time, while all 252 pairs receive predictions. Table 6 reports all four horizons and the fractions below 10% and 20% relative error. Neither curve has the lower median error at every horizon; the retry curve has at least as many predictions below 10% error and more below 20% at each horizon. The two curves have similar prediction errors, although their priors constrain different parameters. The forecast does not identify internal checks or state reuse, or test savings from early stopping.
Table 6. Agent Score Prediction from 2- and 4-Hour Observations. Both curves use priors from other tasks as specified in Appendix § 18 .§ 2 . Median relative errors and fractions below 10% and 20% use 248 pairs with positive observed scores at each prediction time. All 252 pairs receive predictions; four pairs with zero observed scores are excluded from relative errors at each prediction horizon.
Related Work
Reasoning compositionality and long-horizon reliability. Prior work documents difficulties composing intermediate results [7 ] , falling success with task duration [14 ] , and failures at high problem complexity [28 ] . Zhang et al. [41 ] formulate compute and accuracy laws, measure compositionality gaps, and introduce SFT-Compo as a training intervention. We use their LoRe-Compo setting to study test-time sampling and state reuse.
Decomposition, search, and local error correction. Hierarchical reinforcement learning composes subgoals through options, MAXQ, and skill chaining [31 , 6 , 13 ] . Least-to-Most prompting uses earlier answers to solve later subproblems [45 ] ; Tree of Thoughts searches and backtracks over partial states [38 ] , and Graph of Thoughts combines and refines intermediate results [4 ] . Chain-in-Tree chains routine steps and reuses generated children when branching becomes necessary [18 ] . Recursive and agentic inference systems similarly pass subcall outputs to later computations [40 , 1 , 39 , 25 ] . MAKER [23 ] combines extreme decomposition, error detection, and first-to-k k k -ahead voting, with asymptotic foundations in Meyerson and Qiu (2025). Under its voting model, MAKER derives logarithmic voting budgets and Θ ( N log N ) \Theta(N \log N) Θ ( N log N ) total expected cost for fixed task reliability, assuming local success probability above one half. Our finite-cap analysis bounds work across correct and incorrect states under first acceptance and global stopping; its cost guarantee requires precision and acceptance bounds only at correct prefixes.
Stopped testing and restart analysis. Start-up demonstration tests study total-success and consecutive-failure stopping criteria, including dependent trials [9 , 2 ] . Our result bounds expected work uniformly over the specified retry class and relates it to correctness at retained prefixes. Classical restart scheduling optimizes repeated complete runs [21 ] ; the present cap and stopping rule are fixed. Appendix § 13 .10.6 gives the comparison and exact work recursion.
Verification and test-time sampling. Independent sampling improves candidate coverage [5 ] , while adaptive test-time computation allocates effort according to task difficulty and verification quality [30 , 27 , 24 ] . Self-consistency uses answer agreement as a proxy for correctness [37 ] ; process supervision and reward models assess intermediate reasoning [35 , 19 , 44 ] . ProcessBench and Socratic-PRMBench document limits of identifying and evaluating reasoning errors [43 , 17 ] . Formal verification and autoformalization provide stronger, domain-specific checks [16 , 32 ] . Our empirical Oracle is reference-answer matching, and SC is thresholded modal-answer selection; neither verifies a full reasoning trace. Labiad et al. [15 ] train a search policy to guide a frozen answer model and show that gains over repeated sampling depend on decoding and exploration choices. Their comparisons match the answer-generation allocation; concept generation adds a small separate inference cost. Our arithmetic experiments measure repeated-answer coverage under fixed decoding.
Retained context and execution cost. Atom of Thoughts decomposes and contracts problems into self-contained states designed to preserve answer equivalence [34 ] . MEM1 learns a compact recurrent state and discards redundant interaction history [46 ] . These methods address what to retain. Our analysis specifies the correctness and continuation conditions that the retained state must satisfy. Using counterfactual error histories, Sinha et al. [29 ] show that earlier mistakes can impair later reasoning, with thinking mitigating this effect in their experiments. Context length and information placement can also affect model behavior [20 ] . Adaptive sequential Monte Carlo avoids recomputing shared prefixes by reordering KV caches and particle tensors during resampling [36 ] . This reduces execution cost without establishing the correctness of retained reasoning. Appendix § 11 .§ 1 gives a separate qualitative recurrence. The reliability proof instead controls errors at correct prefixes and bounds the probability of retaining an incorrect intermediate state.
Discussion
Acceptance and correctness. At a fixed retained state, more attempts increase the chance that a candidate passes the check. With the same candidate distribution and check, they leave the error rate among accepted candidates unchanged. Reliable continuation therefore requires both a sufficiently accurate check and a state that contains the information needed by later steps. Checking an answer and retaining its full reasoning trace impose different correctness requirements on what is passed forward.
Executed work and total cost. The local cap reserves enough attempts for difficult steps, while acceptance often allows the procedure to advance earlier. With constant acceptance probability and sufficient precision, the stopped loop uses linearly many attempts in expectation. The cost of generating candidates, checking them, and processing retained states must then be counted at every reached state. A stricter check can improve precision while increasing the cost of each attempt or reducing the chance of acceptance. Both effects enter the comparison between checking cost and avoided generation.
Choosing a sampling configuration. The arithmetic results show that the benefit of more attempts varies across tasks, even when first-attempt accuracy is low. On the paired mathematics problems, the answer-only prompt scores closer to full context than to no context, although the comparison changes instructions as well as retained information. Larger candidate and continuation budgets also give uneven gains across models. These observations help describe the configurations evaluated here. Establishing computational savings from reuse still requires a comparison at the same whole-task success rate, with generation, checking, and retained-state processing all included.
Conclusion
Reliable reuse depends on which candidates a check accepts and how later steps use the retained state. Under the stated retry and stopping rules, we give conditions for correct completion and bounds on executed attempts. Additional retries reduce exhaustion, while the candidate distribution and check determine accepted-state precision. Total cost depends on per-attempt cost and acceptance probability.
The experiments document second-subproblem coverage across continuation prompts and variable gains from repeated arithmetic answers. They describe practical sampling choices but do not establish the long-chain guarantees. Assessing reuse on a new task requires measuring retained-state error, continuation reliability, and total cost at matched whole-task success.
Limitations
Execution and checking assumptions. The work theorem assumes conditionally independent, identically distributed retries at each retained state and termination when the local budget is exhausted. Feedback that changes the next attempt and fallback after exhaustion require separate analysis. The binary-check examples further assume that check outcomes are independent conditional on candidate correctness. The experiments do not directly test these execution assumptions.
Checks and retained information. Agreement can select common correct answers, but shared errors can also receive many votes [37 ] . Similar SC and Oracle scores on the second subproblem do not tell us how often either selector keeps a wrong first answer. The correctness condition applies to everything passed forward: checking an extracted answer does not verify a reasoning trace retained alongside it. Process-verifier benchmarks document errors in learned checks; formal verification uses task-specific correctness criteria [43 , 17 , 16 , 32 ] .
Decomposition and empirical scope. The theorem takes the decomposition and correctness criterion as inputs. A smaller step can be easier to check but requires more checks; a larger step may retain information whose correctness is harder to establish. The LoRe-Compo subproblems are mathematically separate, and arithmetic retries whole answers, so neither experiment estimates uniform reliability at the prefixes of a long dependent chain. Open-ended tasks may need different representations and task-specific checks before the sufficient conditions become applicable. The available composite aggregates do not identify accepted-state error or fallback contributions; prompt differences also prevent isolating an information-reuse effect.
Cost and auxiliary models. The total-cost bound includes generation, checking, and state processing at every reached state. Growing contexts or more accurate checks can increase that cost and must remain explicit in the budget expression. When complete solutions are already reliable, the extra checking may outweigh the work saved by reuse. The appendix’s qualitative error-propagation and mixture models describe possible behaviors; finite retry pools cannot identify a permanent capability boundary. Agent-score prediction also does not identify internal verification or establish a compute-allocation benefit.
AI Use Statement
We used generative AI tools to assist manuscript writing, revision, and the development and checking of mathematical derivations. The language models used to generate candidate solutions and continuations, together with the answer-selection procedures, are part of the experimental protocols described in § 4 . We take responsibility for the final manuscript and its scientific claims.
References
Modeling Assumptions and Their Scope
The analysis uses explicit assumptions about sampling, checks, and task decomposition. This appendix states their scope and relates them to the experimental protocols. The Limitations section explains their implications for checking, continuation, and empirical interpretation.
Independence assumption (see Limitations). Prop. 3 requires matching subproblem success rates between composite and standalone prompts, within-run independence of subproblem correctness, and independent identically distributed composite runs. The reuse result in Prop. 5 requires the same reliability bounds for every correct accepted state passed to later stages, with the total bound on accepted-state errors below the target failure probability. Our experiments sample subproblem pairs from distinct MATH subjects as a practical way to reduce concept overlap between subproblems. Subject separation does not establish these assumptions: shared formatting, latent correlations, and position-dependent generation can affect both dependence and marginal success rates.
Error propagation assumptions (see Limitations). The error model in Appendix § 11 .§ 1 assumes that earlier failures add linearly to later failure probabilities, remain in context, and have a common baseline probability q t c l e a n = q ˉ q_{t}^{\mathrm{clean}}=\bar{q} q t clean = q ˉ when preceding steps are correct. Real autoregressive models exhibit nonlinear error interactions, heterogeneous step difficulty, and partial attention decay across long contexts [20 ] , none of which the closed-form solution q ˉ ( 1 + c c t x ) t − 1 \bar{q}(1+c_{\mathrm{ctx}})^{t-1} q ˉ ( 1 + c ctx ) t − 1 captures. Appendix § 11 .§ 1 gives the closed form; its parameters are not fitted to the experimental data.
Stepwise decomposition requirement (see Limitations). Prop. 5 requires each step to have a positive probability of producing a correct accepted state from every correct input state. A suitable decomposition must keep the individual steps within the model’s capabilities. Open-ended generation, planning without intermediate checks, and tasks without a step-level correctness criterion may not admit such a decomposition, so the product lower bound need not apply.
Task length must reflect reasoning steps. The scaling variable N N N counts steps in the chosen decomposition, rather than prompt length or operand digits. Memorization or familiarity can let a model answer without following that decomposition, changing the relation between input size and executed work. Comparing Base 7 and Base 10 varies the numeral representation; without observations of internal steps, it cannot determine the process used to obtain an answer.
Reliability of checks (see Limitations). On LoRe-Como, self-consistency (SC) and Oracle selection yield similar second-subproblem success rates. This comparison does not estimate the accuracy of either check, and the arithmetic experiments do not compare these selection rules. The error rate among accepted SC answers can be measured by comparing them with reference answers, excluding fallback candidates that did not pass the check. Summaries that include fallback continuations describe all retained paths and cannot directly estimate the error rate among accepted states.
Table 5. Core notation used in the paper. Proof, fit, and metric symbols are defined where they appear.
Error Propagation Model
Errors in autoregressive generation may remain in the input context and affect later steps [42 , 20 ] . Let q t q_t q t be the failure probability at step t t t under the generated prefix, and q t c l e a n q_t^{\mathrm{clean}} q t clean its value when all preceding steps are correct. For a coefficient c c t x ≥ 0 c_{\mathrm{ctx}} \ge0 c ctx ≥ 0 describing the effect of earlier errors, consider the qualitative approximation
q t ≈ q t c l e a n + c c t x ∑ j < t q j . (11) q_t \approx q_t^{\mathrm{clean}} + c_{\mathrm{ctx}} \sum_{j<t} q_j. \tag*{(11)} q t ≈ q t clean + c ctx j < t ∑ q j . (11)
If q t c l e a n = q ˉ q_t^{\mathrm{clean}}=\bar{q} q t clean = q ˉ at every step, differencing the recurrence gives
q t ≈ q ˉ ( 1 + c c t x ) t − 1 . (12) q_t \approx\bar{q}(1+c_{\mathrm{ctx}})^{t-1}. \tag*{(12)} q t ≈ q ˉ ( 1 + c ctx ) t − 1 . (12)
When q ˉ > 0 \bar{q}>0 q ˉ > 0 and c c t x > 0 c_{\mathrm{ctx}}>0 c ctx > 0 , this expression increases with the step index. If the baseline difficulty varies across steps, c c t x > 0 c_{\mathrm{ctx}}>0 c ctx > 0 alone does not imply increasing failure probability. The parameters c c t x c_{\mathrm{ctx}} c ctx and q ˉ \bar{q} q ˉ are not fitted here. The recurrence is a qualitative approximation with a linear, persistent context effect, valid only while predicted probabilities remain below one. The recurrence offers an intuition for context-carried errors, while the product comparison and reuse guarantee use their own explicit probability assumptions. Arithmetic retries do not observe step failures within a run and cannot directly test this recurrence.
Correct Candidates before Checking
For a fixed step instance and correct input state s s s , let p t ( s ) p_t(s) p t ( s ) be the probability that a generated candidate is correct before checking. With R R R independent identically distributed attempts from this fixed context, the probability of no correct candidate is ( 1 − p t ( s ) ) R (1-p_t(s))^R ( 1 − p t ( s ) ) R , which tends to zero whenever p t ( s ) > 0 p_t(s)>0 p t ( s ) > 0 . Across a distribution of step instances and correct input states, define the probability of generating no correct candidate and its asymptotic error floor by
q t c l e a n ( R ) : = E s [ ( 1 − p t ( s ) ) R ] , q t f l o o r : = lim R → ∞ q t c l e a n ( R ) = P s ( p t ( s ) = 0 ) . (13) q_t^{\mathrm{clean}}(R) := \mathbb{E}_s\left[(1-p_t(s))^R\right], \qquad q_t^{\mathrm{floor}} := \lim_{R\to\infty} q_t^{\mathrm{clean}}(R) = P_s(p_t(s)=0). \tag*{(13)} q t clean ( R ) := E s [ ( 1 − p t ( s ) ) R ] , q t floor := R → ∞ lim q t clean ( R ) = P s ( p t ( s ) = 0 ) . (13)
The limit follows by bounded convergence; a nonzero floor can arise from positive mass on locally unsolvable instances, rather than from independent retries at a fixed positive success probability. A two-component approximation assigns mass q t f l o o r q_t^{\mathrm{floor}} q t floor to such instances and uses a common failure probability ε l o c , t ∈ [ 0 , 1 ) \varepsilon_{\mathrm{loc},t}\in[0,1) ε loc , t ∈ [ 0 , 1 ) for the remaining instances:
q t c l e a n ( R ) ≈ q t f l o o r + ( 1 − q t f l o o r ) ε l o c , t R . (14) q_t^{\mathrm{clean}}(R) \approx q_t^{\mathrm{floor}} + (1-q_t^{\mathrm{floor}})\varepsilon_{\mathrm{loc},t}^R. \tag*{(14)} q t clean ( R ) ≈ q t floor + ( 1 − q t floor ) ε loc , t R . (14)
This expression is exact for the stated two-point mixture; independence alone does not imply this mixture or a common failure probability on solvable instances. Its zero-floor special case is
q t f l o o r = 0 ⟹ q t c l e a n ( R ) ≈ ε l o c , t R . (15) q_t^{\mathrm{floor}}=0 \quad\Longrightarrow\quad q_t^{\mathrm{clean}}(R)\approx\varepsilon_{\mathrm{loc},t}^R. \tag*{(15)} q t floor = 0 ⟹ q t clean ( R ) ≈ ε loc , t R . (15)
These probabilities concern generated candidates before checking. They do not include the effect of accepting an incorrect candidate or rejecting a correct one. The arithmetic experiments in § 4.4 use complete-answer attempts. The unsolved fraction at R = 32 R=32 R = 32 neither identifies an asymptotic error floor nor estimates the theorem’s per-step failure probability.
Proofs and Supporting Analysis
This appendix gives the formal results and their proofs. It covers complete-solution sampling, retry budgets, stage composition, and stopped state reuse. Each result specifies its assumptions.
Setup and Notation
We use the same model notation throughout the paper: θ \theta θ denotes the parameters of the reasoning model, and p θ p_\theta p θ denotes its induced generation distribution. For a problem x x x , fix a decomposition into N ≥ 1 N\ge1 N ≥ 1 steps and write a sampled reasoning chain as z 1 : N = ( z 1 , … , z N ) z_{1:N}=(z_1,\ldots,z_N) z 1 : N = ( z 1 , … , z N ) , where z t z_t z t is the text generated at step t t t . Let s t = [ x , z 1 : t ] s_t=[x,z_{1:t}] s t = [ x , z 1 : t ] denote the full generated history after step t t t , with s 0 = x s_0=x s 0 = x . In reuse, s t s_t s t instead denotes the task information and intermediate results actually passed forward, as in § 2 ; the prompt presents this state to the model. Each step is sampled autoregressively from p θ ( ⋅ ∣ s t − 1 ) p_\theta(\cdot\mid s_{t-1}) p θ ( ⋅ ∣ s t − 1 ) . The final answer y y y is extracted from the completed run. The reuse result assumes that correct completion of every stage yields a correct final answer: every accepted state is correct and all stages terminate, extraction returns the composite target (for two stages, [ a ∗ ( x 1 ) , a ∗ ( x 2 ) ] [a^*(x_1),a^*(x_2)] [ a ∗ ( x 1 ) , a ∗ ( x 2 )] ; likewise for multiple stages below). Correctness refers to the retained state, not to reasoning discarded during answer extraction. For local step analysis, G t ( s t − 1 , z t ) ∈ { 0 , 1 } G_t(s_{t-1},z_t)\in\{0,1\} G t ( s t − 1 , z t ) ∈ { 0 , 1 } indicates whether the resulting state is correct, q t : = P ( G t = 0 ) q_t:=P(G_t=0) q t := P ( G t = 0 ) is its failure probability, and q t c l e a n q_t^{\mathrm{clean}} q t clean is the corresponding probability when all preceding states are correct. The check V t ( s t − 1 , z t ) ∈ { 0 , 1 } V_t(s_{t-1},z_t)\in\{0,1\} V t ( s t − 1 , z t ) ∈ { 0 , 1 } separately records rejection or acceptance and may disagree with G t G_t G t . We write N ( x ) N(x) N ( x ) for the length of the chosen decomposition of x x x , abbreviated as N N N when the problem is clear. The single-run quantities are C θ , 1 ( x ) = E [ L ] C_{\theta,1}(x)=\mathbb{E}[L] C θ , 1 ( x ) = E [ L ] and A θ , 1 ( x ) = P ( y = a ∗ ( x ) ) A_{\theta,1}(x)=P(y=a^*(x)) A θ , 1 ( x ) = P ( y = a ∗ ( x )) , where L L L is the total generated token count. For two subproblems x 1 , x 2 x_1,x_2 x 1 , x 2 , their composition x 1 ⊕ x 2 x_1\oplus x_2 x 1 ⊕ x 2 is formed by concatenating them with a connector prompt. We define its composite target as a ∗ ( x 1 ⊕ x 2 ) : = [ a ∗ ( x 1 ) , a ∗ ( x 2 ) ] a^*(x_1\oplus x_2):=[a^*(x_1),a^*(x_2)] a ∗ ( x 1 ⊕ x 2 ) := [ a ∗ ( x 1 ) , a ∗ ( x 2 )] . For these chosen decompositions, step-count additivity means that the step counts satisfy
N ( x 1 ⊕ x 2 ) = N ( x 1 ) + N ( x 2 ) . (16) N(x_1\oplus x_2)=N(x_1)+N(x_2). \tag*{(16)} N ( x 1 ⊕ x 2 ) = N ( x 1 ) + N ( x 2 ) . (16)
Operationally, our experiments use distinct MATH subjects as a practical proxy for reduced concept overlap across subproblems. Step-count additivity does not imply the marginal-matching or probabilistic independence assumptions of Prop. 3. For reuse, a step must admit independent repeated attempts from a fixed input state and an accept-or-reject check V V V . The ideal predicate G \mathcal{G} G defines correctness, whereas V V V is the check applied to candidate states; acceptance alone does not imply G = 1 \mathcal{G}=1 G = 1 . In the reuse proofs, 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 uniformly bounds ρ t ( s ) \rho_t(s) ρ t ( s ) , and α \alpha α uniformly bounds the error rate α t ( R ; s ) \alpha_t(R;s) α t ( R ; s ) among accepted states over all relevant steps, correct accepted input states s s s , and attempt budgets R R R . With R R R total attempts, equivalently R − 1 R-1 R − 1 retries, all candidates are rejected with probability at most ρ R \rho^R ρ R . Returning an incorrect accepted state is a separate source of failure. For independent sampling, the accuracy and generation cost of K K K complete runs satisfy
A θ , K ( x ) = 1 − ( 1 − A θ , 1 ( x ) ) K (17) A_{\theta,K}(x) = 1 - (1 - A_{\theta,1}(x))^K \tag*{(17)} A θ , K ( x ) = 1 − ( 1 − A θ , 1 ( x ) ) K (17)
C θ , K ( x ) = K ⋅ C θ , 1 ( x ) (18) C_{\theta,K}(x) = K \cdot C_{\theta,1}(x) \tag*{(18)} C θ , K ( x ) = K ⋅ C θ , 1 ( x ) (18)
Here A θ , K A_{\theta,K} A θ , K is Pass@K K K coverage and C θ , K C_{\theta,K} C θ , K is expected generation cost; K = 1 K=1 K = 1 denotes a single complete run. Across task lengths N N N , the conditional scaling assumptions are
C θ , 1 ( x ) = Θ ( N ) (Compute Law) (19) C_{\theta,1}(x) = \Theta(N) \qquad\text{(Compute Law)} \tag*{(19)} C θ , 1 ( x ) = Θ ( N ) (Compute Law) (19)
A θ , 1 ( x ) = exp ( − λ θ N ) , λ θ > 0 (Accuracy Law) (20) A_{\theta,1}(x) = \exp(-\lambda_\theta N), \qquad\lambda_\theta> 0 \qquad\text{(Accuracy Law)} \tag*{(20)} A θ , 1 ( x ) = exp ( − λ θ N ) , λ θ > 0 (Accuracy Law) (20)
Notation conventions. All probabilities denoted by P ( ⋅ ) P(\cdot) P ( ⋅ ) are taken under the relevant sampling process induced by p θ p_\theta p θ ; p θ p_\theta p θ itself denotes the model distribution. For an integer K K K , [ K ] [K] [ K ] denotes { 1 , … , K } \{1,\ldots,K\} { 1 , … , K } . The symbol ≪ \ll ≪ denotes an informal “much smaller than” condition in limiting approximations. Failure budgets satisfy δ , δ i , δ m ∈ ( 0 , 1 ) \delta,\delta_i,\delta_m \in(0,1) δ , δ i , δ m ∈ ( 0 , 1 ) , with δ = δ 1 + δ 2 \delta=\delta_1+\delta_2 δ = δ 1 + δ 2 in the two-stage result and ∑ m δ m = δ \sum_m \delta_m=\delta ∑ m δ m = δ in the multi-stage result, where the sum ranges over all stages of the task.
Ideal Laws Under Per-Step Errors
We begin with the success probability and cost implied by independent per-step errors. This calculation concerns a step decomposition; the arithmetic experiments measure complete-answer coverage.
Proposition 1 (Exponential Decay of Success Probability). Consider a chosen decomposition into N N N steps, each with independent failure probability ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and assume the final answer is correct if and only if all N N N steps are correct. Then:
A θ , 1 ( x ) = ( 1 − ε ) N ≤ e − ε N (21) A_{\theta,1}(x) = (1-\varepsilon)^N \le e^{-\varepsilon N} \tag*{(21)} A θ , 1 ( x ) = ( 1 − ε ) N ≤ e − εN (21) where the equality ( 1 − ε ) N (1-\varepsilon)^N ( 1 − ε ) N is exact and the upper bound e − ε N e^{-\varepsilon N} e − εN follows from log ( 1 − ε ) ≤ − ε \log(1-\varepsilon) \le-\varepsilon log ( 1 − ε ) ≤ − ε . This gives Eq. (74) with the per-step accuracy decay rate λ θ = − log ( 1 − ε ) \lambda_\theta=-\log(1-\varepsilon) λ θ = − log ( 1 − ε ) .
Proof. Step 1: Success requires all steps. Let F i F_i F i indicate failure at step i i i ; each step succeeds with probability 1 − ε 1-\varepsilon 1 − ε , so independence yields the following product:
A θ , 1 ( x ) = ∏ i = 1 N P ( F i = 0 ) = ( 1 − ε ) N . (22) A_{\theta,1}(x) = \prod_{i=1}^{N} P(F_i=0) = (1-\varepsilon)^N. \tag*{(22)} A θ , 1 ( x ) = i = 1 ∏ N P ( F i = 0 ) = ( 1 − ε ) N . (22)
Step 2: Logarithmic inequality. Since log \log log is concave and log ( 1 ) = 0 \log(1)=0 log ( 1 ) = 0 , the tangent line at x = 1 x=1 x = 1 gives log ( x ) ≤ x − 1 \log(x)\le x-1 log ( x ) ≤ x − 1 for all x > 0 x>0 x > 0 . Substituting x = 1 − ε x=1-\varepsilon x = 1 − ε : log ( 1 − ε ) ≤ ( 1 − ε ) − 1 = − ε \log(1-\varepsilon)\le(1-\varepsilon)-1=-\varepsilon log ( 1 − ε ) ≤ ( 1 − ε ) − 1 = − ε for all ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . Taking the natural logarithm of Step 1:
log A θ , 1 ( x ) = N log ( 1 − ε ) ≤ − ε N . (23) \log A_{\theta,1}(x) = N\log(1-\varepsilon) \le-\varepsilon N. \tag*{(23)} log A θ , 1 ( x ) = N log ( 1 − ε ) ≤ − εN . (23)
Step 3: Exponential bound and approximation. Exponentiating both sides:
A θ , 1 ( x ) ≤ e − ε N . (24) A_{\theta,1}(x) \le e^{-\varepsilon N}. \tag*{(24)} A θ , 1 ( x ) ≤ e − εN . (24)
For fixed N N N as ε → 0 \varepsilon\to0 ε → 0 , the Taylor expansion log ( 1 − ε ) = − ε + O ( ε 2 ) \log(1-\varepsilon)=-\varepsilon+O(\varepsilon^2) log ( 1 − ε ) = − ε + O ( ε 2 ) yields A θ , 1 ( x ) / e − ε N → 1 A_{\theta,1}(x)/e^{-\varepsilon N}\to1 A θ , 1 ( x ) / e − εN → 1 . □ \square □
The Compositionality Breakdown under Independent Sampling
We first give a general event-inclusion bound for a common pool of composite runs, then prove the conditional product comparison used in the main text.
Proposition 2 (Event-Inclusion Bound). For any K ≥ 1 K \ge1 K ≥ 1 , sample a common pool of K K K composite runs for x 1 ⊕ x 2 x_1 \oplus x_2 x 1 ⊕ x 2 . Let E i K E_i^K E i K denote coverage of a correct answer to x i x_i x i , and E 12 K E_{12}^K E 12 K coverage of both correct answers in one run. These events satisfy
P ( E 12 K ) ≤ P ( E 1 K ∩ E 2 K ) ≤ min { P ( E 1 K ) , P ( E 2 K ) } , (25) P(E_{12}^K) \le P(E_1^K \cap E_2^K) \le\min\{P(E_1^K), P(E_2^K)\}, \tag*{(25)} P ( E 12 K ) ≤ P ( E 1 K ∩ E 2 K ) ≤ min { P ( E 1 K ) , P ( E 2 K )} , (25) without independence. All probabilities refer to the common pool of composite runs.
Proposition 3 (Product Form). Let a : = A θ , 1 ( x 1 ) ∈ ( 0 , 1 ) a := A_{\theta,1}(x_1) \in(0,1) a := A θ , 1 ( x 1 ) ∈ ( 0 , 1 ) and b : = A θ , 1 ( x 2 ) ∈ ( 0 , 1 ) b := A_{\theta,1}(x_2) \in(0,1) b := A θ , 1 ( x 2 ) ∈ ( 0 , 1 ) . Assume each subproblem has the same correctness probability in a composite run as in its standalone run, the two correctness indicators are independent within each composite run, and the composite runs are i.i.d. across K K K samples. Then A θ , 1 ( x 1 ⊕ x 2 ) = a b A_{\theta,1}(x_1 \oplus x_2) = ab A θ , 1 ( x 1 ⊕ x 2 ) = ab and:
A θ , K ( x 1 ⊕ x 2 ) < A θ , K ( x 1 ) ⋅ A θ , K ( x 2 ) , ∀ K ≥ 2. (26) A_{\theta,K}(x_1 \oplus x_2) < A_{\theta,K}(x_1) \cdot A_{\theta,K}(x_2), \qquad\forall K \ge2. \tag*{(26)} A θ , K ( x 1 ⊕ x 2 ) < A θ , K ( x 1 ) ⋅ A θ , K ( x 2 ) , ∀ K ≥ 2. (26)
Remark 1 (Experimental proxy). The main-text product comparison relies on the assumptions of Prop. 3; the same-pool event-inclusion bound of Prop. 2 holds without independence. Our experiments sample subproblem pairs from distinct MATH subjects to encourage reduced concept overlap across subproblems. The no_context ablation in Table 3 gives a descriptive comparison: second-subproblem success without x 1 x_1 x 1 information is 36.2%. This differs from joint success on both problems, and the available standalone x 2 x_2 x 2 reference covers fewer models than the second-subproblem evaluation. As discussed in Appendix § 11 , subject separation establishes neither independence within a run nor matching success rates across prompt formats.
Proof of Prop. 2. For a pool of K K K composite runs with sample space Ω \Omega Ω , define
E 12 K : = { ∃ k : run k returns a correct answer to both x 1 and x 2 } , E 1 K : = { ∃ k : run k returns a correct answer to x 1 } , (27) \begin{aligned}
E_{12}^K &:= \{\exists k : \text{run } k \text{ returns a correct answer to both } x_1 \text{ and } x_2\},\\
E_1^K &:= \{\exists k : \text{run } k \text{ returns a correct answer to } x_1\}, \tag*{(27)}
\end{aligned} E 12 K E 1 K := { ∃ k : run k returns a correct answer to both x 1 and x 2 } , := { ∃ k : run k returns a correct answer to x 1 } , (27)
and analogously E 2 K E_2^K E 2 K for x 2 x_2 x 2 . The inclusion E 12 K ⊆ E 1 K ∩ E 2 K E_{12}^K \subseteq E_1^K \cap E_2^K E 12 K ⊆ E 1 K ∩ E 2 K holds: if some run k k k is correct on both subproblems, then that same run witnesses E 1 K E_1^K E 1 K and witnesses E 2 K E_2^K E 2 K . Monotonicity of probability gives P ( E 12 K ) ≤ P ( E 1 K ∩ E 2 K ) ≤ min { P ( E 1 K ) , P ( E 2 K ) } P(E_{12}^K) \le P(E_1^K \cap E_2^K) \le\min\{P(E_1^K), P(E_2^K)\} P ( E 12 K ) ≤ P ( E 1 K ∩ E 2 K ) ≤ min { P ( E 1 K ) , P ( E 2 K )} , which is Eq. (25) . This bound holds for every K K K without assuming independence of subproblem-answer correctness.
Proof of Prop. 3. Assume the matching composite/standalone marginals, within-run independence, and across-run i.i.d. conditions, and let a : = A θ , 1 ( x 1 ) a := A_{\theta,1}(x_1) a := A θ , 1 ( x 1 ) and b : = A θ , 1 ( x 2 ) b := A_{\theta,1}(x_2) b := A θ , 1 ( x 2 ) , so that A θ , 1 ( x 1 ⊕ x 2 ) = a b A_{\theta,1}(x_1 \oplus x_2) = ab A θ , 1 ( x 1 ⊕ x 2 ) = ab . For K K K independently sampled runs, define indicator random variables: X k ∈ { 0 , 1 } X_k \in\{0,1\} X k ∈ { 0 , 1 } records that sampled run k k k succeeds on x 1 x_1 x 1 with P ( X k = 1 ) = a P(X_k = 1) = a P ( X k = 1 ) = a ; Y k ∈ { 0 , 1 } Y_k \in\{0,1\} Y k ∈ { 0 , 1 } records that sampled run k k k succeeds on x 2 x_2 x 2 with P ( Y k = 1 ) = b P(Y_k = 1) = b P ( Y k = 1 ) = b ; and Z k : = X k Y k Z_k := X_kY_k Z k := X k Y k records that sampled run k k k succeeds on both with P ( Z k = 1 ) = a b P(Z_k = 1) = ab P ( Z k = 1 ) = ab . The two sequences are independent, with i.i.d. entries within each sequence.
Step 1: Event formulation. Define success events:
E 1 K : = { ∃ k : X k = 1 } , E 2 K : = { ∃ k : Y k = 1 } , E 12 K : = { ∃ k : Z k = 1 } . (28) E_1^K := \{\exists k : X_k = 1\}, \qquad E_2^K := \{\exists k : Y_k = 1\}, \qquad E_{12}^K := \{\exists k : Z_k = 1\}. \tag*{(28)} E 1 K := { ∃ k : X k = 1 } , E 2 K := { ∃ k : Y k = 1 } , E 12 K := { ∃ k : Z k = 1 } . (28)
Independence across runs gives the following probabilities for the three success events:
P ( E 1 K ) = 1 − ( 1 − a ) K , P ( E 2 K ) = 1 − ( 1 − b ) K , P ( E 12 K ) = 1 − ( 1 − a b ) K . (29) P(E_1^K) = 1 - (1-a)^K, \qquad P(E_2^K) = 1 - (1-b)^K, \qquad P(E_{12}^K) = 1 - (1-ab)^K. \tag*{(29)} P ( E 1 K ) = 1 − ( 1 − a ) K , P ( E 2 K ) = 1 − ( 1 − b ) K , P ( E 12 K ) = 1 − ( 1 − ab ) K . (29)
Step 2: Set inclusion. Key observation: E 12 K ⊆ E 1 K ∩ E 2 K E_{12}^{K} \subseteq E_{1}^{K} \cap E_{2}^{K} E 12 K ⊆ E 1 K ∩ E 2 K . To see this, suppose ζ ∈ E 12 K \zeta\in E_{12}^{K} ζ ∈ E 12 K , so there exists k k k with Z k ( ζ ) = X k ( ζ ) Y k ( ζ ) = 1 Z_k(\zeta) = X_k(\zeta)Y_k(\zeta) = 1 Z k ( ζ ) = X k ( ζ ) Y k ( ζ ) = 1 . Then X k ( ζ ) = 1 X_k(\zeta) = 1 X k ( ζ ) = 1 , hence ζ ∈ E 1 K \zeta\in E_{1}^{K} ζ ∈ E 1 K ; and Y k ( ζ ) = 1 Y_k(\zeta) = 1 Y k ( ζ ) = 1 , hence ζ ∈ E 2 K \zeta\in E_{2}^{K} ζ ∈ E 2 K . Therefore ζ ∈ E 1 K ∩ E 2 K \zeta\in E_{1}^{K} \cap E_{2}^{K} ζ ∈ E 1 K ∩ E 2 K , completing the inclusion. Monotonicity of probability gives:
P ( E 12 K ) ≤ P ( E 1 K ∩ E 2 K ) . (30) P(E_{12}^{K}) \leq P(E_{1}^{K} \cap E_{2}^{K}). \tag*{(30)} P ( E 12 K ) ≤ P ( E 1 K ∩ E 2 K ) . (30)
Step 3: Independence gives exact product. Since { X k } k = 1 K \{X_k\}_{k=1}^{K} { X k } k = 1 K and { Y k } k = 1 K \{Y_k\}_{k=1}^{K} { Y k } k = 1 K are mutually independent by assumption, any event measurable w.r.t. { X k } \{X_k\} { X k } alone is independent of any event measurable w.r.t. { Y k } \{Y_k\} { Y k } alone. E 1 K = { ∃ k : X k = 1 } E_{1}^{K} = \{\exists k : X_k = 1\} E 1 K = { ∃ k : X k = 1 } depends only on { X k } \{X_k\} { X k } , and E 2 K = { ∃ k : Y k = 1 } E_{2}^{K} = \{\exists k : Y_k = 1\} E 2 K = { ∃ k : Y k = 1 } depends only on { Y k } \{Y_k\} { Y k } . Therefore E 1 K E_{1}^{K} E 1 K and E 2 K E_{2}^{K} E 2 K are independent:
P ( E 1 K ∩ E 2 K ) = P ( E 1 K ) P ( E 2 K ) = [ 1 − ( 1 − a ) K ] [ 1 − ( 1 − b ) K ] . (31) P(E_{1}^{K} \cap E_{2}^{K}) = P(E_{1}^{K})P(E_{2}^{K}) = [1 - (1-a)^{K}][1 - (1-b)^{K}]. \tag*{(31)} P ( E 1 K ∩ E 2 K ) = P ( E 1 K ) P ( E 2 K ) = [ 1 − ( 1 − a ) K ] [ 1 − ( 1 − b ) K ] . (31)
Combining this product identity with the event inclusion from Step 2 gives the comparison
1 − ( 1 − a b ) K ≤ [ 1 − ( 1 − a ) K ] [ 1 − ( 1 − b ) K ] . (32) 1 - (1-ab)^{K} \leq[1 - (1-a)^{K}][1 - (1-b)^{K}]. \tag*{(32)} 1 − ( 1 − ab ) K ≤ [ 1 − ( 1 − a ) K ] [ 1 − ( 1 − b ) K ] . (32)
This establishes the non-strict product comparison in Prop. 3; strictness is proved next.
Step 4: Strictness. For K ≥ 2 K \geq2 K ≥ 2 and a , b ∈ ( 0 , 1 ) a,b \in(0,1) a , b ∈ ( 0 , 1 ) , the inequality is strict. Consider the event:
E 1 , 2 : = { X 1 = 1 , Y 1 = 0 , X 2 = 0 , Y 2 = 1 , ∀ k ≥ 3 : X k Y k = 0 } . (33) E_{1,2} := \{X_1 = 1,\ Y_1 = 0,\ X_2 = 0,\ Y_2 = 1,\ \forall k \geq3 : X_kY_k = 0\}. \tag*{(33)} E 1 , 2 := { X 1 = 1 , Y 1 = 0 , X 2 = 0 , Y 2 = 1 , ∀ k ≥ 3 : X k Y k = 0 } . (33)
The following three properties show that this event has positive mass outside joint success.
(i) E 1 , 2 ⊆ E 1 K ∩ E 2 K E_{1,2} \subseteq E_{1}^{K} \cap E_{2}^{K} E 1 , 2 ⊆ E 1 K ∩ E 2 K . X 1 = 1 X_1 = 1 X 1 = 1 implies E 1 K E_{1}^{K} E 1 K ; Y 2 = 1 Y_2 = 1 Y 2 = 1 implies E 2 K E_{2}^{K} E 2 K .
(ii) E 1 , 2 ⊆ ( E 12 K ) c E_{1,2} \subseteq(E_{12}^{K})^{c} E 1 , 2 ⊆ ( E 12 K ) c . Under E 1 , 2 E_{1,2} E 1 , 2 : sampled run 1 has Z 1 = X 1 Y 1 = 1 ⋅ 0 = 0 Z_1 = X_1Y_1 = 1 \cdot0 = 0 Z 1 = X 1 Y 1 = 1 ⋅ 0 = 0 ; sampled run 2 has Z 2 = X 2 Y 2 = 0 ⋅ 1 = 0 Z_2 = X_2Y_2 = 0 \cdot1 = 0 Z 2 = X 2 Y 2 = 0 ⋅ 1 = 0 ; and Z k = 0 Z_k = 0 Z k = 0 for all k ≥ 3 k \geq3 k ≥ 3 by construction. Hence no sampled run succeeds on both subproblems, so E 12 K E_{12}^{K} E 12 K does not occur under this construction.
(iii) P ( E 1 , 2 ) > 0 P(E_{1,2}) > 0 P ( E 1 , 2 ) > 0 . By mutual independence of all { X k } \{X_k\} { X k } and { Y k } \{Y_k\} { Y k } :
P ( E 1 , 2 ) = a ( 1 − b ) ( 1 − a ) b ∏ k = 3 K ( 1 − a b ) = a b ( 1 − a ) ( 1 − b ) ( 1 − a b ) K − 2 > 0 , (34) P(E_{1,2}) = a(1-b)(1-a)b \prod_{k=3}^{K}(1-ab) = ab(1-a)(1-b)(1-ab)^{K-2} > 0, \tag*{(34)} P ( E 1 , 2 ) = a ( 1 − b ) ( 1 − a ) b k = 3 ∏ K ( 1 − ab ) = ab ( 1 − a ) ( 1 − b ) ( 1 − ab ) K − 2 > 0 , (34)
The strict positivity follows because every factor is positive for a , b ∈ ( 0 , 1 ) a,b \in(0,1) a , b ∈ ( 0 , 1 ) .
Properties (i) and (ii) give E 1 , 2 ⊆ ( E 1 K ∩ E 2 K ) ∖ E 12 K E_{1,2} \subseteq(E_{1}^{K} \cap E_{2}^{K}) \setminus E_{12}^{K} E 1 , 2 ⊆ ( E 1 K ∩ E 2 K ) ∖ E 12 K , so P ( ( E 1 K ∩ E 2 K ) ∖ E 12 K ) ≥ P ( E 1 , 2 ) > 0 P((E_{1}^{K} \cap E_{2}^{K}) \setminus E_{12}^{K}) \geq P(E_{1,2}) > 0 P (( E 1 K ∩ E 2 K ) ∖ E 12 K ) ≥ P ( E 1 , 2 ) > 0 , establishing the required strict comparison P ( E 12 K ) < P ( E 1 K ∩ E 2 K ) P(E_{12}^{K}) < P(E_{1}^{K} \cap E_{2}^{K}) P ( E 12 K ) < P ( E 1 K ∩ E 2 K ) for every K ≥ 2 K \geq2 K ≥ 2 .
Low accuracy behavior in the difficult problem range. Under the assumptions of Prop. 3, consider the ratio between composite accuracy and the product of standalone accuracies when K a , K b ≪ 1 Ka, Kb \ll1 K a , K b ≪ 1 . The approximation 1 − ( 1 − x ) K ≈ K x 1 - (1-x)^{K} \approx Kx 1 − ( 1 − x ) K ≈ K x for K x ≪ 1 Kx \ll1 K x ≪ 1 follows from ( 1 − x ) K = 1 − K x + O ( K 2 x 2 ) (1-x)^{K} = 1 - Kx + O(K^{2}x^{2}) ( 1 − x ) K = 1 − K x + O ( K 2 x 2 ) . Applying this to each term:
A θ , K ( x 1 ) = 1 − ( 1 − a ) K ≈ K a , A θ , K ( x 2 ) = 1 − ( 1 − b ) K ≈ K b , A_{\theta,K}(x_1) = 1 - (1-a)^{K} \approx Ka,\qquad A_{\theta,K}(x_2) = 1 - (1-b)^{K} \approx Kb, A θ , K ( x 1 ) = 1 − ( 1 − a ) K ≈ K a , A θ , K ( x 2 ) = 1 − ( 1 − b ) K ≈ K b ,
A θ , K ( x 1 ⊕ x 2 ) = 1 − ( 1 − a b ) K ≈ K ( a b ) , A_{\theta,K}(x_1 \oplus x_2) = 1 - (1-ab)^{K} \approx K(ab), A θ , K ( x 1 ⊕ x 2 ) = 1 − ( 1 − ab ) K ≈ K ( ab ) ,
where the last line uses K ( a b ) ≤ K a ⋅ b ≤ K a ≪ 1 K(ab) \leq Ka \cdot b \leq Ka \ll1 K ( ab ) ≤ K a ⋅ b ≤ K a ≪ 1 , ensuring the approximation is valid. Define σ : = A θ , K ( x 1 ⊕ x 2 ) / [ A θ , K ( x 1 ) A θ , K ( x 2 ) ] \sigma:= A_{\theta,K}(x_1 \oplus x_2)/[A_{\theta,K}(x_1)A_{\theta,K}(x_2)] σ := A θ , K ( x 1 ⊕ x 2 ) / [ A θ , K ( x 1 ) A θ , K ( x 2 )] . Then σ = 1 \sigma= 1 σ = 1 means accuracy compositionality, and σ < 1 \sigma< 1 σ < 1 means composite accuracy falls below the product of standalone accuracies. The resulting first-order ratio quantifies the relative gap before either accuracy saturates:
σ = A θ , K ( x 1 ⊕ x 2 ) A θ , K ( x 1 ) ⋅ A θ , K ( x 2 ) ≈ K ( a b ) ( K a ) ( K b ) = K a b K 2 a b = 1 K . (35) \sigma= \frac{A_{\theta,K}(x_1 \oplus x_2)}{A_{\theta,K}(x_1) \cdot A_{\theta,K}(x_2)} \approx\frac{K(ab)}{(Ka)(Kb)} = \frac{Kab}{K^{2}ab} = \frac{1}{K}. \tag*{(35)} σ = A θ , K ( x 1 ) ⋅ A θ , K ( x 2 ) A θ , K ( x 1 ⊕ x 2 ) ≈ ( K a ) ( K b ) K ( ab ) = K 2 ab K ab = K 1 . (35)
This 1 / K 1/K 1/ K degradation scales inversely with the number of samples in the low-accuracy regime, showing that the relative compositionality breakdown of independent sampling worsens before saturation. This first-order approximation requires K a , K b ≪ 1 Ka, Kb \ll1 K a , K b ≪ 1 . Under the assumptions of Prop. 3, the product inequality (26) holds for all K ≥ 2 K \geq2 K ≥ 2 and a , b ∈ ( 0 , 1 ) a,b \in(0,1) a , b ∈ ( 0 , 1 ) ; the common-pool inclusion in Eq. (25) remains valid for dependent subproblem-answer correctness.
State Reuse: Mathematical Foundations
We now derive a product lower bound on success and a sufficient computation budget for state reuse.
Definition 1 (Retry Loop). Start from s 0 ∨ = x s_0^{\vee}=x s 0 ∨ = x . At step t t t , let s = s t − 1 ∨ s=s_{t-1}^{\vee} s = s t − 1 ∨ be the fixed accepted input state and ρ t ( s ) : = P ( V t = 0 ∣ s ) \rho_t(s):=P(V_t=0\mid s) ρ t ( s ) := P ( V t = 0 ∣ s ) its single-attempt rejection probability. The loop uses an integer cap R ≥ 1 R\ge1 R ≥ 1 and repeats the following generation and checking steps:
Sample a candidate span z t ( r ) ∼ p θ ( ⋅ ∣ s ) z_t^{(r)}\sim p_\theta(\cdot\mid s) z t ( r ) ∼ p θ ( ⋅ ∣ s ) from the fixed input state.
Form the candidate intermediate state s ~ t ( r ) \tilde{s}_t^{(r)} s ~ t ( r ) , using either the full state [ s , z t ( r ) ] [s,z_t^{(r)}] [ s , z t ( r ) ] or the prescribed extracted intermediate answer.
Check V t ( s ~ t ( r ) ) V_t(\tilde{s}_t^{(r)}) V t ( s ~ t ( r ) ) ; if accepted, return s t ∨ = s ~ t ( r ) s_t^{\vee}=\tilde{s}_t^{(r)} s t ∨ = s ~ t ( r ) and proceed.
If rejected, retry from the same s s s until R R R total attempts have been used; if all are rejected, stop with failure.
Let A t ( R ) A_t^{(R)} A t ( R ) be the event that the loop returns an accepted state, and let G t \mathcal{G}_t G t indicate whether that state is correct. Define accepted-state error, the error probability conditional on acceptance, as
α t ( R ; s ) : = P ( G t = 0 ∣ A t ( R ) , s ) . (36) \alpha_t(R;s):=P\left(\mathcal{G}_t=0\mid A_t^{(R)},s\right). \tag*{(36)} α t ( R ; s ) := P ( G t = 0 ∣ A t ( R ) , s ) . (36) Assume generation and check outcomes are independent and identically distributed across attempts conditional on s s s . Failure comprises budget exhaustion or an incorrect acceptance:
β t ( R ; s ) : = ρ t ( s ) R + ( 1 − ρ t ( s ) R ) α t ( R ; s ) ≤ ρ t ( s ) R + α t ( R ; s ) . (37) \begin{aligned}
\beta_t(R;s)&:=\rho_t(s)^R+\left(1-\rho_t(s)^R\right)\alpha_t(R;s)\\
&\le\rho_t(s)^R+\alpha_t(R;s). \tag*{(37)}
\end{aligned} β t ( R ; s ) := ρ t ( s ) R + ( 1 − ρ t ( s ) R ) α t ( R ; s ) ≤ ρ t ( s ) R + α t ( R ; s ) . (37) The two terms are budget exhaustion and an incorrect state returned as accepted; the formal loop does not return a fallback after all candidates are rejected.
Proposition 4 (Logarithmic Attempt Requirement). Under the assumptions of Def. 1, suppose ρ t ( s ) ≤ ρ \rho_t(s)\le\rho ρ t ( s ) ≤ ρ for a fixed 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and α t ( r ; s ) ≤ α \alpha_t(r;s)\le\alpha α t ( r ; s ) ≤ α for every relevant step, correct accepted input state s s s , and budget r r r . To keep the probability of any step exhausting its budget or accepting an incorrect state at most δ \delta δ , it suffices that N α < δ N\alpha<\delta N α < δ and
R ≥ ⌈ log ( N / ( δ − N α ) ) log ( 1 / ρ ) ⌉ . (38) R\ge\left\lceil\frac{\log(N/(\delta-N\alpha))}{\log(1/\rho)}\right\rceil. \tag*{(38)} R ≥ ⌈ log ( 1/ ρ ) log ( N / ( δ − N α )) ⌉ . (38) For fixed 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and α ≤ c δ / N \alpha\le c\delta/N α ≤ cδ / N with fixed 0 ≤ c < 1 0\le c<1 0 ≤ c < 1 , the sufficient budget above is Θ ( log ( N / δ ) ) \Theta(\log(N/\delta)) Θ ( log ( N / δ )) ; in the separate case ρ = 0 \rho=0 ρ = 0 , one attempt suffices for the rejection term.
Proof. Step 1: Union bound. Let H i − 1 H_{i-1} H i − 1 be the event that the first i − 1 i-1 i − 1 steps complete with correct accepted states, and let E i : = H i − 1 ∩ { step i fails after its R -attempt loop } E_i:=H_{i-1}\cap\{\text{step }i\text{ fails after its }R\text{-attempt loop}\} E i := H i − 1 ∩ { step i fails after its R -attempt loop } be the first-failure event at
@page 24/51 starts_mid=0 ends_mid=1
State Reuse: Mathematical Foundations
We now derive a product lower bound on success and a sufficient computation budget for state reuse.
Definition 1 (Retry Loop). Start from s 0 ∨ = x s_0^{\vee}=x s 0 ∨ = x . At step t t t , let s = s t − 1 ∨ s=s_{t-1}^{\vee} s = s t − 1 ∨ be the fixed accepted input state and ρ t ( s ) : = P ( V t = 0 ∣ s ) \rho_t(s):=P(V_t=0\mid s) ρ t ( s ) := P ( V t = 0 ∣ s ) its single-attempt rejection probability. The loop uses an integer cap R ≥ 1 R\ge1 R ≥ 1 and repeats the following generation and checking steps:
Sample a candidate span z t ( r ) ∼ p θ ( ⋅ ∣ s ) z_t^{(r)}\sim p_\theta(\cdot\mid s) z t ( r ) ∼ p θ ( ⋅ ∣ s ) from the fixed input state.
Form the candidate intermediate state s ~ t ( r ) \tilde{s}_t^{(r)} s ~ t ( r ) , using either the full state [ s , z t ( r ) ] [s,z_t^{(r)}] [ s , z t ( r ) ] or the prescribed extracted intermediate answer.
Check V t ( s ~ t ( r ) ) V_t(\tilde{s}_t^{(r)}) V t ( s ~ t ( r ) ) ; if accepted, return s t ∨ = s ~ t ( r ) s_t^{\vee}=\tilde{s}_t^{(r)} s t ∨ = s ~ t ( r ) and proceed.
If rejected, retry from the same s s s until R R R total attempts have been used; if all are rejected, stop with failure.
Let A t ( R ) A_t^{(R)} A t ( R ) be the event that the loop returns an accepted state, and let G t \mathcal{G}_t G t indicate whether that state is correct. Define accepted-state error, the error probability conditional on acceptance, as
α t ( R ; s ) : = P ( G t = 0 ∣ A t ( R ) , s ) . (39) \alpha_t(R;s):=P\left(\mathcal{G}_t=0\mid A_t^{(R)},s\right). \tag*{(39)} α t ( R ; s ) := P ( G t = 0 ∣ A t ( R ) , s ) . (39) Assume generation and check outcomes are independent and identically distributed across attempts conditional on s s s . Failure comprises budget exhaustion or an incorrect acceptance:
β t ( R ; s ) : = ρ t ( s ) R + ( 1 − ρ t ( s ) R ) α t ( R ; s ) ≤ ρ t ( s ) R + α t ( R ; s ) . (40) \begin{aligned}
\beta_t(R;s)&:=\rho_t(s)^R+\left(1-\rho_t(s)^R\right)\alpha_t(R;s)\\
&\le\rho_t(s)^R+\alpha_t(R;s). \tag*{(40)}
\end{aligned} β t ( R ; s ) := ρ t ( s ) R + ( 1 − ρ t ( s ) R ) α t ( R ; s ) ≤ ρ t ( s ) R + α t ( R ; s ) . (40) The two terms are budget exhaustion and an incorrect state returned as accepted; the formal loop does not return a fallback after all candidates are rejected.
Proposition 4 (Logarithmic Attempt Requirement). Under the assumptions of Def. 1, suppose ρ t ( s ) ≤ ρ \rho_t(s)\le\rho ρ t ( s ) ≤ ρ for a fixed 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and α t ( r ; s ) ≤ α \alpha_t(r;s)\le\alpha α t ( r ; s ) ≤ α for every relevant step, correct accepted input state s s s , and budget r r r . To keep the probability of any step exhausting its budget or accepting an incorrect state at most δ \delta δ , it suffices that N α < δ N\alpha<\delta N α < δ and
R ≥ ⌈ log ( N / ( δ − N α ) ) log ( 1 / ρ ) ⌉ . (41) R\ge\left\lceil\frac{\log(N/(\delta-N\alpha))}{\log(1/\rho)}\right\rceil. \tag*{(41)} R ≥ ⌈ log ( 1/ ρ ) log ( N / ( δ − N α )) ⌉ . (41) For fixed 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and α ≤ c δ / N \alpha\le c\delta/N α ≤ cδ / N with fixed 0 ≤ c < 1 0\le c<1 0 ≤ c < 1 , the sufficient budget above is Θ ( log ( N / δ ) ) \Theta(\log(N/\delta)) Θ ( log ( N / δ )) ; in the separate case ρ = 0 \rho=0 ρ = 0 , one attempt suffices for the rejection term.
Proof. Step 1: Union bound. Let H i − 1 H_{i-1} H i − 1 be the event that the first i − 1 i-1 i − 1 steps complete with correct accepted states, and let E i : = H i − 1 ∩ { step i fails after its R -attempt loop } E_i:=H_{i-1}\cap\{\text{step }i\text{ fails after its }R\text{-attempt loop}\} E i := H i − 1 ∩ { step i fails after its R -attempt loop } be the first-failure event at step i i i . These disjoint first-failure events exhaust trajectory failure, so the union bound gives
P ( g l o b a l f a i l ) = P ( ⋃ i = 1 N E i ) ≤ ∑ i = 1 N P ( E i ) . (42) P(\mathrm{global\ fail}) = P\left(\bigcup_{i=1}^{N} E_i\right) \le\sum_{i=1}^{N} P(E_i). \tag*{(42)} P ( global fail ) = P ( i = 1 ⋃ N E i ) ≤ i = 1 ∑ N P ( E i ) . (42)
Conditioned on H i − 1 H_{i-1} H i − 1 , step i i i starts from a correct accepted prefix. By Eq. (37), P ( E i ) ≤ P ( step i fails ∣ H i − 1 ) ≤ ρ R + α P(E_i) \le P(\text{step } i \text{ fails} \mid H_{i-1}) \le\rho^{R} + \alpha P ( E i ) ≤ P ( step i fails ∣ H i − 1 ) ≤ ρ R + α , giving:
P ( g l o b a l f a i l ) ≤ N ( ρ R + α ) . (43) P(\mathrm{global\ fail}) \le N(\rho^{R}+\alpha). \tag*{(43)} P ( global fail ) ≤ N ( ρ R + α ) . (43)
Step 2: Per-Step Target. For N α < δ N\alpha< \delta N α < δ , the per-step requirement is
N ( ρ R + α ) ≤ δ ⟺ ρ R ≤ δ − N α N . (44) N(\rho^{R}+\alpha) \le\delta\qquad\Longleftrightarrow\qquad\rho^{R} \le\frac{\delta-N\alpha}{N}. \tag*{(44)} N ( ρ R + α ) ≤ δ ⟺ ρ R ≤ N δ − N α . (44)
Step 3: Solve for R R R . Taking logarithms (note log ρ < 0 \log\rho< 0 log ρ < 0 , so the inequality flips):
R log ρ ≤ log ( δ − N α N ) (45) R\log\rho\le\log\left(\frac{\delta-N\alpha}{N}\right) \tag*{(45)} R log ρ ≤ log ( N δ − N α ) (45)
R ≥ log ( N / ( δ − N α ) ) log ( 1 / ρ ) . (46) R \ge\frac{\log\left(N/(\delta-N\alpha)\right)}{\log(1/\rho)}. \tag*{(46)} R ≥ log ( 1/ ρ ) log ( N / ( δ − N α ) ) . (46)
Because the attempt budget is an integer, taking the ceiling gives a sufficient choice:
R ≥ ⌈ log ( N / ( δ − N α ) ) log ( 1 / ρ ) ⌉ . (47) R \ge\left\lceil\frac{\log\left(N/(\delta-N\alpha)\right)}{\log(1/\rho)}\right\rceil. \tag*{(47)} R ≥ ⌈ log ( 1/ ρ ) log ( N / ( δ − N α ) ) ⌉ . (47)
If, for example, N α ≤ c δ N\alpha\le c\delta N α ≤ cδ for a fixed c < 1 c < 1 c < 1 , then R = Θ ( log ( N / δ ) ) R = \Theta(\log(N/\delta)) R = Θ ( log ( N / δ )) . More attempts alone cannot establish this guarantee when the bound on accepted-state errors already reaches δ \delta δ .
Accepted-State Error under a Fixed Check
Fix a correct input state s s s and a step t t t . Suppose the same candidate-generation law and the same single-candidate checking rule are used independently on every attempt, irrespective of the attempt cap R R R . Let ρ = P ( V t = 0 ∣ s ) < 1 \rho= P(V_t = 0 \mid s) < 1 ρ = P ( V t = 0 ∣ s ) < 1 and w = P ( G t = 0 , V t = 1 ∣ s ) w = P(G_t = 0, V_t = 1 \mid s) w = P ( G t = 0 , V t = 1 ∣ s ) . Returning an incorrect state on attempt r r r requires rejection on the first r − 1 r-1 r − 1 attempts and an incorrect acceptance on attempt r r r . Summing over the possible first-acceptance attempts gives the joint and acceptance probabilities
P ( i n c o r r e c t r e t u r n e d s t a t e , A t ( R ) ∣ s ) = ∑ r = 1 R ρ r − 1 w = w ( 1 − ρ R ) 1 − ρ , (48) P(\mathrm{incorrect\ returned\ state}, A_t^{(R)} \mid s) = \sum_{r=1}^{R} \rho^{r-1}w = \frac{w(1-\rho^{R})}{1-\rho}, \tag*{(48)} P ( incorrect returned state , A t ( R ) ∣ s ) = r = 1 ∑ R ρ r − 1 w = 1 − ρ w ( 1 − ρ R ) , (48)
P ( A t ( R ) ∣ s ) = 1 − ρ R . (49) P(A_t^{(R)} \mid s) = 1-\rho^{R}. \tag*{(49)} P ( A t ( R ) ∣ s ) = 1 − ρ R . (49)
Dividing by the acceptance probability yields the conditional error and the total local failure:
α t ( R ; s ) = w 1 − ρ , β t ( R ; s ) = ρ R + ( 1 − ρ R ) w 1 − ρ . (50) \alpha_t(R;s) = \frac{w}{1-\rho}, \qquad\beta_t(R;s) = \rho^{R} + (1-\rho^{R})\frac{w}{1-\rho}. \tag*{(50)} α t ( R ; s ) = 1 − ρ w , β t ( R ; s ) = ρ R + ( 1 − ρ R ) 1 − ρ w . (50)
The conditional error among accepted states is independent of R R R in this fixed-check setting, and the local failure probability approaches that error as R R R grows. This calculation includes false rejections through ρ \rho ρ ; w / ( 1 − ρ ) w/(1-\rho) w / ( 1 − ρ ) is the error conditional on acceptance, not the probability of acceptance conditional on an incorrect candidate. Changing the voting pool or acceptance threshold changes the checking rule and can therefore change the error among accepted states.
A batch selector could be treated as one local attempt only after its returned-state law, rejection event, and computation cost are specified. Independent batches would then need the corresponding conditional bounds at every correct prefix. The empirical protocol’s multiple retained states and fallback continuations are not obtained merely by substituting M M M for R R R in the single-state theorem.
Product Lower Bound Under State Reuse
The next proposition composes stage reliability guarantees and adds their computation budgets.
Proposition 5 (Product Lower Bound for State Reuse). For subproblems x 1 , x 2 x_1,x_2 x 1 , x 2 with N 1 , N 2 N_1,N_2 N 1 , N 2 steps, assume the loop of Def. 1. At stage i i i , let ρ i , t ( s ) ≤ ρ i \rho_{i,t}(s) \le\rho_i ρ i , t ( s ) ≤ ρ i with 0 < ρ i < 1 0 < \rho_i < 1 0 < ρ i < 1 and α i , t ( r ; s ) ≤ α i \alpha_{i,t}(r; s) \le\alpha_i α i , t ( r ; s ) ≤ α i for every step, correct accepted input state s s s , and budget r r r . For stage 2, these bounds must hold for every correct state passed from stage 1. Let δ 1 , δ 2 > 0 \delta_1,\delta_2 > 0 δ 1 , δ 2 > 0 be target failure probabilities with δ 1 + δ 2 = δ \delta_1 + \delta_2 = \delta δ 1 + δ 2 = δ . Assume each stage reaches a well-defined final state after its prescribed N i N_i N i accepted steps. Let S i S_i S i denote completion of stage i i i with every accepted state correct. Completing both stages correctly must yield the target under answer extraction:
S 1 ∩ S 2 ⊆ { y = a ∗ ( x 1 ⊕ x 2 ) } . S_1 \cap S_2 \subseteq\{y = a^*(x_1 \oplus x_2)\}. S 1 ∩ S 2 ⊆ { y = a ∗ ( x 1 ⊕ x 2 )} . When N i α i < δ i N_i\alpha_i < \delta_i N i α i < δ i , allocate the following sufficient attempt budget to each step in stage i i i :
R i ≥ ⌈ log ( N i / ( δ i − N i α i ) ) log ( 1 / ρ i ) ⌉ , (51) R_i \ge\left\lceil\frac{\log(N_i/(\delta_i-N_i\alpha_i))}{\log(1/\rho_i)} \right\rceil, \tag*{(51)} R i ≥ ⌈ log ( 1/ ρ i ) log ( N i / ( δ i − N i α i )) ⌉ , (51) By Prop. 4, stage i i i then fails to complete with all accepted states correct with probability at most δ i \delta_i δ i . Under these assumptions, state reuse satisfies:
A v s r ( x 1 ⊕ x 2 ) ≥ ( 1 − δ 1 ) ( 1 − δ 2 ) = 1 − δ + δ 1 δ 2 ≥ 1 − δ . (52) A_{\mathrm{vsr}}(x_1 \oplus x_2) \ge(1-\delta_1)(1-\delta_2) = 1-\delta+\delta_1\delta_2 \ge1-\delta. \tag*{(52)} A vsr ( x 1 ⊕ x 2 ) ≥ ( 1 − δ 1 ) ( 1 − δ 2 ) = 1 − δ + δ 1 δ 2 ≥ 1 − δ . (52) This exact lower bound uses target stage guarantees rather than standalone accuracies.
Computation budget. Set δ i = δ N i / ( N 1 + N 2 ) \delta_i = \delta N_i/(N_1+N_2) δ i = δ N i / ( N 1 + N 2 ) and use the common error bound α i = α \alpha_i = \alpha α i = α . Both subproblems then have the same per-step target failure probability:
δ 1 N 1 = δ 2 N 2 = δ N 1 + N 2 . (53) \frac{\delta_1}{N_1} = \frac{\delta_2}{N_2} = \frac{\delta}{N_1+N_2}. \tag*{(53)} N 1 δ 1 = N 2 δ 2 = N 1 + N 2 δ . (53)
If N α < δ N\alpha< \delta N α < δ for N = N 1 + N 2 N = N_1 + N_2 N = N 1 + N 2 and ρ i ≤ ρ < 1 \rho_i \le\rho< 1 ρ i ≤ ρ < 1 , choose the common attempt count
R ∗ = ⌈ log ( N / ( δ − N α ) ) log ( 1 / ρ ) ⌉ (54) R^* = \left\lceil\frac{\log(N/(\delta-N\alpha))}{\log(1/\rho)} \right\rceil \tag*{(54)} R ∗ = ⌈ log ( 1/ ρ ) log ( N / ( δ − N α )) ⌉ (54)
This choice satisfies both stage constraints. Let c g e n c_{\mathrm{gen}} c gen and c v e r c_{\mathrm{ver}} c ver uniformly bound generation and checking costs per attempt in a common unit, for all reached states. The per-step computation budget is c ˉ s t e p ( R ∗ ) = R ∗ ( c g e n + c v e r ) \bar{c}_{\mathrm{step}}(R^*) = R^*(c_{\mathrm{gen}}+c_{\mathrm{ver}}) c ˉ step ( R ∗ ) = R ∗ ( c gen + c ver ) . It is an upper bound on actual cost and sums across stages:
C ‾ v s r ( x 1 ) + C ‾ v s r ( x 2 ) = N 1 c ˉ s t e p ( R ∗ ) + N 2 c ˉ s t e p ( R ∗ ) = ( N 1 + N 2 ) c ˉ s t e p ( R ∗ ) = C ‾ v s r ( x 1 ⊕ x 2 ) . (55) \begin{aligned}
\overline{C}_{\mathrm{vsr}}(x_1)+\overline{C}_{\mathrm{vsr}}(x_2)
&= N_1\bar{c}_{\mathrm{step}}(R^*)+N_2\bar{c}_{\mathrm{step}}(R^*) \\
&= (N_1+N_2)\bar{c}_{\mathrm{step}}(R^*) = \overline{C}_{\mathrm{vsr}}(x_1\oplus x_2). \tag*{(55)}
\end{aligned} C vsr ( x 1 ) + C vsr ( x 2 ) = N 1 c ˉ step ( R ∗ ) + N 2 c ˉ step ( R ∗ ) = ( N 1 + N 2 ) c ˉ step ( R ∗ ) = C vsr ( x 1 ⊕ x 2 ) . (55)
Proof of Prop. 5. Step 1: Reliability of x 1 x_1 x 1 . For R 1 R_1 R 1 from Eq. (51) , every correct accepted prefix s s s has local failure bounded by the allocated per-step target for the first stage:
β 1 , t ( R 1 ; s ) ≤ ρ 1 R 1 + α 1 ≤ δ 1 N 1 . (56) \beta_{1,t}(R_1;s) \le\rho_1^{R_1}+\alpha_1 \le\frac{\delta_1}{N_1}. \tag*{(56)} β 1 , t ( R 1 ; s ) ≤ ρ 1 R 1 + α 1 ≤ N 1 δ 1 . (56)
A union bound over the N 1 N_1 N 1 possible first-failure locations gives the first-stage guarantee:
P ( S 1 c ) ≤ N 1 ( ρ 1 R 1 + α 1 ) ≤ δ 1 , hence P ( S 1 ) ≥ 1 − δ 1 . (57) P(S_1^{\mathrm{c}}) \le N_1(\rho_1^{R_1}+\alpha_1) \le\delta_1,\qquad\text{hence}\quad P(S_1) \ge1-\delta_1. \tag*{(57)} P ( S 1 c ) ≤ N 1 ( ρ 1 R 1 + α 1 ) ≤ δ 1 , hence P ( S 1 ) ≥ 1 − δ 1 . (57)
Step 2: Reliability of x 2 x_2 x 2 from correct accepted x 1 x_1 x 1 states. With R 2 R_2 R 2 satisfying Eq. (51) , each attempt is drawn from the model given its fixed accepted input state. The bounds ρ 2 \rho_2 ρ 2 and α 2 \alpha_2 α 2 must hold for every correct accepted state passed from x 1 x_1 x 1 ; acceptance alone does not establish this requirement. Conditioning on an arbitrary such state s N 1 ✓ s_{N_1}^{\checkmark} s N 1 ✓ yields the same second-stage bound:
P ( S 2 ✓ ∣ s N 1 ✓ , S 1 ) ≤ N 2 ( ρ 2 R 2 + α 2 ) ≤ δ 2 . (58) P\left(S_2^{\checkmark} \mid s_{N_1}^{\checkmark}, S_1\right) \le N_2(\rho_2^{R_2}+\alpha_2) \le\delta_2. \tag*{(58)} P ( S 2 ✓ ∣ s N 1 ✓ , S 1 ) ≤ N 2 ( ρ 2 R 2 + α 2 ) ≤ δ 2 . (58)
Marginalizing over correct accepted states (i.e., conditioning on S 1 S_1 S 1 ):
P ( S 2 ✓ ∣ S 1 ) = E [ P ( S 2 ✓ ∣ s N 1 ✓ , S 1 ) ∣ S 1 ] ≤ δ 2 , (59) P(S_2^{\checkmark} \mid S_1) = \mathbb{E}\left[P\left(S_2^{\checkmark} \mid s_{N_1}^{\checkmark}, S_1\right) \mid S_1\right] \le\delta_2, \tag*{(59)} P ( S 2 ✓ ∣ S 1 ) = E [ P ( S 2 ✓ ∣ s N 1 ✓ , S 1 ) ∣ S 1 ] ≤ δ 2 , (59)
Thus the conditional second-stage reliability satisfies the allocated target, P ( S 2 ∣ S 1 ) ≥ 1 − δ 2 P(S_2 \mid S_1) \ge1-\delta_2 P ( S 2 ∣ S 1 ) ≥ 1 − δ 2 .
Step 3: Composite accuracy via chain rule. By assumption, S 1 ∩ S 2 S_1 \cap S_2 S 1 ∩ S 2 implies that the prescribed extraction returns a correct composite answer. The probability chain rule gives:
A v s r ( x 1 ⊕ x 2 ) ≥ P ( S 1 ∩ S 2 ) = P ( S 1 ) ⋅ P ( S 2 ∣ S 1 ) ≥ ( 1 − δ 1 ) ( 1 − δ 2 ) . (60) \mathrm{A}_{\mathrm{vsr}}(x_1 \oplus x_2) \ge P(S_1 \cap S_2) = P(S_1)\cdot P(S_2 \mid S_1) \ge(1-\delta_1)(1-\delta_2). \tag*{(60)} A vsr ( x 1 ⊕ x 2 ) ≥ P ( S 1 ∩ S 2 ) = P ( S 1 ) ⋅ P ( S 2 ∣ S 1 ) ≥ ( 1 − δ 1 ) ( 1 − δ 2 ) . (60)
Step 4: Target level product bound. Expanding gives ( 1 − δ 1 ) ( 1 − δ 2 ) = 1 − δ + δ 1 δ 2 ≥ 1 − δ (1-\delta_1)(1-\delta_2)=1-\delta+\delta_1\delta_2\ge1-\delta ( 1 − δ 1 ) ( 1 − δ 2 ) = 1 − δ + δ 1 δ 2 ≥ 1 − δ . No small-δ i \delta_i δ i approximation is needed for this lower bound because the cross term is nonnegative. Equation (60) is an exact lower bound; equality with actual standalone accuracies is not implied.
Comparison with independent sampling. The two propositions compare different quantities. Under Prop. 3, independent sampling yields composite accuracy below the product of standalone accuracies, with a ratio of approximately 1 / K 1/K 1/ K when K a , K b ≪ 1 Ka, Kb \ll1 K a , K b ≪ 1 . Under Prop. 5, reuse from accepted states yields a product lower bound in stage reliability guarantees; it concerns target guarantees rather than an equality of actual standalone accuracies.
Multi-Stage Generalization
We extend Prop. 5 by induction to arbitrary multi-stage workflows with J J J subproblems x = x 1 ⊕ ⋯ ⊕ x J x=x_1\oplus\cdots\oplus x_J x = x 1 ⊕ ⋯ ⊕ x J , each requiring N m N_m N m steps, for a total of N = ∑ m = 1 J N m N=\sum_{m=1}^{J}N_m N = ∑ m = 1 J N m .
Step 1: Proportional budget allocation. Allocate failure budgets proportionally to step counts:
δ m : = δ N m N , ∑ m = 1 J δ m = δ . (61) \delta_m := \delta\frac{N_m}{N}, \qquad\sum_{m=1}^{J}\delta_m=\delta. \tag*{(61)} δ m := δ N N m , m = 1 ∑ J δ m = δ . (61)
This yields a uniform per-step target across all subproblems:
δ m N m = δ N for all m ∈ [ J ] . (62) \frac{\delta_m}{N_m}=\frac{\delta}{N}\quad\text{for all }m\in[J]. \tag*{(62)} N m δ m = N δ for all m ∈ [ J ] . (62)
Step 2: Uniform attempt count. Assume ρ t ( s ) ≤ ρ \rho_t(s)\le\rho ρ t ( s ) ≤ ρ with 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and α t ( r ; s ) ≤ α \alpha_t(r;s)\le\alpha α t ( r ; s ) ≤ α for all stages, relevant steps, correct accepted input states s s s , and attempt budgets r r r , with N α < δ N\alpha<\delta N α < δ . Prop. 4 gives a common sufficient retry budget by imposing the constraint ρ R + α ≤ δ / N \rho^R+\alpha\le\delta/N ρ R + α ≤ δ / N at each step:
R ≥ ⌈ log ( N / ( δ − N α ) ) log ( 1 / ρ ) ⌉ = Θ ( log N δ ) (63) R\ge\left\lceil\frac{\log\left(N/(\delta-N\alpha)\right)}{\log(1/\rho)}\right\rceil=\Theta\left(\log\frac{N}{\delta}\right) \tag*{(63)} R ≥ ⌈ log ( 1/ ρ ) log ( N / ( δ − N α ) ) ⌉ = Θ ( log δ N ) (63)
when N α ≤ c δ N\alpha\le c\delta N α ≤ cδ for a fixed 0 ≤ c < 1 0\le c<1 0 ≤ c < 1 . Since all stages receive the same error allowance per step, this common attempt budget meets the reliability requirement for every stage length N m N_m N m .
Step 3: Summing the computation budget. Let R ∗ R^{*} R ∗ be the smallest integer budget in Eq. (63) . Each attempt costs at most c g e n + c v e r c_{\mathrm{gen}} + c_{\mathrm{ver}} c gen + c ver , so the per-step computation budget is
c ‾ s t e p ( R ∗ ) = R ∗ ( c g e n + c v e r ) . (64) \overline{c}_{\mathrm{step}}(R^{*}) = R^{*}(c_{\mathrm{gen}} + c_{\mathrm{ver}}). \tag*{(64)} c step ( R ∗ ) = R ∗ ( c gen + c ver ) . (64)
Since R ∗ R^{*} R ∗ is the same for all subproblems, the computation budget sums across stages. Actual cost is no larger because each loop stops at first acceptance:
C ‾ v s r ( x ) = ∑ m = 1 J C ‾ v s r ( x m ) = ∑ m = 1 J N m ⋅ c ‾ s t e p ( R ∗ ) = ( ∑ m = 1 J N m ) c ‾ s t e p ( R ∗ ) = N ⋅ c ‾ s t e p ( R ∗ ) . (65) \begin{aligned}
\overline{C}_{\mathrm{vsr}}(x) = \sum_{m=1}^{J} \overline{C}_{\mathrm{vsr}}(x_m) = \sum_{m=1}^{J} N_m \cdot\overline{c}_{\mathrm{step}}(R^{*}) \\
&= \left(\sum_{m=1}^{J} N_m\right)\overline{c}_{\mathrm{step}}(R^{*}) = N \cdot\overline{c}_{\mathrm{step}}(R^{*}). \tag*{(65)}
\end{aligned} C vsr ( x ) = m = 1 ∑ J C vsr ( x m ) = m = 1 ∑ J N m ⋅ c step ( R ∗ ) = ( m = 1 ∑ J N m ) c step ( R ∗ ) = N ⋅ c step ( R ∗ ) . (65)
The additive budget upper-bounds the expected total cost of reuse.
Step 4: Success probability across stages. Assume each stage reaches a well-defined final state after its prescribed N m N_m N m accepted steps. Let S m S_m S m denote stage-m m m completion with every accepted state correct. Assume that completing all stages correctly yields a correct final answer under the prescribed extraction. The probability chain rule gives:
P ( ⋂ m = 1 J S m ) = P ( S 1 ) ∏ m = 2 J P ( S m | ⋂ j = 1 m − 1 S j ) . (66) P\left(\bigcap_{m=1}^{J} S_m\right) = P(S_1)\prod_{m=2}^{J} P\left(S_m \,\middle|\, \bigcap_{j=1}^{m-1} S_j\right). \tag*{(66)} P ( m = 1 ⋂ J S m ) = P ( S 1 ) m = 2 ∏ J P ( S m j = 1 ⋂ m − 1 S j ) . (66)
As in Step 2 of the proof of Prop. 5 , completion of all earlier stages with correct states gives stage m m m a correct accepted input state. The uniform bounds give per-step failure probability at most ρ R + α \rho^{R} + \alpha ρ R + α . Applying Prop. 4 with target failure probability δ m \delta_m δ m and N m N_m N m steps yields:
P ( S m | ⋂ j = 1 m − 1 S j ) ≥ 1 − δ m , for all m . (67) P\left(S_m \,\middle|\, \bigcap_{j=1}^{m-1} S_j\right) \ge1 - \delta_m,\quad\text{for all }m. \tag*{(67)} P ( S m j = 1 ⋂ m − 1 S j ) ≥ 1 − δ m , for all m . (67)
Substituting these conditional stage guarantees into Eq. (66) gives
A v s r ( x ) ≥ P ( ⋂ m = 1 J S m ) ≥ ∏ m = 1 J ( 1 − δ m ) . (68) A_{\mathrm{vsr}}(x) \ge P\left(\bigcap_{m=1}^{J} S_m\right) \ge\prod_{m=1}^{J}(1-\delta_m). \tag*{(68)} A vsr ( x ) ≥ P ( m = 1 ⋂ J S m ) ≥ m = 1 ∏ J ( 1 − δ m ) . (68)
Step 5: Product bounds. The product of stage guarantees obeys the following exact inequality:
∏ m = 1 J ( 1 − δ m ) ≥ 1 − ∑ m = 1 J δ m . \prod_{m=1}^{J}(1-\delta_m) \ge1-\sum_{m=1}^{J}\delta_m. m = 1 ∏ J ( 1 − δ m ) ≥ 1 − m = 1 ∑ J δ m .
For J = 1 J=1 J = 1 there is equality. Suppose the inequality holds for J − 1 J-1 J − 1 factors; the induction step gives
∏ m = 1 J ( 1 − δ m ) = ∏ m = 1 J − 1 ( 1 − δ m ) ⋅ ( 1 − δ J ) ≥ ( 1 − ∑ m = 1 J − 1 δ m ) ( 1 − δ J ) = 1 − ∑ m = 1 J δ m + δ J ∑ m = 1 J − 1 δ m ≥ 1 − ∑ m = 1 J δ m , \begin{aligned}
\prod_{m=1}^{J}(1-\delta_m) = \prod_{m=1}^{J-1}(1-\delta_m)\cdot(1-\delta_J) \ge\left(1-\sum_{m=1}^{J-1}\delta_m\right)(1-\delta_J) \\
&=1-\sum_{m=1}^{J}\delta_m+\delta_J\sum_{m=1}^{J-1}\delta_m \ge1-\sum_{m=1}^{J}\delta_m,
\end{aligned} m = 1 ∏ J ( 1 − δ m ) = m = 1 ∏ J − 1 ( 1 − δ m ) ⋅ ( 1 − δ J ) ≥ ( 1 − m = 1 ∑ J − 1 δ m ) ( 1 − δ J ) = 1 − m = 1 ∑ J δ m + δ J m = 1 ∑ J − 1 δ m ≥ 1 − m = 1 ∑ J δ m ,
where the last step drops the nonnegative cross term. Therefore:
∏ m = 1 J ( 1 − δ m ) ≥ 1 − ∑ m = 1 J δ m = 1 − δ . (69) \prod_{m=1}^{J}(1-\delta_m) \ge1-\sum_{m=1}^{J}\delta_m = 1-\delta. \tag*{(69)} m = 1 ∏ J ( 1 − δ m ) ≥ 1 − m = 1 ∑ J δ m = 1 − δ . (69)
The exact product inequality therefore gives the desired guarantee A v s r ( x ) ≥ 1 − δ A_{\mathrm{vsr}}(x) \ge1-\delta A vsr ( x ) ≥ 1 − δ .
Exponential lower bound: We use 1 − x ≥ e − x / ( 1 − x ) 1-x \ge e^{-x/(1-x)} 1 − x ≥ e − x / ( 1 − x ) for x ∈ [ 0 , 1 ) x \in[0,1) x ∈ [ 0 , 1 ) , which follows from log ( 1 − x ) ≥ − x / ( 1 − x ) \log(1-x) \ge-x/(1-x) log ( 1 − x ) ≥ − x / ( 1 − x ) . To verify it, let f ( x ) = log ( 1 − x ) + x / ( 1 − x ) f(x)=\log(1-x)+x/(1-x) f ( x ) = log ( 1 − x ) + x / ( 1 − x ) ; then f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 and f ′ ( x ) = x / ( 1 − x ) 2 ≥ 0 f'(x)=x/(1-x)^2 \ge0 f ′ ( x ) = x / ( 1 − x ) 2 ≥ 0 . For δ m = δ N m / N ≪ 1 \delta_m=\delta N_m/N \ll1 δ m = δ N m / N ≪ 1 , we have 1 / ( 1 − δ m ) = 1 + δ m + O ( δ m 2 ) ≈ 1 1/(1-\delta_m)=1+\delta_m+O(\delta_m^2)\approx1 1/ ( 1 − δ m ) = 1 + δ m + O ( δ m 2 ) ≈ 1 , so δ m / ( 1 − δ m ) ≈ δ m + δ m 2 \delta_m/(1-\delta_m)\approx\delta_m+\delta_m^2 δ m / ( 1 − δ m ) ≈ δ m + δ m 2 . Substitution gives the following exponential comparison for the product of stage guarantees:
∏ m = 1 J ( 1 − δ m ) ≥ exp ( − ∑ m = 1 J δ m 1 − δ m ) ≈ exp ( − δ − ∑ m = 1 J δ m 2 ) . (70) \prod_{m=1}^{J}(1-\delta_m)\ge\exp\left(-\sum_{m=1}^{J}\frac{\delta_m}{1-\delta_m}\right)\approx\exp\left(-\delta-\sum_{m=1}^{J}\delta_m^2\right). \tag*{(70)} m = 1 ∏ J ( 1 − δ m ) ≥ exp ( − m = 1 ∑ J 1 − δ m δ m ) ≈ exp ( − δ − m = 1 ∑ J δ m 2 ) . (70)
For δ m = O ( δ / J ) \delta_m=O(\delta/J) δ m = O ( δ / J ) , the second-order term is ∑ m δ m 2 = O ( δ 2 / J ) \sum_m\delta_m^2=O(\delta^2/J) ∑ m δ m 2 = O ( δ 2 / J ) . As the largest stage budget vanishes, we obtain the exponential bound below; the linear approximation also requires δ → 0 \delta\to0 δ → 0 :
A v s r ( x ) ≥ exp ( − δ − o ( δ ) ) ≈ 1 − δ . (71) A_{\mathrm{vsr}}(x)\ge\exp(-\delta-o(\delta))\approx1-\delta. \tag*{(71)} A vsr ( x ) ≥ exp ( − δ − o ( δ )) ≈ 1 − δ . (71)
Together with Step 3, this establishes A v s r ( x ) ≥ ∏ m ( 1 − δ m ) ≥ 1 − δ A_{\mathrm{vsr}}(x)\ge\prod_m(1-\delta_m)\ge1-\delta A vsr ( x ) ≥ ∏ m ( 1 − δ m ) ≥ 1 − δ and an additive computation budget under proportional failure allocation, provided N α < δ N\alpha<\delta N α < δ .
Complete-Sampling Background
Accuracy Compositionality under Independent Sampling
At budget K K K , accuracy compositionality means that composite accuracy equals A θ , K ( x 1 ) A θ , K ( x 2 ) A_{\theta,K}(x_1)A_{\theta,K}(x_2) A θ , K ( x 1 ) A θ , K ( x 2 ) , the probability of solving both subproblems in separate, independent K K K -attempt experiments. In this established term, accuracy refers to Pass@K K K coverage. For the following comparison, write a i = A θ , 1 ( x i ) ∈ ( 0 , 1 ) a_i=A_{\theta,1}(x_i)\in(0,1) a i = A θ , 1 ( x i ) ∈ ( 0 , 1 ) for i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } . Assume that each subproblem has the same probability of being answered correctly inside a composite run as in its standalone run, and that the two subproblem correctness indicators are independent within each composite run. Together with independence across the K K K runs, these assumptions give:
A θ , 1 ( x 1 ⊕ x 2 ) = a 1 a 2 , A θ , K ( x 1 ⊕ x 2 ) = 1 − ( 1 − a 1 a 2 ) K < A θ , K ( x 1 ) A θ , K ( x 2 ) , K ≥ 2. (72) \begin{aligned}
A_{\theta,1}(x_1\oplus x_2)&=a_1a_2,\\
A_{\theta,K}(x_1\oplus x_2)&=1-(1-a_1a_2)^K<A_{\theta,K}(x_1)A_{\theta,K}(x_2),\quad K\ge2. \tag*{(72)}
\end{aligned} A θ , 1 ( x 1 ⊕ x 2 ) A θ , K ( x 1 ⊕ x 2 ) = a 1 a 2 , = 1 − ( 1 − a 1 a 2 ) K < A θ , K ( x 1 ) A θ , K ( x 2 ) , K ≥ 2. (72)
For K = 1 K=1 K = 1 , the corresponding product relation holds with equality. The strict gap for K ≥ 2 K\ge2 K ≥ 2 arises because each composite success requires one run to solve both subproblems, whereas separately covered subproblems may be solved by different runs. For example, when both subproblems have single-run accuracy 0.5 and K = 2 K=2 K = 2 , complete-solution success is 0.4375, compared with 0.5625 for separate sampling. This requirement that one run solve both subproblems is the single-run requirement under independent sampling. The event inclusion behind it holds without the product assumptions: a pool containing a jointly correct run also covers each subproblem separately, while the converse need not hold (Prop. 2). The comparison fixes attempts per subproblem; it does not equate measured token costs across prompt formats. This bottleneck is a property of sampling and aggregation, and would also occur for modular stochastic solvers with independent errors.
Sampling Cost as Task Length Grows
To compare computational cost as task length grows at a fixed target success rate, we consider decompositions indexed by N N N and adopt the idealized scaling assumptions of Zhang et al. [41 ] . For a fixed model and decoding configuration, assume:
C θ , 1 ( x ) = Θ ( N ) , A θ , 1 ( x ) = e − λ θ N , λ θ > 0. (73) C_{\theta,1}(x)=\Theta(N),\qquad A_{\theta,1}(x)=e^{-\lambda_\theta N},\qquad\lambda_\theta>0. \tag*{(73)} C θ , 1 ( x ) = Θ ( N ) , A θ , 1 ( x ) = e − λ θ N , λ θ > 0. (73)
λ θ \lambda_\theta λ θ is the per-step accuracy decay rate, and linear cost means expected generated tokens scale linearly with N N N up to constant factors. For example, the exponential accuracy relation holds when steps are correct independently with probability 1 − ε 1-\varepsilon 1 − ε , where 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , and the final answer is correct if and only if all N N N steps are correct [3 ] . In this case:
A θ , 1 ( x ) = ( 1 − ε ) N = e − λ θ N , λ θ = − log ( 1 − ε ) . (74) A_{\theta,1}(\mathbf{x})=(1-\varepsilon)^N=e^{-\lambda_{\theta}N},\qquad\lambda_{\theta}=-\log(1-\varepsilon). \tag*{(74)} A θ , 1 ( x ) = ( 1 − ε ) N = e − λ θ N , λ θ = − log ( 1 − ε ) . (74)
For single-run accuracy p = A θ , 1 ( x ) ∈ ( 0 , 1 ) p=A_{\theta,1}(\mathbf{x})\in(0,1) p = A θ , 1 ( x ) ∈ ( 0 , 1 ) , target reliability 1 − δ 1-\delta 1 − δ requires at least
K δ ( N ) = ⌈ log δ log ( 1 − p ) ⌉ . (75) K_{\delta}(N)=\left\lceil\frac{\log\delta}{\log(1-p)}\right\rceil. \tag*{(75)} K δ ( N ) = ⌈ log ( 1 − p ) log δ ⌉ . (75)
At fixed δ \delta δ , the exponential accuracy law gives the asymptotic total generation cost
C i n d e p ( N , δ ) = K δ ( N ) C θ , 1 ( x ) = Θ ( N e λ θ N log ( 1 / δ ) ) . (76) C_{\mathrm{indep}}(N,\delta)=K_{\delta}(N)C_{\theta,1}(\mathbf{x})=\Theta\left(N e^{\lambda_{\theta}N}\log(1/\delta)\right). \tag*{(76)} C indep ( N , δ ) = K δ ( N ) C θ , 1 ( x ) = Θ ( N e λ θ N log ( 1/ δ ) ) . (76)
This restart cost motivates the following analysis of reliability and cost under state reuse.
Sufficient Budgets and Stage Composition
The following bounds give sufficient retry budgets and stage-composition guarantees. They follow from the local failure decomposition and remain valid under the execution assumptions of § 3 . The expected-work theorem sharpens the bound based on the reserved budget while retaining these guarantees. Summing the first-failure probabilities gives the trajectory bound:
P ( trajectory failure ) ≤ N ( ρ R + α ) . (77) P(\text{trajectory failure})\leq N(\rho^R+\alpha). \tag*{(77)} P ( trajectory failure ) ≤ N ( ρ R + α ) . (77)
For 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and N α < δ N\alpha<\delta N α < δ , a sufficient common cap is:
R ∗ = ⌈ log ( N / ( δ − N α ) ) log ( 1 / ρ ) ⌉ . (78) R^*=\left\lceil\frac{\log(N/(\delta-N\alpha))}{\log(1/\rho)}\right\rceil. \tag*{(78)} R ∗ = ⌈ log ( 1/ ρ ) log ( N / ( δ − N α )) ⌉ . (78)
For stages of N 1 , N 2 N_1,N_2 N 1 , N 2 steps, allocate δ i = δ N i / ( N 1 + N 2 ) \delta_i=\delta N_i/(N_1+N_2) δ i = δ N i / ( N 1 + N 2 ) . Let S i S_i S i denote correct completion of stage i i i . If every correct stage-1 output supports the stage-2 guarantee and S 1 ∩ S 2 S_1\cap S_2 S 1 ∩ S 2 yields the target answer, then:
A v s r ( x 1 ⊕ x 2 ) ≥ P ( S 1 ∩ S 2 ) = P ( S 1 ) P ( S 2 ∣ S 1 ) ≥ ( 1 − δ 1 ) ( 1 − δ 2 ) ≥ 1 − δ . (79) A_{\mathrm{vsr}}(x_1\oplus x_2)\geq P(S_1\cap S_2)=P(S_1)P(S_2\mid S_1)\geq(1-\delta_1)(1-\delta_2)\geq1-\delta. \tag*{(79)} A vsr ( x 1 ⊕ x 2 ) ≥ P ( S 1 ∩ S 2 ) = P ( S 1 ) P ( S 2 ∣ S 1 ) ≥ ( 1 − δ 1 ) ( 1 − δ 2 ) ≥ 1 − δ . (79)
Let c g e n , c v e r c_{\mathrm{gen}},c_{\mathrm{ver}} c gen , c ver bound per-attempt generation and checking cost at all reached states, with other processing included in these units. The expected total cost is bounded by the deterministic budget:
C v s r ( N , δ ) ≤ C ‾ v s r ( N , δ ) : = N R ∗ ( c g e n + c v e r ) . (80) C_{\mathrm{vsr}}(N,\delta)\leq\overline{C}_{\mathrm{vsr}}(N,\delta):=NR^*(c_{\mathrm{gen}}+c_{\mathrm{ver}}). \tag*{(80)} C vsr ( N , δ ) ≤ C vsr ( N , δ ) := N R ∗ ( c gen + c ver ) . (80)
For fixed ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) , N α ≤ c δ N\alpha\leq c\delta N α ≤ cδ with fixed c < 1 c<1 c < 1 , and bounded per-attempt costs, the sufficient scaling remains:
R ∗ = Θ ( log ( N / δ ) ) , C v s r = O ( N log ( N / δ ) ) . (81) R^*=\Theta(\log(N/\delta)),\qquad C_{\mathrm{vsr}}=O(N\log(N/\delta)). \tag*{(81)} R ∗ = Θ ( log ( N / δ )) , C vsr = O ( N log ( N / δ )) . (81)
At a fixed correct input state s s s , let T t T_t T t count local attempts. The truncated geometric identity gives:
E [ T t ∣ s ] = ∑ r = 1 R ρ t ( s ) r − 1 = 1 − ρ t ( s ) R 1 − ρ t ( s ) ≤ 1 1 − ρ . (82) \mathbb{E}[T_t\mid s]=\sum_{r=1}^{R}\rho_t(s)^{r-1}=\frac{1-\rho_t(s)^R}{1-\rho_t(s)}\leq\frac{1}{1-\rho}. \tag*{(82)} E [ T t ∣ s ] = r = 1 ∑ R ρ t ( s ) r − 1 = 1 − ρ t ( s ) 1 − ρ t ( s ) R ≤ 1 − ρ 1 . (82)
The product factors are conditional stage guarantees, rather than standalone accuracies under different prompts. If per-attempt cost grows, its dependence on task length must remain in the cost bound.
Proofs for Reliability and Expected Work
Exact Reliability and Minimal Common Cap
Let F t \mathcal{F}_t F t contain the complete history at entry to step t t t , including the event that the step is reached. At a fixed correct entry history, put q = ρ t ( s ) q = \rho_t(s) q = ρ t ( s ) and w = Pr ( G t = 0 , V t = 1 ∣ F t ) w = \Pr(G_t = 0, V_t = 1 \mid\mathcal{F}_t) w = Pr ( G t = 0 , V t = 1 ∣ F t ) . The probability of first accepting an incorrect state on attempt r r r is q r − 1 w q^{r-1}w q r − 1 w . Summing over r ≤ R r \le R r ≤ R and dividing by 1 − q R 1-q^R 1 − q R gives α t ( R ; s ) = w / ( 1 − q ) \alpha_t(R;s) = w/(1-q) α t ( R ; s ) = w / ( 1 − q ) whenever q < 1 q < 1 q < 1 . This establishes Eq. (4) for every finite cap under the fixed retry law. The probability of correct advancement is exactly ( 1 − q R ) ( 1 − α t ( s ) ) (1-q^R)(1-\alpha_t(s)) ( 1 − q R ) ( 1 − α t ( s )) .
On H t − 1 H_{t-1} H t − 1 , all entry histories are correct, so their conditional average has correct-advancement probability at least ( 1 − ρ R ) ( 1 − α ) (1-\rho^R)(1-\alpha) ( 1 − ρ R ) ( 1 − α ) . Multiplying these conditional lower bounds proves Thm. 1. No independence across entry states is needed. The homogeneous construction in that theorem realizes equality and, by making errors irreversible, equates final-answer and trajectory success. Consequently the lower bound is also the infimum of final-answer success over the specified model class.
Write d = ( 1 − δ ) 1 / N d=(1-\delta)^{1/N} d = ( 1 − δ ) 1/ N . For 0 < ρ < 1 0<\rho<1 0 < ρ < 1 , a common cap certifies the target over the entire class exactly when
( 1 − ρ R ) ( 1 − α ) ≥ d . (83) (1-\rho^R)(1-\alpha) \ge d. \tag*{(83)} ( 1 − ρ R ) ( 1 − α ) ≥ d . (83)
For finite R R R , 1 − ρ R < 1 1-\rho^R<1 1 − ρ R < 1 , so this is possible if and only if α < 1 − d \alpha<1-d α < 1 − d . In that case its minimal integer solution is
R min = max { 1 , ⌈ log ( 1 − d / ( 1 − α ) ) log ρ ⌉ } . (84) R_{\min}=\max\left\{1,\left\lceil\frac{\log(1-d/(1-\alpha))}{\log\rho}\right\rceil\right\}. \tag*{(84)} R m i n = max { 1 , ⌈ log ρ log ( 1 − d / ( 1 − α )) ⌉ } . (84)
Both logarithms are negative; division by log ρ \log\rho log ρ reverses the inequality used to solve for R R R . If α = 1 − d \alpha=1-d α = 1 − d , the target is attained only in the limit of unbounded retries. If α > 1 − d \alpha>1-d α > 1 − d , even that limit cannot give a uniform guarantee. When ρ = 0 \rho=0 ρ = 0 , the exact condition is ( 1 − α ) N ≥ 1 − δ (1-\alpha)^N\ge1-\delta ( 1 − α ) N ≥ 1 − δ , and R = 1 R=1 R = 1 suffices. At α = 1 \alpha=1 α = 1 , no positive reliability guarantee follows.
A convenient sufficient choice comes from
1 − [ ( 1 − ρ R ) ( 1 − α ) ] N ≤ N [ ρ R + ( 1 − ρ R ) α ] ≤ N ( ρ R + α ) . (85) 1-\left[(1-\rho^R)(1-\alpha)\right]^N \le N\left[\rho^R+(1-\rho^R)\alpha\right]\le N(\rho^R+\alpha). \tag*{(85)} 1 − [ ( 1 − ρ R ) ( 1 − α ) ] N ≤ N [ ρ R + ( 1 − ρ R ) α ] ≤ N ( ρ R + α ) . (85)
The first inequality is 1 − ( 1 − u ) N ≤ N u 1-(1-u)^N\le Nu 1 − ( 1 − u ) N ≤ N u for u ∈ [ 0 , 1 ] u\in[0,1] u ∈ [ 0 , 1 ] . Solving ρ R ≤ ( δ − N α ) / N \rho^R\le(\delta-N\alpha)/N ρ R ≤ ( δ − N α ) / N gives Eq. (78) whenever N α < δ N\alpha<\delta N α < δ . As N → ∞ N\to\infty N → ∞ at fixed δ \delta δ , 1 − ( 1 − δ ) 1 / N = − log ( 1 − δ ) / N + O ( N − 2 ) 1-(1-\delta)^{1/N}=-\log(1-\delta)/N+O(N^{-2}) 1 − ( 1 − δ ) 1/ N = − log ( 1 − δ ) / N + O ( N − 2 ) . Replacing the numerator by δ \delta δ additionally requires a small-δ \delta δ approximation.
Heterogeneous Steps and Multiple Stages
Suppose step t t t has predetermined cap R t R_t R t and bounds ρ t < 1 \rho_t<1 ρ t < 1 and α t < 1 \alpha_t<1 α t < 1 valid at every correct entry history. Conditioning on H t − 1 H_{t-1} H t − 1 as above gives
Pr ( H N ) ≥ ∏ t = 1 N ( 1 − ρ t R t ) ( 1 − α t ) . (86) \Pr(H_N)\ge\prod_{t=1}^{N}(1-\rho_t^{R_t})(1-\alpha_t). \tag*{(86)} Pr ( H N ) ≥ t = 1 ∏ N ( 1 − ρ t R t ) ( 1 − α t ) . (86)
A bound averaged over standalone inputs need not hold for states produced by earlier stages.
Partition the steps into stages of sizes N 1 , … , N m N_1,\ldots,N_m N 1 , … , N m . If stage j j j completes correctly with conditional probability at least 1 − δ j 1-\delta_j 1 − δ j from every correct entry state, then the probability of correct completion of all stages is at least
∏ j = 1 m ( 1 − δ j ) ≥ 1 − ∑ j = 1 m δ j . (87) \prod_{j=1}^{m}(1-\delta_j)\ge1-\sum_{j=1}^{m}\delta_j. \tag*{(87)} j = 1 ∏ m ( 1 − δ j ) ≥ 1 − j = 1 ∑ m δ j . (87)
For the common bounds of the main text, allocating δ j = δ N j / N \delta_j=\delta N_j/N δ j = δ N j / N and using Eq. (78) supplies such guarantees. These factors need not equal standalone success probabilities. The second stage can meet its target with or without a correct preceding state, despite different success rates.
Expected Attempts: Full Conditional Proof
Let I t I_t I t indicate that step t t t is reached, and define its conditional single-attempt rejection probability ρ t \rho_t ρ t given F t \mathcal{F}_t F t when I t = 1 I_t = 1 I t = 1 . This abbreviation records rejection conditional on the entry history, at both correct and incorrect states. Assign ρ t = 0 \rho_t = 0 ρ t = 0 on unreachable histories, which do not contribute to the sums below. Let T t = 0 T_t = 0 T t = 0 when I t = 0 I_t = 0 I t = 0 and otherwise count the attempts at this step. Conditional i.i.d. retries imply
E [ T t ∣ F t ] = I t ∑ r = 0 R − 1 ρ t r . (88) \mathbb{E}[T_t \mid\mathcal{F}_t] = I_t \sum_{r=0}^{R-1} \rho_t^r. \tag*{(88)} E [ T t ∣ F t ] = I t r = 0 ∑ R − 1 ρ t r . (88)
This identity includes ρ t = 1 \rho_t = 1 ρ t = 1 , for which the sum is R R R . For any θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , the low-rejection contribution satisfies
∑ t = 1 N E [ T t 1 { ρ t ≤ θ } ] ≤ 1 1 − θ ∑ t = 1 N Pr ( I t = 1 , ρ t ≤ θ ) ≤ N 1 − θ . (89) \sum_{t=1}^{N} \mathbb{E}[T_t 1\{\rho_t \le\theta\}] \le\frac{1}{1-\theta}\sum_{t=1}^{N} \Pr(I_t = 1,\rho_t \le\theta) \le\frac{N}{1-\theta}. \tag*{(89)} t = 1 ∑ N E [ T t 1 { ρ t ≤ θ }] ≤ 1 − θ 1 t = 1 ∑ N Pr ( I t = 1 , ρ t ≤ θ ) ≤ 1 − θ N . (89)
Let F t F_t F t denote exhaustion at step t t t and Z = ∑ t I t 1 { ρ t > θ } Z = \sum_t I_t 1\{\rho_t > \theta\} Z = ∑ t I t 1 { ρ t > θ } . Exhaustion has conditional probability ρ t R \rho_t^R ρ t R at a reached step, hence
θ R E [ Z ] ≤ ∑ t = 1 N E [ I t 1 { ρ t > θ } ρ t R ] = ∑ t = 1 N Pr ( F t , ρ t > θ ) ≤ 1. (90) \theta^R\mathbb{E}[Z] \le\sum_{t=1}^{N} \mathbb{E}[I_t 1\{\rho_t > \theta\}\rho_t^R] = \sum_{t=1}^{N} \Pr(F_t,\rho_t > \theta) \le1. \tag*{(90)} θ R E [ Z ] ≤ t = 1 ∑ N E [ I t 1 { ρ t > θ } ρ t R ] = t = 1 ∑ N Pr ( F t , ρ t > θ ) ≤ 1. (90)
The last inequality uses mutual exclusivity of exhaustion events under global stopping. Since a high-rejection visit costs at most R R R , its total expected contribution is at most R θ − R R\theta^{-R} R θ − R . Adding the two contributions gives
E [ W ] ≤ N 1 − θ + R θ R . (91) \mathbb{E}[W] \le\frac{N}{1-\theta} + \frac{R}{\theta^R}. \tag*{(91)} E [ W ] ≤ 1 − θ N + θ R R . (91)
This estimate requires no bound on ρ t \rho_t ρ t , including at states reached after an incorrect acceptance.
For the uniform upper bound, put ℓ N = log ( N + 1 ) \ell_N = \log(N+1) ℓ N = log ( N + 1 ) and θ = e − ℓ N / ( 2 R ) \theta= e^{-\ell_N/(2R)} θ = e − ℓ N / ( 2 R ) . The inequality e u ≥ 1 + u e^u \ge1+u e u ≥ 1 + u yields ( 1 − e − u ) − 1 ≤ 1 + 1 / u (1-e^{-u})^{-1} \le1+1/u ( 1 − e − u ) − 1 ≤ 1 + 1/ u , so
E [ W ] ≤ N + 2 N R ℓ N + R N + 1 ≤ N + 3 N R ℓ N . (92) \mathbb{E}[W] \le N + \frac{2NR}{\ell_N} + R\sqrt{N+1} \le N + \frac{3NR}{\ell_N}. \tag*{(92)} E [ W ] ≤ N + ℓ N 2 N R + R N + 1 ≤ N + ℓ N 3 N R . (92)
To verify the last step for every N ≥ 1 N \ge1 N ≥ 1 , set x = N + 1 ≥ 1 x = \sqrt{N+1} \ge1 x = N + 1 ≥ 1 . The function x − x − 1 − 2 log x x-x^{-1}-2\log x x − x − 1 − 2 log x is zero at one and has derivative ( x − 1 ) 2 / x 2 ≥ 0 (x-1)^2/x^2 \ge0 ( x − 1 ) 2 / x 2 ≥ 0 . Thus log ( N + 1 ) N + 1 ≤ N \log(N+1)\sqrt{N+1} \le N log ( N + 1 ) N + 1 ≤ N . Independently of this expectation bound, the deterministic cap gives E [ W ] ≤ N R \mathbb{E}[W] \le NR E [ W ] ≤ N R .
For the lower bound, fix q = ( N + 1 ) − 1 / R q = (N+1)^{-1/R} q = ( N + 1 ) − 1/ R at every reached state and always advance on acceptance. Let v = 1 − q R = N / ( N + 1 ) v = 1-q^R = N/(N+1) v = 1 − q R = N / ( N + 1 ) . The probability of reaching step t t t is v t − 1 v^{t-1} v t − 1 , and its conditional expected attempts equal v / ( 1 − q ) v/(1-q) v / ( 1 − q ) . Therefore
E [ W ] = v 1 − q ∑ t = 1 N v t − 1 = N ( 1 − v N ) 1 − e − ℓ N / R . (93) \mathbb{E}[W] = \frac{v}{1-q}\sum_{t=1}^{N}v^{t-1} = \frac{N(1-v^N)}{1-e^{-\ell_N/R}}. \tag*{(93)} E [ W ] = 1 − q v t = 1 ∑ N v t − 1 = 1 − e − ℓ N / R N ( 1 − v N ) . (93)
The binomial inequality ( 1 + 1 / N ) N ≥ 2 (1+1/N)^N \ge2 ( 1 + 1/ N ) N ≥ 2 gives 1 − v N ≥ 1 / 2 1-v^N \ge1/2 1 − v N ≥ 1/2 . Also 1 − e − u ≤ min { 1 , u } 1-e^{-u} \le\min\{1,u\} 1 − e − u ≤ min { 1 , u } , so
E [ W ] ≥ N 2 max { 1 , R ℓ N } ≥ 1 4 ( N + N R ℓ N ) . (94) \mathbb{E}[W] \ge\frac{N}{2}\max\left\{1,\frac{R}{\ell_N}\right\} \ge\frac{1}{4}\left(N+\frac{NR}{\ell_N}\right). \tag*{(94)} E [ W ] ≥ 2 N max { 1 , ℓ N R } ≥ 4 1 ( N + ℓ N N R ) . (94)
Combining the upper and lower estimates yields the finite bounds
1 4 ( N + N R log ( N + 1 ) ) ≤ sup P ∈ P N , R E P [ W ] ≤ N + 3 N R log ( N + 1 ) . (95) \frac{1}{4}\left(N+\frac{NR}{\log(N+1)}\right) \le\sup_{P\in\mathcal{P}_{N,R}}\mathbb{E}_P[W] \le N+\frac{3NR}{\log(N+1)}. \tag*{(95)} 4 1 ( N + log ( N + 1 ) N R ) ≤ P ∈ P N , R sup E P [ W ] ≤ N + log ( N + 1 ) 3 N R . (95)
This proves the matching order for the entire class P N , R \mathcal{P}_{N,R} P N , R . It is a worst-case expectation over the class, not a lower bound on every individual process.
Combining Reliability and Work
For fixed ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) and α ≤ c δ / N \alpha\le c\delta/N α ≤ cδ / N with c < 1 c < 1 c < 1 , the cap in Eq. (78) is at most 1 + log ( N / ( ( 1 − c ) δ ) ) / log ( 1 / ρ ) 1 + \log(N/((1-c)\delta))/\log(1/\rho) 1 + log ( N / (( 1 − c ) δ )) / log ( 1/ ρ ) . At fixed δ \delta δ , this is O ( log N ) O(\log N) O ( log N ) for N ≥ 2 N \ge2 N ≥ 2 . Theorems 1 and 2 therefore imply Pr ( H N ) ≥ 1 − δ \Pr(H_N) \ge1-\delta Pr ( H N ) ≥ 1 − δ and E [ W ] = O ( N ) \mathbb{E}[W] = O(N) E [ W ] = O ( N ) . Since W ≥ N 1 H N W \ge N1_{H_N} W ≥ N 1 H N , its expectation is also at least ( 1 − δ ) N (1-\delta)N ( 1 − δ ) N . A uniform per-attempt cost bound g N g_N g N on all reached states gives expected total cost O ( N g N ) O(Ng_N) O ( N g N ) and a deterministic total-cost cap for the entire run of O ( N log N g N ) O(N\log N g_N) O ( N log N g N ) .
If δ N ≥ N − d \delta_N \ge N^{-d} δ N ≥ N − d for a fixed d > 0 d > 0 d > 0 , the cap remains O ( log N ) O(\log N) O ( log N ) and the same expectation upper bound follows. For smaller targets, substitute the actual R R R into Thm. 2. For example, δ N = e − κ N \delta_N = e^{-\kappa N} δ N = e − κ N can require R = Θ ( N ) R = \Theta(N) R = Θ ( N ) under the sufficient allocation, yielding an O ( N 2 / log N ) O(N^2/\log N) O ( N 2 / log N ) work bound from the unrestricted process class. This is an upper bound for reliable processes; the matching witness for the unrestricted class is not asserted to meet that exponentially small failure target.
Proof of the acceptance-sensitive bound. For the cap in Eq. (9) , every correct prefix exhausts with probability at most ( 1 − c ) δ / N (1-c)\delta/N ( 1 − c ) δ / N . Together with α ≤ c δ / N \alpha\le c\delta/N α ≤ cδ / N , the first-failure bound gives Pr ( H N ) ≥ 1 − δ \Pr(H_N) \ge1-\delta Pr ( H N ) ≥ 1 − δ . For fixed c , δ c,\delta c , δ , log ( N / ( ( 1 − c ) δ ) ) / log ( N + 1 ) \log(N/((1-c)\delta))/\log(N+1) log ( N / (( 1 − c ) δ )) / log ( N + 1 ) is bounded uniformly for N ≥ 1 N \ge1 N ≥ 1 . The ceiling and h N ≤ 1 h_N \le1 h N ≤ 1 therefore give R N / log ( N + 1 ) = O ( 1 / h N ) R_N/\log(N+1) = O(1/h_N) R N / log ( N + 1 ) = O ( 1/ h N ) . Applying Thm. 2 proves E [ W ] = O ( N / h N ) \mathbb{E}[W] = O(N/h_N) E [ W ] = O ( N / h N ) . For the lower construction, set q = 1 − h N q = 1-h_N q = 1 − h N and accept only correct states. Writing v = 1 − q R N v = 1-q^{R_N} v = 1 − q R N , each step’s expected attempts equal v / h N v/h_N v / h N and the success probability is v N ≥ 1 − δ v^N \ge1-\delta v N ≥ 1 − δ . Thus v ≥ 1 − δ v \ge1-\delta v ≥ 1 − δ and the probability of reaching any step is at least 1 − δ 1-\delta 1 − δ , giving E [ W ] ≥ N ( 1 − δ ) 2 / h N \mathbb{E}[W] \ge N(1-\delta)^2/h_N E [ W ] ≥ N ( 1 − δ ) 2 / h N . This also covers h N = 1 h_N = 1 h N = 1 , where exactly N N N attempts are executed. If every attempt has cost g N g_N g N , the cost upper bound has a matching construction in those units as well.
Proofs for the Binary-Checking Examples
Binary-checking model. At every correct prefix, a new candidate is correct with fixed probability p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) . Given its correctness, repeated checks are independent: a correct candidate passes with probability a a a , an incorrect one with probability b b b , where 0 < b < a < 1 0 < b < a < 1 0 < b < a < 1 . The parameters are fixed across correct prefixes and task lengths. Each candidate and its checks form one conditionally independent attempt at a fixed entry history. Different random seeds do not by themselves establish this noise model; shared candidate difficulty or systematic errors can violate it. For unanimity among k k k checks, the acceptance probability and accepted-state error are
h k = p a k + ( 1 − p ) b k , α k = ( 1 − p ) b k p a k + ( 1 − p ) b k . (96) h_k = pa^k + (1-p)b^k,\qquad\alpha_k = \frac{(1-p)b^k}{pa^k + (1-p)b^k}. \tag*{(96)} h k = p a k + ( 1 − p ) b k , α k = p a k + ( 1 − p ) b k ( 1 − p ) b k . (96)
All k k k checks are executed when full-check costs are counted below.
Unanimity: precision and acceptance probability. The probability that all k k k checks accept a correct candidate is a k a^k a k , and it is b k b^k b k for an incorrect candidate. Bayes’ rule gives Eq. (96) . For a target ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) , the precision condition is
α k ≤ ϵ ⟺ ( b a ) k ≤ ϵ p ( 1 − ϵ ) ( 1 − p ) . (97) \alpha_k \le\epsilon\quad\Longleftrightarrow\quad\left(\frac{b}{a}\right)^k \le\frac{\epsilon p}{(1-\epsilon)(1-p)}. \tag*{(97)} α k ≤ ϵ ⟺ ( a b ) k ≤ ( 1 − ϵ ) ( 1 − p ) ϵ p . (97)
For the smallest integer k ≥ 1 k \ge1 k ≥ 1 satisfying this with ϵ = c δ / N \epsilon= c\delta/N ϵ = cδ / N , where p , a , b , c , δ p,a,b,c,\delta p , a , b , c , δ are fixed and 0 < c < 1 0 < c < 1 0 < c < 1 , we have k = log N / log ( a / b ) + O ( 1 ) k = \log N/\log(a/b) + O(1) k = log N / log ( a / b ) + O ( 1 ) . Hence a k = Θ ( N − γ ) a^k = \Theta(N^{-\gamma}) a k = Θ ( N − γ ) for γ = − log a / log ( a / b ) > 0 \gamma= -\log a/\log(a/b) > 0 γ = − log a / log ( a / b ) > 0 . Moreover, h k = p a k / ( 1 − α k ) = Θ ( N − γ ) h_k = pa^k/(1-\alpha_k) = \Theta(N^{-\gamma}) h k = p a k / ( 1 − α k ) = Θ ( N − γ ) . To make ( 1 − h k ) R (1-h_k)^R ( 1 − h k ) R of order 1 / N 1/N 1/ N , one needs R = Θ ( log N / [ − log ( 1 − h k ) ] ) = Θ ( N γ log N ) R = \Theta(\log N/[-\log(1-h_k)]) = \Theta(N^\gamma\log N) R = Θ ( log N / [ − log ( 1 − h k )]) = Θ ( N γ log N ) . Together with the accepted-state error allocation, a sufficiently large constant in this cap guarantees Pr ( H N ) ≥ 1 − δ \Pr(H_N) \ge1-\delta Pr ( H N ) ≥ 1 − δ .
Unanimity: expected-cost lower bound. Use the homogeneous law at every correct prefix and make any incorrect acceptance irreversible. Write h = h k h = h_k h = h k , α = α k \alpha= \alpha_k α = α k , and u = ( 1 − ( 1 − h ) R ) ( 1 − α ) u = (1-(1-h)^R)(1-\alpha) u = ( 1 − ( 1 − h ) R ) ( 1 − α ) . Then Pr ( H N ) = u N \Pr(H_N)=u^N Pr ( H N ) = u N . If u N ≥ 1 − δ u^N\ge1-\delta u N ≥ 1 − δ , each correct-prefix reach probability Pr ( H t − 1 ) = u t − 1 \Pr(H_{t-1})=u^{t-1} Pr ( H t − 1 ) = u t − 1 is at least 1 − δ 1-\delta 1 − δ . Also 1 − ( 1 − h ) R ≥ u ≥ 1 − δ 1-(1-h)^R\ge u\ge1-\delta 1 − ( 1 − h ) R ≥ u ≥ 1 − δ . The expected attempts from each such prefix are [ 1 − ( 1 − h ) R ] / h ≥ ( 1 − δ ) / h [1-(1-h)^R]/h\ge(1-\delta)/h [ 1 − ( 1 − h ) R ] / h ≥ ( 1 − δ ) / h . Thus
E [ W ] ≥ ∑ t = 1 N Pr ( H t − 1 ) 1 − ( 1 − h ) R h ≥ N ( 1 − δ ) 2 h = Ω ( N 1 + γ ) . (98) \mathbb{E}[W]\ge\sum_{t=1}^{N}\Pr(H_{t-1})\frac{1-(1-h)^R}{h}\ge\frac{N(1-\delta)^2}{h}=\Omega(N^{1+\gamma}). \tag*{(98)} E [ W ] ≥ t = 1 ∑ N Pr ( H t − 1 ) h 1 − ( 1 − h ) R ≥ h N ( 1 − δ ) 2 = Ω ( N 1 + γ ) . (98)
Counting k k k unit-cost checks on every attempt gives Ω ( N 1 + γ log N ) \Omega(N^{1+\gamma}\log N) Ω ( N 1 + γ log N ) checking cost. If checking stops at the first failed check, the same candidate lower bound applies, but multiplying by k k k is no longer justified. The lower bound counts work on correct prefixes only, so arbitrary behavior after an error cannot invalidate it. For the matching upper bound, choose R N R_N R N from Eq. (9) with h N = h k h_N=h_k h N = h k . All k k k unit-cost checks are executed on each candidate and generation has uniformly bounded cost, so g N = Θ ( k ) g_N=\Theta(k) g N = Θ ( k ) on all reached states. Cor. 1 gives O ( N k / h k ) = O ( N 1 + γ log N ) O(Nk/h_k)=O(N^{1+\gamma}\log N) O ( N k / h k ) = O ( N 1 + γ log N ) , matching the lower bound. The upper bound permits arbitrary rejection at incorrect states, subject to the same conditional i.i.d. local retry and global stopping rules.
Majority: precision with nonvanishing acceptance probability. For odd k k k , let u k u_k u k be the probability of majority acceptance given a correct candidate and v k v_k v k the same probability given an incorrect candidate. Under a > 1 / 2 > b a>1/2>b a > 1/2 > b , Hoeffding’s inequality yields 1 − u k ≤ e − 2 k ( a − 1 / 2 ) 2 1-u_k\le e^{-2k(a-1/2)^2} 1 − u k ≤ e − 2 k ( a − 1/2 ) 2 and v k ≤ e − 2 k ( 1 / 2 − b ) 2 v_k\le e^{-2k(1/2-b)^2} v k ≤ e − 2 k ( 1/2 − b ) 2 . For all sufficiently large k k k , u k ≥ 1 / 2 u_k\ge1/2 u k ≥ 1/2 , so
h k = p u k + ( 1 − p ) v k ≥ p / 2 , α k = ( 1 − p ) v k h k ≤ 2 ( 1 − p ) p e − 2 k ( 1 / 2 − b ) 2 . (99) h_k=pu_k+(1-p)v_k\ge p/2,\qquad\alpha_k=\frac{(1-p)v_k}{h_k}\le\frac{2(1-p)}{p}e^{-2k(1/2-b)^2}. \tag*{(99)} h k = p u k + ( 1 − p ) v k ≥ p /2 , α k = h k ( 1 − p ) v k ≤ p 2 ( 1 − p ) e − 2 k ( 1/2 − b ) 2 . (99)
Choose an odd k k k of order log ( N / δ ) \log(N/\delta) log ( N / δ ) with a sufficiently large constant to get α k ≤ c δ / N \alpha_k\le c\delta/N α k ≤ cδ / N . The correct-prefix rejection bound ρ = 1 − p / 2 < 1 \rho=1-p/2<1 ρ = 1 − p /2 < 1 is independent of N N N . A cap R = O ( log ( N / δ ) ) R=O(\log(N/\delta)) R = O ( log ( N / δ )) now certifies reliability. For fixed δ \delta δ , conditional i.i.d. candidate attempts at every reached state and uniform per-check cost bounds give E [ W ] = O ( N ) \mathbb{E}[W]=O(N) E [ W ] = O ( N ) and E [ c o s t ] = O ( N log N ) \mathbb{E}[\mathrm{cost}]=O(N\log N) E [ cost ] = O ( N log N ) . The pathwise cap is N R k = O ( N log 2 N ) NRk=O(N\log^2N) N R k = O ( N log 2 N ) in the same units. The precision claim uses the noise law only at correct prefixes; the expected-work bound also requires the fixed retry law at incorrect states.
Dependence and boundary cases. If repeated checks share a latent blind spot, their false-acceptance probability need not decrease exponentially with k k k . Independent random seeds do not remove dependence caused by a shared candidate or systematic misunderstanding. The conditional Bernoulli law above fixes a a a and b b b within each correctness class and excludes such additional latent variation. The unanimity exponent assumes a < 1 a<1 a < 1 and b > 0 b>0 b > 0 ; perfect true acceptance or zero false acceptance needs a separate calculation. Majority’s fixed threshold at one half additionally requires a > 1 / 2 > b a>1/2>b a > 1/2 > b .
Relation to Classical Stopped Testing
The stopping pattern. Each attempt is a binary trial: acceptance completes a step; rejection leaves it unfinished. The run ends at the N N N th acceptance or the first run of R R R consecutive rejections. With constant rejection probability, this is a special case of total-success/consecutive-failure stopping in start-up demonstration testing. Gera [9 ] studies such criteria under a previous-sum-dependent model; Balakrishnan et al. [2 ] review i.i.d., Markov-dependent, exchangeable, and multistate formulations.
We connect worst-case expected work over P N , R \mathcal{P}_{N,R} P N , R to correctness at correct prefixes.
A prescribed homogeneous law. For rejection probability q ∈ ( 0 , 1 ) q\in(0,1) q ∈ ( 0 , 1 ) at every step, let a R ( q ) = ∑ j = 0 R − 1 q j = ( 1 − q R ) / ( 1 − q ) a_R(q)=\sum_{j=0}^{R-1}q^j=(1-q^R)/(1-q) a R ( q ) = ∑ j = 0 R − 1 q j = ( 1 − q R ) / ( 1 − q ) . A step takes a R ( q ) a_R(q) a R ( q ) attempts in expectation and advances with probability 1 − q R 1-q^R 1 − q R , so
E q [ W ] = a R ( q ) ∑ t = 0 N − 1 ( 1 − q R ) t = 1 − q R 1 − q 1 − ( 1 − q R ) N q R . (100) \mathbb{E}_q[W]=a_R(q)\sum_{t=0}^{N-1}(1-q^R)^t=\frac{1-q^R}{1-q}\frac{1-(1-q^R)^N}{q^R}. \tag*{(100)} E q [ W ] = a R ( q ) t = 0 ∑ N − 1 ( 1 − q R ) t = 1 − q 1 − q R q R 1 − ( 1 − q R ) N . (100)
At q = 0 q=0 q = 0 the work is N N N ; at q = 1 q=1 q = 1 it is R R R . This fixed-law calculation supplies the lower construction in Thm. 2; it does not bound every process in P N , R \mathcal{P}_{N,R} P N , R .
Exact recursion for the process class. Let V n V_n V n be the supremum of expected remaining attempts with n n n steps left and the common cap R R R . Then V 0 = 0 V_0 = 0 V 0 = 0 and
V n = max q ∈ [ 0 , 1 ] { a R ( q ) + ( 1 − q R ) V n − 1 } . (101) V_n = \max_{q \in[0,1]} \left\{ a_R(q) + (1-q^R)V_{n-1} \right\}. \tag*{(101)} V n = q ∈ [ 0 , 1 ] max { a R ( q ) + ( 1 − q R ) V n − 1 } . (101)
Condition on the complete entry history. Current-step expected work is a R ( q ) a_R(q) a R ( q ) ; acceptance leaves at most V n − 1 V_{n-1} V n − 1 expected attempts, while exhaustion ends the run. Continuity on [ 0 , 1 ] [0,1] [ 0 , 1 ] guarantees a maximum. Choose a maximizing q q q and, after acceptance, repeat for n − 1 n-1 n − 1 steps. Induction gives equality and an attaining process whose rejection probability depends only on the number of remaining steps. History dependence alone is not the distinction: the unrestricted supremum reduces to this scalar recursion. Thm. 2 gives its order uniformly in N N N , R R R without solving the successive maximizations. This characterizes the process class; a model need not realize its maximizing law.
What is needed for reliable reuse. A uniform acceptance lower bound h h h on all reached states immediately gives E [ W ] ≤ N / h \mathbb{E}[W] \le N/h E [ W ] ≤ N / h by summing geometric waiting times. In Cor. 1, the acceptance lower bound holds only at correct prefixes. An incorrect acceptance may lead to states with arbitrary rejection probabilities. Global stopping bounds their work without extending the correct-prefix acceptance assumption to those states. If rejection changes the retry law, rejecting the first R − 1 R-1 R − 1 candidates and accepting the last at every step gives W = N R W = NR W = N R . If exhaustion permits fallback and continuation, always rejecting likewise gives W = N R W = NR W = N R . These constructions show why the execution assumptions matter. The lower witness for Thm. 2 completes all steps with probability ( N / ( N + 1 ) ) N (N/(N+1))^N ( N / ( N + 1 ) ) N , approaching e − 1 e^{-1} e − 1 ; Cor. 1 supplies a separate matching construction within its reliable class.
Restart schedules and checking costs. Luby et al. [21 ] optimize schedules for repeated complete runs of Las Vegas algorithms. Our cap is fixed, and exhaustion ends the task; the result does not optimize restart schedules or decomposition. Selective classification studies the risk–coverage tradeoff [8 ] . Here its coverage corresponds to acceptance probability, distinct from answer coverage in our experiments. MAKER already accounts for voting cost and the probability that a generated response survives red-flagging [23 ] . Precision and acceptance probability are thus established concerns. Here they enter a first-acceptance process with a finite cap through g N / h N g_N/h_N g N / h N and the accepted-state error requirement in Cor. 1. Standard Bayes and concentration calculations [12 ] show why low error need not imply low cost.
Implementation Details
This section records the implementation details used for the LoRe-Compo experiments in § 4 .
The protocol first generates candidate answers to x 1 x_1 x 1 , selects intermediate answers, and uses them when generating answers to x 2 x_2 x 2 . It also retains fallback candidates that did not pass the check. This manuscript package documents the protocol but does not include the implementation.
The finite-budget arithmetic experiments in § 4.4 use a separate complete-answer retry setup, described after the LoRe-Compo details; they do not perform digit-level state reuse.
LoRe-Compo Implementation
Dataset format and connector prompt. The LoRe-Compo data file contains 500 unique MATH500 subproblems and 250 composite pairs. Readers can obtain the benchmark online from the LoRe Authors’ repository at https://github.com/ASTRAL-Group/LoRe , under LoRe-Bench/LoRe-Compo/compo_bench_math500.jsonl; this paper does not redistribute the records. Each subproblem record stores a MATH subject label, problem text, solution, and ground-truth answer. A pair links two subproblems, their answers, and this prompt:
Composite pair prompt.
Answer the following questions in order:
Q1. {question 1}
Q2. {question 2}
The Pass@K K K baseline uses this pair prompt directly for independent sampling over complete runs. The subject labels are used only as a proxy for reduced concept overlap across subproblems; they do not imply probabilistic independence of model outputs.
Independent sampling prompts. For each standalone or composite problem, independent sampling uses the template Question: {problem} followed by Answer:. For composite pairs, {problem} is the pair prompt above. We sample K ∈ { 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 } K \in\{1, 2, 4, 8, 16, 32, 64, 128\} K ∈ { 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 } complete runs with a maximum generation length of 10,240 tokens. The reported runs use vLLM with seed 42, repetition penalty 1.05, and family-specific temperatures 0.6/0.7/0.8 for DeepSeek/Qwen3/GPT-OSS. For K = 1 K=1 K = 1 , the executed parameters use top-p = 1.0 and top-k = − 1 -1 − 1 ; the do_sample field is not consumed by the vLLM call, so Pass@1 is not greedy decoding in this code path. For K > 1 K>1 K > 1 , the executed parameters use top-p = 0.7 and top-k = 50. The LoRe-Compo scripts pass these prompt strings directly to vLLM; model-specific chat templates are not applied in this implementation.
Two-stage protocol prompts. Stage 1 samples M M M answers to x 1 x_1 x 1 with its standalone prompt. The main two-stage comparison generates M = 8 M=8 M = 8 candidates and retains up to B = 4 B=4 B = 4 intermediate answers for continuation. These answers pass the selection rule when it succeeds; otherwise they are fallback candidates. The budget-allocation sweep also evaluates ( M , B ) ∈ { ( 4 , 2 ) , ( 8 , 2 ) , ( 8 , 4 ) , ( 16 , 8 ) } (M,B) \in\{(4,2), (8,2), (8,4), (16,8)\} ( M , B ) ∈ {( 4 , 2 ) , ( 8 , 2 ) , ( 8 , 4 ) , ( 16 , 8 )} . Stages 1 and 2 use the same family-specific temperatures, top-p = 0.7, top-k = 50, seed 42, repetition penalty 1.05, and 10,240-token cap. The main stage-2 prompt supplies the retained answer through the following answer_only template:
Two-stage protocol: stage-2 prompt (answer_only).
Question 1 has been solved. The answer was: {q1_answer}
==========================================
Now solve Question 2:
==========================================
{question 2}
Important: Question 2 is a different problem.
Think step by step and provide the answer for Question 2.
The prompt ablation additionally evaluates no_context, which passes only x 2 x_2 x 2 , and full_context, which passes the generated x 1 x_1 x 1 reasoning text and retained x 1 x_1 x 1 answer; retained fallback answers are not accepted. For full_context, the implementation truncates the retained x 1 x_1 x 1 context to the most recent portion when it exceeds the configured context budget. no_context uses the same single-subproblem prompt for x 2 x_2 x 2 , while full_context adds the retained x 1 x_1 x 1 reasoning and answer before Question 2.
Answer extraction and matching. Before extraction, generated text is split at </think> when a reasoning tag is present, and answer extraction is applied first to the post-thinking answer text. For math-style answers, extraction first uses the final \boxed{...} expression if present, then explicit answer patterns such as Answer:, The answer is, and Final answer:, and finally falls back to the last numeric expression. For composite answers, extraction first tries to split the generated text into Q1 and Q2 sections and extract one answer from each section. If this split fails, it falls back to the first two numeric expressions when available. Correctness uses numeric comparison with tolerance 10 − 6 10^{-6} 1 0 − 6 when both prediction and target are numeric; otherwise strings are stripped, lowercased, spaces are removed, and exact string equality is used. No computer algebra system (CAS) checks algebraic equivalence.
Oracle and self-consistency selection. Oracle selection compares each stage-1 candidate’s extracted x 1 x_1 x 1 answer with the reference answer. If reference-matching candidates exist, the first B B B matches are retained and each receives a continuation.
If none matches, the fallback keeps the first B B B candidates so that continuation tokens and second-subproblem success are still measured. All such paths use fallback routing, which the formal loop excludes by terminating without returning a state whenever selection fails.
Self-consistency selection counts the extracted x 1 x_1 x 1 answers among the M M M candidates. If the most common answer has vote share at least 0.5, it keeps up to B B B candidates with that answer.
If no answer reaches this threshold, the empirical protocol keeps the first B B B candidates as a fallback for measurement; the formal loop would instead stop without returning a state. Ties are not broken by a separate randomized procedure: the implementation uses the first most common answer returned by the counter over generated candidates.
Comparing accepted SC answers against reference answers measures the error rate among accepted states in the evaluated sample. It does not estimate the uniform theoretical bound α \alpha α across all steps, correct input states, and budgets. An error estimate that includes fallbacks instead describes all retained candidates, including those rejected by the selection rule.
Retained-path correctness fields. The implementation defines path-level fields for first-answer correctness, second-answer correctness, and their conjunction.
The implementation field final_correct denotes second-subproblem success: whether any retained continuation solves x 2 x_2 x 2 , regardless of the retained x 1 x_1 x 1 answer’s correctness. Joint success requires both answers to be correct on a shared continuation path.
Joint success must be computed from the path-level field requiring both answers to be correct. Estimating the error rate among accepted states additionally requires excluding fallback paths.
The distinction matters when fallback candidates are retained or the check accepts an incorrect answer. With Oracle selection and at least one reference match, the reused intermediate answers are correct according to the answer matcher; this does not verify the full reasoning traces.
Case Example: One LoRe-Compo Pair. Consider the pair with MATH500 indices (477, 21). The first subproblem asks for the number of possible tens digits B B B such that the two-digit number “B 6 B6 B 6 ” is a square, with answer 2. The second asks for the greatest integer less than ( 7 + 5 ) 6 (\sqrt{7}+\sqrt{5})^6 ( 7 + 5 ) 6 , with answer 13535. The independent-sampling baseline presents both subproblems in one prompt and succeeds only when a single sampled run returns the correct pair [2, 13535].
The two-stage protocol samples M M M solutions for the first subproblem and selects extracted answers using Oracle matching or SC voting. If an answer passes the selection rule, the model receives that accepted intermediate answer when solving the second subproblem; otherwise it continues from fallback candidates to measure second-subproblem coverage.
The example contrasts complete-solution sampling with separate continuation prompts. The second subproblem does not mathematically depend on the first answer.
Case Example: Answer Matching and Selection. The pair with MATH500 indices (277, 222) contains a first subproblem asking for 53 \sqrt{53} 53 in simplest radical form, with target answer \sqrt{53}. For nonnumeric answers, the checker strips whitespace, lowercases strings, removes spaces, and then applies exact string matching. Thus \sqrt{53} is accepted, while a semantically equivalent expression may not be accepted unless extracted into the same normalized string. For generated composite answers, if Q1/Q2 section extraction fails, the extractor falls back to the first two numeric expressions in the post-</think> answer text.
For Oracle selection, if no stage-1 candidate matches the target, the empirical fallback keeps the first B B B candidates so that continuation budget is still measured; these paths are neither accepted states nor part of the formal product theorem. Consider these M = 8 M=8 M = 8 candidate answers:
200 , 200 , 200 , 200 , 210 , 300 , 2000 , PARSE_ERROR . 200,\quad200,\quad200,\quad200,\quad210,\quad300,\quad2000,\quad\texttt{PARSE\_ERROR}. 200 , 200 , 200 , 200 , 210 , 300 , 2000 , PARSE_ERROR .
The answer 200 has vote share 4 / 8 = 0.5 4/8=0.5 4/8 = 0.5 , meeting the self-consistency threshold, so up to B = 4 B=4 B = 4 candidates with that answer are kept. If the top vote share were 3 / 8 3/8 3/8 , the protocol would retain the first B B B candidates as a fallback. Ties use the first most common answer encountered by the counter; no randomized tie-breaking rule is applied.
Metric Definitions and Limits of the Reported Aggregates
Joint versus second-subproblem coverage. Let i = 1 , … , D i=1,\ldots,D i = 1 , … , D index the D = 250 D=250 D = 250 composite pairs, and let R i \mathcal{R}_i R i be the retained paths that receive continuations. Write G i b ( 1 ) G_{ib}^{(1)} G ib ( 1 ) and G i b ( 2 ) G_{ib}^{(2)} G ib ( 2 ) for the correctness indicators of the first and second answers on path b ∈ R i b\in\mathcal{R}_i b ∈ R i . The distinction between second-subproblem coverage and joint coverage is expressed by the statistics
A ^ 2 r e t = 1 D ∑ i = 1 D 1 { ∃ b ∈ R i : G i b ( 2 ) = 1 } , (102) \widehat{A}_{2}^{\mathrm{ret}}=\frac{1}{D}\sum_{i=1}^{D}\mathbf{1}\{\exists b\in\mathcal{R}_i:G_{ib}^{(2)}=1\}, \tag*{(102)} A 2 ret = D 1 i = 1 ∑ D 1 { ∃ b ∈ R i : G ib ( 2 ) = 1 } , (102)
A ^ j o i n t r e t = 1 D ∑ i = 1 D 1 { ∃ b ∈ R i : G i b ( 1 ) = G i b ( 2 ) = 1 } . (103) \widehat{A}_{\mathrm{joint}}^{\mathrm{ret}}=\frac{1}{D}\sum_{i=1}^{D}\mathbf{1}\{\exists b\in\mathcal{R}_i:G_{ib}^{(1)}=G_{ib}^{(2)}=1\}. \tag*{(103)} A joint ret = D 1 i = 1 ∑ D 1 { ∃ b ∈ R i : G ib ( 1 ) = G ib ( 2 ) = 1 } . (103)
Only the first statistic is reported for the two-stage experiments. The reported aggregates cannot replace missing path-level records. The second cannot be reconstructed by multiplying marginal accuracies or from A ^ 2 r e t \widehat{A}_{2}^{\mathrm{ret}} A 2 ret alone. Restricting R i \mathcal{R}_i R i to paths that passed selection would define accepted-path coverage; its denominator must still contain all D D D pairs, with an empty path set contributing zero. These definitions supply no new measurements and do not make the multiple-path protocol equivalent to the formal loop.
Acceptance and fallback. Error among accepted intermediate answers requires comparing those answers to the reference, excluding every fallback that did not pass selection. A calculation must specify whether it weights individual retained answers or one selected state per pair; multiple retained copies of a modal answer need not define the same distribution as the theorem’s returned state. An empirical average under either choice would not establish a uniform bound over all correct prefixes. The reported continuation aggregates do not determine this error rate, the frequency of fallback, or the joint contribution of accepted and fallback paths. Oracle reference matching checks an extracted answer; in the full-context ablation, the retained reasoning text is not separately checked.
Partial successes in a common candidate pool. For K K K complete composite runs, let G i 1 r G_{i1r} G i 1 r and G i 2 r G_{i2r} G i 2 r denote subproblem-answer correctness in run r r r . Define
J i ( K ) = 1 { ∃ r ≤ K : G i 1 r = G i 2 r = 1 } , (104) J_i(K) = 1\{\exists r \le K : G_{i1r} = G_{i2r} = 1\}, \tag*{(104)} J i ( K ) = 1 { ∃ r ≤ K : G i 1 r = G i 2 r = 1 } , (104)
U i ( K ) = 1 { ∃ r ≤ K : G i 1 r = 1 } 1 { ∃ r ≤ K : G i 2 r = 1 } . (105) U_i(K) = 1\{\exists r \le K : G_{i1r} = 1\}1\{\exists r \le K : G_{i2r} = 1\}. \tag*{(105)} U i ( K ) = 1 { ∃ r ≤ K : G i 1 r = 1 } 1 { ∃ r ≤ K : G i 2 r = 1 } . (105)
Then J i ( K ) ≤ U i ( K ) J_i(K) \le U_i(K) J i ( K ) ≤ U i ( K ) for every realized pool, without an independence assumption. The average D − 1 ∑ i [ U i ( K ) − J i ( K ) ] D^{-1}\sum_i[U_i(K)-J_i(K)] D − 1 ∑ i [ U i ( K ) − J i ( K )] would measure pools containing separately correct subproblem answers but no jointly correct run. It is an oracle coverage diagnostic, not a deployable answer-selection rule. The reported Pass@K K K values average J i ( K ) J_i(K) J i ( K ) ; they cannot identify the difference U i ( K ) − J i ( K ) U_i(K)-J_i(K) U i ( K ) − J i ( K ) .
Comparability and uncertainty. The decoding differences and unspecified cross-budget nesting in Appendix § 15 .§ 1 prevent interpreting all composite rows as one controlled budget curve. Single-subproblem and paired-answer extraction also follow different fallback rules: the paired extractor can return the first two numeric expressions when section parsing fails, while semantic equivalence is not checked by a CAS. The available aggregate results do not quantify extraction errors or their differential effect between protocols. Scores depend on the specified prompts, answer matching, and extraction.
There are 250 pairs per model, giving 0.4-percentage-point resolution for each model’s pair-level accuracy. SC–Oracle differences of at most 1.6 points correspond to a net difference of at most four successful pairs; the number of pairs on which the selectors disagree cannot be inferred from these marginal scores. Paired uncertainty cannot be recovered from the rounded marginal scores alone; the shared test pairs also make models’ aggregate outcomes dependent. We report the observed differences without asserting statistical equivalence, significance, or robustness across decoding seeds.
Controlled Arithmetic Implementation
The Base 7 and Base 10 experiments use the same complete-answer sampling structure. Digit count indexes problem size; no digit-position state is checked or reused. For each base, task, and digit count, the scripts pre-generate 50 problems using seed 42 ⋅ 10000 + 100 ⋅ j + n 42 \cdot10000 + 100 \cdot j + n 42 ⋅ 10000 + 100 ⋅ j + n , where j = 0 j=0 j = 0 for addition, j = 1 j=1 j = 1 for multiplication, and n n n is the digit count. The evaluated digit counts are n ∈ { 1 , … , 10 } n \in\{1,\ldots,10\} n ∈ { 1 , … , 10 } and the tasks are addition and multiplication. Each problem receives R max = 32 R_{\max}=32 R m a x = 32 independent attempts in one vLLM call, with checkpoints at R ∈ { 2 , 4 , 8 , 16 , 32 } R \in\{2,4,8,16,32\} R ∈ { 2 , 4 , 8 , 16 , 32 } .
Thus each model is evaluated on 2 bases × \times × 2 tasks × \times × 10 digit counts × \times × 50 problems, with 32 attempts per problem; each combination of model, base, task, and digit count contains 1,600 completions.
Arithmetic prompts. The Base 7 template specifies its carry rule and answer format:
Base 7 addition prompt.
Task: Perform addition in Base-7 (septenary system).
Calculate {a_b7} + {b_b7} in Base-7.
Rules: In Base-7, digits are 0-6. When a digit-sum reaches 7,
carry 1 to the next position.
Think step by step and give your final answer
in Base-7 inside \boxed{}.
Base 7 multiplication uses the analogous prompt with multiplication-specific carry instructions. Base 10 uses the corresponding decimal arithmetic prompts, asking for the sum or product of two decimal operands and a final boxed numerical answer.
Arithmetic sampling and extraction. For DeepSeek-family models, the arithmetic scripts use temperature 0.6 and top-p p p = 0.95. For Qwen3 models, they use temperature 0.6, top-p p p = 0.95, top-k k k = 20, and min-p p p = 0.0. For GPT-OSS models, they use temperature 1.0 and top-p p p = 1.0. All arithmetic runs use seed 42, maximum generation length 10,240 tokens, and n n n =32 completions per prompt. Answer extraction first uses the final \boxed{...} expression if present. Base 7 falls back to the last digit string with commas and spaces removed; Base 10 removes commas and takes the last signed integer.
Unsolved fraction. For each problem, the retry matrix stores a binary correctness value for each of the 32 attempts. The checkpoint statistic E ^ ( R ) \hat{E}(R) E ^ ( R ) averages failure indicators over the first R R R attempts:
E ^ ( R ) = 1 ∣ D ∣ ∑ x ∈ D 1 { attempts 1 , … , R all fail on x } . \hat{E}(R) = \frac{1}{|\mathcal{D}|}\sum_{x\in\mathcal{D}} \mathbf{1}\{\text{attempts }1,\ldots,R\text{ all fail on }x\}. E ^ ( R ) = ∣ D ∣ 1 x ∈ D ∑ 1 { attempts 1 , … , R all fail on x } .
The unsolved fraction after 32 attempts is E ^ ( 32 ) \hat{E}(32) E ^ ( 32 ) , and empirical Pass@R R R is 1 − E ^ ( R ) 1-\hat{E}(R) 1 − E ^ ( R ) . Each value of R R R uses the first R R R of the same 32 attempts. In this arithmetic probe, Pass@1 is the first sampled attempt among the 32 returned completions, not a greedy decoding run.
Case Example: Base 7 Addition. For a one-digit Base 7 addition problem, the script samples decimal operands in [ 1 , 6 ] [1,6] [ 1 , 6 ] and converts them to Base 7. If the sampled operands are decimal 5 and 6, the prompt asks for 5 + 6 in Base 7. The target is decimal 11, written as 14 in Base 7. A final boxed answer of 14 is correct; a decimal answer 11 is incorrect because the output must be in Base 7.
Case Example: Counting Unsolved Problems. Suppose a condition has 50 problems and, for a given problem, the 32-attempt correctness row is
0 , 0 , 0 , 1 , 0 , … . 0,0,0,1,0,\ldots. 0 , 0 , 0 , 1 , 0 , … . This problem contributes to E ^ ( 1 ) \hat{E}(1) E ^ ( 1 ) , E ^ ( 2 ) \hat{E}(2) E ^ ( 2 ) , and E ^ ( 3 ) \hat{E}(3) E ^ ( 3 ) because the first R R R attempts all fail for those checkpoints. It does not contribute to E ^ ( 4 ) \hat{E}(4) E ^ ( 4 ) or later checkpoints because an attempt has succeeded by R = 4 R=4 R = 4 . Problems left unsolved within this budget are not necessarily impossible to solve.
Arithmetic Results by Base and Digit Count
Figure 5 replots the first-attempt accuracies and mean token counts shown in Figure 8 and Figure 15 . Figure 6 gives the corresponding unsolved fractions for each model and operation. Digit count indexes input size, not measured reasoning steps; the numerical ranges differ across bases.
Figure 5. Accuracy and Generated Tokens by Digit Count. Top: first-attempt accuracy from Figure 8 . Bottom: mean generated tokens per attempt from Figure 15 . Both rows plot the reported heatmap cells under the protocol in Appendix C.3; colors identify models.
Figure 6. Unsolved Fraction in Base 7 and Base 10. Each curve reports E ^ ( 32 ) \hat{E}(32) E ^ ( 32 ) by digit count for one model and operation, comparing the two bases under the stated sampling protocol.
Figure 15. Average Generated Tokens per Attempt. Cells show mean output length for each combination of model, base, operation, and digit count under a 10,240-token generation cap. The displayed range is 115–10,240 tokens; averages are 7,391 for Base 7 multiplication and 2,702 for Base 10 addition.
Detailed Results of Repeated Arithmetic Attempts
The arithmetic protocol in Appendix § 15 .§ 3 yields 320 combinations of model, base, operation, and digit count, each with 50 problems and 32 complete-answer attempts per problem. The following figures show the per-condition curves, single-attempt scores, and token measurements.
Unsolved-Fraction Curves
Figure 7 shows E ^ ( R ) \hat{E}(R) E ^ ( R ) for all 320 conditions. At R = 32 R = 32 R = 32 , 235 conditions have no unsolved problems and 85 have at least one. All 80 Base 10 addition conditions reach zero unsolved problems. Base 7 multiplication has the largest mean unsolved fraction, 0.40, with 33 of 80 conditions above 0.5. The curves vary across models and digit counts, including GPT-OSS-120B’s nonmonotonic low-digit Base 7 multiplication results. Appendix E.4 defines the two-component fits shown as dashed curves.
Figure 7. Empirical Unsolved-Fraction Curves. Rows are models; columns are Base 10 addition, Base 10 multiplication, Base 7 addition, and Base 7 multiplication. Colors encode n = 1 , … , 10 n = 1, \ldots, 10 n = 1 , … , 10 . Solid curves show E ^ ( R ) \hat{E}(R) E ^ ( R ) and dashed gray curves show fitted two-component models. The panels retain both zero and nonzero unsolved fractions within 32 attempts, including GPT-OSS-120B’s nonmonotonic Base 7 multiplication results.
First-Attempt Accuracy
Figure 8 complements the unsolved-fraction heatmap by showing Pass@1. Low Pass@1 can coexist with high Pass@32: R1-1.5B on Base 7 addition at n = 3 n = 3 n = 3 has Pass@1 = 0.08 and Pass@32 = 0.98, with E ^ ( 32 ) = 0.02 \hat{E}(32) = 0.02 E ^ ( 32 ) = 0.02 . Across the 320 conditions, 12 have a gain from additional attempts, Pass@32 minus Pass@1, greater than 0.80. For R1-1.5B on Base 7 multiplication at n ≥ 7 n \ge7 n ≥ 7 , Pass@1 remains zero and E ^ ( 32 ) = 1 \hat{E}(32) = 1 E ^ ( 32 ) = 1 . These cases distinguish first-attempt accuracy from finite-pool answer coverage, without identifying how an intermediate state would affect later steps.
Unsolved Fraction at Different Attempt Budgets
Figure 9 reports E ^ ( R ) \hat{E}(R) E ^ ( R ) at R ∈ { 2 , 4 , 8 , 16 , 32 } R \in\{2, 4, 8, 16, 32\} R ∈ { 2 , 4 , 8 , 16 , 32 } . Across 320 conditions, the mean absolute gap between E ^ ( 16 ) \hat{E}(16) E ^ ( 16 ) and E ^ ( 32 ) \hat{E}(32) E ^ ( 32 ) is 0.031, with a maximum of 0.32. These differences describe changes within the observed budget; they do not establish convergence beyond it. Because every checkpoint uses a prefix of the same pool, solved problems remain covered at later checkpoints.
Figure 9. Unsolved Fraction at Different Attempt Budgets. Rows correspond to R ∈ { 2 , 4 , 8 , 16 , 32 } R \in\{2, 4, 8, 16, 32\} R ∈ { 2 , 4 , 8 , 16 , 32 } and columns to the four base–operation combinations. Curves show E ^ ( R ) \hat{E}(R) E ^ ( R ) against digit count; colors identify models. The reported mean absolute gap between R = 16 R = 16 R = 16 and R = 32 R = 32 R = 32 is 0.031 across 320 conditions, with a maximum of 0.32; every checkpoint uses the same nested attempt pool.
Two-Component Mixture Fits
We fit the empirical curves by nonlinear least squares using
E ^ ( R ) ≈ π s ε g o o d R + ( 1 − π s ) ε b a d R , (106) \hat{E}(R) \approx\pi_s \varepsilon_{\mathrm{good}}^{R} + (1-\pi_s)\varepsilon_{\mathrm{bad}}^{R}, \tag*{(106)} E ^ ( R ) ≈ π s ε good R + ( 1 − π s ) ε bad R , (106)
Here π s \pi_s π s is the weight of the faster-decaying component and ε g o o d \varepsilon_{\mathrm{good}} ε good its per-attempt failure rate. The remaining weight 1 − π s 1-\pi_s 1 − π s belongs to a slowly decaying component with ε b a d \varepsilon_{\mathrm{bad}} ε bad near one. Figures 10 and 11 display all 128 conditions with n ∈ { 3 , 5 , 7 , 9 } n \in\{3, 5, 7, 9\} n ∈ { 3 , 5 , 7 , 9 } . The weight 1 − π s 1-\pi_s 1 − π s of the slowly decaying component tracks E ^ ( 32 ) \hat{E}(32) E ^ ( 32 ) in the reported comparisons with E ^ ( 32 ) > 0.1 \hat{E}(32) > 0.1 E ^ ( 32 ) > 0.1 , but can exceed it when few problems remain unsolved. The fit summary also reports ε g o o d < 0.1 \varepsilon_{\mathrm{good}} < 0.1 ε good < 0.1 for R1-14B in conditions where R1-1.5B has ε g o o d > 0.5 \varepsilon_{\mathrm{good}} > 0.5 ε good > 0.5 . The weight 1 − π s 1-\pi_s 1 − π s describes the fitted component over the observed window; if both fitted failure rates are below one, the fitted curve tends to zero.
Gain from Additional Attempts by Digit Count
Figure 12 plots Pass@R R R minus Pass@1 against digit count at R ∈ { 4 , 8 , 16 , 32 } R \in\{4, 8, 16, 32\} R ∈ { 4 , 8 , 16 , 32 } , separately for addition and multiplication. The gain is at most 1 − P a s s @ 1 1-\mathrm{Pass@1} 1 − Pass@1 ; its distance from this maximum equals E ^ ( R ) \hat{E}(R) E ^ ( R ) . For R1-7B on Base 7 multiplication at n = 4 n=4 n = 4 , Pass@1 = 0 and Pass@32 = 0.26, leaving E ^ ( 32 ) = 0.74 \hat{E}(32) = 0.74 E ^ ( 32 ) = 0.74 . The vertical axis spans the full gain range from zero to one.
Figure 12. Gain from Additional Attempts by Digit Count. Top: addition; bottom: multiplication. Panels identify models, the horizontal axis is digit count, colors encode R ∈ { 4 , 8 , 16 , 32 } R \in\{4, 8, 16, 32\} R ∈ { 4 , 8 , 16 , 32 } , and line styles distinguish bases. The plotted quantity is Pass@R R R minus Pass@1; its gap to 1 − P a s s @ 1 1 - \mathrm{Pass}@1 1 − Pass @1 equals E ^ ( R ) \hat{E}(R) E ^ ( R ) .
Eight-Digit Multiplication Trajectories
Figure 13 selects eight-digit multiplication in each base and plots the full E ^ ( R ) \hat{E}(R) E ^ ( R ) trajectory for every model. Several trajectories flatten around 8–16 attempts, while others continue to decrease through the observed window. Figure 9 reports the corresponding checkpoints across all conditions.
Figure 13. Unsolved Fraction for Eight-Digit Multiplication. Each model panel shows E ^ ( R ) \hat{E}(R) E ^ ( R ) for Base 7 (solid green) and Base 10 (dashed blue) at n = 8 n = 8 n = 8 . Markers identify R ∈ { 2 , 4 , 8 , 16 , 32 } R \in\{2, 4, 8, 16, 32\} R ∈ { 2 , 4 , 8 , 16 , 32 } . The curves retain the full observed range from 1 to 32 attempts for both numeral bases.
Pass@1 and Pass@32 by Digit Count
Figure 14 pairs Pass@1 and Pass@32 at each digit count for all 320 conditions. Panels identify models, colors distinguish bases, and the two marker types identify the attempt budgets. Within-pair gaps measure retry gain; gaps above Pass@32 measure the unsolved fraction.
Figure 14. Pass@1 and Pass@32 by Digit Count. Top: addition; bottom: multiplication. Panels identify models, colors distinguish Base 7 and Base 10, and markers distinguish Pass@1 from Pass@32. The vertical separation at each digit count is the gain from additional attempts.
Generated Token Counts
Figure 15 reports average generated tokens per attempt. The displayed range is 115–10,240 tokens, with the upper value set by the generation cap. Base 7 multiplication averages 7,391 tokens, compared with 2,702 for Base 10 addition, a ratio of about 2.7×. This contrast varies both the base and the operation. GPT-OSS-120B uses 115 tokens for one-digit Base 10 addition and 116–153 for one- and two-digit Base 10 multiplication; these short decimal outputs do not explain the different coverage pattern observed for Base 7 arithmetic under the same attempt budget.
Figure 11. Two-Component Fits for Base 10. The layout, checkpoints, and curve styles follow Figure 10 , with Base 10 addition and multiplication shown in the two panels.
Figure 10. Two-Component Fits for Base 7. Solid curves show empirical E ^ ( R ) \hat{E}(R) E ^ ( R ) ; dashed curves show nonlinear least-squares fits of π s ε g o o d R + ( 1 − π s ) ε b a d R \pi_s\varepsilon_{\mathrm{good}}^R + (1-\pi_s)\varepsilon_{\mathrm{bad}}^R π s ε good R + ( 1 − π s ) ε bad R at n ∈ { 3 , 5 , 7 , 9 } n \in\{3,5,7,9\} n ∈ { 3 , 5 , 7 , 9 } . The slowly decaying component’s weight 1 − π s 1-\pi_s 1 − π s is compared with the unsolved fraction in Appendix § 17 .§ 4 .
Agent Score Prediction: Derivation and Details
The forecasting comparison in § 4.5 uses a curve motivated by a special case of the repeated-attempt model: every instance is solvable and checks accept exactly the correct candidates.
We evaluate agent score prediction using each task–model pair’s scores at 2 and 4 hours, together with priors fitted to other tasks in the same category, excluding the target task. At 12 hours, the retry curve and the sigmoid curve in log time obtain median relative errors of 10.7% and 10.9%, respectively, over 248 pairs with positive observed scores.
From Repeated Attempts to a Score Curve
We extend the model for generating correct candidates in Appendix § 11 .§ 2 to continuous time. (14) approximates the probability of no correct candidate after R R R attempts:
q t c l e a n ( R ) ≈ q t f l o o r + ( 1 − q t f l o o r ) ⋅ ε l o c , t R . q_t^{\mathrm{clean}}(R) \approx q_t^{\mathrm{floor}} + (1-q_t^{\mathrm{floor}})\cdot\varepsilon_{\mathrm{loc},t}^{R}. q t clean ( R ) ≈ q t floor + ( 1 − q t floor ) ⋅ ε loc , t R .
In the special case q t f l o o r = 0 q_t^{\mathrm{floor}}=0 q t floor = 0 and ε l o c , t = ε \varepsilon_{\mathrm{loc},t}=\varepsilon ε loc , t = ε , every instance has the same per-attempt failure probability. A perfect check gives α = 0 \alpha=0 α = 0 and ρ = ε \rho=\varepsilon ρ = ε , with success probability
1 − q t c l e a n ( R ) = 1 − ε R . (107) 1-q_t^{\mathrm{clean}}(R)=1-\varepsilon^R. \tag*{(107)} 1 − q t clean ( R ) = 1 − ε R . (107)
The general loop also includes incorrect acceptance in its failure bound (Eq. (37)).
Mapping to agent tasks. For the prediction model, t t t is elapsed time in hours. We replace R R R with t / T t/T t / T , where the positive time scale T T T is fitted together with the remaining parameters. The fitted score S ( t ) ∈ [ 0 , S max ] S(t)\in[0,S_{\max}] S ( t ) ∈ [ 0 , S m a x ] is a continuous-time analogue of success probability, scaled by the task-specific ceiling S max S_{\max} S m a x to represent cumulative task credit.
Scaling the resulting success curve by the task-specific ceiling S max S_{\max} S m a x gives:
S ( t ) = S max ⋅ ( 1 − ε t / T ) . (108) S(t)=S_{\max}\cdot(1-\varepsilon^{t/T}). \tag*{(108)} S ( t ) = S m a x ⋅ ( 1 − ε t / T ) . (108)
(108) , the retry curve , substitutes R = t / T R=t/T R = t / T and scales the result by the task ceiling.
Comparison curve. We also evaluate a sigmoid curve in log time:
S ( t ) = S max 1 + ( t m i d / t ) β . (109) S(t)=\frac{S_{\max}}{1+(t_{\mathrm{mid}}/t)^\beta}. \tag*{(109)} S ( t ) = 1 + ( t mid / t ) β S m a x . (109)
Here t m i d > 0 t_{\mathrm{mid}}>0 t mid > 0 is the time when S = S max / 2 S=S_{\max}/2 S = S m a x /2 , and β > 0 \beta>0 β > 0 controls curve steepness; this β \beta β is unrelated to the local failure probability β t ( R ; s ) \beta_t(R;s) β t ( R ; s ) . The expression is a sigmoid function of log t t t , labeled “Sigmoid (log time)” throughout the figures and tables for this forecasting comparison.
Both models are monotone and bounded and approach their fitted ceilings as t t t increases.
Experimental Setup
Data. We use publicly reported scores from the EdgeBench long-horizon agent benchmark ([47 ] ), which evaluates 5 frontier models across 51 tasks spanning 6 categories (Formal Mathematics, Games, Systems Engineering, Optimization, Scientific Computing, and Knowledge) at time budgets t ∈ { 2 , 4 , 6 , 8 , 10 , 12 } t\in\{2,4,6,8,10,12\} t ∈ { 2 , 4 , 6 , 8 , 10 , 12 } hours. All six scores are available for 252 task–model pairs.
Prediction protocol. For each target (task, model) pair, we use S ( 2 h ) S(2\mathrm{h}) S ( 2 h ) and S ( 4 h ) S(4\mathrm{h}) S ( 4 h ) as its observed scores, fit model parameters using the priors below, and predict S ( t ) S(t) S ( t ) for t ∈ { 6 , 8 , 10 , 12 } h t\in\{6,8,10,12\}\mathrm{h} t ∈ { 6 , 8 , 10 , 12 } h . Both curves use category-level priors, meaning parameter estimates obtained from other tasks before fitting the target pair. The retry curve uses ( ε c a t , c c a t ) (\varepsilon_{\mathrm{cat}},c_{\mathrm{cat}}) ( ε cat , c cat ) , the median fitted failure parameter and score-ceiling ratio; the sigmoid curve in log time uses β c a t \beta_{\mathrm{cat}} β cat , the median slope. For each target task, priors are medians of fits to all six observations from other tasks in the same category. Every model trajectory belonging to the target task is excluded when computing these priors.
Parameter estimation. For the retry curve (Eq. (108) ), we jointly optimize ( ε , T , S max ) (\varepsilon, T, S_{\max}) ( ε , T , S m a x ) using maximum a posteriori (MAP) estimation: squared error on the two observed points plus a penalty for deviation from ( ε c a t , c c a t ) (\varepsilon_{\mathrm{cat}}, c_{\mathrm{cat}}) ( ε cat , c cat ) . Because ε t / T \varepsilon^{t/T} ε t / T depends on ε \varepsilon ε and T T T only through − log ( ε ) / T -\log(\varepsilon)/T − log ( ε ) / T , we do not interpret the two parameters separately. For the sigmoid curve in log time (Eq. (109) ), we optimize ( S max , t m i d , β ) (S_{\max}, t_{\mathrm{mid}}, \beta) ( S m a x , t mid , β ) with regularization toward β c a t \beta_{\mathrm{cat}} β cat . For both curves, fitting uses regularization coefficient 2.0 and Nelder–Mead optimization with at most 2,000 iterations and 10 − 4 10^{-4} 1 0 − 4 parameter and objective tolerances. The retry curve uses 0.01 < ε < 0.999 0.01 < \varepsilon< 0.999 0.01 < ε < 0.999 , 0.05 < T ≤ 10 0.05 < T \le10 0.05 < T ≤ 10 , and 0 < S max ≤ 105 0 < S_{\max} \le105 0 < S m a x ≤ 105 ; the sigmoid curve in log time uses 0.01 < t m i d ≤ 500 0.01 < t_{\mathrm{mid}} \le500 0.01 < t mid ≤ 500 , 0.05 < β ≤ 6 0.05 < \beta\le6 0.05 < β ≤ 6 , and 0 < S max ≤ 105 0 < S_{\max} \le105 0 < S m a x ≤ 105 . MAP optimization produces numerical predictions for all 252 pairs, including the 53 cases where an analytic closed-form solution for the sigmoid curve in log time does not exist (i.e., when the observed growth ratio S ( 4 h ) / S ( 2 h ) S(4\mathrm{h})/S(2\mathrm{h}) S ( 4 h ) / S ( 2 h ) is inconsistent with the prior slope β c a t \beta_{\mathrm{cat}} β cat ).
Fitting inputs and regularization. For fitting only, let u = max { S ( 2 ) , 0 } u = \max\{S(2), 0\} u = max { S ( 2 ) , 0 } and let v = S ( 4 ) v = S(4) v = S ( 4 ) when S ( 4 ) > u S(4) > u S ( 4 ) > u , or v = 1.001 u + 0.01 v = 1.001u + 0.01 v = 1.001 u + 0.01 otherwise. Both procedures use these same adjusted early observations; evaluation uses the original later scores. The ceiling ratio for each source-task fit is S max / max { S ( 4 ) , 0.1 } S_{\max}/\max\{S(4), 0.1\} S m a x / max { S ( 4 ) , 0.1 } , using that source task’s observed four-hour score. The prior c c a t c_{\mathrm{cat}} c cat is the median of these ratios after excluding the target task. Let σ ε , σ c , σ β \sigma_{\varepsilon}, \sigma_c, \sigma_{\beta} σ ε , σ c , σ β be the population standard deviations of the corresponding source-fit parameters, with
s ε = max { σ ε , 0.05 } , s c = max { σ c , 0.1 } , s β = max { σ β , 0.15 } . s_{\varepsilon} = \max\{\sigma_{\varepsilon}, 0.05\}, \qquad s_c = \max\{\sigma_c, 0.1\}, \qquad s_{\beta} = \max\{\sigma_{\beta}, 0.15\}. s ε = max { σ ε , 0.05 } , s c = max { σ c , 0.1 } , s β = max { σ β , 0.15 } .
Writing f r e t r y f_{\mathrm{retry}} f retry and f s i g f_{\mathrm{sig}} f sig for the two score curves, the implemented objectives are
L r e t r y = [ f r e t r y ( 2 ) − u ] 2 + [ f r e t r y ( 4 ) − v ] 2 + 2 [ ( ε − ε c a t s ε ) 2 + ( S max / max { v , 0.1 } − c c a t s c ) 2 ] . \mathcal{L}_{\mathrm{retry}} = [f_{\mathrm{retry}}(2)-u]^2 + [f_{\mathrm{retry}}(4)-v]^2
+ 2\left[\left(\frac{\varepsilon-\varepsilon_{\mathrm{cat}}}{s_{\varepsilon}}\right)^2 + \left(\frac{S_{\max}/\max\{v,0.1\}-c_{\mathrm{cat}}}{s_c}\right)^2\right]. L retry = [ f retry ( 2 ) − u ] 2 + [ f retry ( 4 ) − v ] 2 + 2 [ ( s ε ε − ε cat ) 2 + ( s c S m a x / max { v , 0.1 } − c cat ) 2 ] .
L s i g = [ f s i g ( 2 ) − u ] 2 + [ f s i g ( 4 ) − v ] 2 + 2 ( β − β c a t s β ) 2 . \mathcal{L}_{\mathrm{sig}} = [f_{\mathrm{sig}}(2)-u]^2 + [f_{\mathrm{sig}}(4)-v]^2 + 2\left(\frac{\beta-\beta_{\mathrm{cat}}}{s_{\beta}}\right)^2. L sig = [ f sig ( 2 ) − u ] 2 + [ f sig ( 4 ) − v ] 2 + 2 ( s β β − β cat ) 2 .
The sigmoid penalizes slope deviations. Both optimizers start with ceiling min { v c c a t , 100 } \min\{vc_{\mathrm{cat}}, 100\} min { v c cat , 100 } . A coarse parameter grid supplies the starting point; the optimizer’s output replaces it only when the objective improves. Prior construction uses unregularized six-observation fits with up to 3,000 iterations, S max ≤ 110 S_{\max} \le110 S m a x ≤ 110 , and, for the retry curve, T ≤ 8 T \le8 T ≤ 8 . The bounds above apply to the target-pair prediction fits.
Results
Table 6 reports median relative errors and the fractions of predictions below the 10% and 20% error thresholds at all four prediction times. Median errors are similar, with neither curve having a smaller error at every prediction time. The retry curve has at least as many predictions below 10% relative error, and more below 20%, at every prediction time.
Figure 4 and Figure 16 show the 12-hour predictions and increasing median error at later times. Both curves have median error below 11% at all four prediction times.
Figure 4. Agent Score Prediction at 12 Hours. Each point is a task–model pair. Predictions use its scores at 2 and 4 hours and parameter estimates from other tasks in the same category, excluding the target task. The retry curve models diminishing gains from repeated attempts; the comparison curve is sigmoid in log time (Appendix § 18 .§ 1 ). All 252 pairs are plotted; median relative errors are 10.7% and 10.9%, respectively, over 248 pairs with positive observed scores. Dashed and dotted lines mark perfect prediction and ± 20 % \pm20\% ± 20% bands.
Figure 16. Median Relative Error by Prediction Time. Both curves use the protocol in Appendix § 18 .§ 2 . Relative errors use 248 pairs with positive observed scores at each prediction time; the dashed line marks 10%.
Interpretation
The two curves have similar median errors when fitted to early observations with priors from other tasks in the same category. These predictions use early scores and information from other tasks; they do not test the checks assumed by the reuse theorem. Although the source tasks are shared, the penalties constrain different parameters: failure and ceiling ratio for the retry curve, and slope for the sigmoid. Both procedures also use the ceiling-ratio prior for initialization. The differences compare the fitted procedures; they do not isolate curve shape under identical parameter information. Predictive fit does not identify agents’ internal checking or state-reuse behavior. The experiment predicts later scores; it does not evaluate early stopping or compute allocation.