Research map / Learning theory and algorithms / Sample complexity

Instance-Optimal Estimation with Multiple LLM Judges on a Budget

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Optimal mean estimation and subsampling · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formulates budgeted heteroskedastic multi-judge estimation, derives an oracle cost-variance allocation for inverse-variance weighting, proposes the two-phase Est-IVWE with optimistic variance bias, and proves matching local (Assouad-type) minimax lower bounds, validated on synthetic and HelpSteer2 data.

Problem

Under a fixed budget, how to allocate LLM-judge evaluation queries across heterogeneous judges (known costs, unknown heteroskedastic variances) and prompt-response instances to minimize the l_p error of estimated score vectors.

Approach

Analyze IVWE to derive an oracle cost-weighted allocation that assigns each query to its best cost-variance judge; estimate variances in a forced-exploration phase and inflate them optimistically by a bias tau, then allocate by IVWE; prove matching local in-expectation lower bounds via Assouad rather than Fano.

Key results

• Est-IVWE outperforms Uniform allocation on both synthetic and HelpSteer2 datasets and rapidly approaches the Oracle as budget grows.
• Est-IVWE (Gaussian) performs on par with or better than the bounded Est-IVWE on both experiments despite bounded data.
• Error curves on HelpSteer2 plateau at non-zero values, attributed to finite resampling pool and judge bias.

Surprising findings

• The Gaussian variant of Est-IVWE outperforms the bounded variant despite the scores being strictly bounded, though it lacks a rigorous guarantee.

Limitations

• Costs are assumed fixed per judge rather than query-dependent or stochastic.
• No matching high-probability lower bound; the Fano-type argument is too coarse for the allocation geometry.
• Judge inherent biases are not modeled; HelpSteer2 error plateaus indicate bias effects.

Experimental setup

Datasets: HelpSteer2 synthetic Beta-distributed scores (K=1000, J=10)

Benchmarks: HelpSteer2 (complexity, correctness, helpfulness, verbosity) synthetic Beta data

Metrics: l_p estimation error 10%/90% quantiles over 50 runs

Baselines: Uniform allocation Oracle IVWE with known variances Est-IVWE (Gaussian variant)

Builds on: Neyman allocation common mean estimation (Graybill-Deal) empirical Bernstein inequality Assouad's lemma

Closest papers by meaning

• Tuning LLM Judge Design Decisions for 1/1000 of the Cost (ICML 2025 · similarity 0.87)
• From Uncertain Judgments to Calibrated Rankings: Conformal Elo Estimation for LLM Evaluation (NeurIPS 2026 · similarity 0.86)
• JudgeLM: Fine-tuned Large Language Models are Scalable Judges (ICLR 2025 · similarity 0.86)
• Justice or Prejudice? Quantifying Biases in LLM-as-a-Judge (ICLR 2025 · similarity 0.86)
• Efficient Evaluation of LLM Performance with Statistical Guarantees (NeurIPS 2026 · similarity 0.85)
• JudgeBench: A Benchmark for Evaluating LLM-Based Judges (ICLR 2025 · similarity 0.85)