Traditional recurrent neural networks (RNNs) compress the entire history of a sequence into a single hidden vector $h_t \in \mathbb{R}^d$. While this allows for constant-memory $O(1)$ inference per token, it creates a fundamental information bottleneck. A vector of size $d$ can only store $O(d)$ independent variables. As a sequence grows, older information is inevitably overwritten or diluted, limiting the network's ability to perform complex associative recall or track overlapping long-term dependencies.
To break this bottleneck, a powerful paradigm has emerged: replacing the vector-valued hidden state with a two-dimensional matrix $M_t \in \mathbb{R}^{d \times d}$. By transitioning from a vector to a matrix, the memory capacity scales quadratically to $O(d^2)$ relative to the hidden dimension.
The Core Intuition: Outer-Product Associative Memory
How does a matrix state store and retrieve information without the quadratic computational cost of full self-attention? The core mechanism relies on treating the matrix as an associative memory via covariance-like update rules.
At each time step, the model generates key ($k_t \in \mathbb{R}^d$) and value ($v_t \in \mathbb{R}^d$) vectors from the current input. Instead of adding a vector to a vector, the model computes the outer product of the value and key vectors to update the memory matrix:
$$M_t = M_{t-1} + v_t k_t^\top$$
This outer product creates a $d \times d$ matrix that binds the key and value together. To retrieve information, the model projects a query vector $q_t \in \mathbb{R}^d$ and performs a tensor contraction (matrix-vector multiplication):
$$y_t = M_t q_t$$
Because matrix multiplication is associative, we can see exactly why this acts as an attention-like retrieval mechanism:
$$y_t = ( \sum_{\tau=1}^t v_\tau k_\tau^\top ) q_t = \sum_{\tau=1}^t v_\tau (k_\tau^\top q_t)$$
The term $(k_\tau^\top q_t)$ is a scalar representing the similarity between the current query and a past key. The matrix state effectively stores all past key-value pairs simultaneously, allowing the model to retrieve a weighted sum of past values based on query similarity—all without storing the historical tokens explicitly.
As explored by Imanol Schlag et al. in A Modern Self-Referential Weight Matrix That Learns to Modify Itself, utilizing a weight matrix as the primary storage state increases the number of controllable temporal variables, providing a significantly higher bandwidth for internal state changes and allowing the model to effectively reprogram its behavior during inference.
Brian Mak et al. leverage this mechanism in Residual Matrix Transformers: Scaling the Size of the Residual Stream, replacing the standard vector-based residual stream with an outer-product memory matrix. This architectural shift allows researchers to scale a model's memory capacity independently of its compute and parameter count.
Unlocking Parallel Training
A historical flaw of traditional RNNs was their sequential training bottleneck: the hidden state $h_t$ cannot be computed until $h_{t-1}$ is complete. Matrix-valued recurrent memory elegantly solves this by bridging the gap between recurrent efficiency and the parallel training of Transformers.
As Angelos Katharopoulos et al. demonstrated in Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, if the standard softmax activation in attention is replaced with a kernel-based feature map, the attention operation can be mathematically reformulated as a recurrent matrix update. Because matrix multiplication is associative, the entire sequence of updates can be computed in parallel during training using a prefix sum (cumulative scan), while retaining an efficient $O(1)$ recurrent formulation for fast autoregressive inference.
Parallel Training (Transformer View):
Inputs ---> [ Q, K, V Matrices ] ---> Parallel Matrix Multiplication ---> Outputs
Sequential Inference (RNN View):
Input_t ---> Q_t, K_t, V_t ---> M_t = M_{t-1} + V_t K_t^T ---> Output_t = M_t Q_t
To make this formulation competitive with standard Transformers, modern architectures integrate exponential gating to control what gets written or forgotten. In xLSTM: Extended Long Short-Term Memory, Andreas Auer et al. introduce matrix-based memory cells combined with exponential gating. This allows the model to stabilize recurrent updates and decouple state updates from sequential dependencies, enabling full parallelization during training while maintaining the constant memory overhead characteristic of recurrent architectures during inference.
Decoupling Capacity from Hardware Constraints
By shifting from 1D vectors to 2D matrices, models can scale up their internal state capacity without a corresponding explosion in parameter count or hardware bandwidth.
In a standard RNN, increasing the hidden state dimension $d$ causes the parameter matrices to grow by $O(d^2)$. In contrast, a matrix-valued hidden state expands the memory capacity to $O(d^2)$ while keeping the parameter matrices small. Ganesh Venkatesh et al. exploit this property in Memory-efficient Speech Recognition on Smart Devices, representing the recurrent cell state as a two-dimensional matrix to maintain high capacity while reducing off-chip memory accesses and overall model size for low-power devices.
Diverse Architectural Expressions
The principle of matrix-valued recurrent memory manifests across several modern sequence modeling frameworks:
- Gated Linear Attention (GLA): Songlin Yang et al. in Gated Linear Attention Transformers with Hardware-Efficient Training utilize matrix-valued hidden states alongside hardware-aware algorithms to enhance complex information retrieval and associative recall over long sequences.
- RWKV: As detailed by Zhiyuan Li et al. in A Survey of RWKV, modern iterations of the RWKV architecture scale expressive capacity by adopting multi-headed matrix-valued hidden states rather than simple vector states to manipulate complex relational information.
- Block-Recurrent Transformers: Instead of a single vector or a strict $d \times d$ matrix, DeLesley Hutchins et al. in Block-Recurrent Transformers utilize a multi-vector block state representation, expanding memory capacity to retain granular details across sequences exceeding 60,000 tokens.
- Non-Text Domains: The high capacity of matrix memory has proven highly effective outside natural language. Benedikt Alkin in Vision-LSTM: xLSTM as Generic Vision Backbone demonstrates that matrix-valued memory cells allow recurrent vision backbones to capture global context and rival Vision Transformers. Similarly, Niklas Schmidinger et al. in Bio-xLSTM: Generative modeling, representation and in-context learning of biological and chemical sequences show that matrix-based memory structures excel at tracking multiple overlapping biological motifs simultaneously where vector-based state space models struggle.
Key Foundational Work
The Lifted Matrix-Space Model for Semantic Composition (2017) — contributed 1 concept elements to this direction.
Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention (2020) — contributed 1 concept elements to this direction.