Coverage That Survives the Stopping Rule: Conformal Guarantees for Cost-Sensitive Feature Acquisition

Many prediction systems do not see all their inputs for free. A clinical model can ask for a blood panel, an image, or a stress test, and each one costs money, time, or patient risk. Cost-sensitive feature acquisition studies policies that decide, patient by patient, which measurement to order next and when to stop and predict. These policies are judged almost entirely on accuracy per unit cost. They have no guarantee that the final answer comes with honest uncertainty. The natural fix is to wrap the policy's final predictor in conformal prediction, a method that turns any model's errors on held-out data into prediction sets that contain the true label with a chosen probability, say 90%. That fix hides a trap. The guarantee holds only on average over everyone. The policy decides when to stop using the same information that makes the model confident. Patients who are stopped early after a few cheap tests are exactly the ones for which an overconfident model looks sure, so their sets can be too small, while patients who went through many tests are over-covered.

We propose to treat the policy's acquisition pathway, meaning the set of features a patient ended up with, as the unit on which coverage must hold. The claim has three parts. First, the number of distinct pathways a policy uses decides whether pathway-level coverage is statistically achievable. Second, that number can be controlled when the policy is designed. Third, the right stopping rule is "stop when the calibrated prediction set is informative enough," not "stop when entropy is low." The result is a policy that minimizes expected measurement cost subject to a coverage requirement that holds within each pathway and within named demographic groups. It pays a small, measurable price in cost to keep the set of pathways small enough to certify.

Core Claim

Fix an acquisition policy trained on separate data. For a patient with features $X$, the policy deterministically produces a terminal observed subset $S(X)$. Everything the final predictor sees is a function of $X$, so a patient's pathway is itself a covariate. Calibrating separately within each pathway (the "Mondrian" scheme) then gives exact finite-sample coverage conditional on the pathway:

$$P\big(Y \in C(X) \mid S(X) = s\big) \ge 1-\alpha \quad \text{for every pathway } s,$$

where $\alpha$ is the allowed error rate and $C(X)$ the prediction set. The cost is sample size. A pathway with $n_s$ calibration points can only produce a finite set if $n_s \ge 1/\alpha - 1$, because the conformal quantile needs at least that many scores to fall below the top rank. A dynamic policy over $D$ features can in principle use up to $2^D$ pathways, so unconstrained instance-wise policies make this guarantee vacuous for most of their pathways.

Combinatorial complexity therefore shows up as a statistical constraint rather than only a computational one. The central object we study is the frontier of expected acquisition cost against the number of pathways $m$. Along that frontier, conditional coverage becomes certifiable once $m$ is small relative to the calibration size $n$. Our hypothesis is that this frontier is flat over a wide range: a policy restricted to a few dozen pathways loses little cost efficiency relative to an unrestricted one, but it gains pathway-conditional validity that the unrestricted policy cannot have.

Relation to Prior Work

Three acquisition methods motivate and supply parts of the design. Sampling-guided exploration of active feature selection policies casts acquisition as a decision process over observed subsets. It avoids imputation and adds a sparsity penalty that collapses trajectories into a few interpretable pathways, evaluated with real economic costs on UCI Heart. Its sparsity penalty is justified by interpretability and it optimizes AUC. We reuse the penalty as the control knob for $m$ and give it a statistical reason to exist.

Learning-To-Measure meta-trains a Transformer policy that maximizes conditional mutual information and reports log-loss and expected calibration error. Active feature acquisition via explainability-driven ranking imitates SHAP-derived orderings and assumes uniform costs. Neither offers distribution-free coverage, and neither checks calibration within subgroups. We use both as policies to be audited and wrapped, not replaced.

The conformal side supplies the method and a warning. Batch Multivalid Conformal Prediction gives BatchGCP, which fits one quantile regression over indicators of overlapping groups to obtain simultaneous group-conditional coverage. It is the natural tool when pathways and demographic groups intersect. We use it with pathway indicators plus protected-attribute indicators as the group family. Conformal Classification with Equalized Coverage for Adaptively Selected Groups shows that exhaustive partitioning fragments calibration data and that adaptive group selection loses power below roughly 200 samples. That constraint is the reason we shrink the pathway family at design time instead of selecting groups after the fact. Sample-Conditional Coverage in Split-Conformal Prediction establishes that exact coverage conditional on individual inputs is impossible. Pathway conditioning is a finite, policy-induced relaxation that sidesteps the impossibility. Rectifying Conformity Scores for Better Conditional Coverage rescales scores by an estimated conditional quantile, which is a competing route we test. Conditional Coverage Diagnostics for Conformal Prediction provides the ERT metrics, which frame miscoverage as a classification problem, and we use them to measure residual gaps beyond the groups we calibrate on.

Confidence on the focal handles coverage after a data-dependent selection of points. Our problem is a data-dependent selection of features. It becomes relevant only if the stopping rule touches calibration data, and we design around that with sample splitting.

Finally, Population-Robust Feature Selection via Generalized Welfare Optimization is the closest existing work that joins combinatorial selection and subgroup robustness. It uses discrete screen-and-swap search to pick one static panel that protects the worst group, and it shows that rounding continuous relaxations degrades performance. It has no dynamic acquisition and no conformal calibration. Its 1-swap search is the template for our pathway-library search, and its static panel is the $m=1$ endpoint of our frontier.

Research Program

The first component is an audit. We take existing policies (the sampling-guided policy, Learning-To-Measure, and a greedy mutual-information-per-cost rule as in Peri-Diagnostic Decision Support Through Cost-Efficient Feature Acquisition at Test-Time) and apply marginal split conformal prediction to their final predictors. We then measure coverage within each terminal pathway, within bins of acquisition depth, and within demographic groups, and we compute ERT with the classifier given pathway identity. The hypothesis is a systematic pattern: under-coverage for shallow pathways and over-coverage for deep ones.

The second component is coverage-aware stopping. Instead of stopping on entropy or a step budget, the policy stops when the conformal set computed for the current observed subset reaches a target size (classification) or width (regression), or when the budget runs out. The per-subset thresholds used for stopping are fit on one calibration split. The final sets are calibrated by BatchGCP on a second, disjoint split. The stopping rule is therefore a fixed function of $X$ when the second split is used, and the guarantee is preserved.

The third component is pathway-library design. We restrict the policy to a library of at most $m$ terminal subsets. The library is chosen by discrete local search in the style of PopFS. The objective is expected cost plus a penalty on worst-pathway set size, and a hard constraint requires every library member to receive enough calibration mass. We then sweep $m$ to trace the cost-versus-$m$ frontier, and alongside it the resulting set sizes and conditional coverage gaps.

Baselines

The naive reference point is an acquisition policy with no calibration: the predictor's own top-probability or credible set is reported as is. This shows how badly uncertainty is misstated without any conformal step. The next reference is the same policy with marginal split conformal prediction, which satisfies average coverage by construction. It is the method a practitioner would reach for first.

The strongest existing competitor is BatchGCP from Batch Multivalid Conformal Prediction. It is applied post hoc to the unrestricted sampling-guided policy from Sampling-guided exploration of active feature selection policies, with groups defined as terminal-pathway indicators, depth bins, and demographic attributes. This is the fairest test of whether policy redesign matters at all, because BatchGCP already targets overlapping groups efficiently. We also run rectified scores from Rectifying Conformity Scores for Better Conditional Coverage, giving the rectifier the pathway mask as an input. All methods receive the same training, stopping-threshold, and calibration splits, the same base predictor family, and the same tuning budget, measured in hyperparameter trials selected on a validation split. I found no reported conditional-coverage result on Lacuna for any acquisition policy, and no reported AUC-versus-cost number that I can quote from the file for the sampling-guided policy on UCI Heart. The comparison will therefore be run fresh rather than against a published figure.

Beating BatchGCP means the following. At matched expected acquisition cost (within 5%), our method must achieve worst-pathway and worst-group coverage within one standard error of $1-\alpha$ where the baseline falls short, or equal coverage with smaller average set size. It must also give lower L1-ERT on held-out data.

Two ablations isolate the ingredients. The first keeps coverage-aware stopping but removes the pathway cap. The second keeps the cap but uses entropy stopping. A final static endpoint uses a single PopFS-selected panel with standard conformal calibration, which is the $m=1$ extreme.

Why not just…?

Why not just calibrate separately within each terminal pathway of whatever policy you have? This gives exact coverage per pathway, but only where pathways have enough calibration points. Pathways with fewer than about $1/\alpha - 1$ points get infinite sets. The fragmentation finding in Conformal Classification with Equalized Coverage for Adaptively Selected Groups predicts the failure. Our frontier experiment measures it directly, as the fraction of patients receiving trivial sets as a function of how many pathways the unrestricted policy uses.

Why not just run BatchGCP on top of an unconstrained policy and skip redesigning the policy? This is the real threat. BatchGCP shares strength across overlapping groups and may cope with many sparse pathways. However, its guarantee for a group degrades as that group's probability mass shrinks. With hundreds of rare pathways, the rare ones are exactly where miscoverage concentrates. The head-to-head comparison at matched cost settles this. If post-hoc BatchGCP matches our worst-pathway coverage and set size, the conclusion is that calibration alone suffices, and we will report that the pathway cap is unnecessary.

Why not just select one fixed feature panel and calibrate once? A static panel has one pathway and trivially valid coverage. The price is ordering expensive tests for every patient. The $m=1$ endpoint of the frontier quantifies this cost. The proposal is justified only if moderate $m$ recovers most of the savings of full dynamic acquisition.

Why not just add the observed-feature mask as input to a rectified score and calibrate marginally? Rectification can shrink the gap if the score's spread given the mask is learned well. It offers no finite-sample guarantee per pathway, though, and it inherits estimation error on rare masks. We include it as a baseline and check it with ERT.

Proposed Experiments

The main testbed is UCI Heart with the real economic feature costs used by the sampling-guided policy. We add the HTA waveform benchmark from the same work, where imputation-based policies fail and pathways are numerous. We also use the medical tasks and synthetic Gaussian-process priors used by Learning-To-Measure, including XOR-style tasks where features are informative only together, so that myopic stopping is expected to stop too early.

For each dataset and each $\alpha \in \{0.1, 0.05\}$ we report five quantities: expected acquisition cost; marginal coverage; worst-pathway, worst-depth-bin, and worst-demographic-group coverage; average set size or interval width; and L1-ERT from Conditional Coverage Diagnostics for Conformal Prediction. Everything is averaged over at least 20 random splits.

The first decisive check is the audit. Marginal conformal prediction on existing policies should show a monotone relation between pathway depth and coverage. If no such relation appears, the motivating mechanism is wrong and the proposal narrows to design only.

The second check is the frontier. Plotting cost against $m$ should show that some $m$ far below the unrestricted pathway count reaches within 10% of unrestricted cost while achieving pathway-conditional validity.

The third check is the head-to-head against post-hoc BatchGCP at matched cost. If that comparison is a tie, the paper's contribution reduces to the audit and the coverage-aware stopping rule, and we will say so.