Voronoi Conformal Prediction Without Spending the Calibration Set

Conformal prediction wraps any classifier and returns a set of candidate labels that contains the true label with a promised probability, for example 90%. The promise holds with no assumptions about the model. It only needs a held-out calibration set of labeled examples that resemble the test data. A recent method, Multi-Dimensional Conformal Prediction, makes these sets much smaller. It gives the model several diverse prediction heads, so each candidate label gets a vector of "how wrong does this look" scores. It then divides that score space into Voronoi cells, meaning regions defined by which reference point is nearest. Finally it ranks the cells by how often they contain true labels rather than false ones. On CIFAR-100 at 90% coverage this cuts mean set size to about 15.3, against about 35.3 for averaging the heads and about 22.5 for an optimized weighting of them. The catch is data. The method splits the calibration set in two: one half places the cells and the other sets the threshold. For a clinical cohort of 20 to 100 patients, which is where calibrated uncertainty matters most, that split is expensive.

The proposal is to stop spending calibration points on geometry. Coverage only requires that the rule turning a score vector into a single number be fixed independently of the calibration points. We therefore build the Voronoi partition and its cell ranking from a different source, and give every scarce calibration point to the threshold. That source is either out-of-fold predictions on the training data or a large public dataset from a neighboring domain. Seeds are placed by farthest-first traversal, a greedy rule that repeatedly picks the point farthest from all points chosen so far. The number of cells is set by how much geometry-defining data exists, not by the calibration size. The question is empirical and sharp: how much set-size efficiency survives when the geometry is borrowed rather than fitted on local data, and does it beat simply using all $N$ points with an ordinary one-dimensional score?

Core Claim

At small $N$, splitting the calibration set costs more than it looks. Split conformal with $n$ calibration scores uses the $k$-th smallest score as the threshold, where $k=\lceil (n+1)(1-\alpha)\rceil$ and $\alpha$ is the allowed miss rate. The coverage achieved on a given calibration draw follows a known distribution:

$$ \text{coverage} \mid \text{calibration set} \sim \mathrm{Beta}\big(k,\; n+1-k\big), $$

with variance of roughly $\alpha(1-\alpha)/(n+2)$. This is the standard order-statistic result for exchangeable scores. Take $N=20$ and $\alpha=0.1$. With a 10/10 split, $k=10$ out of $n=10$, so the threshold is the maximum score and sets become nearly trivial. Using all 20 points, the threshold is the second-largest score, and the spread of realized coverage shrinks by about $\sqrt{2}$.

Our claim is that a partition and ranking learned on data that is independent of the calibration set keeps most of the Voronoi method's efficiency gain. Combined with the full calibration budget, it should give smaller and more stable sets than the original split method, its Jackknife+ variant, and one-dimensional scores. Coverage stays exactly valid even when the geometry source is shifted from the local cohort, because the threshold is always set locally.

This is a claim about how to allocate scarce labels, not about a new classifier. We treat the Voronoi ranking as one estimator among several, and we explicitly test whether a simpler learned scalar score does as well.

Where This Sits

The method comes from Multi-Dimensional Conformal Prediction (also indexed as Multi-Dimensional Conformal Prediction). It supplies the self-ensemble heads, which are trained with a cosine-similarity penalty to stay diverse, and the true-to-false cell ranking. It also motivates this work, because its authors name the calibration split as the main small-data limitation. Their answer is Jackknife+ resampling, which they describe as costly. We keep their scoring but move the geometry-fitting data elsewhere.

The seeding rule comes from Intrinsic Dimension Adaptive Partitioning for Kernel Methods. That paper places Voronoi centers by farthest-first traversal so cells follow the data's intrinsic shape. It proves learning rates that depend on intrinsic rather than ambient dimension. Its guarantees are asymptotic, with thousands of points per cell, so here it is only a seeding heuristic, not a guarantee.

Two other Voronoi papers constrain the design:

  • Few-shot Learning as Cluster-induced Voronoi Diagrams shows that prototype classifiers are one-seed Voronoi diagrams and gains 2–5% from richer cells over frozen features. It addresses accuracy, not calibrated sets, and it is the kind of geometry-over-fixed-features design we inherit.
  • Geometry-Aware Probabilistic Circuits via Voronoi Tessellations shows that oblique Voronoi facets make exact integration hard. Our use needs only a nearest-seed lookup, so we avoid that problem entirely.

On the small-sample side, several papers establish that tiny, heterogeneous cohorts are the real deployment regime and that point predictions there are fragile:

We follow the last finding when choosing the base model.

Research Program

Base models. On each MedMNIST task from MedMNIST v2, we fine-tune DINOv2 end to end with $H$ diverse heads, using the diversity loss of the multi-dimensional conformal method. $H$ ranges over 3 to 7, since the original paper reports that cells empty out beyond about 7 dimensions.

Geometry sources. We compare three sources for the partition and ranking.

  1. Split (the original method). Geometry comes from half of the local calibration set.
  2. Out-of-fold training scores. We train $K=5$ copies of the heads, each on four-fifths of the training data. Each copy scores the fifth it did not see, which avoids the overconfidence of in-sample scores. Seeds and cell ranks come from these held-out scores.
  3. Public neighbor data. A model trained on the full public training split is scored on a held-out public pool. That geometry is then applied to a small "local" cohort drawn under a controlled shift, such as color and contrast perturbations or class-prior changes. This mimics a hospital deploying a public model.

For sources 2 and 3, all $N$ local points set the threshold.

Choosing the number of cells. The cell count is chosen by cross-validation inside the geometry source only, never on calibration data.

Analysis. We will measure how the efficiency gap between sources grows as $N$ shrinks and as shift grows. We expect borrowed geometry to lose ranking quality under shift. The bet is that the variance saved on the threshold outweighs that loss below some crossover $N$. Locating that crossover is the main deliverable.

Baselines

Naive reference points. - The full label set, which is trivially covered. - Split conformal with the standard one-dimensional adaptive scores the original paper compares against (RAPS, SAPS), using all $N$ calibration points. This is what a practitioner would do by default, and at very small $N$ it may be hard to beat.

Strongest existing methods. - Multi-dimensional Voronoi conformal prediction in its original split form. - Its Jackknife+ variant, which also reuses every point, only at higher compute cost.

The only reported numbers in our file are on CIFAR-100 at 90% coverage: mean set size about 15.3 for the Voronoi method, 35.3 for uniform head averaging, and 22.5 for weight-optimized blending. We will first reproduce these to validate our implementation. No reported result was found on Lacuna for the method's set sizes on PathMNIST, nor for its Jackknife+ variant anywhere, so we will run both ourselves.

Fairness conditions. All methods share:

  • the same fine-tuned backbone and heads;
  • the same $N \in \{10, 20, 50, 100\}$ local points, with 500 random calibration/test redraws per setting;
  • the same tuning budget, with hyperparameters tuned only on non-calibration data.

Ablations isolating the key ingredients. - Farthest-first seeds versus random and k-means seeds, keeping the cell count fixed. - Borrowed geometry with the split still enforced. This separates the benefit of the data source from the benefit of the extra calibration points.

What counts as winning. Beating the baselines means, at $N \le 50$ and with exact marginal coverage on every setting:

  • a smaller mean set size than both the split and Jackknife+ versions;
  • a narrower 5th–95th percentile band of realized coverage across redraws;
  • being no worse than the best one-dimensional score.

Why not just…?

Why not just use RAPS or SAPS with all $N$ points? This is the honest default. It uses every point and fits nothing extra. The original paper's gains over one-dimensional scores were measured with ample calibration data, so at $N=20$ they may vanish. Our sweep over $N$ reports this crossover directly. If one-dimensional scores win everywhere below $N=100$, that negative result is itself useful guidance for clinical deployment.

Why not just use the Jackknife+ variant the authors already propose? It addresses the same waste of data. However, it refits the partition $N$ times, and its guarantee is weaker, typically $1-2\alpha$ in the worst case, per the standard Jackknife+ analysis. We compare set size, coverage, and wall-clock time at matched $N$. If Jackknife+ matches borrowed geometry at acceptable cost, our contribution narrows to the claim that geometry can come from public data without refitting.

Why not just learn a scalar score with logistic regression or gradient boosting on the out-of-fold score vectors? This is the real threat. The Voronoi ranking is essentially a nonparametric estimate of where true labels are denser than false ones, and a small classifier trained on the same borrowed data estimates the same thing. It plugs into split conformal with the same validity.

We run it as a first-class competitor, trained on exactly the same geometry source. If it matches the Voronoi cells, we will report that the gain comes from reallocating data, not from tessellation, and recommend the simpler scorer. Voronoi cells should win only if the true/false regions are multimodal in ways a smooth classifier averages away, and cell-level diagnostics will show whether that happens.

Why not just average the heads? On CIFAR-100 the original paper already reports 35.3 for head averaging against 15.3 for Voronoi. It stays in our baselines to check whether that gap survives at small $N$.

Decisive Checks

Validity. Across all 500 redraws and all shift levels, the realized-coverage distribution must match the Beta law above for full-$N$ thresholding. Any systematic undercoverage would mean an independence leak in our pipeline.

Crossover location. Plotting set size against $N$ for the split, Jackknife+, borrowed-Voronoi, borrowed-logistic, and RAPS methods should show borrowed geometry winning at small $N$. If the split method or RAPS wins at $N=20$ on PathMNIST and DermaMNIST, the idea fails.

Shift robustness. The public-neighbor setting should degrade set size gracefully as shift grows while coverage stays exact. We will report the shift level at which borrowed geometry stops helping.