Beyond the Attention Lottery: Expressive Power and Topological Complexity via Algebraic Geometry

We study algebraic and geometric properties of simplified attention models. For exact computation of all pairwise inner products between two independently varying collections of $N$ vectors in ${\mathbb{R}}^d$, we prove that a single-hidden-layer network with square activations requires at least $N^2+1$ hidden units and give an explicit construction using $2N^{2}d$ units. Thus the width is $\Theta (N^2)$ for fixed $d$, while the optimal dependence on a growing $d$ is left open. For a fixed latent representation and explicitly specified admissible query and key maps, allowing a nonlinear key map strictly enlarges the linear span of attention score functions. When $d\ge 2$ and each summand may instead use an unrestricted preceding map, the standard, single-sided, and dual-sided spans coincide. In a bias-free, softmax-free residual attention model, we derive that every output coordinate is a polynomial of odd degree at most $3^L$ after $L$ layers; the occurrence of particular lower degrees requires nondegeneracy conditions. We then discuss Milnor–Thom bounds only for the corresponding idealized polynomial decision boundaries, and analyze actual input scaling in softmax attention: small scales produce nearly uniform averaging, whereas large scales concentrate on maximal scores under a positive score gap. The final discussion presents the “lottery of attention” as a conjectural geometric interpretation of parameter sparsity and initialization; it is not a theorem guaranteeing optimization feasibility or homotopic convergence.