Aleksandar Terzić: Structured Sparse Transition Matrices to Enable State Tracking in SSMs

Item: Aleksandar Terzić: Structured Sparse Transition Matrices to Enable State Tracking in SSMs
Rating: 4
Author: PostSingularity Institute

by Aleksandar Terzić

Formal & Physical Sciences AI — Models & Research UYQArtificial intelligence (AI)UYQMMachine learning

🎙 Aleksandar Terzić 👥 3K 📅 May 13, 2026 ⏱ 50 min 👁 67 📄 expert opinion 🧭 2026-08-16

Available in: English (current) Français

Keywords

SSMtransition matrixexpressivityfinite state automatastructured sparsity

Summary

The talk by Aleksandar Terzić, from IBM and ETH Zurich, presents a novel approach to state space models (SSMs) using structured sparse transition matrices to enhance their expressivity for state tracking tasks. The speaker begins by motivating SSMs as a dominant sequence modeling paradigm alongside transformers, highlighting their constant-time generation cost and memory efficiency. He then discusses theoretical expressivity results, framing SSMs in terms of finite state automata (FSA) and showing that the structure of the transition matrix determines which automata can be emulated. He reviews existing transition matrix structures: diagonal (as in Mamba) which are efficient but limited to solvable groups, and dense unstructured matrices which are expressive but computationally expensive. He introduces DeltaNet and Delta product as intermediate solutions based on diagonal-plus-low-rank structures. The core contribution is the PDSSM (Product of Diagonal and Sparse column one-hot matrices), which combines a complex diagonal matrix with a column one-hot sparse matrix. This structure preserves efficiency under multiplication, enabling a fast parallel scan. The speaker proves that PDSSM can emulate any finite state machine with a single layer and state size equal to the number of states, and that this is optimal in terms of state size. He also shows that PDSSM maintains a constant overhead compared to diagonal SSMs, unlike dense models. Experimental results on automata from algebraic groups (cyclic, dihedral, and A5) demonstrate that PDSSM achieves length generalization where diagonal models fail, and does so efficiently. The talk concludes with a discussion of stability guarantees and future directions.

249 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk provides valuable insights into the expressivity of state space models, particularly the role of transition matrix structure. The argumentation is solid, building from theoretical foundations (FSA emulation) to practical design choices (PDSSM). The speaker clearly explains the trade-offs between different matrix structures and supports claims with experimental results on automata of varying complexity. The presentation of the PDSSM architecture is detailed, including the generation of column one-hot matrices and the efficient multiplication algorithm. The proof of optimal state size is a strong theoretical contribution. However, the talk is somewhat dense and assumes familiarity with SSMs and formal language theory, which may limit accessibility. The experimental results are limited to specific automata, and the speaker acknowledges that further work is needed to fully understand the trainability of complex diagonal SSMs on non-commutative groups.

Scientific Rigor, Source Quality, Title Accuracy

The talk demonstrates scientific rigor by referencing prior work (e.g., Mamba, DeltaNet, Delta product, work by Merrill) and presenting theoretical results with proofs. The sources cited are relevant and include recent papers. The title accurately reflects the content, focusing on structured sparse transition matrices and state tracking. The talk is well-structured, with clear definitions and motivations. The speaker also acknowledges collaborators and the venue (NeurIPS 2025), adding credibility. No public comments were provided, so no analysis of audience reception is possible.

230 words

Title / Content Match

The title accurately reflects the content, focusing on structured sparse transition matrices in state space models and their role in state tracking.

Quality & Reliability

8/10

The talk is given by a researcher from IBM and ETH Zurich, presenting work published at NeurIPS 2025. It includes theoretical results, experimental evidence, and references to prior work. The presentation is clear and well-structured, with a focus on formal language expressivity. However, it is a single talk without peer review in this context, and some claims are based on unpublished or recent results.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

NeurIPS 2025 paper on PDSSM — The talk is based on a paper presented at NeurIPS 2025.
Mamba: Linear-Time Sequence Modeling with Selective State Spaces — Referenced as a popular diagonal SSM.
DeltaNet: Change-of-State and Delta Rule for Efficient Memory — Referenced as a diagonal-plus-low-rank SSM.
Delta Product: Improving State-Space Model for Sequence Modeling — Referenced as an extension of DeltaNet.
The Illusion of State in State-Space Models — Referenced for the solvable vs non-solvable group distinction.

Concurring Sources

Mamba: Linear-Time Sequence Modeling with Selective State Spaces — Confirms the popularity and efficiency of diagonal SSMs.
The Illusion of State in State-Space Models — Supports the importance of solvable vs non-solvable groups for expressivity.

Dissenting Sources

Wired Linear RNNs: Parallelizing Linear RNNs — The talk mentions that DPLR models are more expressive than structured sparse SSMs in general, which could be seen as a counterpoint to the claim that PDSSM is sufficient for all FSAs.

Contribution & Novelties

The talk introduces PDSSM, a novel state space model with structured sparse transition matrices that combine complex diagonal and column one-hot components. This design achieves expressivity comparable to dense models for finite state machine emulation while maintaining computational efficiency. The theoretical result that any N-state FSA can be emulated with state size N and that this is optimal is a significant contribution. The efficient multiplication algorithm for column one-hot matrices enables fast parallel scan, making the model practical. The talk also provides a clear comparison with existing approaches, highlighting the trade-offs.

Pour aller plus loin :

State Space Models — Background on state space models.
Finite-state machine — Formal definition and properties.
Krohn–Rhodes theory — Decomposition of finite semigroups, relevant to automata complexity.
Parallel prefix sum — Algorithm used in parallel scan for SSMs.

134 words

Radar Profile

The radar profile shows high scores in quantitative information, qualitative information, technical level, and global reliability, indicating a technically dense and reliable presentation. The talk is highly specialized, with a strong theoretical foundation and practical implications.

Reliability 8/10