Unbiased Training with Pruned Forward Passes

Training a Transformer costs the same for every token of every example, even though most images contain empty background and most examples are already learned. Two research lines attack this waste separately. Progressive token pruning drops or merges uninformative tokens as they pass through deeper layers. Importance sampling replaces the usual uniform random choice of training examples with a choice that favors informative ones. Today these lines do not meet. Token pruning mostly saves compute at inference time. Sample selection decides only whether an entire example is kept or thrown away.

We propose to treat a token-pruned forward pass as a cheap but slightly wrong gradient estimate of the full model. A small, randomly chosen fraction of examples also receives a full-token pass. On those examples, the measured difference between the two gradients corrects the error. In two sentences: most of each batch goes through a physically shortened network, and a few examples get both the short and the full pass so that the error from pruning can be measured and subtracted. The result is an unbiased estimate of the dense model's gradient at a fraction of the cost. The same per-example statistics then decide, during training, which examples to skip, which to prune, and how aggressively to prune.

Core Claim

Token pruning changes the function the network computes, because attention is nonlinear in its inputs. For that reason, reweighting kept tokens, the way Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization (DPPO) reweights kept completions in reinforcement learning, cannot make intra-network pruning unbiased. What can be made unbiased is a two-level estimator in the style of multilevel Monte Carlo, an established statistical technique for combining cheap and expensive estimates.

Let $g_i^D$ be example $i$'s gradient under the dense network and $g_i^P$ its gradient under the pruned network. Both are taken with respect to the same weights. Each example in a candidate pool receives a pruned pass with probability $p_i$. Independently, it receives a paired dense-and-pruned pass with probability $r_i$. The gradient estimate is

$$\hat g = \sum_i \frac{\mathbb{1}[A_i]}{p_i}\, g_i^P + \frac{\mathbb{1}[B_i]}{r_i}\,\big(g_i^D - g_i^P\big),$$

where $A_i$ and $B_i$ are the two independent selection events. Taking expectations gives $\mathbb{E}[\hat g]=\sum_i g_i^D$ exactly.

The estimator's variance is roughly $\sum_i \|g_i^P\|^2/p_i + \|g_i^D-g_i^P\|^2/r_i$. Let $c_P$ and $c_D$ be the per-example costs of a pruned and a dense pass. Minimizing that variance under a fixed compute budget gives the classical cost-aware allocation:

$$p_i \propto \frac{\|g_i^P\|}{\sqrt{c_P}}, \qquad r_i \propto \frac{\|g_i^D-g_i^P\|}{\sqrt{c_D+c_P}}.$$

This form follows from Lagrangian minimization of a sum of $v_i/q_i$ terms under a linear cost constraint.

The claim is that well-designed pruning keeps the discrepancy $\|g_i^D-g_i^P\|$ small for most examples. If so, $r_i$ can be a few percent, and the method trains a dense model with nearly the cost of training a pruned one. The first allocation is ordinary sample importance sampling. The second is new: it spends dense compute where pruning hurts the gradient most. The running average of the discrepancy also works as a schedule controller. It allows heavier pruning when pruning is harmless and backs off when it is not. This responds to the static schedules of Token Merging: Your ViT But Faster and DynamicViT.

Relation to Prior Work

Three lines of prior work motivate the gap by stopping short of training-time savings with a dense-model guarantee.

DynamicViT learns which tokens to drop using a small prediction network. During training, however, it masks tokens rather than deleting them, so training is not faster. Training Noise Token Pruning replaces token deletion with Gaussian noise during training. It still computes every token and saves compute only at inference. Both methods train a model that is meant to be pruned. We instead train a model that is correct as a dense model and keep tensors physically short during training.

Training-Trajectory-Aware Token Selection removes easy tokens from the loss without any reweighting. That shows dropping easy tokens can help reasoning distillation, but it leaves the bias of the update uncharacterized. Our estimator makes that bias explicit and removes it.

Sample-level methods supply the importance-sampling machinery, and their limits shape our design. Not All Samples Are Created Equal gives a cheap upper bound on per-example gradient norm from last-layer pre-activation gradients. It also gives a rule for switching importance sampling off when the variance gain does not cover the overhead. We reuse both, computing the bound from the pruned pass so it is nearly free.

Understanding the Training Speedup from Sampling with Approximate Losses (SIFT) filters examples using an early-layer preview loss. It hits a convergence floor because its selection is greedy and unweighted, and it runs every kept example at full length. Our method makes graded rather than binary decisions, with skip, prune, and paired-dense as the three options. Its weights are unbiased by construction.

Carpe Diem shows that informativeness is transient, so we track discrepancies over a sliding window rather than over the full training history. Prioritized Training on Points that are Learnable, Worth Learning, and not yet Learnt warns that high-loss examples are often noise. We therefore cap $p_i$ and mix in a uniform floor, so that noisy examples are not over-sampled.

Two papers constrain the design. Which Tokens to Use? finds that plain attention Top-K pruning matches learned predictors on classification. We therefore use cheap attention-based or merging-based pruning as the cheap pass rather than inventing a new scorer. D²Pruner shows that attention scores carry positional bias. In our method, such scoring errors appear as larger discrepancies. The correction term absorbs them rather than letting them silently bias training.

Research Program

We will build the estimator for two architectures, a ViT classifier and a BERT-style encoder. The cheap pass will use a physically shrinking pruner with a constant per-layer reduction, either ToMe-style merging or [CLS]-attention Top-K. A constant reduction keeps tensor shapes fixed within a batch and avoids the variable-length problem noted for Adaptive Token Sampling.

Each step works as follows. A candidate pool is scored using the pruned pass's last-layer gradient bound and a sliding-window estimate of each example's discrepancy. Examples are then assigned to the skip, pruned, or paired-dense level. Paired examples share early layers up to the first pruning point, which lowers the paired cost below $c_D+c_P$.

A controller adjusts the pruning rate to keep total estimator variance per unit of compute near its minimum. This is the variance-aware schedule called for in Gap 4 of the research file.

The analysis has three parts. We will measure the bias of the pruned-only gradient (the case $r_i=0$) against the dense gradient across training. We will check whether the discrepancy is predictable from cheap features. We will also determine when variance reduction is too small to pay for itself, applying the switching logic of Not All Samples Are Created Equal.

Baselines

The naive reference is uniform-shuffled dense training with a standard cosine schedule. It runs on the same data, the same hardware, and the same number of hyperparameter-tuning trials, and it is evaluated on wall-clock time to target accuracy. For ImageNet DeiT-S, the dense end point reported in DynamicViT is 79.8% top-1. Beating this baseline means reaching the same dense accuracy in clearly less wall-clock time.

The strongest existing method for faster training via intermediate-layer selection is SIFT from Understanding the Training Speedup from Sampling with Approximate Losses. It reports BERT-base reaching 64% validation accuracy in about 43 hours versus about 57 hours for the baseline, a 24.5% wall-clock speedup. We will rerun SIFT in our codebase with its layer-1 preview and 50% keep rate, under the same hardware and tuning budget. Beating it means reaching 64% faster than SIFT while matching or exceeding its final accuracy, because SIFT's greedy selection has a convergence floor.

On ImageNet we found no reported result on Lacuna for training-time wall-clock speedup from token pruning. DynamicViT and TNT save compute only at inference. We will therefore construct the comparison ourselves.

The importance-sampling baseline is the method of Not All Samples Are Created Equal, which reports a 5% relative test-error improvement over uniform sampling on CIFAR-100 at equal time. It isolates how much of our gain comes from sample selection alone.

The key ablation sets $r_i=0$, training on the pruned gradient alone with importance weights. A second ablation uses uniform $r_i$ instead of discrepancy-proportional $r_i$. These two isolate whether the correction term, and its allocation, are what make the method work.

Why not just…?

Why not just train with token pruning and then fine-tune densely for a few epochs at the end? This two-stage schedule is the most serious threat. It is cheap, simple, and plausibly closes much of the gap. Our method differs in that it never accumulates bias that later has to be undone, and it decides adaptively how much dense compute to spend. We will run the two-stage schedule as a main baseline with its dense fraction tuned to match our total compute. If it matches our dense accuracy at equal wall-clock time, the correction term is not worth its complexity and we will report that. The bias measurements from the ablation with $r_i=0$ will show whether the pruned-only trajectory drifts in ways a short fine-tune cannot repair.

Why not just drop tokens uniformly at random during training? Random dropping is free to compute, and as training-time regularization it may behave better than its inference-time record suggests. That record is poor: Adaptive Token Sampling and Which Tokens to Use? find random dropping degrades faster than attention-guided selection as pruning increases. In our estimator, random dropping can serve as the cheap pass, and the correction keeps it unbiased. The real question is whether attention-guided pruning lowers the discrepancy enough to justify the scoring cost. We will test this by swapping the pruner while holding everything else fixed.

Why not just compose SIFT with off-the-shelf ToMe during training? This combination already gives both sample skipping and token reduction, with no new theory. But it inherits SIFT's convergence floor and adds ToMe's uncorrected bias. Under aggressive compression, ToMe falls to 43.37% on DeiT-B at about 5.8 GFLOPs according to Training Noise Token Pruning. We will run this composition at matched compute. Our method should win mainly in the aggressive-pruning regime, where uncorrected bias is largest.

Proposed Experiments

The vision setting is training DeiT-S and DeiT-B from scratch on ImageNet-1K. We will report wall-clock time and FLOPs to reach the dense baseline's accuracy. We will also report final accuracy evaluated densely and at several ToMe inference rates, since a dense-correct model should prune at least as well at inference as a model trained to be pruned.

The language setting is BERT-base pretraining on BookCorpus and English Wikipedia, using SIFT's 64% validation target. A noisy-label run on Clothing-1M will test whether the uniform floor and the cap on $p_i$ prevent noisy examples from dominating selection. That failure mode is documented for loss-based selection by Prioritized Training on Points that are Learnable, Worth Learning, and not yet Learnt.

Three checks will decide the outcome. First, the variance of the estimator above, measured against true dense full-batch gradients on held-out checkpoints, must stay within a small factor of uniform dense mini-batch variance. That must hold while the average paired fraction $r_i$ stays under about 10%. Second, the method must beat the tuned two-stage baseline and the SIFT-plus-ToMe composition on time to target, with gains concentrated at pruning ratios above 50%. Third, the discrepancy-proportional allocation of $r_i$ must outperform uniform allocation at equal cost. If it does not, the per-example discrepancy carries no usable signal and the method reduces to a simpler control-variate trick.