The KV cache is the unavoidable dilemma of long-context inference: as context grows, softmax attention must read more keys and values, slowing generation; storing them all in VRAM breaks memory first. Linear attention and state space models compress context into a fixed-size state, making speed and memory constant, but the fixed capacity ceiling makes recall collapse as information grows. Moritz Brosamle from the Department of Mathematics at the University of Tubingen proposes LEMA (Latest Exact Match Attention) on arXiv, choosing a third path: the state can grow without bound, but it lives neither in VRAM nor gets scanned token by token — it is simply looked up as a dictionary. (https://arxiv.org/abs/2609.25802)
Attention reduced to one hash lookup
The LEMA rule is minimal: queries and keys are binarized first, and each query attends only to the latest exactly matching key, returning zero when nothing matches. The generation-step pseudocode in the paper is a few lines — one dictionary lookup, one dictionary insert, with an existing key overwriting its old value. The KV cache of each attention head thus becomes a dictionary: state size grows with content, with a theoretical bound of 2 to the power of head-dimension entries, while in practice only keys that occur are stored.
Theory: bidirectional equivalence with word-RAMs
The paper proves that LEMA transformers with chain of thought can simulate word-RAMs, an abstraction of modern computers; conversely, word-RAMs can simulate LEMA transformers at a cost per token independent of context length. The author states that, to their knowledge, this two-way correspondence has not been established for other attention variants — expressivity results for the hard-attention family usually prove only one direction.
Training: annealing from soft attention to the hard rule
Exact matching is non-differentiable, making training the hardest part. The paper passes gradients through binarization with a straight-through estimator, then uses stick-breaking attention as a soft surrogate, slowly annealing it towards LEMA. The author admits this is merely a first attempt: the annealing is sensitive to learning rates, and training still requires compute quadratic in sequence length.
Results: beats GDN on recall, still trails softmax overall
On a synthetic associative recall task (vocabulary 4096), LEMA trained only at 8 associations extrapolates almost perfectly to 4096, while the fixed-state gated DeltaNet (GDN) fails once associations grow too numerous. On language models from 29M to 834M parameters trained on FineWeb-Edu, LEMA matches the validation loss of softmax transformers at 55-57% of its parameters. Two long-range recall proxies show the difference more clearly: in the farthest bucket of repeated rare bigrams, LEMA loss sits 2.1 nats below its own baseline versus 0.7 for GDN; on RULER single-needle retrieval (S-NIAH-1), once LEMA retrieves successfully, repeated filler sentences no longer change its state, so retrieval persists indefinitely without state growth.
Engineering: hash table in memory, constant generation speed
The inference implementation packs all heads KV caches into a single open-addressing hash table (linear probing) in main memory, leaving only weights and activations in VRAM. Benchmarked against vLLM on an RTX 3090, LEMA generates at constant speed comparable to GDN as long as the hash table stays away from capacity. For the trained 834M model, per-head dictionaries hold on average 1.7k entries after 16k tokens and 18k after 256k — the paper tests with a 50 GB hash table in main memory. The cost: around 10% of heads never find a match. Code is open-sourced (github.com/moritzbroe/latest_exact_match_attention).
Connecting "attention that resembles a computer" with "attention that can be trained", LEMA offers a rare route: recall via unbounded state, speed via O(1) lookup, and VRAM relief via main memory. The gap at the 834M scale shows the training method is far from mature, but the cure for KV-cache anxiety may not be smarter compression — it may be a different data structure altogether.