- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies support-exact evaluation of a fixed batch decision under paid, partial evidence. It formulates local query policies by their fee saving and residual count uncertainty, and uses these quantities to construct a net-price allocation that predicts batch-level savings. The paper proves cost comparisons to the optimal legal query policy, accounting for omitted local policies, finite supply, and threshold geometry. When response probabilities are unknown but shared across repeated component types, it develops an executed-path learner and proves an excess learning cost in a critical regime, supported by synthetic calculations and BigCodeBench record replays.
Critical strengths
-
The paper clearly distinguishes support-exact evaluation from statistical estimation, and provides cost bounds that account for local-policy coverage, finite supply, threshold geometry, and exact completion costs.
-
The unknown-law analysis charges pilots, exploratory hints, and completion queries rather than reporting oracle savings alone. Figure 1b explicitly shows regimes with negative net savings, which makes the empirical discussion more credible.
Critical weaknesses
The unknown-law method is not shown to provide practical savings at finite batch sizes. In Figure 1b, the reported mean savings are 0.125,-51.94, and -378.00 for , and 41 of 48 runs take the initial full-completion branch. The BigCodeBench replay only demonstrates exact stopping with fixed records and different thresholds, not the learned query policy. A convincing evaluation should include realistic multi-type interfaces where Learn(σ) achieves consistently positive net savings after all pilot, acquisition, and completion fees.
Questions for authors
-
Can the authors provide a realistic multi-type example where Learn(σ) achieves consistently positive net savings after charging pilot, hint, and completion fees?
-
The method assumes known finite support graphs and uses an explicit query-history graph. What is the practical cost of constructing these graphs and verifying their support/completion conditions for a real evaluation pipeline?
-
Appendix D.4 notes that the identity of a public full routine can convey information about the law. How does the learning guarantee change when only a distribution-independent public full routine is available?
2 comments
Thank you for your rebuttal. As my original score was already positive, I will maintain it unchanged.
Response to Reviewer zuu4: W1, W3, W4, Q1–Q3
Thank you for recognizing the exact-decision formulation and the complete query-fee accounting. We have added experiments on reserve selection and multiple item types, measured graph costs, and derived a bound for a fixed public routine.
W1 — What changes the finite-size costs in Figure 1b?
We added an empirical Bernstein reserve rule and checked for an exact decision after each query. At N=12,801, using the same stopping checks, the original reserve coefficient takes the result-only fallback in 335 of 512 new batches; the Bernstein rule does so in 12 of 512. Mean savings relative to full evaluation rise from 453.17 to 1,256.90 fee units. Result-only exact stopping on those same batches saves 903.63, so Bernstein saves 353.27 more. These fees include pilots, hints, result queries, and final completion.
The reserve changes which queries are bought, not the decision rule. After each purchase we update the possible pass-count interval [L,U] and stop only when L≥k or U<k. Fewer full-evaluation branches lower fees while preserving exact outcomes.
W4, Q1 — Does Learn(σ) save fees on multiple item types?
We added a three-type H/P/X simulation using the paper's code-testing interface: H is a paid prediction, P a prefix-test result, and X the complete-test result. Each type has its own probabilities and fees. The (H,prefix,remainder) fee triples are (0.25, 1, 10), (0.75, 2, 16), and (1, 3, 6).
A failed prefix gives X=0; after a passing prefix, the remainder determines X. H can be queried before or after the prefix. The learner chooses among these paid paths under one batch threshold.
At N=38,401, the graph learner was evaluated on 32 independent batches, charging every pilot, hint, prefix, and remainder query. Mean net savings relative to full evaluation were 1,684.27 with reserve coefficient 40 (23/32 batches positive) and 3,350.33 with coefficient 20 (28/32 positive). Within each type, items share the same response law, as assumed in Theorem 2.
The coefficient-20 learner also saves 604.38 and 838.28 units on average at N=2,401 and 9,601. Both sizes use the same complete fee accounting.
W3 — What was added beyond fixed-order BigCodeBench replay?
On the original 148 Qwen and 144 Llama programs, we tested both an online rule that selects the next test from already purchased responses and a static-H priority rule. Mean total fees (Qwen/Llama) are 188.12/162.12 for shorter-test-suite-first stopping, 189.83/166.99 for online ordering, and 187.98/159.73 for H priority. The H fees are included at 0.01 per program. Thus, H priority saves an additional 0.14/2.39 fee units against shorter-suite-first stopping. The three-type experiment above directly evaluates Learn(σ).
Q2 — What does graph construction and condition checking cost?
For programs with 3–12 ordered tests, our graphs have 21–75 states and 24–96 reply edges. Building one takes 23–51 microseconds in our implementation. Each state records prefix progress, whether a failure occurred, and the current hint observation.
The graph is built once per interface; backward dynamic programming scores legal queries. We check that every terminal history determines the result and every unresolved history admits a legal completion.
The test protocol supplies the logical support: one failed test implies X=0; all tests passing implies X=1. We check that each terminal full-evaluation state determines X and each unfinished state has a legal completion. Equation (12) bounds the expected completion fee per unit of remaining uncertainty; in our six-outcome example the largest ratio is 72. With d freely ordered binary queries, the history graph can have up to 3d states.
Q3 — What if the public full-evaluation routine is distribution-independent?
Theorem 2 is unchanged when one fixed public routine is optimal for every law in the family. The prefix-then-remainder routine in Appendix B.4 and the common routine used for Corollary 1 are examples.
When a fixed routine is legal but more expensive than the optimal one, our supplementary derivation adds its expected excess fee. For item g, let Cσg be the fee of the supplied routine, vg its minimum expected full-evaluation fee, and Ig=1 when that item is selected for full evaluation before graph learning, without observing its own responses. The added term is
Δpre=∑gPr(Ig=1)(ECσg−vg).
When this term is O(N1/4), the total excess fee retains the fourth-root order under the other conditions of the theorem.
For two unit-fee OR tests with success rates 0.8 and 0.2, the better order costs 1.2 and the reverse costs 1.8. The extra 0.6 belongs in this term.