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

Jiamiao Liu; Dewen Qiao; Yu Zhang; Xuetao Chen

cs.ITOct 29, 2026

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

Authors: Jiamiao Liu, Dewen Qiao, Yu Zhang, Xuetao Chen

Organizations: Department of Information, Xinqiao Hospital Army Medical University (Third Military Medical University) Chongqing 400037, China

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.

Figures & tables

Figure 1: Polynomial decay exponent

a

of the minimax squared risk

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

of semantic entropy for three meanings and a known judge, when

\Delta=n^{-\beta}

and

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

is fixed. In the shaded band

5/8<\beta<2/3

, channels in

\mathcal{U}_{4}

allow consistent estimation and channels with an admissible double pair do not, although

N_{4}=n^{4}\Delta^{6}\to\infty

for both. Blue: a homogeneous judge ( Yu and Liu, 2026b ) . Red, dash-dotted: a judge with meaning-dependent sensitivities and one common false-equivalence probability, for almost every positive sensitivity profile ( Yu and Liu, 2026a ) . Green: general channels in

\mathcal{U}_{4}

, whose tree functions on at most four vertices are injective. Purple, dashed: general channels in

\mathcal{U}

with an admissible double pair, two interior distributions with equal tree functions on at most four vertices and different entropies; their exponent jumps at

\beta=5/8

from the left limit

1/12

, open circle, to the value

0

, large purple dot. Small filled dots mark the thresholds of the other three curves, beyond which each exponent is

0

and the curves coincide; open circles at

\beta=1/2

mark the excluded endpoint

n\Delta^{2}=1

. The rates hold on fixed polynomial windows, which cover every fixed

\beta>1/2

Observation and channel	minimax squared risk	$\beta_{c}$	least-favorable pair	separated by
meanings observed	$1/n$	none	interior	the labels
homogeneous judge, $M=I$ ( Yu and Liu, 2026b )	$\min\{1,N_{3}^{-1/2}\}$	$3/4$	near a vertex	trees on $3$ vertices
meaning-dependent sensitivity, $M=\mathrm{diag}(w)$ , almost every $w\in(0,\infty)^{3}$ ( Yu and Liu, 2026a )	$\min\{1,N_{5}^{-1/5}\}$	$5/8$	near $\theta\propto 1/w$	trees on $5$ vertices
general $M\in\mathcal{U}_{4}$	$\min\{1,N_{4}^{-1/3}\}$	$2/3$	near $\theta^{*}$	trees on $4$ vertices
general $M\in\mathcal{U}$ with an admissible double pair	$\min\{1,N_{4}^{-1/3}\}+e^{-\Theta(N_{5})}$	$5/8$	near $\theta^{*}$ for the rate; the double pair for the threshold	trees on $4$ vertices near $\theta^{*}$ , on $5$ at the double pair

Table 1: Three meanings: how the structure of a known judge sets the minimax squared risk of semantic entropy and the consistency threshold

\beta_{c}

for

\Delta=n^{-\beta}

, with

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

fixed and

N_{v}:=n^{v}\Delta^{2v-2}

. Every rate with a judge holds on fixed polynomial windows

n\Delta^{2}\leq n^{-\kappa}

; in the last row,

e^{-\Theta(N_{5})}

is the cost of the double pair, with constants in the exponent that depend on the channel. The fourth column says where a least-favorable pair of distributions sits, and the fifth which trees first tell its two members apart.

Figure 2: The seven trees on at most five vertices, grouped by the role of their tree functions. For fixed

q\in(0,1)

and

M

, in the weak regime, the statistic of a tree on

v

vertices has variance of order

1/N_{v}

, and

N_{v+1}=\delta N_{v}

, so the statistics on more vertices are noisier. For a channel in

\mathcal{U}

, the edge and wedge functions determine

x_{1}^{2}

and

x_{2}^{2}

at the equitable point to leading order, and the two trees on four vertices separate a perturbation from its reflections in the eigen-axes at third order, which is why the four-vertex statistics set the rate

N_{4}^{-1/3}

. The trees on five vertices separate the two points of an admissible double pair, at which the tree functions on at most four vertices agree. The five-vertex trees enter the risk through the term

e^{-\Theta(N_{5})}

Figure 3: The two points of the lower bound at the equitable point of the channel

M_{0}

. (a) Near

\theta^{*}

(star), the level curves of the edge function (gray),

F_{K_{2}}(\theta^{*}+D_{u}x)=c+\lambda_{1}x_{1}^{2}+\lambda_{2}x_{2}^{2}

, are ellipses centered at

\theta^{*}

; the dotted lines are the eigen-axes

x_{1}=0

and

x_{2}=0

\widetilde{M}

, the dashed curves the level curves of the entropy through

\theta_{+}

and

\theta_{-}

, the plus sign marks the uniform distribution, and the shaded regions lie outside the simplex. A perturbation

x=s\zeta_{0}

, here with

s=1/4

, and its three reflections in the eigen-axes (circles) lie on one ellipse, the darker one, while the entropy separates

x

from its reflection

-x

at first order. The filled points are

\theta_{+}=\theta^{*}+sD_{u}\zeta_{0}

and

\theta_{-}

, the reflection corrected at second order, at which the edge and wedge functions take their values at

\theta_{+}

. (b) The same construction for

31

amplitudes

s

from

10^{-3}

0.3

: the entropy gap grows like

s

, and

\mathcal{D}_{4}(\theta_{+},\theta_{-})

and the largest difference of the five-vertex tree functions grow like

s^{3}

, with fitted log-log slopes

1.00

3.00

and

3.00

for

s\leq 0.01

; the edge and wedge functions agree to within

10^{-45}

. So

|H(\theta_{+})-H(\theta_{-})|^{3}\asymp\mathcal{D}_{4}(\theta_{+},\theta_{-})

, as in the cubic modulus, and at

s\asymp N_{4}^{-1/6}

the difference

\mathcal{D}_{4}

is of the same order

N_{4}^{-1/2}

as the errors of the four-vertex statistics, while the squared entropy gap is of order

N_{4}^{-1/3}

Figure 4: The fiber path for the channel

M_{0}

, between the two points

\theta^{0}

and

\theta^{1}

of its admissible double pair, whose entropies are

0.654

and

0.483

. (a) The distributions

\theta_{t}

in the simplex: straight pieces in the parameter half-plane (blue, solid) and the two crossings through collisions of atoms at the Gauss nodes (red, dashed), with the collision points marked by crosses, the second of which lies next to

\theta^{1}

; the star is the equitable point

\theta^{*}

and the squares are the three face equitable points. (b) The entries of the channel

M_{t}

, equal to

M_{0}

at both ends. (c) The three tree functions on five vertices. The four tree functions on at most four vertices are constant along the path; at the

1081

evaluated points, in

50

-digit arithmetic, they differ from their values at the endpoints by at most

9.2\times 10^{-49}

. Of the seven tree functions, only the three on five vertices move. Light vertical lines separate the seven pieces and dotted lines mark the collisions.

Channel	class	double pairs	smallest $\mathcal{D}_{5}$	entropy gap
$M_{0}$	$\mathcal{U}\setminus\mathcal{U}_{4}$	1	$1.98\times 10^{-3}$	0.171
$M_{1}$	$\mathcal{U}_{4}$	0	none	none
$M_{2}$	$\mathcal{U}_{4}$	0	none	none
$M_{3}$	$\mathcal{U}^{\sigma}_{\{3\}}$	1	$6.02\times 10^{-4}$	0.114
$M_{4}$	$\mathcal{U}^{\sigma}_{\{2\}}$	1	$1.33\times 10^{-3}$	0.207
$M_{5}$	$\mathcal{U}^{\sigma}_{\{1\}}$	1	$5.70\times 10^{-4}$	0.0784

Table 2: Certified channels (entries in Appendix G ) and two random samples. Double pairs are pairs of distinct points of

\Theta_{3}

at which

F_{\leq 4}

agrees; for the strata

\mathcal{U}^{\sigma}

, only pairs outside the symmetric pairs are counted. A channel with a counted double pair lies outside the corresponding class with subscript 4. The separation, given in the fourth column, is the interval lower bound of

\mathcal{D}_{5}

over the double pairs, rounded down; the entropy gap is

|H(\theta)-H(\theta^{\prime})|

for each double pair. The grid channels have diagonal entries in

\{12,\dots,28\}/20

and off-diagonal entries in

\{-6,\dots,6\}/20

, and were drawn conditioned on

\min_{c}\theta^{*}_{c}\geq 1/20

; the random channels have independent entries, uniform on the grid of step

1/200

, diagonal entries in

[1/2,3/2]

and off-diagonal entries in

[-1/2,1/2]

, the second sample with one diagonal draw shared by the three diagonal entries. All classifications are exact rational computations in SymPy with outward-rounded interval arithmetic in mpmath. The proportions are empirical for these distributions.

Figure 5: How the proofs depend on one another. An arrow from one result to another means that the proof of the second uses the first, and a dashed arrow that it reruns an argument from the proof of the first, with the results that argument uses: Theorem 6 reruns the proofs of Theorems 9 , 10 and 1 and of Proposition B.4 on each stratum, adding Lemmas F.1 , F.2 and F.3 , and takes the classes of

M_{3},\dots,M_{9}

from the certificates of Appendix G ; Proposition B.4 reruns the covering argument of the proof of Theorem 9 (a); Lemma F.2 reruns, for another map, the lower bound in the proof of Lemma B.1 ; and Lemmas E.2 , E.3 , E.4 and E.5 use the objects and steps of the proof of Proposition 13 and, in Lemma E.4 , the factorization in the proof of Lemma 7 . Not shown are Lemma 11 , which shows why the path of the lower bound must move the channel and on which no proof depends, Lemmas A.4 , A.5 and A.6 , used in the proofs of Lemmas B.1 , B.3 , F.2 and F.3 and of Theorem 10 , and Lemma E.1 on the Gauss nodes, used in the proof of Lemma 16 .

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Check	population and settings	result
Variance of the tree U-statistics	exact enumeration, $n\in\{5,6\}$ , 56 cases	mean: relative error $\leq 2.2\times 10^{-11}$ ; variance formula: $\leq 1.5\times 10^{-14}$
	exact variances, 875 cases	variance over bound $\leq 0.124$
	weak regime, $n=10^{4}$ , $\delta=10^{-4}$	variance over leading term in $[1.0000,1.0013]$
Rotation path	38 of the 40 channels formed by the twenty grid channels and twenty channels within $0.02$ of $M_{0}$ , entrywise; $s\in\{0.04,0.02,0.01,0.005\}$	tree orders in $[2.990,3.265]$ , unicyclic orders in $[0.976,1.068]$ , edge and wedge residual $\leq 8.3\times 10^{-57}$
Rotation path	the two other grid channels, with the smallest eigenvalue gaps; $s\in\{0.02,0.01,0.005,0.0025\}$	tree orders in $[2.967,3.386]$ , unicyclic orders in $[0.941,1.078]$ , edge and wedge residual $\leq 7.6\times 10^{-58}$
Fisher information, exact, $n=5$	$M_{0}$ , $q=0.3$ , $s=0.02$ , $\Delta\in\{0.02,0.01,0.005\}$ ; rotation path at 5 times; straight segment at fixed $M$ , $t\in\{0,0.25\}$	fitted power of $\Delta$ : $5.984$ to $5.986$ ; $1.995$ to $1.997$ ( $5.984$ at the midpoint over these $\Delta$ , where the edge derivative vanishes)

Appendix

Table 3: Sampled numerical diagnostics of steps of the proofs. The ratios of the modulus search are the largest values the searches attained, hence lower bounds for the modulus constants; ranges and bounds are rounded outward. Settings and metrics are defined in Appendix H .

Semantic Entropy

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

See all 15 papers

Oct 13, 2026

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

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

τ

: 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}

Xiaoli Yu, Jiamiao Liu

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

Semantic Entropy Minimax Estimation Information-Theoretic Lower Bounds Pairwise Comparison

Ask PDF

Aug 8, 2026

Evaluator Ensembles Under Reward Hacking: Covariance Geometry and Finite-Search Guarantees

Language-model judges and reward models enable scalable supervision, but finite optimization can exploit evaluator errors rather than improve response quality. We characterize this failure through the covariance geometry of evaluator ensembles. For calibrated judges, the ensemble mean retains common-mode error along the all-ones direction, whereas cross-judge disagreement captures only orthogonal error. Consequently, disagreement can be high despite robust aggregation, or low while shared response-dependent errors persist. We prove that common-mode error is not identifiable from internal judge scores alone. Under a joint sub-Gaussian model, we bound best-of-K selection overstatement and target-quality regret, extending the guarantees to predictably adaptive search under conditional calibration. The resulting search terms scale as the square root of log K and are asymptotically tight for Gaussian projected errors. We further show that noisy quality proxies introduce artificial rank-one covariance without changing disagreement, and propose a bounded two-anchor Bernstein certificate for finite-search error and regret. Fixed-seed Gaussian stress tests over 120 (J, rho, K) configurations and real-model audits validate the theory while revealing the limits of disagreement-based diagnostics under increasing search pressure.

Fariya Afrin, Ibne Farabi Shihab

Department of Computer Science, Kalinga Institute of Industrial Technology · Department of Computer Science, Iowa State University

Reward Hacking LLM Evaluation LLM-as-a-Judge Best-of-N Sampling Reward Model Evaluation

Ask PDF

Jul 18, 2026

Tight Sample Bounds for Renyi and Min-Entropy Estimation

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.

Arman Adibi, Piotr Krysta

Department of Computer Science

Sample Complexity Information-Theoretic Lower Bounds

Ask PDF

Abstract

Semantic Entropy

Explore similar work

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

Evaluator Ensembles Under Reward Hacking: Covariance Geometry and Finite-Search Guarantees

Tight Sample Bounds for Renyi and Min-Entropy Estimation