- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper proposes BB-EDGE for certifying pairwise mean-performance advantages on fixed LLM benchmarks. It combines block-factorized empirical-Bernstein e-processes, stakes proportional to benchmark weights, and direct e-Holm to provide anytime-valid family-wise error control under explicit assumptions. Experiments on synthetic data and four real-world benchmarks evaluate error control and certification efficiency.
Critical strengths
- The paper provides a rigorous mathematical formulation and false-positive control guarantees under explicit assumptions, supported by a fairly complete theoretical analysis.
- The ablation studies are reasonably thorough and demonstrate improved evaluation efficiency while controlling false positives in the tested settings.
Critical weaknesses
- The practical scope of the method needs further clarification. Real-data validation of its treatment of within-block dependence focuses mainly on multi-turn dialogue and tool use. It would be helpful to demonstrate benefits in other evaluation settings with dependent scores and explain how the partitioning assumptions can be justified in those settings.
- The incremental contribution over existing methods needs further clarification. SERPANT-R already substantially mitigates false positives in the heterogeneity-only experiments. The paper should more clearly explain BB-EDGE's efficiency advantage over this baseline and the conditions under which that advantage holds.
Questions for authors
- Theoretical efficiency. Please clarify when the positive-growth condition in Theorem 4 holds for the chosen stake grid, and provide a more explicit theoretical characterization of the evaluation budget needed for certification.
- Practical applicability. Please add experimental evidence from some other practical settings involving dependent scores beyond multi-turn dialogue and tool use, and explain how the blocks are defined and their independence justified.
- Incremental benefit. Building on Figure 11, please quantify BB-EDGE's evaluation-cost savings over SERPANT-R at matched certification targets, especially in settings where both methods keep empirical false-positive rates within the target level.
Response to Reviewer JTyp
We appreciate your insightful comments on our work. Please find our response below:
1. Evaluation on more benchmarks [W1, Q2]
Thank you for highlighting the concern. We include two additional real-world benchmarks with dependent scores: IFEval [1] for instruction following and ClassEval [2] for class-level code generation.For IFEval, the instructions of each prompt are evaluated on the same response, so we group them into one block, i.e., ∣Cm∣∈1,2,3. In ClassEval, we group the methods of each class into a block, with ∣Cm∣∈2,…,10, since they share class attributes and are generated together. Each prompt or class is generated in a separate stateless execution with independent randomization and no shared context across blocks. Since independence cannot be tested directly, we assess correlation as a diagnostic for dependence. As shown in the table below, all 95% confidence intervals for the cross-replicate and cross-block correlations contain zero, indicating no detectable correlation across replicates or blocks. We have added these tests across replicates and across blocks in Lines 474–480 and Table 2.
Additionally, we also add the certified graphs, Top-k certification, and rank intervals for IFEval and ClassEval in Appendix F.
2. Efficiency advantage over SERPANT-R [W2, Q3]
Thank you for the great suggestion. Former Figure 11 now appears as Figure 7 in the revised manuscript. The table below summarizes the results shown in Figure 7(a) for a synthetic i.i.d. item stream (N=100, ∣Cm∣=1, hi,ℓ=0) that satisfies SERPANT-R’s assumptions. The results show that both BB-EDGE and SERPANT-R control the anytime FWER, while BB-EDGE achieves higher power. For instance, BB-EDGE reaches 80% power at 50 replicates, whereas SERPANT-R requires 100 replicates to reach 81%, thereby halving the evaluation cost.
3. Clarification of theoretical efficiency [Q1]
Thank you for this insightful comment. We have moved the former Theorem 4 (power consistency) to the main text as Theorem 2, and added Proposition 2 to make the positive-growth condition and the certification budget explicit. These results characterize BB-EDGE’s efficiency in two respects:
Positive growth. With our running-mean predictions, the average log growth converges to the deterministic rate ae,g∞=λgδe/w⋆−∑mψE(λg,m)σe,m2, where the first term is the evidence gained from the true gap δe and the second is a variance penalty from block-level noise. Hence, the condition holds if and only if ae⋆=maxg:ρg>0ae,g∞>0, i.e., at least one stake on the grid gains more from the signal than it loses to noise. A simple sufficient condition is Δa,bB−τ>λmin/[4(1−λmin)], where λmin is the smallest positive stake with positive mixture weight. Since this threshold vanishes as λmin→0, including small stakes in the grid allows even small gaps above the margin to be eventually certified, although smaller stakes yield slower evidence growth.
Evaluation budget. With the design fixed, the first certification time satisfies limsupα↓0log(1/α)Te(α)≤ae⋆1 almost surely. That is, for small α, certifying an edge requires at most about log(1/α)/ae⋆ replicates. The budget therefore grows only logarithmically in 1/α: asymptotically, halving α adds at most about log2/ae⋆ replicates. Moreover, fewer replicates are needed as ae⋆ increases, which occurs when the gap is wider or the block variances are smaller.
[1] Instruction-following evaluation for large language models, arXiv 2023.
[2] Evaluating Large Language Models in Class-Level Code Generation, ICSE 2024.