Recalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits

When many related prediction problems (which the paper calls "questions") each have only a handful of labels, what information can we share across them? Which information is truly necessary to make good decisions? This paper answers both questions around recalibration, motivated by decision models like Jev (TypeSafe AI, 2026)—which return a probability for any yes/no question a developer writes down.

Problem Setup: Probabilities, True Mappings, and Composite Risk

The paper's formal setup is clear. A predictor reports probabilities $P$ on $m$ questions, with output distribution $\mu$; each question has $n$ labels, and there exists a non-decreasing mapping $g_j(p)=\mathbb{P}(Y=1\mid P=p)$, i.e., the calibration curve. The composite risk is defined as the excess Brier score relative to the true mapping, averaged over all questions.

In other words, what we care about is not how accurately a single question is calibrated, but how much room for improvement remains overall once the calibration errors of $m$ questions are aggregated. This setup is close to real-world scenarios: a general model answers a large number of fine-grained questions simultaneously, yet each question has only a few annotations.

The paper decomposes the estimation difficulty into several sources: the extent to which the true mappings deviate from some common non-decreasing shape (characterized by sup-distance $\tau$ and total variation $V$, i.e., fixed effects), and the scarcity of labels per question $n$. This decomposition makes both "what to share" and "what is needed" quantifiable.

Minimax Rates: What Sharing Information Buys

For a non-atomic output distribution $\mu$, when all mappings lie within sup-distance $\tau\le 1$ of some non-decreasing shape and total variation $V\le 2$, the minimax lower bound on composite risk is:

$$(mn)^{-2/3}+\min{\tau^2,1/n}+\min{\tau^2,V^2,(V/n)^{2/3}}$$

(ignoring universal constant factors).

This expression has several layers worth unpacking. The first term $(mn)^{-2/3}$ shows that even if each question has few labels, as long as the number of questions $m$ is large enough, pooling across questions can still drive down overall risk. The second term $\min{\tau^2,1/n}$ reflects the cost of heterogeneity between mappings: if the calibration curves of different questions differ substantially ($\tau$ large), then sharing structure alone cannot eliminate this part of the error. The third term brings total variation $V$ into the picture as well, forming a finer characterization of deviations from complex shapes.

At the algorithmic level, the estimator proposed in the paper is not complicated: a pooled isotonic fit, plus a per-question correction term, where this correction is estimated only once on the hold-out labels of the entire problem set. Crucially, this estimator does not need to know $\tau$, $V$, or $\mu$ in advance; as long as $n\ge 2$ and $m\ge 3$, it achieves the above rate.

Conversely, if each question is tuned separately using its own labels, one loses a factor of roughly $\min{n,\log(m^2/n)}$ when the mappings differ only by a constant and $m^2/n$ is large. This directly shows that treating questions in isolation is wasteful when labels are scarce.

Identification Limits: Other Questions May Not Identify the Bayes Rule

If the mappings of different questions are drawn from some unknown prior (random effects), the situation becomes more subtle. The paper points out that in this case, other questions may not identify the Bayes rule. The resulting loss is called "identification regret."

The paper provides bounds in two directions. On the upper bound side, once the data distribution of a given question is known, identification regret is at most $2^{-n}$—a result that generalizes Skibinsky's (1968) bound on coins. On the lower bound side, in the worst case, for every finite $m$, the regret is at least $\beta_\star^{-n}/(72\sqrt{n})$, where $\beta_\star\approx 3.583$.

What is interesting here is the precise characterization of the constant $\beta_\star$. For constant mappings (i.e., an uninformative predictor) and a constant-mapping prior, the exponential base is exactly $\beta_\star$, not 4 as the moment range would suggest; for monotone mappings, this base lies in the interval $[2,\beta_\star]$.

From a practical standpoint, this set of results conveys an optimistic signal: as long as each question has more than a few labels, information that cannot be learned is almost unnecessary. In other words, the loss due to identification limits decays very quickly; the real bottleneck lies more in the estimation rate under limited labels than in information-theoretic unidentifiability.

Implications for Engineering Practice

The most valuable aspect of this work is that it turns "sharing across questions" from intuition into a computable trade-off.

• Pooling beats per-question tuning: When questions share a common shape to borrow from, sharing information can significantly reduce overall calibration error, while independent per-question tuning incurs a clear cost when labels are few.
• Use corrections sparingly: The per-question correction only needs to be estimated once on global hold-out labels, rather than consuming labels separately for each question—counter to much engineering intuition.
• Labels need not be plentiful: Identification regret decays exponentially with $n$, showing that "few labels" is not itself a fatal bottleneck; what is really needed is a sufficiently large number of questions $m$.

For teams building yes/no probability prediction services, this framework offers a way of thinking: rather than accumulating large amounts of annotation for each fine-grained question, it is better to focus on expanding question coverage and aligning probability outputs using pooled calibration with a global correction.

One-line Summary

The paper proves that in few-label many-question settings, pooled calibration can share information across questions, and identification limits decay extremely quickly.

Paragraph Summary

Around the setting where many related questions each have very few labels, the paper studies recalibration of probabilistic predictions. The authors define composite risk as the mean excess Brier score relative to the true calibration curves, and give minimax rates: under fixed effects, risk consists of $(mn)^{-2/3}$ and several min terms involving heterogeneity $\tau$ and total variation $V$. Algorithmically, a pooled isotonic fit plus a one-time global correction achieves this rate without needing to know any parameters in advance; per-question tuning separately loses a factor of roughly $\min{n, \log(m^2/n)}$ when $m^2/n$ is large. Under random effects, other questions may not identify the Bayes rule for a given question, with an upper bound on identification regret of $2^{-n}$ and a worst-case lower bound governed by $\beta_\star\approx 3.583$. The core conclusion: sharing structure across questions matters far more than accumulating labels per question, and few labels are not themselves a fatal bottleneck.