The Illusion of State in State-Space Models

Neural nets and the brain-model problem

Minsky, M · 1954

Earlier work this paper cites.

Algebraic theory of machines. i. prime decomposition theorem for finite semigroups and machines

Krohn, K. and Rhodes, J · 1965

Earlier work this paper cites.

File change semantics and the familiarity theory of definiteness

Heim, I · 1983

Earlier work this paper cites.

Bounded-width polynomial-size branching programs recognize exactly those languages in nc1

Barrington, D. A · 1989

Earlier work this paper cites.

The complexity of iterated multiplication

Immerman, N. and Landau, S · 1989

Earlier work this paper cites.

Prefix sums and their applications

Blelloch, G. E · 1990

Earlier work this paper cites.

On threshold circuits and polynomial computation

Reif, J. H. and Tate, S. R · 1992

Earlier work this paper cites.

Threshold circuits for iterated matrix product and powering

Mereghetti, C. and Palano, B · 2000

Earlier work this paper cites.

Division is in uniform T ​ C 0 TC^{0}

Hesse, W · 2001

Earlier work this paper cites.

Introduction to automata theory, languages, and computation

Hopcroft, J. E., Motwani, R., and Ullman, J. D · 2001

Earlier work this paper cites.

Uniform constant-depth threshold circuits for division and iterated multiplication

Hesse, W., Allender, E., and Barrington, D. A. M · 2002

Cited alongside, same era.

Weighted Automata Algorithms , pp. 213–254

Mohri, M · 2009

Cited alongside, same era.

Sequential neural networks as automata

Merrill, W · 2019

Cited alongside, same era.

Combining recurrent, convolutional, and continuous-time models with linear state space layers

Gu, A., Johnson, I., Goel, K., Saab, K. K., Dao, T., Rudra, A., and Re, C · 2021

Cited alongside, same era.

Chess as a testbed for language model state tracking

Toshniwal, S., Wiseman, S., Livescu, K., and Gimpel, K · 2021

Cited alongside, same era.

Formal language recognition by hard attention transformers: Perspectives from circuit complexity

Hao, S., Angluin, D., and Frank, R · 2022

Hungry hungry hippos: Towards language modeling with state space models

Fu, D. Y., Dao, T., Saab, K. K., Thomas, A. W., Rudra, A., and Re, C · 2023

Later among the works it cites.

Mamba: Linear-time sequence modeling with selective state spaces, 2023

Original

Gu, A. and Dao, T · 2023

Later among the works it cites.

Liquid structural state-space models

Hasani, R., Lechner, M., Wang, T.-H., Chahine, M., Amini, A., and Rus, D · 2023

Later among the works it cites.

Entity tracking in language models

Kim, N. and Schuster, S · 2023

Later among the works it cites.

Transformers learn shortcuts to automata

Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C · 2023

Later among the works it cites.

Structured state spaces: Combining continuous-time, recurrent, and convolutional models, January 2022b