acceptodds
Under review as a conference paper at ICLR 2027

Pay Once, Certify Every Round: Anytime-Valid Verdicts for Self-Improving Programs

Abstract

A program that improves itself repeats one round. It proposes a batch of candidates, edited copies of its own code, scores them on a fixed set of tasks, and keeps at most one. Each score costs a model call on one task, so the cost of a round is the number of program–task cells it reads. This paper asks how few cells a round can read, together with the decision rule that makes that small sample enough. We present BranchCert, a certificate that returns one of two verdicts for the round: Accept for a named candidate that beats the parent, the program the loop is running, or None Better when no candidate does. It returns Undecided when the budget runs out first. The certificate reads every candidate and the shared parent along one random order of the tasks. The unread tasks then form a uniformly random sample of the table, which lets the certificate stop as soon as the comparison is settled and bound its error at whatever time it stops. A second form spends the paid history of the loop. Earlier rounds scored other programs on the same tasks, those scores predict how the current batch will fare, and the certificate measures the residual the prediction leaves. On recorded rounds of a running self-improvement loop, on public evaluation tables, and on a paired re-execution of a recorded round, the certificate reaches the verdict of the complete table after a fraction of the reads. It agrees with the complete table in every run on the recorded loop, errs in at most 0.5% of runs on the public tables, and lowers its mean cost as the loop accumulates paid history.

Primary area:
foundation or frontier models, including LLMs
Keywords:
self-improving agents, anytime-valid inference, testing by betting, sampling without replacement, evaluation cost, control variates, candidate selection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_R8qeOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
3(+1)
Read review
Paper summary

The paper introduces certificates called BranchCert which reduces the number of evaluations done on candidate programs. It returns ACCEPT if a candidate meets all requirements, NONE BETTER if none meet the requirements or UNDECIDED if the budget runs out. They introduce multiple variants of BranchCert such as BranchCert-Σ\Sigma+H, which uses earlier evaluation results (history) to set bounds to predict candidate outcomes. The paper provides theory about these methods and also experiments focused on self-improvement chains, public score tables and tool-use.

Critical strengths
  1. The paper provides conditions for reducing the number of read cells in evaluation. The exact bounds account for the worst-case and help evaluation end more earlier, and determine one of ACCEPT, NONE BETTER, UNDECIDED for the batch of candidates.
  2. The experiments show low read percentages. On the Qwen 3.5-9B chains (Table 3), BranchCert-Σ\Sigma reads only 23.2% of the full table and then adding in history, the method only reads 19.4%, all while having no wrong outputs in these chains. They also show that on MATH and MMLU tasks, the certificate admits candidates that tend to improve performance on tasks, specifically by MATH task improved by 4.9% on average over six chains (Section 5.4, pg. 8 & Table 3)
Critical weaknesses
  1. My main concern is that efficiency gains do not seem that practical. I think adding runtime of the certificates and token usage of the steps would show more practical improvements.
  2. I found Section 3 and 4 hard to follow due to the heavy theory without any practical examples. Figure 1 and 2 help explain the approach but the lack of examples with each of the BranchCert made it difficult to follow.
Questions for authors
  1. Could you report runtime and token usage through the process to reach a decision on a batch of candidates? Is there any overhead when updating bounds of the certificate and deciding on the decisions?
  2. Could you provide a walk-through (diagram) on a batch of candidates with the three variants of BranchCert? This would make the paper read more clearly.

I have chosen weak accept for the paper. The contribution seems to be good as reducing evaluation time is an important problem in self-improving agent systems. I think the addition of computation costs and making the method easier to understand would strengthen the paper.

5 comments
AuthorsOpenReview ↗

Response to Reviewer R8qe (1/3): output tokens, wall-clock time and overhead (W1, Q1)

Thank you for the constructive review. Both of your suggestions led to additions in the main text: a measurement of output tokens and wall-clock time in §5.4, and a worked round as the new Figure 3. We share your view that "reducing evaluation time is an important problem in self-improving agent systems". Here are the replies.

W1 & Q1.1: Whether the savings are practical, shown by the runtime and token usage needed to reach a verdict on a batch of candidates.

Answer: Thank you for this suggestion. The savings in cells hold in output tokens, and in wall-clock time when the first batch is full. We executed one recorded round end to end on GPUs, with one parent and eight candidate system prompts of Qwen3.5-9B on 1,500 MATH and 1,500 MMLU tasks. The complete table ran twice, and each certificate ran under two prefetch schedules. The table shows the schedule with a full first batch of 256 tasks per row, and executed cells include the prefetched cells that a certificate never read.

runcells executedoutput tokenswall-clock
complete table, two runs25,50025.0 M, 25.1 M3,212 s, 2,385 s
BranchCert-Σ14,120 (−45%)15.4 M (−38%)1,735 s
BranchCert-Σ+H12,364 (−52%)14.0 M (−44%)2,200 s

With windows that grow from 64 to 256 tasks, the certificates execute fewer cells, 10,744 and 10,260, and take 2,448 s and 2,447 s, about the time of a complete table. At a fixed evaluation budget, the saving allows more rounds. Within a budget of four complete tables and a cap of 12 rounds, BranchCert-Σ+H completes all 12 rounds with budget to spare where full evaluation completes 4, and its final prompts reach the highest MATH test accuracy among the four gates compared. The revision reports the measurement in §5.4 and Appendix E.11, and the loops in §5.2 and Appendix E.14.

Q1.2: The overhead of updating the bounds of the certificate and of deciding.

Answer: The overhead is negligible. Updating the bounds takes 0.7 ms of single-core CPU time per read, against about 0.1 s of GPU inference per cell, and 4.5 s for a full round of BranchCert-Σ on average. We report this cost in §5.4.

AuthorsOpenReview ↗

Response to Reviewer R8qe (2/3): one round under the three forms (W2, Q2)

W2 & Q2: Sections 3 and 4 are hard to follow without a concrete example. A walk-through of one batch of candidates under the three forms of BranchCert would help.

Answer: We agree. The revision adds the walk-through to §4 as the new Figure 3, and its two examples follow. The first paragraph of §4 points to the walk-through before the theory, and each step of Sections 3 and 4 states its purpose before its formal statement.

A small example. One target has eight tasks, and a candidate qualifies by solving at least two more tasks than the parent (T=2T=2).

task12345678total
parent E0E_0010110104
E1E_1001010002
E2E_2111110106

The paired total DkD_k of a candidate lies between the worst and best completions of its unread cells, Lk=Rk−(unread parent cells)L_k = R_k - (\text{unread parent cells}) and Uk=Rk+(unread candidate cells)U_k = R_k + (\text{unread candidate cells}), where RkR_k is the candidate's read score minus the parent's read score. The exact form reads the parent row once and then each candidate in turn.

candidatereads of its row[L,U][L, U]decision
E1E_14[−3,1][-3, 1]U<2U < 2, no completion qualifies, exclude E1E_1
E2E_27[2,3][2, 3]L≥2L \ge 2, every completion qualifies, ACCEPT E2E_2

The round ends after 19 of the 24 cells. The parent row is read once for both candidates, and each candidate stops as soon as no completion of its unread cells can change its verdict.

A recorded round under the three forms. Round 2 of chain 1 evaluates eight candidates on 1,500 required and 1,500 control tasks per row, and a candidate must solve 30 more required tasks than the parent. The three forms read every row along one shared random order and differ only in the bound they maintain. The table reports reads, with the change from the exact certificate in parentheses.

required gain (needs 30)exact certificateBranchCert-ΣBranchCert-Σ+H
reads to exclude c5−321,275611 (−52%)356 (−72%)
reads to exclude c1−111,3081,012 (−23%)695 (−47%)
reads to exclude c3+171,4471,447 (0%)1,247 (−14%)
new cells in the whole round12,45710,215 (−18%)8,597 (−31%)

The exact certificate uses only the fact that an unread cell is 0 or 1. BranchCert-Σ adds the sampling law of the random reading order, and BranchCert-Σ+H adds a prediction from the paid history of round 1. The further a candidate is below the requirement, the earlier the two statistical forms exclude it, and most candidates of the recorded chains are below it. All three forms accept the same qualifying candidate, c6.

AuthorsOpenReview ↗

Response to Reviewer R8qe (3/3): further results on larger rounds and larger benchmarks

Your question on practical gains also led us to examine how the cost of a round changes with its size. The revision reports the two replays below in Appendix E.15.

Further result 1: A round with more candidates.

With two targets, a round of 20 or 40 candidates reads fewer cells than a round of 10. The parent row is read once for the whole batch, and a larger batch more often contains a qualifying candidate, which ends the round. The table reports BranchCert-Σ on the HELM Lite rounds of Table 4.

candidates per roundrounds with a qualifying candidateshare of the table readcells read per round
10 (Table 4)9 of 2438.2%7,566
2020 of 2418.8%7,274 (−4%)
4024 of 245.8%4,226 (−44%)

Further result 2: A benchmark with more tasks.

The cost of the two statistical forms grows more slowly than the table, with no wrong verdict at any size. We cut every target of the six chains to 375 and 750 tasks. The last column gives the cells per round of BranchCert-Σ+H and their multiple of the smallest table.

tasks per targetexact certificateBranchCert-ΣBranchCert-Σ+Hcells per round, BranchCert-Σ+H
37536.7%31.6%28.7%1,938
75041.2%32.1%28.4%3,831 (2.0×)
1,500 (Table 3)39.9%23.2%19.4%5,232 (2.7×)

We hope these measurements address your main concern on practical gains and that the walk-through makes Sections 3 and 4 easier to follow. Thank you again for both suggestions, which improved the paper. We are happy to answer any further questions.

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

This paper studies how to reduce evaluation cost when deciding whether to accept one of several candidate edits in a self-improvement round. BranchCert certifies whether a candidate meets all improvement and non-inferiority requirements on a fixed score table, or if none of them are qualified or the budget is insufficient. It introduces statistical variants that read all programs along a shared random task order and can reuse earlier evaluations through residual predictions. Experiments are conducted on HELM Lite tables, recorded Qwen3.5-9B prompt-improvement chains and live Granite-4.2-8B tool-use rounds, comparing against without-replacement confidence sequences, per-candidate gates and anytime-valid evaluators.

Critical strengths
  • The set-level formulation is well motivated, as candidates share a parent and certifying that none qualifies is useful when most proposed edits fail.
  • The guarantees hold under adaptive stopping and scheduling across candidate rows, and the ablations show why the sampling conditions matter.
  • The evaluation includes many baselines, recorded chains, a live re-execution and fresh-task checks. On the recorded chains, the mean share read drops from 39.9% for the exact certificate to 23.2% for BranchCert-Σ and 19.4% with history reuse.
Critical weaknesses
  • Logical reads do not fully capture execution cost. In the live re-execution, BranchCert-Σ executes 11,136 cells but reads only 9,595 before stopping, as unread cells are prefetched, and reading cells sequentially also limits batching. Token cost and wall-clock time under realistic parallelism should be reported.
  • The savings over simple baselines are modest. In Table 4, BranchCert-Σ reads 38.2% of the HELM tables while the exact certificate, which has no statistical risk, reads 44.7%. History reuse also gives no saving on HELM, and on the chains 42 of 336 runs with history read more than BranchCert-Σ.
  • The experiments do not cover the self-improvement setting well. All chains rewrite a system prompt with one model on MATH and MMLU for only eight rounds, and only 7 of 48 rounds end in ACCEPT, so the wrong-ACCEPT rate on the chains is barely tested. In Table 3, the held-out MATH gain also mostly comes from chain 6 (81.0% to 93.7%). Independent loops driven by BranchCert and minibatch gates (e.g., GEPA) should be compared at the same total budget, ideally also on code-editing loops such as the Darwin Gödel Machine on SWE-bench.
  • The guarantee targets a cached finite table rather than expected rollout performance. In the live re-execution, 6.6% and 5.7% of cells change under temperature-zero decoding, and the majority-label bound in Appendix B assumes independent rollouts, which the audit in Appendix E.6 shows does not hold.
Questions for authors
  • In the live re-execution, the history-based residual ranges assume cached parent scores equal the newly read ones. How are they reconciled when the fresh parent scores differ, and does Theorem 2 still hold in that case?
  • The same admission tasks are reused in every round. Over longer chains, does repeated selection on them hurt fresh-task performance, and can task refresh keep the benefit of history reuse?
5 comments
AuthorsOpenReview ↗

Response to Reviewer vkm4 (1/4): execution cost and the size of the savings (W1, W2)

Thank you for the close, constructive review. Your comments address the details that decide practical deployment, from the prefetched cells of the live run to the parent cache behind Equation (3). They led to new experiments in the revision, among them an end-to-end cost measurement, independent loops per gate at one budget, and loops over SWE-bench Verified. Here are the replies.

W1: Logical reads may understate execution cost, because prefetch executes cells that are never read and sequential reading limits batching. Token cost and wall-clock time under realistic parallelism should be reported.

Answer: Thank you for this suggestion. We measured output tokens and wall-clock time under batched GPU execution with every executed cell charged, and the certificates save output tokens under both prefetch policies and wall-clock time with a full first batch. A certificate fixes only the order in which scores are read, so cells can execute ahead of the reads in batches. We executed round 2 of chain 1 end to end on GPUs, running the complete table twice and each certificate under two prefetch policies.

runcells readcells executedoutput tokenswall-clock
complete table, two runs25,50025.0 M, 25.1 M3,212 s, 2,385 s
BranchCert-Σ, windows of 64 to 256 tasks9,90310,744 (−58%)12.4 M (−50%)2,448 s
BranchCert-Σ+H, windows of 64 to 256 tasks9,35910,260 (−60%)11.9 M (−52%)2,447 s
BranchCert-Σ, first batch of 256 tasks10,29214,120 (−45%)15.4 M (−38%)1,735 s
BranchCert-Σ+H, first batch of 256 tasks9,38712,364 (−52%)14.0 M (−44%)2,200 s

Small windows save the most output tokens, and a full first batch saves the most wall-clock time. At a fixed budget, the saving allows more rounds (W3.1). The revision adds this measurement to §5.4 and the full accounting to Appendix E.11.

W2.1: On HELM, BranchCert-Σ reads 38.2% of a table against 44.7% for the exact certificate, which carries no statistical risk, so the saving over a simple baseline looks modest.

Answer: The exact certificate of Table 4 is itself a form of BranchCert (Theorem 1), and Table 4 reports the hardest of the nine settings in our difficulty sweep.

setting, 216 HELM roundsmedian saving of BranchCert-Σ over the exact certificate
nearest-ability candidates at the smallest requirement (Table 4)9.4%
the other eight settings27.7% to 56.8%

Every external stopping rule that reads less than BranchCert-Σ either errs above the level or leaves most runs undecided. The revision shows this comparison in the main text as Table 1 and states its setting and the sweep in §5.1.

W2.2: History reuse gives no saving on HELM.

Answer: Paid history saves more reads the better earlier rows predict the current paired differences. On HELM, the earlier rows belong to unrelated models, which is the null case of §5.1. In a self-improvement loop, they belong to the loop's own earlier candidates. The table reports the share of each table read (%).

paid historyBranchCert-ΣBranchCert-Σ+Hdifference (points)
HELM, rows of unrelated models38.237.8−0.4
chains, the loop's own earlier rounds23.419.6−3.8
chains, permuted history23.423.7+0.3
chains, adversarial predictions23.424.7+1.3

A misleading history preserves the guarantee: across the five predictors of Appendix E.13, including the permuted and adversarial ones, none of the 15,360 runs returns a wrong verdict.

W2.3: On the chains, 42 of 336 runs with history read more than BranchCert-Σ.

Answer: Those 42 runs are individual reading orders, and the saving is consistent once orders are averaged. With the six chains as units, BranchCert-Σ+H reads 16.7% less than BranchCert-Σ (standard error 2.9), and reads less in every chain. The revision reports this chain-level estimate in §5.2 and Table 20.

AuthorsOpenReview ↗

Response to Reviewer vkm4 (2/4): independent loops per gate, SWE-bench Verified and wrong ACCEPT (W3)

W3.1: The chains cover one model, one task pair and eight rounds. Independent loops driven by BranchCert and by minibatch gates such as GEPA should be compared at the same total budget.

Answer: Thank you for this valuable suggestion. We ran this comparison, and the loop driven by BranchCert-Σ+H reaches the highest MATH test accuracy. Each gate runs its own loop from the same initial prompt and proposer over three seeds, within a budget of four complete tables (108,000 acceptance cells, unread prefetch counted) and at most 12 rounds. Final parents are scored on 1,000 MATH test tasks outside the acceptance tasks. The last column gives the lead of BranchCert-Σ+H in points.

gaterounds within budgetaccepted (non-qualifying)MATH test accuracylead of BranchCert-Σ+H (points)
BranchCert-Σ+H123 (0)92.4%
full evaluation43 (0)86.5%+5.9
GEPA pipeline124 (0)88.0%+4.4
GEPA minibatch gate1222 (18)80.3%+12.1

Two effects contribute: rounds that read fewer cells leave budget for more rounds, and the certificate accepts no non-qualifying edit. BranchCert-Σ+H keeps MMLU within 1 point of every other gate. Beyond the chains, the paper evaluates the certificate on live tool-use rounds of Granite-4.2-8B (§5.4), on 95 HELM models (§5.1), and on loops over the SWE-bench Verified leaderboard (W3.2). The revision adds these loops to §5.2 and Appendix E.14.

W3.2: Ideally also code-editing loops, such as the Darwin Gödel Machine on SWE-bench.

Answer: Thank you for pointing us to this setting. BranchCert reads only the score table, so it handles a code edit in the same way as a prompt edit, and we evaluated it on SWE-bench Verified. The 135 coding agents of the public leaderboard, from multiple model families, enter in chronological order at eight per round over 17 rounds. The 306 issues annotated at 15 minutes or more form the required target and the 194 shorter ones form the control (b=±0.02b=\pm0.02), with 512 reading orders per gate.

gateagent–issue results per loopwrong verdicts
full evaluation67,500reference
BranchCert-Σ25,137 (−63%)none in 8,704 rounds
GEPA pipeline19,161NONE BETTER in 2,605 of the 6,849 rounds with a qualifying agent
GEPA minibatch gate948non-qualifying agent accepted in 26.4% of rounds

The staged evaluation of the Darwin Gödel Machine (10, then 60, then 200 tasks) is a sequence of such fixed batches, so BranchCert applies to it unchanged. The revision reports these loops in Appendix E.12.

W3.3: Only 7 of 48 chain rounds end in ACCEPT, so the chains test the wrong-ACCEPT rate on few rounds.

Answer: We tested wrong ACCEPT where it is hardest to avoid, with a candidate placed on the qualification boundary, and where ACCEPT is frequent, and the wrong-ACCEPT rate stays below α/2\alpha/2 in both.

testwrong ACCEPT
chain rounds edited so that one candidate is on the requirement or one task short, 288,000 runsat most 0.23% at α=0.05\alpha=0.05 and 0.83% at α=0.2\alpha=0.2
HELM, 715 ACCEPT verdicts over five levels from 0.01 to 0.2at most one per level

The boundary replays run without history and with four history predictors, including the permuted and adversarial ones. The revision reports them in Appendix E.13.

W3.4: The held-out MATH gain of Table 3 comes mostly from chain 6.

Answer: The held-out gain holds with chain 6 excluded, and the revision now reports the gain without chain 6 (§5.4). On the 500 fresh tasks of §5.4, the final prompts gain 4.9 MATH points on average and 3.1 without chain 6. MATH rises in five of the six chains and falls in none, and MMLU changes by 0.0 to +1.6 points.

AuthorsOpenReview ↗

Response to Reviewer vkm4 (3/4): the certified table, the parent cache and task refresh (W4, Q1, Q2)

W4: The guarantee covers a cached finite table and does not cover expected rollout performance. Cells change under temperature-zero re-execution, and the independence assumption of Appendix B fails in the audit of Appendix E.6.

Answer: You are right about the target. BranchCert certifies the realized score table, the object on which every gate decides, including full evaluation on the complete table. It controls the decision error of reading part of the table at level α\alpha and leaves the measurement error of the evaluator where the complete table leaves it, so it needs no model of rollout noise. Rollouts are dependent in practice: inference stacks change greedy outputs with batch size, GPU count, and numerical precision [1], as Appendix E.6 finds. In our re-execution study, both fresh complete tables keep the qualifying candidate c7, and both certificates return the complete-table verdict in all 32 replays. A loop can guard against evaluator noise [2] by raising the requirement by the observed noise band or by defining each cell as a majority vote over repeated rollouts (Appendix B.1), and either choice redefines the table and leaves BranchCert unchanged. The revision states this scope in §3 and §4.3.

Ref: [1] J. Yuan, H. Li, X. Ding, et al. Understanding and Mitigating Numerical Sources of Nondeterminism in LLM Inference. NeurIPS 2025. [2] D. Heineman, V. Hofmann, I. Magnusson, et al. Signal and Noise: A Framework for Reducing Uncertainty in Language Model Evaluation. NeurIPS 2025.

Q1: When fresh parent scores differ from the cached ones, how the history-based ranges are reconciled, and whether Theorem 2 holds in that case.

Answer: Paid parent scores are cache hits and are never re-executed, so no fresh parent score can differ from the score its range uses, and every range contains its paired difference. The paired re-execution decodes in batches, so its agreement with the complete table is an empirical check, and the 32 replays on the two fully executed fresh tables fall under Theorem 2. Before round 2, the re-execution preloads the 8,506 cells paid in round 1 (1,500 of them in the current parent's required row), and every other cell executes once and is cached. For an evaluator without a cache, we tested two remedies on a stale parent row (where 46 and 54 parent cells differ).

handling of a stale cached parent rowoutcome over 512 runs
range check of our implementationhalts 510 runs before any verdict, and the other 2 accept a qualifying candidate
stale cells widened to the range [−1,1][-1,1]a qualifying ACCEPT in every run, with 11% to 12% fewer reads than BranchCert-Σ

The revision states this cache contract in §3 and §4.3 and reports the replay in Appendix E.13.

Q2.1: Whether repeated selection on the same admission tasks hurts fresh-task performance over longer chains.

Answer: We observe no drop on fresh tasks in either the 8-round chains or the 12-round loops of BranchCert-Σ+H, the setting where the adaptive-overfitting risk of reusable holdouts [3] would appear. After eight rounds, the final prompts change MATH accuracy on 500 fresh tasks by 0.0 to +13.8 points per chain and MMLU by 0.0 to +1.6. In the 12-round loops of W3.1, the final parents of BranchCert-Σ+H gain 11.2 MATH points on tasks outside the acceptance set.

Q2.2: Whether task refresh can keep the benefit of history reuse.

Answer: Task refresh keeps part of the saving from paid history, and the saving decreases with the refreshed share. We replayed all six chains, replacing a random share of each target's tasks before every round, as benchmarks that continually collect fresh tasks do [4], and discarding the paid history on replaced tasks.

share of tasks replaced before every roundsaving of BranchCert-Σ+H over BranchCert-Σ, pooled over the chains
none16.4%
a quarter10.2%
a half6.1%

No replay returns a wrong verdict. The revision reports task refresh in §5.2 and Appendix E.10.

Ref: [3] C. Dwork, V. Feldman, M. Hardt, et al. The Reusable Holdout: Preserving Validity in Adaptive Data Analysis. Science, 2015. [4] I. Badertdinov, A. Golubev, M. Nekrashevich, et al. SWE-rebench: An Automated Pipeline for Task Collection and Decontaminated Evaluation of Software Engineering Agents. NeurIPS 2025 Datasets and Benchmarks Track.

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

This paper studies how few program–task cells a self-improvement round needs to read to decide whether any candidate qualifies against a shared parent on a fixed, finite task set. It presents BranchCert, a set-level certificate that returns ACCEPT for a named candidate that meets the required improvement on every target, NONE BETTER when no candidate qualifies, or UNDECIDED when the budget runs out first. BranchCert-E uses exact bounds on unread scores. BranchCert-Σ reads candidates along a shared random order of tasks and uses finite-population confidence sequences to provide anytime-valid verdicts. BranchCert-Σ+H additionally uses the paid history of the loop to predict current paired differences and applies residual betting to those predictions. The theoretical results bound wrong ACCEPT and wrong NONE BETTER verdicts under adaptive scheduling and stopping, and extend across rounds through a prespecified error budget. Experiments on public evaluation tables, recorded self-improvement chains, live tool-use rounds, and a paired re-execution study report reduced distinct-cell cost and high agreement with the complete table. Fresh-task evaluations provide additional evidence of generalization beyond the finite-table guarantee.

Critical strengths
  1. A principled set-level certificate for a complete self-improvement round. BranchCert explicitly distinguishes ACCEPT for a named qualifying candidate, NONE BETTER when no candidate qualifies, and UNDECIDED at budget exhaustion. Theorem 2 controls wrong ACCEPT and wrong NONE BETTER verdicts under adaptive scheduling and stopping, while accounting for the shared parent row. This is a meaningful contribution because it aligns the statistical guarantee with the decision the loop actually needs to make.
  2. Effective reuse of the paid history of the loop. BranchCert-Σ+H uses frozen predictions of current paired differences and applies residual betting while retaining the finite-table guarantee under the stated conditions. On the recorded self-improvement chains, it reads a mean 19.4% of each table, compared with 23.2% for BranchCert-Σ, with no observed wrong verdicts. This provides concrete evidence that previously paid evaluations can reduce the cost of later rounds, supporting the practical value of the proposed approach.
Critical weaknesses
  1. The comparisons do not sufficiently isolate the contribution of the proposed certificate. In Table 4, the published without-replacement sequences use an eager-parent Bonferroni wrapper, whereas the main BranchCert results also benefit from lazy parent reads and one-sided set-level error allocation. Under the same eager-parent wrapper, BranchCert-Σ reads 43.1% of the table, compared with 43.6% for ALPHA with an adaptive prior. Running representative existing sequences within the same lazy-parent, set-level wrapper would clarify the source of the advantage. This comparison is consequential because the current evidence establishes the effectiveness of the combined procedure more clearly than the additional value of the proposed betting construction.
  2. The connection between paid-history reuse and the paired re-execution study remains unclear. Equation (3) uses a recorded parent score to restrict the range of the current paired difference, and Section 4.3 requires that the cached parent score equal the score a new read returns. However, Section 5.4 reports score changes in the paired re-execution study. The paper should explain whether parent scores remain cached or are re-executed, and how historical ranges are handled when scores change. This does not invalidate the frozen-table guarantee, but it limits what the re-execution study establishes about BranchCert-Σ+H in settings with nondeterministic scores.
Questions for authors
  1. Baseline comparison: How do representative published without-replacement sequences, such as ALPHA or hedged-capital betting, perform under the same lazy parent reads, one-sided set-level error allocation, and acquisition schedule as BranchCert-Σ? Table 4 shows relatively small differences within the eager-parent wrapper; this comparison would help determine how much of the reported saving comes from the betting construction versus the set-level wrapper.
  2. Paid history under re-execution: In the paired re-execution study, does BranchCert-Σ+H retain cached parent scores or re-execute those cells? If parent scores are re-executed, how are the ranges in Equation (3) updated to ensure that they still contain every current paired difference? Please clarify which score table the finite-table guarantee applies to in this study.
  3. Reproducibility: Could you provide the experimental betting grid, mixture weights, HELM Lite requirements, and the configuration and training data of the low-rank factor model? Could you also clarify how the anytime-valid evaluators in Table 4 were adapted to the set-level decision? These details would materially help assess whether the reported distinct-cell costs reflect comparable implementations.
  4. Recorded-chain construction: What rule selected the accepted candidate and next parent when multiple candidates qualified in the complete table? During replay, were all certificates constrained to follow that recorded parent sequence, or could they select different qualifying candidates? Please clarify how any differences affected subsequent proposals, paid history, and cost accounting.
  5. Distinct-cell cost versus executed cost: In the paired re-execution study, some cells are prefetched but remain unread when the certificate reaches its verdict. Could you distinguish distinct cells read, cells actually executed, and cache hits for both BranchCert-Σ and BranchCert-Σ+H? Does the reported saving remain comparable when all executed cells are charged?
  6. Budget enforcement: Algorithm 2 can read the rest of a parent row or acquire a parent–candidate pair within one iteration. How is the remaining budget checked before these operations, and how does the implementation handle a budget insufficient to complete them? This clarification is important for interpreting the budgeted decision rates.
  7. Uncertainty in the paid-history saving: How are the standard errors in Table 3 computed, and do they account for repeated reading orders on the same round and dependence between rounds within a chain? Could you provide an uncertainty estimate for the paired cost reduction using the six chains as the independent units? This would help assess the stability of the reported benefit from paid history.
5 comments
AuthorsOpenReview ↗

Response to Reviewer 37sV (1/4): wrapper, sequence and paid history separated (W1, Q1)

Thank you for the careful, precise review. Your first question led to the decomposition that §5.1 and §5.2 now report. We appreciate your note that the set-level certificate is "a meaningful contribution because it aligns the statistical guarantee with the decision the loop actually needs to make". Here are the replies.

W1 & Q1: Isolate the betting construction from the wrapper by running published without-replacement sequences, such as ALPHA and hedged capital, under the same lazy parent reads, one-sided set-level allocation and acquisition schedule as BranchCert-Σ.

Answer: Thank you for this suggestion. We ran this comparison, and it separates three contributions: the wrapper, the betting sequence, and paid history. Every sequence uses the reading orders, parent cache, and distinct-cell charging of BranchCert-Σ, and inside the wrapper also its acquisition schedule. The table reports the share of each table read (%), as the mean across runs on the chains and as the within-round median of Table 4 on HELM, with the change from reading the parent row first in parentheses.

sequencechains, parent row firstchains, inside the wrapperHELM, parent row firstHELM, inside the wrapper
BranchCert-Σ+H30.319.4 (−36%)42.937.8 (−12%)
BranchCert-Σ34.823.2 (−33%)43.138.2 (−11%)
control-variate betting with the same history36.123.7 (−34%)44.140.0 (−9%)
hedged capital37.725.2 (−33%)44.440.5 (−9%)
ALPHA, adaptive prior41.727.4 (−34%)43.639.4 (−10%)
  1. The wrapper (across each row). The certificate of Theorem 2 needs only a nonnegative martingale per row, so any anytime-valid without-replacement sequence can run inside the wrapper, and the wrapper reduces the reads of every sequence we ran.
  2. The sequence (down each column, without history). Inside the wrapper, BranchCert-Σ reads less than hedged capital and adaptive ALPHA in every chain.
  3. Paid history. Prior work uses side information as a control variate in betting confidence sequences without replacement [1]. Residual betting bets on the residual of each paired difference, whose conditional mean is exact under every hypothesized finite-population total, and reads less than control-variate betting with the same history in all six chains.

No sequence returns a wrong verdict on the chains, and each errs in at most 0.52% of runs on HELM. The revision shows the published sequences inside the wrapper in the main text as Table 1, adds the full wrapper block to Table 4 and the chain comparison to Appendix E.8, and states the decomposition in §5.1 and §5.2.

Ref: [1] S. Shekhar, Z. Xu, Z. Lipton, P. Liang, A. Ramdas. Risk-limiting Financial Audits via Weighted Sampling without Replacement. UAI 2023.

AuthorsOpenReview ↗

Response to Reviewer 37sV (2/4): the parent cache, executed cells and chain-level uncertainty (W2, Q2, Q5, Q7)

W2 & Q2: In the paired re-execution, whether cached parent scores are retained or re-executed, how the ranges of Equation (3) stay valid when scores change, and which table the finite-table guarantee covers.

Answer: Paid parent scores are served from the cache without re-execution, so the ranges of Equation (3) remain valid, and the finite-table guarantee covers the realized table whenever that table does not depend on the reading order.

questionanswer
Cached or re-executed?Cached. The cache holds the 8,506 cells paid in round 1, and the 1,500 of them in the current parent's required row are cache hits.
Ranges of Equation (3)?Each range is built from the cached parent score that the round reads, so it contains the paired difference.
Which table?The realized table: the cached history plus the first execution of every remaining cell.

The realized table does not depend on the reading order when a score does not depend on the batch it is decoded in, as under deterministic inference [2]. The paired re-execution decodes in batches, so its agreement with the complete table is an empirical check, and all 32 replays on the two fully executed fresh tables fall under Theorem 2 and return the complete-table verdict. For an evaluator that re-executes cached parent cells, we replayed a stale parent row (46 and 54 cells differ). Our range check halts 510 of 512 runs before any verdict, and widening the stale cells to [−1,1][-1,1] returns a qualifying ACCEPT in every run with 11% to 12% fewer reads than BranchCert-Σ, with predictions fitted on all of round 1. The revision states this cache contract in §3 and §4.3 and reports the stale-cache replay in Appendix E.13.

Ref: [2] J. Yuan, H. Li, X. Ding, et al. Understanding and Mitigating Numerical Sources of Nondeterminism in LLM Inference. NeurIPS 2025.

Q5: Distinct cells read, cells executed and cache hits for both forms, and whether the saving remains when every executed cell is charged.

Answer: The saving remains when every executed cell is charged.

re-execution of round 2 of chain 1BranchCert-ΣBranchCert-Σ+Hchange
new cells read9,5957,856−18.1%
cells executed, unread prefetch included11,1368,860−20.4%
cache hits on paid parent cells1,5001,500
executed share of the 25,500 cells of a complete table43.7%34.7%

End-to-end GPU runs of this round charge every executed cell and generate 38% to 52% fewer output tokens than the complete table. §5.4 and Appendix E.11 report this accounting.

Q7: How the standard errors of Table 3 are computed, and the uncertainty of the paired saving with the six chains as independent units.

Answer: Thank you for suggesting the chain-level estimate. Treating the six chains as independent units, as recommended when evaluation items are clustered [3], BranchCert-Σ+H reads 16.7% less than BranchCert-Σ with standard error 2.9, and the saving is positive in every chain (5.2% to 23.7%). This is the mean of the six per-chain savings, and the All row of Table 3 gives the saving of the pooled shares, 16.4%. The standard errors in Table 3 average the rounds of a chain within each reading order and then vary the eight orders, so they measure reading-order randomness on fixed chains. The revision reports the chain-level estimate in §5.2 and Table 20.

Ref: [3] E. Miller. Adding Error Bars to Evals: A Statistical Approach to Language Model Evaluations. arXiv, 2024.

AuthorsOpenReview ↗

Response to Reviewer 37sV (3/4): constants, evaluator adaptation, selection rule and budget check (Q3, Q4, Q6)

Q3.1: The betting grid, mixture weights, HELM Lite requirements, and the configuration and training data of the low-rank factor model.

Answer: A single set of constants governs every table in the paper, and the revision collects these settings in Appendix D.6 alongside the released code.

itemvalue
betting gridfractions {0.05,0.1,0.2,0.3,0.5,0.7,0.9}\lbrace 0.05, 0.1, 0.2, 0.3, 0.5, 0.7, 0.9\rbrace, each scaled by the range of the unread residuals
mixture weightsuniform over the grid
pseudo-countκ=2\kappa=2
parent rowcompleted once any candidate has read half of a target
HELM requirementsb=0.02b=0.02 on the required family and b=−0.02b=-0.02 on the control family
HELM roundssix family pairs, parents at four ability quantiles, the ten nearest-ability candidates, 16 reading orders
factor model, dataper-instance scores of the other HELM models on the round's tasks, excluding the round's parent and candidates
factor model, fitlogistic low-rank factorization, rank from {8,16,32,64}\lbrace 8, 16, 32, 64\rbrace and weight decay from 10110^{1} to 10−510^{-5} selected on 20% held-out entries, Adam for 2,000 epochs at learning rate 10−210^{-2}

Q3.2: How the anytime-valid evaluators of Table 4 were adapted to the set-level decision.

Answer: Each evaluator retains its native sampling rule and runs one process per candidate and target at level α/(KQ)\alpha/(KQ), sharing the reading order, parent cache, and cell charging with BranchCert. A candidate is accepted once its processes certify every target, and the round returns NONE BETTER once every candidate is excluded. All evaluators use the same factor model, which supplies the surrogate for CELEUS, the sampling rule for FAQ, and the control variate for AV-AIVAT.

Q4: The rule that chose the accepted candidate and the next parent when several candidates qualified, whether replays follow the recorded parent sequence, and the effect on proposals, paid history and cost.

Answer: One fixed rule selected each parent, and every replay follows the recorded sequence. Appendix D.4 of the revision now states the rule.

questionanswer
Selection ruleThe first candidate certified by BranchCert-Σ under reading order 0 became the next parent, and NONE BETTER kept the parent.
ReplaysEvery replay of every method reads the same chain of recorded tables, with the recorded parents and proposals.
A different qualifying candidateAn ACCEPT of another qualifying candidate counts as correct and leaves later tables unchanged. This can occur only in the 7 ACCEPT rounds.
Paid history and costEach replay builds its history from the cells it read along its own order and is charged for each cell at its first read.

Q6: How the remaining budget is checked before Algorithm 2 completes a parent row or reads a parent–candidate pair, and what happens when the budget cannot cover them.

Answer: Algorithm 2 checks the budget before every cell read and returns UNDECIDED at the first unpaid read beyond BB. Each parent cell in a row completion counts as one read, and cached paid cells carry no charge. No decision inside Algorithm 2 depends on BB, so a budgeted run follows the unbudgeted cell sequence until it halts, and Theorem 2(ii) covers this stopping rule because the path lemma holds at any random index. The revision states this per-cell check in Algorithm 2 (Appendix D.5).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.