Technical Summary: CELEUS

Problem Statement

The evaluation of Large Language Models (LLMs) increasingly relies on sequential curation of samples to estimate performance metrics. However, standard evaluation practices face a critical gap between theoretical rigor and practical application. Existing methods that update confidence intervals (CIs) sequentially often fail to be anytime-valid. This means that when an evaluator repeatedly updates CIs and uses them to decide when to stop (e.g., when the interval width reaches a target precision), the claimed coverage probability (e.g., 95%) may fail due to "double dipping"—using the same data to both select the evaluation strategy and quantify uncertainty. Furthermore, simply collecting more samples does not certify that the estimate is precise enough for decision-making, leaving no statistically grounded stopping criterion.

Current approaches like Cer-Eval attempt to address this via adaptive partitioning but rely on fixed-partition assumptions that do not hold when partitions are learned adaptively from the data, leading to potential coverage loss. Additionally, efficient evaluation is hindered by the high cost of obtaining ground-truth labels or human judgments, necessitating strategies that minimize the number of evaluated samples while maintaining statistical validity.

Methodology

The paper proposes CELEUS (Certifiable and Efficient LLM Evaluation via E-Processes), a framework that bridges the gap between theoretical guarantees and practical efficiency by leveraging E-processes.

Core Framework

1. Anytime-Valid Confidence Intervals: CELEUS constructs CIs using E-processes, which provide guarantees that hold at any stopping time. Unlike traditional methods, E-processes rely only on the assumption that evaluation scores are bounded (ensured via normalization or clipping), making them robust to adaptive stopping rules.
2. Sequential Procedure: The method operates on a finite data pool $D_N$. At each round $t$, it selects an unevaluated sample, observes its true risk, and updates the CI. The process stops when the CI width reaches a target precision $\epsilon$.

Key Technical Components

To ensure efficiency and validity under non-uniform sampling, CELEUS constructs inferential signals using two primary ingredients:

• Uncertainty-Guided Sampling: Instead of uniform random sampling, CELEUS prioritizes samples that are expected to reduce estimation variance. The sampling probability $q_t$ is designed to be proportional to the magnitude of the discrepancy between the observed risk and a surrogate score. This aligns with the variance-optimal sampling rule derived theoretically.
• Surrogate-Assisted Approximations: For unevaluated samples, CELEUS utilizes scores from a smaller, pre-trained surrogate model (e.g., a 7–8B model) to approximate the true risk. This allows the framework to extract information from the entire pool without evaluating every sample with the target model.

Signal Construction

The framework constructs a per-round signal $\hat{S}_t$ that is conditionally unbiased for the finite-pool risk $R_N$. The signal combines:

1. A surrogate-completed estimate of the pool risk (using observed risks for evaluated samples and surrogate scores for the rest).
2. An inverse-probability-weighted correction for the newly evaluated sample's residual (the difference between its true risk and surrogate score).

This conditional unbiasedness is the central mechanism enabling the construction of valid E-processes. The framework then lifts the CI from the finite-pool risk $R_N$ to the population risk $R$ using a Hoeffding-style correction, which depends on the full pool size $N$.

Theoretical Guarantees

• Anytime-Valid Coverage: The resulting CIs cover the true population risk with probability at least $1-\alpha$ at any stopping time.
• Shrinkage Rate: The width of the CIs shrinks at a near-parametric rate of $O(\sqrt{\log t \log \log t / t})$, up to logarithmic factors.
• Variance Reduction: The paper proves that the proposed uncertainty-guided sampling and surrogate assistance reduce the conditional variance of the signals, directly accelerating the shrinkage of the confidence intervals.

Key Contributions

1. Bridging the Rigor-Practice Gap: CELEUS provides the first framework for LLM evaluation that is both statistically rigorous (anytime-valid) and practically efficient, resolving the coverage failures of existing adaptive methods like Cer-Eval.
2. Novel Signal Construction: The paper introduces a conditionally unbiased signal that integrates surrogate-assisted approximations with inverse-probability weighting, enabling valid E-process construction under non-uniform, adaptive sampling.
3. Theoretical Analysis: The authors provide proofs for the unbiasedness of the estimator, the validity of the anytime-valid CIs, and the variance-optimal properties of their sampling strategy. They characterize the convergence rate of the CI width.
4. Empirical Validation: Extensive experiments demonstrate that CELEUS achieves target precision using 54–62% fewer evaluated samples than baselines (such as uniform sampling with E-processes) while preserving nominal coverage. The use of small surrogate models (7–8B parameters) without task-specific fine-tuning further improves efficiency by an additional 10–23% compared to the non-surrogate variant.

Results

Experiments were conducted on three benchmarks (SST-2, AG News, MMLU) with various target models (e.g., Llama-3-70B, DeepSeek-67B, Mixtral-8×7B) and surrogate-target pairs.

• Coverage: In diagnostic settings where Cer-Eval failed to maintain coverage (miscoverage rate of 16.1% vs. nominal 5%), CELEUS and other E-process-based methods maintained miscoverage rates below the nominal level (0.021–0.030).
• Efficiency: CELEUS reached the target precision ($\epsilon=0.05$) with significantly fewer labels. For instance, on MMLU, it required 3,242 samples compared to 8,144 for the baseline (EVALUE), a 60% reduction.
• Surrogate Impact: The surrogate-assisted variant consistently outperformed the version without surrogates, demonstrating that leveraging pre-trained smaller models effectively reduces the variance of the estimation signal.

Significance and Claims

The paper claims that CELEUS offers a statistically grounded criterion for deciding when enough samples have been evaluated, moving beyond simple point estimates to certified confidence intervals. By ensuring anytime-validity, it allows evaluators to monitor progress and stop early without inflating Type I error rates.

The authors emphasize that their method is particularly valuable in scenarios where evaluation relies on expensive human annotation or strong LLM judges, as it drastically reduces the number of such evaluations required. They note that while the method addresses statistical uncertainty in evaluation, it does not resolve other deployment risks (e.g., safety, bias) nor does it guarantee that the benchmark itself is representative of real-world conditions. The computational cost of surrogate scoring is acknowledged but shown to be negligible compared to the savings from reducing the number of target-model evaluations.

Future work suggested by the authors includes extending the framework to distribution-shift-aware evaluation scenarios.