acceptodds
Under review as a conference paper at ICLR 2027

The Cost of Exact Batch Decisions with Partial Evidence

Abstract

We study the cost of reproducing a fixed batch decision from paid evidence. Each item has a hidden result and a finite query interface. The output must be correct for every result vector compatible with the purchased responses. We compare its expected cost with full evaluation. A local query policy saves work but leaves uncertainty in the batch count. We price these two quantities together. This gives an additive comparison with the optimum over all legal queries. The error separates missing local policies, insufficient repeated items, and threshold geometry. For a single threshold, bounded representation and supply losses give a bounded remainder. No variance lower bound is needed. We then let the shared response probabilities be unknown. Observed support endpoints provide learning feedback without reading every retained result. Under declared interfaces and supplied completion bounds, the extra fee is the square root of the remaining opportunity scale. It is sharply of order at a critical threshold. All acquisition and final completion queries are charged.

Primary area:
learning theory
Keywords:
learning theory, sequential testing, exact evaluation, partial evidence, query complexity, information acquisition, adaptive querying, batch decisions

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_zuu4OpenReview ↗
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 O(N1/4)O(N^{1/4}) excess learning cost in a critical regime, supported by synthetic calculations and BigCodeBench record replays.

Critical strengths
  1. 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.

  2. 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 N=801,3201,12801N=801,3201,12801, 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
  1. Can the authors provide a realistic multi-type example where Learn(σ) achieves consistently positive net savings after charging pilot, hint, and completion fees?

  2. 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?

  3. 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
AuthorsOpenReview ↗

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,801N=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][L,U] and stop only when L≥kL\ge k or U<kU<k. Fewer full-evaluation branches lower fees while preserving exact outcomes.

W4, Q1 — Does Learn(σ\sigma) save fees on multiple item types?

We added a three-type H/P/XH/P/X simulation using the paper's code-testing interface: HH is a paid prediction, PP a prefix-test result, and XX the complete-test result. Each type has its own probabilities and fees. The (H,prefix,remainder)(H,\text{prefix},\text{remainder}) fee triples are (0.25, 1, 10), (0.75, 2, 16), and (1, 3, 6).

A failed prefix gives X=0X=0; after a passing prefix, the remainder determines XX. HH can be queried before or after the prefix. The learner chooses among these paid paths under one batch threshold.

At N=38,401N=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,401N=2,401 and 9,6019,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-HH 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 HH priority. The HH fees are included at 0.01 per program. Thus, HH priority saves an additional 0.14/2.39 fee units against shorter-suite-first stopping. The three-type experiment above directly evaluates Learn(σ\sigma).

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=0X=0; all tests passing implies X=1X=1. We check that each terminal full-evaluation state determines XX 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 dd freely ordered binary queries, the history graph can have up to 3d3^d 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 gg, let CσgC_{\sigma_g} be the fee of the supplied routine, vgv_g its minimum expected full-evaluation fee, and Ig=1I_g=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).\Delta_{\mathrm{pre}}=\sum_g\Pr(I_g=1)\bigl(\mathbb E C_{\sigma_g}-v_g\bigr).

When this term is O(N1/4)O(N^{1/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.

Thank you for your rebuttal. As my original score was already positive, I will maintain it unchanged.

Reviewer_LZZJOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper looks at how to make a decision about a batch without fully evaluating every item. The important point is that the final decision still has to be exactly the same as if everything had been checked. The authors study which queries are worth paying for, relate their approach to the optimal adaptive strategy, and then consider what changes when query-response probabilities are unknown and have to be learned from the batch itself.

Critical strengths
  1. Clear motivation and an interesting setup. Focusing on recovering the exact decision (and not just estimating batch accuracy) makes a lot of sense here.

  2. Theorem 1 is interesting. The authors compare their characterization against the optimal policy across adaptive queries, not just a fixed strategy. They also manage to handle missing local policies, limited supply, and threshold effects while keeping an additive O(1)O(1) gap under the single-threshold condition.

  3. The learning results are interesting too. Even with partial observation, the purchased queries give enough information to evaluate different policies. Getting an O(N1/4)O(N^{1/4}) learning overhead together with a matching lower bound in the two-sensor case is a nice result.

Critical weaknesses
  1. I am not sure how easily the results can be applied beyond the considered setup. In particular, the learning guarantees assume repeated item types with shared response laws, known query supports, and supplied optimal full-evaluation routines. I understand why these assumptions are useful for the analysis, but I would have liked a clearer discussion of how one would verify or obtain them in a new evaluation problem.

  2. I find the gap between the theoretical results and the actual procedure quite large. For instance, at N=801N=801 the known-law optimum saves around 744 fee units, but the sufficient reserve condition asks for 8,402 items, more than the entire batch. In Figure 1b, the learning method falls back to full evaluation in 41 out of 48 runs, and the average savings are negative for the two larger batch sizes.

  3. I am also not fully convinced by the practical significance of the critical-threshold rate. In the majority-gate example, the oracle saves on the order of N\sqrt{N}, whereas full evaluation costs order NN. So even if the learning overhead is only O(N1/4)O(N^{1/4}), the fraction of the total cost saved still goes to zero in this regime. The rate is interesting mathematically, but I would have liked a clearer discussion of what it means in practice.

  4. The real-data experiment feels a bit disconnected from the main learning contribution. It shows that one can stop early when a threshold is already determined, but it only replays fixed orders of test outcomes. It does not really show whether the proposed adaptive acquisition method is better than a simpler exact-stopping approach on realistic data.

Questions for authors
  1. How would one check whether the library and supply errors in Theorem 1 are small for a new query interface? I think this matters for understanding when the characterization is useful.

  2. Is there a realistic batch-size regime where the unknown-law method actually gives positive net savings? The difference between the known-law optimum and Figure 1b seems quite important.

  3. Could the authors evaluate the learned acquisition strategy on a more realistic setup, rather than only replaying fixed query orders? I think a comparison with a simple exact-stopping baseline would help.

I think the theoretical part is interesting, especially the comparison against the optimal adaptive policy and the learning-cost result. My main concern is what we can actually do with these results. The guarantees rely on assumptions that seem difficult to check in practice, and the finite experiments do not yet show that the learning method can recover the savings predicted by the theory. Overall, I am more convinced by the mathematical contribution than by its practical significance.

3 comments
AuthorsOpenReview ↗

Response to Reviewer LZZJ (1/2): W1, Q1

Thank you for recognizing the comparison with the optimal adaptive policy and for asking how the results can be used. Our contribution is a cost characterization: Theorem 1 identifies the saving available to an exact batch decision, and Theorem 2 with Corollary 1 characterizes the extra cost of learning the response probabilities. We have added an explicit interface calculation and experiments with simple exact-stopping baselines.

W1 — Where the learning assumptions come from

Thank you for asking how these assumptions can be obtained. Appendix B.4 gives a code-testing interface where the support and optimal full routine follow directly from the test protocol. Let HH be a cheap prediction, PP indicate whether a fixed test prefix passes, and XX indicate whether all tests pass. A failed prefix forces X=0X=0, so X≤PX\le P. This leaves six possible binary triples (H,P,X)(H,P,X).

Specifically, (P,X)(P,X) can only be (0,0)(0,0), (1,0)(1,0), or (1,1)(1,1); HH may take either value. These six cases follow from test logic, not observed frequencies. A hint guides queries, whereas P=0P=0 certifies X=0X=0.

In this interface, the remaining tests can be run after the prefix passes. When all six allowed triples have positive probability, every exact full evaluation must run the prefix and, if it passes, the remaining tests. That procedure therefore attains the minimum full-evaluation fee for every distribution in the stated family. It is specified by the protocol before the response probabilities are learned.

If the prefix costs cpc_p and the remainder costs rr, the expected full fee is v=cp+rPr⁡(P=1)v=c_p+r\Pr(P=1). Under this support, a hint cannot replace a test needed to determine XX. Thus the supplied full routine is optimal for every allowed response law.

Repeated types come from the sampling design: within a type, items are independent draws from one distribution and share the same query choices and fees.

In a new benchmark, a type is defined by its sampling process and query interface. Sharing a test list specifies legal queries; sharing a response law determines which observations can be pooled. Both are stated in the evaluation protocol. Paid pilot tests estimate that type's response probabilities. Equation (42) shows how complete calibration records give a confidence bound on the smallest allowed outcome probability.

Given mm independently completed (H,P,X)(H,P,X) triples, Eq. (42) subtracts a sampling margin from the smallest of the six observed frequencies. A positive resulting lower bound supplies the probability floor used in Theorem 2; calibration queries are charged. We will place this concrete example next to Theorem 2 so that the source of each assumption is explicit.

Q1 — Checking library and supply errors

With the query graph, fees, and response probabilities specified, both terms can be calculated. A local policy is a rule for choosing queries on one item. The policy library is the set of such rules used to predict the batch saving.

A partial local rule may leave XX unresolved. Its column records the saved fee and uncertainty remaining on the acceptance and rejection sides; the associated prices determine its value for the batch.

For the library error, Eq. (6) compares the chosen library with every legal local policy. At each corner price λ\lambda of the library's price region, a backward dynamic-programming calculation gives Ug,λU_{g,\lambda}: the lowest expected query fee plus the priced remaining uncertainty for item gg. If vgv_g is that item's optimal expected full-evaluation fee, its error term is

dg=max⁡λ(vg−Ug,λ).d_g=\max_{\lambda}\bigl(v_g-U_{g,\lambda}\bigr).

The maximum is over those corner prices; Eq. (7) combines the item-level terms into DND_N. In our added six-outcome H/P/XH/P/X example, vg=6.40v_g=6.40. A library that omits the hint has dg=2.13d_g=2.13; including all legal local choices gives dg=0d_g=0. We checked these values both by enumerating the local policies and by dynamic programming.

The six-outcome interface also makes the legal local policies easy to enumerate, so the numerical library check can be repeated without a large search.

The corner prices come from the library's fee/uncertainty columns. At each corner, the Bellman calculation checks all legal query choices. A positive gap identifies a missed policy with a better priced value.

For the supply error, LNL_N is the expected saving lost when too few reserved items of a useful type are available. It can be computed from the count distribution or bounded using Eq. (10). With unknown probabilities, the same calculations can be made over a simultaneous confidence set obtained from paid calibration data. This gives an upper bound on the error for the distributions in that set.

To check supply in a new batch, set aside a known number of unused items per type, calculate the probability of falling back to full evaluation, and weight that event by the saving lost. This is the role of LNL_N in Theorem 1.

AuthorsOpenReview ↗

Response to Reviewer LZZJ (2/2): W2–W4, Q2, Q3

W2, Q2 — When the unknown-law learner saves money

Yes. At N=12,801N=12,801, our new empirical Bernstein reserve variant saves 1,256.90 fee units after all query fees, versus 903.63 for result-only exact stopping. This is an additional 353.27 units saved across 512 new independent simulated batches. The paired 95% t interval, adjusted across the three tested sizes, is [240.62, 465.91].

Your concern about the gap in Figure 1 is justified. The 744.24-unit saving at N=801N=801 is the optimum when response probabilities are known. Figure 1b includes the cost of learning those probabilities. We addressed the finite-size gap by changing the reserve selection and checking for an exact decision after each query. The reserve is the set of items left available for later query choices.

The new experiment retains the Figure 1 setting: each result costs 10, each hint costs 1, and the hint error rate is 0.1. With the same per-query stopping checks, the original reserve coefficient sends 335 of 512 largest-size batches to the result-only fallback branch; the Bernstein rule sends 12 of 512. Its mean saving rises from 453.17 to 1,256.90. The comparisons use the same batches and count every pilot, hint, result, and final completion query.

Every policy uses the same sampled batch, so 353.27 is a paired cost difference. The Bernstein reserve uses statistics from paid pilots; every query still checks the exact stopping condition.

The 8,402-item figure is indeed a conservative sufficient reserve bound. It bounds supply loss; the stopping certificate itself depends on the purchased results. The new experiments directly measure the effect of choosing the reserve from the observed pilot mean and variance.

W3 — The practical meaning of the fourth-root rate

You are correct that the saved fraction of the total bill tends to zero in this critical majority example. Our result answers the next question: how much of the saving available with known response probabilities remains after paying to learn them?

Under the paper's critical-regime assumptions, the best known-law policy saves Θ(N)\Theta(\sqrt N), while the additional learning fee is O(N1/4)O(N^{1/4}). Learning therefore consumes only an O(N−1/4)O(N^{-1/4}) fraction of the available saving. Equation (15) states this retained fraction explicitly. Corollary 1 gives a matching minimax lower bound on the common-routine two-sensor family: this fourth-root worst-case learning cost is unavoidable on that family.

This complements Theorem 1, which characterizes the optimum over all legal adaptive query policies. For one threshold and bounded library and supply losses, the error in that cost characterization is additive O(1)O(1). Together, the results identify the available saving and the price of learning to obtain it.

The new finite experiment gives the corresponding fee scale. At N=12,801N=12,801, full evaluation costs 128,010. The Bernstein reserve variant saves 1,256.90, or 0.98% of that bill, including 353.27 beyond result-only exact stopping. We will state the total-bill fraction and the oracle-saving fraction side by side in the revision.

W4, Q3 — Real-record costs compared with exact stopping

Thank you for suggesting this comparison. We added same-batch exact-stopping baselines and measured the total fees of the query rules. On the original 148 Qwen and 144 Llama programs, the results are:

Mean total query feeQwenLlama
Fixed task-ID order used in the original replay206.89183.77
Shorter test suites first188.12162.12
Online test ordering from purchased responses189.83166.99
Static-HH ordering, with all HH fees187.98159.73

One unit is the fee for one test-result query. The table averages all pass-count thresholds and the two task-ID tie-breaking orders. The HH fee is set to 0.01 per program. Each rule stops when the purchased results determine the exact batch decision.

The online rule chooses each next test using purchased responses. The shorter-suite baseline uses public test counts. Both follow the same exact stopping rule, so their query fees can be compared directly. Relative to shorter-suite-first stopping, online ordering costs 1.71 more on Qwen and 4.87 more on Llama; static-HH ordering saves 0.14 and 2.39, respectively.

For the paper's learning algorithm, we added simulations using the original single-type model and a three-type code-testing model. The single-type Bernstein variant saves 353.27 more than result-only exact stopping at N=12,801N=12,801. In the three-type experiment at N=38,401N=38,401, Learn with reserve coefficient 20 saves 3,350.33 relative to full evaluation. Sorting by the public query fees saves 3,082.50 on the same 32 batches. Their paired mean difference is 267.83, with a 95% t interval of [−783.71, 1,319.36].

I thank the authors for their detailed answers. I have read the other answers and this response, and I believe that they have clarified the unclear parts of the paper.

I recommend highlighting any changes in the paper in a specific color so that they are easier to cross-check.

I'm increasing my score to 3.

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

Many practical evaluation pipelines—such as software release gates or LLM code generation benchmarks (e.g., BigCodeBench)—ultimately reduce a batch of N items to a categorical threshold decision (e.g., whether a set of programs pass a fixed pass rate). This paper studies support-exact batch evaluation: an evaluator can buy partial evidence (such as cheap proxy predictions H or short test prefixes P before running expensive full test suites X) and stop early, provided that the batch decision is logically guaranteed to be identical across every possible completion compatible with the purchased observations ([L, U] lies entirely within one decision category).

Critical strengths
  1. Novel and Practically Grounded Problem Formulation ("Support-Exact" Certification): The distinction between statistical estimation (which tolerates a δ error probability) and support-exact certification (which uses probabilistic priors to route queries economically, but requires 100% logical certainty on the realized batch before stopping) is a major conceptual contribution.

  2. Strong theoretical analysis: Obtaining an additive O(1) optimality gap (rather than multiplicative approximations common in stochastic Boolean function evaluation) via component-excluding dual projections (Lemma A) and delayed-activation martingale tracking (Lemma C). Furthermore, discovering and proving both the upper and matching minimax lower bounds for the Θ(N^(1/4)) intra-batch learning overhead (against Θ(√N) oracle savings) is a non-trivial and elegant theoretical result.

  3. Clear cost trade-offs in the empirical analysis.

Critical weaknesses
  1. The empirical analysis of simply replaying sequential unit-cost test-bit disclosures in two fixed program orders (ascending vs. reversed task ID) doesn't truly reflect the theoretical analysis. Showing a real LLM proxy H (e.g., a fast lightweight verifier or static analyzer) combined with prefix tests on BigCodeBench would have tested the core theoretical machinery much more directly.

  2. The sufficient reserve size in Equation (10) is very conservative to make the algorithm practical (for standard LLM benchmark sizes - N ∼ 10² - 10⁴) without some kind of heuristic tightening.

Questions for authors
  1. Related to point #1 under Cons, if you use a cheap LLM prediction or static check as H on the 148 Qwen and 144 Llama records, does the gain-to-exposure condition c_h < r(1/2 - ε_h) hold in practice, and how much additional fee is saved over prefix-only stopping?

  2. Related to point #2 under Cons, have you experimented with replacing this worst-case reserve threshold with an empirical Bernstein stopping rule or a smaller practical constant (e.g., aL≈2/β^a_L \approx 2/\hat{\beta}), and at what batch size N does learning achieve positive net savings under a less conservative reserve?

2 comments
AuthorsOpenReview ↗

Response to Reviewer PTK2: W1, W2, Q1, Q2

Thank you for recognizing the cost characterization and the learning-cost result, and for the two concrete experimental suggestions. We added a static checker to the BigCodeBench study and tested both smaller reserve coefficients and an empirical Bernstein reserve rule. We address the original experiment and your two questions below.

W1 — Why the original replay uses fixed orders

You are right that Figure 2 uses fixed query orders. It tests the threshold-distance relation in Eq. (4). On the same 148 Qwen programs, requiring 74 passes takes 242 test queries, whereas requiring 32 passes takes all 411 queries. Only the threshold changes. This shows how the decision rule changes the amount of evidence needed.

We have added a static checker HH and compared its query order with prefix-only exact stopping on these programs. We also added learner experiments with smaller reserves and an empirical Bernstein reserve rule. The two comparisons below report their costs.

W1, Q1 — How much a real H saves beyond prefix-only stopping

With the HH fee set to 0.01 test-query units per program, ordering programs using HH saves an additional 0.14 units on Qwen and 2.39 on Llama. We added a source-code static checker for this experiment. One fee unit is the cost of reading one test result. The baseline checks programs with shorter test suites first and stops as soon as the batch decision is certain.

Mean total query feeQwen: 148 programsLlama: 144 programs
Prefix-only, shorter suites first188.12162.12
Ordering by HH, including every HH query187.98159.73
Additional saving from HH0.142.39

These are averages over all pass-count thresholds and the two task-ID tie-breaking orders. All purchased test results and all HH queries are charged.

Our checker flags seven failures (two Qwen, five Llama), all found by the first test. The shortest prefix already reveals these failures, which explains the small extra saving from changing the program order.

For this ordering rule, buying HH gives positive mean net savings when its per-program fee chc_h is below 0.01096 for Qwen and 0.02657 for Llama. Thus, the fee of 0.01 satisfies both purchasing thresholds. Equation (5) gives an analytic threshold for equally likely pass/fail outcomes and symmetric prediction errors. Here, the purchasing thresholds are calculated directly: divide the additional test fees saved by the number of HH queries purchased.

In Eq. (5), rr is the result-query fee and εh\varepsilon_h the symmetric hint error rate. The real batches have 31/148 and 20/144 passes, so their purchasing thresholds are obtained from the observed query costs.

W2, Q2 — Smaller reserves and empirical Bernstein: results at each N

Yes—the original reserve bound is conservative. We tested both suggestions. At N=801N=801, the bound requires 8,402 reserve items. This is a sufficient condition for a small supply-loss term. Exact stopping itself requires only that the observed test results determine the batch decision.

We reduced the reserve coefficient in Procedure 2 from 160 to 40 and 20. We also added an empirical Bernstein version with coefficient 20. It uses the mean and variance of the paid pilot results to form a 95% interval for the pass probability, then selects the reserve using the interval endpoints. Pilot items are the items fully evaluated first to estimate these probabilities.

The pilot interval only chooses the reserve. The final decision still needs purchased evidence proving at least kk passes or proving that kk cannot be reached. We retain the graph learner and exact stopping rule and charge all pilots.

We ran 512 new independent simulated batches at each size, using the original Figure 1 model: a result query costs 10, a hint costs 1, and the hint error rate is 0.1. The learner uses the results observed during each run. Each run stops when those responses certify the exact batch decision. Mean savings relative to evaluating every item are:

NNResult-only exact stoppingFixed coefficient 40Fixed coefficient 20Empirical Bernstein, coefficient 20
801209.57177.74180.09209.57
3,201463.03279.34352.46330.31
12,801903.631,170.561,141.681,256.90

All pilot, hint, result, and completion queries are included. The result-only baseline uses the same item order and stops as soon as enough results determine the decision.

At N=12,801N=12,801, Bernstein saves 353.27 more units than result-only exact stopping. The paired 95% t interval, adjusted across the three sizes, is [240.62, 465.91]. At the same coefficient of 20, it also saves 115.22 more than the fixed-coefficient learner, with interval [32.29, 198.15]. Thus, positive mean savings occur at all three tested sizes, and the gain over simple result-only stopping appears at N=12,801N=12,801.

Reviewer_PTK2OpenReview ↗

Ack authors' response

Thabnk you for addressing my questions. I will keep my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.