Why Are Linear RNNs More Parallelizable?

This paper establishes a theoretical foundation for the superior parallelizability of linear RNNs by demonstrating that they correspond to log-depth arithmetic circuits ($\mathsf{NC}^1$-complete), whereas nonlinear RNNs are fundamentally limited by their ability to solve $\mathsf{L}$- and $\mathsf{P}$-complete problems, thereby explaining why linear variants can be efficiently parallelized like transformers while traditional nonlinear RNNs cannot.

The Gist

Imagine you are trying to build a super-smart robot that can read a book, understand the story, and answer questions about it. To do this, the robot needs a "brain" that processes information in two main ways:

1. Sequential Thinking: Reading one word at a time, remembering what came before, and updating its understanding step-by-step. (This is like reading a book aloud to yourself).
2. Parallel Thinking: Looking at the whole page at once, spotting patterns instantly, and processing everything simultaneously. (This is like scanning a page with your eyes to find a specific word immediately).

For a long time, the best robot brains (called Transformers) were great at parallel thinking but struggled with deep, sequential logic. The older robot brains (called Nonlinear RNNs) were great at sequential logic but terrible at parallel thinking—they were too slow because they had to do everything one step at a time.

Recently, a new type of brain called the Linear RNN (LRNN) has emerged. It promises the best of both worlds: it can think sequentially and run in parallel. But why? And are all Linear RNNs created equal?

This paper answers those questions by looking at the "mathematical DNA" of these brains. Here is the breakdown in simple terms.

1. The Core Problem: The Speed vs. Power Trade-off

Think of Nonlinear RNNs (the old-school brains) as a master chef cooking a complex stew.

• How they work: They taste the soup, add a spice, taste it again, add another spice, and repeat. They can make incredibly complex flavors (they are very powerful).
• The problem: They must do this one step at a time. You cannot have 100 chefs cooking the same stew simultaneously because the second chef needs to know what the first chef tasted. This makes them slow on modern computers that love to do many things at once.

Think of Transformers (the current standard) as a team of 100 chefs, each looking at a different part of the recipe at the same time.

• How they work: They are incredibly fast.
• The problem: They struggle with tasks that require strict, step-by-step logic (like counting how many times a specific letter appears in a very long sentence). They are "shallow" thinkers.

Linear RNNs are the new hybrid. They try to be the master chef who can somehow get 100 chefs to help without breaking the recipe.

2. The Big Discovery: Why Linear RNNs are Fast

The authors used a branch of math called Complexity Theory (which classifies how hard problems are to solve) to prove exactly why Linear RNNs are faster.

• The Nonlinear RNN Barrier: The paper proves that nonlinear RNNs are so powerful they can solve problems that are mathematically "impossible" to parallelize efficiently.

  • Analogy: Imagine a puzzle where every piece depends on the piece before it in a way that creates a chain reaction. If you try to solve it with 1,000 people, they all have to wait for the person before them to finish. The paper shows that nonlinear RNNs are like this puzzle. To make them fast, you'd need to break the laws of math (specifically, a famous unsolved problem called P vs. NC).

• The Linear RNN Advantage: Linear RNNs, however, are mathematically "shallow."

  • Analogy: Imagine a line of people passing a bucket of water. In a nonlinear RNN, the person at the end has to wait for the first person to pour, then the second, then the third... one by one. In a Linear RNN, the water flows through a system of pipes that allows the whole line to move almost instantly.
  • The Result: Linear RNNs can be simulated by a computer circuit that is only slightly deeper (slightly more "steps") than a Transformer. This means they can run on parallel hardware almost as fast as Transformers, while still keeping their sequential memory.

3. Not All Linear RNNs Are the Same

The paper also discovered that not all Linear RNNs are equally powerful. They split them into two camps:

• The "Simple" Linear RNNs (PD LRNNs):

  • Analogy: These are like a train. It moves in a straight line, switching tracks occasionally. It's fast and parallelizable, but it can only solve problems that fit on a straight track.
  • Math: They are limited to a complexity class called NC1. They are great, but they hit a ceiling.

• The "Advanced" Linear RNNs (DPLR LRNNs):

  • Analogy: These are like a high-speed maglev train with a switching network. They can still move fast in parallel, but they have a slightly more complex internal structure that allows them to handle much harder puzzles.
  • Math: They reach a higher complexity class called PNC1. They can solve problems that the "Simple" ones cannot, including complex math tasks like multiplying a long chain of matrices.

4. The Experiments: Theory Meets Reality

The authors didn't just do math; they built these robots and tested them on two specific puzzles:

1. The Graph Puzzle: "If I start at point A, can I get to point Z?" (This is a classic "hard" sequential problem).
   • Result: The old Nonlinear RNNs solved it perfectly. The "Simple" Linear RNNs and Transformers failed. The "Advanced" Linear RNNs (like RWKV-7 and DeltaNet) solved it perfectly.
2. The Matrix Puzzle: "Multiply a long list of matrices together."
   • Result: Again, the Advanced Linear RNNs and Nonlinear RNNs succeeded. The Transformers and "Simple" Linear RNNs failed.

The Takeaway

This paper gives us a roadmap for building the next generation of AI.

• If you want speed: Use Linear RNNs. They are nearly as parallelizable as Transformers.
• If you want smarts: You need the "Advanced" Linear RNNs (like DeltaNet or RWKV-7). They are powerful enough to solve hard logical puzzles that Transformers can't, without sacrificing the speed.
• The Warning: If you try to make a Linear RNN too complex (add too many "nonlinear" twists), you break its ability to run in parallel, and it becomes slow again.

In short: Linear RNNs are the "Goldilocks" of AI architecture. They are just complex enough to be smart, but just simple enough to be fast. And within that family, the "Advanced" versions are the ones that can do the heavy lifting.

Technical Summary

Here is a detailed technical summary of the paper "Why Are Linear RNNs More Parallelizable?" by Merrill et al.

1. Problem Statement

The machine learning community is increasingly adopting Linear Recurrent Neural Networks (LRNNs) (e.g., Mamba, RWKV, DeltaNet) as alternatives to Transformers due to their ability to process long sequences in parallel. While prior work has established that LRNNs can be theoretically expressive, a fundamental gap remains in understanding why LRNNs are parallelizable while traditional nonlinear RNNs are not.

Specifically, the paper addresses:

• What theoretical barriers prevent nonlinear RNNs from being parallelized as efficiently as Transformers or LRNNs?
• How do different variants of LRNNs compare in terms of expressive power and parallelizability?
• Can we formally characterize the trade-off between expressivity (ability to solve complex problems) and parallelism (computational efficiency) across different RNN architectures?

2. Methodology

The authors employ circuit complexity theory and automata theory to rigorously analyze RNN architectures.

• Circuit Complexity Classes: The paper maps RNN capabilities to standard complexity classes:
  • $TC^0$: Constant-depth threshold circuits (Transformers, simple LRNNs like Mamba).
  • $NC^1$: Log-depth bounded fan-in boolean circuits (highly parallelizable).
  • $PNC^1$: Log-depth arithmetic circuits with positivity checks (slightly more powerful than $NC^1$, but still highly parallelizable).
  • $L$ (Logspace): Problems solvable with logarithmic memory (sequential).
  • $P$ (Polynomial time): Problems solvable in polynomial time (generally considered sequential).
• Datatypes and Precision: The analysis distinguishes between logarithmic precision (bits grow as $O(\log n)$) and polynomial precision (bits grow as $O(n^c)$). This distinction is crucial for determining whether a model can simulate Turing machines.
• Automata Simulation: The authors associate each RNN class with specific automata models (e.g., Weighted Finite Automata, Counter Machines, Turing Machines) to establish lower and upper bounds on their capabilities.
• Empirical Validation: The theoretical predictions are tested on synthetic algorithmic tasks: Sorted Deterministic Graph Connectivity (an $L$-complete problem) and Iterated Matrix Multiplication (a $PNC^1$-complete problem).

3. Key Contributions

A. Theoretical Separation of Nonlinear RNNs and LRNNs

The paper establishes a fundamental trade-off:

• Nonlinear RNNs (with Polynomial Precision): Can simulate Turing Machines and solve $P$-complete problems. Under the assumption that $NC \neq P$, these models cannot be parallelized to poly-logarithmic depth. They require sequential computation.
• Nonlinear RNNs (with Logarithmic Precision): Can solve $L$-complete problems (e.g., graph connectivity). They likely require $\Omega(\log^2 n)$ depth to parallelize, incurring an $O(\log n)$ overhead compared to Transformers ($O(\log n)$ depth).
• Linear RNNs (LRNNs): Regardless of precision, all LRNNs fall within the class $PNC^1$. This means they can be simulated by arithmetic circuits of depth $O(\log n \log^* n)$.
  • Significance: LRNNs are nearly as parallelizable as Transformers (which are in $TC^0 \subseteq NC^1$), incurring only a negligible depth overhead of $O(\log^* n)$. This explains why they can be efficiently parallelized in practice.

B. Fine-Grained Hierarchy of LRNN Variants

The authors refine the expressivity landscape within the $PNC^1$ class, distinguishing between different parameterizations:

1. Permutation-Diagonal (PD) LRNNs (e.g., PD-SSM):
   • Expressivity: $NC^1$-complete.
   • Can simulate Deterministic Weighted Finite Automata (DWFA).
   • Cannot solve $L$-complete problems (like graph connectivity).
2. Diagonal-Plus-Low-Rank (DPLR) LRNNs (e.g., DeltaNet, RWKV-7):
   • Expressivity: $PNC^1$-complete.
   • Can simulate general Weighted Finite Automata (WFA) over semirings.
   • Can solve Iterated Matrix Multiplication (a $PNC^1$-complete problem).
   • Result: DPLR architectures are strictly more expressive than PD architectures while maintaining high parallelizability.

C. Automata-Theoretic Correspondence

The paper provides a mapping between RNN types and automata:

• Transformers / Simple LRNNs: $TC^0$ (Regular languages with specific constraints).
• PD LRNNs: $NC^1$ (Deterministic WFAs).
• DPLR LRNNs: $PNC^1$ (General WFAs).
• Log-Precision Nonlinear RNNs: $L$ (Counter Machines).
• Poly-Precision Nonlinear RNNs: $P$ (Turing Machines).

4. Key Results

• Parallelizability Limit: Nonlinear RNNs face a fundamental barrier to parallelization. Even with log precision, they require deeper circuits ($\Omega(\log^2 n)$) than Transformers or LRNNs ($O(\log n)$). With poly precision, they likely require super-polylogarithmic depth.
• LRNN Efficiency: LRNNs achieve a "sweet spot." They are powerful enough to solve $PNC^1$-complete problems (like iterated matrix multiplication) but remain efficient enough to be parallelized with only a tiny overhead ($O(\log^* n)$) compared to Transformers.
• Experimental Verification:
  • Graph Connectivity: Only nonlinear RNNs successfully learned the $L$-complete sorted deterministic graph connectivity task. Transformers, Mamba, and DeltaNet failed to generalize to longer sequences, confirming the theoretical limit of LRNNs for $L$-complete tasks.
  • Iterated Matrix Multiplication: DPLR LRNNs (RWKV-7, DeltaNet) and nonlinear RNNs achieved near-perfect accuracy on this $PNC^1$-complete task. Transformers and Mamba (which are limited to $TC^0$) failed, validating the theoretical expressivity gap.

5. Significance and Implications

• Design Guidelines: The paper provides a theoretical foundation for designing Large Language Models (LLMs). It suggests that DPLR architectures (like RWKV-7 and DeltaNet) offer the optimal balance: they are significantly more expressive than Transformers (handling $PNC^1$ tasks) while retaining the parallelizability of linear models.
• Clarifying the "Linear" Advantage: It resolves the mystery of why linear RNNs are parallelizable: their state updates can be unrolled into arithmetic circuits of log-depth, whereas nonlinear updates introduce sequential dependencies that break this structure.
• Benchmarking: The authors propose Iterated Matrix Multiplication and Sorted Graph Connectivity as synthetic benchmarks to evaluate the inductive biases of future RNN architectures, moving beyond simple state-tracking tasks.
• Theoretical Rigor: By connecting deep learning architectures to classical complexity classes ($NC$, $L$, $P$), the paper bridges the gap between practical engineering and theoretical computer science, offering precise predictions about what models can and cannot learn.

In summary, the paper demonstrates that Linear RNNs are more parallelizable because they are mathematically constrained to the $PNC^1$ complexity class, which allows for efficient log-depth simulation. In contrast, nonlinear RNNs can express sequential computations ($L$ and $P$) that inherently resist parallelization. Furthermore, within the linear family, DPLR variants are identified as the most expressive class that still maintains this parallel efficiency.