CELEUS: Certifiable and Efficient LLM Evaluation via E-Processes

• URL: http://arxiv.org/abs/2606.20820v1
• Date: Thu, 18 Jun 2026 18:07:42 GMT
• Title: CELEUS: Certifiable and Efficient LLM Evaluation via E-Processes
• Abstract summary: We propose a Certifiable framework for Efficient LLM evaluation, which leverages E-processes to build anytime-valid CIs.<n>We prove that such signals remain unbiased for the evaluation score conditional on the past, enabling statistically-grounded and anytime-valid CIs.<n>Experiments show that Celeus reaches the target precision using 54-62% fewer evaluated samples than baselines, while preserving anytime-valid coverage.
• Score: 18.54239835812274
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can we trust evaluation scores to capture an LLM's true real-world performance? Certifiable evaluation answers this question by providing guarantee for LLM evaluation. In particular, existing methods sequentially curate evaluation samples and keep updating confidence intervals (CIs) that cover the true performance with high probability (e.g., 95%) until some conditions are satisfied, e.g., the CI width reaches a target precision. However, existing methods are not generally anytime-valid: the claimed coverage (e.g., 95%) may fail when CIs are repeatedly updated and used to decide when to stop, leaving a gap between theoretical rigor and practice. This paper bridges this gap by proposing Celeus, a Certifiable framework for Efficient LLM evaluation, which leverages E-processes to build anytime-valid CIs. Concretely, we propose signals that combine two ingredients: (i) Uncertainty-guided sampling to select informative samples for evaluation, and (ii) Surrogate-assisted approximations for unevaluated samples. We prove that such signals remain unbiased for the evaluation score conditional on the past, enabling statistically-grounded and anytime-valid $e$-process CIs. More importantly, the two ingredients reduce estimation variance and help reach the target precision with fewer evaluated samples. We also prove that CIs obtained by Celeus can shrink at a near-parametric rate up to logarithmic factors and analyze the oracle variance-optimal sampling rule that motivates the empirical uncertainty-guided one. Experiments show that Celeus reaches the target precision using 54-62% fewer evaluated samples than baselines, while preserving anytime-valid coverage.

Related papers

• Knowing When to Stop: Bayesian Optimal Stopping for LLM Evaluations [0.0]
  optstop treats evaluation as a sequential measurement problem.<n>It keeps every benchmark item eligible for sampling, without requiring a calibrated item bank.<n>It runs live or retrospectively, and includes a safeguard that samples more cautiously as measured performance approaches zero.
  arXiv  Detail & Related papers  (2026-08-14T16:06:41Z)
• LLM-as-a-Verifier: A General-Purpose Verification Framework [74.40111651545979]
  We introduce LLM-as-a-Verifier, a general-purpose verification framework.<n>It provides fine-grained feedback for agentic tasks without requiring additional training.<n>It achieves state-of-the-art performance on several benchmarks.
  arXiv  Detail & Related papers  (2026-07-06T17:59:35Z)
• Crossing the Validation Crisis: Cross-Validation Reduces Benchmarking Variance Surprisingly Well [15.198198886832595]
  We show that cross-validation improves markedly confidence when evaluating and comparing learning algorithm performances.<n>We introduce the concept of sample gain, which quantifies the virtual data augmentation achieved by using multiple cross-validation splits.
  arXiv  Detail & Related papers  (2026-06-10T18:03:19Z)
• A Semantic-Sampling Framework for Evaluating Calibration in Open-Ended Question Answering [19.55210880950831]
  Expected measures whether a model's predicted confidence aligns with its empirical accuracy, and is central to the reliable deployment of large language models (LLMs)<n>We introduce Sem-ECE, a calibration evaluation framework for open-ended question answering (QA)<n>We study two estimators within framework: Sem$$-ECE, the same-sample self-consistency score, and Sem$$-ECE, a held-out variant that separates answer selection from confidence evaluation.
  arXiv  Detail & Related papers  (2026-05-08T19:53:49Z)
• Confident Rankings with Fewer Items: Adaptive LLM Evaluation with Continuous Scores [25.638175689769934]
  We present a principled extension of IRT-based adaptive testing to continuous bounded scores (ROUGE, BLEU, LLM-as-a-Judge)<n>We introduce an uncertainty aware ranker with adaptive stopping criteria that achieves reliable model ranking while testing as few items as possible.<n>Our method uses 2% of the items while improving ranking correlation by 0.12 over random sampling, with 95% accuracy on confident predictions.
  arXiv  Detail & Related papers  (2026-01-20T11:59:13Z)
• Rethinking LLM Evaluation: Can We Evaluate LLMs with 200x Less Data? [82.09573568241724]
  EssenceBench is a coarse-to-fine framework utilizing an iterative Genetic Algorithm (GA)<n>Our approach yields superior compression results with lower reconstruction error and markedly higher efficiency.<n>On the HellaSwag benchmark (10K samples), our method preserves the ranking of all models shifting within 5% using 25x fewer samples, and achieves 95% ranking preservation shifting within 5% using only 200x fewer samples.
  arXiv  Detail & Related papers  (2025-10-12T05:38:10Z)
• Importance Sampling is All You Need: Predict LLM's performance on new benchmark by reusing existing benchmark [38.42021928363628]
  Existing benchmarks face two major challenges: (1) the escalating cost of constructing high-quality test suites and reference solutions, and (2) the increasing risk of data contamination.<n>We propose BIS, a prompt-centric evaluation framework that enables ground-truth-free prediction of LLM performance on code generation tasks.<n>Our framework achieves an average absolute prediction error of 1.1% for code correctness scores, with best- and worst-case errors of 0.3% and 1.9%, respectively.
  arXiv  Detail & Related papers  (2025-08-02T05:34:05Z)
• A Sample Efficient Conditional Independence Test in the Presence of Discretization [54.047334792855345]
  Conditional Independence (CI) tests directly to discretized data can lead to incorrect conclusions.<n>Recent advancements have sought to infer the correct CI relationship between the latent variables through binarizing observed data.<n>Motivated by this, this paper introduces a sample-efficient CI test that does not rely on the binarization process.
  arXiv  Detail & Related papers  (2025-06-10T12:41:26Z)
• Cer-Eval: Certifiable and Cost-Efficient Evaluation Framework for LLMs [29.764833226591012]
  This paper introduces a certifiable and cost-efficient evaluation framework for large language models (LLMs)<n>We use test sample complexity'' to quantify the number of test points needed for a certifiable evaluation and derive tight bounds on test sample complexity.<n>Based on the developed theory, we develop a partition-based algorithm, named Cer-Eval, that adaptively selects test points to minimize the cost of LLM evaluation.
  arXiv  Detail & Related papers  (2025-05-02T17:05:01Z)
• On Speeding Up Language Model Evaluation [48.51924035873411]
  We propose an $textitadaptive$ approach to explore this space.<n>We lean on multi-armed bandits to sequentially identify the next (method, validation sample)-pair to evaluate.<n>We show that it can identify the top-performing method using only 5-15% of the typical resources.
  arXiv  Detail & Related papers  (2024-07-08T17:48:42Z)
• Self-Evaluation Improves Selective Generation in Large Language Models [54.003992911447696]
  We reformulate open-ended generation tasks into token-level prediction tasks. We instruct an LLM to self-evaluate its answers. We benchmark a range of scoring methods based on self-evaluation.
  arXiv  Detail & Related papers  (2023-12-14T19:09:22Z)
• LLMs as Factual Reasoners: Insights from Existing Benchmarks and Beyond [135.8013388183257]
  We propose a new protocol for inconsistency detection benchmark creation and implement it in a 10-domain benchmark called SummEdits. Most LLMs struggle on SummEdits, with performance close to random chance. The best-performing model, GPT-4, is still 8% below estimated human performance.
  arXiv  Detail & Related papers  (2023-05-23T21:50:06Z)
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient [62.24615324523435]
  This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candidate features, our result sheds light on the fact that sparsity-aware methods can make batch RL more sample efficient.
  arXiv  Detail & Related papers  (2020-11-08T16:48:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.