Remembering Has a Price: Learning Memory Worth under Resource Constraints

AI summary

Overview

Research area: Lifelong / continual learning for LLM-based language agents, specifically memory management under joint resource constraints (test-time continual learning).

Technical level: Advanced — assumes familiarity with retrieval-augmented generation, online learning, kernel ridge regression, and agent benchmarks.

Scope: The paper formalizes "resource-constrained lifelong agents," shows that existing memory mechanisms degrade under tight joint budgets, and proposes TokenWorth, a lightweight online memory-worth estimator that improves both success rate and token efficiency across three LifelongAgentBench environments on two backbones.

What This Paper Is About

Lifelong agents are supposed to keep improving by storing and reusing past experience, but in practice they run under tight limits on how much they can generate, how many interaction rounds they get, and how much memory they can store or inject. The authors show that under such joint constraints, several sophisticated memory methods provide little benefit over simple retrieval or even a no-memory agent, and sometimes perform much worse. The goal is therefore not to retrieve the most relevant memory, but to learn which memories are actually worth spending scarce context and tokens on.

Key Contributions

1. A formalization of resource-constrained lifelong agents. The paper defines a joint budget 𝒞 = (O_max, J_max, B_max, K_max, L_max) covering per-task output tokens (including all auxiliary LLM calls such as reflection or skill extraction), interaction rounds, persistent memory capacity, number of retrieved memories, and injected memory length, and defines the objective as maximizing average task reward over the task stream under that budget.

2. TokenWorth, an online memory-worth framework. Memory worth is decomposed into an interpretable, prior-regularized linear base scorer over four features (similarity, utility, reliability, recency) plus a residual Recursive Feature Machine (RFM) over a richer query–memory representation, trained from the sparse task-level reward signal y_t = 2r_t − 1 ∈ {−1, +1}.

3. Two-timescale adaptation inside the residual learner. Fast kernel-ridge-regression updates track local residual structure, while a slower Average Gradient Outer Product (AGOP) update adapts the diagonal feature metric, so prediction and feature geometry do not adapt at the same rate.

4. A unified worth signal for retrieval and memory lifecycle. Query-dependent worth selects what to use now, while probe-averaged worth V_t(m) — averaged over a small set of recent probe queries — governs admission, replacement, and eviction in the bounded memory bank.

Main Findings

• Existing memory methods are fragile under joint constraints. Under the stringent budget, several lifelong-memory baselines give limited improvement over the no-memory Standard agent and can substantially underperform it, particularly on KG (for example, MemRL reaches 4.7% on local KG versus 30.7% for Standard).
• Best success rate in all six settings. TokenWorth achieves the highest task success rate in every environment–deployment combination: local (Qwen2.5-14B-Instruct) DB 65.0%, OS 59.4%, KG 36.7%; API (DeepSeek-V4-Flash) DB 62.2%, OS 73.2%, KG 36.7%.
• Large margins on database interaction. Locally, TokenWorth beats the strongest baseline RAG (33.0%) by 32.0 percentage points on DB; it also improves the strongest baseline by 4.8 points on OS and 6.0 points on KG. Under the API deployment the gains over the best competing method are 30.0 points on DB, 3.0 on OS, and 4.7 on KG.
• Fewest output tokens as well. TokenWorth uses the lowest output-token count in all six settings: relative to Standard it reduces generation by 9.3%, 51.5%, and 18.7% on local DB, OS, and KG, and by 31.6%, 58.3%, and 21.3% on the API counterparts.
• Gains are not from longer generation. Because token use falls while success rises, the authors attribute the improvement to better memory selection letting the frozen backbone use a limited generation budget more effectively.
• Ablation shows the residual learner needs geometry adaptation. On local DB, the base scorer alone reaches 64.2%, adding an RFM residual with a fixed feature metric drops to 63.0%, and the full framework with AGOP-based feature adaptation reaches 65.0% — recovering the degradation and modestly exceeding the base-only variant.
• Not a capacity problem. Under the same budget, different memory policies produce markedly different downstream performance, so the failures cannot be attributed simply to insufficient memory capacity.

Methodology in Plain English

The agent keeps a small bank of past successful interactions. For a new task, it first pulls a short candidate list using cheap textual relevance, then scores each candidate with two pieces working together: a simple linear formula that captures stable, human-readable signals about whether a memory tends to help, and a nonlinear correction model that captures query-specific exceptions. The linear part starts from hand-set weights and is pulled back toward them so it does not drift when feedback is scarce; the nonlinear part is fit with kernel ridge regression over a compact hashed-text representation plus usage statistics such as reliability, recency, and access frequency.

The nonlinear part has two speeds: its prediction coefficients update frequently to catch local patterns, while the distance measure used to compare memories (a diagonal metric learned via AGOP) updates more slowly and is refit afterward. The residual correction is ramped in gradually over the first three fits to avoid abrupt early behavior.

After each task, the environment returns a binary reward; the selected memory gets label +1 or −1, the linear scorer is refit on a bounded FIFO window, and the correction model learns the part of that label the linear scorer failed to explain. The same worth score then decides what stays in memory: candidates come only from externally verified successes, worth is averaged over recent probe queries to estimate long-term value, and when the bank is full the lowest-worth memory is evicted. Everything happens in a lightweight controller — the backbone stays frozen, with no fine-tuning, task replay, counterfactual re-execution, or extra LLM calls.

Evaluation uses three LifelongAgentBench environments (DB, OS, KG) with memory capacity 64 and at most one retrieved memory per task; output-token budgets are 128, 512, and 128 with interaction limits of 3, 5, and 15 rounds respectively. Baselines are Standard, RAG, MemRL, Mem0, MemP, MemSkill, Reflexion, EvoSC, and EvoSkill, all sharing the same frozen backbone, task stream, and budget.

Why This Matters

Research impact. The paper reframes lifelong agent memory from a relevance problem to a value-estimation problem, and argues that memory research should be evaluated under explicitly stated joint budgets rather than with unbounded context and interaction. The finding that well-known memory methods can fall below a no-memory baseline on some environments is a useful corrective for the field, and the "worth" formulation connects agent memory to credit assignment under sparse, single-sample feedback.

Real-world applications:

• Cost-sensitive agent deployment: API-based agents where every generated token is billed and every extra interaction round costs money and latency.
• Long-running assistants on constrained hardware: on-device or edge agents with hard memory caps and limited inference budgets.
• Tool-use and operations agents: database, operating-system (Bash), and knowledge-graph assistants that must pick the single most useful past episode rather than stuffing context.
• Skill-library maintenance: systems that accumulate reusable skills or procedures (the Reflexion, MemSkill, EvoSkill, EvoSC family) and must decide what to keep versus discard as the task distribution shifts.

Industry relevance. Because TokenWorth requires no backbone updates and no additional LLM calls, it is an attractive drop-in controller layer for production agents that must hold a fixed cost envelope while improving over time.

Future Directions

• Budget-efficient credit assignment. The paper states directly that feedback is observed only for the selected memory, so its causal contribution remains unidentified; developing methods that resolve this without counterfactual re-execution is named as the key open problem.
• Robustness across budget levels. The authors explicitly note their results characterize one fixed stringent budget and do not claim robustness across a range of budget levels, leaving budget sweeps and adaptive budgeting open.
• Beyond the three main environments. Online lifelong variants of BigCodeBench and ALFWorld are described as additional evaluations reported in Appendix C, but their numbers are not included in the main text summarized here, so the generality of the approach on coding and embodied tasks is not quantified in this portion of the paper.
• Richer memory-worth representations. The current representation deliberately uses deterministic hashed text vectors rather than learned semantic embeddings and a diagonal (rather than full) feature metric; whether learned embeddings or full-matrix geometry improve worth estimation under the same token budget is untested.

Target Audience

Researchers and advanced practitioners working on LLM agents, continual/lifelong learning, and memory systems for language models — particularly those building deployed agents under real cost constraints. It is also relevant to engineers designing retrieval and context-management layers for production agents, and to benchmark designers interested in evaluation protocols that fix generation, interaction, and memory budgets rather than reporting unbounded-context results. Readers without background in online learning or kernel methods will find the method sections dense but the problem framing and results accessible.

Authors’ abstract

Lifelong agents continually accumulate and reuse experience to improve after deployment, yet in practice they often operate under tight generation, interaction, and memory budgets. Under such stringent joint constraints, we find that existing lifelong-memory methods can become ineffective, with several sophisticated approaches offering little advantage over simple retrieval or even no-memory agents. This reveals a more fundamental problem: resource scarcity makes each memory decision more consequential. When only a small amount of past experience can be retained or reused and opportunities for reasoning and recovery are limited, retrieving a relevant but ineffective memory can consume scarce context and hinder downstream execution. The key challenge is therefore not simply to retrieve relevant experience, but to determine which experiences are actually worth retaining and reusing. To address this challenge, we propose TokenWorth, a lightweight online memory framework that learns query-dependent memory worth from sparse execution feedback and applies it consistently to memory retrieval and bounded memory management. Across three LifelongAgentBench environments and both local and API-based deployments, TokenWorth achieves the highest task success rate while using the fewest output tokens among the evaluated methods. These results suggest that effective lifelong adaptation under resource constraints depends not on remembering more, but on learning what is worth remembering. Our code is publicly available at https://github.com/AIGNLAI/TokenWorth.