Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911100714352640 |
|---|---|
| author | Khavari, Behnoush Shakerinava, Mehran Khullar, Jayesh Huang, Jerry Rivest, François Ravanbakhsh, Siamak Chandar, Sarath |
| author_facet | Khavari, Behnoush Shakerinava, Mehran Khullar, Jayesh Huang, Jerry Rivest, François Ravanbakhsh, Siamak Chandar, Sarath |
| contents | Recent work has shown that LRNN models such as S4D, Mamba, and DeltaNet lack state-tracking capability due to either time-invariant transition matrices or restricted eigenvalue ranges. To address this, input-dependent transition matrices, particularly those that are complex or non-triangular, have been proposed to enhance SSM performance on such tasks. While existing theorems demonstrate that both input-independent and non-negative SSMs are incapable of solving simple state-tracking tasks, such as parity, regardless of depth, they do not explore whether combining these two types in a multilayer SSM could help. We investigate this question for efficient SSMs with diagonal transition matrices and show that such combinations still fail to solve parity. This implies that a recurrence layer must both be input-dependent and include negative eigenvalues. Our experiments support this conclusion by analyzing an SSM model that combines S4D and Mamba layers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_07395 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs Khavari, Behnoush Shakerinava, Mehran Khullar, Jayesh Huang, Jerry Rivest, François Ravanbakhsh, Siamak Chandar, Sarath Machine Learning 68Q32 Recent work has shown that LRNN models such as S4D, Mamba, and DeltaNet lack state-tracking capability due to either time-invariant transition matrices or restricted eigenvalue ranges. To address this, input-dependent transition matrices, particularly those that are complex or non-triangular, have been proposed to enhance SSM performance on such tasks. While existing theorems demonstrate that both input-independent and non-negative SSMs are incapable of solving simple state-tracking tasks, such as parity, regardless of depth, they do not explore whether combining these two types in a multilayer SSM could help. We investigate this question for efficient SSMs with diagonal transition matrices and show that such combinations still fail to solve parity. This implies that a recurrence layer must both be input-dependent and include negative eigenvalues. Our experiments support this conclusion by analyzing an SSM model that combines S4D and Mamba layers. |
| title | Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs |
| topic | Machine Learning 68Q32 |
| url | https://arxiv.org/abs/2508.07395 |