LLM Evaluation as Tensor Completion: Low Rank Structure and Semiparametric Efficiency

Problem Formulation

The paper addresses the statistical challenges inherent in evaluating Large Language Models (LLMs) via pairwise human judgments, as seen in platforms like ARENA. In these settings, users compare two model responses and select a preferred one, generating noisy, sparse, and highly non-uniform data. Current leaderboard practices often report point estimates with limited uncertainty quantification and fail to explicitly exploit the low-rank structure of model performance across tasks, categories, and contexts.

The authors formalize this problem as semiparametric inference for a low-rank latent score tensor ($T^\star$) observed through pairwise comparisons.

• Model: They adopt a Bradley-Terry-Luce (BTL) type framework where the probability of model $a$ beating model $b$ in context $t$ is $\sigma(\langle T^\star, X \rangle)$, with $X$ encoding the pairwise contrast.
• Structure: $T^\star$ is assumed to have a low-rank Tucker structure, reflecting that model performance is driven by a small number of latent factors (e.g., reasoning, coding, multilingual ability) rather than independent entries for every model-task pair.
• Observation: Data consists of binary outcomes from non-uniformly sampled pairwise contrasts, not direct tensor entries.
• Goal: The objective is not full tensor recovery but the efficient estimation of smooth functionals $\psi(T^\star)$, which can be linear (e.g., ability gaps, category scores) or nonlinear (e.g., win probabilities).

Methodology

The paper develops a framework for constructing statistically efficient estimators and valid confidence intervals under these constraints.

1. Semiparametric Efficiency Theory
The authors derive the fundamental limits of estimation by characterizing the efficient influence function (EIF) and the semiparametric efficiency bound.

• Tangent Space: They define a signal tangent space $\mathcal{T}$ that combines the low-rank manifold constraints with linear identification constraints (e.g., zero-sum normalization) required for identifiability in pairwise models.
• Information Operator: They define a Fisher information operator $G$ induced by the logistic link and the sampling distribution. Crucially, they show that under heterogeneous matchups and non-uniform sampling, $G$ is anisotropic (direction-dependent).
• Efficiency Bound: The efficiency bound is given by $V_{\text{eff}}(\psi) = \langle P_{\mathcal{T}}\nabla\psi, A^{-1}P_{\mathcal{T}}\nabla\psi \rangle$, where $A = P_{\mathcal{T}} G P_{\mathcal{T}}$ is the restricted information operator and $P_{\mathcal{T}}$ is the projection onto the tangent space.

2. The Non-Commutativity Bottleneck
A central technical challenge identified is that the information operator $G$ generally does not commute with the tangent-space projector $P_{\mathcal{T}}$.

• In isotropic settings (e.g., Gaussian noise), $G$ is proportional to the identity, making inversion straightforward.
• In pairwise comparisons, the varying Fisher information $I(\eta) = \sigma(\eta)(1-\sigma(\eta))$ creates anisotropy. Consequently, the inverse restricted operator $(P_{\mathcal{T}} G P_{\mathcal{T}})^{-1}$ can exhibit unfavorable entrywise amplification, creating a dimension-dependent bottleneck for standard debiasing arguments. This is quantified by a constant $C_A$ that can scale with $\sqrt{\bar{d}}$ (the largest mode dimension).

3. Estimators
To address these challenges, the authors propose two main estimators:

• One-Step Debiased Estimator: A standard semiparametric approach using the EIF. It requires inverting the estimated restricted information operator. While efficient, its theoretical guarantees depend on the magnitude of $C_A$, requiring larger sample sizes to ensure asymptotic normality when information is highly heterogeneous.
• Score-Whitened Estimator: To overcome the non-commutativity bottleneck, the authors introduce a score-whitening method. By rescaling the score function by the local Fisher information ($\tilde{s}_\eta = s_\eta / I(\eta)$), they transform the effective information operator into an isotropic one. This eliminates the need for operator inversion, removes the $C_A$ bottleneck, and yields a simpler estimator with stable asymptotic behavior under weaker sample complexity conditions ($n \gg \bar{d} \text{polylog}(\bar{d})$).
• Inverse-Probability Weighting (IPW): For non-uniform sampling, they combine score whitening with IPW to restore isotropy, allowing the method to handle real-world data where popular models receive disproportionately more comparisons.

Key Contributions

1. Statistical Formulation: The paper unifies LLM evaluation into a low-rank tensor completion framework under pairwise comparisons, explicitly handling identification constraints and non-uniform sampling.
2. Efficiency Characterization: It provides the first semiparametric efficiency bounds for low-rank pairwise-comparison models, deriving the EIF and the information equation $AH^\star = P_{\mathcal{T}}\nabla\psi$.
3. Identification of a New Bottleneck: The authors identify and analyze the non-commutativity between the anisotropic information operator and the tangent-space projector as a fundamental obstacle in heterogeneous pairwise data, a phenomenon absent in isotropic tensor completion.
4. Score-Whitening Solution: They introduce a score-whitening technique that equalizes local Fisher information, effectively "preconditioning" the problem to restore isotropy and enable efficient inference without operator inversion.
5. Theoretical Guarantees: The paper establishes asymptotic normality and valid variance estimation for both linear and nonlinear functionals, proving that the proposed estimators achieve the semiparametric efficiency bound (or a robust alternative) at optimal sample-complexity scales.

Results

The authors validate their theory through synthetic and real-data experiments:

• Initialization: They demonstrate that a low-rank initialization (via spectral estimation and alternating minimization) followed by entrywise refinement is essential for accurate estimation in sparse regimes, significantly outperforming per-task BTL models.
• Asymptotic Normality: Simulations confirm that both the efficient and score-whitened estimators achieve near-nominal coverage (95%) for linear and nonlinear targets (e.g., win probabilities) as sample size increases.
• Efficiency vs. Robustness: The efficient estimator consistently yields smaller standard errors (higher efficiency) than the score-whitened estimator, confirming it targets the semiparametric bound. However, the score-whitened estimator offers greater robustness and stability under highly heterogeneous information geometries.
• Non-Uniform Sampling: Experiments on non-uniform sampling (mimicking ARENA data) show that IPW combined with score whitening maintains valid coverage. The efficient estimator retains a variance advantage but requires stable estimation of the information operator.
• Real-Data Application: Applied to the ARENA dataset (81k observations, 30 models, 10 categories), the efficient one-step estimator produced the narrowest confidence intervals with coverage close to 95%, outperforming baseline approaches and the more conservative score-whitened approach.

Significance and Claims

The paper claims to provide a principled framework for uncertainty quantification in LLM evaluation. By moving beyond simple ranking to semiparametric inference on structured latent tensors, it addresses the critical need for reliable confidence intervals in model comparison.

The authors emphasize that their work bridges the gap between tensor completion theory and pairwise comparison statistics. They argue that standard completion methods are insufficient because they ignore the binary nature of the data, the identification constraints, and the heteroscedasticity of the information. The proposed framework is not limited to LLMs; the authors note its broader applicability to any low-rank inference problem involving heterogeneous information geometry, non-uniform sampling, and 1-bit observations.

The paper modestly positions its contribution as establishing the theoretical limits and constructing feasible estimators for this specific class of problems, rather than proposing new LLM architectures or benchmarking protocols. It highlights that the "non-commutativity bottleneck" is a unique feature of this setting that necessitates the proposed score-whitening or careful operator inversion strategies.