PaperlayerView exact revision on arXiv

Source-linked AI summary

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers

William Merrill, Ashish Sabharwal

arXiv:2503.03961v3cs.LGcs.CC

TL;DR

The paper studies whether minimally increasing transformer depth can overcome fixed-depth limits on sequential reasoning over long inputs. It analyzes highly uniform transformers with depth Θ(log n), proves expressivity results for regular languages and graph connectivity, and finds that depth scaling is more efficient than width or chain-of-thought scaling. Experiments on hard regular-language recognition closely match the theoretical depth requirements.

  • Problem

    Fixed-depth transformers cannot express regular-language recognition and graph connectivity under standard complexity conjectures, leaving bounded-context capacity and depth scaling requirements unclear.

  • Method

    The paper analyzes universal transformers that repeat a fixed layer block Θ(log n) times for inputs of length n, using uniform constructions including a division-and-remainder primitive.

  • Results

    Θ(log n) depth expresses regular languages and graph connectivity, while experiments show depth has a strong correlation with effective context length for hard regular-language recognition.

  • Takeaways & Limitations

    Depth scaling is more efficient than superpolynomial width scaling or superlogarithmic chain-of-thought scaling for these reasoning problems and supports practical depth selection.

  • Takeaways & Limitations

    Log-depth transformers still cannot express P-complete problems unless NC=P, and the experiments do not evaluate weight-reused looped transformers’ inductive biases or learning dynamics.

Abstract

from arXiv · show

Recent theoretical results show transformers cannot express sequential reasoning problems over long inputs, intuitively because their computational depth is bounded. However, prior work treats the depth as a constant, leaving it unclear to what degree bounded depth may suffice for solving problems over short inputs, or how increasing the transformer's depth affects its expressive power. We address these questions by analyzing transformers whose depth can grow minimally with context length $n$. We show even highly uniform transformers with depth $Θ(\log n)$ can express two important problems: recognizing regular languages, which captures state tracking abilities and was known to be expressible only by an unconventional, non-uniform model of transformers, and graph connectivity, which underlies multi-step reasoning. Notably, both of these problems cannot be expressed by fixed-depth transformers under standard complexity conjectures, demonstrating the expressivity benefit of growing depth. Moreover, our theory quantitatively predicts how depth must grow with input length to express these problems, showing that depth scaling is more efficient than scaling width or chain-of-thought steps. Empirically, our detailed experiments designed to bridge the expressivity vs. learnability gap reveal that our theoretical depth requirements for regular language recognition closely match the practical depth requirements for successfully training transformers. Thus, our results clarify how depth affects a transformer's reasoning capabilities, and provide practical guidance for effective depth selection for sequential reasoning.

1 Introduction

The paper asks how much bounded depth can accomplish on finite contexts and whether logarithmically growing depth enables problems beyond fixed-depth transformers. It analyzes highly uniform transformers and finds that Θ(log n) depth can solve regular-language recognition and graph connectivity, more efficiently than scaling width or chain-of-thought steps.

  • Motivation: Fixed-depth transformers are known to fail on regular-language recognition and graph connectivity beyond TC0, motivating depth as a route to sequential reasoning.These tasks correspond to state tracking and multi-step logical inference.
  • Approach: The paper studies universal transformers that repeat a fixed block Θ(log n) times on inputs of length n.The construction uses highly uniform transformers with shared weights across blocks and layers.
  • Main result: Θ(log n) depth suffices for regular-language recognition and graph connectivity over arbitrary context lengths.The construction works in a stronger uniform setting than prior non-uniform approaches.
  • Efficiency comparison: Superpolynomial width and superlogarithmic chain-of-thought steps are required for the same regular-language problems, making depth scaling more efficient.Figure 1 summarizes the contrasting asymptotic requirements.
  • Bounded contexts: A fixed depth d handles bounded inputs of size 2^O(d), including strings up to length 107 and graphs with up to 128 vertices at depth 32.At depth 80, the reported limits rise to 440K-length strings and graphs with up to 2.1B vertices.
  • Practical implication: The experiments provide practical guidance for choosing model depth and motivate dynamic depth as an inference-time compute strategy.The paper also reports that its theoretical depth requirements closely match training requirements for hard regular languages.

2 Preliminaries: Universal Transformers

Universal transformers use a fixed model whose repeated layers provide input-dependent depth, with computation represented in residual streams and standard attention and feedforward sublayers. The formalization assumes logarithmic depth and p-precise arithmetic, while identifying memory cleanup and numerical precision as important construction conditions.

  • Universal architecture: An (s,r,t)-universal transformer has s initial layers, r repeated layers, and t final layers, totaling s + r d(n) + t layers.The repeated block is selected cyclically during the input-dependent portion of the computation.
  • Computation: The model is unrolled with d(n)=⌈log n⌉, initializes residual streams from token embeddings and positional encodings, and selects the maximum-scoring output token.The output is produced by an unembedding projection after the final layer.
  • Uniformity: Universal transformers are uniform special cases of fixed-depth transformers, so a dynamic-depth construction yields a fixed-depth model for any bounded context length N.This uniformity is stronger because the same looped construction applies across input lengths.
  • Transformer sublayers: Each layer combines masked pre-norm, self-attention, and feedforward updates that add δ_i to the residual stream.Masked pre-norm selects residual dimensions before normalization, while feedforward updates use ReLU projections.
  • Positional information: The construction assumes a beginning-of-sequence marker or separable first positional encoding and uses no positional encodings by default.The stated positional-encoding generalization requires the first position to remain distinguishable.
  • Memory management: Intermediate residual-stream values must be reset to prevent outputs from earlier loop iterations interfering with later computation.The paper describes storing, reading, writing, and deleting numerical values in normalized or unnormalized representations.
  • Numerical precision: Scalars use p=c log n bits, and the analysis assumes addition, multiplication, division, exponentiation, and layer normalization are p-precise.The required internal precision for attention summation and layer normalization remains an open low-level question.

3 Fixed Depth Transformers Can Divide Small Integers

The paper constructs a seven-layer transformer block that divides small integers and computes remainders, providing a primitive for modular routing in later log-depth constructions. The proof uses attention to identify multiples, retrieve quotients, compare neighboring quotient groups, and recover quotient-remainder pairs.

  • Theorem: A seven-layer block computes normalized quotient and remainder values b_i and c_i when a_i=b_i m+c_i, given a_i≤i and c_i<m.The block uses causally masked attention and masked pre-norm.
  • Quotient recovery: The construction first marks positions that are multiples of m and stores their quotients, then retrieves the nearest preceding quotient to obtain floor(i/m).This establishes quotient information at every position before the later comparison steps.
  • Local comparisons: A third layer adds encodings of i−1 and i−2, enabling later layers to compare each position’s quotient with those of its two predecessors.These comparisons identify the local run of positions sharing a quotient.
  • Quotient and remainder: A fifth layer counts positions sharing the same quotient, excluding the first such position, and a sixth layer retrieves the quotient and remainder for a_i.The resulting values are ϕ(floor(a_i/m)) and ϕ(a_i mod m).
  • Cleanup: The final layer clears intermediate residual-stream values, completing the division computation without leaving temporary state.Cleanup is possible because the stored values have normalized or Boolean forms.
  • Relation to prior work: The division construction uses masked pre-norm rather than the nonstandard positional embeddings used by a related modular-counting construction.The comparison highlights a different implementation assumption rather than a different computational goal.

4 Log Depth Enables Recognizing Regular Languages

Logarithmic depth lets highly uniform transformers recognize regular languages for arbitrary input lengths, overcoming fixed-depth limitations while retaining standard architectural features. The construction also yields quantitative bounds for bounded-input recognition and extends to iterated associative operations.

  • Uniform log-depth construction: A single fully uniform transformer can recognize any regular language on strings of arbitrary length when unrolled to ⌈log2|w|⌉ depth.The construction uses fixed parameters independent of input length and supports residual connections and layer normalization.
  • Uniform log-depth construction: Theorem 1 uses a (0, 8, 9)-universal transformer with model dimension O(|Q|^2) for NFAs or O(|Q| log|Q|) for DFAs.The feedforward-width bounds depend on the automaton’s state count.
  • Expressivity beyond fixed depth: Under TC0 ≠ NC1, Θ(log n) depth provides expressive power unavailable to fixed-depth transformers for regular-language recognition.The result contrasts with prior constructions that used non-uniform parameters or nonstandard positional encodings.
  • Extensions: The framework extends to iterated binary associative operations, constructing an Θ(b log n)-layer transformer from a b-layer implementation of the operation.Iterated matrix multiplication is given as an example, with the theorem applying directly when matrices come from a fixed set.
  • Bounded-input implications: A fixed-depth d transformer recognizes strings whenever 4⌈log2|w|⌉ + 5 ≤ d, giving an explicit depth-to-context bound.An analogous bounded-length result applies to universal shared-parameter transformers.

5 Log Depth Enables Graph Connectivity

A highly uniform log-depth transformer can solve graph connectivity, a reachability problem beyond fixed-depth transformers under standard complexity assumptions. Its repeated layers implement logarithmic-scale path expansion, and the theorem yields a corresponding bounded-input depth guarantee.

  • Theorem and construction: A (17, 2, 1)-universal transformer with fixed dimension and feedforward width solves directed or undirected graph connectivity after ⌈log2 n⌉ repetitions.The input includes an n × n adjacency matrix, n^3 padding tokens, and unary source and target vertices.
  • Theorem and construction: The construction stores Bℓ(i,j) predicates for paths of length at most 2^ℓ and uses Cℓ(i,k,j) predicates as intermediate compositions.The repeated layers alternate between computing the Cℓ and Bℓ predicates.
  • Theorem and construction: The final layer retrieves B⌈log n⌉(s,t) at the source-target coordinate to decide whether the graph contains a path from s to t.The final token attends specifically to the position representing coordinates (s,t).
  • Expressivity beyond fixed depth: Log-depth transformers can solve graph connectivity even though NC1 circuits cannot unless NC1 = NL.Graph connectivity is NL-complete and is therefore a key test of expressive power beyond TC0.
  • Bounded-input implications: A d-layer transformer solves connectivity on graphs with at most 2^((d−20)/2) vertices.This follows from the condition 18 + 2⌈log2 n⌉ ≤ d.

6 Comparing Scaling Depth to Scaling Width or Chain of Thought

For these reasoning problems, increasing depth is more efficient than increasing width or using logarithmically many chain-of-thought steps. Experiments on regular-language recognition closely follow the predicted logarithmic depth scaling and the sharper width dependence.

  • Depth versus width: Fixed-depth transformers require drastic width growth with sequence length to gain expressive power beyond TC0, whereas minimally growing depth suffices.The paper therefore concludes that depth is more efficient than width for these problems.
  • Scope: The width-versus-depth comparison may differ for knowledge-intensive or highly parallelizable tasks.The paper explicitly limits its efficiency conclusion to the reasoning problems under discussion.
  • Depth versus width: For A5 state tracking, depth follows d = 4.8 log2 n − 15.8 with r^2 = 0.93, while width follows n = 7.2 log2 w − 41.7 with r^2 = 0.98.These fits model effective context length and support the predicted logarithmic depth versus exponential width scaling.
  • Depth versus chain of thought: O(log n) chain-of-thought steps remain within L-uniform TC0, according to Theorem 4.This contrasts with Θ(log n) transformer depth, which solves regular-language recognition and graph connectivity beyond TC0 under the stated assumptions.

7 Experiments: Learning to Recognize Regular Languages

The experiments test how depth and width affect trained transformers’ effective context length on the A5 state-tracking task, finding relationships that closely support the theoretical predictions.

  • Experimental setup: The experiments train transformers of varying depths and widths on A5 state tracking, a canonical testbed for hard regular language recognition.A5 sequences contain even permutations, and each token’s label is their cumulative product.
  • Experimental setup: 100 million sequences of lengths up to 1024 are used to evaluate non-universal transformers under controlled depth and width variations.One series fixes width at 512 while varying depth from 6 to 24; another fixes depth at 6 while varying width from 128 to 1024.
  • Evaluation: The effective context length n* is the maximum token index at which a model achieves at least 95% validation accuracy.Results are aggregated across seeds by selecting the best-performing model for each depth-width setting.
  • Results: r2 = 0.93 links depth to log n*, while r2 = 0.98 links log width to n*, supporting the predicted depth and width relationships.The depth relationship has an empirical slope of 4.8 layers per log tokens, compared with theoretical coefficients of 8 and 4 for different transformer constructions.

8 Conclusion

The paper concludes that logarithmically growing depth makes regular language recognition and graph connectivity expressible, while remaining more efficient than scaling width or chain-of-thought steps. It also identifies limits on which problems log-depth transformers can solve and leaves practical learning dynamics for future work.

  • Conclusion: Logarithmic depth growth makes regular language recognition and graph connectivity expressible, whereas fixed-depth transformers cannot express them over unbounded contexts.Fixed depth d suffices only up to bounded context lengths of 2^O(d).
  • Conclusion: Depth scaling is more efficient for these problems than width scaling, which requires superpolynomial growth, or chain-of-thought scaling, which requires superlogarithmic growth.
  • Limitations and future work: Unless NC = P, log-depth or polylog-depth transformers cannot express P-complete problems such as circuit evaluation and Horn-clause satisfiability.
  • Limitations and future work: Future work should study the depth required for other problems in NC and whether repeated layers can serve as inference-time compute.

Limitations

The paper’s constructions establish expressivity results but leave important practical questions unresolved, especially the inductive biases and learning dynamics of looped transformers.

  • Scope boundary: The constructions show that looped transformers can express NC1-hard problems, but they do not analyze the models’ inductive biases or learning dynamics.These factors are identified as important beyond expressivity in practical applications.
  • Scope boundary: The experiments use non-looped transformers, so the depth requirements under shared weights remain an open question.
  • Architectural considerations: Masked pre-norm can prevent values added by one layer from remaining accessible as-is in later layers, complicating value erasure.The paper discusses storage and erasure mechanisms to address this architectural issue.
  • Architectural assumptions: The constructions assume positional encodings can detect the initial token, which can be enabled by a beginning-of-sequence token or supported directly by many position embeddings.

C Regular Language Recognition Proof

The proof reduces regular-language recognition to multiplying transition-monoid elements and implements this computation with a binary tree encoded across transformer layers. A uniform construction uses logarithmic depth in the input length, with explicit model-size bounds.

  • Size bounds: The model dimension is O(|Q|^2) for nondeterministic automata and O(|Q| log|Q|) for deterministic automata.These bounds arise from storing nondeterministic transition relations or deterministic transition indices.
  • Reduction: Regular-language recognition is reduced to multiplying a sequence of transition-monoid elements.The transformer must compute the cumulative product corresponding to the input string and test whether it maps the initial state to an accepting state.
  • Binary-tree construction: Θ(log |w|) depth suffices because each binary-tree level multiplies two items while retaining cumulative products at active tokens.At level ℓ, active token i stores the product over the preceding block of length 2^ℓ.
  • Layer schedule: 8 layers are used per repeated level, followed by 9 final layers that test the resulting monoid element for acceptance.The construction is repeated ⌈log2|w|⌉ times, with one additional layer implementing the final lookup test.

D Graph Connectivity Proof

The graph-connectivity proof computes reachability predicates for exponentially increasing path lengths and alternates these computations through a fixed-width universal transformer. After logarithmically many repetitions, the final token reads the source-to-target reachability value.

  • Theorem: A (17, 2, 1)-universal transformer with fixed model dimension and width solves directed or undirected connectivity after ⌈log2 n⌉ repetitions.Its input includes the n × n adjacency matrix, n^3 padding tokens, and unary source and target markers.
  • Predicate invariant: B_ℓ(i,j) records whether a path of length at most 2^ℓ exists from i to j.The base predicate represents self-loops and direct edges, while later predicates combine two shorter paths through an intermediate vertex.
  • Predicate updates: C_ℓ(i,k,j) combines reachability from i to k and from k to j, enabling the next B_ℓ predicate.The ternary predicates are stored in n^3 padding positions and support the intermediate-vertex computation.
  • Representation: The construction uses n^2 positions for binary predicates and n^3 padding positions for ternary predicates.The input layout places the adjacency matrix first, followed by padding tokens and unary encodings of the queried vertices.
  • Final decision: The final layer retrieves B_⌈log n⌉(s,t), which equals 1 exactly when the graph contains a path from s to t.The source and target coordinates select the corresponding reachability entry from the first n^2 positions.

E Proofs for Width Scaling and Chain of Thought Claims

The width-scaling and chain-of-thought arguments show that polynomial width or logarithmically many reasoning steps remain simulable by uniform TC0 circuits. These results contrast with the logarithmic-depth constructions used for the target problems.

  • Width scaling: A fixed-depth transformer with polynomially growing width and L-computable weights can be simulated in L-uniform TC0.Both self-attention and feedforward sublayers admit constant-depth threshold-circuit simulations with polynomial size.
  • Chain-of-thought scaling: O(log n) chain-of-thought steps are insufficient to recognize languages outside L-uniform TC0.The proof enumerates all polynomially many possible logarithmic-length chains and simulates each in parallel.

F Experimental Details

The experiments address trainability through curriculum learning and controlled depth and width sweeps. They use fixed-width depth experiments, fixed-depth width experiments, and substantial single-GPU compute.

  • Curriculum Training: Curriculum training increases A5 sequence lengths from 2 to 4 and onward to a fixed maximum power of 2.The curriculum was introduced because directly training on long sequences was infeasible and produced noisy gradients from later tokens.
  • Depth Experiments: Depth experiments used fixed width 512 and evaluated depths including 6, 9, 12, 15, 18, 21, and 24.The runs used varying numbers of repetitions and batch sizes, with additional runs added to clarify the depth trend.
  • Width Experiments: Width experiments used fixed depth 6 and tested widths 128, 258, 512, and 1024.Each width condition used five runs with otherwise matched hyperparameters.
  • Compute: The combined experiments required approximately 1000 GPU hours, with each run launched on a single GPU.The estimate covers the reported training experiments.
  • Reproducibility: The data-generation codebase used in the experiments was released under the MIT license.The experiments relied on the codebase of Merrill et al. (2024) for data generation.

NeurIPS Paper Checklist

The checklist records theoretical assumptions and proofs, experimental reproducibility details, statistical-fit reporting, and discussion of limitations. It also notes that the paper’s simplifying assumptions are discussed in Section 2.

  • Limitations: The checklist records that simplifying assumptions are discussed in Section 2.
  • Theory Assumptions and Proofs: The checklist asks whether each theoretical result provides complete assumptions and correct proofs.
  • Theory Assumptions and Proofs: All theoretical results have their proofs included either beside the formal statements or in the appendix.
  • Experimental Result Reproducibility: Sections F and 7 provide the key details needed to reproduce the experiments.
  • Experiment Statistical Significance: The paper reports r2 as a measure of linear fit for experimental significance.
Loading 2503.03961v3…