# Sharp Integrality Gaps in Calibration Distance

arXiv: https://arxiv.org/abs/2610.05679 · HTML: https://mlsanity.com/paper/2610.05679/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 12 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Builds on (most cited first, 9 of 9)

- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)
- [Can a calibration metric be both testable and actionable?](https://mlsanity.com/paper/2502.19851/) (2025)
- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)
- [Truthfulness of Decision-Theoretic Calibration Measures](https://mlsanity.com/paper/2503.02384/) (2025)
- [Smooth Calibration and Decision Making](https://mlsanity.com/paper/2504.15582/) (2025)
- [A Perfectly Truthful Calibration Measure](https://mlsanity.com/paper/2508.13100/) (2025)
- [The Importance of Being Smoothly Calibrated](https://mlsanity.com/paper/2603.16015/) (2026)
- [Computational and Statistical Hardness of Calibration Distance](https://mlsanity.com/paper/2603.18391/) (2026)

## Abstract (arXiv)

We study the offline gap between deterministic calibration distance C and its fractional relaxation L for binary unit-weight sequences under total absolute-change cost. We sharpen the offline comparison C <= L + O(sqrt(T)) (Qiao and Zheng, 2024, Theorem 2) to the sharp worst-case order Theta(T^(1/3)). If Delta_T is the supremum of C - L over length-T inputs, then T^(1/3)/1000 <= Delta_T <= 41T^(1/3) for T >= 216. The upper bound holds for every input, while each T >= 216 has a rational lower-bound input. For every input with m distinct forecasts, C <= L + m, and the unrestricted-sample worst-case sparse order is Theta(m). For rational forecasts and accuracy, with binary-encoded multiplicities of separately assignable unit identities, a grid-free polynomial-bit-time procedure returns B <= L <= U, U - B < eta, and an exactly calibrated compact repair of cost at most U + m <= L + m + eta.