- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper develops a fixed-key, zero-temperature geometric framework for comparing global Top-k routing with sliding-window hardmax routing through tropical polynomials, power diagrams, and Newton polytopes. It gives matching combinatorial upper and constructive lower bounds on the number of strict routing regions, yielding versus per-query capacities and the corresponding product-space counts for independently varying query sequences. Under a matched post-routing KV-pair budget, the paper interprets the resulting ratio as a geometric advantage for globally content-adaptive routing.
Critical strengths
- The paper isolates a precise geometric object—strict routing regions under fixed keys—and gives a coherent representation for both mechanisms, including the support-set power diagram for Top-k and the position-indexed local diagrams for sliding windows.
- The moment-curve and parabola constructions are concrete and useful: under explicit dimension assumptions they make the label-count bounds tight, rather than leaving the results as loose combinatorial upper bounds.
- The presentation is self-contained, with definitions, proofs, and small visual examples that make the hypersimplex and power-diagram viewpoints accessible to readers interested in sparse-attention theory.
Critical weaknesses
- The proof of Theorem 4.1 contains a geometric statement that is false for the paper's general nonzero biases: it identifies the strict regions with open normal cones of the unlifted Newton polytope, whereas Appendix A correctly notes that nonzero coefficients induce a regular subdivision/power diagram and generally translate the cells. The label-count upper bound can be proved directly, but the theorem's current tropical-geometric proof needs correction and its assumptions must be stated consistently.
- The comparison assigns a -label hardmax router to sliding-window attention while Top-k selects a -element support set; standard sliding-window softmax attention still aggregates all local keys. Consequently, the ratio measures discrete routing-label diversity under an asymmetric hardmax abstraction, not the information, output-function, or end-to-end expressivity of the two attention operators. The budget also excludes the full-candidate scan/sort cost for global Top-k, so the claimed design implication is narrower than the wording suggests.
- The sequence-level and capacities rely on independently varying queries with fixed keys, an abstraction that removes the query–key coupling and causal dependencies of self-attention. The paper does not establish how this product-space count predicts any property of a trained Transformer, and the novelty boundary relative to the cited tropical analyses of Top-k/MoE support regions and Top-1 attention is not sharply separated from those prior results.
Justification of Recommendation
I recommend weak rejection because the incorrect normal-cone argument for general nonzero biases and the asymmetric hardmax comparison outweigh the useful routing-region formulation and tight constructive bounds. The independent-query product counts further limit the stated connection to self-attention capacity. I would rate the paper higher with a corrected geometric proof, a comparison and budget accounting aligned with the attention operators being discussed, and conclusions that establish or explicitly restrict the connection to coupled self-attention.
Questions for authors
- Can the authors replace the normal-fan step in Theorem 4.1 with a proof valid for arbitrary , and state exactly when the unlifted Newton-polytope normal-fan interpretation is valid?
- What is the intended claim about ordinary finite-temperature sliding-window attention, and can the authors either analyze its fixed-support/continuous output or explicitly restrict the comparison and its conclusions to zero-temperature hardmax routing while accounting for the omitted global-retrieval cost?
- How should the capacity results be interpreted when queries and keys are generated by the same self-attention computation, and what theorem-level distinction from the cited prior Top-k/MoE and Top-1 tropical analyses establishes the claimed novelty?
Revision locations
The revised manuscript incorporates the clarifications and corrections discussed in our response, with revisions highlighted in blue. The relevant locations are listed below. Section and theorem numbers refer to the revised manuscript.
1. Attribution and scope of contribution (W1; Q1). Appendix C, final paragraph (p. 23) explicitly acknowledges that the moment-curve/squared-polynomial construction used in our Top-k lower-bound proof also appears in Wang et al. (2026). It distinguishes this inherited construction from our unified geometric comparison of global Top-k, global Top-1, and sliding-window hardmax. Section 1 (pp. 2–3) presents the comparative research question and contributions; Section 3 (pp. 5–7) develops the common geometric framework; and Section 4.5.2 (pp. 9–10) separates support-selection diversity from candidate-range diversity.
2. Capacity metric and consistent comparisons (W2; Q2). Section 2.2, the paragraph following Definition 2.5 (p. 4) clarifies that the metric counts selections realized on nonempty open query sets under one fixed parameter configuration, and relates it to the affine regions of the selection potential rather than the finite-temperature attention output. Section 2.3 (p. 4) explicitly distinguishes Top-k support selection from the window hardmax winner observable. Section 4.5.2, Theorems 4.6–4.7 (pp. 9–10) introduces global Top-1 as an intermediate reference: Top-B versus Top-1 fixes the global candidate range, whereas Top-1 versus window hardmax fixes the single-winner observable and yields the ratio N/B for full windows. Figure 1 (p. 2) has also been updated to include global Top-1.
3. Proof correction and full-window conditions (W3; Q3). Section 4.1 (pp. 7–8) and Appendix B.5 (p. 19) replace the incorrect unlifted-polytope argument with a direct strict-half-space proof: each support induces at most one nonempty open convex region, preserving the upper bounds (kN) and (kN)L for arbitrary fixed biases. The paragraph following Proposition 3.4 (p. 6) and Appendix B.3 (p. 18) specify the conditions for the unlifted normal-fan interpretation and give the lifted-polytope formulation for general biases. Theorems 4.3–4.4 (p. 8) state the position-dependent window counts using nt=∣Wt∣, while Theorem 4.7 (p. 10) explicitly requires ∣Wt∣=B at every compared position for the full-window ratios.
4. Retrieval costs and the memory interpretation (W4; Q5). Section 4.5.1, Definition 4.5 and the following paragraphs (p. 9) define a candidate-KV input budget conditional on completed selection. Global database storage, indexes, search, sorting, and candidate-transfer costs are explicitly excluded rather than assumed zero. The revision also distinguishes cumulative KV input volume from simultaneously resident candidate-buffer occupancy and gives the buffer requirement under sequential reuse. This makes the execution assumptions explicit and limits the accounting to the specified downstream stage.
Thank you for your time and constructive comments!