# LapMerge: Differentiable Exact-Budget Token Merging in Linear Time

arXiv: https://arxiv.org/abs/2610.13858 · HTML: https://mlsanity.com/paper/2610.13858/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Visual token pruning in multimodal models, one of 12 directions in Efficient LLM inference and serving.
- First posted on arXiv 9 Oct 2026.

## Placed in

- Efficient LLM inference and serving / [Visual token pruning in multimodal models](https://mlsanity.com/inference/visual-token-pruning-in-multimodal-models/)

## Abstract (arXiv)

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.