CS Paper Radar

Pair-Dependent Judge Errors Change the Minimax Rate of Semantic Entropy

Jiamiao Liu, Dewen Qiao, Yu Zhang, Xuetao Chen

cs.IT cs.LG ·submitted 2026-10-29 02:18 UTC · v1
code/data

Abstract

Semantic entropy, the entropy of the meanings among a language model's sampled answers, is estimated from the verdicts of a judge that declares pairs of answers equivalent or not, and automatic judges err in ways that depend on the answers they compare. The existing minimax theory covers only judges whose false-equivalence probability is the same for all pairs. We model a known judge that declares two answers with meanings $a$ and $b$ equivalent with probability $q+ΔM_{ab}$, for a symmetric matrix $M$ and $q$ bounded away from $0$ and $1$, and show that for three meanings the rate is set by tree statistics on four answers, while on an open set of channels the consistency threshold is set by trees on five. For every channel in an explicit open class, the minimax squared risk is of order $N^{-1/3}$ with $N=n^4Δ^6$ on polynomial weak windows on which $n^5Δ^8$ exceeds a multiple of $\log n$, and of order $\min\{1,N^{-1/3}\}$ on every polynomial weak window when the tree functions on at most four vertices are injective. The exponent comes from a cubic degeneracy at the equitable point. On an open set of channels in the class, the four-vertex tree functions take equal values at two distributions with different entropies. For such a channel, on every polynomial weak window, the minimax risk is of the order of the sum of $\min\{1,N^{-1/3}\}$ and a term that decays exponentially in $n^5Δ^8$, so no estimator is consistent while $n^5Δ^8$ stays bounded, even as $N\to\infty$. For $Δ=n^{-β}$ with $β>1/2$, channels of the class with injective four-vertex tree functions allow consistent estimation exactly for $β<2/3$, and the channels of this open set exactly for $β<5/8$, at which the risk exponent drops from $1/12$ to $0$. Computer-assisted certificates show that both kinds of channels occur on open sets.

Comment
47 pages, 5 figures, 3 tables. Code: https://github.com/yahiko-l/pair-dependent-semantic-entropy

Closest papers

Nearest neighbours by meaning across the whole index.

Rarity Determines Minimax Rates of Semantic Entropy From Weak Pairwise Judgments With a Known Channel

cs.IT cs.LG ·2026-10-13 ·Xiaoli Yu, Jiamiao Liu
code/data similarity 0.82
Abstract · 39 pages, 7 figures, 7 tables. Code: https://github.com/yahiko-l/semantic-entropy-rarity

The semantic entropy of a language model is the entropy of the meanings of its sampled answers. The meanings are never observed, and the entropy is estimated from the verdicts of a pairwise equivalence judge. Given the meanings of $n$ answers, a known channel declares each pair equivalent independently, with probability $q+Δ$ within a meaning and $q$ across meanings. At most $K$ meanings occur, and $q$ is bounded away from $0$ and $1$. For a weak judge, with $nΔ^2\to0$, the global minimax rate is set by distributions near a vertex of the simplex and overstates the difficulty elsewhere. We show that the difficulty is set by how many meanings can be rare. Over distributions with at most $s$ meanings below a fixed probability $τ<1/(K-s)$, the minimax squared risk is of order $N^{-1/s}$ for $s\ge2$, $N^{-1}\log^2(e+N)$ for $s=1$ and $N^{-1}$ for $s=0$, capped at one, where $N=n^KΔ^{2K-2}$. The matching lower bounds hold on every fixed polynomial window $nΔ^2\le n^{-κ}$. One estimator attains these rates without knowing $s$ or $τ$: it averages products of centered verdicts along all spanning trees of every $k$-set of answers, projects the resulting power sums onto the valid moment set and inverts them. The case $s=K-1$ gives the global rate $N^{-1/(K-1)}$ and the consistency threshold: with $Δ=n^{-γ}$ the entropy is uniformly consistently estimable exactly when $γ<K/(2K-2)$. On polynomial windows, the same estimator attains the sharp local minimax constant on shrinking neighborhoods of interior points with distinct probabilities. Restricting the average to stars multiplies the constant by $K^{K-3}$.

0.45

Parallel Repetition for Entangled Games via Conditional Relative Entropy

cs.CC quant-phcs.IT ·2026-10-15 ·Rahul Jain
similarity 0.65
Abstract · 35 pages, version 1

We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value $1-\varepsilon<1$ and answer alphabets $\mathcal A,\mathcal B$, its $n$-fold repeated value is at most \[ \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, \] for every $n\ge1$. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least $1-\varepsilon+δ$ is at most $\exp[-Ω(δ^5n/(\varepsilon^2L))]$ for $0<δ\le\varepsilon$. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.

0.30

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

cs.CC quant-ph ·2026-10-27 ·Kuan Cheng, Ruiyang Wu
similarity 0.55
Abstract

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler-extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$, our matrix sampler uses $$ m+O_α(\log(D/δ))\text{ random bits and } O_α\!\left(\varepsilon^{-2-α}\log^{1+α}(D/δ)\right)\text{ samples}, $$ for any constant $α>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1+α} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.

0.09

All Verdicts are Not Equal: Rethinking LLM Judge Reliability

cs.CL cs.AI ·2026-10-08 ·Vineet Kumar, Darshita Rathore, Anindya Moitra
publishedtheory similarity 0.55
Abstract · Accepted at AACL IJCNLP (Main) 2026

LLM-as-a-Judge is the standard paradigm for NLP evaluation, yet its systemic reliability remains poorly understood despite being widely treated as a deterministic ground truth. We present a comprehensive reliability audit, stresstesting six frontier models across four benchmarks, five prompt formats, two presentation orders, three sampling temperatures, and ten repetitions per condition. Our empirical analysis reveals severe vulnerabilities: verdicts change across identical replications at temperature zero, position-order swaps flip the majority of verdicts on challenging tasks, and the most deterministic judge achieves perfect consistency by trivially repeating incorrect verdicts, agreeing with ground truth only 51% of the time. To formalize these multi-faceted failure modes, we introduce the trustworthy verdict rate (T ), a unified metric capturing the joint probability that an evaluation is reproducible, order-invariant, and accurate. UsingT , we derive a theoretical upper bound on accuracy imposed by position bias and show that reliability is item-specific rather than modellevel. Finally, we demonstrate that shifting from pairwise win-rate to holistic rubric scoring improves trustworthiness more than any single-format prompting intervention, offering an actionable framework for robust NLP evaluation.

0.21

Two Sample Sizes in Test-Time LLM Ensembling: Buffered ERM and Minimax Theory

cs.LG math.STstat.ML ·2026-10-15 ·Zhi Zhang, Arash A. Amini
theoryhot direction similarity 0.55
Abstract

Test-time scaling can improve the performance of large language models by generating multiple answers to a question and aggregating them. Weighted ensembles extend this idea by drawing answers from several models, with the weights determining how often each model is used. Learning these weights from a training dataset involves two sample sizes: $Q$ labeled questions and $N$ generations per model and question. We study their interplay through the clean risk, the population error of the ensemble's infinite-generation voting rule. Under a margin condition with exponent $β$, we show that empirical risk minimization (ERM) with a calibrated margin buffer achieves excess risk of order $Q^{-1/2}+N^{-β/2}$, up to logarithmic factors, for fixed numbers of models and candidate answers. To investigate the optimality of this dependence on $Q$ and $N$, we analyze a simplified submodel with two models and two possible answers per question. We characterize its minimax excess risk up to constants by a Hellinger modulus for a binomial-mixture experiment. Polynomial approximation and spectral analysis reveal three regimes. When questions are relatively scarce, the $Q^{-1/2}$ term governs learning and the general buffered ERM is optimal. In an intermediate regime, pooling generation counts across questions improves upon estimating each answer distribution separately, with only logarithmic gains from additional questions. With sufficiently many questions, the minimax excess risk reaches an $N^{-β}$ identification floor that persists even with infinitely many questions. The submodel's lower bounds also apply to general ensembles, matching the buffered-ERM upper bound up to logarithmic factors when questions are scarce and in parts of the intermediate regime. Questions remain about the transitions between regimes and the construction of matching pooled estimators for general ensembles.

0.33

The Hardness of Estimating Cross-Entropy Risk for Language Models

cs.LG stat.ML ·2026-08-16 ·Hanti Lin
theory similarity 0.55
Abstract · Substantially revised and expanded version under a new title. Retains the main impossibility results of v1 and adds a new positive theorem c…

Language models, once pretrained, are routinely assessed by the holdout method, which estimates their per-token cross-entropy risk---a quantity that may be finite or infinite. We prove possibility and impossibility theorems that characterize the hardness of this estimation problem. The estimand depends on two objects: the unknown data distribution $p$ and the distribution $q$ induced by the language model under study. Our ignorance of $p$ is empirical, whereas our ignorance of $q$, or at least of its tail, is mathematical; so the parameter space {\em should} range over pairs $(p,q)$---a product space---to fully capture our ignorance. {\em Negative results}: no estimator is pointwise consistent, even when the parameter space is restricted to full-support models and to data distributions whose expected text length is below a fixed bound; worse, every estimator fails on a dense set of pairs. {\em Positive results}: the holdout estimator becomes pointwise consistent when the models are further restricted to Transformers or, architecture-neutrally, to full-support models with a finite context window; and, where no such design is in place, it still consistently estimates the risk capped at any fixed threshold, which suffices for screening candidate models in practice. {\em Lesson}: designs such as the Transformer architecture and finite context windows, although adopted for computational or engineering reasons, pay a {\em statistical dividend}: they suffice to make pointwise consistency possible---a dividend visible only in how they turn a negative result into positive ones.

0.04

Separating Words with Automata in the Half-adversarial Case

cs.FL ·2026-08-28 ·Gabriel Bathie
theory similarity 0.55
Abstract

We consider the problem of separating words with deterministic finite automata (DFA) (Goral{č}{í}k and Koubek, 1986). This problem asks: given two distinct words $u,v$ of length at most $n$, what is the size of the smallest DFA that accepts one and rejects the other? The best upper bound on the worst-case over all pairs of words of length at most $n$ is $\tilde{O}(n^{1/3})$ states (Chase, 2021), while the best lower bound is $Ω(\log n)$. In this work, we consider the half-random, half-adversarial case: we show that if $u$ is a uniformly random binary word of length $n$, then with high probability, for any word $v$ not equal to $u$, there is a DFA with $O(\log^{7/3} n \mathrm{poly}\log\log n)$ states that separates $u$ and $v$. Our results are based on a novel analysis that exploits the structural sparsity of random words: we show how to apply block-wise compaction with small deterministic transducers to reduce the separation problem to the case of words with short run-length encodings.

0.21

Entropy-Weighted Soundness for Multi-Answer Birthday Graphs

cs.CC cs.DS ·2026-11-03 ·Alexandru Popa
theory similarity 0.54
Abstract · 29 pages

The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables. Although a satisfying assignment induces a $K$-clique for $K=\binom n\ell$, an arbitrary selection of $K$ vertices may repeat some views and omit others. This makes soundness substantially harder than under uniform view sampling. For bounded-occurrence, constant-gap Boolean ternary CSPs whose constraints each involve three distinct variables (allowing arbitrary Boolean predicates), we prove that the graph's maximum induced $K$-vertex density satisfies \[ ρ^*(K)\le 2\exp\!\left(-c\, \frac{\ell^3}{n^2\log(en/\ell)}\right) \] for $2\le\ell\le x_0n$ and $\ell\log(en/\ell)\ge C_0\log(n+1)$, with positive constants depending only on the source parameters. The argument refines the biclique counting method by charging the entropy of an adversarially chosen flattening to mutual information and a combinatorial obstruction energy. In the overlapping parameter range it strengthens the explicit soundness exponent previously established for this graph. We also establish an unconditional stability theorem for arbitrary sets $H$ of exactly $K$ distinct local assignments, with missing views and multiple answers: $f_*(H)\le34(n/\ell)q_{\mathrm{con}}(H)$ for every $1\le\ell\le n$. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.

0.36