Multimodal language models, which read an image as hundreds of "visual tokens" (small patch embeddings fed to a language model alongside the text), spend most of their compute on those tokens even though many of them show blank walls or sky. Current methods for shrinking this set make three separate, hand-set decisions. They decide which tokens to delete, which to average together, and how many to keep in total. The keep count is usually a fixed ratio for every image. We propose to make all three decisions at once by solving a single small optimization per image: an unbalanced optimal transport problem. Optimal transport computes the cheapest way to move probability mass from one set of points to another. The unbalanced version is also allowed to throw mass away, at a price.
In our formulation, each original token starts with mass proportional to how much the text query attends to it. Tokens whose mass the solver chooses to destroy are pruned. Tokens whose mass flows onto a retained token are merged into it. Retained tokens that end up receiving almost no mass are dropped, so the number of surviving tokens varies from image to image. An entropy penalty makes the problem smooth and solvable in a few dozen GPU matrix scalings (the Sinkhorn algorithm), so the method needs no training and runs as a plug-in at inference time.
Core Claim
A single entropic unbalanced transport solve, with attention-derived source mass and a norm-preserving merge, should match or beat the best training-free pruning and merging methods at equal average token count. It should do especially well on text-heavy and multi-object images, where deleting low-attention patches is known to hurt. As a by-product, it should produce a per-image token budget that tracks visual complexity.
The objective is the standard entropic unbalanced transport problem. Here $a$ is the attention-derived mass on the $m$ original tokens, $b$ is a uniform prior mass on $k_{\max}$ candidate retained tokens, $C$ is a cost matrix of feature distances, $P$ is the coupling (the transport plan), $H(P)$ is its entropy, and the two KL terms charge for mass that is created or destroyed:
$$\min_{P \ge 0} \; \langle P, C\rangle - \gamma H(P) + \tau_a \,\mathrm{KL}(P\mathbf{1}\,\|\,a) + \tau_b\,\mathrm{KL}(P^\top\mathbf{1}\,\|\,b).$$
The small $\tau_a$ regime makes it cheap to destroy source mass, which amounts to pruning. As $\tau_a, \tau_b \to \infty$, the balanced problem is recovered, which amounts to merging everything. Each retained token $j$ is rebuilt as the coupling-weighted average of its sources. That average is then rescaled to the largest norm among its main contributors, following the maximum-norm interpolation of Token Fusion, because plain averages shrink feature norms and drift off the model's learned feature distribution.
Relation to Prior Work
Three existing papers apply optimal transport to token reduction, and each fixes a different piece that we leave free.
OTPrune selects a subset of tokens to minimize a 2-Wasserstein distance to the full set. It approximates both sets as Gaussians, which gives a log-determinant greedy selection, and it assigns uniform mass to every token. It prunes only, uses a fixed budget, and names attention-weighted mass as unexplored future work. We solve the discrete problem directly with non-uniform mass, merge instead of delete where merging is cheap, and let the budget float.
CoverPrune poses selection as transport coverage for 3D models. It depends on 3D coordinates and a greedy heuristic, and it also only prunes.
AVIOT is the closest method. It solves balanced entropic transport from video tokens to a fixed number of learned target tokens and rebuilds each target as a weighted average of its sources. Balance forces every background token's mass into the targets. The fixed target count and the need for fine-tuning are exactly what we remove. We treat AVIOT as the source of the transport-and-average mechanism and our unbalanced relaxation as the change that makes pruning and adaptive budgets fall out of the same solve.
Sparse Sinkhorn Attention uses Sinkhorn balancing to sort blocks and truncate them. It is trained end-to-end and works at block granularity, so it motivates rather than competes with this work.
The solver itself comes from the unbalanced transport literature: Sinkhorn Divergences for Unbalanced Optimal Transport and Structured Matching via Cost-Regularized Unbalanced Optimal Transport. In the unbalanced case, the scaling updates simply become $u \leftarrow (a/Kv)^{\tau_a/(\tau_a+\gamma)}$ and the analogous update for $v$. Two known failure modes of entropic transport, both reported in Sinkhorn Distances and Fast Computation of Wasserstein Barycenters, constrain the design:
- Underflow at small $\gamma$, which we handle with log-domain updates.
- Over-blurring at large $\gamma$, which is why we sweep $\gamma$ and expect a sharp optimum rather than monotone gains.
Research Program
We insert the operator in the setting of FastV, inside the language model after a shallow layer $K$ (default 2). There, the attention from text tokens to image tokens is already available and is question-dependent. The source mass $a$ is that attention, smoothed with a temperature. This smoothing blunts the "attention sink" outliers that OTPrune identifies as a source of noise.
The $k_{\max}$ candidate retained tokens are chosen by attention-weighted farthest-point sampling, so that small high-attention regions such as text lines are guaranteed a candidate. The cost matrix is the cosine distance between the layer-$K$ keys, the same descriptor used by Token Merging. After 20–50 log-domain iterations, we drop candidates whose received mass falls below a threshold $\epsilon$ and rebuild the survivors with the norm-preserving average. Positions of merged tokens take the mass-weighted mean of their sources' rotary positions. At $m=576$ and $k_{\max}\le 192$, each iteration is a matrix-vector product with roughly $10^5$ entries, so overhead should be negligible next to one language-model layer. We will measure this rather than assume it, and will use FlashSinkhorn-style fused kernels only if needed.
The analysis side asks whether the three knobs behave as the theory says:
- $\tau_a$ should trade pruned mass against merged mass.
- $\epsilon$ and $\tau_b$ should control average budget.
- The per-image survivor count should correlate with independent complexity proxies, such as object count and amount of rendered text.
Baselines
The naive reference is the unmodified LLaVA-1.5-7B/13B and LLaVA-1.6-7B with all 576 (or more) tokens. It gives the accuracy ceiling and the FLOP and latency denominator. A second naive point is random token dropping at matched average count, which shows how much any selection signal is worth.
FastV (An Image is Worth 1/2 Tokens After Layer 2) drops the lowest-attended image tokens after layer $K$. It shares our insertion point and our attention signal, so it isolates what transport adds over ranking. It will be run at the same $K$ and at the same average token count our method produces.
OTPrune is the strongest existing transport-based, training-free method on this exact model family and benchmark suite. The file reports that it beats FastV and DivPrune across 11 benchmarks, the latter with Wilcoxon $p=0.028$. It gives no raw per-benchmark numbers ("no reported result found on Lacuna" for its individual scores), so we will rerun it at matched token budgets.
DyMU (DyMU) is the strongest dynamic-length competitor. Its reported figure is that the DyMU-mid configuration preserves 99.2% of original LLaVA-1.5 performance with 4.3× fewer attention-block FLOPs, averaged over a suite including GQA, MMBench, POPE, and Video-MME.
ToMe-style bipartite merging is the standard merge baseline, and DivPrune is the diversity baseline. All methods get the same models, the same prompts, and a hyperparameter sweep of equal size (at most 20 configurations) on a held-out slice of each benchmark's training or dev split.
"Beating" OTPrune and DyMU means one of two things. The first is higher mean relative accuracy across the suite at equal average tokens. The second is equal accuracy at fewer tokens, with a measured decoding-latency reduction that is not worse than FastV's.
Three ablations isolate the key ingredient:
- Balanced entropic transport with the same attention mass and a fixed $k$. This is essentially AVIOT's mechanism made training-free, and it tests whether unbalancedness matters.
- The unbalanced solve with uniform source mass, which tests whether attention mass matters.
- Plain averaging instead of norm-preserving merging, which tests the Token Fusion correction.
Why not just…?
Why not just prune by attention and fold each dropped token into its nearest kept token? This is the most serious threat. It is essentially EViT's fusion (EViT), generalized from one fused token to many, and it costs almost nothing. Our method differs in two ways. The retained set's masses are balanced against the attention mass, so one kept token cannot swallow a whole background. The soft plan also lets a boundary patch split its mass between neighbours. We will implement this "hard top-$k$ plus nearest-kept merge" baseline with the same norm-preserving rebuild and the same candidate set. If it matches us within noise, then entropy and transport add nothing beyond clustering, and we will report that as the finding.
Why not just set the budget by keeping tokens until they cover, say, 95% of the attention mass? This gives a dynamic budget for free and is a real threat to our adaptive-budget claim. We will compare the two at matched average token counts. We will also check which budget correlates better with per-image accuracy loss relative to the full model. Our expectation is that attention mass alone undercounts images with many small, weakly attended but necessary regions, such as OCR crops. If the cumulative-attention rule wins there, we drop the adaptive-budget claim and keep only the merge component.
Why not just use OTPrune, since it already optimizes a transport objective? OTPrune's Gaussian approximation summarizes the tokens by a single mean and covariance. That summary cannot distinguish two objects from one blurred object, and the method discards non-selected tokens outright. The discrete solve has neither limitation. We test this directly by splitting benchmark images into bins by detected object count. If our advantage does not grow with object count, the Gaussian approximation is adequate and our gain, if any, comes from merging and the attention mass instead.
Decisive Experiments
The main evaluation covers GQA, MMBench, MME, POPE, ScienceQA-IMG, SeedBench, MMMU, OCR-VQA, and the three captioning sets (COCO, Flickr30k, Nocaps), matching the suites used by OTPrune, FastV, and DyMU. We sweep average retention over 5%, 10%, 20%, and 33%. Metrics are:
- accuracy relative to the full model;
- theoretical FLOPs;
- measured prefill and decode latency at batch size 1, and with length-bucketed batching.
The last metric responds to the wall-clock concern raised by DyMU and FastV.
Four checks decide the proposal:
- Our method must beat OTPrune and match or beat DyMU's 99.2% retention figure on the shared benchmarks at no more tokens.
- The gap over FastV and over the nearest-kept-merge baseline should be largest on OCR-VQA and in the multi-object bins, which is where the mechanism predicts it.
- The balanced ablation should lose to the unbalanced version at low retention. If it does not, the core claim fails.
- Per-image budgets should correlate with accuracy loss under a fixed budget better than the cumulative-attention rule does.
As a secondary portability test, we apply the operator inside ViT-B on ImageNet-1K at a merge rate comparable to $r=20$. There, the reference numbers are ToFu's 74.06% top-1 against ToMe's 67.54% (Token Fusion). This asks whether the same solve helps where no text query supplies the attention mass and the class token's attention must stand in for it.
References
- Token Fusion: Bridging the Gap between Token Pruning and Token Merging
- OTPrune: Distribution-Aligned Visual Token Pruning via Optimal Transport
- CoverPrune: Coverage-Driven Token Pruning for 3D VLMs via Optimal Transport
- Aggregating Visual Information with Optimal Transport for VideoLM Token Compression
- Sparse Sinkhorn Attention
- Sinkhorn Divergences for Unbalanced Optimal Transport
- Structured Matching via Cost-Regularized Unbalanced Optimal Transport
- Sinkhorn Distances: Lightspeed Computation of Optimal Transport
- Fast Computation of Wasserstein Barycenters
- An Image is Worth 1/2 Tokens After Layer 2: Plug-and-Play Inference Acceleration for Large Vision-Language Models
- Token Merging: Your ViT But Faster
- FlashSinkhorn: IO-Aware Entropic Optimal Transport on GPU
- DyMU: Dynamic Merging and Virtual Unmerging for Efficient Variable-Length VLMs
- EViT: Expediting Vision Transformers via Token Reorganizations