LIT-666: Sparse Distributed Memory

Kanerva (MIT Press, 1988; paperback 2003) — https://mitpress.mit.edu/9780262514699/sparse-distributed-memory/

Key takeaways

• The problem is the best match. Given a set of stored memories and a query, return the stored item closest to the query, quickly, without comparing against every memory. OSTI’s catalogue abstract lists “the search of memory for the best match” among the book’s subjects, and LIT-641 restates the model as a solution to exactly that problem.

• The model, in three primitives. Everything lives in {0,1}ⁿ with Hamming distance. Patterns are an address and a pointer — the pointer is the address itself when autoassociative, another pattern’s address when heteroassociative, which is how sequences are stored. Neurons sit at fixed, randomly placed addresses, far fewer than 2ⁿ of them, which is where “sparse” comes from; each holds a vector of counters. The query is an address to read from.

• Write and read are both distributed over a radius. A write adds a pattern’s pointer to every neuron within Hamming distance d of its address, so each neuron holds a superposition of many patterns. A read sums the stored vectors of every neuron within d of the query and thresholds each bit by majority. Because a pattern was stored in many neurons and the query reads from many, the read weights each pattern by how many neurons the two circles share — the intersection of two hyperspheres, which falls off near-exponentially with the distance between query and pattern. That weighting is the property LIT-641 maps onto softmax.

• Neurons as address decoders, and the cerebellum. Each neuron fires when an input lies within d of its address, so the layer is an address decoder over a sparse sample of the space. The book maps this onto the cerebellar cortex: granule cells as the decoders, their parallel-fibre synapses as the storage, Purkinje cells as the summation and threshold — the mapping LIT-641 §5 restates and credits to this book, while noting what it does not explain.

• Critical distance is the book’s; the other two optimal radii are not. LIT-641 fits β against three optimal radii. Its §1 cites all three to Kanerva’s 1993 review. The review, filed as LIT-669 and read in full, has the signal-to-noise optimum and the capacity analysis, and no critical distance. LIT-641’s own Appendix B.5 reproduces the critical-distance curve as “Figure 7.3 from the SDM book”. Per its Appendix B.4, the review also replaces the book’s variance approximation (the book’s Appendix C) with a more accurate one.

Standing in the anthology

The record held the claim that attention approximates Kanerva’s memory (THEORY-097, sourced to LIT-641) and did not hold the memory. This is the source that claim is about, and LIT-641 could not stand without it — it is filed as what LIT-641 carries further.

It has not been read. The book is not openly available. This note is written from OSTI’s catalogue abstract (record 7055202), which lists its contents, and from LIT-641’s account of the model: §1 and §5, and since version 2 its Appendix B. Every takeaway above says which of those it rests on. Two questions were left for a reading:

• Whether the hypersphere-intersection weighting is derived in the book. Answered, secondhand. LIT-641 Appendix B.1 says the book derives the exact circle-intersection equation in its Appendix B, with a continuous approximation used throughout. It also reports that the book’s tabulated values are “slightly inaccurate”, probably from rounding.
• Which biological claims the book makes itself. Still open. Kanerva’s own account of the cerebellar mapping, discrepancies included, is in the 1992 review (LIT-669). Whether the book says the same was not checked.

Nothing here moves a practice. SOTA-192 recommends QK-norm on its own evidence; the SDM account explains why the technique might work and does not change whether to use it.

The source is a publisher’s catalogue URL, the weakest kind this record accepts: the book has no DOI in Crossref, and ACM’s 10.5555/534853 is an internal identifier that does not resolve through doi.org.