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

Top-$k$ 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-$k$ produces a power diagram indexed by $k$-element support sets, whereas sliding-window hardmax produces position-dependent local power diagrams indexed by accessible keys. Given $N$ candidate keys and under the stated dimension conditions, the maximum numbers of single-query routing regions are $\Theta ((\genfrac{}{}{0ex}{}{N}{k}))$ for global Top-$k$ and $\Theta (w)$ for a sliding window of width $w$. For $L$ independently varying queries with full windows, the corresponding sequence-level capacities are $\Theta ({\left(\genfrac{}{}{0ex}{}{N}{k}\right)}^L)$ and $\Theta (w^L)$. When the two mechanisms have the same budget $k=w=B$, their capacity ratio is $\left(\genfrac{}{}{0ex}{}{N}{B}\right)/B$ per query and $[(\genfrac{}{}{0ex}{}{N}{B})/B{]}^L$ 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.