acceptodds
Under review as a conference paper at ICLR 2027

From Sequential Refinement to One-Shot Global Selection: Monotone Adaptive Tokenization

Abstract

Adaptive tokenization reduces the cost of transformers on high-resolution and high-dimensional data by allocating fine-grained tokens to informative regions and coarse-grained tokens elsewhere, typically through sequential Top- refinement over a quadtree or octree. This refinement can itself become a bottleneck: when run on the GPU, it accounts for 53–80% of each training step on our 2D benchmarks, exceeding the runtime of the model itself, because its dependent rounds must run sequentially, each dominated by kernel-launch overhead. We observe that when importance scores are monotone along the hierarchy, with every ancestor scoring no lower than its descendants, the hierarchy satisfies the heap order property; as in classical heap selection, sequential Top- refinements then select exactly the highest-scoring regions. Monotone Adaptive Tokenization (MAT) therefore replaces sequential refinement with one global Top- selection while preserving the exact Top- allocation under monotone scores; non-monotone metrics are made monotone through bottom-up sum or max reductions. Across high-resolution 2D segmentation, large-scale 3D point clouds, and multichannel weather data, MAT achieves up to and higher training and inference throughput than sequential refinement on 2D data, and over a dense-voxel baseline in 3D with substantially lower memory usage, and and over sequential refinement on weather data, while preserving downstream quality. Across the tested token budgets and attention backends, the speedups reach up to in training and in inference.Our code is publicly available at https://anonymous.4open.science/r/Monotone_Adaptive_Tokenization-76FC.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
adaptive tokenization, vision transformers, hierarchical refinement, monotone scores, high-resolution data

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Y5WNOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Monotone Adaptive Tokenization (MAT), an efficient approach to hierarchical adaptive tokenization that replaces sequential Top-1 refinement with one-shot global Top-K selection. The key insight is that when importance scores are monotone along ancestor–descendant paths, the hierarchy satisfies the heap-order property, allowing global Top-K selection to exactly reproduce the token allocation of sequential greedy refinement. For non-monotone importance metrics, the authors introduce bottom-up sum or max reductions to construct monotone scores, enabling the same selection strategy under the adapted scores.

The method is evaluated across high-resolution 2D image segmentation, large-scale 3D point-cloud segmentation, and weather downscaling, with additional ImageNet experiments examining score adaptation. The results demonstrate improved end-to-end training and inference efficiency while maintaining comparable downstream task quality, including up to 3.73× training and 2.56× inference speedups over sequential refinement.

Critical strengths
  1. A clear and effective algorithmic insight. The paper presents a simple and principled reformulation of hierarchical adaptive tokenization, exploiting score monotonicity to replace sequential refinement with global Top-K selection. Under the stated assumptions, this reformulation preserves the exact token allocation without introducing approximation errors. Although the underlying heap-order property is well established, I consider its application to eliminating the sequential dependency in adaptive tokenization a meaningful and elegant insight.

  2. Meaningful system-level optimization with convincing empirical evidence. The paper identifies a concrete computational bottleneck in existing sequential refinement and demonstrates substantial end-to-end efficiency improvements while maintaining comparable downstream performance. The evaluation across multiple data modalities, together with detailed runtime profiling and scaling experiments, provides convincing evidence of the practical value of the proposed optimization.

Critical weaknesses

I didn't recognize main flaws that may justify rejection. Below are my major concerns:

  1. Unclear practical advantages over competitive parallel baselines. While MAT achieves substantial speedups over sequential Top-1 refinement, its additional efficiency gains over existing parallel alternatives, such as Batch-M and APT, are relatively modest in several settings. MAT preserves exact greedy allocation and provides explicit token-budget control, but the paper does not sufficiently establish when these properties translate into meaningful practical advantages. A more systematic comparison of accuracy–efficiency trade-offs against strong parallel baselines would better substantiate its practical significance.

  2. Insufficient characterization of applicability and computational trade-offs. MAT relies on importance scores being available for all candidate regions before selection and satisfying monotonicity, potentially through score adaptation. This assumption may limit its applicability to methods with dynamically computed or feature-dependent importance scores. Furthermore, computing scores across the full hierarchy may introduce unnecessary overhead when only a small fraction of regions requires refinement. The paper lacks a clear characterization of these applicability boundaries and the conditions under which global selection remains beneficial.

Questions for authors
  1. Practical advantages over strong parallel baselines. Table 1 shows that MAT's efficiency gains over Batch-M and APT are relatively modest in several settings, despite substantial improvements over sequential Top-1 refinement. Could the authors clarify under which conditions MAT provides meaningful advantages over these competitive parallel methods? In particular, can the authors further substantiate the practical benefits of exact greedy allocation and fixed token-budget control, ideally through matched-budget accuracy–efficiency comparisons?

  2. Applicability and computational trade-offs. MAT assumes that importance scores for all candidate regions can be computed before refinement. As I am not fully familiar with the broader adaptive tokenization literature, could the authors clarify which representative existing methods satisfy this assumption, and how broadly applicable it is in practice? Additionally, the Top-1 and MAT implementations share the same score-construction pipeline. Could the authors further discuss the computational trade-off between precomputing scores for the full hierarchy and computing them on demand during refinement?

2 comments

Thank you for the detailed rebuttal and additional clarification. The matched-budget comparison with APT provides useful evidence for MAT's practical advantages beyond sequential Top-1 refinement. I also appreciate the clearer characterization of the applicable scoring methods and the explicit discussion of the method's limitations.

I think these responses substantially address my main concerns. While the additional efficiency gains over strong parallel baselines remain somewhat setting-dependent, the combination of exact greedy allocation, explicit token-budget control, and competitive efficiency is a meaningful practical advantage.

Overall, I maintain my positive assessment.

Thank you for your careful review and constructive feedback. We appreciate your positive assessment and the time you took to engage with our work throughout the discussion.

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

Previous adaptive tokenization methods are time-consuming and can take 53% - 80% of the time in each training step to do refinement. This is caused by the fact that KK dependent rounds must run sequentially. The authors observed that if the scores in the adaptive tokenization tree forms a heap structure, then the KK sequential Top-1 refinements then select exactly the KK highest-scoring regions. Based on this observation, the authors proposed the Monotone Adaptive Tokenization (MAT) which improves much better throughput. The authors did experiments on 2D high-resolution pathology data, 3D data, and showed effectiveness of the proposed method.

Critical strengths

The idea that transforming the adaptive tokenization tree to a heap structure is interesting. The authors dived deep into the problem, and observed the limitation of AP/APT method. The authors identified the pinpoint that Top-1 refinement in previous method requires KK sequential dependent rounds, which limits the application of the method. They transformed the tree to a heap so that only one global Top-KK selection is needed, which significantly reduced the refinement time.

The authors applied their proposed method on 2D high-resolution pathology data for segmentation, 3D point-cloud data, and multichannel spatiotemporal datasets. Results in Table 1 show that the method achieved similar quality performance as previous methods, but improves throughputs, efficiency in most cases.

Critical weaknesses

The novelty of this paper is not significant. Heap is a well-known concept in the field, and the heap construction is trivial. Also, the paper uses existing methods to compute the scores.

Questions for authors

I know that during the refinement, the scores of the ancestors will be changed using max operation or sum operation in Sec. 3.3. Will there be any side-effects?

In Fig. 2, the node that has a score of 100 is not a leaf node. I understand only the leaf node will be used to be tokenized. But why the node is also ranked in Top-K?

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

The paper reformulates hierarchical adaptive tokenization. With fixed scores that are monotone from ancestors to descendants, and a shared ancestor-first tie order, global Top-K selection returns exactly the split nodes selected by K sequential frontier Top-1 refinements. The selected internal nodes induce the final token partition. Additive scores are already monotone; other criteria are adapted by bottom-up sum or max reduction. The paper correctly limits equivalence after adaptation to the adapted scores, rather than claiming that the original non-monotone trajectory is preserved.

Critical strengths

The conditional result is correct, concise, and useful: it separates allocation semantics from execution order and removes a sequential dependency chain without approximating the specified Top-1 partition. The paper acknowledges that the heap-order argument follows classical results; the contribution is its connection to tokenization and GPU execution.

The same-pipeline comparison is stronger than a typical cross-model speed table. Top-1 and MAT share the GPU tokenization pipeline and differ in split selection. Table 4 reports identical sets at three budgets, with sequential selection growing from 252.8 to 996.3 ms while one-shot selection remains around 0.46 ms. On PAIP, training increases from 5.46 to 20.37 samples/s and inference from 4.43 to 11.34, at essentially unchanged Dice. These results provide a coherent mechanism-to-system argument, subject to timing clarification.

The evaluation also includes high-resolution 2D, forest point clouds, weather data, and non-monotone-score adaptation on ImageNet. The appendix usefully discloses precision/batching differences and distinguishes gains shared by GPU implementations from MAT-specific gains.

Critical weaknesses

First, the practical frontier relative to strong parallel alternatives is narrower than the large Top-1 speedups suggest. In 3D, MAT versus Batch-M has training throughput 2.05 versus 2.04, inference 0.354 versus 0.365, and higher memory usage; its F1 advantage is only 0.26 without uncertainty information. On ERA5, training versus Batch-M(m=4) improves only about 1.047 times, with quality 78.27 versus 78.26. PAIP is more compelling: versus Batch-M(m=64), MAT improves both throughput and Dice, from 79.10 to 80.77. The contribution should be positioned around exact allocation and specific quality-time-memory advantages rather than broad dominance.

Second, the necessary tie order is not connected to the GPU implementation. The proof specifies ancestor-first ordering, but Algorithm 1 only invokes global Top-K. Max reduction necessarily creates equal-score ancestor chains, and integer edge counts produce additional ties. A Top-K primitive that arbitrarily chooses a tied descendant without its ancestor would violate closure; this is a counterexample to unconstrained selection, not to the paper's theorem and not evidence that the authors implemented it incorrectly. Please specify the lexicographic key or equivalent procedure, its numerical behavior and cost, and closure/set-equality checks on constant, zero, and max-chain scores.

Third, the 2D timing description does not explicitly identify synchronization at the boundaries of the complete measurement window. Preserving overlap between steps is reasonable, but the full timed window must account for completed GPU work. A separate synchronized stage-decomposition pass does not establish that the main throughput window has correct boundaries. The text already specifies synchronization for 3D and ERA5 inference, so this concern should not be generalized to every measurement. Timing code or a trace and a longer-window check would resolve it.

Fourth, baseline and metric definitions need clarification. PAIP APT averages 7,123 tokens versus MAT's 8,191, so its lower Dice is not a pure selection-rule comparison. The complete APT method also includes aggregation, packing, and CPU scoring overlap; it should be clear whether the table evaluates that full method or only its threshold rule in a shared pipeline. The 3D F1 matching/aggregation and ERA5 R-squared target and aggregation are also insufficiently specified for independent reproduction.

Finally, MAT processes all N candidates whereas sequential refinement may inspect only a much smaller portion for small K. The fixed-resolution budget sweep does not establish the crossover as N/K grows. The non-monotone study is useful empirical evidence, but does not guarantee negligible quality loss or low scoring cost for arbitrary criteria.

Questions for authors
  • How is ancestor-first tie ordering implemented and included in timing?
  • Are the complete 2D timing windows synchronized at both boundaries?
  • What are the matched-quality frontiers against tuned Batch-M and complete APT?
  • Please specify F1/R-squared definitions and data versions, and characterize full-tree/scoring cost at small K relative to N.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.