Infinite Graphs as Limits on Attention

A finite-dimensional attention head cannot realize the random graph. Modeling a hard-attention head as a threshold dot-product graph, we show that a head of dimension $d$ fails the $(d+1)$-extension property at every threshold. The Rado graph, in which every relational query has a witness, therefore lies beyond every finite dimension. Forster's sign-rank bound turns the barrier into a rate: a generic relation on $n$ tokens forces $$\begin{gathered} d= \\ Omega( \\ sqrtn) \end{gathered}$$, independently of how the token embeddings are chosen. Grading a head by the largest query it answers gives a hierarchy. Answering every query on $k$ tokens needs at least $2^k$ tokens and dimension at least $k$. Conversely, with $$\begin{gathered} n \\ ge{2}^{Ck} \end{gathered}$$ tokens for a constant $C$, a head with independent Gaussian embeddings of dimension $$\begin{gathered} O(k \\ logn) \end{gathered}$$ suffices with high probability. At an exponential token budget, that Gaussian head fails with high probability for each dimension $$\begin{gathered} k \\ led \\ lec{k}^2/ \\ logk \end{gathered}$$: some $k$ of its directions have a positive cone too small for any available token to hit. For directed heads, with queries and keys separate, the barrier holds on tournaments and the Gaussian bounds transfer for $$\begin{gathered} d= \\ Omega(k) \end{gathered}$$. Whether some head answers all $k$-token queries at dimension linear in $k$ is open.