How Many Labels Does Concept Erasure Need? Sample-Supported Depth for Iterative Deflation

Concept erasure edits a neural network's internal representations so that a protected or spurious attribute, such as gender in a biography encoder or background in a bird classifier, can no longer be read out by a linear probe. Two families of methods compete. The first is iterative deflation: repeatedly find the direction that best predicts the attribute, project it out, and repeat. The second is closed-form erasure, which removes the attribute in a single linear map. Both are fitted on a finite set of examples labeled with the attribute, and both are judged mostly on those same examples or on a development split. Nobody has asked how many attribute labels are needed before the erasure actually holds on new data. This question matters in practice because protected-attribute labels are scarce, costly, and often legally restricted.

The proposal claims that every linear eraser fitted on $n$ labels in $d$ dimensions has an out-of-sample leakage floor set by $d/n$. It also claims that deflation steps beyond the depth the sample can support leave held-out leakage unchanged while steadily deleting main-task information. We will derive this floor, measure it on standard erasure benchmarks by subsampling attribute labels, and build a cross-fitted deflation procedure that accepts a step only when held-out data certifies it against a calibrated null. The result is a sufficiency curve that tells a practitioner, before collecting more labels, what leakage they can expect and how deep to deflate. It also gives a principled account of when iterative deflation or closed-form erasure is the better use of a fixed label budget.

Core Claim

Work in whitened coordinates and consider a binary attribute with population class-mean difference $\delta \in \mathbb{R}^d$. Linear guardedness is equivalent to zero class-mean difference (LEACE: Perfect linear concept erasure in closed form), so what an eraser leaves behind on new data is the part of $\delta$ it failed to remove. An eraser fitted on $n$ labeled points estimates $\delta$ with noise of norm roughly $c\sqrt{d/n}$, where $c$ depends only on class balance. Projecting out the estimate therefore leaves a true residual of size

$$\| \delta_{\text{res}} \| \approx \min\!\left( \|\delta\|,\; c\sqrt{d/n} \right),$$

where the second term is the component of $\delta$ orthogonal to its noisy estimate. A fresh linear probe then retains an accuracy advantage of roughly $\Phi(\|\delta_{\text{res}}\|/2) - 1/2$ over chance, with $\Phi$ the standard normal distribution function.

Three predictions follow and are testable.

First, held-out leakage should fall like $\sqrt{d/n}$ for every method, closed-form or iterative.

Second, extra deflation steps fitted on the same $n$ points cannot lower this floor. After the first step the training-set mean difference is already zero. Later steps instead find directions along which sampling noise happens to separate the classes. There are about as many such directions as the residual dimension allows relative to $n$, so each extra step deletes one essentially random direction of main-task variance. This predicts that the number of steps iterative nullspace projection "needs" grows with $d/n$ rather than reflecting genuine concept dimensionality.

Third, deflating with fresh labels at each step does reach new signal, but it hits the same noise floor at each step's smaller batch size. Pooling labels should therefore beat splitting them across steps when the concept is low-rank. Splitting should pay off only when the concept occupies several directions of comparable strength.

Relation to Prior Work

The motivating evidence comes from the erasure literature. Null It Out: Guarding Protected Attributes by Iterative Nullspace Projection (INLP) introduced the train-a-probe, project-out-its-weights loop. It reported that GloVe gender clustering needed 35 iterations, but it gives no account of how that number depends on sample size. We hypothesize that much of that depth is sample-driven.

Removing Spurious Concepts from Neural Network Representations via Joint Subspace Estimation (JSE) showed that greedy deflation over-removes main-task signal. It adds a statistical stopping test that compares how well a candidate direction predicts the spurious attribute versus the main task. It also reports degradation at correlation 0.95 because counter-examples are scarce, but it states no sample threshold. Our stopping rule asks a different question: is this direction real out of sample? JSE asks which concept the direction belongs to. The two rules can be combined.

The closed-form side is represented by LEACE, which argues that iterative methods accumulate error and replaces them with one optimal oblique projection. Its optimality is a population statement, and its whitening step needs a well-conditioned $d \times d$ covariance estimate. Our analysis applies to LEACE equally. We do not claim deflation beats it in general, only that the comparison has been made without controlling the label budget.

The theory side constrains and supplies method. Black-Box k-to-1-PCA Reductions: Theory and Applications shows that deflation through a one-direction oracle loses nothing under the variance-captured metric and pays $k^{\Theta(\log k)}$ under the angle metric. On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis shows that errors can compound rapidly when eigengaps are small. An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise shows that sequential extraction with per-step noise calibration reaches sample complexity linear in $d$. All three assume $k$ is known and that the target is variance. We transfer their per-step error accounting to a supervised setting where $k$ is unknown and the depth itself must be decided from data.

Research Program

The program has three parts.

The first part is the analysis. We will derive the leakage floor above for binary and multiclass attributes, both for erasers that only estimate class means and for erasers that also estimate a whitening covariance. The covariance-based case adds a condition-number factor that becomes unstable as $n$ approaches $d$. We will also bound the expected collateral damage, measured as the main-task variance removed, from $j$ steps taken beyond the supported depth.

The second part is the procedure, cross-fitted deflation. The labeled set is split. A direction is fitted on one half, and the held-out half is used to test whether the class-mean difference along that direction exceeds what the same procedure produces when attribute labels are permuted. A step is accepted only if it passes. The roles of the halves are then swapped and the results averaged, so no labels are wasted. The permutation null replaces INLP's "dev accuracy at chance" rule. That rule is miscalibrated at small development-set sizes, where chance accuracy fluctuates by about $1/\sqrt{m}$ for $m$ held-out points.

The third part is the sufficiency curve. From a pilot subsample, the fitted $\sqrt{d/n}$ law is extrapolated to predict the label count needed to reach a target held-out leakage. The prediction is validated against actual larger subsamples.

Baselines

The naive reference point is no erasure: the raw representation, probed by a freshly trained logistic regression on a large untouched test split.

The strongest existing method is LEACE. On BERT biography embeddings it reports reducing the true-positive-rate gap from 0.198 to 0.084 with about a 2% loss in profession accuracy (LEACE: Perfect linear concept erasure in closed form). We will run LEACE in three forms. The first is the published version. The second is a version with a shrinkage-regularized covariance, whose shrinkage is tuned on the same held-out labels our method uses. The third is a whitening-free orthogonal projection onto the estimated mean difference.

INLP with development-set stopping and JSE with its own statistical stopping rule are the iterative competitors.

Two ablations isolate our key ingredient. The first applies the same permutation-null test to in-sample statistics, which isolates cross-fitting. The second uses cross-fitting with a fixed threshold instead of a permutation null.

All methods receive the identical attribute-labeled subsample at each budget $n$, from 50 labels up to the full set. All share one held-out split for tuning, receive the same number of tuning configurations, and are evaluated on a test split that no method touches. Beating LEACE means one of two things at matched $n$. Either our method shows lower held-out probe leakage at equal main-task accuracy, or it shows equal leakage with higher main-task accuracy or worst-group accuracy, outside seed-level confidence intervals. That improvement should appear in the regime where $n$ is comparable to $d$, which is where the analysis predicts it.

Why not just…?

Why not just use LEACE with a shrunk covariance? This is the real threat. If shrinkage LEACE matches cross-fitted deflation at every budget, the honest conclusion is that the sufficiency law, not deflation, is the contribution. The proposal is built so that this outcome is still informative. The analysis predicts that a closed-form rank-one eraser and a well-stopped deflation share the same mean-estimation floor. Deflation should differ only when the concept is spread over several directions whose strengths must be detected one at a time, which is the multiclass and GloVe settings. The experiments report both regimes separately.

Why not just stop INLP when development accuracy reaches chance, as the original paper does? At small $n$ the development set is small. Chance-level accuracy is then a noisy target, and a probe trained in fewer dimensions than samples can always separate its training data. If our account is right, INLP's step count on GloVe should rise as labels are removed while held-out leakage stays flat. Showing that pattern directly tests this alternative.

Why not just collect more labels? Often this is the right answer, and the sufficiency curve says how many labels are needed. Its value is predicting that number from a pilot instead of discovering it after collection. The extrapolation check, where a curve fitted at small $n$ is compared with observed leakage at large $n$, decides whether that prediction is trustworthy.

Why not just project once? INLP's GloVe result already shows a single step leaves residual gender information when the probe is a max-margin classifier. Our analysis instead predicts that a single mean-difference projection is enough for a binary attribute up to the noise floor. Running both on GloVe tests which reading is correct.

Proposed Experiments

The first testbed is the 20-dimensional synthetic subspace task from JSE, extended to $d$ up to 768 with planted concept rank 1 to 8 and controllable correlation with the main task. Here the residual $\delta_{\text{res}}$ is known exactly, so the $\sqrt{d/n}$ law and the collateral-damage bound can be checked directly.

The real benchmarks are BERT embeddings on the Bios corpus, GloVe gender debiasing, and Waterbirds and CelebA embeddings. On Bios we track true-positive-rate gap and profession accuracy. On GloVe we track V-measure and SimLex-999. On Waterbirds and CelebA we track worst-group accuracy. For Waterbirds and CelebA, no reported numerical result was found on Lacuna, since JSE reports them only in figures, so we will re-run all baselines ourselves.

The decisive checks are as follows. Held-out leakage plotted against $n$ should follow the predicted slope for all methods. The INLP step count should scale with $d/n$. Accepted cross-fitted steps beyond the first should appear only when the planted concept rank exceeds one. A curve fitted on 10% of labels should predict leakage at full data within its confidence band. If held-out leakage instead keeps falling with uncertified extra steps, the core claim is wrong.