Technical Summary: On Subquadratic Architectures: From Applications to Principles

Problem Statement

Transformers currently dominate sequence modeling but suffer from quadratic attention costs, motivating the development of subquadratic alternatives based on recurrent, state-space, and linear-attention mechanisms. While hybrid foundation models increasingly replace attention layers with subquadratic operators (e.g., Samba, Nemotron Nano, Kimi Linear), it remains unclear which specific architectural designs yield the most effective sequence models for complex tasks. Prior comparisons have largely been limited to standard language modeling and commonsense reasoning benchmarks, where performance differences are often marginal. The paper addresses the lack of head-to-head comparisons on data domains with long-range, structured dependencies, specifically code and time series, where architectural inductive biases are hypothesized to diverge significantly.

Methodology

The authors employ a three-pronged methodology: empirical evaluation on complex domains, a unified theoretical formulation, and controlled synthetic experiments.

1. Empirical Evaluation on Complex Domains

The study compares three leading subquadratic architectures: xLSTM (Beck et al., 2024), Mamba-2 (Dao and Gu, 2024), and Gated DeltaNet (Yang et al., 2024b). Evaluations are conducted across three settings:

• Code-Focused Pre-training: 400M-parameter inter-layer hybrid models are pre-trained on code corpora (Nemotron-CC-Code-v1). Performance is measured via HumanEval pass@k and reasoning benchmarks (HellaSwag, PIQA, etc.).
• Code-Focused Distillation: Subquadratic students are distilled from a strong Transformer teacher (Qwen3-4B-Instruct) using a linearization pipeline. The study compares plug-in matrix-state replacements (xLSTM [1:0] vs. Gated DeltaNet) under identical initialization and optimization recipes.
• Time-Series Foundation Model (TSFM) Pre-training: Models are trained on a heterogeneous forecasting benchmark (GIFT-Eval) across five parameter scales (1M to 80M), isolating the sequence mixer backbone while keeping the forecasting pipeline fixed.

2. Unified Theoretical Formulation

To explain empirical differences, the authors derive a unified framework expressing all three architectures in terms of linear attention with gating mechanisms. This formulation standardizes the notation for writing, forgetting, overwriting, and reading from state. The analysis focuses on two primitive capabilities:

• Accumulation: The ability to sum or count over unbounded lengths.
• State Tracking: The ability to perform ordered finite-state updates (e.g., parity, permutation composition).

3. Controlled Synthetic Experiments

The authors test the hypothesis that architectural differences stem from accumulation and state tracking capabilities using length-generalization tasks. Models are trained at sequence length 128 and evaluated at 128, 512, and 2048.

• Accumulation Tasks: Majority counting, AnBn, AnBnCn.
• State-Tracking Tasks: Parity, Modular Arithmetic (Z5), and symmetric group (S3) word problems.

Key Results

Empirical Performance

• Code Pre-training: xLSTM [7:1] consistently outperforms Mamba-2 and Gated DeltaNet across all training configurations (20B and 100B tokens) and sampling budgets (pass@k). The margin is most pronounced on code generation (HumanEval), with xLSTM improving over the next-best backbone by up to 1.81 points.
• Code Distillation: In the distillation setting, xLSTM [1:0] (mLSTM) achieves the highest average pass@1 score across four code benchmarks, outperforming both default Gated DeltaNet and its negative-eigenvalue variant.
• Time-Series Pre-training: xLSTM [3:1] demonstrates superior performance in zero-shot forecasting (MASE and CRPS) from 1M to 40M parameters. At 80M parameters, the gap narrows, with Mamba-2 slightly leading on CRPS, but xLSTM remains competitive.

Theoretical and Synthetic Findings

• Unified Analysis: The authors identify that Mamba-2 ties its input and forget gates (similar to a GRU), limiting its expressiveness. Gated DeltaNet explicitly overwrites old values, which aids retrieval but hinders accumulation. xLSTM separates matrix-state linear attention from recurrent updates, allowing for flexible memory correction via an exponential input gate.
• Synthetic Tasks:
  • Mamba-2: Fails to generalize on both accumulation and state-tracking tasks beyond training length.
  • Gated DeltaNet: The default variant fails state tracking; the negative-eigenvalue variant [−1, 1] solves state tracking in-distribution but fails to generalize to longer sequences (e.g., Parity accuracy drops from 1.00 to 0.47 at length 2048).
  • xLSTM: xLSTM [1:0] excels at accumulation (counting) but fails state tracking. The hybrid xLSTM [1:1] successfully combines both, achieving perfect state tracking and strong counting extrapolation.

Significance and Claims

The paper claims that xLSTM's advantage on complex sequence tasks stems from its ability to combine robust state tracking with counting-like accumulation.

• Architectural Mechanism: The authors argue that xLSTM's gating scheme enables more flexible and stable memory correction compared to the tied gates of Mamba-2 or the explicit overwriting of Gated DeltaNet.
• Design Principle: The results suggest that for complex domains like code and time series, the optimal architecture is a hybrid that retains efficient accumulation blocks (linear attention) as the dominant component while incorporating a smaller number of recurrent layers to support state tracking. This explains the success of configurations like xLSTM [7:1] and xLSTM [3:1].
• Scope: The findings are presented as the first head-to-head comparison of these specific operators across code and time-series domains, moving beyond standard language modeling benchmarks to reveal clearer architectural separations.

The authors remain modest regarding limitations, noting that their code experiments are at a 400M parameter scale and that the time-series experiments are the only ones to include a full scaling sweep. They suggest that extending these comparisons to larger scales and additional data domains is a necessary next step.