mlsanityData to 7 Oct 2026

A Logic for Expressing Log-Precision Transformers

arXiv 2210.02671 ↗First posted 6 Oct 2022cs.LG cs.CCcited by 67

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

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.

Key facts. Cited by 67 papers in the map (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 11 of its 29 references that are in the map. First posted on arXiv 6 Oct 2022.

Builds on

11 of 29 references.

References · 11

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2020On Layer Normalization in the Transformer Architecturecited by 906
  4. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  5. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  6. 2021Thinking Like Transformerscited by 182
  7. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  8. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  9. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  10. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  11. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 23; 2025: 26; 2026: 12.

67 papers.

Sort:

By area:

  1. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  2. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  3. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelscited by 186
  4. 2024The Illusion of State in State-Space Modelscited by 181
  5. 2025Hierarchical Reasoning Modelcited by 167
  6. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  7. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  8. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  9. 2024A Peek into Token Bias: Large Language Models Are Not Yet Genuine Reasonerscited by 73
  10. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  11. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  12. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 47
38 more
  1. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  2. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  3. 2024Memory3: Language Modeling with Explicit Memorycited by 39
  4. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 36
  5. 2025PaTH Attention: Position Encoding via Accumulating Householder Transformationscited by 32
  6. 2024Transformers Can Represent n-gram Language Modelscited by 31
  7. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  8. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  9. 2025The Geometry of Reasoning: Flowing Logics in Representation Spacecited by 21
  10. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  11. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  12. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  13. 2025Knee-Deep in C-RASP: A Transformer Depth Hierarchycited by 12
  14. 2025Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformerscited by 11
  15. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  16. 2025Circuit Complexity Bounds for Visual Autoregressive Modelcited by 10
  17. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  18. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  19. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9
  20. 2024Transformers as Transducerscited by 8
  21. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  22. 2025Quantitative Bounds for Length Generalization in Transformerscited by 8
  23. 2023MLRegTest: A Benchmark for the Machine Learning of Regular Languagescited by 7
  24. 2025The Counting Power of Transformerscited by 7
  25. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  26. 2024Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoningcited by 5
  27. 2024ENTP: Encoder-only Next Token Predictioncited by 5
  28. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
  29. 2025Efficient Turing Machine Simulation with Transformerscited by 4
  30. 2026Length Generalization Bounds for Transformerscited by 4
  31. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  32. 2025The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architecturescited by 3
  33. 2026Context-Free Recognition with Transformerscited by 3
  34. 2026Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidthcited by 3
  35. 2023Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languagescited by 2
  36. 2024A Transformer with Stack Attentioncited by 2
  37. 2023On The Expressivity of Recurrent Neural Cascadescited by 1
  38. 2024How Out-of-Distribution Detection Learning Theory Enhances Transformer: Learnability and Reliabilitycited by 1

50 most cited of 67 All 67 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025Transformers are Inherently Succinct
  2. 2024Transformer-based Language Models for Reasoning in the Description Logic ALCQ
  3. 2023Transformers in the Service of Description Logic-based Contexts
  4. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
  5. 2026To See the Unseen: on the Generalization Ability of Transformers in Symbolic Reasoning
  6. 2023Assessing Logical Reasoning Capabilities of Encoder-Only Transformer Models
  7. 2026On the Expressiveness of State Space Models via Temporal Logics
  8. 2024Reasoning in Transformers -- Mitigating Spurious Correlations and Reasoning Shortcuts