Partial Answer of How Transformers Learn Automata

Tiantian ZHANG (Crystal) · 2025

Read Partial Answer of How Transformers Learn Automata by Tiantian ZHANG (Crystal) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20395.txt.

Introduction

Tiantian Zhang offers a partial answer to how transformers learn rule machines in this 2025 paper. Transformers are the models behind modern language tools. Automata are simple machines that follow fixed rules step by step, and how a transformer can mimic one is an open question.

Zhang builds a frame that mimics finite automata inside a transformer. It uses tools from the math of symmetry, joining group products with wave-based modules. The frame yields leaner transformer builds for such tasks. The paper is brief and states its claim plainly. It gives theory readers one clear path toward a full answer.

Catalog record

CREATORTiantian ZHANG (Crystal)
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20395

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Partial Answer of How Transformers Learn Automata Tiantian ZHANG (Crystal) Abstract We introduce a novel framework for simulating finite automata using representation-theoretic semidirect products and Fourier modules, achieving more efficient Transformer-based implementations. Classical Krohn–Rhodes theory decomposes automata into cascades of simple groups and flip-flop memories, but this decomposition leads to deep, sequential simulation circuits with large embedding dimensions. In contrast, we model the automaton’s transition monoid as a semidirect product M = N ⋊ H M=N\rtimes H , where HH is a group acting linearly on a monoidal memory component NN. This formulation captures both control (via HH) and memory (via NN) in a unified, low-depth structure. Using representation theory and Fourier analysis over finite groups and monoids, we embed the states of NN and HH jointly into a flat feature space, enabling parallelizable updates via linear operations. Our method achieves Transformer simulation depth O ⁡ ( log ⁡ T ) O(\log T) , compared to O ⁡ ( log ⁡ T ⋅ log ⁡ | Q | ) O(\log T\cdot\log|Q|) for prime decompositions, and avoids width blowup even for automata with rich memory structures. The approach subsumes classical group-only models and extends naturally to automata with additive or stack-like monoidal memories, offering a new, fully parallelizable algebraic foundation for automaton-to-Transformer compilation. 1 Introduction In the original paper [ 1 ] , it states for the future direction: Finer-grained circuit complexity of self-attention: For certain automata of interest (e.g. bounded Dyck language parsers (Yao et al., 2021), and the gridworld automata from Theorem 3), there exist extremely shallow Transformer solutions, with depth independent of both T and |Q| . Which other natural classes of automata have this property of “beyond Krohn-Rhodes” representability? This paper answers: The Fourier composition module shows that automata whose state spaces form algebraic groups (especially abelian groups like \mathbb{Z}_{p} ) and whose transitions are group actions can be simulated by extremely shallow Transformer circuits, with depth independent of both input length T and state size |Q| . Thus, natural classes like modular counters, abelian group automata, and cumulative phase trackers have this “beyond Krohn-Rhodes” representability. 2 Shallow Fourier Transformer Setup 2.1 Fourier Composition Module for Modular Counters Let Q=\mathbb{Z}_{p} denote the cyclic group of integers modulo p , and let \omega=e^{2\pi i/p} denote the primitive p -th root of unity. The standard Fourier embedding of a state x\in Q is given by: \Phi(x)=\left(\omega^{0x},\omega^{1x},\dots,\omega^{(p-1)x}\right)\in\mathbb{C}^{p}. Given two transition functions f,g:Q\to Q , we define their Fourier composition via: \varphi_{\text{fourier}}(f,g)=F^{-1}\left(F(f)\cdot F(g)\right), where: • F(f) and F(g) denote the discrete Fourier transforms (DFT) of f and g , • \cdot denotes pointwise (Hadamard) product, • F^{-1} denotes the inverse DFT over \mathbb{Z}_{p} . Operationally, the module applies: 1. Fourier transform to both inputs: F(f) , F(g) , 2. Pointwise multiplication: F(f)\cdot F(g) , 3. Inverse Fourier transform to recover the composed function. This Fourier composition module can be implemented as either: • A fixed attention block with sinusoidal basis projections, or • A learned complex-valued linear layer operating in the frequency domain. 2.2 Relation to Attention and Positional Encoding The Fourier embedding \Phi(x) naturally parallels the positional encodings used in Transformer architectures. Each position x is mapped into a high-dimensional complex vector capturing all phase information relative to \mathbb{Z}_{p} . Thus, attention over such Fourier-embedded states amounts to operations in the frequency domain. The attention layer used here acts by taking average (or learned) interactions between the Fourier embeddings, aligning with the fixed or learned frequency interactions. (The frequency stuff is inspired by [ 2 ] ) Because Fourier transforms are linear, this attention can be realized by fixed-weight projections or by a shallow learned layer. The proof of how to embedding is in A.1 2.2.1 Summary of Mapping Stage Operation Embedding Fourier basis projection \Phi Query/Key/Value Identity maps Attention Frequency-wise multiplication (Hadamard product) Output Inverse Fourier transform F^{-1} 2.3 Depth Analysis of the Fourier Module 2.3.1 Length Proof Intuition We now formally prove that the Fourier composition module has depth O(1) , independent of sequence length T . Lemma 1 (Informal) . The Fourier composition module operates with depth O(1) , independent of sequence length T . Proof. At each position t , given f_{t},g_{t}:Q\to Q , the module computes: \varphi_{\text{fourier}}(f_{t},g_{t})=F^{-1}(F(f_{t})\cdot F(g_{t})). This involves: • Applying a fixed Fourier transform F (a matrix multiplication of size p\times p ), • A pointwise Hadamard product (entrywise multiplication), • Applying a fixed inverse Fourier transform F^{-1} (another matrix multiplication). Each of these operations has complexity depending only on p , not on the sequence length T . Moreover, they act independently at each token t , requiring no recurrence or sequential accumulation. Thus, the entire computation can be executed in parallel across all T positions with constant (non-growing) depth, determined only by the fixed sequence of Fourier transforms and pointwise operations. Therefore, the overall depth of the Fourier composition module is O(1) , independent of T . ∎ 2.4 Proof of Bound of Simulation Automata Definition 1 (Modular automaton) . A modular automaton is a semiautomaton A=(Q,\Sigma,\delta) where: • The state set is Q=\mathbb{Z}_{p} for some prime p , • The input alphabet \Sigma is arbitrary, • The transition function \delta:Q\times\Sigma\to Q consists of modular functions over \mathbb{Z}_{p} , meaning for each \sigma\in\Sigma , \delta(\cdot,\sigma) is a function of the form: x\mapsto a_{\sigma}x+b_{\sigma}\mod p, for some fixed coefficients a_{\sigma},b_{\sigma}\in\mathbb{Z}_{p} . Theorem 1 (Constant-depth Transformer simulation of modular automata) . Let A=(Q,\Sigma,\delta) be a modular automaton. Then there exists a Transformer of constant depth, width O(p) , and fixed attention structure, which simulates A over arbitrary input sequences of length T , with no dependence on T in either the depth or the width. Proof. We construct a Transformer block as follows: 1. Embedding: Each token x\in Q=\mathbb{Z}_{p} is mapped into its Fourier basis embedding: \Phi(x)=(\omega^{0x},\omega^{1x},\omega^{2x},\dotsc,\omega^{(p-1)x})\in\mathbb{C}^{p}, where \omega=e^{2\pi i/p} is a primitive p -th root of unity. 2. Transition simulation: Each transition x\mapsto a_{\sigma}x+b_{\sigma}\mod p corresponds to an action in Fourier space: • Modular multiplication x\mapsto a_{\sigma}x corresponds to permuting Fourier coefficients, • Modular addition x\mapsto x+b_{\sigma} corresponds to multiplying Fourier coefficients by phases \omega^{jb_{\sigma}} , • Thus, applying \delta(\cdot,\sigma) amounts to a simple, fixed linear operation in the Fourier basis. 3. Locality: Fourier transform, coefficient-wise phase shift, and inverse Fourier transform each act independently per token, requiring constant-time operations regardless of sequence length T . 4. Constant depth: Fourier transform, pointwise multiplication, and inverse Fourier transform can each be implemented with O(1) Transformer layers. Thus, overall simulation depth is O(1) , independent of both T and p (for fixed p ). 5. Width: We define width as the dimension of the per-token embeddings at each layer. Since each token is mapped into \mathbb{C}^{p} via the Fourier embedding, the width is O(p) , independent of the sequence length T . Fourier space has size p but no sequential steps are needed 6. Comparison to explicit counting: Previous constructions (e.g., Lemma 6) simulate modular counting explicitly over time and require width O(pT) to store evolving states. In contrast, working in Fourier space compresses the entire evolution into width O(p) , achieving a constant factor improvement. Thus, modular automata over \mathbb{Z}_{p} with modular affine transitions can be simulated by constant-depth, bounded-width Transformers. ∎ 3

Read the complete text