💬 NLP

Learning What Not to Forget: Long-Horizon Agent Memory from a Few Kilobytes of Learning

The paper introduces LRE (Learned Relevance Eviction), a lightweight, CPU-only, language-model-free scorer that learns to identify and retain critical interaction history for long-running agents, achieving superior accuracy and efficiency compared to existing baselines while operating with minimal computational cost and annotation-free training.

Original authors: Nusrat Jahan Lia, Aritra Mazumder

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nusrat Jahan Lia, Aritra Mazumder

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a super-smart assistant (like a highly advanced AI) trying to solve a complex puzzle or have a long conversation with a friend. The problem is, your brain has a strict size limit. You can only hold a certain amount of information in your "active memory" at one time.

As you work, you accumulate a massive history of notes, actions, and conversations. Eventually, this history gets too big to fit in your brain. You have to throw some things away to make room for new thoughts. This is called eviction.

The paper introduces a new method called LRE (Learned Relevance Eviction) to solve this problem. Here is how it works, using simple analogies:

The Problem: The "Too Big to Fit" Brain

Imagine you are packing for a trip, but your suitcase has a tiny zipper that only opens halfway. You have hundreds of items (your conversation history or task steps).

The Old Way (FIFO/Recency): You just throw away the oldest items at the bottom of the pile to make room for new ones.
- The Risk: You might throw away the "load-bearing" item, like your passport or a specific code token needed to log in. If you lose that, your trip (or task) fails, even if you have plenty of space left.
The Expensive Way (LLM Compression): You hire a professional editor (another AI) to read your notes and summarize them into a short paragraph.
- The Risk: The editor might accidentally leave out a crucial detail while trying to be brief. Also, hiring an editor every time you add a note is slow and costs a lot of money (computing power).

The Solution: LRE (The Smart, Tiny Librarian)

LRE is a tiny, super-fast "librarian" that lives on a standard computer chip (CPU). It doesn't need a super-computer or a second AI to do its job.

1. It's Tiny and Fast
Think of LRE as a pocket-sized checklist (only a few kilobytes in size). It doesn't rewrite your notes; it just decides which notes to keep. It runs so fast it can check over 1,000 notes per second, whereas the "professional editors" (dense encoders) might only manage 36.

2. It Learns What Matters (The "Load-Bearing" Concept)
LRE looks at your history and asks: "Will I need this specific piece of information later?"

The Analogy: Imagine you are building a house. You have a pile of bricks, wood, and random trash.
- A "recency" approach keeps the last few items you touched.
- LRE looks at the pile and says, "That specific brick from step 3 is the foundation for the roof we are building in step 17. Keep it exactly as it is."
- It keeps the exact text (verbatim), so if a password or a specific ID number is needed later, it's still there, unchanged.

3. It Doesn't Need a Teacher (Self-Supervision)
Usually, to teach a computer what to keep, you need a human to label thousands of examples ("Keep this," "Throw that away").

LRE's Trick: It learns by watching itself. It looks at its own past behavior.
- In a conversation: If the AI mentions a fact (like "I am transgender") and then 400 turns later, it uses that fact to answer a question, LRE learns: "Ah, that fact was important! I should have kept it."
- In a task: If the AI generates a login token and uses it three times later, LRE learns: "That token is load-bearing. Keep it."
- This means it can learn without any human paying to label data.

The Results: Why It Wins

The paper tested LRE in two main scenarios:

1. The Agent (The Robot Worker)

Scenario: An AI trying to book a flight or manage an email account using a series of steps.
Result: When the memory limit was tight, other methods failed because they threw away the login token or the specific ID number needed to finish the job. LRE kept those exact details.
Analogy: While other methods were running in circles trying to log in again and again (wasting time), LRE had the key in its pocket the whole time and finished the job in 37% fewer steps. It was just as accurate as keeping everything, but used 52% less space.

2. The Conversationalist (The Chat Partner)

Scenario: Remembering details from a long chat that happened weeks ago.
Result: LRE was better at finding the right piece of information to answer a question than complex, expensive AI models that try to summarize the chat.
Analogy: If you ask, "What did Caroline say about her family 400 messages ago?", LRE finds that exact message instantly. Other methods either forgot it or summarized it so poorly the answer was lost.

The Bottom Line

LRE is a cheap, fast, and precise way to manage memory.

It doesn't summarize or rewrite (which causes errors).
It doesn't need expensive super-computers to decide what to keep.
It learns from its own mistakes and successes.

The paper argues that for AI agents and chatbots, we don't need to throw away information or hire expensive editors to summarize it. We just need a tiny, smart filter that knows how to keep the "load-bearing" bricks of our history so the structure doesn't collapse.

Technical Summary: Learning What Not to Forget (LRE)

Problem Statement

Long-running Large Language Model (LLM) agents and conversational assistants accumulate interaction histories that eventually exceed the model's context window. To function within fixed token budgets, systems must evict (discard) older history. The core challenge is that eviction is a proactive, query-blind decision: the system must decide what to keep before the future query or action requiring that information exists.

Standard approaches fail in this setting:

Reactive Heuristics (Recency/FIFO): Discard older information based solely on time, often removing "load-bearing" details (e.g., access tokens, identifiers) required for future steps, causing agents to loop or fail.
LLM-based Compression: Summarizing history via LLM calls introduces non-deterministic behavior, paraphrasing errors (losing exact identifiers), and significant latency/cost.
Neural Retrieval/Scoring: Methods that use dense embeddings or attention-based scoring often require a neural forward pass for every unit or are tied to specific model layers, incurring inference costs that scale poorly.

The paper argues that memory eviction is fundamentally a fidelity problem: the system needs to retain exact, verbatim state (not just summarized concepts) to ensure future actions succeed, but must do so with a policy that is cheap, proactive, and independent of the host LLM.

Methodology: LRE (Learned Relevance Eviction)

The authors propose LRE, a lightweight, CPU-only, language-model-free scorer designed to learn which units of history are "load-bearing."

Core Mechanism

Unit Definition: History is segmented into discrete units (e.g., dialogue turns or agent action-observation pairs).
Causal Feature Extraction: For each unit $u_i$ $u_{i}$ , LRE computes a feature vector $\phi(u_i, u_{\le i})$ $ϕ (u_{i}, u_{\leq i})$ based only on the prefix history. Features include:
- Structural: Position in trajectory, recency, length.
- Lexical: TF-IDF, digit counts, capitalized words, presence of URLs/IDs.
- Domain-Specific: Error indicators, code-token presence (for agents), question markers (for conversation).
Scoring: A small, L2-regularized logistic regression model ( $f_\theta$ $f_{θ}$ ) assigns a relevance probability $p_i$ $p_{i}$ to each unit.
- Cost: The model is tiny (e.g., 1.7 KB for agents) and runs on CPU with no neural forward passes at inference time.
Selection (Knapsack Problem): Given a token budget $B$ $B$ , LRE selects the subset of older units $S^*$ $S^{*}$ that maximizes the sum of scores $\sum p_i$ $\sum p_{i}$ subject to the token cost constraint $\sum c_i \le B$ $\sum c_{i} \leq B$ .
- The selection is extractive: units are kept verbatim. No summarization or rewriting occurs, preserving exact identifiers and values.
- A recent window $R_k$ (e.g., last 5 steps) is always retained uncapped.

Self-Supervised Training

To avoid expensive human annotation, LRE derives labels from the system's own behavior (hindsight):

Agent Domain (AppWorld): A step is labeled positive ( $y=1$ ) if an identifier it introduces (e.g., an ID, token) is reused by $\ge 3$ subsequent steps. This identifies "load-bearing state."
Conversation Domain (LoCoMo/LongMemEvalS): A turn is labeled positive if its content tokens have a $\ge 40\%$ overlap with the eventual answer to a question asked later in the session.
Result: This approach recovers 95% of the performance of a fully supervised model (trained on human gold labels) on LongMemEvalS and 82% on LoCoMo.

Key Contributions

A Query-Blind, Proactive Policy: LRE is the first learned eviction policy that operates without access to the future query, making it suitable for real-time agent loops where the next step is unknown.
Verbatim Fidelity: Unlike compression methods that paraphrase, LRE extracts units exactly as they appeared. This is critical for preserving opaque credentials (tokens, IDs) that summarization destroys.
Extreme Efficiency:
- Zero Neural Cost: The scorer runs on CPU with no LLM calls or GPU forward passes.
- Speed: It scores ~~1,181 units/second, significantly faster than dense encoders (~~103 units/s) or token-pruning LLMs (~36 units/s).
- Model Size: The scorer is only a few kilobytes.
Annotation-Free Supervision: Demonstrates that "relevance" can be learned from the system's own logs (reuse patterns) without human labeling.

Experimental Results

Agent Performance (AppWorld)

Task Success: On a 2048-token budget, LRE achieves 41.1% task success, matching the 44.0% success rate of keeping the entire history (unbounded).
Comparison:
- FIFO (Recency): Drops to 34.5% success; agents loop due to lost credentials.
- ACON (LLM Compression): Drops to 26.2% success; summarization loses exact tokens, causing re-authentication loops.
- LRE: Solves 14 tasks that no other policy (including full history in some edge cases of loop failure) could complete.
Efficiency: LRE completes tasks in 19 steps on average, compared to 30.6 for FIFO and 33.5 for ACON. It requires zero compressor calls, whereas ACON requires ~5.45 calls per task.
Context Reduction: Reduces peak context size by up to 52% compared to the worst-case unbounded baseline while maintaining high accuracy.

Conversational Memory (LoCoMo & LongMemEvalS)

Relevance Ranking: LRE achieves a Macro-AUC of 0.829 on LoCoMo and 0.708 on LongMemEvalS.
Baseline Comparison: It outperforms dense embedding encoders (0.643) and token-pruning methods (0.402) despite those methods using neural forward passes. Recency and decay models perform near random (0.478).
Downstream QA: When used as a retention policy for a QA model, LRE provides the best answer quality under a fixed budget, outperforming recency and content salience baselines.

Significance and Claims

The paper argues that cheap learned relevance is sufficient for proactive memory retention in LLM agents.

Fidelity over Compression: The primary failure mode of existing systems is not just "forgetting," but "distorting" (via summarization) or "losing" (via recency) exact state. LRE solves this by prioritizing verbatim extraction.
Deployability: Because LRE is query-blind, CPU-only, and annotation-free, it is a practical policy for production systems where latency and cost are constraints.
Self-Sufficiency: Systems can learn what to keep from their own operational logs, eliminating the need for external supervision.

The authors conclude that while proactive eviction cannot perfectly predict all future needs (a fundamental limitation), a learned, extractive policy like LRE provides a Pareto-optimal balance of accuracy, cost, and fidelity that current baselines cannot match.