Technical Summary: Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization

Problem Formulation

Selecting the best Large Language Model (LLM) for a specific task using fixed benchmarks is often prohibitively expensive. Exhaustive evaluation requires running every model on every example, a process that can cost tens of thousands of dollars and requires significant computational resources, particularly when stochastic agents require repeated rollouts for reliable estimates.

To mitigate this, Multi-Armed Bandit (MAB) algorithms, such as UCB-E, have been proposed to adaptively allocate evaluation budgets, focusing resources on promising candidates. However, further savings can be achieved by predicting model scores using the structure of the model-example score matrix. Since models often exhibit similar performance profiles across examples, and examples often admit similar scores across models, the score matrix is hypothesized to be well-approximated by a low-rank matrix.

The core challenge addressed in this work is that these low-rank predictions are not ground truth; they can be biased. Naively incorporating these predictions into MAB algorithms can lead to incorrect identification of the best model. Furthermore, existing statistical guarantees for doubly robust estimators often assume infinite populations or stationary data distributions, which do not hold in this setting where:

1. Examples are sampled without replacement from a fixed, finite dataset.
2. Predictions are generated by repeatedly refitting an online low-rank model to the same adaptively observed score matrix, creating strong cross-arm dependence.

The goal is to develop a framework that leverages these cheap, imperfect predictions to reduce the number of LLM calls while maintaining statistical validity (unbiased estimates and valid confidence intervals) in a finite-sample, adaptive setting.

Methodology: PULSE

The authors propose PULSE (Prediction-Powered Unbiased Low-Rank Sequential Evaluation), a sequential framework that combines adaptive sampling with low-rank score prediction. The method operates in two alternating stages:

1. Low-Rank Factorization (Prediction)

The algorithm models the probability that model $i$ answers question $j$ correctly using a low-rank logistic model:
$$\hat{S}_{i,j} = \sigma(u_i^\top v_j)$$
where $u_i$ and $v_j$ are learned latent representations. The model is trained by minimizing the Binary Cross-Entropy (BCE) loss on observed entries with $L_2$ regularization to prevent overfitting. Crucially, the question representations ($V$) are initialized from a training split and kept frozen, while model representations ($U$) are updated online as new scores are observed.

2. Doubly Robust Estimation (Unbiased Evaluation)

To ensure statistical validity despite biased predictions, PULSE employs a doubly robust estimator for each model's mean accuracy $\mu_i$. At any step $t$, for a selected model $i$, the estimator $\hat{\theta}_i^t$ is constructed as:
$$\hat{\theta}_i^t = \frac{1}{n} \left[ \sum_{j \in O_i^{t-1}} S_{i,j} + \sum_{j \in U_i^t} \lambda_i^t \hat{S}_{i,j}^t + \frac{S_{i,j_t} - \lambda_i^t \hat{S}_{i,j_t}^t}{\pi_i^t} \right]$$
Where:

• $O_i^{t-1}$: Set of previously observed examples for model $i$.
• $U_i^t$: Set of unobserved examples.
• $\hat{S}_{i,j}^t$: Predicted score from the low-rank model.
• $\lambda_i^t \in [0, 1]$: A tunable weight that balances the prediction with the observation.
• $\pi_i^t$: The probability of sampling the specific example $j_t$ (inverse probability weighting).
• The final term is an inverse-probability residual correction that removes bias introduced by the potentially inaccurate predictions.

Key Theoretical Properties:

• Conditional Unbiasedness: The estimator is proven to be conditionally unbiased ($E[\hat{\theta}_i^t | \mathcal{F}_{t-1}] = \mu_i$) provided the weights and predictions are measurable with respect to the history $\mathcal{F}_{t-1}$.
• Variance Reduction: The variance of the estimator depends on the correlation between true and predicted scores. If predictions are informative, the variance is reduced compared to using observations alone.
• Finite-Sample Confidence Intervals (CIs): Using martingale concentration inequalities (specifically Freedman's inequality), the authors derive valid finite-sample CIs. The width of these intervals is driven by the conditional variance of the residual correction term, which can be minimized by tuning $\lambda_i^t$.
• Adaptive Tuning: Since the optimal $\lambda_i^t$ depends on unknown future scores, the algorithm uses a "predictable plug-in" approximation based on past residuals to estimate the optimal weight dynamically.

3. Best-Model Identification

PULSE integrates these estimators into a UCB-E style bandit loop. At each step, it selects the model with the highest upper confidence bound, evaluates it on a batch of new examples, updates the low-rank factorization, and refits the estimator. The algorithm guarantees a high probability of identifying the unique best model within a finite budget.

Key Contributions

1. Unbiased Estimator with Low-Rank Predictions: The authors derive a doubly robust estimator that leverages low-rank factorization predictions to reduce variance while guaranteeing unbiasedness, even when predictions are imperfect.
2. Finite-Sample Validity in Adaptive Settings: They establish finite-sample confidence intervals and success guarantees for best-model identification in a setting characterized by sampling without replacement and time-varying, adaptively generated predictions. This extends existing doubly robust theory to the specific constraints of LLM benchmarking.
3. Empirical Efficiency: The proposed PULSE algorithm is shown to significantly reduce the number of required LLM calls compared to standard UCB-E, while maintaining high identification accuracy.

Experimental Results

The authors evaluated PULSE on real-world benchmarks involving 2,200 models across six datasets (including MMLU-Pro, BBH, GPQA, MATH, etc.).

• Performance vs. UCB-E: PULSE consistently outperformed the standard UCB-E algorithm (which uses only observed scores) across all difficulty levels (defined by the accuracy gap $\Delta_{top2}$ between the top two models).
• Cost Savings: To achieve 95% identification accuracy, PULSE reduced the number of required LLM calls by up to 46% compared to UCB-E.
• Importance of Bias Correction: A "Naive-Pooling" baseline, which used predicted scores directly without bias correction, performed significantly worse than both PULSE and UCB-E. This confirms that naively incorporating biased predictions is detrimental and that the proposed debiasing mechanism is essential.
• Computational Overhead: The computational cost of running PULSE (approx. 60 seconds for a 540k budget) is negligible compared to the cost of the LLM evaluations saved.

Significance and Claims

The paper claims that PULSE provides a principled framework for accelerating LLM evaluation. Its primary significance lies in bridging the gap between the efficiency of using cheap predictions and the statistical rigor required for reliable model selection.

The authors emphasize that their approach allows practitioners to:

• Save Compute and Cost: Significantly reduce the budget required for benchmarking without sacrificing the reliability of the "best model" selection.
• Maintain Validity: Ensure that the identification of the best model is statistically sound, with valid confidence intervals, even in complex, non-i.i.d. settings involving adaptive sampling and imperfect predictions.

The work does not claim to solve all LLM evaluation challenges but specifically targets the trade-off between evaluation cost and statistical validity in best-model identification. The authors note limitations, such as the dependence on the quality of the low-rank factorization and the current focus on binary scoring functions, suggesting future work could explore richer contextual information and non-binary scores.