Kanerva: Token-Budgeted, Validity-Aware Memory for Coding Agents, Without an LLM in the Loop

Coding agents forget everything between sessions, and the memory systems built for them mostly select context by similarity top-k, ignore what items cost in tokens, and have no model of whether a stored fact is still true. We cast agent memory as online budgeted selection, show that the surveyed systems are special cases, and derive where each is worst-case suboptimal. We then present Kanerva, a local memory layer with no LLM in the loop. It scores each candidate with a calibrated relevance model over retrieval, item and context features, selects under a hard token budget, keeps an item's validity apart from its usefulness, expands candidates through neighbouring turns, and stays silent when the store looks unable to answer a prompt. We prove a (1/2)(1 - 1/e) selection guarantee with a per-query certificate, a bound on how probability error reaches the selection, a dynamic regret bound that separates the cost of expiring items, a linear lower bound for validity-blind learners, a rate-distortion bound for reversible consolidation, and a stationary store-size result. On a third held-out test with no LLM in the evaluation, on fifteen repositories in four languages that nothing was fitted or tuned on, averaged over budgets from 128 to 4096 tokens and without structured keys, Kanerva recovers 0.775 of the evidence against 0.752 for hybrid retrieval and 0.749 for hybrid with a cross-encoder, and it leads on all fifteen. On facts that changed it injects an outdated version 34.9% of the time against 99.9% for hybrid, and on none of the test queries with keys, though a simple keep-the-newest-twin rule gets 36.5% and the store alone does not detect free-text updates, though a real agent shown similar notes fixed most of them in a small trial. The lexical configuration, which needs no model, is close to level with BM25 from 512 tokens up. Three further tests on six C and C++ repositories each, which the model had never seen, are less clear. Two give the same picture with a smaller lead, a change to the near-twin rule cuts stale injection there to 16.0%, and on the third, with class methods among the facts, the lead over hybrid does not hold on strict recall. On BEAM, a check and not a test because earlier tests saw it, it recovers 0.574 against 0.440 for hybrid. No untouched conversation benchmark remains. A gate that keeps the store silent on prompts it cannot answer costs 5.6% of recall on the store's own questions, and its false-alarm rates come from foreign questions. When a small local model answers from the selected notes, little of this carries over: no difference between methods survives correction, and on conversations far higher recall does not beat BM25. Online learning adds almost nothing on top of the fitted model, on simulated feedback, and forgetting costs recall.