REVIEW 7 cited by
Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Linear Recurrent Neural Networks (LRNNs) such as Mamba, RWKV, GLA, mLSTM, and DeltaNet have emerged as efficient alternatives to Transformers for long sequences. However, both Transformers and LRNNs struggle to perform state-tracking, which may impair performance in tasks such as code evaluation. In one forward pass, current architectures are unable to solve even parity, the simplest state-tracking task, which non-linear RNNs can handle effectively. Recently, Sarrof et al. (2024) demonstrated that the failure of LRNNs like Mamba to solve parity stems from restricting the value range of their diagonal state-transition matrices to $[0, 1]$ and that incorporating negative values can resolve this issue. We extend this result to non-diagonal LRNNs such as DeltaNet. We prove that finite precision LRNNs with state-transition matrices having only positive eigenvalues cannot solve parity, while non-triangular matrices are needed to count modulo $3$. Notably, we also prove that LRNNs can learn any regular language when their state-transition matrices are products of identity minus vector outer product matrices, each with eigenvalues in the range $[-1, 1]$. Our experiments confirm that extending the eigenvalue range of Mamba and DeltaNet to include negative values not only enables them to solve parity but consistently improves their performance on state-tracking tasks. We also show that state-tracking enabled LRNNs can be pretrained stably and efficiently at scale (1.3B parameters), achieving competitive performance on language modeling and showing promise on code and math tasks.
Forward citations
Cited by 7 Pith papers
-
SHiPPO: Recurrent Memory with Transported Polynomial Projections
SHiPPO transports HiPPO coefficient memories via right actions into Sylvester dynamics, and diagnostics show this recovers order-sensitive memory changes that high-rank writes cannot.
-
The Capability Convergence Hypothesis: Capability from Access Structure, Not Scale
Long-context capability converges to hybrid architectures pairing O(1) state with a scalable index; pure scaling of SSMs or Transformers alone hits information, horizon, or circuit walls.
-
Eigenvalues as a Metric for Memory Dynamics in Sequence Models
Eigenvalue spectra of attention and SSM dynamics show consistent signatures of memory retention and selective forgetting that align with task requirements.
-
Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encoding
TAPE makes positional embeddings content-aware and equivariant, improving Transformer performance on arithmetic and long-context tasks and extending representational power to NC1-complete algorithms.
-
Understanding Transformer from the Perspective of Associative Memory
Frames the Transformer as associative memory, derives retrieval SNR for linear, softmax, ReLU, and SoLU kernels, and proposes DeltaFormer, a softmax-plus-delta-rule variant claimed to exceed TC0 expressivity.
-
State Propagation Also Satisfies: A Complex-Valued State-Space Model for Deterministic State Tracking
A small complex-valued recurrent model achieves 100% accuracy on three length-16 state-tracking puzzles, but the claim that state propagation alone is sufficient is not tested against any baseline.
-
ARWKV: Pretrain is not what we need, an RNN-Attention-Based Language Model Born from Transformer
A three-stage distillation pipeline converts Qwen 2.5 into a pure RWKV-7 RNN, but the resulting 7B models lose substantial benchmark accuracy.
Discussion (0). Continue with ORCID to comment.