Pruning Tokens Without Pruning the Unknown

Vision Transformers, image models that split a picture into patches ("tokens") and let every patch compare itself with every other, pay a cost that grows with the square of the number of patches. The usual way to make them cheaper is to throw away or merge the patches the model considers unimportant. "Unimportant" is decided by the model's own training task, which only ever involved a fixed list of known classes. This proposal argues that this is the wrong rule for any system that must also say "I have never seen this before", a task called open-set recognition. A novel object is, almost by definition, something the known-class model does not find salient. A known-class pruner will therefore tend to discard exactly the patches that carry the evidence of novelty, and it will do so in the early layers, before any downstream detector of unknowns gets to look.

We propose to measure this failure directly, then fix it with a token-keeping rule that adds a cheap "how atypical is this patch?" score to the usual attention-based importance. The number of patches kept is decided per image by an online controller rather than fixed in advance. That controller is a feedback loop of the kind used in streaming hyperparameter adaptation: it spends extra tokens on images whose open-set decision is uncertain and spends fewer on easy ones, while holding average compute at a target budget. The question is whether this recovers full-attention open-set performance at a fraction of the compute, and whether it beats the simple answers: random dropping, uniform downsampling, and a fixed ratio tuned offline.

Core Claim

Current efficient-attention methods choose which tokens survive using closed-set signals. SG-Former's significance map is learned from the supervised classification loss (SG-Former). FastV ranks image tokens by the attention they receive at a fixed layer and drops a fixed fraction (FastV). Neither paper evaluates rejection of unknown inputs. In parallel, the open-set literature motivates using global attention at all: Open Set Recognition using Vision Transformer with an Additional Detection Head attributes the CNN performance ceiling in open-set recognition to the narrow region each convolution sees. It shows a full-attention ViT-B/16 with a distance-based detection head improving TinyImageNet AUROC by 14.6% over CNN methods, but it pays the full quadratic cost.

Our claim has two parts. First, closed-set token reduction costs open-set AUROC much more than it costs closed-set accuracy at the same compute. Second, a pruning score that adds patch-level atypicality, combined with a per-image budget set by an online controller, closes most of that gap. The diagnostic half stands on its own, and if it turns out false, we have learned that the efficiency literature is safe for open-set use. As far as the file shows, no prior work tests either half.

Research Program

The base model is a ViT-B/16 trained on the known classes, followed by the two-stage detection head of the ViT detection-head paper. That head maps features into compact class clusters and rejects an input whose distance to the nearest class centre exceeds a threshold. We insert a reduction step after an early layer $\ell$, in the style of FastV.

For each patch token $i$, the keep score is

$$s_i = a_i + \lambda\, u_i,$$

where $a_i$ is the normalised attention the token receives from the class token at layer $\ell$ (the closed-set importance), $u_i$ is the token's atypicality, and $\lambda$ weights the two. We compute $u_i$ as the Mahalanobis distance of the token's layer-$\ell$ feature from a Gaussian fitted to known-class patch features. The Gaussian lives in a low-dimensional projection, and its covariance is stabilised with Ledoit-Wolf shrinkage, following AGE. AGE uses this tool for whole-image class modelling after offline PCA; we reuse it at the patch level as a cheap novelty prior.

Pruned tokens are not deleted. They are averaged into a single summary token, so the global receptive field is preserved in coarse form, as in SG-Former's background aggregation.

The keep ratio $r$ for each image comes from a controller. It reads the evidence of a first, cheap pass at the minimum ratio $r_{\min}$. If the detection head's distance to the nearest centre falls inside an uncertainty band around the rejection threshold, the image is re-run at a ratio $r_{\max}$. The band width $\beta$ is the hyperparameter that trades compute for accuracy. Rather than grid-searching it, we tune it online by a dual update:

$$\beta_{t+1} = \beta_t - \eta\,(c_t - C),$$

where $c_t$ is the measured compute of image $t$, $C$ is the target average compute, and $\eta$ is a step size. This holds average cost at $C$ without labels. The rejection threshold itself is tracked online from running known-class distance statistics. This follows the streaming lesson from ABACOC and Stream-51 that boundaries fixed offline go stale under drift.

To avoid the hardware gap FastV notes, the kept tokens are gathered into a dense, shorter sequence and images are batched by their ratio. We report wall-clock time as well as FLOPs.

Baselines

The naive reference point is the unmodified full-attention ViT-B/16 with the detection head. It defines the accuracy ceiling and the compute we are trying to cut. No reported absolute AUROC for this model was found on Lacuna, only the +14.6% TinyImageNet margin over CNNs, so we reproduce it ourselves under a fixed training recipe shared by every variant.

The strongest existing competitor is closed-set token reduction applied to the same backbone and head. This means FastV-style attention ranking at layer $\ell$ with a fixed drop ratio, plus a SG-Former-style significance-guided aggregation variant. These are the methods a practitioner would actually deploy to cut cost, and they are what our claim says is unsafe. No reported open-set result found on Lacuna for FastV or SG-Former; the reported figures are closed-set (for example, SG-Former-B at 84.7% ImageNet-1K top-1). We run them at matched average FLOPs, with the same frozen detection head, and give each the same tuning budget we give our controller's $\eta$ and $\lambda$.

For the streaming setting, the strongest reported reference is SLDA on Stream-51, with $\Omega_{AUOSC}\approx 0.66$ (Stream-51). For the few-shot setting it is MET, at 76.93% AUROC on 1-shot MiniImageNet (MET). We treat these as context rather than head-to-head targets, because their backbones differ.

The ablations isolate each ingredient. Atypicality score with a fixed ratio tests whether the score alone does the work. Attention score with the adaptive budget tests whether the controller alone does the work. Random keeping and uniform 2×2 pooling of tokens are run at matched FLOPs. Our method beats the field if, at 50% average FLOPs, it keeps open-set AUROC within one point of full attention while the closed-set pruners lose clearly more, and if it beats every ablation at matched compute.

Why not just…?

Why not just keep full attention and accept the cost? For small benchmark images this is a fair answer, and our full-attention baseline reports it honestly. The quadratic term matters once resolution grows: token count rises with image area, so attention cost rises with its square. We therefore also report results at 2× input resolution, where full attention becomes the expensive option the efficiency literature exists to avoid.

Why not just drop tokens at random, or pool uniformly? This is the real threat. Uniform pooling never systematically ignores a region, so it may preserve novelty evidence better than salience-based pruning does. SG-Former reports that uniform downsampling loses fine detail on closed-set tasks (+3.0 mIoU over Swin-B on ADE20K), but nobody has measured the effect on rejecting unknowns. If random or uniform reduction matches our method at equal FLOPs, we will report that the danger lies in salience itself and that simple reduction suffices. That would still be a useful, decisive finding, and it would retire the controller.

Why not just tune a fixed keep ratio offline per compute budget? FastV's authors themselves flag fixed ratios as suboptimal across inputs, but that is an argument, not a measurement. Our fixed-ratio-plus-atypicality ablation, given the same tuning budget, settles it. If it matches the adaptive version, we drop the controller and keep the score.

Why not just threshold softmax confidence and skip the detection head? MET's gain over SnaTCHer and the detection-head paper's gain over CNN methods both indicate that softmax confidence is a weak rejection signal. We include max-softmax as an extra rejection rule under every pruning scheme. This shows whether the pruning damage is specific to distance-based detectors.

Proposed Experiments

The first experiment is the diagnostic. On the TinyImageNet, CIFAR+10/+50 and ImageNet-200 open-set protocols used by the detection-head paper, we plot closed-set accuracy and open-set AUROC against kept-token fraction for each reduction method. The decisive check is whether the AUROC curve falls faster than the accuracy curve for attention-ranked pruning, but not for random pruning.

To target the mechanism directly, we build a "small intruder" split from the VOC/COCO open-world partition used by UC-OWOD. It contains images dominated by a known-class object that also hold a small object from an unknown task, and the image-level label is "contains an unknown". We also log what fraction of the intruder's patches each method keeps.

CUB is the hard case where unknowns closely resemble knowns, which MET identifies as the limit of what can be discerned. Here we expect atypicality to help least, and we report the result either way.

Finally, we run the full system on Stream-51 under single-pass streaming with drift. This tests whether the online threshold and the budget controller hold the target compute and keep $\Omega_{AUOSC}$ from degrading over the stream, compared with the same model using thresholds fixed offline.

The proposal succeeds if three things hold. Salience pruning must measurably hurt open-set recognition more than closed-set accuracy. Our score must recover most of that loss at matched compute. And the adaptive budget must add a gain beyond the best fixed ratio. Failing the first ends the project cheaply. Failing the third reduces it to a scoring rule.