Research map / Time series / Causal and generative time series
Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PD-SSM, a time-varying state-space model whose transition matrices are products of a column one-hot matrix and a complex diagonal matrix, enabling single-layer FSA emulation at linear scan cost.
Problem
Structured SSM transition matrices (diagonal, DPLR, block-diagonal) limit expressivity for finite-state automaton (FSA) state tracking, while dense transition matrices are prohibitively expensive for parallel scans.
Approach
Parametrize transition matrices as A(u_t)=P(u_t)D(u_t), with P a column one-hot (hardmax-selected) matrix from a dictionary of trainable matrices and D a bounded complex diagonal matrix; the PD set is closed under multiplication and products cost Theta(N), so one layer of size N with an NxN readout can emulate any N-state FSA.
Key results
- PD-SSM achieves 98.8% average validation accuracy on the automaton state tracking benchmark, the best among compared models (second-best ~85.1%).
- On A5 and S5 length-generalization tasks, a single-layer PD-SSM reaches 100% on all tested settings except S5 with 32 generators (1.07%), where the complex diagonal model fails on (A5,2).
- On the 6-dataset UEA subset PD-SSM averages 67.0% test accuracy, within standard error of LinOSS-IM (67.8%); on LRA, it averages 74.4%, the best among time-variant SSMs (Mamba, S7).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PD-SSM instead of the strongest reported parallel baseline | FSA state tracking models · FSA state tracking average | validation accuracy: 85.1 ± 8.2 -> 98.8 ± 0.9 | Helped |
| Use PD-SSM instead of Gated DeltaProduct [-1,1] | FSA state tracking models · A5, 2 generators | validation accuracy: 97.9 -> 100.0 | Helped |
| Use PD-SSM instead of Gated DeltaProduct [-1,1] | FSA state tracking models · A5, 6 generators | validation accuracy: 92.5 -> 100.0 | Helped |
| Use PD-SSM instead of Gated DeltaProduct [-1,1] | FSA state tracking models · A5, 8 generators | validation accuracy: 91.8 -> 100.0 | Helped |
| Use PD-SSM instead of depth-2 Gated DeltaProduct [-1,1] | FSA state tracking models · A5, 12 generators | validation accuracy: 68.4 -> 100.0 | Helped |
| Use PD-SSM instead of Gated DeltaProduct [-1,1] | FSA state tracking models · S5, 4 generators | validation accuracy: 88.7 -> 100.0 | Helped |
| Use PD-SSM instead of depth-2 Gated DeltaProduct [-1,1] | FSA state tracking models · S5, 8 generators | validation accuracy: 62.2 -> 100.0 | Helped |
| Use PD-SSM instead of Gated DeltaProduct [-1,1] | FSA state tracking models · S5, 32 generators | validation accuracy: 1.23 -> 1.07 | Hurt |
| Use PD-SSM instead of LinOSS-IM | UEA multivariate time-series classifiers · UEA multivariate time-series classification average | test accuracy: 67.8 ± 2.00 -> 67.0 ± 2.02 | No clear effect |
| Use PD-SSM instead of S7 | Time-variant Long-Range Arena models · Long-Range Arena average | accuracy: 73.9 -> 74.4 | Helped |
| Replace dense SD-SSM transitions with PD transitions | Single-layer SSM runtime · D=5632, sequence length 64 | speedup: 71 × | Helped |
| Replace PD transitions with complex diagonal transitions (ablation) | Single-layer SSM runtime · D=5632, sequence length 64 | relative runtime: 7× faster | Hurt |
Surprising findings
- Complex diagonal SSMs, which theoretically can represent parity, did not learn it in the natural-language experiments, whereas PD-SSM converged within 10,000 steps.
- Time-invariant SSMs performed significantly better on average than the time-variant ones on LRA.
Limitations
- Overhead from generating the P(u_t) matrices makes PD-SSM slower than diagonal SSMs.
- S5 with 32 generating permutations is not emulated (1.07% accuracy).
- Not yet evaluated in large-scale pretraining.
Experimental setup
Datasets: Automaton state tracking tasks (Cycle Navigation, Even Pairs, Modular Arithmetic, Parity) A5 and S5 permutation automata UEA Multivariate Time-Series Classification Archive subset Long-Range Arena (ListOps, Text, Image, Retrieval, Pathfinder) Natural-language FSA state tracking (English sentences)
Benchmarks: Automaton state tracking (Cycle Navigation, Even Pairs, Modular Arithmetic, Parity) A5/S5 length generalization UEA multivariate time-series subset Long-Range Arena subset Natural-language state tracking
Metrics: validation accuracy test accuracy runtime
Baselines: LSTM Transformer Mamba DeltaNet Gated DeltaNet Gated DeltaProduct RWKV-7 D-SLiCE LinOSS-IM Log-NCDE S7 LRU
Builds on: Mamba S5 Structured dense SSM (SD-SSM) Gated DeltaProduct Neural controlled differential equations Parallel scan
Closest papers by meaning
- Autocorrelation Matters: Understanding the Role of Initialization Schemes for State Space Models (ICLR 2025 · similarity 0.86)
- Provable Benefits of Complex Parameterizations for Structured State Space Models (NeurIPS 2024 · similarity 0.86)
- The Illusion of State in State-Space Models (ICML 2024 · similarity 0.86)
- Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models (NeurIPS 2025 · similarity 0.86)
- From Generalization Analysis to Optimization Designs for State Space Models (ICML 2024 · similarity 0.86)
- Parameter-Efficient Fine-Tuning of State Space Models (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.