Did You Check the Right Pocket? Cost-Sensitive Store Routing for Memory-Augmented Agents
Madhava Gaikwad · 2026
Read Did You Check the Right Pocket? Cost-Sensitive Store Routing for Memory-Augmented Agents by Madhava Gaikwad (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15658.txt.
Introduction
Gaikwad studies how memory-augmented agents should pick which memory store to query. Most systems search every store for every question. That habit wastes tokens and pulls in off-topic context. He frames the choice as a store-routing problem. Scores cover coverage, exact match, and token efficiency. An oracle router beat uniform retrieval on question answering while using far fewer tokens. He also casts routing as a cost-sensitive choice that trades accuracy against retrieval cost.
Catalog record
| CREATOR | Madhava Gaikwad |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34589 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.15658
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Did You Check the Right Pocket? Cost-Sensitive Store Routing for Memory-Augmented Agents Madhava Gaikwad Abstract Memory-augmented agents maintain multiple specialized stores, yet most systems retrieve from all stores for every query, increasing cost and introducing irrelevant context. We formulate memory retrieval as a store-routing problem and evaluate it using coverage, exact match, and token efficiency metrics. On downstream question answering, an oracle router achieves higher accuracy while using substantially fewer context tokens compared to uniform retrieval, demonstrating that selective retrieval improves both efficiency and performance. Our results show that routing decisions are a first-class component of memory-augmented agent design and motivate learned routing mechanisms for scalable multi-store systems. We additionally formalize store selection as a cost-sensitive decision problem that trades answer accuracy against retrieval cost, providing a principled interpretation of routing policies. 1 Introduction Consider a user asking an agent: “What was my weight before I started the diet?” This query depends on historical information from a previous chat session and therefore should draw from long-term memory. It does not require the current-session context, and it typically does not require raw transcripts. Yet many memory-augmented agent frameworks retrieve from multiple stores or large aggregated memory contexts regardless of query type, relying on the language model to filter relevant information during generation ( Lewis et al. 2020 ; Liu et al. 2023a ; Chase 2023 ) . Uniform retrieval carries two costs. First, it creates computational waste by querying memory stores that cannot contain the answer. Second, it can cause accuracy degradation : irrelevant or noisy retrieved context can hinder the model’s ability to identify answer-bearing information, particularly in long-context settings where additional tokens reduce the signal-to-noise ratio ( Liu et al. 2023b ; Yu et al. 2024 ; Zhang et al. 2026 ) . We formalize store selection as a routing problem . Given a query, the router chooses which stores to search before retrieval. This decouples store selection from within-store ranking and makes the accuracy–cost tradeoff explicit. Our evaluation separates two questions. First, do routing policies choose the stores that should be searched for a given query? We test this with synthetic routing labels derived from query taxonomies (Section 5.1 ). Second, if the router chooses the right stores, does this improve downstream QA accuracy on real LLMs ? We test this with an oracle router and fixed store subsets (Section 5.2 ). This setup isolates the value of store selection from model capability and from within-store retrieval quality. Contributions. (1) We define routing metrics (coverage, exact match, waste) that capture complementary aspects of store selection quality. (2) We introduce simple routing baselines, including a conservative hybrid heuristic that emphasizes coverage. (3) We evaluate routing policies using both synthetic labels and real LLM-based QA, showing that selective store choice can reduce tokens while improving accuracy, and that uniform retrieval can underperform despite using more context. (4) We formalize store routing as a cost-sensitive subset-selection problem, providing a decision-theoretic framework that explains when selective retrieval improves both efficiency and accuracy. 2 Related Work Adaptive Retrieval. Prior work studies when to retrieve (Self-RAG Asai et al. 2023 , FLARE Jiang et al. 2023 ) and how much to retrieve (Adaptive-RAG Jeong et al. 2024 ). Recent methods explore which retriever to use through learning-to-rank formulations Kim & Diaz 2025 or self-reflection mechanisms Wu et al. 2026 . SmartRAG Gao et al. 2025 uses reinforcement learning for joint retrieval and generation optimization. We consider a complementary question: where retrieval should occur when memory is partitioned across heterogeneous stores with distinct semantic roles (e.g., episodic vs. semantic memory). Memory Systems. MemGPT Packer et al. 2024 implements hierarchical memory with explicit management operations. Generative Agents Park et al. 2023 rely on reflection and importance scoring to consolidate information over time. Recent architectures organize memory hierarchically for multi-agent reasoning Zhang et al. 2025 . These systems focus primarily on memory organization ; we instead focus on memory access , specifically cost-sensitive routing across stores prior to retrieval. Our store taxonomy draws on cognitive distinctions between episodic and semantic memory Tulving et al. 1972 , and translates these distinctions into operational routing decisions. Multi-Index and Federated Retrieval. The information retrieval literature has long examined federated search across heterogeneous collections Callan 2002 ; Si & Callan 2003 ; Shokouhi et al. 2011 , where resource selection algorithms estimate relevance distributions for each collection Lu & Callan 2006 . These methods route queries across independent search engines; in our setting, the same principles apply to agent memory stores that differ semantically (e.g., current dialogue vs. historical summaries) rather than by document source. Retrieval Routing and Selection. Recent RAG work shows that routing queries across specialized retrievers can improve both efficiency and accuracy Kim & Diaz 2025 ; Wu et al. 2026 ; Guo et al. 2025 . ExpertRAG Gumaan 2025 applies mixture-of-experts routing to context selection, while RAP-RAG Ji et al. 2025 plans adaptive retrieval sequences for multi-hop reasoning. Unlike retriever routing, our setting routes across persistent memory stores whose contents reflect distinct temporal or semantic roles (e.g., STM vs. LTM), requiring store-level rather than passage-level decisions. Context Noise in Long Documents. Long-context modeling faces signal-to-noise challenges when irrelevant tokens distract attention Li et al. 2024b . Recent analyses show that long-context LLMs often underperform targeted retrieval despite larger windows Li et al. 2024a , and that retrieval decisions themselves benefit from uncertainty-guided policies Chen et al. 2026 . Our work complements these findings by showing that store-level noise, retrieving information from irrelevant memory types, can further degrade performance, especially when each store contributes hundreds of tokens. Memory Benchmarks. LoCoMo Maharana et al. 2024 evaluates multi-session conversational memory. LongMemEval Wu et al. 2025 benchmarks knowledge updates and temporal ordering. We use their question taxonomies to derive store-labeling protocols. 3 Problem Formulation 3.1 Memory Architecture A memory store is an independent index containing semantically related information. Each store can be queried separately, and the retrieved content is concatenated into the LLM context. Following MemGPT, we consider four stores: Short-Term Memory (STM) holds the current conversation, typically the last N turns. Queries such as “what did I just mention” or “today’s meeting” require STM. Summary Store contains compressed user facts, including preferences, biographical details, and ongoing projects. Queries such as “what is my phone number” target this store. Long-Term Memory (LTM) stores summaries of past conversations. Queries about earlier discussions (“what did we talk about last week”) rely on LTM. Episodic Memory preserves raw transcripts. Queries that require exact wording or precise timestamps may need episodic memory. 3.2 The Routing Problem Let \mathcal{S}=\{\text{STM},\text{Sum},\text{LTM},\text{Epi}\} denote the set of stores, where Sum is the Summary store and Epi is episodic memory. Given a query q , a routing policy \pi selects stores \hat{G}=\pi(q)\subseteq\mathcal{S} . The system retrieves content from the selected stores and prompts the LLM. Let G denote the ground-truth stores , the stores containing the information needed to answer q . In our synthetic routing evaluation, we derive G from query type: a “single-hop fact” query has G=\{\text{Sum}\} ; a “temporal comparison” query has G=\{\text{LTM},\text{Epi}\} . See Section 9 for the full mapping. 3.3 Evaluation Metrics We evaluate routing with three metrics: Coverage measures whether all necessary stores were included: