Linear memory systems face a fundamental logarithmic penalty for top-1 retrieval but can achieve quadratic capacity if you only need the correct answer ranked highly rather than first—a distinction that matters for building efficient retrieval systems.
This paper analyzes how many key-value pairs a linear memory matrix can store, showing the answer depends on the retrieval task. For winner-take-all retrieval (finding the single best match), capacity scales as d² ≈ n log n due to extreme-value statistics. For listwise retrieval (keeping the correct answer in a top-k list), capacity improves to d² ≈ n.