SAM: Replacing O(n²) Attention with O(1) Content-Addressed Memory via Semantic Structure

Read full text Summarise with VIRAT
Authors: Saxena Saksham
Cited by: 0

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