Transformers Are Hard for Machines, Not Only for Circuits

Saha, Xu, Ye, and Yu construct a transformer that no extended arithmetic circuit computes in fewer than $LH\cdot N^{\omega -o(1)}-O(LH\cdot N^2)$ gates when $\omega >2$, and ask whether the bound survives in the Word-RAM model, whose algorithms branch on the values they compute. We prove one theorem, and a corollary answers their question for the numerically-branched algorithms defined next. Call a Word-RAM algorithm numerically-branched if its operations on real cells come from $\{+,-,\times ,/,\exp ,\ln \}$ and a real value reaches word memory only in two ways. One is a comparison; the other is a read of its bits by a function whose level sets are countable unions of intervals. Rectified activations, argmax, threshold masking, and top-$k$ retrieval are all computed by numerically-branched algorithms. The theorem: if every extended arithmetic circuit agreeing with a function $f$ on some nonempty open subset of a region has size at least $s$, then every numerically-branched algorithm computing $f$ on the whole region takes time at least $s$. Every circuit lower bound whose reduction reads only local information therefore transfers. There is no hypothesis on $f$, because the proof works with the algorithm's own trace. On a region where every comparison and every bit-read has a fixed outcome, that trace is a fixed circuit, and the region is built by nested shrinking rather than by a genericity assumption. The theorem has four consequences, for the transformer of Saha et al., its sigmoid and gated-linear-unit variants, rectified-linear-unit variants on an open piece where every rectifier is active and the perceptron is the identity, and $N\times N$ real matrix multiplication.