Skip to content

Agentic Plan Caching: Test-Time Memory for Fast and Cost-Efficient LLM Agents

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Agentic Plan Caching (APC) is a test-time memory system for Plan-Act LLM agents that extracts generalized plan templates from completed executions, matches new requests via keyword retrieval, and uses lightweight models to adapt cached templates—avoiding the full planning cost. Evaluated on five benchmarks, it reduces serving cost by 50.31% and latency by 27.28% while retaining 96.61% of accuracy-optimal performance.

Problem

Existing LLM caching techniques—context caching (KV-cache reuse) and semantic caching (input-output pair reuse)—are designed for stateless chatbot workloads and fail for Plan-Act agents because: (1) KV caches are model-specific and don't transfer across the multiple LLMs in an agent pipeline; (2) agent outputs are data-dependent (vary with external context even for identical queries); and (3) neither approach can adapt cached content to handle minor query variations. The result is that the expensive planning stage is redundantly re-executed for structurally similar tasks.

Method

APC operates as a test-time cache of (keyword, plan_template) pairs:

  1. Keyword extraction: A lightweight model (GPT-4o-mini) extracts a high-level intent keyword from the incoming query (e.g., "working capital ratio"), avoiding semantic embedding similarity which over-weights context-specific tokens.
  2. Cache lookup: Exact dictionary match on extracted keyword (O(1), scales to 10⁶ entries with µs latency).
  3. Cache hit path: A small planner LM (LLaMA-3.1-8B) adapts the retrieved plan template to the current context-specific details, replacing the large planner LM.
  4. Cache miss path: The large planner LM generates a plan normally; upon successful task completion, a two-step process generates a new cache entry—first a rule-based filter strips verbose reasoning from the execution log, then a lightweight LLM removes entity/numeric specifics to produce a reusable generalized template.
  5. LRU eviction manages cache capacity; cold-start can be mitigated by offline pre-population.

Key Contributions

  • Systematic analysis of why context caching and semantic caching are structurally inadequate for Plan-Act agents (model-specificity, data-dependency, limited adaptability).
  • APC framework: keyword-based intent extraction + exact-match retrieval + lightweight template adaptation, distinguished from semantic caching and full-history caching.
  • Demonstration that small LMs (8B) can successfully adapt concise plan templates but fail on raw unfiltered execution logs, motivating the LLM-based template filtering step.
  • Evaluation on five diverse workloads (FinanceBench, QASPER, TabMWP, AIME 2024/2025, GAIA) across two agent architectures (Minion, Open Deep Research).

Results

  • Average cost reduction: 50.31% vs. accuracy-optimal baseline; overhead from keyword extraction + cache generation is only 1.04% of total cost.
  • Average latency reduction: 27.28% on FinanceBench (100-query microbenchmark, 46% hit rate).
  • Accuracy retention: 96.61% of accuracy-optimal performance on average.
  • GAIA (Open Deep Research): 76.42% cost reduction ($69.02 → $16.27) with only 0.61% accuracy drop (37.58% → 36.97%).
  • FinanceBench: APC at $1.86 / 85.50% accuracy vs. accuracy-optimal at $3.57 / 85.50%; full-history caching degrades to 72.00% at $1.99.
  • Semantic caching (threshold=0.9): suffers −46% to −56% accuracy drop on cache hits across datasets.
  • Cache size: diminishing returns beyond cache size ≈ number of unique task keywords; LRU eviction used.
  • Worst-case overhead (zero hit rate): 1.31% of total cost on average.

Limitations

  • Cold start: cache begins empty; early queries incur full large-model cost plus cache generation overhead; pre-population requires knowing the target workload distribution in advance.
  • Low-hit-rate workloads: GAIA's heterogeneous, rarely-recurring tasks limit keyword-level cache reuse during the planning phase (benefit comes mainly from re-planning phases).
  • Exact keyword matching: requires identical extracted keywords for a cache hit; fuzzy matching increases hit rate but degrades accuracy and introduces O(n) lookup latency that scales poorly (10⁵ entries: ~148 ms vs. ~56 µs for exact match).
  • Architecture dependency: evaluated only on sequential Plan-Act pipelines (Minion, smolagents); applicability to more complex multi-agent topologies (parallel branches, dynamic replanning) is unvalidated.
  • Test-time only: templates are extracted at test time; no mechanism for proactive offline template construction beyond manual pre-population.
  • Cache generation latency (~4 s/entry) adds wall-clock overhead on cache misses; parallel cache generation is listed as future work.

Relevance to Agentic AI / LLM Agents

APC directly targets the serving-efficiency bottleneck of deployed LLM agents, a problem that becomes acute as agents are used in production at scale—the planning stage dominates cost and latency in ReAct-style loops precisely because it requires the most capable (and expensive) models. The keyword-based intent abstraction is a concrete mechanism for separating task structure from task context, which is a fundamental challenge in agent memory and reuse. The work complements capability-focused agent memory research (MemGPT, Reflexion-style agents) by showing that the same "store and retrieve past executions" principle can be optimized for cost reduction rather than accuracy improvement. For researchers tracking agentic AI, APC establishes a clean baseline and design space (keyword granularity, template abstraction level, small-LM adaptation) for test-time efficiency that is orthogonal to—and composable with—model distillation, KV-cache reuse, and speculative decoding.