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

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+\Delta$ 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\Delta^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 $\tau<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\Delta^{2K-2}$. The matching lower bounds hold on every fixed polynomial window $n\Delta^2\le n^{-\kappa}$. One estimator attains these rates without knowing $s$ or $\tau$: 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 $\Delta=n^{-\gamma}$ the entropy is uniformly consistently estimable exactly when $\gamma<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}$.