Sub-Quadratic State-Space Transformers with Provable Long-Horizon Memory Retention

Sophia Lin; Omar Khalil

doi:10.5555/peerrxiv.2026.00392.v2

PeerRxiv:2609.00392v2 · CS-AI / Machine Learning & Foundation Models

Sub-Quadratic State-Space Transformers with Provable Long-Horizon Memory Retention

Dr. Sophia Lin (Stanford University)
ORCID: 0000-0002-3310-8821 · Pooled Credits: 2 Cr

Dr. Omar Khalil (University of Toronto)
ORCID: 0000-0003-9012-4411 · Pooled Credits: 2 Cr

CANONICAL CITATION ID

PeerRxiv:2609.00392v2

PEERRXIV VERSION DOI

10.5555/peerrxiv.2026.00392.v2

FREE CERN ZENODO DATACITE DOI

10.5281/zenodo.1400392

BAYESIAN SCORE / WILSON 95% LB

4.18 / 5.00 (LB 43.8%)

Abstract

Linear-time sequence models and structured state-space models (SSMs) achieve O(L) inference scaling but provably suffer from exponential memory decay on associative recall tasks over context lengths exceeding 128k tokens. We derive a spectral-gated hybrid operator that interleaves rank-r Hankel state compressions with sparse local attention heads, achieving O(L log L) complexity with tight lower bounds on long-horizon associative recall.

Version Lineage (Before v1 vs. After v2)

V1 — Before Manuscript (v1 — Initial Submission) · DOI: 10.5555/peerrxiv.2026.00392.v1 · 2026-09-20

Before Peer Review: Theorem 3.2 proof sketch under exact FP64 arithmetic + 256k context benchmarks.

V2 — After Manuscript (v2 — Post-Rebuttal Peer-Validated Version) · DOI: 10.5555/peerrxiv.2026.00392.v2 · 2026-10-10

After Peer Review: Extended Theorem 3.2 proof to finite-precision BF16 arithmetic, added 1M-token benchmarks on 8x H200 GPUs, and released open-source Triton kernels.

Public Signed Referee Reports (3)

Dr. Sebastien Moreau (INRIA Paris) · ORCID: 0000-0002-1190-3321 Round 2 [ORIGINAL] · Verdict: ENDORSED (undefined/5.0) · DOI: 10.5555/peerrxiv.2026.00392.r1

Summary: Theorem 3.2 is a landmark theoretical result for hybrid SSM-attention architectures. Comparing the Before (v1) and After (v2) manuscripts confirms that the BF16 quantization proof is completely watertight.

Critique: All comments addressed in the v2 After Manuscript.

Prof. Ananya Patel (Carnegie Mellon University (CMU)) · ORCID: 0000-0003-8821-5543 Round 2 [ORIGINAL] · Verdict: ENDORSED (undefined/5.0) · DOI: 10.5555/peerrxiv.2026.00392.r2

Summary: The 1M-token empirical evaluations and open Triton kernels added in v2 make this immediately reproducible and highly impactful.

Critique: Endorsed without reservations following v2 revision.

Dr. Henrik Lindqvist (KTH Royal Institute of Technology) · ORCID: 0000-0001-4490-1287 Round 2 [FRESH] · Verdict: ENDORSED (undefined/5.0) · DOI: 10.5555/peerrxiv.2026.00392.r3

Summary: Cloned the open-source repository and reproduced Figure 4 on a single node. Fully endorse publication as a Peer-Validated Article.

Critique: None.

BibTeX Citation Record (Includes Signed Open Peer Reviews)

@article{lin2026peerrxiv00392v2,
  author        = {Sophia Lin and Omar Khalil},
  title         = {{Sub-Quadratic State-Space Transformers with Provable Long-Horizon Memory Retention}},
  journal       = {PeerRxiv Open Science Repository},
  year          = {2026},
  month         = sep,
  eid           = {PeerRxiv:2609.00392v2},
  eprint        = {PeerRxiv:2609.00392v2},
  archivePrefix = {PeerRxiv},
  primaryClass  = {cs-ai},
  issn          = {0000-0000},
  doi           = {10.5555/peerrxiv.2026.00392.v2},
  note          = {PeerRxiv Peer-Validated Monograph (3 Signed Open Reviews, Editor-Less Quorum); Dual Free DataCite DOI: 10.5281/zenodo.1400392},
  url           = {http://peerrxiv-platform.pages.dev/abs/peerrxiv.2026.00392}
}

@misc{lin2026peerrxiv00392v2_review_r1,
  author       = {Sebastien Moreau},
  title        = {{Signed Open Referee Report (Round 2, ORIGINAL Seat) on: Sub-Quadratic State-Space Transformers with Provable Long-Horizon Memory Retention}},
  year         = {2026},
  publisher    = {PeerRxiv Open Science Repository},
  doi          = {10.5555/peerrxiv.2026.00392.r1},
  url          = {http://peerrxiv-platform.pages.dev/doi/10.5555/peerrxiv.2026.00392.r1},
  note         = {Verdict: ENDORSED (undefined/5.0)}
}

@misc{lin2026peerrxiv00392v2_review_r2,
  author       = {Ananya Patel},
  title        = {{Signed Open Referee Report (Round 2, ORIGINAL Seat) on: Sub-Quadratic State-Space Transformers with Provable Long-Horizon Memory Retention}},
  year         = {2026},
  publisher    = {PeerRxiv Open Science Repository},
  doi          = {10.5555/peerrxiv.2026.00392.r2},
  url          = {http://peerrxiv-platform.pages.dev/doi/10.5555/peerrxiv.2026.00392.r2},
  note         = {Verdict: ENDORSED (undefined/5.0)}
}

@misc{lin2026peerrxiv00392v2_review_r3,
  author       = {Henrik Lindqvist},
  title        = {{Signed Open Referee Report (Round 2, FRESH Seat) on: Sub-Quadratic State-Space Transformers with Provable Long-Horizon Memory Retention}},
  year         = {2026},
  publisher    = {PeerRxiv Open Science Repository},
  doi          = {10.5555/peerrxiv.2026.00392.r3},
  url          = {http://peerrxiv-platform.pages.dev/doi/10.5555/peerrxiv.2026.00392.r3},
  note         = {Verdict: ENDORSED (undefined/5.0)}
}