Remember What Cannot Be Recovered: Memory Allocation from Theory to Frontier Agents

Language-model agents sustain extended interactions through context compaction, persistent memory, and retrieval, choosing what to remember and what to recover later under uncertainty about future needs and recovery resources. An agent may omit a dependency from memory if alternative paths preserve the answers it needs, but that dependency becomes necessary when unavailable components block those alternatives. For ordered random workflows, we quantify the average number of edges and bits needed to preserve every answer. In the small-average-error regime we analyze, we construct an asymptotically optimal memory by arranging retained connections so that surviving routes branch and reconnect, providing alternative paths between many source-target pairs using the same stored edges. We then test whether frontier language models can choose what to remember. On random and real citation graphs, models asked to write the memory fall far short: DeepSeek V4-Pro, GLM 5.2, and Muse Glimmer 30B do no better than randomly chosen edges, and on citation graphs most of their errors are avoidable isolation errors, in which every stored neighbor of an endpoint fails, an event that an even allocation of the budget makes much less likely. Telling models how our theory spreads the budget reduces these errors for a model that follows the advice, but its memories still do no better than random ones: avoiding isolation is necessary, yet good memories also depend on which routes are kept, and the models do not work this out from the graph. Our results show that what an agent should remember depends on how its information can be recovered rather than on how important it looks, and that current models do not yet make this choice on their own.