TL;DR
This paper establishes a formal expressivity gap between input-dependent and state-dependent gating in diagonal State Space Models (SSMs). The authors prove that while input-gated models (like the core of Mamba) fail at context-dependent memory tasks like "induction heads" in the scalar case, adding simple state-feedback gating solves them exactly and leads to superior performance across diverse sequence modeling benchmarks.
What Problem Does This Paper Address?
Modern State Space Models (SSMs) have gained massive popularity as efficient alternatives to Transformers, largely because their linear, diagonal dynamics allow for fast training via parallel associative scans. However, to achieve "selectivity"—the ability to choose what to remember or forget—models like Mamba (S6) use gates that depend only on the current input token.
In contrast, classical Recurrent Neural Networks (RNNs) like LSTMs use gates that depend on both the input and the previous state. This paper asks a fundamental architectural question: Where should a gate look? Does restricting a gate to look only at the input limit what the model can learn? The authors investigate whether adding state feedback to the gating mechanism of diagonal SSMs can unlock new capabilities without sacrificing the structural simplicity that makes SSMs efficient.
Methods
The authors define a family of three matched diagonal SSMs that share the same underlying recurrence but differ in how their gates ($\Delta(k)$) are computed:
- Input-Gated (IG): The gate depends only on the current input $u(k)$. This is a simplified version of the Mamba (S6) layer.
- State-Gated (SG): The gate depends only on the previous recurrent state $x(k-1)$.
- Dual-Gated (DG): The gate depends on both the current input and the previous state.
The paper provides a formal expressivity separation proof. They show that for scalar models, state gating can solve the "induction-head" task for any sequence length, while input gating (including scalar S6) mathematically cannot solve it even for very short sequences (length 5) under standard stability assumptions.
Datasets
The models were evaluated on three distinct benchmarks:
- Induction Head: A synthetic task requiring the model to remember a token that follows a specific "trigger" and retrieve it when that trigger appears again later in the sequence.
- Selective Copying: A task where the model must pick out specific "content" tokens from a stream of noise and reproduce them in order.
- Sequential MNIST: A real-world image classification task where images are processed as sequences of rows and columns in multiple directions.
Key Insights and Ideas
- The "Weighted Average" Trap: The core theoretical insight is that in input-gated scalar models, the final state is essentially a weighted average of potential targets. If the gate doesn't know the internal state, it can't "close" effectively after seeing a target, leading to blurred memories that a simple readout cannot distinguish.
- Task-Specific Strengths: The research reveals a clear trade-off. State gating is essential for context-dependent tasks (like induction heads) because the state tells the gate when it has found what it needs to store. Input gating is better for content-filtering tasks (like selective copying) where the decision to store a token depends mostly on the token itself.
- Efficiency vs. Expressivity: While state-dependent gating breaks the "associative scan" property (making it harder to parallelize directly), the authors note that the resulting dynamics still have a diagonal Jacobian. This structure allows for alternative parallelization methods like fixed-point or quasi-Newton iterations, potentially preserving the speed advantages of SSMs.
Key Results
The empirical results strongly support the theoretical findings:
- Induction Head: Input-gated models (IG and S6) failed completely, achieving near-zero accuracy. In contrast, State-Gated (SG) models achieved high accuracy, and Dual-Gated (DG) models reached ~99% accuracy.
- Selective Copying: As the task difficulty increased (more tokens to recall), IG outperformed SG, confirming that input-based filtering is a distinct and necessary capability.
- Dual Gating Wins: The DG model, which combines both signals, was the most robust, achieving the best or competitive results across all tasks.
Limitations and Future Work
- Parallelization: The current implementation uses naive sequential processing for state-gated variants. Developing and testing scalable, parallel implementations using diagonal Jacobian solvers is a critical next step for practical use in large models.
- Scalar Theory: The formal separation proof is restricted to scalar models. While experiments show the advantage persists in higher dimensions, a general multi-dimensional theory is still needed.
- Scale: The experiments were conducted on synthetic tasks and MNIST. Testing these gating mechanisms on large-scale language modeling (e.g., at the billion-parameter scale) will clarify their impact on real-world performance and training stability.
Summary updated