📊 statistics

Efficient Sequential Evaluation of Large Language Models

This paper proposes a framework for the efficient sequential evaluation of large language models by constructing confidence sequences via test supermartingales and designing adaptive querying rules to minimize evaluation costs, while revealing that simple uniform sampling can sometimes outperform more complex adaptive strategies due to prediction mismatches and distribution spikiness.

Original authors: Chia-Yu Hsu, Shubhanshu Shekhar

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Chia-Yu Hsu, Shubhanshu Shekhar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a judge trying to figure out how good a new, super-smart robot is at answering questions. You have a giant test bank with thousands of questions, but checking every single one takes forever and costs a fortune. So, you decide to ask just a few questions to get a good idea of the robot's overall score. The tricky part is knowing when to stop. If you stop too early, your guess might be wild; if you wait too long, you've wasted time. In the world of statistics, there's a special tool called a "confidence sequence" that acts like a shrinking safety net. Unlike a regular net that only works if you promise to stop at a specific time, this safety net stays valid no matter when you decide to stop looking. It guarantees that the robot's true score is always inside the net, even if you change your mind about when to stop based on what you've seen so far.

Now, imagine you have a crystal ball (or in this case, a history book) showing how previous robots answered these same questions. You can use that history to predict which questions the new robot will find easy or hard. The big question is: How do you use that crystal ball to pick the best questions to ask next, so your safety net shrinks as fast as possible? This is the puzzle tackled by Chia-Yu Hsu and Shubhanshu Shekhar in their paper, "Efficient Sequential Evaluation of Large Language Models." They are trying to figure out the most efficient way to test a new Large Language Model (LLM) by asking fewer questions while still being mathematically sure of the result.

The authors set up a game where they try to shrink that safety net (the confidence sequence) as quickly as possible. They explore two main strategies for building this net. The first is like a "Reverse Information Projection" (RIPr), which is a fancy way of saying they find the "worst-case" scenario that still fits the data and measure how far the new robot is from that worst case. The second strategy is "testing-by-betting," where they imagine placing a bet on whether the robot is good or bad, and they win money (or "wealth") if their prediction is right, which helps shrink the net.

To make the process faster, they propose a "growth-oriented" rule. This is like a detective who, instead of asking random questions, always picks the next question that is most likely to give them a big clue to narrow down the suspect's identity. They calculate which question will make their safety net shrink the most in the very next step. However, they run into a snag: their crystal ball (the prediction from historical data) isn't perfect. If the prediction is wrong, the detective might chase the wrong clues, and the net stops shrinking as fast as it should. They find that two things slow the net down: when the predictions are way off (mismatch) and when the detective only asks questions that are very similar to each other (spikiness), ignoring the rest of the test bank.

To fix this, the authors try mixing their "smart detective" strategy with two other approaches: one that focuses on fixing the crystal ball's predictions, and another that just asks questions completely at random (uniform sampling). They run simulations with different types of robot behaviors and test banks to see which mix works best. Interestingly, their experiments suggest that there isn't one single "magic" strategy that wins every time. Sometimes, the most complicated, adaptive detective strategy works great, but other times, the simplest strategy—just picking questions at random—performs just as well, or even better, especially when the predictions are shaky. They conclude that while smart, adaptive rules are powerful, the humble, random approach is a surprisingly strong competitor that shouldn't be ignored.

Problem Statement
The paper addresses the challenge of efficiently evaluating a newly developed Large Language Model (LLM) on a fixed benchmark consisting of $N$ questions. The goal is to estimate the model's average correctness rate (capability) with acceptable uncertainty while minimizing the number of queries (questions answered). Unlike standard fixed-time confidence intervals, the authors aim to construct a Confidence Sequence (CS)—a sequence of confidence sets that maintains valid coverage uniformly over time (anytime-valid). This allows the evaluator to stop querying as soon as the estimate is sufficiently precise, adapting the stopping time to the strength of the evidence. The setting leverages historical performance data from previous LLMs on the same benchmark to predict the likelihood of the new model answering each question correctly, thereby guiding an active, adaptive querying strategy.

Methodology
The authors propose a framework that jointly designs an adaptive querying rule and a CS construction based on test supermartingales.

CS Construction via Test Supermartingales:
The authors invert a family of test supermartingales to form the CS. For a candidate value $m$ (a potential average correctness rate), a test supermartingale accumulates evidence against $m$ if $m \neq \theta^*$ (the true average). The CS at time $t$ consists of all $m$ whose supermartingale values have not crossed a rejection threshold ( $1/\alpha$ ).
Two specific constructions for the test supermartingales are investigated:
- Reverse Information Projection (RIPr): This approach identifies the "least favorable" distribution within the null class (distributions with mean $m$ ) that is closest to the true distribution in Kullback-Leibler (KL) divergence. The likelihood ratio between the true distribution and this projection serves as the e-value. In an oracle setting (where true correctness probabilities are known), this method is shown to be growth-optimal.
- Testing-by-Betting: This approach frames the problem as a betting game where a bet is placed on an estimator of the target parameter. The wealth process grows if the candidate $m$ is incorrect. The authors propose a computationally lighter variant using a quadratic lower bound on the log-wealth growth.
Active Querying Rules:
To shrink the CS width rapidly, the authors design querying rules that maximize the expected log-increment (Kelly criterion) of the test supermartingale.
- Oracle Setting: Assuming known true probabilities, they propose a growth-oriented maxmin criterion. This rule selects the query distribution that maximizes the worst-case one-step expected log-increment over the current CS endpoints (the lower and upper bounds of the interval).
- Practical Setting: Since true probabilities are unknown, the authors use predictions derived from a Bayesian factor model fitted on historical data. They replace the true parameters with these predictions (plug-in approach) in both the e-value construction and the querying rule.
Mixture Querying Strategies:
Recognizing that pure growth-oriented querying can be sensitive to prediction errors and the "spikiness" (low minimum probability) of the query distribution, the authors propose mixture querying rules. These combine:
- Growth-oriented sampling (to shrink the CS).
- Prediction refinement (to improve the accuracy of the plug-in predictions).
- Uniform exploration (to ensure a lower bound on query probabilities and mitigate spikiness).
  These mixtures can be time-scheduled or data-dependent (adapting weights based on prediction uncertainty and stability).

Key Contributions

Oracle Optimality: In an oracle setting, the authors demonstrate that the RIPr-based construction achieves oracle growth optimality among valid conditional e-values. They also show that for the testing-by-betting approach, a specific growth-oriented sampling rule coincides with the variance-reduction sampling rule from prior work.
Theoretical Analysis of Shrinkage: The paper analyzes the shrinkage behavior of the resulting CSs in the practical (plug-in) setting. It identifies two key factors that slow down CS shrinkage:
1. Accumulated Prediction Mismatch: Quantified by a KL-divergence term for RIPr and a Mean Squared Error (MSE) term for testing-by-betting. The analysis suggests RIPr is more sensitive to prediction mismatch than the betting approach.
2. Spikiness of the Querying Distribution: A low lower bound on query probabilities ( $h$ ) significantly hinders the growth of the betting-based CS by restricting the valid betting range, whereas RIPr is less directly affected by this specific constraint.
Empirical Findings: Through experiments on synthetic datasets with varying capability regimes (e.g., models similar to historical data vs. out-of-family models), the authors find:
- There is no universally best querying rule; performance depends on the dataset structure and the quality of predictions.
- The testing-by-betting approach is generally more robust to prediction mismatch than RIPr.
- Surprisingly, the simplest rule, uniform sampling, often performs competitively against more complex adaptive rules, particularly when prediction refinement is difficult or the model is significantly different from historical data.

Significance and Claims
The paper claims to provide a principled method for sequential LLM evaluation with anytime-valid uncertainty guarantees. By leveraging historical data, it aims to reduce the cost of evaluation (number of queries) while maintaining rigorous statistical validity.

The authors modestly frame their theoretical bounds as "diagnostic" rather than sharp characterizations of optimal design, noting that they capture the effects of prediction mismatch and minimum query probabilities but may not fully reflect finer properties of the sampling rules. They emphasize that their work highlights the trade-offs between growth-oriented querying, prediction refinement, and uniform exploration. The observation that uniform sampling can outperform adaptive rules in certain regimes suggests that the complexity of adaptive querying may not always yield proportional benefits, a finding that challenges the assumption that adaptivity is always superior in this context.

The work positions itself as a sequential counterpart to prior work on prediction-powered inference, extending the scope to active querying from a fixed benchmark rather than passive sampling from a stream. Future work is suggested to include developing more effective querying rules (potentially via reinforcement learning) and exploring alternative prediction methods beyond the Bayesian factor model.

More like this