📊 statistics

Instance-Optimal Estimation with Multiple LLM Judges on a Budget

This paper addresses the problem of cost-effective LLM evaluation by formulating budgeted heteroskedastic multi-judge estimation, proposing an adaptive algorithm (EST-IVWE) that achieves instance-optimal score estimation by leveraging optimistically biased variance estimates, and establishing a matching local minimax lower bound to prove its theoretical optimality.

Original authors: Junghyun Lee, Sanghwa Kim, Yassir Jedra, Alexandre Proutière, Se-Young Yun

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Junghyun Lee, Sanghwa Kim, Yassir Jedra, Alexandre Proutière, Se-Young Yun

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 manager trying to grade the performance of 1,000 different employees (the "prompts" or questions). You have a limited budget of money to spend on getting these grades.

To do this, you hire a team of 10 different "judges" (these are Large Language Models, or LLMs). Here is the catch:

They cost different amounts: Some judges are cheap (like a junior intern), while others are expensive (like a senior expert).
They are unreliable in different ways: Some judges are very consistent but slow/expensive. Others are fast/cheap but make wild, inconsistent guesses.
The questions are different: Some questions are easy to answer (low variance), while others are tricky and confusing (high variance).

The big question the paper asks is: How do you spend your money to get the most accurate overall grades?

The Old Way: The "Fair Share" Mistake

Most people would just say, "Let's be fair." They would ask every judge to grade the same number of questions.

The Problem: This is wasteful. You might be paying a $100 expert to grade a question that a $1 intern could have graded perfectly. Or, you might be asking a cheap, unreliable judge to grade a super-hard question, wasting your money on bad data.

The Paper's Solution: "Smart Shopping"

The authors propose a smart strategy called EST-IVWE. Think of it as a two-step shopping trip to get the best value for your money.

Step 1: The "Taste Test" (Exploration)

Before you spend your whole budget, you spend a tiny bit of money to "test drive" every judge on every type of question.

You ask the cheap intern and the expensive expert to grade a few of the same questions.
The Goal: You aren't trying to get the final grade yet. You are just trying to figure out: Who is actually good at this specific type of question?
The Trick: The paper introduces a clever mathematical "safety net." If a judge seems too perfect (zero variance) during the test, the algorithm assumes they might just be lucky and adds a tiny bit of "doubt" to their score. This prevents the system from getting confused by lucky streaks.

Step 2: The "Strategic Spend" (Exploitation)

Now that you know who is good at what, you spend the rest of your budget intelligently.

The Rule: For each specific question, you only hire the one judge who offers the best "price-to-quality" ratio.
The Analogy: Imagine you need to buy a specific tool. You wouldn't buy 50 cheap hammers and 50 expensive screwdrivers. You would figure out which tool does the job best for the lowest price, and then buy only that tool.
The algorithm calculates exactly how many times to ask that specific "best judge" to grade that specific question to get the most accurate result.

Why This Matters (The "Instance-Optimal" Claim)

The paper claims this method is "Instance-Optimal."

What that means: It doesn't just work well on average; it works perfectly for your specific situation. If your judges have weird quirks or your questions are unusually hard, this method adapts to that exact scenario to get the best possible score.
The Proof: The authors didn't just guess this was good. They used advanced math (like a "local minimax lower bound") to prove that you literally cannot do better than this method. It's the theoretical limit of efficiency.

The "Fano vs. Assouad" Analogy

The paper mentions a technical debate about how to prove this is the best method.

The "Fano" approach is like trying to find a needle in a haystack by looking at the whole haystack at once. It's too blurry and misses the fine details of which specific judge is best for which specific question.
The "Assouad" approach (which the authors used) is like looking at the haystack one tiny square inch at a time. It preserves the local details, allowing them to prove exactly how the budget should be split down to the penny.

The Results

The authors tested this on fake data and real-world data (using actual LLMs to grade each other).

The Result: Their "Smart Shopping" method (EST-IVWE) consistently beat the "Fair Share" method (Uniform Allocation).
The Takeaway: As you get more budget, their method gets closer and closer to the performance of a "Magic Oracle" (a hypothetical god who already knows exactly which judge is best for every question without having to test them first).

Summary

In a world where evaluating AI is expensive and messy, this paper provides a recipe to stop wasting money. Instead of treating all judges and all questions the same, it says: Test a little bit, figure out the best deal for each specific task, and then spend your money only on that best deal. This gets you the most accurate results for the least amount of cash.

Technical Summary: Instance-Optimal Estimation with Multiple LLM Judges on a Budget

1. Problem Formulation

The paper addresses the challenge of evaluating Large Language Models (LLMs) using the "LLM-as-a-judge" framework under strict budget constraints. In this setting, there are $K$ prompt–response pairs (queries) to be evaluated by $J$ available LLM judges. Each judge $j$ has a known query cost $c_j$ , but the reliability of their evaluations varies. Specifically, the variance $\sigma^2_{k,j}$ of the score provided by judge $j$ on query $k$ is unknown and heteroskedastic (dependent on both the judge and the intrinsic difficulty of the query).

The goal is to adaptively allocate a fixed total budget $B$ across the $K \times J$ query–judge pairs to estimate the true score vector $s \in \mathbb{R}^K$ as accurately as possible. The accuracy is measured by minimizing the $\ell_p$ -error ( $\|\hat{s} - s\|_p$ ) for a fixed $p \in [1, \infty]$ . The problem is formalized as budgeted heteroskedastic multi-judge estimation, a cost-aware generalization of Neyman allocation where variances are unknown and scores are bounded within a known interval $[0, R]$ .

2. Methodology

Oracle Allocation (Known Variances)

The authors first analyze the Inverse-Variance Weighted Estimator (IVWE) assuming the variances $\sigma^2_{k,j}$ are known. They derive the Oracle allocation that minimizes the error rate of the IVWE.

Key Insight: The optimal allocation is sparse. For each query $k$ , the entire budget allocated to that query should be assigned to a single "optimal" judge $j^*(k)$ that minimizes the product of cost and variance: $j^*(k) = \arg\min_j c_j \sigma^2_{k,j}$ .
Allocation Rule: The budget is distributed across queries such that the allocation weight $\omega^*_{k, j^*(k)}$ is proportional to $(c_{j^*(k)} \sigma^2_{k, j^*(k)})^{\frac{p}{p+2}}$ . This generalizes previous work (e.g., Saha et al., 2026) which was limited to $p=\infty$ and a single judge.

Adaptive Algorithm: EST-IVWE (Unknown Variances)

Since variances are unknown in practice, the paper proposes EST-IVWE, a two-stage adaptive algorithm:

Phase I (Forced Exploration): The algorithm queries every $(k, j)$ pair a fixed number of times ( $N_0$ ) to compute empirical variance estimates $\hat{\sigma}^2_{k,j}$ .
Phase II (Allocation): The remaining budget is allocated based on the empirical optimal allocation derived from these estimates.
- Technical Innovation: To handle the instability of variance estimates near zero (which would cause numerical issues in the allocation formula), the algorithm uses an optimistically biased variance estimator $\bar{\sigma}_{k,j} = \hat{\sigma}_{k,j} + \tau$ . This bias stabilizes the allocation for "easy-to-evaluate" pairs (low variance) without significantly impacting the asymptotic error rate.
- Sample Splitting: The samples used for variance estimation in Phase I are not reused for the final mean estimation in Phase II. This decouples the randomness of the variance estimates from the mean estimates, ensuring the final estimator remains unbiased conditional on the variance estimates.

Theoretical Lower Bounds

The paper establishes local minimax lower bounds to prove the instance-optimality of EST-IVWE.

Limitation of Fano's Inequality: The authors demonstrate that standard high-probability lower bounds based on Fano-type packing arguments are too coarse for this problem. They fail to capture the local variance structure required for optimal allocation, yielding suboptimal rates for $p < \infty$ .
Assouad-Type Argument: Instead, the authors employ an Assouad-type in-expectation argument based on local perturbations. This technique preserves the local variance structure and yields a sharp lower bound that matches the upper bound of EST-IVWE up to lower-order terms. This proves that the algorithm is instance-optimal.

3. Key Contributions

Problem Formalization: Defined the budgeted heteroskedastic multi-judge estimation problem, extending Neyman allocation to settings with unknown, heteroskedastic variances and bounded scores.
Oracle Analysis: Derived the optimal sparse allocation for the IVWE under known variances, showing that budget should be concentrated on the single best judge per query.
Adaptive Algorithm: Proposed EST-IVWE, an adaptive algorithm that achieves the oracle error rate without prior knowledge of variances, utilizing optimistic bias and sample splitting to handle bounded, non-Gaussian scores.
Sharp Lower Bounds: Proved a matching local minimax lower bound using an Assouad-type in-expectation framework, establishing the instance-optimality of the proposed method. The paper highlights that Fano-type arguments are insufficient for capturing the precise allocation geometry in this setting.
Empirical Validation: Validated the approach on synthetic data and the real-world HelpSteer2 dataset, demonstrating significant improvements over naive uniform allocation.

4. Results

Theoretical Performance: The error rate of EST-IVWE matches the leading term of the Oracle IVWE rate (which assumes known variances) up to lower-order terms in the budget $B$ . Specifically, for $p \ge 2$ , the error scales as $O(\sqrt{A^*_p/B})$ , where $A^*_p$ is the optimal allocation objective.
Empirical Performance: Experiments on synthetic data ( $K=1000, J=10$ ) and the HelpSteer2 dataset ( $K \approx 178, J=3$ ) show that EST-IVWE consistently outperforms uniform allocation and rapidly converges to the performance of the Oracle strategy as the budget increases.
Robustness: The algorithm remains robust across different cost structures (e.g., when high-variance judges are cheaper) and different error norms ( $\ell_1, \ell_2, \ell_\infty$ ).

5. Significance and Claims

The paper claims to provide a complete theoretical and algorithmic solution to the problem of budget-constrained evaluation with multiple heterogeneous judges. Its primary significance lies in:

Instance-Optimality: Proving that the proposed adaptive strategy is theoretically optimal for any specific problem instance (defined by the variance profile), not just in a worst-case sense.
Methodological Insight: Demonstrating that standard high-probability lower bound techniques (Fano) are inadequate for problems where the optimal allocation depends on fine-grained local variance structures, and that in-expectation arguments (Assouad) are necessary to derive sharp bounds.
Practical Utility: Offering a practical, two-stage algorithm that requires no prior knowledge of judge reliability, making it immediately applicable to real-world LLM evaluation pipelines where costs and variances vary.

The authors note that while their framework is motivated by LLM-as-a-judge, it addresses a broader class of adaptive resource allocation problems. They acknowledge that extending the framework to stochastic costs (e.g., token-length dependent) and incorporating judge bias models are directions for future work, and that deriving a matching high-probability lower bound remains an open theoretical challenge.