The Safety Gate That Can't Get a Certificate
Modern AI systems hide a quiet failure mode. A model may be perfectly capable, but the deployment team cannot prove it. The problem surfaces when a selective predictor, one that outputs a decision only when confidence is high enough and abstains otherwise, must meet a safety guarantee for every reporting unit it serves. A reporting unit could be a specific tool in an LLM agent, a content moderation policy label, a patient subgroup in a clinical classifier, or a product category in a recommendation engine.
The guarantee in question is certified precision: for each reporting unit, the fraction of accepted predictions that are correct must exceed some target, say 0.90, and this must hold with a specified confidence, often tied to a familywise error rate that controls false discoveries across all units simultaneously. The paper by Priye, Wang, Ling, and Chaykowsky frames a problem that practitioners know intuitively but rarely formalize: the real difficulty is not whether a certificate would be valid if granted, but whether your finite calibration data can produce one at all.
Why Global Guarantees Hide Subgroup Failures
The classical selective prediction literature, going back to Chow in 1970 and extended by El-Yaniv and Geifman, treats the abstention gate as a binary system: a single model, a single threshold, a single precision target. A global guarantee says the overall precision of traffic that passes the gate is at or above the target. This is necessary but insufficient. A gate that is safe on average can still be unsafe for a specific tool or patient subgroup, because error rates vary across the units that make up the system.
Conformal prediction and conformal risk control, developed by Bates, Angelopoulos, Lei, and others, give finite-sample, distribution-free methods for constructing valid prediction sets and risk-controlling prediction sets. Mondrian conformal prediction extends this to group-conditional coverage: each subgroup gets its own guarantee. These methods answer the question "is the returned policy trustworthy?" They do not answer "how should a fixed calibration budget be allocated across alternative partitions of reporting units, given that some units are too rare to certify?"
This is the gap the paper fills. It studies not the validity of a single certificate, but the availability of certificates across a deployment. Availability, in this paper's precise sense, is the probability that finite calibration data can produce a valid certificate for a given reporting unit at a given precision target. As the gate becomes safer (precision target rises) or more fine-grained (more reporting units), availability drops. Some units receive too little evidence to certify.
Making Availability Computable: Exact Binomial Inversion
The authors ground availability in classical statistics. For a reporting unit with true selective error rate p (the probability that an accepted prediction is wrong) and a target precision 1 minus alpha, the question of whether calibration data of size n can certify the unit reduces to a binomial tail bound. Specifically, exact binomial inversion computes the minimum sample size required to reject the null hypothesis that the error exceeds alpha at a given confidence level.
This is not a new statistical technique. What is new is the application: using binomial inversion to compute, for each candidate reporting partition, which units can be certified and which cannot, given the actual calibration sample sizes each unit would receive under that partition. The availability of a unit is the probability that its calibration sample size meets or exceeds the binomial threshold, computed over the random allocation of calibration examples to units.
The calculation depends on three quantities: the true error rate of the predictor within the unit, the target precision, and the familywise error budget that controls simultaneous inference across all units. The familywise error is typically managed through a Bonferroni or similar correction, which divides the total allowed false discovery rate among units. More units means smaller per-unit budgets, which means larger required sample sizes, which means lower availability.
The paper illustrates this with a concrete example. At a target precision of 0.90, a familywise failure probability of 0.05, and a true selective error of 0.05, certifying a single group at 80% availability requires 179 served calibration examples. Fifty groups require 450 each for the same per-group availability. Raising the error margin from 0.05 to 0.09 while holding fifty groups fixed increases the requirement from 450 to 13,407 examples. The constraint on granularity comes from two directions: the number of simultaneous guarantees and the margin between the true error and its target.
Reporting-Partition Selection as a Dynamic Program
Given a set of reporting units with known or estimated error rates, the deployment planner faces an optimization problem: choose a partition of units into certifiable groups, where each group receives enough calibration examples to meet the availability target, while maximizing the total traffic that can be certified. This is the reporting-partition selection problem.
The paper formulates this as a dynamic program under a fixed group order. The state space tracks the cumulative sample size allocated to groups processed so far, and the transitions decide whether to merge a unit with an existing group or start a new group. The objective function trades off among three quantities: safety (the per-group precision guarantee), granularity (the number of distinct reporting units), and served traffic (the fraction of total requests that fall into certifiable units).
The dynamic program yields a Pareto frontier: a curve of achievable (granularity, traffic) pairs at a fixed safety level. This frontier is the central object of the paper. It reveals what the deployment team can certify and at what cost. A steep section of the frontier means that a small increase in required traffic for a new unit forces a large reduction in overall certified volume. A flat section means the additional unit comes cheaply.
The Population-Finite Gap: Where Theory Meets Data
The frontier computed from population quantities, the true error rates and sample sizes known exactly, looks very different from the frontier computed from finite calibration data. The population frontier reveals a large opportunity: many units can be certified at high granularity if the planner has perfect information. The finite-sample frontier collapses much of that opportunity.
The paper quantifies this gap with a single metric: mean coverage, the average fraction of traffic that can be certified across all units. A truth-informed planner, one with access to population quantities, achieves a mean coverage gain of 0.157 over a baseline strategy of support balancing (distributing calibration examples proportional to each unit's traffic volume). A naive estimator, one that uses raw calibration counts without any correction, recovers only 0.005 of that gain. The gap between 0.157 and 0.005 is the central challenge the paper addresses: recovering lost availability from finite data.
The reason the naive estimator performs so poorly is straightforward. Small units have high variance in their estimated error rates. Some units appear to have very low error because only a few calibration examples fell into them, and all happened to be correct. Others appear to have high error because a few bad examples landed in a tiny bucket. The naive planner allocates based on these noisy estimates, misallocating calibration budget to units that look good but aren't, or starving units that would certify with slightly more data.
Split-Sample Planning: Constructing and Selecting Partitions
The paper's main methodological contribution is a split-sample approach to partition selection. The idea is simple but effective: split the calibration data into two independent halves. Use the first half to construct a set of candidate reporting partitions, each one a candidate grouping of units. Then use the second half to evaluate which of these candidates performs best on the actual available data.
Constructing candidates on the first split means the planner explores the space of possible groupings without overfitting to the particular calibration samples that will be used for the final certificate. Selecting on the second split means the choice is validated on fresh data, preserving the statistical guarantee. This is conceptually similar to cross-validation in model selection, adapted to the specific structure of the partition problem.
The results are consistent. The split-sample approach improves mean coverage over support balancing by 0.060. While this is less than the 0.157 population optimum, it represents a meaningful recovery of availability that the naive estimator misses. The improvement direction, split-sample over support balancing, is reproduced in 59 of 60 model effects across three intent-routing datasets and two architectures. The one exception is an outlier, not a contradiction.
The three intent-routing datasets come from different LLM tool-calling setups, and the two architectures are distinct model families. The consistency across these settings suggests the method is not dataset-specific but reflects a general property of finite-sample partition selection.
Reallocating the Familywise Error Budget
The paper introduces a second lever for recovering availability: reallocating the familywise error budget across reporting units. The standard approach distributes the budget equally, giving each unit the same alpha. But units differ in their error rates and sample sizes. A unit with a low true error rate and plenty of calibration data can afford a tighter per-unit alpha without sacrificing availability. A unit with a high error rate and sparse data needs a looser per-unit alpha to certify at all.
Reallocating the budget means solving an optimization that assigns per-unit alpha values subject to the familywise constraint. This is valid-preservation: the simultaneous guarantee across all units is maintained, but the allocation is adaptive rather than uniform. The paper shows this recovers additional coverage, both when computed from population quantities and from noisy estimates.
The two levers, split-sample partition selection and adaptive error budget allocation, are complementary. They address different sources of availability loss. Partition selection addresses structural misallocation, choosing the wrong groupings. Budget allocation addresses statistical misallocation, giving each unit the wrong precision target. Using both together yields the best performance.
The Frontier Across Domains
The paper demonstrates that the availability frontier is not specific to LLM tool-calling. The same structure recurs, with predictor-specific ceilings, across four distinct domains: LLM tool-calling (the primary experimental setting), content moderation (classifying comments as safe or unsafe), lesion classification (medical imaging for skin or tissue abnormalities), and recommendation systems (predicting user preferences).
In each domain, the frontier takes the same shape: a curve of achievable (granularity, coverage) pairs at a fixed safety level, with a steep section where adding units becomes costly and a flat section where units come cheaply. The ceiling of the frontier, the maximum achievable coverage, varies by predictor. A more accurate predictor has a higher ceiling because its true error rates are lower, making certification easier across all units. But even a perfect predictor faces a finite-sample ceiling: if calibration data is limited, some units simply cannot be certified regardless of the predictor's accuracy.
This is the paper's key insight for practitioners: certified availability is a plannable deployment resource. It is not a fixed property of the model, nor is it purely a function of data volume. It is the output of a planning process that trades off among safety, granularity, and traffic. The frontier makes these trade-offs explicit and quantifiable.
What This Means for Working Developers
If you deploy a selective predictor with per-group safety guarantees, this paper gives you a framework for answering three questions before you ship. First, can your calibration data certify the reporting units you need? The binomial inversion calculation gives a concrete yes-or-no answer for each unit, given its estimated error rate and calibration sample size. Second, how should you group your reporting units to maximize certified traffic? The dynamic program over partitions gives the optimal grouping. Third, how much availability are you leaving on the table by using a naive allocation strategy? The population-finite gap quantifies the cost.
The practical steps are straightforward. Collect calibration data for each reporting unit. Estimate per-unit error rates, either from held-out data or from the calibration set itself using conformal methods. Run the binomial inversion to check which units can be certified at your target precision. If some cannot, try the split-sample approach: partition your calibration data, construct candidate groupings on one half, and select the best grouping on the other. If you have flexibility in your precision targets, consider adaptive error budget allocation.
The method does not require retraining or modifying the underlying predictor. It operates entirely at the deployment layer, as a planning step before the system goes live. This makes it compatible with any selective prediction framework, including conformal risk control, selective classification, and simple confidence thresholding.
Limitations and Open Questions
The paper acknowledges several limitations. The split-sample approach recovers only about 38% of the population-finite gap (0.060 out of 0.157). The remaining availability is lost to estimation noise that no amount of clever partitioning can recover. The dynamic program assumes a fixed group order, which may not be optimal in all cases. The adaptive error budget allocation depends on accurate estimates of per-unit error rates, which are themselves noisy for small units.
The experiments focus on classification tasks. The framework's extension to regression or structured prediction is not explored. The paper also does not study sequential or online settings where calibration data arrives over time, which would require online versions of the partition selection algorithm.
Perhaps the most important open question is whether better estimators for per-unit error rates could close more of the gap. The paper frames estimation as the central challenge but does not propose new estimators, focusing instead on how to use existing estimates more effectively through partition selection and budget allocation. Better uncertainty quantification for small-unit error rates could push the finite-sample frontier closer to the population optimum.
Planning Certifications Before They're Needed
The contribution of this paper is reframing a deployment problem as an optimization problem. The availability of safety certificates is not a mysterious property of the data. It is the output of a planning process with quantifiable trade-offs. Teams that plan their certification strategy, rather than discovering availability failures after calibration, can deploy more granular safety guarantees over more traffic. The frontier is the tool for that planning: it tells you what is possible, what it costs, and where the next unit of calibration data is best spent.