- 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-+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
- 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.
- The experiments show low read percentages. On the Qwen 3.5-9B chains (Table 3), BranchCert- 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
- 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.
- 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
- 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?
- 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
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 ().
| task | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | total |
|---|---|---|---|---|---|---|---|---|---|
| parent | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 4 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 2 | |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6 |
The paired total of a candidate lies between the worst and best completions of its unread cells, and , where 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.
| candidate | reads of its row | decision | |
|---|---|---|---|
| 4 | , no completion qualifies, exclude | ||
| 7 | , every completion qualifies, ACCEPT |
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 certificate | BranchCert-Σ | BranchCert-Σ+H | |
|---|---|---|---|---|
| reads to exclude c5 | −32 | 1,275 | 611 (−52%) | 356 (−72%) |
| reads to exclude c1 | −11 | 1,308 | 1,012 (−23%) | 695 (−47%) |
| reads to exclude c3 | +17 | 1,447 | 1,447 (0%) | 1,247 (−14%) |
| new cells in the whole round | 12,457 | 10,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.
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 round | rounds with a qualifying candidate | share of the table read | cells read per round |
|---|---|---|---|
| 10 (Table 4) | 9 of 24 | 38.2% | 7,566 |
| 20 | 20 of 24 | 18.8% | 7,274 (−4%) |
| 40 | 24 of 24 | 5.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 target | exact certificate | BranchCert-Σ | BranchCert-Σ+H | cells per round, BranchCert-Σ+H |
|---|---|---|---|---|
| 375 | 36.7% | 31.6% | 28.7% | 1,938 |
| 750 | 41.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.
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.
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.
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.
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.