Reproduce “Transformers as Transducers” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, Ashish Sabharwal
Formal analysis reveals the sequence-to-sequence transduction capabilities of transformer architectures, mapping unique-hard attention models to aperiodic rational transductions and demonstrating that average-hard attention can simulate S-RASP, which computes aperiodic polyregular transductions and additional non-aperiodic functions. The study leverages RASP variants to characterize how positional information and prefix sum operations increase transformer expressivity.
Key insights
- RASP provides an effective intermediate representation for transformer analysis, simplifying the reasoning about their computational limits and capabilities by translating complex linear algebra into high-level programming constructs.
- Explicit position information (e.g., in B-RASP[pos]) and prefix sum operations (e.g., in S-RASP) are critical architectural primitives that significantly enhance transformer expressivity for sequence-to-sequence tasks.
- Average-hard attention transformers are formally more expressive than unique-hard attention transformers, being capable of simulating S-RASP and therefore a broader range of transductions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.