Improved state mixing in higher-order and block diagonal linear recurrent networks
Organizations: NISYS, Frankfurt am Main · Ernst Strüngmann Institut, Frankfurt am Main · ELLIS Institute Tübingen · MPI for Intelligent Systems ·
Abstract
Linear recurrent networks (LRNNs) and linear state space models (SSMs) promise computational and memory efficiency on sequence modeling tasks, yet their diagonal state transitions limit expressivity. Dense and/or nonlinear architectures (e.g., LSTMs) on the other hand are provably more expressive, but computationally costly. Here, we explore how expressivity in LRNNs can be increased via richer state mixing across time and channels while maintaining competitive efficiency. Specifically, we introduce two structured LRNN architectures: (i) Higher-order Linear Recurrent Units (H-LRU), which generalize recurrences to arbitrary order, mixing multiple past states, and (ii) Block-Diagonal LRUs (BD-LRU), which enable dense intra-block channel mixing. To ensure stable training, we introduce a selective gate normalization scheme that allows for scalable window and block sizes. To maintain efficiency, we implement block-diagonal parallel scans in PyTorch and Triton that keep the throughput competitive with diagonal LRNNs for moderate orders (H-LRU) and block sizes (BD-LRU). Consistent with prior theoretical studies on the limitations of diagonal models, we empirically demonstrate that our architectures benefit from the increased expressivity of structured state mixing, on synthetic sequence modeling and on language modeling tasks that require tracking structure. Our results show that the structure of state mixing is a critical driver of performance in LRNNs, offering a practical pathway to closing the efficiency-expressivity gap in linear sequence models.
Figures & tables
| Models | (10k samples) | (250) | (50k) | (3k) | (100k) | Overall |
|---|---|---|---|---|---|---|
| LSTM [ 29 ] | 1.000 | 0.316 | 1.000 | 0.368 | 1.000 | 0.737 |
| Mamba2 [ 12 ] | 0.657 | 0.281 | 0.429 | 0.119 | 0.261 | 0.349 |
| PD-SSM [ 55 ] | 1.000 | 0.273 | 0.569 | 0.154 | 0.347 | 0.469 |
| DeltaNet[-1,1] [ 62 , 21 ] | 1.000 | 0.264 | 0.507 | 0.138 | 0.140 | 0.410 |
| DeltaProduct 4 [-1,1] [ 52 ] | 1.000 | 0.279 | 1.000 | 0.136 | 0.140 | 0.511 |
| H-LRU m5 | 0.622 | 0.318 | 0.448 | 0.194 | 0.377 | 0.392 |
| Models | In-Context Recall | Selective Copy | Compression | Overall |
|---|---|---|---|---|
| LSTM | 1.000 | 1.000 | 0.749 | 0.916 |
| Mamba2 | 1.000 | 0.812 | 0.721 | 0.844 |
| DeltaNet[-1,1] | 1.000 | 0.902 | 0.765 | 0.889 |
| DeltaProduct 4 [-1,1] | 1.000 | 1.000 | 0.735 | 0.911 |
| BD-LRU m1 | 0.779 | 0.835 | 0.725 | 0.780 |
| BD-LRU m2 | 1.000 | 0.964 | 0.760 | 0.908 |
| PPL | |||||||||
| Model | FineWeb | WikiText | NIAH | Anagram | Markov | Linear | ARC-E | bAbI | PIQA |
| BD-LRU/H-LRU m1 | 20.7 | 49.2 | 0.280 | 0.611 | 0.230 | 0.604 | 0.484 | 0.357 | 0.659 |
| H-LRU m2 | 19.3 | 41.6 | 0.505 | 0.670 | 0.230 | 0.743 | 0.484 | 0.376 | 0.660 |
| H-LRU m4 | 19.6 | 43.8 | 0.370 | 0.698 | 0.440 | 0.743 | 0.491 | 0.338 | 0.664 |
| H-LRU m8 | 20.5 | 48.5 | 0.290 | 0.644 | 0.257 | 0.799 | 0.486 | 0.338 | 0.658 |
| BD-LRU m2 | 19.8 | 46.0 | 0.285 | 0.639 | 0.253 | 0.688 | 0.470 | 0.331 | 0.650 |
| Gate parametrization | |||
|---|---|---|---|
| Softmax ( ) | 46.7 | 43.3 | 42.6 |
| Sigmoid ( ) | 46.8 | 44.9 | 44.3 |
| Linear ( ) | 56.1 | 47.1 | 43.6 |
| ReLU ( ) | 106.5 | 92.5 | 57.0 |
| Implementation | |||||
|---|---|---|---|---|---|
| Sequential (PyTorch) | 78.4 / 178 | 300 / 461 | 2383 / 1597 | – | – |
| Block hopscan (PyTorch) | 16.9 / 217 | 20.8 / 618 | 49.7 / 2219 | 195 / 8616 | 776 / 34199 |
| Block hopscan + torch.compile | 3.2 / 132 | 3.4 / 227 | 9.9 / 406 | 37.4 / 1366 | – |
| Triton scan | 3.2 / 208 | 3.3 / 590 | 7.1 / 2109 | 26.7 / 8181 | 106 / 32456 |
| Triton scan + torch.compile | 3.7 / 132 | 3.8 / 228 | 4.5 / 546 | 16.5 / 1932 | 64.8 / 7478 |
| Model (ms / MB) | rank 1 | rank 2 | rank 4 | rank 8 | |
|---|---|---|---|---|---|
| 4096 | BD-LRU (block size ) | 4.0 / 620 | 4.5 / 516 | 4.5 / 546 | 6.4 / 1447 |
| H-LRU (window size ) | 4.1 / 620 | 5.7 / 790 | 7.7 / 1333 | 17.6 / 6678 | |
| DeltaNet / DeltaProduct ( ) | 7.7 / 1203 | 8.4 / 1646 | 10.2 / 1983 | 11.8 / 2204 | |
| LSTM | 89.2 / 299 | – | – | – | |
| 16384 | BD-LRU (block size ) | 14.4 / 2228 | 16.3 / 1821 | 16.5 / 1932 | 24.2 / 5539 |
| H-LRU (window size ) | 14.3 / 2228 | 20.7 / 2910 | 29.1 / 5083 | 69.1 / 26462 |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Architecture | FLOPs per recurrent step | Implementation complexity |
|---|---|---|
| LSTM | ||
| H-LRU | ||
| BD-LRU | ||
| Mamba2 | ||
| DeltaNet | ||
| DeltaProduct 4 |
| Models | (10k samples) | (50k) | (100k) |
|---|---|---|---|
| LSTM | 1.000 (1.000 0.000) | 1.000 (1.000 0.000) | 1.000 (1.000 0.000) |
| Mamba2 c4 s2 | 0.640 (0.622 0.020) | 0.423 (0.402 0.033) | 0.268 (0.242 0.028) |
| Mamba2 c4 s4 | 0.626 (0.609 0.022) | 0.432 (0.396 0.035) | 0.278 (0.237 0.042) |
| Mamba2 c4 s8 | 0.657 (0.597 0.055) | 0.429 (0.400 0.025) | 0.261 (0.239 0.033) |
| DeltaNet[-1,1] nh8 | 1.000 (0.752 0.223) | 0.507 (0.456 0.061) | 0.140 (0.136 0.004) |
| DeltaProduct 4 [-1,1] nh8 | 1.000 (1.000 0.000) | 1.000 (0.868 0.132) | 0.140 (0.137 0.004) |
| Models | S3 (250) | S4 (3k) |
|---|---|---|
| LSTM | 0.316 (0.298 0.016) | 0.368 (0.297 0.093) |
| Mamba2 c4 s2 | 0.284 (0.277 0.006) | 0.115 (0.113 0.003) |
| Mamba2 c4 s4 | 0.284 (0.278 0.006) | 0.115 (0.105 0.009) |
| Mamba2 c4 s8 | 0.281 (0.279 0.002) | 0.119 (0.115 0.004) |
| DeltaNet[-1,1] nh8 | 0.264 (0.259 0.005) | 0.138 (0.117 0.018) |
| DeltaProduct 4 [-1,1] nh8 | 0.279 (0.273 0.008) | 0.136 (0.136 0.000) |
| Models | In-Context Recall Tasks | Selective Copy Tasks | Compression Tasks |
|---|---|---|---|
| LSTM | 1.000 (1.000 0.000) | 1.000 (0.998 0.002) | 0.749 (0.697 0.092) |
| Mamba2 c2 s2 | 1.000 (0.970 0.030) | 0.791 (0.743 0.051) | 0.623 (0.508 0.142) |
| Mamba2 c2 s4 | 1.000 (0.988 0.012) | 0.812 (0.786 0.032) | 0.721 (0.582 0.131) |
| Mamba2 c2 s8 | 1.000 (1.000 0.000) | 0.830 (0.799 0.032) | 0.606 (0.535 0.069) |
| Mamba2 c4 s2 | 1.000 (1.000 0.000) | 0.798 (0.753 0.059) | 0.623 (0.528 0.108) |
| Mamba2 c4 s4 | 1.000 (1.000 0.000) | 0.800 (0.756 0.060) | 0.637 (0.548 0.098) |
| Models | Memorization Tasks | Fuzzy Recall Tasks | Noisy Recall Tasks |
|---|---|---|---|
| LSTM | 0.787 (0.778 0.006) | 0.128 (0.120 0.005) | 0.999 (0.999 0.000) |
| PD-SSM | 0.787 (0.777 0.006) | 0.117 (0.109 0.003) | 0.800 (0.750 0.027) |
| DeltaNet[-1,1] | 0.357 (0.339 0.013) | 0.525 (0.461 0.035) | 1.000 (1.000 0.000) |
| DeltaProduct 4 [-1,1] | 0.332 (0.316 0.003) | 0.373 (0.309 0.045) | 1.000 (1.000 0.000) |
| BD-LRU m1 | 0.785 (0.777 0.005) | 0.142 (0.136 0.002) | 0.687 (0.681 0.006) |
| BD-LRU m2 | 0.785 (0.776 0.005) | 0.293 (0.267 0.013) | 1.000 (1.000 0.000) |
| Models | cycle nav | mod arith no brack | mod arith w brack | parity |
|---|---|---|---|---|
| LSTM | 1.000 | 0.976 | 0.663 | 1.000 |
| BD-LRU m1 | 0.434 | 0.370 | 0.370 | 0.512 |
| BD-LRU m2 | 0.425 | 0.493 | 0.417 | 1.000 |
| BD-LRU m3 | 0.597 | 0.546 | 0.434 | 1.000 |
| BD-LRU m4 | 0.608 | 0.459 | 0.435 | 1.000 |
| BD-LRU m5 | 1.000 | 0.525 | 0.422 | 1.000 |
Linear RNNs
Linear recurrent neural networks (RNNs) model sequences with linear state updates, aiming for efficient, parallelizable memory over long contexts.
See all 29 papers