In plain words: Transformers that store numbers with about log n bits can be written exactly as logic sentences adding majority-vote counting to 'all' and 'some' quantifiers. This gives the tightest known description and the first logic for such models, which unlike finite-precision ones can attend broadly.
Abstract · A Logic for Expressing Log-Precision Transformers
One way to interpret the reasoning power of transformer-based language models is to describe the types of logical rules they can resolve over some input text. Recently, Chiang et al. (2023) showed that finite-precision transformers can be equivalently expressed in a generalization of first-order logic. However, finite-precision transformers are a weak transformer variant because, as we show, a single head can only attend to a constant number of tokens and, in particular, cannot represent uniform attention. Since attending broadly is a core capability for transformers, we ask whether a minimally more expressive model that can attend universally can also be characterized in logic. To this end, we analyze transformers whose forward pass is computed in $\log n$ precision on contexts of length $n$. We prove that any log-precision transformer can be equivalently expressed as a first-order logic sentence that, in addition to standard universal and existential quantifiers, may also contain majority-vote quantifiers. This is the tightest known upper bound and first logical characterization of log-precision transformers.
William Merrill, Ashish Sabharwal
arXiv:2210.02671 · cs.LG, cs.CC · submitted Oct 6, 2022 · updated Sep 10, 2025
abstract · pdf · html · May 24, 2023: Restructured version of old preprint. Oct 12, 2023: To appear at NeurIPS. Sept 10, 2025: minor technical corrections
FOM is a symbolic language that can capture computation inside transformers!