💬 NLP

Cooperative Memory Paging with Keyword Bookmarks for Long-Horizon LLM Conversations

This paper proposes "cooperative paging," a memory management strategy for long-horizon LLM conversations that replaces evicted content with minimal keyword bookmarks and a recall tool, achieving state-of-the-art answer quality on the LoCoMo benchmark while revealing that coarse fixed-size pages and distinctive bookmark specificity are critical for effective retrieval.

Original authors: Ziyang Liu

Published 2026-04-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ziyang Liu

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 having a very long, deep conversation with a brilliant friend (the AI). You've been talking for hours, covering everything from your favorite movies to your peanut allergy and your budget for a new car.

But here's the catch: Your friend has a tiny memory. They can only hold about 20 minutes of conversation in their head at once. As soon as you talk about something new, they have to forget the old stuff to make room.

The Problem:
If you ask, "Hey, remember that peanut allergy I mentioned three hours ago?" and they've forgotten it, they might just guess or make something up. They don't know what they forgot, so they can't ask for help.

The Old Solutions (and why they failed):

The "Guessing Game": Some systems tried to make the AI realize, "Wait, I don't know this!" and then ask for help. But the paper found that AI is too confident. Even when it's missing info, it just makes up a confident-sounding answer. It doesn't know what it doesn't know.
The "Search Engine": Other systems let the AI search through a giant library of past chats. But asking an AI to "search for something vague" is like asking a librarian to "find that book I read once about a thing." It's too hard.
The "Summary": Some systems just summarize the old chat into a short paragraph. But summaries are like reading a movie plot on a napkin; you lose the specific details (like the exact budget or the specific allergy).

The New Solution: "Cooperative Paging with Keyword Bookmarks"

The authors propose a clever system that works like a physical filing cabinet with a "Table of Contents."

1. The "Bookmark" (The Table of Contents)

Instead of deleting old conversations, the system replaces them with a tiny, cheap bookmark.

Old Chat: "User said they are allergic to peanuts, have a budget of $50, and want to meet on Tuesday." (Takes up 200 words of memory).
New Bookmark: [p3: allergy, peanut, budget] (Takes up only 8 words).

The AI sees this list of bookmarks. It's like looking at the spine of books on a shelf. It doesn't know the whole story of page 3, but it knows page 3 is about peanuts and money.

2. The "Recall" Button (The Cooperative Part)

The AI is given a special tool: a Recall Button.

If you ask, "What should I eat for lunch?" and the AI sees the bookmark [p3: allergy, peanut, budget], it thinks: "Oh! I have a bookmark about peanuts and money. I should check that before I guess."
It presses the button, and the system instantly swaps the tiny bookmark back out for the full conversation about the peanut allergy.
Now the AI has the full details and can give you a safe, accurate answer.

Why this is "Cooperative":
The AI doesn't have to guess what it's missing. The system hands it a map (the bookmarks) and says, "Here are the topics we covered. If you need details, just click the right one."

What the Researchers Discovered (The "Secret Sauce")

The team ran thousands of tests and found some surprising things that go against common sense:

1. "Dumb" is Better than "Smart" for Grouping

The Idea: You might think the system should group conversations by "topic" (e.g., put all the "food" talk in one page and "money" talk in another).
The Reality: This actually made things worse. It created too many tiny pages (like 30 tiny sticky notes). The AI got overwhelmed trying to find the right one.
The Winner: Just cutting the chat into big, fixed chunks (e.g., every 20 turns) worked best. It kept the list of bookmarks short and simple.

2. The "Too Much Info" Trap

The Idea: Maybe the bookmarks should be detailed summaries? "Page 3: User is allergic to peanuts and has a $50 budget."
The Reality: No! If the bookmark is too long, the AI gets lazy. It thinks, "Oh, I have enough info right here," and forgets to press the Recall button.
The Winner: Minimal keywords work best. Just [peanut, budget]. It's short enough to say, "I don't have the full story, I need to check," but specific enough to know which story to check.

3. Specificity is King

If your bookmark just says [preferences], the AI is confused. Is it about food? Movies? Cars?
If the bookmark says [vegetarian, rust-programming], the AI knows exactly what to look for. The more specific the keywords, the better the AI performs.

4. The "Revisiting" Problem

In fake, made-up conversations, people usually move forward (Topic A -> Topic B -> Topic C). The best strategy there is to throw away the oldest stuff first.
But in real human conversations, we constantly jump back and forth. "Remember that thing we talked about yesterday?"
The system learned to keep the "frequently visited" pages in memory and only throw away the ones nobody talks about anymore.

The Bottom Line

This paper solves the "long conversation" problem by treating the AI's memory like a library.

Instead of trying to make the AI remember everything (impossible) or summarize everything (lossy), they give the AI a short, punchy index card for every old topic. When the AI needs a detail, it checks the index card, sees the keyword, and asks the librarian (the system) to fetch the full book.

It turns a "memory crisis" into a simple, cooperative game of "Check the Index, then Fetch." And the best part? The simpler the index card, the better the game works.

1. Problem Statement

Large Language Models (LLMs) face a fundamental resource constraint: the context window is finite, while conversation history grows indefinitely. When the context limit is reached, older content must be evicted. Existing solutions suffer from critical limitations:

Self-Diagnosis Failure: Approaches like MemGPT require the model to detect its own information gaps (e.g., via uncertainty signals or NLL spikes). The authors demonstrate that models do not reliably "struggle" when missing context; instead, they often generate confident but incorrect answers with lower perplexity (NLL), making passive fault detection ineffective.
Irreversible Compression: Methods like summarization or "gist" compression permanently lose details, preventing recovery.
Tool-Based Limitations: Systems relying on explicit retrieval calls often require the model to formulate free-form search queries about what it might be missing, which is cognitively demanding and error-prone.

2. Methodology: Cooperative Paging

The authors propose Cooperative Paging, a mechanism inspired by operating system virtual memory but adapted for LLMs. Instead of the model guessing what to retrieve, the system provides a structured index.

Mechanism:
- Segmentation: Conversation turns are grouped into "pages."
- Eviction & Bookmarking: When the context budget is exceeded, the oldest page is evicted from the active context window. Instead of a summary, it is replaced by a minimal keyword bookmark (e.g., [p3: allergy, peanut, budget]), costing only ~8–24 tokens.
- Recall Tool: The model is provided with a recall(page_ids=[...]) tool.
- Recovery: When the model needs specific details, it calls recall(), and the system injects the full original page content back into the context.
Core Insight: The system shifts the cognitive load from "guessing what is missing" to "checking the index." The bookmark acts as a lightweight table of contents, enabling the model to decide when and which page to retrieve.

3. Key Contributions

Cooperative Paging Mechanism: A novel architecture using minimal keyword bookmarks and a recall tool, achieving 90.9% recall accuracy in controlled settings and outperforming baselines on real-world benchmarks.
Paging Design Space Study: The first systematic study of page boundary strategies and eviction policies for in-session LLM conversations using a turn-by-turn simulator (3,176 synthetic probes, 1,600 LoCoMo probes).
Bookmark Design Principles: Discovery that minimal keyword formats (not rich summaries) yield the best accuracy-to-cost ratio. Crucially, keyword specificity is the dominant factor, improving accuracy by 25.7 percentage points compared to generic labels.
Bottleneck Analysis & Mitigation: Identification of the "bookmark bottleneck" (model knows when to recall but often picks the wrong page) and the proposal of two complementary generation strategies (Hybrid and LLM-Batch) to close this gap.

4. Key Results

A. Benchmark Performance (LoCoMo)

Evaluated on the LoCoMo benchmark (10 real multi-session conversations, 300+ turns each) across four models (GPT-4o-mini, DeepSeek-v3.2, Claude Haiku, GLM-5):

Ranking: Cooperative Paging (Bookmark+Recall) achieved the highest answer quality among six tested methods (including truncation, BM25 retrieval, and full context).
Statistical Significance: Outperformed BM25 retrieval with $p=0.017$ (paired bootstrap) and Full Context with $p=0.047$ .
Cross-Model Consistency: The ranking held across all four models, with the largest gains observed on DeepSeek-v3.2 and GLM-5.

B. Paging Design Findings

Page Granularity Dominates: Coarse, fixed-size pages (e.g., Fixed 20 turns) significantly outperform "smart" content-aware strategies.
- Fixed 20: 96.7% accuracy (Synthetic).
- Topic Shift: 56.7% accuracy.
- Reason: Content-aware splitting creates too many small pages (over-fragmentation), diluting the model's attention across too many bookmarks.
Eviction Policies are Data-Dependent:
- Synthetic Data (Forward-moving): FIFO (First-In-First-Out) is best.
- LoCoMo (Revisit-heavy): LFU (Least Frequently Used) is best.
- Gap: B´el´ady's oracle (optimal offline policy) outperforms the best online policy by 8–14 points, indicating room for adaptive online policies.

C. Bookmark Generation & The "Information-Gap Hypothesis"

The Bottleneck: The model triggers recall() correctly 96% of the time but selects the correct page only ~57% of the time. The failure mode is bookmark discrimination (multiple bookmarks look similar).
Format Ablation: Minimal keywords (~24 tokens) are superior to rich formats (text snippets, structured entities).
- Hypothesis: Richer bookmarks give the model a "false sense of sufficiency," causing it to skip the recall step. Minimal bookmarks create just enough uncertainty to trigger retrieval.
Generation Strategies:
- Hybrid (Heuristic + LLM augmentation): Best for synthetic data (+4.4 E2E points).
- LLM-Batch (Single-call cross-page non-overlap): Best for real LoCoMo data (+8.7 E2E points, +50 points on open-domain questions).
- Failure Modes: Strategies like TF-IDF or per-page LLM generation underperformed because they lowered the recall trigger rate, confirming the Information-Gap Hypothesis.

5. Significance and Implications

Paradigm Shift: Moves LLM memory management from "passive compression" or "active guessing" to cooperative indexing. The model is an active agent that uses a provided index rather than a passive consumer of compressed data.
Design Heuristics:
- Simplicity Wins: Coarse-grained, fixed-size paging is more effective than semantic segmentation.
- Specificity > Quantity: High-quality, domain-specific keywords are far more valuable than verbose summaries.
- Incentive Preservation: Any memory system must preserve the model's incentive to retrieve information; over-summarizing defeats the mechanism.
Future Directions: The paper suggests that the next frontier is learned keyword extraction (to solve the discrimination bottleneck) and adaptive eviction policies that switch based on conversation topology (forward vs. revisit-heavy).

In conclusion, the paper demonstrates that effective long-horizon LLM memory does not require complex retrieval systems or perfect summarization, but rather well-designed minimal cues that enable the model to cooperatively manage its own context window.