acceptodds
Under review as a conference paper at ICLR 2027

Geometric Capacity of Top- and Sliding-Window Attention: A Theoretical Analysis via Tropical Geometry

Abstract

Top- attention and sliding-window attention are two widely used sparse attention mechanisms for reducing the computation and memory cost of long-context models. Although both mechanisms restrict the number of key–value pairs processed by each query, they generate different sets of routing outputs. In this paper, we present the first unified tropical-geometric comparison of their routing capacities under the same post-routing KV activation-memory budget. With fixed keys, we show that both mechanisms partition query space into polyhedral regions in which the selected KV indices remain unchanged. These partitions admit power-diagram representations: global Top- produces a power diagram indexed by -element support sets, whereas sliding-window hardmax produces position-dependent local power diagrams indexed by accessible keys. Given candidate keys and under the stated dimension conditions, the maximum numbers of single-query routing regions are for global Top- and for a sliding window of width . For independently varying queries with full windows, the corresponding sequence-level capacities are and . When the two mechanisms have the same budget , their capacity ratio is per query and at the sequence level. The proposed geometric framework provides a theoretical basis for comparing and designing sparse attention mechanisms for memory-efficient long-context models.

Primary area:
learning theory
Keywords:
Top-$k$ Attention, Sliding-Window Attention, Tropical Geometry, Sparse Attention, Geometric Capacity.

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_YojkOpenReview ↗
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 (Nk)\binom{N}{k} versus ww 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
  1. 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.
  2. 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.
  3. 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
  1. 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.
  2. The comparison assigns a ww-label hardmax router to sliding-window attention while Top-k selects a kk-element support set; standard sliding-window softmax attention still aggregates all ww local keys. Consequently, the (NB)/B\binom{N}{B}/B 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.
  3. The sequence-level wLw^L and (Nk)L\binom{N}{k}^L 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
  1. Can the authors replace the normal-fan step in Theorem 4.1 with a proof valid for arbitrary bib_i, and state exactly when the unlifted Newton-polytope normal-fan interpretation is valid?
  2. 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?
  3. 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?
Reviewer_TMCtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the maximum number of strict routing regions induced by global Top-k attention and sliding-window hardmax with fixed keys and affine scores. It represents these regions using power diagrams and relates Top-k support sets to a projected hypersimplex. Under sufficient dimension conditions, constructive arguments attain C(N,k) regions for global Top-k and the number of accessible keys for sliding-window hardmax. Independent query coordinates give product counts across positions. The paper compares these capacities under a matched post-routing KV budget. The work is entirely theoretical.

Critical strengths
  • S1: The paper provides a clear geometric account of discrete routing choices. Distinguishing support changes from internal score reorderings avoids overcounting and makes the object of analysis precise.
  • S2: Explicit constructions establish attainability under stated conditions. The assumptions concerning fixed keys, independent queries, and excluded retrieval costs are disclosed, making the scope of the results inspectable.
Critical weaknesses
  • W1: The significance of routing-region counts for useful attention behavior remains insufficiently established. More reachable supports need not imply more relevant selections or more informative outputs. The paper provides neither a theoretical connection to task capability nor empirical evidence for that connection. Moreover, the comparison counts B-element supports for global routing but single winners for sliding-window hardmax. The resulting ratio therefore needs further justification as a guide to architecture design. The concern is the missing connection, not the absence of experiments in a theoretical paper.
  • W2: The direct applicability is limited by fixed keys, independently varying queries, the sufficient dimension condition for attaining all supports, and a budget that excludes global retrieval and indexing. These disclosed assumptions do not establish how the results should guide k or window-size choices in practical self-attention. The conceptual contribution also needs clearer separation from existing results: higher-order power diagrams and prior Top-k MoE geometry already provide closely related representations, while Gale's classical moment-curve construction directly yields the main reachability construction. This limits the additional theoretical insight currently established.
  • W3 (Non-critical, proof verified by AI (GPT6 Astra), not affecting my judgement): For nonzero biases, the proof incorrectly bounds the region count by the number of vertices of the unlifted Newton polytope. Scores (-x,1,x) yield three strict winning regions, but their slopes have only two convex-hull vertices. The final combinatorial upper bound remains valid through support-label counting.

References:

Questions for authors

Could you add targeted experiments to test whether the routing-capacity comparison is reflected in useful attention behavior or task performance under matched post-routing KV budgets? This would help establish the practical relevance of the theoretical results.

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

The paper studies the routing geometry of global Top-k attention and sliding-window hardmax under fixed keys, affine query–key scores, and independently varying queries. It defines geometric capacity as the maximum number of nonempty, full-dimensional strict routing regions. Global Top-k regions are labeled by k-element support sets, whereas sliding-window hardmax regions are labeled by individual winning keys. The authors characterize these regions using max-affine functions and power diagrams. They establish the upper bound C(N,k) for global Top-k, where C(N,k) denotes the binomial coefficient, and provide a construction attaining it when d_k >= 2 min{k,N-k}. For sliding-window hardmax, the maximum count at position t is |W_t|. Sequence-level counts follow from Cartesian products of independently varying query spaces. Under full windows and a matched post-routing support budget k = w = B, the paper obtains the ratio C(N,B)/B. It then discusses implications for choosing sparse-attention mechanisms and budgets. The submission is entirely theoretical; its evidence consists of proofs and illustrative geometric examples.

Critical strengths
  1. The routing-region definition is precise. Definition 2.3 correctly distinguishes changes in the selected support from permutations within that support. Each support is defined by selected-versus-unselected strict inequalities, making its feasible region convex and preventing the overcounting of score orderings as separate routing decisions.
  2. The shared-key construction for sliding windows is explicit. Theorem 4.4 uses one key configuration to make every candidate in every window attainable as a unique winner. In particular, with keys k_j = (j, -j^2), the query (2j, 1) gives key j a strictly larger score than every other key. This establishes simultaneous attainability without changing the parameters separately for different windows.
  3. The geometric formulation is transparent and self-contained. The power-distance construction reduces to the original aggregate affine score after subtracting the common squared query norm. This makes the equivalence between support selection and power cells straightforward to verify. The paper also states its fixed-key, independent-query, and post-routing-budget assumptions explicitly.
Critical weaknesses
  1. Limited independent novelty. Wang et al. (ICML 2026, Lemma 3.2 and Theorem 3.3) already provide the moment-curve/squared-polynomial construction used in Appendix B.6. The complement and independent-query extensions are straightforward. The substantive contribution beyond this precedent and the geometry acknowledged in Appendix C remains unclear.
  2. Mismatched capacity measures. The ratio C(N,B)/B compares full support sets for Top-B with individual winners for sliding-window attention. The paper does not establish why this mixed statistic measures a corresponding advantage in attention functionality or performance.
  3. A concrete proof error. In Appendix B.5, scores (-x,-1,x) produce three strict Top-2 regions, although the aggregate slopes have only two convex-hull vertices. This contradicts the claimed Newton-polytope vertex bound. The final C(N,k) upper bound remains valid, but this proof step requires correction.
  4. Unsupported practical conclusions. Maximum window counts depend only on mask size and cannot justify locality or hybrid-design recommendations. The matched KV budget excludes retrieval costs, while summing KV usage across queries does not establish peak memory. The architectural and efficiency claims therefore exceed the analysis.
Questions for authors
  1. Which part of Theorem 4.2 is not already implied by the moment-curve construction of Wang et al., complement-query negation, and continuity? Please give a theorem-level comparison identifying the substantive new result after separating these inherited ingredients.
  2. What shared operational objective justifies counting an entire support for global Top-B but only a winner for sliding-window attention? Why is C(N,B)/B the appropriate comparison, rather than the ratios obtained by applying the same observable to both mechanisms?
  3. How will Appendix B.5 be corrected in light of the explicit Top-2 counterexample? Please identify which statements depend on the incorrect unlifted-polytope argument and make the full-window condition in Theorem 4.6 explicit.
  4. Since arbitrary fixed nonlocal masks of size B have the same maximum capacity as contiguous windows, which result supports the locality and hybrid-architecture recommendations in Section 5? Please identify a concrete selection rule derived from the theory, or narrow those recommendations.
  5. At B = 1, increasing the global candidate pool does not increase the charged budget. What resource-efficiency conclusion remains established when retrieval resources are also constrained, and what execution model makes the sequence-level budget a physical memory quantity?
1 comment
AuthorsOpenReview ↗

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-kk lower-bound proof also appears in Wang et al. (2026). It distinguishes this inherited construction from our unified geometric comparison of global Top-kk, 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-kk 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-BB versus Top-1 fixes the global candidate range, whereas Top-1 versus window hardmax fixes the single-winner observable and yields the ratio N/BN/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 (Nk)\binom{N}{k} and (Nk)L\binom{N}{k}^{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∣n_t=|W_t|, while Theorem 4.7 (p. 10) explicitly requires ∣Wt∣=B|W_t|=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!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.