Content-Addressed Recursive State: Resolving the DenseRetrieval Trade-o with a Cubic-Composition Readout

Abstract

Recurrent architectures that compress history into a single state are cheap but have classically been unable to exactly retrieve far past key–value bindings, whereas attention content-addresses the whole past at quadratic cost. We show that the conflict between dense language modeling and long-range associative recall need not be a binding trade-off. We couple a nonlinear aggregated-state backbone (AGG, an input-gated forget–write recurrence computed by a parallel scan) with a content-addressed readout (SEL, a small polynomial-composition kernel that scores each query against a bounded window of past states and retrieves their values). At a fixed compute budget on WikiText (GPT-2 vocabulary, V=50257), the combined architecture is the first recurrent model we have tested to simultaneously exceed an equal-size transformer on both axes: it cuts dense perplexity from 183.6 to 127.8 (mean over 3 seeds), and on a real-vocabulary associative-recall probe it reaches 1.000 far-distance (d=7) top-1 recall across three seeds — a level no linear state-space model we compared reached — and this near-perfect recall is retained as the number of key–value pairs scales to m=32 (d=31 recall 1.000) and as the probe is moved from synthetic memorization to real-text long-range retrieval, where the model recovers a hidden bond at 93–100% for contexts up to 8K tokens. Two stability mechanisms — a full-sequence window and a floor on the readout gate — turn an occasional boundary collapse into reliable convergence. The content-addressed readout adds only a narrow, windowed kernel with a handful of parameters, and a controlled removal isolates its role. We argue the resulting architecture is a distinct sequence-modeling primitive: it retains the exact retrieval, compact state, and linear-time cost of its two parents.