SideQuest: Model-Driven KV Cache Management for Long-Horizon Agentic Reasoning

SideQuest is a novel model-driven approach that leverages a Large Reasoning Model to perform parallel KV cache compression by reasoning about token utility, significantly reducing memory usage in long-horizon agentic tasks while maintaining accuracy and outperforming existing heuristic methods.

The Gist

The Problem: The "Endless Notebook"

Imagine you are a brilliant detective (the AI) trying to solve a complex mystery. To do this, you have to read hundreds of documents, visit many websites, and talk to different witnesses.

In the past, AI models worked like detectives with a single, infinite notebook. Every time they read a clue, they wrote it down. The problem? As the investigation got longer, the notebook became so heavy and thick that:

1. It got too heavy to carry: The computer's memory (RAM) filled up, slowing everything down.
2. It got hard to find things: The detective had to flip through thousands of pages just to find the one clue needed for the next step.

Existing solutions tried to fix this by using rigid rules (heuristics). For example, a rule might say, "If a page hasn't been looked at in 10 minutes, throw it away."
The flaw: In a complex investigation, a clue you ignored 10 minutes ago might suddenly become the most important piece of evidence in the next step. Throwing it away based on a simple timer causes the detective to miss the solution.

The Solution: SideQuest (The "Sidekick" Detective)

The authors propose SideQuest, a new way to manage memory. Instead of using a rigid rulebook, they give the AI a specialized sidekick (an auxiliary thread) that runs in parallel to the main detective.

Here is how it works, step-by-step:

1. The Main Detective vs. The Sidekick

• The Main Thread: This is the AI solving the user's problem (e.g., "Find the first long weekend after GTC 2026"). It is busy searching, reading, and thinking.
• The Sidekick (SideQuest): This is a second, parallel version of the AI. It isn't trying to solve the mystery. Its only job is to look at the detective's notebook and ask: "Which of these papers are now useless trash?"

2. The "Memory Management Mode"

Every few steps, the system pauses the main detective just enough to let the Sidekick take a quick look. The Sidekick enters a special mode (triggered by a phrase like "Memory management mode").

It analyzes the context with the same intelligence as the main detective:

• "Oh, we found the GTC dates in Document A. We don't need the search results page anymore. Let's throw that away."
• "But wait, we still need Document B because we have to cite it in the final answer. Keep that."

3. The Cleanup

Once the Sidekick decides what to delete, it sends a command to the system to physically remove those pages from the notebook.

• Crucial Point: The Sidekick does this without writing its own thoughts into the main detective's notebook. This keeps the main notebook clean and focused on the actual problem, not on the act of cleaning.

Why This is a Game-Changer

1. It's Smart, Not Stupid
Old methods were like a janitor who sweeps up everything that hasn't been touched in an hour. SideQuest is like a smart assistant who understands the story. It knows that a document might be boring right now but vital later. It only deletes what is truly "stale."

2. It Saves Massive Space
In their tests, SideQuest reduced the memory needed by up to 65%.

• Analogy: Imagine you are packing for a trip. Instead of bringing your entire house (the full history), SideQuest helps you pack only the clothes you need for the next leg of the journey, while knowing exactly what to bring back for the final destination.

3. It Doesn't Slow You Down
Because the Sidekick runs in parallel and the AI is already very fast at reasoning, the "cost" of asking the Sidekick to clean up is tiny. The result? The AI can handle much larger, more complex tasks without crashing or slowing down.

The Result

The paper shows that with just a tiny bit of training (using only 215 examples), the AI learned to be its own garbage collector.

• Accuracy: It didn't get dumber; it stayed almost as accurate as if it had kept everything.
• Speed: It became much faster because it wasn't dragging a heavy, useless notebook around.
• Reliability: It stopped making mistakes caused by "forgetting" important clues that simple rules would have deleted.

Summary

SideQuest turns memory management from a rigid, dumb rule into a smart, reasoning skill. It gives the AI a "Sidekick" that constantly cleans up the workspace, throwing away old, useless papers while keeping the important ones, allowing the AI to solve long, complex mysteries without running out of room.

Technical Summary

1. Problem Statement

The shift from static conversational LLMs to autonomous agentic systems (e.g., deep research, automated software engineering) has created a new memory bottleneck. Unlike single-turn tasks, agents perform multi-hop reasoning over distributed information, causing the context window to grow to hundreds of thousands of tokens.

• The Bottleneck: The Key-Value (KV) cache grows linearly with sequence length, consuming massive GPU memory and becoming memory-bandwidth bound during decoding.
• Limitations of Existing Solutions: Current KV cache compression techniques (e.g., H2O, Scissorhands, SnapKV) rely on fixed heuristics (e.g., retaining "heavy hitters" or local clusters). These methods fail in agentic reasoning because:
  • Dynamic Utility: A token's importance is non-monotonic. Information irrelevant at step $t$ may become critical at step $t+n$.
  • Premature Pruning: Heuristics often discard vital context too early, leading to reasoning failures that are difficult to debug.
  • Static vs. Dynamic: Heuristics assume a static corpus, whereas agentic contexts evolve dynamically through tool calls and internal reflection.

2. Methodology: SideQuest

SideQuest proposes a paradigm shift from heuristic-based pruning to model-driven, semantic-aware memory management. Instead of using fixed rules, the Large Reasoning Model (LRM) itself decides which parts of its context to evict.

Core Architecture

The system operates using a Shared-Context Parallel Reasoning architecture:

1. Main Thread: Executes the primary agentic task (ReAct framework: Reasoning $\to$ Tool Call $\to$ Observation).
2. Auxiliary Thread: Periodically spawned in parallel to the main thread. It shares the same KV cache context but operates under a specific trigger.
   • Trigger: A distinct phrase (e.g., **Memory management mode**) is appended to the auxiliary thread's input.
   • Task: The model analyzes the current state of the reasoning loop and the history of tool outputs (cursors) to identify "stale" information.
   • Output: The auxiliary thread generates a structured command (e.g., {del_cursors: [0]}) to evict specific tool responses that are no longer needed.
3. Synchronization: The system waits for the main thread to complete its current turn before applying the eviction, ensuring the management tokens do not pollute the main reasoning context.

Training Strategy

To teach the model this capability without degrading its general reasoning skills, the authors use a hybrid training pipeline:

• Data Synthesis (Hindsight Analysis): They run a base model on web-browsing tasks. For correct traces, they calculate the "last-use index" for every tool output.
• Dual-Objective Training:
  • Main Traces (Distillation): The original correct traces are used with logit distillation loss to ensure the model retains its core reasoning capabilities.
  • Auxiliary Traces (Cross-Entropy): The model is trained on sequences where it must identify expired cursors and output deletion commands. These traces are generated by masking out tokens corresponding to "stale" cursors and prompting the model to explain why they are obsolete.
• Efficiency: The model is fine-tuned using LoRA on a small dataset (215 high-quality samples) but achieves robust performance.

3. Key Contributions

1. Empirical Evaluation of Heuristics: Demonstrated that static importance metrics fail to capture the dynamic, non-monotonic utility of tokens in multi-step agentic workflows.
2. Model-Driven Memory Management: Introduced SideQuest, a framework where the LRM actively manages its own context via self-referential reasoning, allowing for precise, semantic-aware eviction.
3. Parallel Auxiliary Architecture: Proposed a novel design where memory management is an auxiliary task running in parallel. This prevents management tokens from cluttering the primary context window while maintaining a lean KV cache.
4. Scalable Training Pipeline: Developed a data synthesis method using hindsight analysis to generate high-quality supervision for memory management without expensive human annotation.

4. Experimental Results

The authors evaluated SideQuest on FRAMES (Wikipedia-based multi-hop reasoning) and BrowseComp (complex web navigation) benchmarks using the gpt-oss-20b model.

• Memory Efficiency:
  • Reduced Peak Token Usage by 56–65% compared to the uncompressed baseline.
  • Reduced KV Cache Memory Reads by 53–71%, directly alleviating memory bandwidth bottlenecks.
• Accuracy & Reliability:
  • Minimal Accuracy Degradation: Only a ~2% drop on in-distribution data (FRAMES) and ~5% on out-of-distribution data (BrowseComp).
  • Superior to Heuristics: Heuristic baselines (H2O, SnapKV, R-KV) suffered significant accuracy drops and high "non-completion" rates (model collapse) at similar compression levels.
  • Robustness: SideQuest maintained a near-zero failure rate comparable to the uncompressed baseline, whereas heuristics frequently produced unparsable responses due to critical token loss.
• System Throughput:
  • In a production setting (SGLang on NVIDIA H100), SideQuest increased system throughput by 83.9% (1,523 tok/s vs. 828 tok/s) by enabling larger batch sizes.
  • Reduced total benchmark runtime by 36.8%.

5. Significance and Future Work

• Paradigm Shift: SideQuest moves memory management from a fixed constraint to a learnable reasoning skill. It eliminates the need for manual token budgeting, allowing the agent to adaptively scale context size based on instantaneous task complexity.
• Generalizability: While tested on web browsing, the architecture is domain-agnostic. The authors suggest applying this to coding agents (pruning irrelevant file contents) or safety/governance tasks (running parallel safety checks without separate guardrail models).
• Limitations: Current implementation focuses on evicting tool responses; it does not yet prune the agent's own intermediate reasoning steps (thought tokens). Future work aims to extend this to thought pruning and scaling the training dataset to further close the accuracy gap.

Conclusion: SideQuest establishes a new standard for efficient long-context agentic inference, proving that intelligent, model-driven garbage collection significantly outperforms static heuristics in complex, multi-step reasoning tasks.