CS Paper Radar

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

Xiaoli Yu, Jiamiao Liu

cs.IT cs.LG ·submitted 2026-10-13 08:44 UTC · v1
code/data

Abstract

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}$.

Comment
39 pages, 7 figures, 7 tables. Code: https://github.com/yahiko-l/semantic-entropy-rarity

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT cs.LG ·2026-10-29 ·Jiamiao Liu, Dewen Qiao, Yu Zhang, Xuetao Chen
code/data similarity 0.82
Abstract · 47 pages, 5 figures, 3 tables. Code: https://github.com/yahiko-l/pair-dependent-semantic-entropy

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.

0.29

The Hardness of Estimating Cross-Entropy Risk for Language Models

cs.LG stat.ML ·2026-08-16 ·Hanti Lin
theory similarity 0.65
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

Emergence of the transformer architecture as the score of entropic laws of random measures

cs.AI math.PRstat.ML ·2026-10-29 ·Giacomo Greco
similarity 0.63
Abstract · 38 pages, 3 figures

We show that the transformer architecture emerges as the score of last-token laws in a natural statistical model of language, where sentences are empirical measures of tokens, a language is a law on $P(S^d)$, and our prior belief is that sentences carry no structure at all. By the maximum-entropy principle, we select the law closest to this prior in relative entropy among those reproducing an observed sentence-level statistic. We discuss the relevance of the statistic in the posterior interaction between tokens and we build a statistic, able to capture that interaction, with Luce's choice axiom truncated at the lowest relational order. This procedure gives the softmax choice rule, with the attention cross-moment as its mean parameter. The query--key matrix is then the Lagrange multiplier of a maximum-entropy problem inside each sentence, and the value matrix the multiplier of the constraint over the language, so that the two are untied. Under the optimal entropic law we then show that a transformer head appears in the score of the last-token law. For ordered sentences, causal masking follows from the masked reference choice rule, and with a next-token cross-moment the score equals one causally masked attention head. We also discuss multi-head attention, weight-tied unembedding, and a heuristic reading of residual blocks as projected Langevin steps.

0.35

Parallel Repetition for Entangled Games via Conditional Relative Entropy

cs.CC quant-phcs.IT ·2026-10-15 ·Rahul Jain
similarity 0.61
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

What Does Chain-of-Thought Entropy Measure? A Channel Audit of Scaffolding, Routing, and Content

cs.IT stat.MLcs.LG ·2026-08-26 ·Marios Papamichalis, Regina Ruane
theoryhot direction similarity 0.61
Abstract

Entropy over chain-of-thought tokens decides which tokens receive the policy gradient, which get pruned, and whether a run has collapsed, yet each such statistic reads a next-token distribution mixing three choices: whether to emit connective scaffolding, which connective, and what the substantive continuation should be. Designating a scaffold vocabulary subset separates the three, exactly, for entropy, Kullback--Leibler divergence, and the first-order entropy velocity of a softmax policy. We prove the raw and content conventions disagree about which position is the larger fork on an explicit open region, and bound answer diversity by the content channel plus a leakage term a measured witness certifies. Across twenty-three configurations the scaffold side carries up to 41% of the raw high-entropy set; on a matched-tokenizer ladder, coupling changes only at the math-corpus step while the scaffold's entropy share keeps growing through distillation; a closed-form forecast from one channel correlation tracks selection retention over a 54-point range to five points, unfitted. On compression, the content convention beats raw surprisal in every cell; an answer-leakage audit then corrects our own headline control: re-fed chains earn a quarter to a half of their accuracy from restated answers, and once stripped, no token scorer beats a random contiguous block.

0.33

Universal Decoding via the Pairwise Error Probability

cs.IT ·2026-08-20 ·Nir Elkayam, Meir Feder
theory similarity 0.60
Abstract

We develop a theory of universal decoding built on the pairwise error probability (PEP) primitive of a companion paper. The PEP and its error spectrum are defined for an arbitrary decoding metric, and while raw metric values across a family share no common scale, the PEP supplies one. Universal decoding -- decoding well simultaneously against a whole family of metrics or channels -- becomes the problem of merging the per-metric spectra into a single rule, which we construct from a clipped inverse-PEP statistic. The construction rests on a Kraft-type inequality for decoding, valid for any input prior: per output, every metric canonicalizes into a conditional probability assignment on the codewords, and the merge is the normalized-maximum-likelihood envelope of the induced family. We prove the rule is random-coding universal (it loses only a vanishing rate relative to the best metric in the family, against every channel), show it is an asymptotic minimax/equalizer rule, and derandomize it: over a subexponential channel family a single deterministic code inherits the guarantee. For discrete memoryless channels the construction reduces to types and recovers the maximum-mutual-information decoder, its tilted variant for non-uniform memoryless input, and finite-state universal decoders. It extends to decoding with an erasure option (deterministically, uniformly over erasure margins) and, via a discretization of separable metric families, to continuous alphabets: for AWGN with deterministic interference it attains the matched-ML exponent up to an explicit typical-set cap, and for ISI channels the best exponent in a family of equalize-and-decode rules, under explicit assumptions on the equalizers and the channel spectrum and the same cap. Throughout, universality is a corollary of the PEP analysis rather than a separate theory.

0.26

Optimal Rényi and Logarithmic Additive Functional Entropy Estimation

cs.IT cs.CCeess.SPmath.ST ·2026-10-20 ·Arman Adibi, Piotr Krysta
theory similarity 0.58
Abstract

We characterize the minimax sample complexity of estimating Rényi entropy from independent samples on an alphabet of size at most $k$, when the known order $α>1$ may vary with $k$. For every fixed additive accuracy $\varepsilon\in(0,1/2)$ and success probability $2/3$, we prove matching bounds with constants independent of $k$ and $α$. For $1<α<\log k$, the rate is $Θ_\varepsilon(αk^{1-1/α}X_α(k,\varepsilon))$, where a monotone scalar inequality defines $X_α$ at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below $\log k$ have rate $Θ_\varepsilon(αk^{1-1/α})$; orders at least $\log k$ and min-entropy have rate $Θ_\varepsilon(k\log k)$. We extend the analysis to logarithms of positive additive functionals. For every fixed continuous $f$ satisfying $f(0)=0$, $f(x)>0$ for $x>0$, and $f(x)\sim ax^r$ at zero, with $a>0$ and $r>1$, estimating $-β^{-1}\log\sum_i f(p_i)$ at fixed accuracy, for fixed $β>0$, has sample complexity $Θ(k^{1-1/r})$ for integer $r$ and $Θ(k/\log k)$ otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.

0.17

Optimal Min-Entropy Estimation with High Probability

cs.IT math.STquant-ph ·2026-11-17 ·Qisheng Wang
similarity 0.58
Abstract · 9 pages

Min-entropy plays a fundamental role in assessing the unpredictability of randomness sources. In particular, NIST SP 800-90B specifies min-entropy estimation as a key procedure for entropy sources used in cryptographic random bit generators, illustrating the practical importance of reliable min-entropy estimation. In this paper, we settle the sample complexity of min-entropy estimation with high probability in both the classical and quantum cases. Specifically, for min-entropy estimation with additive error $\varepsilon$ and probability at least $1-δ$, the sample complexity is $Θ(d\log(d/δ)/\varepsilon^2)$ for classical distributions on $d$ symbols and $Θ((d^2+d\log(1/δ))/\varepsilon^2)$ for quantum states on a $d$-dimensional Hilbert space. Our results admit short and simple proofs.

0.37