Technical Summary: Agentic Plan Caching (APC)

Problem Statement

Large Language Model (LLM) based agent applications, which follow a "Plan-Act" paradigm (alternating between reasoning and execution), have demonstrated significant capabilities in complex workflows such as coding, web navigation, and data analysis. However, these applications incur substantial costs and latency due to extensive planning requirements, often necessitating multiple queries to expensive reasoning models.

Existing caching techniques are insufficient for this domain:

• Context Caching (KV Cache): Relies on model-specific internal states that are not transferable across different models or stages of an agent pipeline.
• Semantic Caching: Stores input-output pairs based on prompt similarity. This fails for agents because their outputs are often data-dependent or environment-dependent. For example, the same high-level query ("summarize this dataset") requires different specific actions depending on the dataset's content, or "click the top comment" requires different coordinates depending on the screen state. Conventional semantic caching cannot separate the core intent from dynamic context, leading to high rates of false positives or missed reuse opportunities.

Methodology: Agentic Plan Caching (APC)

The authors propose Agentic Plan Caching (APC), a test-time memory system designed to extract, store, adapt, and reuse structured plan templates from completed agent executions. Unlike traditional methods that cache raw queries or full execution logs, APC focuses on the Plan stage of the agent loop.

System Workflow

1. Keyword Extraction: Upon receiving a new task query, a lightweight language model (e.g., GPT-4o-mini) extracts a high-level keyword or intent (e.g., "working capital ratio") that captures the semantic target of the task, ignoring specific entities like company names or dates.
2. Cache Lookup: The system performs an exact match lookup of this keyword against a cache storing (keyword, plan template) pairs.
   • Cache Hit: If a match is found, a small planner LM (e.g., LLaMa-3.1-8B) adapts the retrieved plan template by injecting current context (e.g., specific company name, fiscal year) to generate a detailed plan.
   • Cache Miss: If no match is found, a large planner LM generates a new plan from scratch.
3. Execution & Adaptation: The generated or adapted plan is passed to an "Actor LM" to execute the task.
4. Template Generation (Post-Execution): Upon successful completion of a task (in the case of a cache miss), the system generates a reusable entry for the cache:
   • A rule-based filter removes verbose reasoning and irrelevant details from the execution log.
   • A lightweight LLM filter strips context-specific elements (entities, numbers) to produce a generalized Plan Template.
   • The associated keyword is extracted and stored alongside the template.

Key Design Choices

• Keyword vs. Query-Based Matching: The authors argue that query-based semantic similarity (using embeddings) is sub-optimal for agents because it overemphasizes context-specific details. Keyword extraction focusing on high-level intent provides a more reliable indicator of reusable plans, reducing false positives and negatives.
• Exact vs. Fuzzy Matching: The system uses exact matching for keywords to ensure low latency and cost. Fuzzy matching was found to introduce significant computational overhead and scalability issues without guaranteed accuracy improvements.
• Template vs. Full History: Instead of caching full execution logs (which small models struggle to process due to length), APC caches distilled, high-quality plan templates that are easier for small models to adapt.

Key Contributions

1. Analysis of Limitations: The paper provides a comprehensive analysis demonstrating why existing context and semantic caching techniques fail in agentic AI scenarios due to model dependencies, data-dependent outputs, and limited adaptability.
2. Novel Caching Paradigm: APC shifts the focus from query-level caching (suitable for chatbots) to task-level caching for agents. It introduces a system that extracts structured plan templates at test-time and adapts them using lightweight models.
3. Empirical Evaluation: The system is evaluated across five diverse agent workloads (including FinanceBench, Tabular Math Word Problems, AIME, and GAIA) and two agent architectures (Minion and Open Deep Research).

Results

Evaluation across diverse benchmarks yields the following average results:

• Cost Reduction: APC reduces agent serving costs by 50.31% compared to the accuracy-optimal baseline (using a large model for all planning).
• Latency Reduction: APC reduces serving latency by 27.28%.
• Performance Retention: The system maintains 96.61% of the optimal application-level accuracy.
• Overhead: The overhead introduced by keyword extraction and cache generation is minimal, accounting for only 1.04% of the total cost on average.
• Robustness: Unlike semantic caching, which suffers significant accuracy drops during cache hits due to false positives, APC maintains consistent accuracy regardless of cache status.

Significance and Claims

The paper claims that Agentic Plan Caching offers a more efficient solution for serving LLM-based agents by complementing existing LLM serving infrastructures. Its significance lies in:

• Decoupling Intent from Context: By separating the core task intent (via keywords) from dynamic environmental data, APC enables the reuse of planning logic across semantically similar but contextually distinct tasks.
• Cost-Effective Scaling: It allows the use of smaller, cheaper models for the planning stage in many scenarios without sacrificing the performance of large models, addressing the high cost barrier of scaling agentic workflows.
• Compatibility: The framework is designed to be compatible with existing agent architectures and can be used jointly with other caching techniques (like KV cache).

The authors note that while the system is effective, it faces a "cold start" limitation where initial performance is lower until the cache is populated, a common trait of test-time caching. They suggest pre-populating caches with offline samples as a mitigation strategy for known workloads.