When a model is checked for fairness across combinations of protected attributes such as race × sex × age × disability × region, the number of subgroups doubles with every binary attribute. Most of these cells contain a handful of people or none. No per-cell statistical test can say anything about them. Current practice either drops them below a minimum-size cutoff or falls back on coarse marginal groups, and the people in the smallest intersections end up with no guarantee at all. This proposal treats the collection of subgroups as points in a hidden low-dimensional space, borrowing the latent space models used for social and biological networks. In those models, two nodes are linked when they sit close together. Here, two subgroups are "close" when the model treats them alike. If that geometry exists and can be verified, a sparse cell can inherit a certified bound from its well-measured neighbors through the triangle inequality. If the geometry does not exist, the method should say so and abstain rather than smooth bias away.
In two sentences: we estimate how similarly a model behaves on each pair of data-rich subgroups, test whether those similarities fit a low-dimensional metric space, and only if they do, use distance in that space to put calibrated error bars on subgroups too small to audit directly. How many subgroups can be audited then depends on the dimension of that space rather than on $2^q$, so measuring the dimension becomes the central empirical question.
Core Claim
On the Epistemic Limits of Personalized Prediction proves that verifying a 1% per-group benefit becomes statistically impossible past roughly 19 binary attributes, even with a sample the size of Earth's population. That bound is minimax over unconstrained distributions, and the authors note that structural assumptions could move it. We do not contradict the result. We make the structural assumption explicit and falsifiable. Let $u(g)$ be a disparity quantity for subgroup $g$, such as its false-negative rate minus the population rate. Let $z_g$ be the subgroup's position in a latent metric space with distance $d$. The assumption is
$$|u(g) - u(h)| \le L\, d(z_g, z_h),$$
where $L$ is a Lipschitz constant estimated from data. Under this assumption, a radius-$\varepsilon$ cover of a $d$-dimensional latent region needs on the order of $(1/\varepsilon)^{d}$ anchor cells (the standard covering-number count for a bounded $d$-dimensional set). That figure, not $2^q$, sets how much data an audit needs.
The novelty has two parts. The first is to learn the metric from model behavior and test it before using it, with tools from latent-space network inference. The second is to turn it into intervals whose coverage is calibrated on held-out cells. Prior intersectional methods treat subgroups in one of three ways: as independent bins (Size-adaptive Hypothesis Testing for Fairness), as half-spaces over attributes (Preventing Fairness Gerrymandering), or as correlation-based attribute blocks (Bounding and Approximating Intersectional Fairness through Marginal Fairness). None asks whether subgroups lie in a metric geometry, and none checks that assumption.
Research Program
Stage 1: anchor distances. We first choose "anchor" subgroups with enough samples (several hundred) to estimate the model's behavior profile reliably. A behavior profile is the joint distribution of score and label, summarized by positive rate, error rates and calibration across score bins. Between every pair of anchors we estimate a distance, such as a Wasserstein distance between profiles, together with its bootstrap uncertainty. This yields a weighted graph over anchors.
The distance is defined by behavior rather than by Hamming distance between attribute vectors, for a reason documented in link prediction. Revisiting Link Prediction: a data perspective shows that structural proximity and feature proximity are often incompatible, so nodes similar in attributes need not be similar in how they connect. By analogy, two subgroups one attribute apart may be treated very differently, which is exactly the high-order interaction that intersectionality is about.
Stage 2: test the geometry. Next we test whether the anchor graph is consistent with a low-dimensional space of constant curvature. Constant curvature means flat, sphere-like (clustered) or hyperbolic (tree-like and hierarchical). We adapt the spectral test of Identifying the latent space geometry of network models through analysis of curvature. That paper estimates curvature and dimension from a matrix of distances between cliques, which serve as pseudo-points, using subsample bootstrap. Its known weakness is a dependence on finding dense cliques in sparse graphs, which does not bite here: anchors already supply direct distance estimates. We add a simpler check in the spirit of The Geometric Block Model, whose triangle-based recovery works because geometry forces transitivity. The check is the rate of triangle-inequality violations among anchor triples beyond bootstrap noise. If the test rejects every low-dimensional geometry, the procedure abstains for sparse cells and reports this. That outcome is itself informative evidence that the Paes et al. wall applies to the model.
Stage 3: place sparse cells. We learn a map $f$ from an attribute vector to a latent position, fitted only on anchors. The map is a small network constrained to the curvature selected in Stage 2. Like the amortized mappings in Structured Embedding Models for Grouped Data, it shares strength across groups. Unlike that paper's hierarchical Gaussian prior, which its authors acknowledge treats groups as unordered labels, our map must respect a tested metric. A sparse cell $g$ with $n_g$ samples receives an upper bound
$$U(g) = \min\Big( U_{\text{own}}(g),\; \min_{h \in \text{anchors}} \big[\hat u(h) + s_h + \hat L\, d(f(a_g), z_h)\big] + c_\alpha \Big),$$
where the terms are defined as follows. $U_{\text{own}}$ is the cell's own small-sample credible bound, taken from SAFT's Dirichlet-multinomial interval. $\hat u(h)$ and $s_h$ are the anchor's estimate and standard error. $a_g$ is the cell's attribute vector. $c_\alpha$ is a split-conformal correction computed on held-out anchors that were artificially subsampled down to sparse sizes. That correction is what makes coverage over cells an empirical guarantee rather than a hope.
Stage 4 (secondary): use the bounds in training. The certified bounds for cells below the minimum-size cutoff can be added as constraints to an active-subgroup training method such as Doubly-Regressing Approach for Subgroup Fairness. That would give the excluded long tail some explicit protection. This stage runs only if Stages 1–3 succeed.
Baselines
Per-cell testing. The naive reference is per-cell auditing with the SAFT procedure of Size-adaptive Hypothesis Testing for Fairness. It combines a Wald test for large groups with Dirichlet-multinomial credible intervals for small ones, and the two agree once groups reach roughly 30–50 people. It is run on exactly the same cells and the same model predictions. It represents "use only each cell's own data." Our method beats it if intervals are narrower at matched empirical coverage on cells below 30 samples.
Marginal bounds. The second baseline is the marginal and total-correlation estimator $u_I^{(q^*)}$ of Molina and Loiseau (Bounding and Approximating Intersectional Fairness). It reported faster convergence than Bayesian estimators on the 1990 Census, and it is the strongest existing method that says something about every intersection without per-cell data. We run it on identical attribute subsets. Their bounds are acknowledged to be loose, so beating them means tighter bounds at equal or better coverage, not merely tighter bounds.
Multilevel regression. The strongest competitor for point estimates is a hierarchical Bayesian model of cell disparity with random effects for main effects and all pairwise interactions. This is the standard small-area estimator; we found no paper on Lacuna applying it to this task, so it is described rather than cited. The shrinkage of S-EFE is the cited analogue. It gets the same anchors, the same held-out calibration split and a tuning budget matched to ours in GPU-hours and hyperparameter trials. Its posterior intervals also receive the same conformal correction, so neither method wins on calibration alone.
Auditor search. For finding the worst subgroup we include the learner-auditor search of Preventing Fairness Gerrymandering. It finds a worst-case half-space over attributes but issues no per-cell certificates.
Ablations. Two ablations isolate the key ingredient. The first replaces the learned behavioral metric with Hamming distance over attributes. The second removes the Stage 2 test and always transfers bounds. The second ablation is how we will show that the test, not just smoothing, prevents hidden bias.
Reported numbers. We found no reported result on Lacuna for interval coverage or width on sparse intersectional cells for any of these methods. The closest reported numbers concern auditing, not certification. Auditing a marginally fair model on Communities and Crime exposed a subgroup 3.5 times more unfair than marginal disparities suggested (Preventing Fairness Gerrymandering). Mixed-integer optimization typically needed fewer than 50 subgroup constraints on Folktables (Intersectional Fairness via Mixed-Integer Optimization). We will therefore establish all baseline numbers ourselves under one protocol.
Why not just…?
Why not just fit a multilevel regression with interaction terms? This is the real threat. On cells whose disparity is mostly additive in the attributes, it will probably match us on point estimates. Two things differ. First, a pairwise-interaction model has no way to represent a disparity that appears only at a three-way or higher conjunction. A behavioral metric can place such a cell far from its one-attribute-away neighbors. Second, the multilevel model has no built-in test of whether its own structure holds. The planted high-order disparity experiment below settles this. If multilevel regression matches our coverage there, the contribution shrinks to the geometry test and the dimension measurements, and we would report it that way.
Why not just use SAFT's Bayesian intervals on each cell? SAFT itself shows that tiny cells sit in a zone with no statistical power: even a 100% observed gap cannot reject equal treatment. Molina and Loiseau find that Bayesian estimators in this regime are dominated by their priors. Borrowing information across cells is therefore the only route to informative intervals. The open question is how to borrow safely.
Why not just bound intersections through marginals? Molina and Loiseau's bounds are exact under independent attributes, but they are loose in practice and degrade when marginals are uninformative. Our comparison on the 1990 Census uses the same 100 subsets of 8 attributes. It will show whether a learned geometry tightens bounds where total-correlation bounds are pessimistic.
Why not just drop small cells, as DRAF does? Truncation is exactly what leaves the long tail unprotected. The 3.5× gerrymandering result shows that unmonitored cells can hide severe bias. Our Stage 4 treats truncation as a starting point and adds certified constraints for sub-cutoff cells.
Proposed Experiments
Semi-synthetic ground truth. The decisive experiments use data where truth is known. On Folktables California (ACS Income and Public Coverage) and on the 2.4-million-record 1990 Census, many cells are large enough to have accurately known disparities. We subsample those cells to 3–30 records to create realistic "pseudo-sparse" cells, run every method, and score each against the full-data value. Metrics are empirical coverage of the 95% upper bound across cells, median interval width, and the fraction of cells receiving a non-trivial bound, meaning "audit reach."
Planted bias. The first decisive check plants extra error into a handful of three- and four-way conjunctions while keeping marginal and pairwise statistics unchanged. A safe method must either cover these cells or abstain. Hamming smoothing, multilevel regression and the no-test ablation are expected to under-cover them. The full method succeeds only if its geometry test or its intervals catch them.
Dimension predicts reach. The second check concerns the scaling claim. Across tasks and models, it asks whether the latent dimension estimated in Stage 2 predicts audit reach as the number of anchors grows. The covering-number argument predicts reach rising faster when the estimated dimension is lower. A null correlation would undercut the central claim.
Extreme sparsity. We then stress-test on Communities and Crime, with 18 protected attributes and $2^{18}$ potential cells, and on CelebA, with 20 binary attributes. On these datasets we report which curvature is selected, how often the procedure abstains, and how the certified worst-cell bound compares with the worst subgroup found by the learner-auditor search. That comparison is a sanity check: a certified bound below a discovered violation would expose a coverage failure.
Training (conditional). If certification holds up, we add sub-cutoff bounds to DRAF training on Communities and Folktables. We report accuracy, worst anchor disparity and worst certified sparse-cell bound against unmodified DRAF.
References
- On the Epistemic Limits of Personalized Prediction
- Size-adaptive Hypothesis Testing for Fairness
- Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
- Bounding and Approximating Intersectional Fairness through Marginal Fairness
- Revisiting Link Prediction: a data perspective
- Identifying the latent space geometry of network models through analysis of curvature
- The Geometric Block Model
- Structured Embedding Models for Grouped Data
- Doubly-Regressing Approach for Subgroup Fairness
- Intersectional Fairness via Mixed-Integer Optimization