{"id":"4d691c8e-4dbb-451c-a0bd-04e45164c95b","arxiv_id":"2505.03814","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Cer-Eval certifies LLM evaluation with confidence intervals while using 20 to 40 percent fewer test points on MMLU, AlpacaEval, and MATH.","lead":"Most large language model benchmarks are evaluated by running every question, which is expensive and provides no formal confidence statement. This paper introduces Cer-Eval, a sequential evaluation method that chooses which questions to test next and stops when a statistically guaranteed confidence interval is reached.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Cer-Eval's certification is unproven: Algorithm 2's 1-NN partitions are not shown to satisfy the benign-partition condition of Theorem 5.2, so the certified bound and the 20–40% savings are not guaranteed for the implemented algorithm.","rationale":"The reader's weakest assumption is exactly the benign-partition gap, and I agree that this is the most load-bearing issue. The paper's headline contributions are (i) a certified sample-complexity bound and (ii) an algorithm that achieves 20–40% savings with a 95% guarantee. The bound in Theorem 5.2 is conditional on a property that the implemented Algorithm 2 is never shown to satisfy. Without that step, the certification of Cer-Eval rests on the simulations, but those simulations validate against the full-benchmark average rather than the true expected loss, so they cannot confirm the guarantee in Definition 3.4. This is not an inconsistency in the theorem—it is an unproven precondition for the algorithm, and it is addressable either by a new analysis of Algorithm 2 or by modifying the partition subroutine to provide a certificate. Because the framework itself is plausible and the issues are fixable, the verdict remains CONDITIONAL, matching the reader. The lower-bound typo in Theorem 4.2 and the IID/without-replacement mismatch are secondary; the former is a sign error in the printed statement (the proof uses the correct condition), and the latter could be handled by invoking Hoeffding-style inequalities for sampling without replacement. Neither is as central as the partition certification gap. Hence I recommend no change to the reader's CONDITIONAL verdict.","tokens_in":16613,"tokens_out":8557,"duration_ms":81695,"concrete_test":"On the simulation setup of Section 6.1 (e.g., S2, K=3 known groups with known per-group variances), run Cer-Eval with fixed ε and δ=0.05. After each run, take the partition returned by Algorithm 2 at termination and record for each group k: n_k, the empirical variance v̂_k, and the realized K. Check whether n_k/n ≥ ln(K+1) max{v̂_k, ε^{2/3}} holds for all k. Repeat over at least 100 trials and report the fraction of trials in which the benign condition fails. Then, since the true group means are known in this synthetic setting, compute the true expected loss R and the empirical coverage of Cer-Eval's CI over the same trials. If the benign condition fails in a substantial fraction of trials while empirical coverage against R is near or above 95%, the missing proof is a genuine gap; if coverage against R falls significantly below 95%, the gap is directly falsified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that Cer-Eval is an (n, ε, δ)-certified online evaluation algorithm with tight sample-complexity bounds. Theorem 5.2 establishes this only for Algorithm 1 when it operates with a benign partition of the test data (Definition 5.1), i.e., each group k must satisfy n_k/n ≥ ln(K+1) max{v_k, ε^{2/3}} for the true conditional variances v_k. The actual implementation, Algorithm 2, produces a partition by training a 1-NN classifier on quantized loss values of the evaluated points, choosing K to minimize the estimated CI radius. The paper contains no argument that such a learned partition satisfies the benign condition. Because the partition is a random function of the evaluated samples and is selected to minimize the estimated CI width, the realized per-group sample sizes n_k are not controlled against the true v_k. The proof of Theorem 5.2 explicitly says 'the known benign partition will be used as the partition subroutine,' so the certified bound does not transfer to Cer-Eval as implemented. The simulations do not resolve this gap: 'the empirical failure probability is calculated as the proportion of trials where the CI does not contain the model's average performance across the entire dataset' (Section 6.2), which is not the true expected loss R targeted by Definition 3.4. Hence neither the theoretical guarantee nor the empirical validation establishes the claimed certification.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Cer-Eval, an online, adaptive framework for LLM evaluation. It formalizes an (n, ε, δ)-certified evaluation algorithm, defines test sample complexity, establishes upper and lower bounds under a bounded-loss assumption (Theorem 4.2), and shows that with a 'benign partition' the required sample size can be reduced by a factor controlled by the within-partition variances (Theorem 5.2). The authors then present Algorithm 1 (Cer-Eval) with a 1-nearest-neighbor partition subroutine (Algorithm 2), and report simulations and real-benchmark experiments on MMLU, AlpacaEval, and MATH claiming 20–40% test-point savings at 95% confidence.","tokens_in":16880,"tokens_out":4244,"duration_ms":44458,"significance":"If the guarantees transferred to the implemented algorithm, this would be a useful contribution: the framework addresses a real gap in current LLM evaluation practice, which typically reports full-dataset averages without finite-sample reliability guarantees. The adaptive Hoeffding/Bernstein machinery is appropriate, and the test-sample-complexity view is a meaningful formalization. The main theoretical ideas are sensible. However, the certification of the implemented algorithm is not established: Theorem 5.2 applies only when Algorithm 1 is run with a known benign partition, while Algorithm 2 is not shown to produce one. In addition, the reported empirical failure probability validates coverage of the finite-dataset average rather than the distributional target in Definition 3.4. These gaps are load-bearing for the paper's headline claim, but they appear addressable rather than fatal.","major_comments":[{"comment":"The lower-bound statement in Theorem 4.2 has a sign error. The theorem states that no algorithm can be (n', ε, δ)-certified whenever lim n' ε^2 / (ln(1/δ) + ln ln(1/ε)) > 0, but a lower bound should rule out sample sizes that grow slower than the benchmark rate, i.e., the limit should be 0. The proof in Appendix A indeed assumes equation (5) with the limit equal to 0, and the printed theorem is therefore inconsistent with its own proof. As stated, the theorem is false for any n' that scales faster than the benchmark rate. This must be corrected, and the statement and proof should be reconciled.","section":"Theorem 4.2 and Appendix A"},{"comment":"The main certification result does not transfer to the implemented algorithm. Theorem 5.2 guarantees that Algorithm 1 is (n', ε, δ)-certified only when it operates with a benign partition satisfying n_k/n ≥ ln(K+1) max{v_k, ε^{2/3}} for the true conditional variances v_k, and the proof explicitly says 'the known benign partition will be used as the partition subroutine.' Algorithm 2, however, produces partitions by training a 1-NN classifier on quantized loss labels and choosing K to minimize the estimated CI radius; the paper never shows that these learned partitions satisfy Definition 5.1. Since the partition is a random function of the evaluated samples and is selected to minimize an estimated width, the per-group sample sizes n_k are not controlled against the true v_k. Consequently, the certified guarantee and the claimed 20–40% savings are not established for Cer-Eval as implemented. The paper should either prove a benign-partition property for Algorithm 2 under explicit conditions, or clearly separate the certified guarantees (oracle partition) from the empirical evaluation of the heuristic.","section":"Definition 5.1, Theorem 5.2, Algorithm 2"},{"comment":"The empirical failure probability in the real-world experiments is computed as the proportion of trials where the confidence interval does not contain the model's average performance across the entire dataset, not the true expected loss R = E_{(X,Y)∼P_XY} ℓ(f(X),Y) targeted by Definition 3.4. As a result, the reported zero empirical failure probability does not validate the (n, ε, δ)-certification claim. The authors should either evaluate coverage on held-out test data drawn from P_XY, or explicitly state that the experiments validate coverage of the finite-dataset average and adjust the strength of the claim accordingly.","section":"Section 6.2 and Definition 3.4"}],"minor_comments":[{"comment":"The word 'raduis' should be 'radius'.","section":"Algorithm 1, line 14"},{"comment":"The word 'basline' should be 'baseline'.","section":"Example 3.1"},{"comment":"The proof refers to 'Theorem 5.1' and 'Theorem 4.1', but the relevant statements appear to be Theorem 5.2 and Theorem 4.2; the cross-references should be corrected.","section":"Appendix A, Proof of Theorem 5.3"},{"comment":"The phrase 'a random subset of S' is underspecified; the size of the subset and the sampling procedure should be stated for reproducibility.","section":"Algorithm 2, line 3"},{"comment":"The ablation discussion states that Algorithm 2 'does not extract enough information from the embedding vectors'; this is a relevant caveat and should be acknowledged in the main text alongside the savings claims, since it further weakens the link between the theoretical savings and the implemented method.","section":"Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The central issue is the gap between Theorem 5.2 and Algorithm 2: the certified guarantee covers only the oracle-partition case, while the implemented algorithm is a heuristic. I do not see evidence of intentional overclaiming, but the abstract and experiments present the savings as certified for Cer-Eval. The lower-bound sign error is straightforward to fix. I would encourage the authors to either add conditions under which Algorithm 2 produces a benign partition, or reframe the contributions so that the theory covers the oracle case and the experiments are explicitly heuristic evidence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take on arXiv:2505.03814. The paper is worth reading. It introduces test sample complexity for LLM evaluation, proves matching bounds (up to a typo), and proposes an adaptive partition-based algorithm that in experiments saves 20–40% of test points while keeping error rates low. That's a genuine contribution to the evaluation subfield.\n\nWhat's new: the formal notion of (n, ε, δ)-certified evaluation and test sample complexity; the upper bound with the iterated logarithm for online evaluation; the idea that partitioning the input space by loss variance can reduce required samples. The empirical work is substantial—multiple datasets, multiple models, an ablation on embedding choices.\n\nWhere it wobbles: the lower bound theorem as printed says no algorithm can be certified when lim n′ε² / ln(1/δ + ln ln(1/ε)) > 0, which contradicts the matching upper bound. The proof assumes the limit is zero (eq. 5 in Appendix A). That's a fixable typo but it's in a central theorem.\n\nMore important: the theory assumes IID samples from P_XY. The experiments sample from fixed benchmarks, likely without replacement. The guarantee in Definition 3.4 targets the true expected loss R, but the empirical failure probability is measured against the full-dataset average, not R. So the '95% confidence' is validated for a different quantity.\n\nThe biggest gap: Theorem 5.2's savings require a benign partition—one where each group has sample size at least ln(K+1) max{v_k, ε^{2/3}} times n. Algorithm 2, the 1-NN partition, is not shown to produce such partitions. The proof literally says 'the known benign partition will be used.' So the certified bound does not cover Cer-Eval as implemented. The savings are empirical, not certified.\n\nThese are addressable. The paper needs either a proof that the learned partition is benign, or a reframing of Cer-Eval as a heuristic with empirical validation, plus a corrected lower bound and an empirical protocol that checks coverage of the target quantity.\n\nCitation pattern looks fine—self-citations are for benchmark construction, not load-bearing. No circularity issue.\n\nWho's it for: anyone working on efficient LLM evaluation or adaptive confidence intervals. It deserves a serious referee; the ideas are worth engaging with. I'd want the revisions above before accepting, but the paper should not be desk-rejected.","headline":"Cer-Eval has a real idea—formal test sample complexity with an adaptive partition algorithm—but the main theorem's guarantee doesn't transfer to the implemented partition subroutine, so the central certification claim is currently unproven.","tokens_in":17385,"tokens_out":3291,"would_cite":true,"duration_ms":29551,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L10","62G15","68T50"],"pacs":[],"model":"deepseek-v4-flash","headline":"Cer-Eval is an online evaluation algorithm that certifies LLM performance with confidence intervals while using 20-40% fewer test points than full-benchmark evaluation.","keywords":["LLM evaluation","test sample complexity","adaptive online evaluation","confidence intervals","sequential analysis","variance reduction","benchmark efficiency","certified evaluation"],"falsifier":"Compute, on a real benchmark, the empirical per-group sample fractions n_k/n and variances v_k at Cer-Eval's termination; if for some group n_k/n < ln(K+1) max{v_k, $epsilon^{{2/3}}$} while the algorithm still claims certification, then the condition behind the sample-savings theorem is violated and the guarantee does not follow from the paper's theory. A direct experiment would run Cer-Eval on a dataset whose loss is determined by a feature absent from the embedding vectors and check whether the reported confidence interval covers the full-dataset average at the claimed 1-delta rate.","tokens_in":16343,"feed_emoji":"📉","tokens_out":6792,"duration_ms":62130,"temperature":0.7,"pith_summary":"The paper aims to replace the standard practice of evaluating a large language model by averaging over an entire benchmark with a sequential, adaptive process that stops as soon as the estimate is within a user-chosen error epsilon with confidence 1-delta. It introduces test sample complexity, the minimum number of test points any certified evaluator needs, and gives matching upper and lower bounds under a bounded-loss assumption. It then shows that partitioning the test data into low-variance groups can shrink the required sample size, and builds the Cer-Eval algorithm that learns such partitions adaptively via 1-nearest-neighbor clustering in embedding space. On MMLU, AlpacaEval, and MATH with models including GPT-4o, Cer-Eval reports comparable estimation error while using roughly 60-80% of the test data (20-40% savings) at the 95% confidence level.","feed_headline":"LLM evaluation needs 20-40% fewer test points","feed_subtitle":"Cer-Eval gives confidence intervals at 95% confidence while skipping up to 40% of benchmark data.","key_machinery":"The load-bearing object is a confidence-interval radius per partition group, built from an adaptive Bernstein-type inequality. For each group k, Cer-Eval computes eta_k = $\\sqrt$((2 ln(log(n_k)+1)+ln(16K/delta))/n_k) and epsilon_k = 2 $eta_k^{2}$/3 + 2 $\\sqrt$((v_k + eta_k + $eta_k^{2}$) $eta_k^{2}$); termination occurs when the weighted average epsilon_hat = sum_j N_j epsilon_j / N falls below the user's epsilon. The 1-nearest-neighbor partition subroutine chooses, among candidate labelings by discretized loss values, the one that minimizes epsilon_hat. This machinery turns variance reduction into sample savings: a benign partition with small within-group variances v_k makes each epsilon_k shrink faster, so the algorithm certifies accuracy with fewer evaluated points.","core_discovery":"The central claim is that certifiable LLM evaluation need not evaluate all test points: an (n, epsilon, delta)-certified online algorithm can stop early and still guarantee that its reported interval contains the true error with probability at least 1-delta. The paper proves that with only a bounded-loss assumption the test sample complexity is Theta($epsilon^{{-2}}$(ln(1/delta)+ln ln(1/epsilon))), and that with a benign partition that concentrates probability mass on low-variance regions the required sample count drops by a factor rho = O(ln(K+1) sum_k max{v_k, $epsilon^{{2/3}}$}). Cer-Eval implements this idea by repeatedly partitioning the embedding space with 1-nearest-neighbor, estimating per-group mean and variance, and sampling from the group that reduces the confidence-interval radius most. In experiments the algorithm matches static full-dataset evaluation error with an empirical failure probability of zero while saving 20-40% of test points on MMLU, AlpacaEval, and MATH for GPT-4o and similar models at 95% confidence.","pith_inferences":["The paper does not show that its 1-nearest-neighbor partition always yields benign partitions; if it does not, the stated savings on a particular benchmark could fall below 20% even though the confidence guarantee may still hold empirically.","If better embeddings or task-specific attributes make learned partitions closer to benign, the observed savings could exceed 40%; the paper's own ablation points to partition quality, not the embedding model, as the limiting factor.","Applying the same certified stopping idea to model ranking could stop as soon as the confidence interval separates two models, using an error level tied to their performance gap.","Instrumenting Cer-Eval to report per-group n_k, v_k, and the benign-partition condition at termination would turn the theoretical assumption into a per-run diagnostic."],"forward_implications":["Users no longer need to evaluate an entire benchmark: with Cer-Eval they can stop once the confidence interval radius reaches a user-set epsilon, and the output carries a 1-delta coverage guarantee.","If the partition-based savings hold, benchmark curators can use test sample complexity to decide whether a dataset is large enough for a target error, or to tell users more data are needed (the paper reports AlpacaEval needs more points at small epsilon).","The apparent scaling law between model size and required test points is explained by accuracy near 0.5: as models improve beyond 50% accuracy, needed test points for fixed error and confidence need not grow with model size.","The framework replaces static averages with a sequential process that adapts when epsilon is implicit, such as deciding whether accuracy exceeds 0.5, or changes during evaluation."],"supporting_citations":[{"why":"Supplies the adaptive Hoeffding inequality that bounds the probability of any wrong decision across the sequential stopping times.","marker":"[31]"},{"why":"Supplies the maximal Bernstein inequality used in the adaptive Bernstein lemma that gives each group's confidence-interval radius.","marker":"[20]"},{"why":"Provides the classical Hoeffding and Bernstein concentration inequalities that anchor the sequential bounds.","marker":"[2]"},{"why":"Gives the lower bound on expected sample size in sequential testing used to prove the matching lower bound on test sample complexity.","marker":"[11]"},{"why":"Provides the lower bound for any delta-certified algorithm with known epsilon, used in the test-sample-complexity lower bound.","marker":"[24]"},{"why":"The MMLU dataset used in the real-world evaluation experiments.","marker":"[14]"},{"why":"The AlpacaEval dataset used in the real-world evaluation experiments.","marker":"[10]"},{"why":"The MATH dataset used in the real-world evaluation experiments.","marker":"[15]"}],"fun_headline_variants":["LLM eval certifiably skips 20-40% of test points","Certifiable evaluation cuts LLM test data by up to 40%","Proven savings: 20-40% fewer LLM test points","LLM evaluation with 95% confidence uses 40% less data","Certify LLM accuracy with fewer test samples"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The 20-40% savings guarantee rests on the assumption that the algorithm's learned partition is benign—each group must contain enough points relative to its true loss variance—and the paper does not prove that its 1-nearest-neighbor partition subroutine produces such a partition.","fun_headline_variants_meta":{"raw":{"variants":["LLM eval certifiably skips 20-40% of test points","Certifiable evaluation cuts LLM test data by up to 40%","Proven savings: 20-40% fewer LLM test points","LLM evaluation with 95% confidence uses 40% less data","Certify LLM accuracy with fewer test samples"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000618,"raw_usage":{"total_tokens":2872,"prompt_tokens":953,"completion_tokens":1919,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":1826}},"tokens_in":569,"tokens_out":1919,"duration_ms":11058,"temperature":1.0,"reasoning_tokens":1826,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:19:41.131639+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, on a real benchmark, the empirical per-group sample fractions n_k/n and variances v_k at Cer-Eval's termination; if for some group n_k/n < ln(K+1) max{v_k, $epsilon^{{2/3}}$} while the algorithm still claims certification, then the condition behind the sample-savings theorem is violated and the guarantee does not follow from the paper's theory. A direct experiment would run Cer-Eval on a dataset whose loss is determined by a feature absent from the embedding vectors and check whether the reported confidence interval covers the full-dataset average at the claimed 1-delta rate.","supporting_citations":[{"cited_title":"Adaptive concentration inequalities for sequential decision problems","cited_arxiv_id":null,"evidence_quote":"Supplies the adaptive Hoeffding inequality that bounds the probability of any wrong decision across the sequential stopping times."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the maximal Bernstein inequality used in the adaptive Bernstein lemma that gives each group's confidence-interval radius."},{"cited_title":"Asymptotic behavior of expected sample size in certain one sided tests","cited_arxiv_id":null,"evidence_quote":"Gives the lower bound on expected sample size in sequential testing used to prove the matching lower bound on test sample complexity."},{"cited_title":"The sample complexity of exploration in the multi-armed bandit problem","cited_arxiv_id":null,"evidence_quote":"Provides the lower bound for any delta-certified algorithm with known epsilon, used in the test-sample-complexity lower bound."}],"review_version":1}