mlsanityData to 14 Oct 2026

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

arXiv 2610.17971 ↗First posted 13 Oct 2026cs.IT cs.LG math.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

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 nDelta2→0, 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≥2, N-1log2(e+N) for s=1 and N-1 for s=0, capped at one, where N=nKDelta2K-2. The matching lower bounds hold on every fixed polynomial window nDelta2≤ n-kappa. 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 Delta=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 KK-3.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 17 of its 49 references that are in the map. First posted on arXiv 13 Oct 2026.

Builds on

17 of 49 references.

References · 17

  1. 2023Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generationcited by 819
  2. 2023Generating with Confidence: Uncertainty Quantification for Black-box Large Language Modelscited by 293
  3. 2024Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similaritiescited by 159
  4. 2014Exact Recovery in the Stochastic Block Modelcited by 78
  5. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 39
  6. 2025Beyond Semantic Entropy: Boosting LLM Uncertainty Quantification with Pairwise Semantic Similaritycited by 28
  7. 2016Spectrum Estimation from Samplescited by 10
  8. 2020Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery modelcited by 9
  9. 2025Estimating Semantic Alphabet Size for LLM Uncertainty Quantificationcited by 8
  10. 2022Is it easier to count communities than find them?cited by 5
  11. 2025Hallucination Detection on a Budget: Efficient Bayesian Estimation of Semantic Entropycited by 5
  12. 2018Estimation of subgraph density in noisy networkscited by 2
5 more
  1. 2023Private and Communication-Efficient Algorithms for Entropy Estimationcited by 2
  2. 2025A statistically consistent measure of semantic uncertainty using Language Modelscited by 2
  3. 2025Local Poisson Deconvolution for Discrete Signalscited by 1
  4. 2026The generalized method of moments is (almost) statistically efficient in low-SNR Gaussian latent-variable modelscited by 1
  5. 2026Characterizing Heterogeneous Rates in Finite Mixture Estimation via Partial Optimal Transportcited by 1

Built on by

Not cited yet.