When Can Conformal Risk Control Certify LLM Outputs? Bounds, Impossibility, and Adaptation for Structured Generation

Title:When Can Conformal Risk Control Certify LLM Outputs? Bounds, Impossibility, and Adaptation for Structured Generation

Abstract:Large language models (LLMs) deployed for structured generation (NER, JSON extraction, QA, and classification) lack formal reliability guarantees, and standard heuristic abstention policies violate user-specified risk targets on 7.5--12.5% of settings, with no per-deployment guarantee. We characterize when conformal risk control (CRC) can certify structured LLM outputs and when it provably cannot. First, we prove a sharpened, attained feasibility frontier: when base risk \mu exceeds target \alpha, any distribution-free method must abstain on at least (\mu-\alpha)/(M-\alpha) of inputs, yielding a closed-form feasibility test that decides whether CRC can work before running it. Second, we establish a proven certification phase diagram across Hoeffding, empirical Bernstein, and a betting-based e-CRC bound, verified over 716 configurations (six open-weight models 3B--72B, eight datasets, six scores): at strict targets (\alpha <= 0.20) the certified sets are nested (51/72/80 certified; Hoeffding-to-Bernstein the largest upgrade, +41%; e-CRC best under calibration scarcity), while at relaxed targets the Hoeffding-Bernstein ordering reverses at a closed-form frontier. Third, we show a negative shift result with a constructive counterpart: under cross-dataset shift the target is violated on 14 of 16 transfers by static CRC and every tested adaptive-conformal-inference (ACI) step size, yet a full-feedback anytime-valid monitor certifies 0 of 16 while remaining non-vacuous. Relaxing the target to \alpha = 0.40 unlocks practical certification (28% NER, 13% QA, 19% CLS). The framework gives a three-step deployment recipe: check feasibility, select the bound and score, then re-check under shift.

Machine Learning (cs.LG)

arXiv:2606.29054 [cs.LG]

(or arXiv:2606.29054v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2606.29054 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.