Complexity-theoretic tradeoffs between precision and expressivity in transformers

A common technique to accelerate inference and reduce the memory costs of transformers and related models is to restrict to low-precision weights and arithmetic. On the other hand, doing this could reduce the expressive power of the model, but the extent of this phenomenon remains poorly-understood. In this paper, we demonstrate a fine-grained theoretical tradeoff between expressivity and precision: For every $p$ we exhibit a function $\Gamma$ which tests equalities, and prove that a one-layer softmax transformer can compute $\Gamma$, with $p$ bits of precision, but not with $p-1$ bits of precision. Equality testing arises, both explicitly and implicitly, in many tasks that transformers are expected to perform, and our results show it is particularly sensitive to model precision. Our proofs combine explicit finite-precision transformer constructions with communication-complexity lower bounds, yielding a tight “one-bit” threshold.