# ERRAND: Budgeted Maintenance of Agent Memory

arXiv: https://arxiv.org/abs/2609.29545 · HTML: https://mlsanity.com/paper/2609.29545/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 80 references that are in the map.
- First posted on arXiv 2 Sep 2026.

## Builds on (most cited first, 30 of 51)

- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [A-MEM: Agentic Memory for LLM Agents](https://mlsanity.com/paper/2502.12110/) (2025)
- [Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory](https://mlsanity.com/paper/2504.19413/) (2025)
- [Zep: A Temporal Knowledge Graph Architecture for Agent Memory](https://mlsanity.com/paper/2501.13956/) (2025)
- [Agent Workflow Memory](https://mlsanity.com/paper/2409.07429/) (2024)
- [FreshLLMs: Refreshing Large Language Models with Search Engine Augmentation](https://mlsanity.com/paper/2310.03214/) (2023)
- [ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory](https://mlsanity.com/paper/2509.25140/) (2025)
- [STALE: Can LLM Agents Know When Their Memories Are No Longer Valid?](https://mlsanity.com/paper/2605.06527/) (2026)
- [Skill-Pro: Learning Reusable Skills from Experience via Non-Parametric PPO for LLM Agents](https://mlsanity.com/paper/2602.01869/) (2026)
- [Supersede: Diagnosing and Training the Memory-Update Gap in LLM Agents](https://mlsanity.com/paper/2606.27472/) (2026)
- [Prioritized Information Bottleneck Theoretic Framework with Distributed Online Learning for Edge Video Analytics](https://mlsanity.com/paper/2409.00146/) (2024)
- [MemTX: Transactional Belief Commit for Stateful Agent Memory](https://mlsanity.com/paper/2607.23929/) (2026)
- [Let's Think in Two Steps: Mitigating Agreement Bias in MLLMs with Self-Grounded Verification](https://mlsanity.com/paper/2507.11662/) (2025)
- [R-ACP: Real-Time Adaptive Collaborative Perception Leveraging Robust Task-Oriented Communications](https://mlsanity.com/paper/2410.04168/) (2024)
- [Inference-Time Budget Control for LLM Search Agents](https://mlsanity.com/paper/2605.05701/) (2026)
- [Feedback Friction: LLMs Struggle to Fully Incorporate External Feedback](https://mlsanity.com/paper/2506.11930/) (2025)
- [Enhancing Vehicular Platooning with Wireless Federated Learning: A Resource-Aware Control Framework](https://mlsanity.com/paper/2507.00856/) (2025)
- [Graph-Native Cognitive Memory for AI Agents: Formal Belief Revision Semantics for Versioned Memory Architectures](https://mlsanity.com/paper/2603.17244/) (2026)
- [AgentCL: Toward Rigorous Evaluation of Continual Learning in Language Agents](https://mlsanity.com/paper/2606.02461/) (2026)
- [Forget to Improve: On-Device LLM-Agent Continual Learning via Budget-Curated Memory](https://mlsanity.com/paper/2606.25115/) (2026)
- ["X of Information'' Continuum: A Survey on AI-Driven Multi-dimensional Metrics for Next-Generation Networked Systems](https://mlsanity.com/paper/2507.19657/) (2025)
- [Shared Spatial Memory Through Predictive Coding](https://mlsanity.com/paper/2511.04235/) (2025)
- [RELIEF: Turning Missing Modalities into Training Acceleration for Federated Learning on Heterogeneous IoT Edge](https://mlsanity.com/paper/2604.04243/) (2026)
- [Lifecycle-Aware Federated Continual Learning in Mobile Autonomous Systems](https://mlsanity.com/paper/2604.20745/) (2026)
- [When Memory Updates but Behavior Does Not: Repairing Implicit Stale Dependencies in Personalized Agent Responses](https://mlsanity.com/paper/2608.01619/) (2026)
- [Reinforcement Learning-Based Energy-Aware Coverage Path Planning for Precision Agriculture](https://mlsanity.com/paper/2601.16405/) (2026)

## Built on by (most cited first, 1 of 1)

- [Not All Experience Belongs in the Weights: Component Routing for Self-Improving GUI Agents](https://mlsanity.com/paper/2610.01787/) (2026)

## Abstract (arXiv)

Deployed agents run on handed-over knowledge: a frozen policy consults a briefing of consolidated items written before the stream begins. The world then moves while the store stands still: paths close, flags change, price bands move; every item was true at handover, and the failure is staleness, not ignorance. We introduce ERRAND, which treats revalidation as a priced errand: a recheck competes with the task it protects for the same scarce actions, funded only when the value per action of resolving a doubt clears a running wage. The errand index is single-peaked, vanishing at both ends of belief, so certainty in either direction costs nothing; free en-route receipts maintain on-path knowledge, and repair writes a version, never a deletion. Under equal action budgets in two drifting tool-use worlds, ERRAND clears every non-oracle policy on the preregistered calibers, primary in every setting and conditional at every binding budget, leading eager revalidation by 10.0pp at the base cap. Restraint wins: given no cap, ERRAND stops on its own, spending 11.0% of steps, while uncapped eager revalidation spends 70.7% and still finishes 4.5pp behind capped ERRAND. The margin sits where the briefing's coverage is thinnest, the shadow price of long-tail knowledge: a small budget, well priced, beats a bigger store that never rechecks.