mlsanityData to 7 Oct 2026

Transformers as Transducers

arXiv 2404.02040 ↗First posted 2 Apr 2024cs.FL cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the sequence-to-sequence mapping capacity of transformers by relating them to finite transducers, and find that they can express surprisingly large classes of transductions. We do so using variants of RASP, a programming language designed to help people "think like transformers," as an intermediate representation. We extend the existing Boolean variant B-RASP to sequence-to-sequence functions and show that it computes exactly the first-order rational functions (such as string rotation). Then, we introduce two new extensions. B-RASP[pos] enables calculations on positions (such as copying the first half of a string) and contains all first-order regular functions. S-RASP adds prefix sum, which enables additional arithmetic operations (such as squaring a string) and contains all first-order polyregular functions. Finally, we show that masked average-hard attention transformers can simulate S-RASP.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 19 of its 38 references that are in the map. First posted on arXiv 2 Apr 2024.

Builds on

19 of 38 references.

References · 19

  1. 2017Attention Is All You Needcited by 59,932
  2. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Themcited by 1,767
  3. 2018Generating Wikipedia by Summarizing Long Sequencescited by 333
  4. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  5. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  6. 2022Neural Networks and the Chomsky Hierarchycited by 214
  7. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  8. 2021Thinking Like Transformerscited by 182
  9. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  10. 2023Representational Strengths and Limitations of Transformerscited by 132
  11. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  12. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
7 more
  1. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  2. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 99
  3. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  4. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  5. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 47
  6. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 37
  7. 2017Logical and Algebraic Characterizations of Rational Transductionscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 4; 2026: 1.

8 papers.

  1. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  2. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  3. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  4. 2024ALTA: Compiler-Based Analysis of Transformerscited by 7
  5. 2025The Transformer Cookbookcited by 5
  6. 2025Is In-Context Learning Learning?cited by 2
  7. 2025On the Existence of Universal Simulators of Attentioncited by 1
  8. 2026Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformerscited by 0