Efficiently Modeling Long Sequences with Structured State Spaces

The state space model x' = Ax + Bu, y = Cx + Du can represent long-range dependencies, but computing it naively is prohibitively expensive in both time and memory - so the theoretical strength of the SSM view was unusable.

A new parameterisation of the SSM. The HiPPO matrix A is made NORMAL (structured as the product of a diagonal and an orthogonal matrix) and combined with a low-rank correction, which makes it STABLY DIAGONALISABLE. Diagonalising collapses the SSM computation into a convolution with a CAYLEY KERNEL, which in turn can be evaluated with FFTs - the entire efficiency win comes from that reduction.

Paper's own claims (abstract): 91% accuracy on sequential CIFAR-10 with no data augmentation or auxiliary losses, on par with a larger 2-D ResNet; generation 60x faster (baseline class: the Transformers it closes the gap to); SoTA on every Long Range Arena task including Path-X at length 16K which all prior work fails on, while being as efficient as all competitors.

arXiv ID 2111.00396 verified via abs-page meta tags on 2026-10-03; title matches. Venue verified strongly: arXiv comment reads 'ICLR 2022 (Outstanding Paper HM)'; OpenReview (api v1) returns venue='ICLR 2022 Oral' / venueid='ICLR.cc/2022/Conference'; and the title appears in the official ICLR 2022 virtual papers listing (iclr.cc/virtual/2022/papers.html). The source note's 'Semantic Scholar gives year 2021' is the arXiv v1 date (2021-10-31), not the venue year - year=2022 is correct here. adoption=research-only, and the reasoning is the decision-relevant part: state-spaces/s4 was last pushed 2024-07-17, roughly two years stale, and neither vLLM nor SGLang nor transformers has an S4 model - the maintained successor is the selective SSM in mamba, recorded separately. So S4 is not abandoned (its repo lives, and the outstanding-paper HM is a real contribution) but it has no path into a serving engine: the Cauchy-kernel FFT formulation has no decode-time incremental form, which is exactly what a serving engine needs. Recorded research-only rather than abandoned with that stated basis. VENUE_TRACK BACKFILL 2026-10-04 (paper-fields pass, agent w3p): venue_track 'main'. ICLR 2022 has no Findings or workshop tier, so 'main' is the only honest value. Re-confirmed independently of the sibling record: static ICLR 2022 listing + the page's JSON-LD creditText 'ICLR 2022' + the arXiv comment 'ICLR 2022 (Outstanding Paper HM)'. DUPLICATE-SLUG-CONSOLIDATION-2026-10-05 (agent w6-papers). data/papers/s4.json and data/papers/s4-structured-state-spaces.json were BOTH live records for arXiv 2111.00396 (Efficiently Modeling Long Sequences with Structured State Spaces), so one paper appeared twice under two slugs and - where the records disagreed - under two different venues. s4-structured-state-spaces.json has been merged into this record and removed. IDENTIFICATION IS BY ARXIV ID, RE-FETCHED NOT ASSUMED: the arXiv API returns one entry for 2111.00396 with this title and the author list [Albert Gu, Karan Goel, Christopher Ré], which both records were matching. Source w6p-arxiv-api-duplicate-id-confirmation. Venue evidence per record is in w6p-openreview-api2-duplicate-venue-records. Every arXiv id in this consolidation was taken from an API response rather than from memory or from the records, per the rule that this repo has shipped wrong ids twice. WHAT WAS CHECKED BEFORE REMOVING ANYTHING: every field of every data/**/*.json record was scanned for the string "s4-structured-state-spaces". Zero inbound references were found - no model, gotcha, source, engine or doc record pointed at it - so the merge breaks no reference. Papers are cited by SOURCE ID, never by slug, so no `sources` entry needed repointing; the retired record's source ids were folded into this record's `sources` so the evidence survives the merge. MERGED FIELD BY FIELD - nothing was silently dropped: mechanism: the retired record's text was materially fuller (712 chars vs 395) and is RETAINED here rather than discarded. Its text: Resurrects the structured state space model x'(t) = A x(t) + B u(t), y(t) = C x(t) + D u(t), realised as a CNN layer, and shows that when the state matrix A is HiPPO-structured the resulting kernel is computed in O(L log L) with FFTs instead of O(L^2) with attention. The HiPPO construction makes A = -1/2 * B C^T - i sqrt(B C^T) for a well-chosen (B, C), producing the 'S4D' real variant and 'S4' complex variant. Crucially the parameters here are FIXED (not a function of the input), which is precisely the weakness Mamba later identifies and fixes. State is fixed-size and constant in sequence length, so like all SSMs there is no KV cache; this was demonstrated at long context before selective SSMs existed. speedup_reported: the retired record's text was materially fuller (550 chars vs 368) and is RETAINED here rather than discarded. Its text: The paper's headline is that a single architecture with a single set of parameters matches or exceeds specialist models across long-range sequence benchmarks (LRA, Long Range Arena) including sequential CIFAR, Path-x, Path-256, and it reaches near state of the art on audio classification and LM tasks while being substantially faster than attention at long length. Numbers are relative perplexities and accuracy, not tokens/second, so there is no clean speedup ratio to quote; the FFT-based O(L log L) formulation is the structural efficiency claim. hardware_relevance was EMPTY on this record while the retired twin listed A100 80GB SXM4, A100 80GB PCIe and Google TPU v4; the twin's populated list is adopted rather than discarded. open_weights: open_weights was null here and true on the retired twin; the repository github.com/state-spaces/s4 is cited by both records, so true is the consistent value. AFFILIATIONS CORRECTED - arXiv HTML byline for 2111.00396v3 gives all three authors (Gu, Goel, Re) the single affiliation 'Department of Computer Science, Stanford University'. Both repo records already said Stanford, so this one needed no correction - recorded because a sweep is only credible if it can also say 'checked and correct'. VENUE AND THE CLAIMS THAT COMPETED FOR IT: ICLR 2022, and the merge is what finally removes the false JMLR claim. The retired twin s4-structured-state-spaces asserted 'Venue is JMLR 2022, confirmed via Semantic Scholar' - a venue the schema has no member for, so it had been recorded as venue='iclr' with JMLR buried in a notes sentence that contradicted the field. A Crossref bibliographic query for the exact title returns six works and not one of them is this paper or a JMLR article (source w6p-crossref-s4-no-jmlr-deposit), so the JMLR claim has no basis in any publisher deposit, and the task's own brief records that Semantic Scholar never said it either. ICLR 2022 stands on three independent legs: the arXiv comment field reads 'ICLR 2022 (Outstanding Paper HM)', OpenReview api v1 returns venue 'ICLR 2022 Oral' with venueid 'ICLR.cc/2022/Conference' for this exact title with authors Gu, Goel, Re, and the OpenReview DBLP mirror returns 'ICLR 2022'. The lesson worth keeping: the false claim survived two waves because S4's real venue is not Crossref-deposited, so an agent recording the ABSENCE of a Crossref hit could read anything into it. A negative result got inverted into a positive attribution, and nothing downstream caught it because the record's own field said iclr all along. STATUS: the contradiction this pair represented is now resolved, so the record is no longer marked contested on account of the duplicate. Fields were changed as stated above; arxiv_id is unchanged.