PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample-Efficient Generative Conformal Prediction

Minxing Zheng, Shixiang Zhu

arXiv:2610.11349v1cs.LGstat.ME

TL;DR

Generative conformal prediction needs enough samples to represent response distributions, but those draws can be costly and uniform counts may waste the budget. CASA allocates samples across inputs to minimize expected set size subject to coverage and budget constraints. Across synthetic and real tasks, it reduces set size at comparable sampling costs and can improve conditional-coverage balance.

  • Problem

    Generator samples can be costly, while fixed sample counts may waste draws on simple inputs and undersample complex ones.

    Source: §1 · p. 1

  • Method

    CASA allocates an input-dependent number of generator samples to minimize expected set size subject to marginal coverage and an average sampling-budget constraint.

    Source: §1 · p. 2, §3.1 · p. 4

  • Results

    Across synthetic and real tasks, CASA reduces set size at comparable sampling costs and improves conditional-coverage balance; on synthetic benchmarks, mean set size falls approximately 12% versus fixed-count PCP.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Allocating samples to recover missed modes can reduce set size even when the conformal radius is optimally adapted to each input.

    Source: §1 · p. 2

    CASA cannot repair a generator that never samples a relevant mode, and its theory assumes separated modes.

    Source: §5 · p. 8

Abstract

from arXiv · show

Generative conformal prediction builds uncertainty sets from samples of a conditional generator, which are efficient only when the samples represent the response distribution well. This can require many samples, each of which can be costly, as in large diffusion models and scientific simulators, so the sampling budget must be used efficiently. Existing methods draw the same number of samples at every input, wasting samples where the response distribution is simple and undersampling where it is complex, which inflates sets and leaves those inputs under-covered. We propose CASA (Conformal Adaptive Sample Allocation), which characterizes the marginal value of an additional sample and allocates samples across inputs to minimize the expected set size subject to marginal coverage and an average sampling budget. Theoretical analysis shows that adaptive allocation yields smaller sets than a fixed count at the same budget: a missed mode forces a radius that spans the gap between modes, and even oracle radius cannot compensate for it. On synthetic and real tasks, CASA produces substantially smaller sets at the same budget, often improves conditional coverage, and complements existing radius-adaptive methods.

1 INTRODUCTION

Generative conformal prediction uses generator samples to build sets that reflect complex response distributions, but costly, uniform sampling can waste draws on simple inputs and undersample complex ones. CASA reallocates samples across inputs; the paper reports smaller sets at matched budgets and explains how recovering missed modes can reduce set size.

1 INTRODUCTION

  • Large diffusion models and scientific simulators make each draw costly; a high-resolution CESM run used roughly 25 million processor-hours per simulated year.The paper notes that large fixed sample counts for every climate initial condition or forcing scenario can be computationally prohibitive.Source: §1 · p. 1
  • Uniform sample counts can waste computation on simple inputs while undersampling complex inputs that drive prediction-set size and conditional-coverage imbalance.The paper poses adaptive allocation as a way to construct small conformal sets while mitigating that imbalance.Source: §1 · p. 1
  • CASA allocates additional draws where they may recover missed response mass and stop sampling where further draws mainly add set volume.It estimates marginal coverage benefit and set-size cost through the same inclusion probability, then optimizes expected set size under coverage and average-budget constraints.Source: §1 · p. 2
  • When samples miss a mode, calibration may require a radius spanning the gap; adaptive sample counts can help even when the radius is optimally adapted per input.The paper argues radius adaptation alone cannot achieve this sample-allocation benefit.Source: §1 · p. 2
  • Approximately 12% lower mean set size on synthetic benchmarks versus fixed-count PCP; on Porto taxi trajectories, mean set area falls approximately 37% with five draws per input on average.The paper also reports that gains persist at matched sampling costs and extend to several existing generative conformal methods.Source: §1 · p. 2
  • Existing sample-based continuous-response conformal methods use the same sample count at every input, while CASA targets set size under a coverage constraint.Related adaptive-computation approaches instead target estimator variance, accuracy, or task reward.Source: §1 · pp. 2–3

2 SETUP AND PRELIMINARIES

The section sets up conditional response distributions and conformal prediction sets, then defines set efficiency and conditional coverage as distinct evaluation properties. It describes PCP sets built from generated samples and explains how missed modes can inflate sets or leave inputs under-covered.

2 SETUP AND PRELIMINARIES

  • A response Y has conditional distribution P_x given input X = x, and a nonconformity score measures discrepancy between a candidate response and the model prediction.The section gives Euclidean prediction error as an example score.Source: §2 · p. 3
  • Efficiency is expected prediction-set size, while conditional coverage is the probability of coverage given x; marginal coverage does not control coverage heterogeneity across inputs.Set size may be measured by Lebesgue measure for continuous outcomes or cardinality for discrete outcomes.Source: §2 · p. 3
  • PCP scores a candidate response by its distance to the nearest generated sample and forms prediction sets from balls around generated samples, with radius scaling that may depend on the input.PCP uses r(x) = 1, whereas later adaptive-radius approaches learn r(x) from the input.Source: §2 · p. 3
  • If samples miss the mode containing the realized response, enlarging the conformal radius still spans the low-density gap; pooled misses can inflate sets broadly or leave specific inputs under-covered.Extra samples can have limited benefit for concentrated distributions, motivating allocation of fewer draws to simple inputs and more to complex or multimodal ones.Source: §2 · p. 4

3 METHODOLOGY

CASA allocates samples across inputs to minimize expected set size under marginal-coverage and average-budget constraints. Under separated modes, adaptive allocation can reduce set size relative to uniform allocation because missed modes force larger radii, a cost radius adaptation alone cannot remove.

3.1 Resource Allocation Representation

  • CASA chooses an input-dependent sample count to minimize expected set size subject to marginal coverage and an average sampling budget.The marginal coverage benefit and set-size cost of an additional draw are both characterized by the increase in inclusion probability, with diminishing returns as sample count grows.Source: §3.1 · p. 4

3.2 Proposed Algorithm

  • CASA estimates coverage and size for candidate counts, solves the dual allocation problem, then calibrates the resulting sets for finite-sample marginal coverage.The coverage guarantee assumes the generator and learned allocation are independent of calibration data and the test pair, and calibration and test data are exchangeable.Source: §3.2 · pp. 4, 6
  • The dual decouples allocation across inputs and reduces optimization to a search over two multipliers; at m = 5,000, it takes 0.17 seconds versus 11 seconds for the primal.For fixed dual variables, each input independently selects the candidate count minimizing its priced cost.Source: §3.2 · p. 5

3.3 Theoretical Analysis

  • Under separated modes, adaptive allocation reduces expected set size by at least a factor of Rd/B versus uniform allocation at equal budget.The gain is largest when mode gaps are wide and inputs differ in how many samples they need; input-dependent radii do not close the gap.Source: §3.3 · p. 6
  • Under the separated-modes assumption, uniform allocation uses the worst-case sample count to attain conditional coverage everywhere, while adaptive allocation uses the average count.Even the smallest radius attaining conditional coverage cannot replace samples needed to represent modes separated by gaps.Source: §3.3 · p. 6

4 EXPERIMENTS

Across synthetic and real tasks, CASA reduces uncertainty-set size at matched sampling costs, while generally maintaining coverage and often improving conditional-coverage balance. Its gains extend to other generative conformal methods and are tied to allocating samples according to input complexity.

Synthetic benchmark

  • 53% smaller sets at a fixed budget and 25% fewer samples at the same set size on the emerging-modes synthetic DGP; CASA maintains marginal validity and lowers conditional-coverage error on most DGPs.Figure 4 shows fixed PCP sets bridging gaps between modes while CASA sets stay at the scale of a mode.Source: §4 · p. 7, Figure 4 · p. 7

Other generative conformal methods

  • CASA count allocation shrinks most sets and lowers conditional-coverage error for other generative conformal methods, but does not guarantee lower error when a method already targets it, as with CP2.Table 1 compares fixed counts with CASA allocation at B = 5 and a 90% coverage target; it reports mean set size, paired geometric-mean size change, and MACE.Source: §4 · p. 7, Table 1 · p. 8

Real data

  • On Porto routes, CASA assigns two samples on through-roads and up to eight near junctions, where extra draws cover exits that fixed PCP misses.Figure 5 shows mean allocated samples, one trip, junction-versus-straight-road sample allocation, and fixed PCP and CASA sets.Source: §4 · p. 7, Figure 5 · p. 8
  • 37% smaller mean set area than fixed PCP on Porto routes at the same budget; CASA also reduces protein set area by 13% at the same budget and 24% at equal samples, and uses 28% fewer samples for matched VQA answer-set size at an 80% target.The Porto gain persists at equal realized samples, under a time split, and with a learned generator.Source: §4 · p. 8

Ablation and sensitivity

  • At the same B = 5 budget, input-blind random counts enlarge PCP sets by 6% and leave MACE nearly unchanged, while CASA shrinks sets by 12% and lowers MACE to 7.8 percentage points.Fixed PCP attains 90.0% coverage; CASA retains valid marginal coverage.Source: §4 · p. 8
  • Changing the regression neighbor count or using fixed input-space partitions changes CASA mean set size by less than 1%, preserving its reduction over fixed PCP; evaluations compare marginal coverage, set size, sample count, and MACE at a 90% target.The experiments use synthetic and real datasets and also test count allocation with other conformal methods.Source: §4 · pp. 7–8

5 CONCLUSION

CASA reallocates generator samples across inputs to reduce set size while preserving finite-sample marginal coverage. The paper identifies limits in its input-only allocation, theory, generator support, pilot cost, and objective.

Conclusion

  • CASA minimizes set size under an average sampling budget while preserving finite-sample marginal coverage, and its gains arise when fixed counts miss modes.The proposed next step is to adapt the count using samples already drawn, which could detect missed modes directly.Source: §5 · p. 8

Limitations and extensions

  • The count is chosen from the input before sampling, the theory assumes separated modes, and allocation cannot recover a relevant mode that the generator never samples.Extending the analysis to smooth or heavy-tailed distributions is proposed to clarify when allocation helps beyond representation.Source: §5 · p. 8
  • Estimating coverage and size requires a one-time pilot pool, which can be costly for expensive generators.Source: §5 · p. 8
  • CASA targets set size, so conditional coverage improves only as a by-product; direct targeting and extension to discrete outputs are proposed next steps.Source: §5 · p. 8

A PROOFS AND THEORETICAL RESULTS

The appendix establishes finite-sample marginal coverage for the learned sampling rule and gives properties of the sample-based estimates used in allocation. The estimates are unbiased, variance-reducing conditional expectations with nondecreasing, discretely concave curves.

A.1 Estimation and Coverage

  • The appendix fixes the radius rule for the main definitions and adds radius as an argument when treating the joint variant.Source: §A.1 · p. 12
  • The added coverage and volume from another sample are nonnegative and nonincreasing with the sample count, because the increment is the probability that earlier draws miss a region and the next draw hits it.Integrating this probability over responses and volume gives the corresponding increment properties.Source: §A.1 · p. 12
  • The pool-based estimators of coverage and volume are unbiased and have no greater variance than the corresponding coverage-indicator and volume statistics.Their curves in the sample count, and the nonnegative-weight regressions, are nondecreasing and discretely concave.Source: §A.1 · p. 12
  • Conditioning on training and fitted quantities leaves augmented calibration and test observations exchangeable, so the conformal order-statistic argument gives coverage of at least 1 − α for the learned-count rule.The same argument applies to the joint variant with a learned radius.Source: §A.1 · p. 12

A.2 Optimization

The optimization selects input-specific sample counts and radii to minimize estimated set volume under coverage and average-budget constraints. Its dual prices yield an efficient water-filling solver and characterize the value of additional sampling budget.

A.2 Optimization

  • CASA’s empirical program chooses a distribution over count-radius pairs at each input to minimize mean estimated volume subject to coverage and budget constraints.The joint variant allows each input to select a count and radius; count-only CASA is the special case with a single radius.Source: §A.2 · pp. 12–13
  • The exact two-price dual decomposes across inputs, and water-filling adds draws in order of priced-cost reduction per draw.For fixed coverage price, it chooses the best radius for each count, then allocates counts along each input’s lower convex hull.Source: §A.2 · pp. 13–14
  • A feasible policy is optimal when each input uses only priced-cost-minimizing actions and positive dual prices correspond to binding constraints.Some optimal policy is deterministic at all but at most two learning inputs.Source: §A.2 · pp. 13–14
  • For CASA’s count-only allocation, an exact dual solver is optimal up to a logarithmic factor, and randomization is needed only to meet constraints exactly.The optimal rule uses counts minimizing the priced cost at each input.Source: §A.2 · p. 14
  • The optimal volume is nonincreasing and convex in the budget, with −λ as a subgradient that prices the value of additional draws.The dual identity also expresses fixed PCP’s excess volume as priced regret; under the stated price condition, that regret can translate into saved draws.Source: §A.2 · p. 15

A.3 Proofs for Section 3.3

The proofs relate sample counts to mode representation and calibrated set size in a separated-mode model. They establish when adaptive allocation can avoid large radii and reduce expected volume relative to uniform counts.

A.3 Proofs for Section 3.3

  • When a mode is missed, uniform allocation can require radius at least 2Rϵ, while a feasible adaptive rule can achieve radius at most 2ϵ and volume ratio VA/VF ≤ B/R^d.The comparison applies when E[cB(X)] < 1−α for uniform counts and a rule with mean count at most B satisfies E[cκ(X)(X)] ≥ 1−α.Source: §A.3 · pp. 15–16
  • With finite calibration, the probability of radius at least 2Rϵ tends to zero when ψ > 1−α and to one when ψ < 1−α.Here ψ is the expected covered-mode probability under the count rule.Source: §A.3 · pp. 15–16
  • For equally weighted modes, the minimum count kα(x) grows on the order of J(x) log(1/α), with the stated bounds when kα(x) exceeds kmin.The bounds are (J−1) log(1/α) ≤ kα(x) ≤ J log(1/α)+1.Source: §A.3 · p. 16
  • If uniform counts fall below kα(x) on some inputs, adaptive allocation using kα achieves expected volume at most B ωd(2ϵ)^d and the stated ratio bound.Uniform allocation’s volume is bounded below by P{kα(X)>B} ωd(2Rϵ)^d.Source: §A.3 · p. 16

A.4 Oracle Radii in the Interval Model

The interval-model analysis isolates gains from reallocating counts even when every input already uses its smallest radius attaining target conditional coverage. With bounded variation in interval length, adaptive counts improve expected length at equal average count and coverage.

A.4 Oracle Radii in the Interval Model

  • The oracle rule chooses the smallest radius attaining conditional coverage 1−α for each input and count, then randomizes counts to adjacent integers while preserving their conditional mean.The allocation uses randomized rounding of the specified input-specific count rule.Source: §A.4 · p. 16
  • For the coefficient Aα, the cited passage explicitly gives the exact expression Aα = log(1/α) −2 + 2√α and states that it is positive.Source: §A.4 · p. 16
  • With oracle radii and bounded interval scales, adaptive counts have a leading expected-length gain proportional to Var{s(X)} over fixed counts at the same coverage and average count.The result distinguishes this residual 1/B gain from larger gains due to crossing the mode-representation threshold.Source: §A.4 · p. 16

B.1 Implementation

The implementation estimates conditional coverage and set volume from samples, then solves the allocation problem over candidate counts and radii. Its evaluation uses shared labeled data, fresh prediction-time samples, and test-set measures of coverage, size, and cost.

B.1 Implementation

  • Synthetic studies use a quantile network trained per data-generating process on 2,000 observations, with 1,000 labeled observations shared across methods.Each seed also uses 500 observations for Dm, 500 for Dn, 1,000 for testing, and 4,000 for the conditional-coverage audit.Source: §B.1 · p. 17
  • Conditional coverage and volume are estimated by nearest-neighbor regression using 60 neighbors, with features based on inputs or sample-free summaries of the generator.The reported sensitivity analysis found less than 1% change in mean set size when using 30 or 120 neighbors or a fixed input partition on synthetic tasks at B = 5.Source: §B.1 · p. 17
  • In one dimension, volume estimates are computed exactly from intervals between sample endpoints; in two dimensions, one set of 256 integration points estimates all counts.Test-set areas are computed by disk-union boundary integration.Source: §B.1 · p. 17
  • The allocation uses 100-sample offline pools, counts from {2, …, 2B−2}, and 80 geometrically spaced candidate radii.The budget counts average prediction-time samples, including auxiliary samples, but excludes the offline pool.Source: §B.1 · p. 17
  • Evaluation reports test-set marginal coverage, mean set size, realized mean sampling cost, and a cell-averaged conditional-coverage measure.The conditional-coverage audit uses 10 input cells for scalar inputs and 16 for two-dimensional inputs, with intervals across seeds.Source: §B.1 · p. 18

B.2 Compared Methods

This section compares fixed and adaptive generative conformal methods, then describes synthetic data-generating processes and the protocol used to evaluate them.

B.2 Compared Methods

  • The compared methods vary sample counts, set geometry, or both; CASA allocates counts, while CASA (joint) adapts counts and radii.Fixed PCP uses K = B and one shared radius; the external methods include radius- or shape-adaptive constructions.Source: §B.2 · p. 18
  • On rare modes, Figure 6 compares fixed-count and CASA constructions across budgets B = 3, . . . , 10, counting auxiliary draws in realized calls.Intervals cover 100 seeds; marginal coverage is 89.6–90.5% for every construction except C-PCP, at 91.5–93.2%.Source: Figure 6 · p. 19, §B.2 · p. 19

B.3 Synthetic DGPs

  • The synthetic DGPs vary response structure, including compact-to-extended distributions, changing scale, emerging or separating modes, rare modes, and heavy tails.The protocol uses budgets B = 3, . . . , 15, 100 seeds, 90% target coverage, and a pool of 100 samples per calibration input.Source: §B.3 · p. 19
  • Figure 7 illustrates calibrated sets for fixed PCP, CASA, and CASA (joint) on four synthetic DGPs; its headings report marginal coverage and mean samples.Panels a–b show test pairs and sets, while c–d show responses and samples at one input; aggregate comparisons are in Figure 3 and Table 1.Source: §B.3 · p. 19

B.4 Taxi Routes

The taxi task predicts a future route displacement from a taxi’s position and recent motion. CASA assigns samples adaptively and reduces set area relative to fixed PCP across the reported budgets.

B.4 Taxi Routes

  • CASA’s mean set area is 0.68, 0.63, and 0.88 of fixed PCP’s at budgets 3, 5, and 10, respectively.Coverage is 90.3–90.4% for CASA and 90.1–90.2% for fixed PCP; Table 2 also reports comparisons at equal realized samples.Source: Table 2 · p. 21, §B.4 · p. 21
  • At equal realized samples, CASA’s mean set area is 0.60 and 0.80 of fixed PCP’s at budgets 5 and 10, respectively.On one split, extra samples covered missed exits and lowered the shared calibrated radius from 63 to 44 m.Source: §B.4 · p. 21, Table 2 · p. 21
  • CASA assigns two samples to through-roads and up to eight near junctions, where route choice can split among exits.The task predicts displacement 300 m farther along the route from position and displacements over the prior 15 s and 60 s; samples come from a nearest-window trajectory library with Gaussian jitter.Source: §B.4 · p. 21

B.5 Protein Backbone Angles

The protein task predicts backbone angles, while the vision-language task forms answer sets for image questions. In both, CASA varies sampling across inputs and reports comparisons with fixed sampling.

B.5 Protein Backbone Angles

  • CASA reduces protein mean set area to 0.76, 0.87, and 0.94 of fixed PCP’s at budgets 3, 5, and 10, respectively.At equal realized samples, the ratios are 0.76 and 0.86; at B = 5, MACE falls from 2.85 to 2.58 points.Source: §B.5 · p. 21, Table 3 · p. 22
  • CASA assigns an average of 3.8 samples to helical residues, 4.8 to extended residues, and 5.8 to residues with ϕ > 0, versus five for fixed PCP.Figure 8 shows sample allocation by Ramachandran-plane position and set area against mean samples; the generator uses ESM-2 embeddings and a library of training residues.Source: §B.5 · p. 21, Figure 8 · p. 22

B.6 Answer Sets for a Vision-Language Model

  • On TextVQA, CASA matches fixed sampling’s set size with 44%, 29%, and 28% fewer samples at B = 3, 4, and 5, respectively.At B = 3, fixed sampling misses the target in three of ten splits, while CASA reaches it in all; Figure 9 compares allocation by question accuracy.Source: Figure 9 · p. 22, §B.6 · p. 23
  • On OK-VQA, CASA’s sets are 11–15% smaller at B = 5–8.The answer-set construction returns distinct sampled answers whose frequencies meet a calibrated threshold; the tasks use Qwen2.5-VL-3B.Source: §B.6 · pp. 22–23

Related papers

Loading 2610.11349v1…