Circuit Complexity From Physical Constraints: Scaling Limitations of Attention
Benjamin Prada, Ankur Mali · 2025
Read Circuit Complexity From Physical Constraints: Scaling Limitations of Attention by Benjamin Prada, Ankur Mali (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19161.txt.
Introduction
Textbook computer theory counts circuits as if wires were free and space unlimited, but real chips obey physics. Benjamin Prada and Ankur Mali introduce circuit classes that live in physical space of a given dimension. In their classes, a circuit's volume grows only so fast, the information crossing its boundary per second is capped, and the circuit can grow only through local, buildable edits. These laws bind any causal system, classical or quantum.
Within that frame they prove hard limits. Algorithms whose running time grows too fast cannot handle the hardest inputs, and a parallel machine in fixed dimension gains only a bounded polynomial speed-up over the best serial one. As the dimension rises without bound, their classes recover the classic model of parallelism. Parallelism thus appears as an idealization that physics never quite grants.
Catalog record
| CREATOR | Benjamin Prada, Ankur Mali |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-19161
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Circuit Complexity From Physical Constraints: Scaling Limitations of Attention Benjamin Prada, Ankur Mali Abstract We argue that the standard circuit complexity measures derived from N C , A C , T C NC,AC,TC provide limited practical information and are now insufficient to further differentiate model expressivity. To address these new limitations, we define a novel notion of local uniformity and a family of circuit complexity classes R C ( ⋅ ) RC(\cdot) that capture the fundamental constraints of scaling physical circuits. Through the lens of R C ( ⋅ ) RC(\cdot) , we show that attention mechanisms with ω ( n 3 / 2 ) \omega(n^{3/2}) runtime cannot scale to accommodate the entropy of increasingly complex datasets. Our results simultaneously provide a methodology for defining meaningful bounds on transformer expressivity and naturally expose the restricted viability of attention. \workshoptitle What Can(’t) Transformers Do? 1 Introduction Merrill–Sabharwal (2023) [ 1 ] place softmax transformers ( SMAT ) with O(\log n) precision in \mathrm{DLOGTIME} -uniform \mathrm{TC}^{0} , and recently Chiang (2025) [ 2 ] proves average-hard transformers ( AHAT ) in \mathrm{DLOGTIME} -uniform \mathrm{TC}^{0} . These containments, paired with Merrill–Sabharwal’s [ 1 ] AC^{0} lower bound, squeeze AHAT and SMAT by AC^{0}\subsetneq SMAT,AHAT\subseteq\text{DLOGTIME-uniform }TC^{0}. This characterization is nearly as tight as possible within the standard language of circuit complexity. Although both transformers may be further bound by intermediate classes like ACC^{0} that extend the set of allowable gates, it is uncertain whether such bounds can provide any useful insight. It is apparent, however, that the expressivity of AHATs and SMATs are not sufficiently captured by these bounds alone. This suggests that existing circuit complexity bounds may be too coarse to fully capture the expressive nuances of these transformer models; therefore, the bounds require refinement via altering the circuit complexity framework. 2 Approach Our work addresses the challenge of quantifying model expressivity by reframing it in terms of scalability. Because a given model must be scaled to support inputs of increasing size, any meaningful measure their expressivity must depend on the rate at which they can be scaled. In practice, this scaling rate is strongly constrained by the speed with which information can propagate: the number of components of a causal system is bounded in time t by \mathcal{O}(t^{3}) , and the entropy rates of the inputs and outputs are each bounded as \mathcal{O}(t^{2}) . These bounds remind us that, while polynomial growth is a useful abstraction for theory, knowing the degree of the polynomial is instrumental to understanding utility. By justifying natural, precise bounds on circuit proportions, we can directly apply complexity theory to a forward-looking design of efficient machine learning architectures. 2.1 Realizable circuits (RC) We introduce a new family of complexity classes RC(t(n)) that capture these scalability restrictions. See Definition B.6 for a more detailed definition. Definition 2.1 ( RC(\cdot) ) . A function f\in RC(t(n)) if there exists a sequence of circuits \{C_{n}\}_{n>0} that each implement f for inputs of length n such that, given a description of C_{n} , a sufficient circuit C_{n+1} can be constructed in \mathcal{O}(t(n)) time, and such that each |C_{n}|=\mathcal{O}(t(n)^{3}) . The parameter t(n) can be interpreted as the maximum desired time in which circuit implementations can be constructed for inputs of length n . For example, RC(\sqrt{n}) is the set of functions whose implementations can scale quadratically in time. Be careful not to interpret t(n) as the scaling rate. The rate that the input length scales is given by n(t)=t^{-1}(n) . Notice that this definition diverges from typical uniformity constraints in that the construction may be incremental. The criteria for DTIME(t(n)) -uniformity necessitates that a mapping n\mapsto C_{n} be computable in \mathcal{O}(t(n)) time, but our constraint is looser, requiring only that C_{n}\mapsto C_{n+1} be computable in \mathcal{O}(t(n)) time. This condition–which we call local uniformity–reveals the scaling benefits of architectures that can be extended efficiently but not necessarily rebuilt efficiently. The second condition bounds the number of circuit components |C_{n}| relative to the time t(n) . The |C_{n}|=\mathcal{O}(t(n)^{3}) constraint is derived simply from the \mathcal{O}(t^{3}) bound on the volume of a causal system. Notice that |C_{n}| and the scaling rate t^{-1}(n) are inversely related. As the scaling rate increases, the ratio of model size to input length decreases. For example, RC(\sqrt{n}) equates to a fast scaling rate of n=\Omega(t^{2}) but limits the size of the circuit significantly to |C_{n}|=\mathcal{O}(n^{3/2}) . 3 Main Results Our first result establishes a relationship between RC functions and polynomial-time functions. Theorem 3.1 . RC(n^{k/3})\subseteq DTIME(n^{k}),\quad\forall k>0 . This result shows that a function with a runtime of \Omega(n^{k}) cannot be scaled faster than n^{3/k} . As a direct corollary, RC(\sqrt{n})\subseteq DTIME(n^{3/2}) . Under the assumption that n^{2} is the fastest possible scaling rate, this result implies that ideal scaling requires a \mathcal{O}(n^{3/2}) time complexity. We justify this assumption by deriving the asymptotic rate at which entropy can enter a causal system. The second of our results refines the classification of SMAT,AHAT through the RC framework. Theorem 3.2 . \displaystyle SMAT,AHAT \displaystyle\subseteq RC(n^{2/3})\cap\text{DLOGTIME-uniform }TC^{0} \displaystyle SMAT,AHAT \displaystyle\not\subseteq RC(\sqrt{n})\cap\text{DLOGTIME-uniform }TC^{0} The RC(n^{2/3})\cap\text{DLOGTIME-uniform }TC^{0} upper bound tightens the placement of SMAT,AHAT by clarifying that scaling is bounded as \mathcal{O}(n^{3/2}) . The RC(\sqrt{n})\cap\text{DLOG-u }TC^{0} non-containment is of especial importance as it separates SMAT,AHAT from the set of architectures that can meet the ideal n^{2} scaling rate. 4 Impact In this work, we extend the theoretical model of circuit complexity to a practical setting directly applicable to the analysis and design of machine learning architectures. Through the construction of RC(t(n)) , we begin to uncover the precise limits of model expressivity in terms of a balance between scalability, time complexity, parallelism, and depth. By adopting only the most conservative, information-theoretic assumptions for physicality, our results can be interpreted to hold agnostic of the choice of computation method. We strongly advocate for a wider theory of expressivity focused on pragmatism. We highlight that expressivity is inseparably tied to both the precise allocation of computation resources and the ability for the computation to scale; however, this effort is incomplete. Although we avoid the discussion of circuits with recurrent connections, such circuits greatly improve efficiency by the reuse of components. Directions for future research are considered in Appendix D. Appendix: Directory A Background. We provide a brief overview of preliminary information necessary to understand the work (e.g., circuit complexity and prior known results). We also include an outline of our reasoning toward the current research direction. B Approach. We introduce the main assumptions and constructions of our framework. In this section, we build our notion of local uniformity and justify the physical constraints that we rely on for the remainder of the work. C Results. We introduce our main results by applying the tools built in the previous section. Here we tie our framework to the broader realm of complexity theory and utilize it to constrict SMAT and AHAT further. D Analysis. We reflect on our results and provide a brief discussion on future extensions. A Background Our work operates in the domain of circuit complexity. To present a complete picture of our contributions, we begin by introducing the standard classes of circuit complexity and their known relationships with