Calibrate Only the Questions the Program Asks

Many systems use a neural classifier as one step in a larger program. A digit reader feeds a "maximum" routine. A person detector feeds a check of whether any two people stand closer than two meters. To give an honest error bar on the program's final answer, current methods put an uncertainty set around each classifier's full label ("this digit is 7, 8, or 9") and push those sets through the program's logic. They pay for every label confusion, including ones the program never looks at. Telling 7 from 8 is irrelevant if the program only asks "is this digit above 5?", yet a set that must contain the exact label at 95% confidence grows to absorb exactly those confusions.

We propose to read the program first and work out which yes/no questions about each label actually decide its output. Each such question becomes a binary classification problem with its own distribution-free guarantee. The guarantee comes from conformal prediction, a method that turns held-out data into prediction sets with a promised coverage rate. The resulting answers are then propagated through the program. The binary reduction is how the method avoids the inflation of uncertainty sets as pipelines grow deeper, and it needs no end-to-end labeled data for new programs.

Core Claim

The closest work, Uncertainty Quantification for Neurosymbolic Programs via Compositional Conformal Prediction, calibrates full prediction sets on each neural output, over-approximates them as intervals, and propagates them through program semantics. It also offers a "direct" variant that calibrates the end-to-end output and a "full" variant that intersects the two. We keep its propagation machinery, which supplies the method, but change what is calibrated.

For ordered labels such as digits, counts, or distance bins, an interval $[a,b]$ is exactly the conjunction of two cumulative binary decisions, "$y > a-1$" and "$y \le b$". These are the order-consistent splits that Aleatoric and Epistemic Uncertainty Measures for Ordinal Classification through Binary Reduction uses to measure ordinal uncertainty. That paper gives no coverage guarantee and does not compose its splits across components. The interval domain of abstract interpretation and the binary-split reduction of ordinal classification are therefore the same object.

This allows a static analysis to compute, for each perception call $i$, the set $T_i$ of thresholds $t$ such that the program output depends on label $y_i$ only through the indicators $\mathbb{1}[y_i > t]$, $t \in T_i$. We then conformally calibrate only those binary splits. The claim is that, for programs whose outputs depend on few thresholds (comparisons, maxima, threshold counts, existence queries), this gives valid output sets that are much smaller and decide the answer more often than calibrating full labels. It does so with zero end-to-end calibration data, which means it covers programs written after calibration.

Research Program

The first piece is the analysis. We define a lattice of binary-predicate abstractions over ordered labels and transfer functions for the program constructs used in the neurosymbolic benchmark: map, filter, max, sum, comparison, and loops via fixed points. A backward pass over the program collects the relevant thresholds $T_i$. For max(...) > 5 this is $\{5\}$ for every element. For sum it is every threshold, and the method degrades gracefully into ordinal interval sets. That is still a test, because contiguous intervals built from splits may or may not beat interval hulls of unordered sets.

The second piece is calibration. Each split $t$ gets a binary nonconformity score from the existing classifier's cumulative probability $\hat P(y > t)$. Following Haas & Hüllermeier, these come from a cross-entropy model rather than an ordinal loss. Each split's one-sided set is calibrated at its own miscoverage level. With $m$ perception calls and miscoverage budget $\alpha$, the guarantee we target is

$$ \Pr\big(P(y_1,\dots,y_m) \in \hat S\big) \ge 1-\alpha, $$

where $P$ is the program, $y_i$ are the true labels, and $\hat S$ is the propagated output set. In the basic version, validity follows from a union bound over the $\sum_i |T_i|$ split events. That is cheaper than a union bound over $m$ full-label events whenever each per-split error rate is below the full-label error rate.

A second variant removes the union bound when calibration data comes as labeled tuples, for example several annotated people per COCO image. It calibrates the maximum of split scores within a tuple, which captures correlated failures. This variant is ablated separately so the two ingredients are not confounded.

We never renormalize split probabilities into a distribution. Top-label calibration and multiclass-to-binary reductions found that renormalizing class-wise binary calibrated probabilities hurts calibration. Working with sets rather than probabilities sidesteps that tension. When separately calibrated splits disagree (non-monotone cumulative estimates), we intersect the one-sided sets, which preserves validity.

Baselines

The naive reference point is the point-prediction pipeline, which runs the program on argmax labels and reports a singleton. It shows how often uncertainty quantification changes the answer and what coverage one gets with no guarantee at all.

The main compositional competitor is the compositional conformal semantics of Ramalingam et al.: full-label conformal sets per component, interval abstraction, and propagation. We will run it with the authors' setup on the same classifiers, the same component calibration data, and the same total $\alpha$. Its direct and full (intersection) variants use end-to-end program labels. They are the strongest existing methods when such labels exist, so they get the same end-to-end data when we report that regime. On MNIST digit lists, that paper reports full sets 1.23x smaller than direct and 1.52x smaller than compositional. The file gives no absolute set sizes, and no reported result was found on Lacuna for set size on the MS-COCO queries, so we will regenerate all three.

A budget-allocation baseline follows TRAC, which composes component conformal guarantees by Bonferroni correction and tunes the per-component split of $\alpha$ by Bayesian optimization on a held-out set. TRAC reports roughly 8% smaller sets than untuned allocation and, at $\alpha=0.1$, coverage 0.90 with 20.4 unique answers on Natural Questions. That is a different benchmark, so it only indicates the size of gain tuning buys. We apply the same tuning, on the same held-out budget, to both the full-label baseline and our split sets.

The key ablation isolates direct binary calibration. It keeps our threshold analysis but derives each split's answer by projecting a full-label conformal set onto the split ("does the set lie entirely above 5?"). If projection matches our method, the gain comes from the program analysis alone, not from calibrating the binary questions.

Beating the competitors means equal or better empirical coverage at the nominal level together with a strictly smaller mean output set. For boolean queries, it also means a higher fraction of decisive (singleton) answers, at zero end-to-end data and on held-out programs.

Why not just…?

Why not just calibrate the program's output directly? End-to-end conformal prediction is valid and, given enough labeled program runs, likely hard to beat. Ramalingam et al. show it is already within 1.23x of their best method. Its weakness is that it needs labeled outputs for each program, so a newly written query has no guarantee. This is a real threat in the data-rich regime. We will settle it with a curve of set size against the number of end-to-end calibration examples, and report honestly where direct calibration catches up.

Why not just project full-label sets onto the thresholds the program uses? This is the cheapest version of the idea, and it may capture most of the gain. A full-label set must still cover confusions irrelevant to the split, so its quantile, and hence its projected indecision, should be larger at the same $\alpha$. That is a prediction, not evidence. The projection ablation above tests it directly. If projection matches, we will report the program analysis as the contribution and drop direct split calibration.

Why not just tune the Bonferroni budget, as TRAC does? Budget tuning redistributes conservatism but does not change the size of the event each component must cover. TRAC's reported gain is about 8% on its benchmark. We apply the same tuning to both methods, so any remaining gap is attributable to the split events.

Why not just apply top-label calibration? Gupta & Ramdas calibrate the probability of the predicted label, which is the right fix when a downstream step conditions on that label. However, it yields calibrated probabilities, not coverage sets, and it splits calibration data by predicted class, starving rare classes. It is complementary rather than competing, and we do not run it as a baseline.

Proposed Experiments

We use the MNIST digit-list programs from Ramalingam et al. (sum and max). We add a family of threshold queries written after calibration: is the max above $t$, how many digits exceed $t$, and is digit $i$ larger than digit $j$. We vary list length to measure growth of the set with depth. On MS-COCO we use their spatial queries with distances discretized into ordered bins, plus existence queries such as "any pair closer than $d$". Where several people per image are labeled, we also run the joint max-score variant.

Metrics are empirical output coverage over repeated calibration splits, mean output set size, the decisive-answer rate for boolean queries, and the growth of set size with list length.

The decisive check is a held-out-program protocol. All methods calibrate once on component data, then answer programs never seen during calibration. Our method should keep nominal coverage and give more decisive answers than compositional full-label propagation on threshold-type queries, with the gap growing with list length. On sum, where every threshold matters, the gap should shrink. If it does not, the advantage is coming from somewhere other than calibrating fewer questions, and we will investigate before claiming it.