When Similarity Is the Wrong Axis: A Co-Need Index for LLM Agent Memory

Long-lived agents commonly retrieve each memory by its similarity to the current query. This objective is poorly matched to compositional requests, whose answers depend on sets of memories connected to one another. We call this structure \emph{co-need locality}. Across four public workloads, co-needed pairs are $1.2$--$3.3\times$ more related than matched random pairs, but the useful relation differs by workload: lexical content in conversation, entity overlap in relational reasoning, and temporal adjacency in agent traces. This mismatch is most visible on LoCoMo, where dense retrieval recovers the complete evidence set for only $3.2\%$ of queries at $k{=}5$, below BM25 at $5.0\%$. We introduce a two-stage co-need index that retrieves anchors, expands them through bounded entity and temporal postings, and ranks the resulting candidates using query and anchor-relative features. Its full-store scorer reaches $10.6\%$ complete-evidence recall on LoCoMo; the bounded index retains $9.7\%$ while scoring 200 candidates. The incremental co-need stage remains near $30\,\mu$s from $10^3$ to $10^6$ memories, compared with $73.8$ ms for full-store scoring at $10^6$. These results identify when query similarity is insufficient and show that relation-aware retrieval can recover missing evidence at bounded additional cost.