SAM: Replacing O(n²) Attention with O(1) Content-Addressed Memory via Semantic Structure
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
We present SAM (Sparse Addressable Memory), an architecture that provides an O(1) alternative to transformer self-attention — which scales at O(n²) in memory and compute — using learned content-addressed memory slots operating at O(1) per token with respect to sequence length. Our theoretical contribution is a formal proof that the expected number of harmful collisions is bounded by k²T^{2α}(1−q)²·μ^P, a clean factorization of semantic complexity and geometric resolution grounded in Heap's Law and PQ subspace independence. Under explicit geometric assumptions, N = O((log T)^P) slots suffice. Empirically, SAM achieves 100% retrieval accuracy on a 24,446-token document, 75–83% across domains, and beats Mamba's 50% baseline — all at O(1) cost per token. Memory footprint remains flat at 28.8MB across 1K–100K tokens, compared to a transformer's 5,767GB at 100K tokens — a 200,183× reduction in training memory and 63× reduction in inference KV-cache, both measured empirically.
Fields of Study & Subjects
Topic Modeling
Natural Language Processing Techniques
Algorithms and Data Compression
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 29 March 2026
- Language
- EN
- Document type
- Preprint