A Logic for Expressing Log-Precision Transformers
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
There are finitely many positions where the weighted average of values by attention scores can be nonzero.
“As observed by Li & Cotterell (2025) and Merrill & Sabharwal (2023), there are finitely many positions where this can be nonzero.”
From Length Generalization Bounds for Transformers (2026) · cites this paper as Merrill & Sabharwal (2023)
Proposition 1 (Section 3, p. 5) bounds the number of nonzero entries in a rounded p-precision attention-weight vector by 2^(2p). This supports a bound on positions contributing through nonzero attention weights, but only under the stated finite-precision condition; the cited sentence leaves that condition unstated. (LLM, conf=0.86)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
Cited by 6
Research works printed but not linked: 21
- Arora, S. and Barak, B. Computational Complexity: A Modern Approach . Cambridge University Press, 2009.
- Barrington, D. A. M., Immerman, N., and Straubing, H. On uniformity within NC 1 . Journal of Computer and System Sciences , 41(3):274-306, 1990.
- Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of transformers to recognize formal languages. In EMNLP , 2020.
- Brent, R. P. and Zimmermann, P. Modern computer arithmetic , volume 18. Cambridge University Press, 2010.
- Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In NeurIPS , 2020.
- Chiang, D. Transformers in uniform TC 0 . Transactions on Machine Learning Research , 2025. ISSN 2835-8856.
- Chiang, D., Cholak, P., and Pillay, A. Tighter bounds on the expressivity of transformer encoders. ICML , 2023.
- Hahn, M. Theoretical limitations of self-attention in neural sequence models. TACL , 8:156-171, 2020.
- Hao, Y., Angluin, D., and Frank, R. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. TACL , 10:800-810, 2022.
- Hesse, W. Division is in uniform TC 0 . In International Colloquium on Automata, Languages, and Programming , pp. 104-114. Springer, 2001.
- Lindner, D., Kramár, J., Rahtz, M., McGrath, T., and Mikulik, V. Tracr: Compiled transformers as a laboratory for interpretability. arXiv , abs/2301.05062, 2023. · arXiv
- Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. In ICLR , 2023.
- Merrill, W. and Sabharwal, A. The parallelism tradeoff: Limitations of log-precision transformers. TACL , 11:531-545, 2023.
- Merrill, W., Ramanujan, V., Goldberg, Y., Schwartz, R., and Smith, N. A. Effects of parameter norm growth during transformer training: Inductive bias from gradient descent. In EMNLP , 2021.
- Merrill, W., Sabharwal, A., and Smith, N. A. Saturated transformers are constant-depth threshold circuits. TACL , 10, 2022.
- Pérez, J., Marinkovi´ c, J., and Barceló, P. On the Turing completeness of modern neural network architectures. In ICLR , 2019.
- Thoppilan, R., Freitas, D. D., Hall, J., Shazeer, N. M., Kulshreshtha, A., Cheng, H.-T., Jin, A., Bos, T., Baker, L., Du, Y., Li, Y ., Lee, H., Zheng, H., Ghafouri, A., Menegali, M., Huang, Y., Krikun, M., Lepikhin, D., Qin, J., Chen, D., Xu, Y., Chen, Z., Roberts, A., Bosma, M., Zhou, Y., Chang, C.-C., Krivokon, I. A., Rusch, W. J., Pickett, M., Meier-Hellstern, K. S., Morris, M. R., Doshi, T., Santos, R. D., Duke, T., Søraker, J. H., Zevenbergen, B., Prabhakaran, V., Díaz, M., Hutchinson, B., Olson, K., Molina, A., Hoffman-John, E., Lee, J., Aroyo, L., Rajakumar, R., Butryna, A., Lamm, M., Kuzmina, V. O., Fenton, J., Cohen, A., Bernstein, R., Kurzweil, R., Aguera-Arcas, B., Cui, C., Croak, M., Chi, E., and Le, Q. LaMDA: Language models for dialog applications. ArXiv , abs/2201.08239, 2022. · arXiv
- Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. Attention is all you need. In NeurIPS , 2017.
- Weiss, G., Goldberg, Y., and Yahav, E. On the practical computational power of finite precision RNNs for language recognition. In ACL , 2018.
- Weiss, G., Goldberg, Y., and Yahav, E. Thinking like transformers. ICML , 2021.
- Xiong, R., Yang, Y., He, D., Zheng, K., Zheng, S., Xing, C., Zhang, H., Lan, Y., Wang, L., and Liu, T.-Y. On layer normalization in the transformer architecture. In ICML , 2020.
- Authors
- Merrill, W., & Sabharwal, A.
- Venue
- Advances in Neural Information Processing Systems 36
- Published
- 2023
- Pages
- 52453-52463
- ISSN
- 1049-5258 (ISSN-L)
- OpenAlex
- W7133231252
- Cited by
- 6
- References
- 0
- Citations by year
- 2025: 1 · 2024: 3 · 2023: 2
- FWCI
- 1.07
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- neural information processing systems (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1922658)
- Allen Institute for Artificial Intelligence
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Numerical Methods and Algorithms
- Keywords
- floating-point arithmetic
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
