acceptodds
Under review as a conference paper at ICLR 2027

LapMerge: Differentiable Exact-Budget Token Merging in Linear Time

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 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 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 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.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
token merging, token reduction, sequence compression, linear complexity, vision transformers, efficient transformers, budget-exact reduction, convex aggregation, long-sequence processing

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_37cSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces LapMerge, a differentiable token merging operator designed to reduce sequence length under an exact output budget while achieving linear-time computation.

Critical strengths

LapMerge provides a mathematically grounded approach to exact-budget token merging by formulating token aggregation as equal-mass partitioning of a smoothed importance distribution.

Critical weaknesses

LapMerge builds on the Laplace CDF and scan-based computations used in LapSum for differentiable ranking and selection. A more systematic comparison with LapSum would help establish the distinct contribution of LapMerge.

Questions for authors
  1. The evaluation on modern multimodal models is limited. The MLLM evaluation primarily relies on POPE with a single Qwen2.5-VL backbone. Additional benchmarks and end-to-end inference measurements would strengthen the practical claims.

  2. The order-permutation experiments show a substantial performance drop when the scan order is randomized, indicating that the method relies on meaningful local structure in the input sequence. While this inductive bias is suitable for spatially or temporally organized tokens, its applicability to sequences where relevant information is distributed across distant positions remains unclear. The paper would benefit from a clearer characterization of when ordered merging is preferable to order-agnostic or content-based merging methods.

  3. Although the paper compares LapMerge with pruning, uniform pooling, and local smoothing baselines, the individual contributions of its main design choices remain insufficiently isolated. In particular, it is unclear how much of the performance gain comes from token merging itself, adaptive equal-mass partitioning, or Laplace-based smoothing.

Reviewer_kYYzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes LapMerge, a token reduction operator for ordered sequences. A scorer gives each token a mass, each token is placed as a Laplace bump at its position, and the mixture CDF is cut into N pieces of equal mass. Each output token is the weighted average of the tokens in its piece. Because of the Laplace kernel this can be done with prefix and suffix sums, so the cost is linear in M + N for both forward and backward, and the output size is exactly N. Experiments cover runtime, MSI prediction on TCGA slides, POPE with Qwen2.5-VL, and LRA, with more in the appendix.

Critical strengths

I like the main idea. Getting exactly N tokens out while staying differentiable and linear in cost is useful, and Section 3 explains clearly why the Laplace kernel makes this work. The paper also reports cases where the method does not help (arXiv, and the order permutation test on LRA-Image), which I found useful for understanding when the locality bias matters.

Critical weaknesses

The accuracy results do not really support the claim that LapMerge matches or beats strong token reducers. For histopathology it is second behind RRT-MIL, and no other reducer (top-k or uniform pooling) is tried in the same pipeline. The POPE gain at 30% is within noise by the authors' own bootstrap, and it is one benchmark with one VLM. On LRA the full Transformer is at chance on Pathfinder and below the usual number on Image, so I am not sure how well these models were trained. Cars and arXiv are mostly single seed. I was also surprised there is no ViT on ImageNet comparison with ToMe or PiToMe (accuracy vs throughput), since that is the standard setting for token merging.

The speed claims are weaker than the abstract suggests. The big gains over TokenLearner and PatchMerger show up when N grows with M. At fixed N=1024 the native PyTorch path, which is the one used for all accuracy results, is only 1.2x to 1.7x faster, and the fused kernel has large errors with near-hard masses. Top-k and uniform pooling are never timed, and in the POPE setup the method keeps the same number of tokens as VisionSelector and uses a dense adapter, so there is no speed gain there. On novelty, the prefix/suffix trick is from LapSum and the cumulative score cut is close to ATS, so the step forward feels small to me.

I think the method also seems sensitive to the kernel width α, which makes it harder to use than the paper suggests. On LRA-Image, setting α to the bin spacing M/N, which looks like the natural choice, loses about 5 points compared to α=1. A very wide kernel loses even more. On POPE, a wider read-out width falls below plain selection, and at 30% the gain is gone for widths above 1. So I am not fully convinced by the claim that no per-task calibration is needed. It would help to have a simple rule for choosing α, or to show that learning it works reliably.

Questions for authors
  1. Could you add a ViT on ImageNet experiment against ToMe and PiToMe, with both accuracy and throughput?
  2. In the histopathology pipeline, what happens if LapMerge is replaced by top-k selection or uniform pooling in front of the same Transformer?
  3. Why is the unreduced Transformer at chance on Pathfinder and below the usual LRA number on Image? How were the LRA baselines tuned?
  4. For POPE, what is the actual latency compared to VisionSelector, and do the gains hold on another benchmark or another VLM?
Reviewer_w8JLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper describes LapMerge, a merging operator to convert an ordered sequence of M tokens to exactly N tokens by partitioning a learned Laplace-mixture density into N equal-mass intervals. Furthermore, by using prefix/suffix scanning and closed-form barrier inversion, LapMerge reduces the time complexity of the forward and backward passes to O(M+N) time. The paper reports strong results showing that on vision and vision-language tasks, LapMerge reduces the running time by almost two orders of magnitude compared to previous work especially, when spatial or temporal locality are presented in the input sequence.

Critical strengths
  • Nice, coherent construction combining several techniques (e.g., closed-form Laplace-mixture inversion, feature aggregation, matrix-free backward computation) to achieve exact output budget under linear running time.
  • The experiments use useful empirical controls, e.g., budget-matched LRA comparisons, a frozen-scorer replacement of POPE, and a direct order intervention. In particular, the order-permutation test on LRA-Image (Table 17) is well controlled.
  • I appreciate explicitly stating the limitations in the appendix.
Critical weaknesses

General:

  • The framing is too broad. In particular, fixed pooling already provides an exact output count, it is differentiable with respect to input features, and it has linear cost. Differentiating LapMerge from TokenLearner, PatchMerger and Perceiver by using only he exact output count is insufficient.
  • You are missing some related work, in particular, Dynamic Token Pooling and Hourglass. You should also clarify the benefits of boundary construction and gradient computation over LapSum and other prior adaptive pooling methods.
  • Regarding the 100x speedup claim, you also need to compare with inexpensive local and adaptive pooling.
  • Regarding the linear runtime complexity, please note that the default soft-top-k router requires O(M\log M) sorting.
  • The largest reported speedups rely on the fused backend, but Tables 6–7 show substantial numerical errors fot thfused backend. Please verify correctness for the results you are reporting.

Some experimental results are not conclusive.

  • Histopathology: Each test cohort contains only about 8–9 positive examples. You should report uniform-pooling and top-k controls with the same head.
  • POPE: The evaluation consider only one model and one benchmark. Furthermore, the baselines are from another paper, and the 30% confidence interval includes zero.
  • LRA: On Image, the unreduced Transformer achieves 35.9% which is significantly lower than the original LRA benchmark (i.e., 42.4%). Please clarify the configuration differences and provide evidence that the baseline was adequately tuned and trained.
  • Cars and arXiv: While for Cars you include three-seed comparisons with top-N selection, for learned poolers you are only using single-runs. Similarly, for budget-matched comparisons on arXiv, you are using single-seed. Finally, LapMerge shows little accuracy improvements over TokenLearner or PatchMerger. Please clarify.

Inconsistent evaluation. You use different experiments use different methods, e.g, fixed or learned coordinates, learned widths, and two-width readout. Also, you need to better support broad claims such as “almost no accuracy cost” using dataset- and budget-specific settings.

Questions for authors
  • Please report the forward and gradient errors for all runtime experiments. Assuming acceptable errors, which of the reported results remain valid?
  • Unclear wether \alpha_r controls the soft-top-k temperature, the mixture width, or both. Please clarify,
  • Regarding the POPE's results, does the 10% retention improvement remain significant for a paired bootstrap clustered by image, rather than by question?
  • For the histopathology experiment, please add uniform-pooling and learned top-k selection baselines using the same token budget, frozen features, token ordering, downstream classifier, and training algorithm.
  • Please rerun LRA using adequately tuned and trained baseline.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.