PaperlayerView exact revision on arXiv

Source-linked AI summary

Transformers Learn Shortcuts to Automata

Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril Zhang

arXiv:2210.10749v2cs.LGcs.FLstat.ML

TL;DR

The paper asks what solutions shallow, non-recurrent Transformers learn when representing sequential algorithmic computations. It studies semiautomata theoretically and empirically, showing that hierarchical shortcut constructions can replace recurrent iteration with shallow parallel computation. These shortcuts can be learned by standard training, but they lack out-of-distribution robustness.

  • Problem

    The paper investigates how Transformers lacking recurrence can perform sequential algorithmic reasoning using far fewer layers than the number of reasoning steps.

  • Method

    The paper combines theoretical analysis of semiautomaton simulations with synthetic experiments training Transformers across varied automata.

  • Results

    Shortcut solutions replace T sequential iterations with L ≪ T parallel self-attention layers, with logarithmic-depth solutions always existing and constant-depth solutions common in the characterized classes.

  • Takeaways & Limitations

    Hierarchical reparameterizations provide a framework for understanding how shallow Transformers can implement bounded-memory algorithmic computations.

  • Takeaways & Limitations

    The learned shortcuts generalize poorly out of distribution, including to unseen sequence lengths, and perform worse than RNNs under limited supervision.

Abstract

from arXiv · show

Algorithmic reasoning requires capabilities which are most naturally understood through recurrent models of computation, like the Turing machine. However, Transformer models, while lacking recurrence, are able to perform such reasoning using far fewer layers than the number of reasoning steps. This raises the question: what solutions are learned by these shallow and non-recurrent models? We find that a low-depth Transformer can represent the computations of any finite-state automaton (thus, any bounded-memory algorithm), by hierarchically reparameterizing its recurrent dynamics. Our theoretical results characterize shortcut solutions, whereby a Transformer with $o(T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We find that polynomial-sized $O(\log T)$-depth solutions always exist; furthermore, $O(1)$-depth simulators are surprisingly common, and can be understood using tools from Krohn-Rhodes theory and circuit complexity. Empirically, we perform synthetic experiments by training Transformers to simulate a wide variety of automata, and show that shortcut solutions can be learned via standard training. We further investigate the brittleness of these solutions and propose potential mitigations.

1 Introduction

The paper studies how shallow, non-recurrent Transformers can represent sequential algorithmic computations. It shows that semiautomaton simulations admit shortcut solutions, including logarithmic- and sometimes constant-depth constructions, which can be learned but may be brittle.

  • Motivation: The paper asks how a shallow, non-recurrent Transformer can represent computations that are naturally described by sequential models.This addresses the mismatch between sequential computational rules and Transformers whose depth can be much smaller than sequence length.
  • Core idea: Transformers learn shortcut solutions that simulate semiautomata with a shallow parallel circuit instead of iterating the single-step recurrence.These shortcuts hierarchically reparameterize the semiautomaton’s global transition dynamics.
  • Theoretical results: Logarithmic-depth shortcuts always exist, while constant-depth shortcuts exist for solvable semiautomata.The paper relates the constant-depth result to the Krohn-Rhodes theorem.
  • Theoretical results: Constant-depth shortcuts do not exist for non-solvable semiautomata unless TC0 = NC1.This establishes a complexity-theoretic boundary for constant-depth simulation.
  • Special constructions: Gridworld semiautomata admit even shorter shortcuts, with depth independent of both sequence length and the number of states.This result goes beyond the general guarantees supplied by the structure theorems.
  • Experiments: Standard training successfully learns shallow shortcut solutions across a wide variety of semiautomaton simulation problems.The experiments report that gradient-based training works despite the non-convex optimization problem.
  • Limitations and mitigation: The learned shortcuts show poor out-of-distribution generalization and perform worse than RNNs under limited supervision.Recency-biased scratchpad training can guide autoregressive Transformers toward iterative RNN-like solutions.

2 Preliminaries

The preliminaries formalize semiautomata, their induced transformation semigroups, and the simulation task. They then contrast recurrent RNN computation with shallow Transformer computation and define shortcut depth and efficiency.

  • Semiautomata: A semiautomaton consists of finite states, a finite input alphabet, and a deterministic transition function.Starting from q0, it produces a state sequence by applying qt = δ(qt−1, σt) at each position.
  • Simulation task: Simulation maps an input sequence to the semiautomaton’s full state trajectory for a fixed starting state.A function class simulates the automaton at length T when it provides such a simulator for every starting state.
  • Algebraic structure: Each semiautomaton induces a transformation semigroup generated by the state mappings associated with input symbols.If the identity is included it is a transformation monoid; if every mapping is invertible it is a permutation group.
  • Recurrent models: An RNN iterates a recurrent unit across positions and can simulate any semiautomaton when that unit represents the transition function.This makes recurrent simulation the canonical sequential construction.
  • Transformers: A Transformer alternates self-attention and position-wise MLP blocks, with shared weights across positions but no recurrence across layers.Attention mixes information across positions, while the MLP performs position-wise function approximation.
  • Shortcut solutions: A T-layer Transformer can implement the sequential solution by assigning one layer to each state transition, while shortcuts use significantly smaller depth.Typical Transformers have L ≪ T, making their sequential computation steps highly parallelizable compared with RNNs.
  • Efficiency measures: The paper measures Transformer efficiency using computational depth, embedding dimension, attention width, MLP width, weight norms, and floating-point precision.Transformer depth scales as Θ(L), whereas RNN depth scales as Θ(T).

3 Theory: shortcuts abound

The theory shows that shallow, non-recurrent Transformers can simulate semiautomata through hierarchical composition rather than explicit step-by-step recurrence. Logarithmic-depth shortcuts always exist, while constant-depth solutions cover solvable semiautomata and depth-2 solutions cover gridworlds.

  • General shortcut constructions: Shortcuts replace explicit iteration with hierarchical composition of transition functions, allowing Transformers to simulate semiautomata in depth o(T).The construction composes transformations δ(·, σ) rather than representing every intermediate state through recurrent layers.
  • General shortcut constructions: O(log T)-depth shortcuts simulate every finite semiautomaton with embedding dimension O(|Q|), attention width O(|Q|), and MLP width O(|Q|^2).
  • Krohn-Rhodes shortcuts: Constant-depth shortcuts exist for solvable semiautomata through Krohn-Rhodes decomposition into modular counters and resettable memory units.The cascade product combines these components with depth depending on |Q| rather than T.
  • Efficiency: The Transformer implementation is efficient because positional weight sharing removes suboptimal T factors from parameter count.
  • Gridworld shortcuts: Depth 2 suffices for gridworld simulation, using self-attention to detect the nearest boundaries with embedding dimension O(1) and attention width O(n).This improves over the general guarantees because the gridworld structure admits a particularly concise parallel construction.
  • Lower bounds: Constant-depth simulation of non-solvable semiautomata is unavailable under standard complexity assumptions: it would imply TC0 = NC1.Theorem 4 formalizes this as a barrier for polynomial-width, O(log T)-precision Transformers with depth independent of T.

4 Experiments: can SGD find the shortcuts?

Synthetic experiments test whether standard gradient-based training can discover the theoretically available shortcuts. Training reaches high in-distribution accuracy across semiautomata, but optimization is unstable and performance degrades under distribution shift or atypical counts.

  • Learnability: >99% in-distribution accuracy was obtained for every tested finite-state semiautomaton, including those generating the non-solvable groups A5 and S5.The experiments trained shallow GPT-2-like Transformers on 19 semiautomata with sequence length T = 100.
  • Learnability: More complex semiautomata, including those corresponding to non-abelian groups, required deeper networks to learn.
  • Generalization: Theoretical constructions can achieve 100% accuracy, but MLPs without periodic activations may need to memorize mod-n values and fail on unseen outlier counts.
  • Mechanistic interpretation: Preliminary attention visualizations found flat summation and conditional-reset heads, while the authors do not claim these mechanisms are generally isomorphic to the proofs.
  • Optimization: Training was highly unstable, with high variance, negative progress, or accuracy that decayed during continued optimization.Reported results focus on the best model among 20 replicates because the primary goal was to test whether training could find shortcuts.

5 Further experiments: more challenging settings

The experiments test shallow Transformer shortcuts under partial supervision and out-of-distribution evaluation. Transformers achieve good in-distribution performance, but recurrent solutions are more robust when labels are sparse, distributions shift, or sequence lengths increase.

  • Incomplete and indirect supervision: Transformers find good in-distribution solutions across the partially observable settings considered.Latent-state observations preserve representational equivalence with the fully observable case, although learning can be harder.
  • Incomplete and indirect supervision: Sparse state labels can prevent Transformers from finding good solutions, whereas LSTM performance remains robust.The comparison varies the probability that each state is revealed during training on length-100 sequences.
  • Out-of-distribution evaluation: Distribution shifts expose shortcut failures: parity accuracy decreases as the input-1 probability moves away from the training value Pr[σ = 1] = 0.5.The proposed mechanism is counting 1s and then computing modulo 2, which can fail on counts rarely seen during training.
  • Length generalization: Transformers lose accuracy on sequence lengths unseen during training, while LSTMs retain perfect performance; positional-encoding changes improve but do not perfect length generalization.Recency-biased scratchpad training guides Transformers toward recurrent depth-T solutions that generalize to longer lengths.
  • Interpretation: Shortcut solutions can be statistically brittle because they may represent intermediate variables such as counts rather than recurrent states.This sensitivity produces failures on rare counts that recurrent models do not exhibit.
  • Computational-statistical tradeoffs: Shallow architectures offer O(log T) or O(1) computation versus O(T) for recurrent processing, creating a computational-statistical tradeoff.The paper concludes that neither architecture dominates across these algorithmic settings.

6 Conclusions and future work

The paper concludes that shallow Transformers can replace recurrent finite-state computation with efficient shortcut circuits, while empirical shortcuts remain vulnerable to distribution and length shifts. It highlights algebraic representation, optimization, interpretability, and practical architecture design as open directions.

  • Conclusions: Shallow Transformers replace T sequential recurrent iterations with a single pass through L ≪ T parallel self-attention layers.Theoretical results characterize extremely shallow solutions, including depth independent of context length T.
  • Conclusions: Gradient-based optimization successfully finds shortcut solutions across the studied automaton-simulation problems.The authors identify this empirical tractability as a striking phenomenon whose precise mechanism remains open.
  • Future work: Krohn-Rhodes theory and circuit complexity provide tools for characterizing constant-depth Transformer representations of recurrent computations.The paper connects Transformer arithmetic circuits to NC1 and ACC0 semigroup word-problem constructions.
  • Future work: Open questions include which natural automata classes admit depth independent of both T and |Q|.The gridworld constructions supply one example of this stronger representability property.
  • Future work: Understanding why gradient descent discovers algebraic shortcuts remains open, especially because related problems are known to be PSPACE-hard.The paper frames hierarchical representation learning as an active frontier.
  • Future work: Automaton simulation offers challenging test cases for mechanistic interpretability, but preliminary analysis interpreted only a small number of simple models.The authors propose these tasks for studying Transformer inductive biases.

A.4 The Transformer architecture

The theoretical Transformer class alternates causal self-attention and position-wise feedforward blocks, with optional residual and positional-encoding components. Its complexity is summarized by depth, widths, sequence length, parameter norms, and numerical precision.

  • Architecture: An L-layer Transformer alternates self-attention blocks and feedforward blocks in a sequence-to-sequence network.The parameter space is the Cartesian product of the individual block parameters, without recurrent weight sharing by default.
  • Attention: Causal self-attention uses query-key scores, a causally masked softmax, value mixtures, and an output projection at each position.Each position attends only to earlier or current positions, and multi-head attention sums multiple independently parameterized heads.
  • Feedforward MLP: The position-wise MLP applies the same ReLU-activated nonlinear map independently to every sequence position.Position encodings are added to the first layer’s input.
  • Residual connections: Residual connections preserve access to earlier representations and position embeddings, while equivalent non-residual constructions can implement or negate them.The theoretical constructions may use residual connections selectively as workspace dimensions.
  • Architectural conventions: The theoretical presentation omits layer normalization and uses padding tokens to simplify constructions without changing the main representational results.Padding is optional in principle; the stated constructions use τ = Θ(T) or τ = 1 depending on the theorem.
  • Complexity measures: Transformer circuit complexity scales as O(T · L · w) gates and O(T · L · w^2) wires, with embedding dimension d independent of T.Depth L corresponds to repeated attention–MLP blocks, and width aggregates attention and MLP widths.
  • Complexity measures: The framework tracks infinity-weight norms and bit precision, but the paper does not directly investigate generalization beyond its positive experiments.Theoretical weight norms can scale with T, and finite precision connects real-valued computations to discrete circuits.

A.5 Additional discussion of related work

The related work spans neural-network studies of formal languages, parity, modular arithmetic, reasoning tasks, and synthetic combinatorial generalization. This paper positions its theoretical guarantees and empirical analyses as a broader account of shortcut solutions in shallow, non-recurrent Transformers.

  • Synthetic combinatorial tasks: The paper further connects shortcut solutions to pointer-value retrieval, LEGO-style chain reasoning, and synthetic combinatorial experiments.These comparisons concern tasks where Transformers can solve parts of a structured problem without naively executing the full chain.
  • Formal languages: Prior work studies Transformers on Dyck languages, including depth-2 constructions for bounded-depth variants.The paper presents its semiautomata framework as encompassing bounded-depth Dyck languages and generalizing these constructions.
  • Algorithmic and symbolic tasks: Transformer research has also examined sparse parity, binary prefix sums, modular addition, mathematical reasoning, and program synthesis.These studies address related algorithmic or symbolic tasks through theoretical analysis, empirical training, or mechanistic interpretation.
  • Formal-language scope: For regular languages, the paper claims O(log T)-depth networks can simulate all context-free languages, while O(1)-depth networks represent some of them.It identifies non-solvable syntactic monoids as obstructing regular languages and distinguishes its conclusions from studies of inductive inference.
  • Generalization: The paper relates its setting to work on length, size, and algorithmic generalization, including recurrent models that use recurrence to simulate extra computational steps.Its use of scratchpads is identified as inspired by prior length-generalization work.
  • Recurrent and non-recurrent models: Related work on recurrent Transformers and autoregressive sequence transduction motivates the paper’s structural analysis of shallow models fitting recurrent dynamics over long sequences.The paper also connects indirectly supervised semiautomata to next-token prediction when continuations depend on a latent state.

B Experiments

This section provides a full description and discussion of the in-distribution simulation experiments reported in Section 4.

  • Experiments: The section fully describes the in-distribution simulation experiments from Section 4.It also discusses those experiments.
  • Experiments: The experiments are discussed as part of the paper’s Section 4 simulation results.The passage identifies Section 4 as the location of the referenced experiments.
  • Experiments: The section combines experimental description with discussion rather than introducing a separate experiment set.The supplied passage characterizes its purpose as a full description and discussion.

B.1.1 Shallow Transformers simulate small groups and semigroups

The experiments train shallow GPT-2-like Transformers on 19 semiautomata, varying depth from 1 to 16 layers, and evaluate token-level state prediction on held-out sequences. Standard training finds high in-distribution accuracy across tasks, while the required depth varies with algebraic structure and training is unstable.

  • Results: Transformers achieve high in-distribution token-level accuracy across tasks, with performance generally improving as the number of layers increases.Evaluation uses independently sampled sequences of length T = 100; some non-monotonicity is attributed to training instability.
  • Results: The minimum depth for 99%+ performance tends to be lowest for semigroups without groups, increases for larger non-abelian groups, and is highest for the non-solvable group S5.The experiments do not control for differences in the amount of supervision provided by larger groups.
  • Results: Q8 is harder to learn than D8 despite equal cardinality, matching the theoretical distinction between their constant-depth shortcut constructions.D8 admits a semidirect-product decomposition, whereas Q8 requires embedding in a larger wreath-product structure.
  • Training stability: Training is unstable, showing high variance, negative progress, and differences between maximum and median accuracy across runs.These effects appear in training curves and in the gap between Figures 8 and 9.
  • Interpretation: Attention visualizations support a two-stage shortcut for Gridworld: prefix-sum computation followed by boundary detection that resets the relevant history.Later positions place no attention on tokens before the detected boundary, consistent with ignoring pre-boundary history.
  • Additional experiments: GPT-2-like models reach near-perfect in-distribution accuracy on additional tasks, while positional encoding affects learning difficulty for the (abab)∗ automaton.Linear positional encoding is challenging, whereas sinusoidal encoding makes learning easier in the reported cases.
  • Additional experiments: Transformer training is less tolerant than LSTM training of incomplete supervision for S5, although performance for C2 remains stable across the tested supervision levels.The reported degradation is specific to lower supervision for S5.

B.2.3 Out-of-distribution generalization

Vanilla Transformers lose accuracy when test input distributions differ from training, consistent with shortcut solutions based on training-frequency statistics. Scratchpad training with recency bias guides them toward recurrent solutions that are more robust to distribution shift.

  • Negative results: Transformer accuracy degrades sharply as the input-symbol probability moves away from its training value, whereas an LSTM maintains perfect accuracy.The proposed explanation is that the Transformer counts frequent patterns, while the LSTM recurrently tracks parity.
  • Negative results: Varying the number of 1s confirms that Transformer performance declines when counts move away from those expected during training.The observed asymmetry may reflect a learned correlation between count and position.
  • Mitigation: Scratchpad training interleaves inputs and states so the Transformer predicts each state from the preceding predicted state.This changes the sequence-to-sequence setup from one long-range prediction problem into sequential state-prediction problems.
  • Mitigation: Scratchpads alone do not prevent the parallel shortcut, because the model can ignore scratchpad positions.An explicit recency bias is therefore combined with scratchpad training.
  • Mitigation: Scratchpad plus recency bias trains Transformers to learn recurrent solutions that are resilient to distribution shift, though the shortcut’s computational advantage is lost.The paper leaves robust shortcut solutions for future work.

B.2.4 Length generalization

Transformers generalize poorly to unseen sequence lengths, but positional strategies and recurrently guided training can improve this behavior. Scratchpad with recency bias is effective, while positional encoding choices trade in-distribution performance against length extrapolation.

  • Results: Transformer accuracy drops sharply on sequence lengths unseen during training, unlike LSTM’s perfect performance across tested scenarios.Randomly shifting positions or removing positional encodings helps but does not make performance perfect.
  • Results: Scratchpad with recency bias guides Transformers toward recurrent depth-T solutions that generalize to longer sequence lengths.Without recency bias, scratchpad training shows no improvement on length generalization.
  • Evaluation: Figure 14 reports mean accuracy with standard-error shadows over 25 (±1) replicates for Dyck and C2 length tests.The figure compares a Transformer with scratchpad and recency-bias variants.
  • Positional encoding: Sinusoidal positional encoding can generalize worse than linear encoding despite comparable or better in-distribution performance.On Grid9, sinusoidal encoding performs significantly worse at doubled length; on partially observed (abab)*, its in-distribution advantage shrinks substantially.
  • Positional encoding: Random positional shifts significantly improve Transformer length generalization on both Dyck and C2.The authors suggest that unseen positional distributions are a main challenge for length generalization.
  • Positional encoding: Removing positional encoding improves generalization for both parity and Dyck, although the Dyck result is less clearly understood.Causal masking still provides implicit position information.

C.2 Proof of Theorem 1: Logarithmic-depth shortcuts via parallel prefix sum

Theorem 1 constructs a logarithmic-depth Transformer that simulates any finite semiautomaton by parallelizing prefix compositions of per-input transition functions. Attention selects composition partners, while MLPs implement function composition.

  • Theorem statement: A depth-⌈log2 T⌉ Transformer continuously simulates any semiautomaton at length T with polynomial architectural resources.The theorem gives embedding dimension 2|Q|+2 and MLP width |Q|2+|Q|, alongside explicit weight-norm bounds.
  • Construction: The construction represents each input symbol as a transition map and computes all prefix compositions through a binary-tree circuit.This replaces sequential recurrence with associative parallel composition.
  • Construction details: The construction assumes T is a power of 2 and handles general T through padding.It also introduces T padding positions to simplify positional selection.
  • Function composition: A three-layer ReLU MLP composes two transition maps into the transition map of their composition.Its dimensions and weights depend only on the finite state set Q.
  • Recursive parallel scan: At layer l, attention looks back by 2^l positions so each layer performs one stage of the parallel prefix scan.Position embeddings implement these look-backs using rotation matrices.
  • Readout: The final representation contains each prefix transition map, from which the state sequence can be read out.An additional MLP is needed for one-hot state outputs.

C.3 Proof of Theorem 2: Constant-depth shortcuts via Krohn-Rhodes decomposition

Theorem 2 uses Krohn-Rhodes decomposition to obtain constant-depth shortcuts for solvable semiautomata. The proof reduces their dynamics to modular counters and memory units, implemented with shallow attention and MLP constructions.

  • Theorem statement: A solvable semiautomaton has a Transformer simulator of depth O(|Q|2 log |Q|).The construction uses a Krohn-Rhodes decomposition and provides explicit polynomial-size resource bounds.
  • Base cases: The proof begins with modular counters and memory units as the two basic components of the decomposition.The modular-counter construction uses flat prefix sums and an MLP for modular reduction.
  • Modular counter: A depth-1 Transformer continuously simulates a modular counter using unweighted prefix sums and a modular-sum MLP.Padding absorbs the attention normalization factor required for uniform prefix aggregation.
  • Memory unit: A depth-1 Transformer continuously simulates a memory semiautomaton by attending to the closest relevant non-no-op token.The construction uses a single attention head followed by a two-layer ReLU MLP.
  • Decomposition: Krohn-Rhodes theory decomposes transformation semigroups into elementary groups and flip-flop monoids.These components can be composed hierarchically through cascade products.
  • Decomposition: A cascade product composes semiautomata hierarchically, with later layers receiving inputs determined by preceding state sequences.This gives the factorized structure used by the proof.
  • Decomposition: The Krohn-Rhodes theorem supplies a transformation cascade whose components can be assembled into the target semiautomaton.The proof explicitly invokes this cascade decomposition as its structural foundation.

C.3.3 Simulating solvable groups

The construction simulates solvable groups by composing canonical group simulators through direct products, semidirect products, and wreath products. This yields Transformer simulations with depth logarithmic in group size, while direct products already give constant-depth simulations for finite abelian groups.

  • Canonical group semiautomata: Canonical group semiautomata use group elements as both states and input symbols, with transitions given by left multiplication.Starting from the identity, the state at time t is the product σ_tσ_{t−1}⋯σ_1.
  • Direct products: Direct-product simulators run component group simulations in parallel without increasing depth.This immediately gives constant-depth simulations for finite abelian groups, which decompose into direct products of cyclic groups.
  • Semidirect products: Semidirect-product simulation uses a 4-stage cascade, extending the direct-product construction to certain non-abelian groups.The construction applies the quotient-group simulator to re-map inputs for the normal-subgroup simulator; examples include S3, D2n, A4, and S4.
  • Wreath products: Wreath-product simulation combines a direct product of copies of N with a semidirect-product construction driven by H.The regular structure of the wreath-product mixing function avoids dependence on the full wreath-product group size in implementation-size measures.
  • Solvable-group bound: 3 log2 |G| bounds the depth of the Transformer simulation for every solvable group G represented as a permutation group.The result applies for every sequence length T ≥ 1, with the stated depth bound depending on group size rather than T.

C.3.4 Simulating semigroups

The semigroup construction lifts Transformer simulators for permutation-reset semiautomata through a Krohn-Rhodes transformation cascade. Its depth and other size measures are bounded explicitly in terms of the state and input spaces and the component simulators.

  • Permutation-reset components: Permutation-reset semiautomata are simulated by combining a group simulator with a memory semiautomaton and one additional layer.The resulting depth is at most 3 log2 |G| + 2, and its dimension is at most |G| + |Q| + 4.
  • Transformation cascade: The full semigroup simulator concatenates |Q| subnetworks, each implementing parallel component simulations followed by cascade routing.Each channel stores one component semiautomaton, while routing MLPs compute the next component’s encoding from predecessor states and the current input.
  • Size bounds: simA.depth = |Q| · (maxi{simi.depth} + 1) −1 ≤3|Q|2 log |Q| + 7|Q|.This bound follows from concatenating the cascade levels and the depth guarantee for the permutation-reset component simulators.
  • Size bounds: simA.dim = Pn i=1 simi.dim + 1 ≤2|Q|(|T (A)| + |Q| + 4) + 1.The extra dimension preserves the input symbol while separate channels hold the component representations.
  • Size bounds: simA.mlpWidth is bounded by 2|Q|(20|Q| |T (A)| T +4|Q|+|T (A)|2|Q|+ |Q|2|Q| |Σ|).The width accounts for component MLPs, cascade routing, and parallel execution within each level.

C.4 Proof of Theorem 3: Even shorter shortcuts for gridworld

The gridworld shortcut detects the latest boundary interaction from distinct prefix sums, then uses the post-boundary action sum to recover the state. A two-attention-layer Transformer implements this procedure with either logarithmic-depth or constant-depth MLPs.

  • Theorem 3: 2 attention layers simulate the (S + 1)-state gridworld for every positive sequence length T.The MLP can use depth O(log S) and width O(T + S), or depth O(1) and width O(T) + 2O(S), with weight norms bounded by poly(T).
  • Algorithmic insight: The boundary detector uses the most recent S + 1 distinct prefix sums rather than parsing the entire input sequence sequentially.Once the relevant boundary and its type are identified, the final state is obtained by summing the subsequent mapped actions and shifting by that boundary.
  • Transformer construction: The first attention layer computes prefix sums, while the second identifies nearby distinct values through circular embeddings and context-dependent retrieval.This division matches the Transformer construction: prefix sums are parallelized first, then distinct-value information supports boundary detection.
  • Correctness: If tmin > tmax, the state at tmin is 0; otherwise, the state at tmax is S.The case analysis identifies which boundary was visited from the ordering of the most recent minimum and maximum prefix-sum positions.
  • Depth-width trade-off: Max pooling reduces the MLP construction to O(1) depth and O(S) width, removing the dependence on T in the width.The alternative O(log S)-depth construction explicitly computes pairwise maxima and then min-pools them.

C.5 Proof of Theorem 4: Depth lower bound for non-solvable semiautomata

The paper proves a conditional depth lower bound for simulating non-solvable semiautomata with fixed-precision Transformers. The argument reduces the problem to circuit-complexity consequences involving NC1 and TC0.

  • Conditional lower bound: For sufficiently large T, fixed-precision Transformers of T-independent depth and polynomial width cannot simulate a non-solvable semiautomaton unless TC0 = NC1.The restriction applies to semiautomata whose transformation monoids contain non-solvable subgroups.
  • Reduction: The reduction uses NC1-completeness of semiautomaton simulation under NC0 reductions.A simulator of depth D would yield a depth-O(D) circuit for bounded-fan-in AND/OR/NOT circuits, via Barrington-style constructions.
  • Circuit simulation: The proof places constant-depth fixed-precision Transformers in TC0 by representing their arithmetic and attention operations with polynomial-size circuits.Position-wise matrix and MLP operations use polynomial-width circuits, while T-way attention summations use a TC0 addition construction.
  • Precision assumption: With O(log T) bits of precision, fixed-arity arithmetic can be represented by constant-depth polynomial-width AC0 circuits.The remaining subtle operation is summing T many O(log T)-bit numbers in softmax and attention mixtures.
Loading 2210.10749v2…