Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China · University of Chinese Academy of Sciences, Beijing 101407, China · Gaoling School of Artificial Intelligence, Renmin University of China, Beijing 100872, China
To quantify the geometric expressivity of transformers, we introduce a tropical geometry framework to characterize their exact spatial partitioning capabilities. By modeling self-attention as a vector-valued tropical rational map, we prove it evaluates exactly to a Power Voronoi Diagram in the zero-temperature limit. Building on this equivalence, we establish a combinatorial rationale for Multi-Head Self-Attention (MHSA): via the Minkowski sum of Newton polytopes, multi-head aggregation expands the polyhedral complexity to
O(NH), overcoming the
O(N) bottleneck of single heads. Extending this to deep architectures, we derive the first tight asymptotic bounds on the number of linear regions in transformers (
Θ(NdmodelL)), demonstrating a combinatorial explosion driven intrinsically by sequence length
N, ambient embedding dimension
dmodel, and network depth
L. Importantly, we guarantee that this idealized polyhedral skeleton is geometrically stable: finite-temperature soft attention preserves these topological partitions via exponentially tight differential approximation bounds.