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

Xiaoli Yu; Jiamiao Liu

cs.ITOct 13, 2026

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

Authors: Xiaoli Yu, Jiamiao Liu

Organizations: School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications, Chongqing 400065, China · Department of Information, Xinqiao Hospital, Army Medical University (Third Military Medical University), Chongqing 400037, China

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

Figures & tables

setting	minimax squared risk	matching lower bound proved on
at most $3$ meanings, all distributions [ 3 ]	$\min\{1,(n^{3}\Delta^{4})^{-1/2}\}$	the whole window $n\Delta^{2}\leq c_{1}$
at most $4$ meanings, all distributions [ 4 ]	$\min\{1,(n^{4}\Delta^{6})^{-1/3}\}$	every fixed window $n\Delta^{2}\leq n^{-\kappa}$
$K$ meanings, at most $s\geq 2$ rare	$\min\{1,N^{-1/s}\}$	every fixed window $n\Delta^{2}\leq n^{-\kappa}$
$K$ meanings, at most one rare	$\min\{1,N^{-1}\log^{2}(e+N)\}$	every fixed window $n\Delta^{2}\leq n^{-\kappa}$
$K$ meanings, none rare	$\min\{1,N^{-1}\}$	every fixed window $n\Delta^{2}\leq n^{-\kappa}$
shrinking $\ell_{2}$ ball of radius $h_{n}$ about an interior $\theta_{0}$ with distinct coordinates	$(1+o(1))\,\mathcal{V}(\theta_{0})/N$	$n\Delta^{2}\leq n^{-\kappa}$ , $\kappa<\frac{1}{K-1}$ , $N\to\infty$ , $h_{n}\to 0$ , $h_{n}\sqrt{N}\to\infty$

Table 1: Minimax Squared Risk of the Semantic Entropy From a Known Pairwise Judge

Figure 1: Polynomial decay exponent

a

of the minimax squared risk for the semantic entropy,

R^{*}=n^{-a+o(1)}

, when

\Delta=n^{-\gamma}

and

q\in[q_{0},1-q_{0}]

is fixed, for

K=5

possible meanings of which at most

s

have probability below a fixed

\tau\in(0,1/5)

. Here

N=n^{5}\Delta^{8}

. The classes

s=0

and

s=1

have the same exponent and share the darkest curve, and for

s=1

the risk carries an extra factor

\log^{2}n

wherever

a>0

. The rates are matched for every fixed

\gamma>1/2

, and open circles mark the excluded endpoint

\gamma=1/2

, where

n\Delta^{2}=1

. Every class loses uniform consistency at the same

\gamma_{c}=K/(2K-2)=5/8

Figure 2: Rarity classes

\Theta_{3,s}(\tau)

for

K=3

possible meanings and

\tau=0.2

, in the simplex

\Theta_{3}

drawn as a triangle whose vertices are the distributions concentrated on one meaning, with gray lines at

\theta_{c}=\tau

. The shaded class

\Theta_{3,s}(\tau)

holds the distributions with at least

3-s

coordinates of at least

\tau

, so

\Theta_{3,0}(\tau)\subset\Theta_{3,1}(\tau)\subset\Theta_{3,2}(\tau)=\Theta_{3}

. Under each class is the order of its minimax squared risk for large

N=n^{3}\Delta^{4}

under the conditions of Theorem 1 (ii).

Figure 3: The

16=4^{4-2}

labeled spanning trees of a set of four answers placed at the corners of a square:

12

paths, grouped by shape, and

4

stars. Given the meanings, the product of the centered verdicts

X_{e}

along the edges of any of them has conditional mean

1

if the four answers share a meaning, and

0

otherwise. The all-tree average averages these products over all trees of all

4

-sets, and the star average over the stars alone. For

K=4

, restricting to the stars multiplies the leading variance of

\widehat{T}_{4}

K^{K-3}=4

Figure 4: Change

|[H]|

of the entropy against the change

D_{e}=|[e_{5}]|

e_{5}=\prod_{c}\theta_{c}

between the two endpoints of the least-favorable fibers of Section 5.1 , for

K=5

possible meanings and

\tau=0.05

: the mixed fiber for

s=2,3,4

, the fiber for

s=1

and the perturbation for

s=0

, at four amplitudes

\varepsilon

(or

\eta

) per decade, computed from the roots of

p_{u}

160

-digit arithmetic. Only

e_{5}

moves along each fiber, so

D_{e}

is the distance in the one-sided transfer, and the entropy responds with its modulus

\phi_{s}(D_{e})

. At

D_{e}=N^{-1/2}

the square of this modulus is of the order of the rate

\psi_{s}(N)

Figure 5: Pairs

(M,M^{\prime})

of motifs that share a vertex, for

K=4

, drawn as the multigraph

U=M\uplus M^{\prime}

with the edges of

M

dark and those of

M^{\prime}

light. Under each pair are the triple

(v-K,\beta,\chi)

and the factor

N\delta^{v-K}\Delta^{2\beta+\chi}

, where

v

is the number of vertices,

\beta

the cycle rank and

\chi

the excess edge multiplicity of

U

. (a) A spanning tree paired with itself. No other pair of motifs with nonzero coefficients has the factor

N

. (b) Two spanning trees of the same

4

-set, a path and a star. (c) Spanning trees of two

4

-sets that share three answers. (d) A spanning tree with one edge doubled, paired with the tree.

		30 motifs on at most $5$ vertices		65 motifs on $6$ or $7$ vertices
$s$	macroscopic	identity	slope of $\|\partial_{u}\varkappa_{M}\|$	largest	last	smallest slope
	meanings	metric	( $5$ vertices)	$R(\varepsilon)$	ratio	of $\max_{z}\|B^{(5)}_{M}\|$
$2$	$3$	$1.99\times 10^{-19}$	$[1.989,\,2.002]$	$0.080$	$[0.331,\,1.001]$	$0.997$
$3$	$2$	$6.76\times 10^{-20}$	$[2.951,\,2.999]$	$0.178$	$[0.111,\,1.010]$	$0.971$
$4$	$1$	$1.13\times 10^{-19}$	$[3.994,\,4.000]$	$0.152$	$[0.013,\,0.335]$	$1.982$

Table 2: Taylor Coefficients of the Sweep of Order 5 on the Mixed Fibers

Figure 6: Largest Taylor coefficient

B^{(5)}_{M}(z)

of the sweep of order

5

, over the

65

tested motifs

M

on six or seven vertices and all their label assignments

z

, divided by the probability scale

\varepsilon

of the rare meanings, at the midpoint of a mixed fiber for

K=5

with

s

rare meanings and macroscopic proportions

(0.5,0.3,0.2)

(0.6,0.4)

and

(1)

for

s=2,3,4

. The coefficients are evaluated in double precision. The largest tested coefficient is consistent with order

\varepsilon

, the order of the uniform coefficient bound, when two or three meanings are macroscopic (

s=3,2

), and decays faster at the vertex (

s=4

$K$	$\varepsilon$	$\max_{u,j}\|\theta_{j}(u)-b_{j}\|/\varepsilon$	$[P_{K}]^{1}_{0}/\varepsilon$	$([H]^{1}_{0}-\varepsilon\log(1/\varepsilon))/\varepsilon$
$4$	$10^{-3}$	$6.88$	$-0.127749$	$-3.05336$
	$10^{-4}$	$7.14$	$-0.130385$	$-3.05845$
	$10^{-5}$	$7.17$	$-0.130650$	$-3.05896$
	$10^{-6}$	$7.17$	$-0.130677$	$-3.05901$
	limit		$-0.13068$	$-3.05902$
$5$	$10^{-4}$	$27.09$	$+0.016107$	$-3.69178$

Table 3: The Fiber for

s=1

in 80-Digit Arithmetic

$K$	$s$	$\tau$	$c_{0}$	pairs	$D_{e}<c_{0}$	viol.	one-sided	both in $\Theta_{K,s}(\tfrac{\tau}{2})$	two-sided	min $D_{e}/c_{0}$
$4$	$0$	$0.2$	$1.00\times 10^{-8}$	$22300$	$8863$	$0$	$2.4\times 10^{-3}$	$16648$	$2.4\times 10^{-3}$	$5.5\times 10^{5}$
$4$	$0$	$0.075$	$1.98\times 10^{-10}$	$22300$	$7657$	$0$	$1.9\times 10^{-4}$	$17032$	$2.0\times 10^{-4}$	$1.1\times 10^{6}$
$4$	$1$	$0.2667$	$3.16\times 10^{-8}$	$22300$	$9385$	$0$	$0.071$	$18568$	$0.096$	$4.7\times 10^{4}$
$4$	$1$	$0.1$	$6.25\times 10^{-10}$	$22300$	$8311$	$0$	$0.016$	$19041$	$0.084$	$1.6\times 10^{5}$
$4$	$2$	$0.4$	$1.60\times 10^{-7}$	$22300$	$10244$	$0$	$0.180$	$19687$	$0.180$	$3.1\times 10^{4}$
$4$	$2$	$0.15$	$3.16\times 10^{-9}$	$22300$	$9712$	$0$	$0.093$	$20572$	$0.093$	$1.2\times 10^{6}$

Table 4: Checks of the One-Sided Local Transfer

$K$	$n$	$q$	$\Delta=10^{-1}$	$10^{-2}$	$10^{-3}$	$10^{-1}$	$10^{-2}$	$10^{-3}$	$10^{-3}$
			$\mathrm{Var}(\hat{T}^{\star}_{K})/\mathrm{Var}(\hat{T}_{K})$			$\nu_{T}$			$\nu_{S}$
$4$	$4$	$0.3$	$3.871281$	$3.998734$	$3.999987$	$1.222173$	$1.017574$	$1.001719$	$1.0017154$
$4$	$4$	$0.5$	$3.895025$	$3.998932$	$3.999989$	$1.027125$	$1.000267$	$1.000003$	$1.0000000$
$4$	$5$	$0.3$	$3.813419$	$3.998108$	$3.999981$	$1.258022$	$1.017878$	$1.001722$	$1.0017168$
$4$	$5$	$0.5$	$3.843904$	$3.998404$	$3.999984$	$1.053407$	$1.000519$	$1.000005$	$1.0000012$
$5$	$5$	$0.3$	$24.020839$	$24.990460$	$24.999905$	$1.232056$	$1.017651$	$1.001719$	$1.0017155$

Table 5: Exact Variances of the All-Tree and Star Averages at Fixed

n

			$\mathrm{Var}(\hat{T}^{\star}_{4})/\mathrm{Var}(\hat{T}_{4})$		$\tilde{\nu}_{T}$		$\tilde{\nu}_{S}$
$q$	$n$	$\delta$	Monte Carlo	exact	Monte Carlo	exact	Monte Carlo	exact
$0.3$	$200$	$0.2$	$3.227\,(0.164)$	$3.069$	$1.737\,(0.082)$	$1.854$	$1.359\,(0.067)$	$1.380$
$0.3$	$200$	$0.1$	$3.132\,(0.175)$	$3.467$	$1.435\,(0.076)$	$1.416$	$1.090\,(0.054)$	$1.191$
$0.3$	$200$	$0.05$	$3.258\,(0.184)$	$3.713$	$1.416\,(0.071)$	$1.222$	$1.119\,(0.055)$	$1.101$
$0.3$	$400$	$0.2$	$2.769\,(0.140)$	$3.064$	$1.972\,(0.092)$	$1.807$	$1.345\,(0.066)$	$1.363$
$0.3$	$400$	$0.1$	$3.410\,(0.182)$	$3.464$	$1.496\,(0.070)$	$1.383$	$1.257\,(0.061)$	$1.180$

Table 6: Monte Carlo Variances of the All-Tree and Star Averages for

K=4

Figure 7: Star versus all-tree averages of the centered verdicts, with

q=0.3

in dark blue and

q=0.5

in light blue. The gray line marks the limit

1

, and the shading spans the exact values drawn in each panel. (a, b) The exact ratio

\mathrm{Var}(\hat{T}^{\star}_{K})/(K^{K-3}\mathrm{Var}(\hat{T}_{K}))

for

K=4

and

K=5

at fixed

n=K

(thick lines) and

n=K+1

(thin lines) as

\Delta

decreases, in exact rational arithmetic, at two base points per

K

: circles

\theta=(0.4,0.3,0.2,0.1)

and

(0.3,0.25,0.2,0.15,0.1)

, squares

\theta=(0.35,0.3,0.2,0.15)

and

(0.28,0.24,0.2,0.16,0.12)

, with the

q=0.3

series offset horizontally to the left of the

q=0.5

series for legibility. (c)

K=4

\theta=(0.4,0.3,0.2,0.1)

: the same ratio against

\delta=n\Delta^{2}

, exact finite-

n

values at

n=200

and

n=800

(lines, which coincide at this scale) and Monte Carlo estimates with

1000

replicates each and delta-method standard errors (circles

n=200

, squares

n=400

, triangles

n=800

, offset horizontally in that order for legibility). All panels check the variance constant behind the loss factor

K^{K-3}

$K$	$\theta_{0}$	$n$	$q$	$\Delta=10^{-2}$	$10^{-3}$	$10^{-4}$	$(I(0)/L_{0}-1)/\Delta$ at $\Delta=10^{-4}$
				$I(0)/L_{0}$
$4$	$(0.4,0.3,0.2,0.1)$	$4$	$0.3$	$0.9831455$	$0.9982887$	$0.9998286$	$-1.7140$
$4$	$(0.4,0.3,0.2,0.1)$	$4$	$0.5$	$1.0000900$	$1.0000009$	$1.0000000$	$+0.0001$
$4$	$(0.4,0.3,0.2,0.1)$	$5$	$0.3$	$0.9833249$	$0.9982905$	$0.9998286$	$-1.7138$
$4$	$(0.4,0.3,0.2,0.1)$	$5$	$0.5$	$1.0002446$	$1.0000024$	$1.0000000$	$+0.0002$
$4$	$(0.35,0.3,0.2,0.15)$	$4$	$0.3$	$0.9845438$	$0.9984312$	$0.9998429$	$-1.5712$

Table 7: Fisher Information Along the Interior Fiber

Semantic Entropy

Semantic entropy measures uncertainty over the meanings of a model’s possible answers rather than over its individual word choices.

See all 14 papers

Tight Sample Bounds for Renyi and Min-Entropy Estimation
Jul 18, 2026Arman Adibi, Piotr KrystaSample Complexity Information-Theoretic Lower Bounds
Department of Computer Science
Extending Minimal Pairs with Ordinal Surprisal Curves and Entropy Across Applied Domains
Mar 15, 2026Andrew KatzLLM Evaluation Surprisal Theory
Department of Engineering Education, Virginia Tech
Entropy Equivalence Testing
May 22, 2026Clément L. Canonne, Yash Pote, Jonathan Scarlett +1Distribution Matching
University of Sydney · National University of Singapore

Jul 18, 2026J/K move · Enter open · S save

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Arman Adibi, Piotr Krysta

Department of Computer Science

Sample Complexity Information-Theoretic Lower Bounds

Open paper AskPDF arXiv

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a

k

-symbol alphabet using

Θ(k/\log k)

samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-

α

R'{e}nyi entropy,

H_α

. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for

k

and integer

α>1

; our lower bounds also hold for noninteger

α\ge1.001

. We prove that min-entropy estimation to constant additive accuracy has sample complexity

Θ(k\log k)

. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires

Θ(\log^2 k)

more samples than Shannon entropy and corrects a previously stated

Θ(k/\log k)

characterization. For every integer

2\leα\le c_0\log k

, we prove the matching fixed-accuracy bound

Θ_{c_0}(αk^{1-1/α})

. Previous results gave

Ω_α(k^{1-1/α})

for fixed integer

α>1

and

O_{c_0}(α^2k^{1-1/α})

for all integer

α>1

. Our upper bound analyzes an unbiased falling-factorial estimator based on

α

-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor

α

is unavoidable. For every real

1.001\leα\le c_0\log k

, we prove the uniform lower bound

Ω_{c_0}(αk^{1-1/α})

. Finally, since

0\le H_α(p)-H_\infty(p)\le\log k/(α-1)

, min-entropy uniformly approximates

H_α

when

α

is a sufficiently large multiple of

\log k

. Combining this reduction with our min-entropy bounds gives

Θ_\varepsilon(k\log k)

sample complexity in the high-order regime.

Abstract

Semantic Entropy

Explore similar work

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Extending Minimal Pairs with Ordinal Surprisal Curves and Entropy Across Applied Domains

Entropy Equivalence Testing