LapMerge: Differentiable Exact-Budget Token Merging in Linear Time

arXiv:2610.13858v2 Announce Type: replace Abstract: Modern vision and language models process ever longer token sequences, and reducing them is the main lever on downstream cost. Token compression, however, faces a fundamental trade-off: selecting tokens discards information, while existing merging methods preserve it only through pairwise token-to-token matching or MN token-to-output interactions. We introduce LapMerge, a differentiable merging operator that resolves this trade-off for ordered sequences: a learned mass distribution partitions the sequence into exactly N equal-mass segments under a Laplace-kernel density, and prefix/suffix scans aggregate each segment, so both the forward and the backward pass run in O(M+N) time. This combination (an exact output budget, end-to-end differentiability, and linear cost) is precisely what previous reducers trade off against one another. The budget can be changed without changing operator parameters, and the learned mass doubles as a token-level map of where the budget is allocated. Across vision and vision-language tasks, LapMerge matches or improves on strong token reducers while being up to two orders of magnitude faster at large sequence lengths; it is particularly effective when token order reflects spatial or temporal locality, and works both as a drop-in reduction module and as a trainable architectural component.

Related

• StructSAM: Structure- and Spectrum-Preserving Token Merging for Segment Anything Models
• Beyond Surrogate Gradients: Fully Differentiable Token Pruning for Vision-Language Models
• HiPrune: Hierarchical Attention for Efficient Token Pruning in Vision-Language Models
• From Saliency to Discriminability: Rank-Preserving Visual Token Pruning for VLM Rerankers

Source: arXiv cs.CV | 2026-10-14