Agentic Plan Caching: Test-Time Memory for Fast and Cost-Efficient LLM Agents
Authors: Qizheng Zhang
Michael Wornow
Kunle Olukotun
Venue: NeurIPS 2025 poster ()
Keywords: Caching
Memory
Serving
LLM Agents
Primary area: infrastructure

Abstract: LLM-based agent applications have shown increasingly remarkable capabilities in complex workflows but incur substantial costs and latency due to extensive planning and reasoning requirements. 
Existing LLM caching techniques (like context caching and semantic caching), primarily designed for serving chatbots, are insufficient for agent applications where outputs depend on external data and environmental contexts. 
We propose **Agentic Plan Caching (APC)**, a novel **test-time memory** that extracts, stores, adapts, and reuses structured plan templates from planning stages of agent applications across semantically similar tasks to reduce the cost and latency of serving. 
Unlike traditional semantic caching, our system extracts plan templates from completed agent executions at test-time, employs keyword extraction to match new requests against cached plans, and utilizes lightweight models to adapt these templates to task-specific plans with contexts. 
Evaluation across multiple real-world agent applications shows that our system can reduce costs by 50.31\% and latency by 27.28\% on average while maintaining performance, offering a more efficient solution for serving LLM-based agents that complements existing LLM serving infrastructures.

Agentic Plan Caching: Test-Time Memory for Fast and Cost-Efficient LLM Agents
Qizheng Zhang
Michael Wornow
Kunle Olukotun
Stanford University
Abstract
LLM-based agent applications have shown increasingly remarkable capabilities in complex workflows but incur substantial costs and latency due to extensive planning and reasoning requirements. Existing LLM caching techniques (like context caching and semantic caching), primarily designed for serving chatbots, are insufficient for agent applications where outputs depend on external data and envirommental contexts. We propose Agentic Plan Caching (APC), a novel test- time memory that extracts, stores, adapts, and reuses structured plan templates from planning stages of agent applications across semantically similar tasks to reduce the cost and latency of serving. Unlike traditional semantic caching, system extracts plan templates from completed agent executions at test-time, em- ploys keyword extraction match requests against cached plans, and utilizes lightweight models to adapt these templates to task-specific plans with contexts. Evaluation across multiple real-world agent applications shows that our system can reduce costs by 50.31% % and latency by 27.28% on average while maintaining performance, offering more efficient solution for serving LLM-based agents that complements existing LLM serving infrastructures.
Introduction
Agent applications based on Large Language Models (LLMs) have shown early promise in replicating human performance on broad range workflows, from coding (26
28 61 to web navigation [23]
70 to open-ended research [ to social interactions [42 57 Many of these LLM-based agents follow a two-stage pipeline, often referred to as the ReAct-agent loop
that alternates between: (1) Plan reasoning about what to do next, and (2) Act executing those plans. While effective, these agents incur significant costs due to the complexity of exccuted workflows [67 31] and need to interact with external tools and environments [3). Specifically, the Plan stage is often implemented via test-time compute techniques 13 47
63 45,,
like chain-of-thouse
reasoning [53], which
require numerous LLM queries and access to expensive LLMs (e.g., reasoning models). This
results in substantial costs for executing agentic workflows via APIs 15 39 or locally [35].
To reduce LLM costs, methods have been developed optimize responses to individual queries 33 69). In particular, caching has emerged as a popular approach, with two primary implementations: Context caching (e.g., KV cache reuse and prompt caching (20
66
62 stores internal model states
stores and reuses (input, output) pairs to accelerate the serving of queries that similar historical queries.
to speed up subsequent generations, while semantic caching [10 46 2
These caching techniques, however, have significant limitations when applied to Plan-Act agents. These agents often require making data-dependent decisions, i.e., L.M outputs depend on external data or contextual information that varies between runs. For example, in data analysis applications, the same high-level query ("summarize key statistics of this dataser") will result in similar high-level plans, but different specific details depending on the characteristics of the dataset provided. Similarly,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

in web or GUI navigation tasks, the same high-level query ("delete the top comment") will require similar sequences of actions (e.g. "click the menu button, scroll down"), but the specifics may differ depending on screen size and window position (e.g, "click coordinates (130, 493), scroll down 38 pixels"). In such cases, conventional caching fails because it does not separate the core intent of the query from the dynamic context. Agents may benefit from local (i.e., individual query-level) optimizations, but miss opportunities for global improvements that leverage patterns across the entire task execution.
To overcome these limitations, we propose Agentic Plan Caching (APC), a novel test-time memory that reduces the serving costs of LLM- based agents that follow the Plan-Act paradigm by adapting and reusing prior execution plans across semantically similar workflows. Our key insight that the Plan stage, which incurs the majority of LLM compute cost, is often repeated (within or across workflows) despite yielding outputs that could be reused in future requests while maintaining performance. When an agent completes an execution of a workflow, we extract structured plan templates from the agent execution log. When a similar request arrives, we employ keyword extraction identify the most important semantic target of the query, then match it against the cache to retrieve the most relevant plan template. Our approach differs from semantic caching by avoiding query-based cache lookups, which we found sub-optimal for agent applications. Whenever additional planning is required, we utilize a lightweight model to adapt the cached structured plan template into more detailed plans with lask-specific contexts (e.g., fiscal year and company name in financial data-intensive reasoning (39 rather than employing an expensive model.
Although several memory architectures have been proposed to help agents store and learn from past experiences 44 40 51 59 (5), these efforts primarily focus on using such memories to improve the agent's s accuracy on completing workflows (e.g., with fewer hallucinations [9] or with higher task success rate (51)) rather than to reduce the cost of serving the agent. To our knowledge, the use of historical experiences to more efficiently serve LLM-based agents remains underexplored, particularly for applications where outputs depend on input data or environmental conditions external to the query itself.
We evaluate agentic plan caching on five diverse agent workloads and find that reduces costs by 50.31 % and latency by 27.28 % (on average) while maintaining 96.61 % of optimal accuracy. The agentic plan caching we propose is compatible with existing LLM serving and agent frameworks, and can be used jointly with existing caching techniques as well.
In summary, we make the following contributions:
1. Analysis of Caching Techniques for Serving LLMs:
We conduct a comprehensive analysis of existing caching techniques for LLM serving (context caching and semantic caching), and point out why they are insufficient for the era of agentic Al applications.
2. Proposal of Agentic Plan Caching: We propose the idea of agentic plan caching, which shifts the focus from query-level caching (suitable for chatbots) to task-level caching (targeting L.-M-based agents). We design and implement a novel caching system that extracts, stores, adapts and reuses agent-generated plans test-time.
3. Evaluation of Caching Techniques: We evaluate our agentic plan caching system on top of real- world agent architecture and five datasets/benchmarks and find that our approach can reduce cost by 50.31 % and latency by 27. 27.28% (on average), while maintaining 96.61 % of optimal application performance.
Background and Motivation
2.1 Plan-Act Agents
The rise of large language models (LLMs) has driven the rapid expansion of agentic AI applications. Unlike single-model tasks like chatbots [17], math [24), or coding [16), these applications coordinate multiple models and queries to solve complex tasks, like data-intensive reasoning [3)], software engineering [64] [2], web navigation [70], etc.
Many such agentic AI applications, like multi-agent systems 50
22 and cloud-edge LLM sys-
tems [66] 39 follow a two-stage pipeline loop (similar to the ReAct-agent loop (63),, as shown in
Figure la (1) Plan and (2) Act. In the Plan stage, planner LLM generates a strategy (e.g., task
2

---

decomposition, information retrieval) that guides subsequent actions of acting LLMs. In the Act stage, the actor LLM acts accordingly based on devised plans and external context environment, and passes down the response to the planner LLM for the next step.
However, due the of multiple L.Mss and queries, especially with advanced models like reasoning or multimodal LLMs, these agentic applications can incur significant costs [30] 41] particularly in terms of token ingestion/generation.. Optimizing these costs is crucial for scaling agentic AI applications.
Context
Costco Corporation consolidated balance sheets...
Context Caching
Cache
Input
LLM
Output
Query
is working capttal ratio for Costro?
Semantic Caching
Planner LM
First, provide the total current assets and total ournent liabiltiies FY2019.
Input
LLM
Output
Plan
Actor LM
Plan Caching
Response
Costoa's total current assets were $23,485
LLM Agent
Planning
Plan
Acting Stape
Input
Output
Output
ratio 1.01
Stage
Context
(a) Plan-Act LLM application
(b) Comparison of different LLM caching techniques
Figure 1: Plan-Act LLM Applications and Caching Techniques. (a) A typical Plan-Act agent pipeline loop and (b) a comparison of LLM caching methods, with cached components highlighted in yellow.
2.2 LLM Caching: Methods and Limitations
Caching one of the most
techniques for reducing the serving cost of LLM
applications. The goal of caching is to eliminate redundant computation. Context caching (20 62 60
[88. also known as KV cache reuse or prompt caching, involves storing and reusing the key-value pairs generated during the prefill phase of LLM inference. Semantic caching [10] 46 2 on the other
hand, stores input-output pairs of previous LLM invocations. This relies on the fact that many prompts share similar underlying intents and thus expected outputs despite having different wording [46).
We find that existing caching techniques, primarily designed for serving chatbots (at query-level) instead of agents (at tesk-,evel), have three major limitations as described below.
1) Model-Specific Constraints. Context caching relies on KV cache as the medium for storing and reusing knowledge [34] 20, (60) These KV caches are inherently model-dependent and not easily transferable across different models [56, 33). since
identical text prompts produce model-specific KV caches. While this limitation is negligible for chatbots that consistently use a single model with the same system prompt, becomes problem for agentic Al applications that typically employ multiple LLMs across various processing stages.
2) Data- Dependent Outputs. Semantic caching stores input-ouiput pairs from previous LLM calls, assuming outputs depend solely on input prompts [1O, 44). While this holds for chatbots, many agentic AI applications
data-dependent: Outputs depend not only on input queries but also on external data (e.g., data-intensive reasoning (39]) or dynamic environments (e.g., web or GUI agents [70] [55] (4)). This dependency complicates the reuse of cached responses even when input prompts are semantically similar.
3) Limited Adaptability. Both context and semantic caching lack flexibility for handling slight variations input. Context caching requires exact text matches. Semantic caching, while more accommodating, does not capture the transformation process from prompt to response. This could hinder adaptation similar queries with minor differences (e.g., numeric values or variable names in mathematical reasoning [18), coding tasks (26)), common challenge in agentic AI.

---

2.3 Related Work
Agent Memory Prior work has explored augmenting LLM agents with external memory (1) reduce hallucinations through context-aware responses 9 and (2) enable complex, long-horizon tasks [5T]. Some studies focus on defining memory formats 63 and managing memory efficiently [40 [59] While our caching system can be adapted as a form of agent memory, it diverges by targeting serving cost reduction rather than enhanced capability, a largely unexplored area.
LLM Serving Engines Existing LLM serving engines like vLLM 32 and SGLang 69 optimize general query inference at scale through techniques such as KV cache management and request scheduling. Our approach is compatible with these systems, extending their capabilities to incorporate cost-effective caching for agentic AI scenarios.
is a problem-solving paradigm where new plans are produced by adapting previously solved cases rather than constructing plans from scratch. By exploiting similarities between past and current situations, CBP supports efficient plan reuse, continual learning, and incremental refinement. While work shares the high-level intuition of "plan storage and reuse", it targets a fundamentally different setting from classic symbolic CBP: LLM-based, neural agents performing open-ended natural-language actions. Specifically, system (1) automatically extracts reusable plan templates at test time from unconstrained LLM generations, instead of relying on hand-crafted symbolic plans, and (2) leverages these stored plans for cost-efficient inference LLM agents.
Case-Based Planning Case-Based Planning (CBP)
3 The Agentic Plan Caching (APC) Framework
In this section, we provide an end-to-end overview of our agentic plan caching framework ($.. and then discuss the motivations behind key design choices ( ($..))
3.1 Overview of System Design
Query
Query
"What FY2019 working capital ratio for Costco?"
Keyword
Plans Responses + Output
Cache
"plan_3" "provide totel
(Keyword, Templote)
total abiliies
"resperou assess 525 stacement
Cache Hit
Cache Miss
millon; current $23,137 millin..
"p
Plan Template
Cache Update
LLM-based Filter
Small LM
Large LM
Plan
Plan
Keyword "working capital ratio"
Actor LM
Context
Actor LM
Plan Template
Response
Response
"rerponse_"" "ropectedi (1)
Output
Output
"plan, 5"
(a)
(b)
(c)
Figure 2: Agentic Plan Caching Framework. We show: (a) cache hit workflow, (b) cache miss workflow, and (c) plan template generation for new cache entries.

---

We provide an end-to-end overview of the agentic plan caching framework in Figure 2 The process begins with a cost-effective language model (e.g.. GPT-40-mini) extracting keyword that captures the higher-level intent of the input task query (e.g.. "compute the average of all numbers listed in an external document" " + "mean calculation "). This keyword is then used to search the plan cache, which stores (keyword, plan template) pairs, potentially resulting in a cache hit or miss.
For cache hit - Figure a small planner LM ("Small LM") adapts the retrieved plan template for the current execution by incorporating context-specific information (e.g,, user information, environment variables). For a cache miss - Figure 2 b) -. large planner LM ("Large LM") generates a new plan from the imput task query. The adapted or generated plan, along with the task context (e.g., external data or web/GUI environment), is then passed to the "Actor LM", which produces a response. The response is evaluated by the "Planner LM" to determine if further iterations are needed. If the task is complete, the final output is generated, concluding the agent's 's execution.
In the case of a cache miss, once the agent successfully completes execution with correct outputs, the system generates plan template that can be reused in future invocations of the agent through the following two-step process: (1) A rule-based filter extracts critical information from the execution log while discarding irrelevant details, such as verbose reasoning steps; (2) A lightweight LLM-based filter removes context-specific elements (e.g., entity names, numeric values), producing a generalized template ("Plan Template") and relevant keywords for caching (Figure (F)gure(cc)).
Additional algorithmic details are provided in the Appendix.
3.2 Design Choices
Why Keyword Extraction? common method for identifying similar queries in cache is to assess semantic or textual similarity, as seen in frameworks like GPTCache [10] which use embeddings for similarity searches. However, we find that query-based similarity matching. despite its popularity, is insufficient for detecting cache hits/misses for agentic plan caching. This is because might overemphasize context-specific details (e.g,, names of individuals or companies) rather than the broader intent of queries, which makes it difficult to establish an effective similarity threshold [46). This often results in a high number of false positives (irrelevant cache hits) or false negatives (missed reuse opportunities). In contrast, extracting keywords that reflect the higher-level intent of queries provides a more reliable indicator of whether two queries would result in similar agentic plans, as illustrated in Figure
Query-Based (threshold=0.7)
Query-Hased (threshold=0.8)
Query-Based (threshold=O..
Keyword-Based
1.0
0.5
0.0
False Positive Rate
False Negative Rate
Figure 3: Query-Based v. Keyword-Based Cache Search. Keyword-baser cache search achieves lower levels of false positive and false negative rates than query-based similarity cache search across different thresholds. This suggests that semantic similarity of queries alone may not effectively capture shared task intents and reusable plans.
Exact Matching v. Fuzzy Matching Our system uses exact matches (between keywords) to minimize false positives. While fuzzy search (2) (identifying cache hits based on similar but not identical keywords) could handle approximate key similarities and is feasible to integrate, we opted against and leave for future exploration for two main reasons: (1) Determining fuzzy matches based on semantic or textual similarity of keywords would reintroduce challenges faced by semantic caching, such as setting effective similarity thresholds, and (2) although lightweight LMS could potentially enable fuzzy matching, cache lookups must remain fast and cost-effective, particularly
5

---

in low-hit-rate scenarios. We present an in-depth analysis of the overhead and scalability of fuzzy matching $4.4
Caching Plan Template v. Caching Full Execution History One naive approach reuse historical experience is to cache and reuse past agent execution logs (containing all inputs and outputs from planner and actor LMs) as in-context learning examples for the small planner LM. However, in our experiments ($4.2), we find that small planner LMs, usually based small language models (e.g., we use L.-.M-3.. 1-88), struggle to handle long-context and unfiltered agent execution logs even when containing reusable plan information. This motivates high-quality plan templates, and re-adapt them so that small planner LMS can better take advantage of their information.
filter agent execution logs into
4 Results and Evaluation
We evaluate our agentic plan caching (APC) framework on five agent workloads that span diverse range of data-intensive reasoning and agentic capabilities. These include long-context data reasoning (FinanceBench [25]. QASPER [19]), mathematical reasoning (Tabular Math Word Problems [36].
AIME 2024 and 2025 (37), and multi-step agentic reasoning and tool use (GAIA 38
Our key findings are:
Reduced Cost: APC reduces agent serving costs by an average of 50.31% % ($4.2
Reduced Latency: APC reduces agent serving latency by an average of 27.28% ($4.3).
High Accuracy: APC maintains 96.61% % of application-level performance compared to the
accuracy-optimal baseline ($4.2).
Low Overhead: On average, keyword extraction and cache generation account for only 1.04% of the overall cost of running each benchmark ($4.3)
4.1 Experiment Setup
Our agentic plan caching system is built on the Minion architecture (Figure Ta from the Minions project [39], sequential Plan-Act LLM framework that can be readily generalized. The Minion architecture is composed of a large (cloud-hosted and smaller (locally hosted) actor LM with access to additional context for plan execution. Given a task query, the planner LM and the actor LM collaborate iteratively (as in Figure Lab to produce final output. We set the maximum number of iterations to be 10.
planner LM for reasoning and task decomposition
While we adopt this architecture for clarity, APC is not restricted to Minion-like like agent architecture; we demonstrate integration into other agent architectures and report end-to-end results in $4.2 Additional implementation details and dataset specifications are provided in the Appendix.
Evaluation Metries We assess application-level performance using GPT-4o the evaluation model, as LLM-based evaluation more effective than exact matches or Fl scores for numeric evaluation and long- fong-form responses [14] 21 68) Cost is calculated based on input/output tokens and the latest API pricing from commercial LLM providers (OpenAl API 77) and TogetherAl API (I). Additional details evaluation models, prompts, and API pricing included in the Appendix.
Language Models For the main results 4.2 we use GPT-4o [5] as the planner LM and LLaMa- 3. 1-B [6] as both the small planner LM and actor LM. For keyword extraction and cache generation, we use GPT-4o-mini ( To demonstrate broader applicability, we include sensitivity analysis with a wider range of models in the Appendix.
Baselines
We evaluate our system against the following baselines:
Accuracy-Optimal: No caching is applied. The large planner LM is always used to establish the best achievable application performance.
Cost-Optimal: No caching applied. The small planner LM is consistently used assess the lowest possible cost.

---

Semantic Caching: We implement query-level semantic caching method based on previous work [TO 46]. Following the approach of GPTCache [T] we cache and reuse responses to individual queries, determining cache hits based on query-level similarity. We set similarity thresholds to 80%, %,,,, and 90%; a lookup considered a hit if the query-level similarity is above this threshold.
Full-History Caching (discussed in 3.2 Inspired by knowledge caching in retrieval-augmented generation [62] 29], this baseline caches the complete agent execution log, including inputs and outputs of all LLM agent components. Cache hits are determined by keyword-level similarity. Upon a hit, the cached execution log is used as an in-context example for the small planner LM to generate new plans.
4.2
Main Results
As shown in Figure and Table[] agentic plan caching reduces cost by 50.31% average while maintaining 96.61 % of application-Ieve performance compared to the accuracy-optimal baseline.
We note that:
Semantic Caching: Despite savings lower similarity thresholds, semantic caching suffers from a high rate of false- salse-positive cache hits, leading to substantial performance degradation. Additional case studies of false-positive hits provided in the Appendix.
Full-History Caching: While full-history caching preserves past plans and actions that might help plan generation for similar tasks, underperforms agentic plan caching in accuracy (72.00% vs. 85.50% in FinanceBench) and incurs higher costs ($1.99 vs. $1.86). This is due the small planner LM's difficulty in processing lengthy and unfiltered histories, emphasizing the necessity of LLM-bbsedd filter extract concise, reusable plan templates.
FinanceBench
TabMWP
0.9
Accuracy
0.7
0.5
0.3
0.1
3
0
4
2 Cost (USD)
Cost (USD)
Accuracy/Cost Optimal
Full History Caching
Semantic Caching
Agentic Plan Caching (Ours)
Figure 4: Results across Four Baselines and Agentic Plan Caching.
Results on GAIA with Open Deep Research Agent Beyond Minion-based architectures, we integrate APC into the Open Deep Research agent from the Hugging Face smolagents library [44 using GPT-4o as the large planner LM and GPT-4o-mini as the small planner LM. As shown in Table I. on the GAIA benchmark (38), APC achieves a 76.42% reduction cost (from $69.02 $16.27) with only a 0.61% 1% drop in accuracy (37.58% to 36.97%), demonstrating strong cost-efficiency even complex, open-domain agent settings.
closer analysis reveals that GAIA's heterogeneous task space, ranging from video dialog reason- ing to sales computation, limits the effectiveness of keyword-basee cache retrieval, as many task descriptions are highly specific and rarely recur. Despite fewer cache hits during initial planning,
We do not use the official GPTCache release as it (1) lacks support for Post-GPT-4 OpenAl models and (2) relies deprecated version of the OpenAl APL.
7

---

Minion
Open Deep Research
Method
QASPER
AIME 2024
AIME 2025
GAIA
Cost./ / Accuracyt
Cost| Accuracyt
Cost./ Accuracyt
Cost./ / Accuracyt
Aecuracy-Optimal
$2.14 / 58.00%
S1.14 64.52%
$1.34 / 61 61.29%
$69.02 37.58%
Cost-Optimal
$0.21 / 53.00%
S0.65 48.39%
$0.60 / 48.39%
$3.16 19.39%
APC (Ours)
$0.78 57.00%
S0.85 61.29%
$0.81 58.06%
$16.27 36.97%
Table I: More Results. We evaluate APC on diverse set of benchmarks covering reasoning and agentic capabilities, as well as agent architecture like Minion and Open Deep Research.
APC improves efficiency in re-planning phases by reusing prior plan structures, thereby reducing redundant large-model invocations.
Cache-Miss Cache-Hit Accuracy To assess the impact of caching application performance, we compare cache-miss and cache-hit accuracy across semantic caching, full-history caching, and agentic plan caching (Figure 5). For semantic and full-history caching, cache-hit accuracy is sig- nificantly lower than cache-miss accuracy, indicating performance trade-off despite potential cost savings. In contrast, agentic plan caching maintains consistent aceuracy regardless of cache-use status, demonstrating its ability to preserve application performance without degradation.
Miss
Cacbe
Cacbe
Miss
Cacbe
Accuracy (%)
-32%
75
-46%
75
-1%%
75
Accuracy
Accuracy
50-
25
Pmanceeeench
'TaMWWP
Pmanceelench
TabMWP
Pmancellench
TabMWP
(a) Semantic caching
(b) Full-history caching
(c) Agentic plan caching
Figure 5: Accuracy Comparison across Caching Methods. While semantic caching with thresh- old=0.9 in (a) and full-history caching in (b) experience notable accuracy drops during cache hits, agentic plan caching in (c) maintains stable performance across datasets.
4.3 Cost and Speed Analysis
Cost Breakdown We analyze the additional overhead introduced by the agentic plan caching mechanism through a cost breakdown analysis (Table On average, keyword extraction and cache generation account for only 1.04% of the total cost. This minimal overhead is achieved because: (1) extracting higher-level goals or intents from task queries can be effectively handled by lightweight models the scale of GPT-4o-mini or smaller, and (2) cache generation leverages rule-based methods to extract templates and uses a lightweight language model only for filtering out query-specific or context-specific details, which a task well-suited to compact models.
Worst-Case Cache Overhead We assess the overhead incurred under the worst-case scenario, where the cache hit rate is zero. As shown Table [ even in this scenario. the cost from keyword extraction and cache generation is minimal (1.31% % on average). In practical deployment, potential mitigation strategy dynamically disable caching when hit rates remain persistently low.
Latency Analysis We evaluated the wall-clock latency of our system and compared it to both accuracy-optimal and cost-optimal baselines. Additionally, we provide a detailed breakdown of latency incurred by each component in our plan caching pipeline. This microbenchmark is based on 100 randomly sampled queries from FinanceBench dataset, with a cache hit rate 46% (i.e., cached plans were used for 46 of the 100 queries). As shown in the Table 3 APC reduces end-to-end latency by 27.28 27.28% on this workload. Most of the additional latency our system comes from LLM LLM-powered cache generation, which takes average of 3.99 seconds per entry. To further

---

FinanceBench
TabMWP
Component
Main Results
Worst Case
Main Results
Worst Case
Large Planner LM
$1.7544 (94.17%)
$3.9227 (97.36%)
$1.9823 (97.76%)
$3.3292 (98.33%)
Small Planner LM
$0.0168 (0.9058)
$0.0095 (0.47%%
Actor LM
$0.0705 (3.78%)
50.0529 (1.31%)
$0.0170 (0.84%)
50.0128 (0.38%)
Cache Overhead
$0.0213 (1.15%)
50.0535 (1.33%)
$0.0190 (0.93%)
$0.0438 (1.29
Keyword Extraction
$0.0050 (0.27%)
50,0050 (0.13%)
$0.0025 (0.12%)
S0.0025 (0.07%)
Cache Generation
$0.0163 (0.88%)
S0.0485 (1.20%)
$0.0165 (0.81%)
50.0413 (1.22%)
Total
$1.8630 (100%)
$4.0291 (100%)
$2.0278 (100%)
$3.3858 (100%)
Table 2: Cost Analysis. We show the breakdown of agentic plan caching costs, including main results and worst-case overhead (i.e., zero cache hit rate).
Method
Plan
Act
Keyword Extraction
Cache Lookup
Cache Generation
Total
Accuracy-Optimal
1813.41
94.39
1959.24
Cost-Optimal
856.75
93.31
1004.79
APC (Ours)
1011.82
131.44
42.29
215.80
1424.82
Table 3: Latency Analysis. Breakdown of wall-clock latency across components of the agent pipeline. All values are measured in seconds.
mitigate this overhead, we (I) automatically disable caching when the hit rate is consistently low, and (2) are actively exploring optimizations such parallel cache generation and speculative next-query inference as part of future work. To summarize, our system offers a favorable performance trade-off: We achieve significantly lower cost than the accuracy-optima baseline while preserving high accuracy at the cost of moderate latency, most of which attributable to one-time cache generation.
4.4 Scalability and Cache Management
Effect of Cache Size Increasing cache size generally reduces both cost and latency, up to a point of diminishing returns. On the FinanceBench dataset, larger caches yield higher hit rates and lower end-to-end latency, as fewer entries need to be regenerated after eviction. reports results using simple LRU eviction policy. Beyond certain capacity, approximately exceeding the number of unique task keywords, further enlarging the cache offers minimal benefit. In practice, users can tune cache capacity based on the desired trade-off between speed and storage.
Cache Size
Hit Rate
Cost
Accuracy
Planning Latency (s) Cache Gen. Latency (s)
Total Lateney (s)
2%
$3.97
92.00%
1638.85
383,87
2232.76
10
13%
$3.51
88.00%
1381.89
334.61
1911.95
20
28%
$2.95
85.00%
1248.06
289.36
1772.61
50
45%
$1.88
86.00%
1015.12
204.99
1459.92
100
46%
$1.86
85,50%
1011.81
215.80
1424.82
Table 4: Effect of Cache Size. Larger caches improve hit rate and reduce overall cost and latency until reaching a point of diminishing returns.
Exact Matching v. Fuzzy Matching For exact match lookups, cache uses Python's built-in dictionary, which provides highly optimized O(1) average-case lookup and insertion. To evaluate empirical performance, we measured wall-clock latency for cache hits and misses across varying cache sizes. Each measurement was averaged over 100 trials with CPU caches cleared before every run. As shown in Table 5 exact matching maintains consistently low latency up to 10 entries.
In contrast, fuzzy matching introduces substantial cache lookup latency that scales poorly with cache size. We implement fuzzy keyword matching in our prototype and use a semantic-similarty model CeentenceTransforee ( ('all-MiniIM-L6-x22) of magnitude slower than exact matching, confirming the computational overhead of semantic search.
As shown in Table this approach is orders

---

Exact Matching
Fuzzy Matching
Cache Size
Cache Hit Latency (p18)
Cache Miss Latency (18)
Cache Hit Latency (JuS)
Cache Miss Latency (Ju)
10a
13
14
$7
24
10a
15
75
10'
16
17
581
554
105
18
10388
10317
10
56
37
148449
1481 147
Table Cache Lookup Scalability. Fuzzy matching incurs much higher latency and scales poorly compared to exact matching. Averages over 100 trials; similarity threshold set to be 0.8.
Similarity Threshold
Hit Rate
Cost
Accuracy
Planning Latency (s)
Total Latency (s)
100%
46%
$1.86
85.50%
1011.82
1424.82
> 80%
54%
$1.15
83.00%
875.31
1219.73
> 60%
64%
$0.93
77.00%
720.29
1044.50
Table 6: Fuzzy Keyword Matching Results. Lower similarity thresholds increase hit rate and reduce cost and latency, but degrade accuracy.
We also find that under fuzzy keyword matching, lowering the similarity threshold increases the cache hit rate and reduces cost and latency, but at the expense of accuracy (Table This highlights the inherent trade-off in fuzzy matching: While risks introducing less relevant cached plans. Our cache interface remains flexible- users can enable fuzzy matching and tune thresholds according to their application's 's tolerance for semantic drift and latercy-accuracy trade-offs.
aggressive matching improves efficiency,
4.5
Cold Start
Cold start is an inherent limitation of test-time plan caching (as opposed to offline caching), since the cache begins empty. In the early phase, APC experiences higher latency and cost due to frequent cache misses and the need to generate new entries. To quantify this effect, we perform a time-series analysis of cache warm-up, shown in Table 7 As the cache grows, hit rate steadily increases, leading to lower marginal cost and latency over time. In practice, if the target workload is known in advance, users can mitigate cold-start overhead by pre-populating the cache with offline samples before deployment.
Query Percentile
# Cache Entries
1lit Rate
Cost
Planning Latency (s) Cache Gen. Latency (8)
Total Latency (s)
20th
15
14.29%
$0.59 (32.07%)
260.19 (27.43%)
59.19 (27.64%)
358.71 (25. 72%)
40tb
27
24.39%
$0.97 (52.72%)
484.88 (51.12%)
130.29 (60.86%)
689.49 (49.44%)
60th
36
36.07%
$1.20 (65.22%)
638. 12 (67. (2..8
167. 89 (78.41%)
926.82 (66 (66.46%)
80th
42
40.75%
$1.63 (88.59%)
820.94 (86.56%)
195.59 (91.35%)
1183..9 199.39 (84 86%)
100th
48.00%
$1.84 (100.00%)
948.36 (100.00%)
214.11 (100.00%)
1394.56 (100.00%)
Table 7: Cold Start Behavior. As the cache warms up. hit rate increases and marginal cost and latency decrease. Pre-warming the cache with offline samples can further mitigate cold-start overhead.
5 Conclusion
We introduce Agentic Plan Caching (APC), which shifts the focus from query-level caching (suitable for chatbots) task-level caching (targeting LLM-based agents). Unlike traditional semantic caching, APC extracts plan templates from completed agent executions at test time, uses keyword- basdd retrieval match new queries to cached plans, and leverages lightweight models to adapt these templates into context-specific task plans. By implementing agentic plan caching and evaluating it on five diverse agent workloads and two Plan-Act agent architectures, we demonstrate that our approach reduces agent serving costs by 50.31 % and latency by 27. 27.28% (on average) while maintaining 96.61 % of optimal application performance. Furthermore, the overhead introduced by plan caching remains minimal, accounting for only 1.04% (on average) of the total serving cost.
10

---

6
Acknowledgment
We thank all the anonymous reviewers and the area chair for their insightful feedback and suggestions, which significantly enhanced the quality of this work. Qizheng Zhang is supported in part by NSF CNS-2211 221223344 1384. Michael Wornow supported by the NSF Fellowship, a Stanford HAT Graduate Fellowship, and Stanford Healthcare. We thank Gerry Wan for his contribution the Open Deep Research experiments in this paper after the initial submission. We thank Avanika Narayan for helpful discussions Minions, and thank Hanchen Li, Zhiqiang Xie, Jon Saad-Falcon, Azalia Mirhoseini, and the LMCache team for helpful discussions on the project idea and its presentation.
References
[1] api.together.ai. hutps://ppi.ooeether.xy//
[2] Build a read--athaee -hroughh semantic cache with Amazon OpenSearch Serverless and Amazon Bedrock.
read -hrr-eddrcrrrag--nennnn--caohha
h-amazon- haapapoooooeeaaaaddeeeeeeeeeesn-
[3] Gemini Deep Research.
[4] GPT-4o mini: advancing cost-efficient intelligence. httpss//ppena..oom/nndd//ggg-o minio-
ancing- cost- wost--fffcientt-eeee inttiienneittelllggneee///
[5] GPT-4o System Card http:///peenocooo////////////ooo
[6] Llama 3.2: Revolutionizing edge Al and vision with open, customizable models. https:
[7] OpenAl API Platform https://openaa.com//ap//
[8] OpenAl deep research. https//ooenai.ccomiileeeeeeeeeee
[9] Reducing hallucinations in LLM agents with a verified semantic cache using Amazon Bedrock
Knowledge Bases. http:///www..aaaao...c/////////a
baste////geebbe/t//--- 8% 5420whenn&2neecesssuu htwp:///wo/o//aoo//o/oo//ooo/onn
[10] Fu Bang. Gptcache: An open-source semantic cache for I1m applications enabling faster answers and cost savings. In Proceedings of the 3rd Workshop for Natural Language Processing Open Source Software (NLP-OSS 2023), pages 212-218. 2023.
[11] Ralph Bergmann and Wolfgang Wilke. On the role of abstraction in case-based reasoning. In European Workshop Advances in Case-Based Reasoning, pages 28-43. Springer, 1996.
[12] Daniel Borrajo, Anna Roubīčková, and Ivan Serina. Progress in case-based planning. ACM Computing Surveys (CSUR), 47(2):1-39, 2015.
[13] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprini arXiiv2407.22788 2024.
[14] Ding Chen, Qingchen Yu, Pengyuan Wang, Wentao Zhang, Bo Tang, Feiyu Xiong, Xinchi Li, Minchuan Yang, and Zhiyu Li. xverify: Efficient answer verifier for reasoning model evaluations. arXiv preprint arXiv:2504 10481, 2025.
[15] Lingjia Chen, Matei Zaharia, and James Zou. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05 2023.
[16] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint 1rXiv:2007.03374, 2021.
[17] Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Banghua Zhu, Hao Zhang, Michael Jordan, Joseph E Gonzalez, et al. Chatbot arena: An open platform for evaluating 1lms by human preference, Forty-first International Conference Machine Learning, 2024.

---

[18] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14168, 2021.
[19] Pradeep Dasigi. Kyle Lo. Iz Beltagy, Arman Cohan, Noah A Smith, and Matt Gardner. A dataset of informattio--sekinng questions and answers anchored in research papers. arXiv preprint arXiv:2105.0300 2021.
[20] In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandelwal, and Lin Zhong. Prompt cache: Modular attention reuse for low-latency inference. Proceedings of Machine Learning and Systems, 6:325-338, 2024.
[21] Anna Goldie, Azalia Mirhoseini, Hao Zhou, Irene Cai, and Christopher D Manning. Synthetic data generation & multi-step for reasoning & tool use. arXiv preprint arXiv:2504.04736, 2025.
[22] Taicheng Guo, Xiuying Chen, Yaqi Wang, Ruidi Chang, Shichao Pei, Nitesh V Chawla, Olaf Wiest, and Xiangliang Zhang. Large language model based multi-agents: A survey of progress and challenges. arXiv preprini arXiv:2402.01688) 2024.
[23] Hongliang He, Wenlin Yao. Kaixin Ma. Wenhao Yu, Yong Dai, Hongming Zhang, Zhenzhong Lan, and Dong Yu. Webvoyager: Building an end-to-end web agent with large multimodal models. arXiv preprint arXiv:2401. 13919, 2024.
[24] Dan Hendryeks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. 2021.
arXiv preprin!
[25] Pranab Islam, Anand Kannappan, Douwe Kiela, Rebecca Qian, Nino Scherrer, and Bertie Vidgen. Financebench: A new benchmark for financial question answering. arXiv preprint arXiv:2311. /1944, 2023.
[26) Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Ar- mando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodehench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.077
2024.
[27] Shengyue Ji, Guoliang Li, Chen Li, and Jianhua Feng. Efficient interactive fuzzy keyword search. In Proceedings of the 18th international conference on World wide web, pages 371 -71-3 2009.
[28] Carlos E Jimenez, John Yang. Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310.06777 2023.
[29] Chao Jin, Zili Zhang, Xuanlin Jiang, Fangyue Liu, Xin Liu, Xuanzhe Liu, and Xin Jin. Rageache: Efficient knowledge caching for auumentl- generation. arXiv preprint arXiv:2404.1 /2457, 2024.
[30] Yizhang Jin, Jian Li, Yexin Liu, Tianjun Gu, Kai Wu, Zhengkai Jiang, Muyang He, Bo Zhao, Xin Tan, Zhenye Gan, et al. Efficient multimodal large language models: A survey. arXiv preprint arXiv:2405. 10739, 2024.
[31] Thomas Kwa, Ben West, Joel Becker, Amy Deng, Katharyn Garcia, Max Hasin, Sami Jawhar, Megan Kinniment, Nate Rush, Sydney Von Arx, et al. Measuring ai ability to complete long tasks. arXiv preprint arXiv:2503. /4499, 2025.
[32] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 61 1-26, 2023.
[33] Yuhan Liu, Yuyang Huang, Jiayi Yao, Zhuohan Gu, Kuntai Du, Hanchen Li, Yihua Cheng, Junchen Jiang. Shan Lu, Madan Musuvathi, et al. Droidspeak: Kv cache sharing for cross-llm communication and multi-llm serving. arXiv preprint 2rXiv:2411.02882 2024.
[34] Yuhan Liu, Hanchen Li, Yihua Cheng, Siddhant Ray, Yuyang Huang, Qizheng Zhang, Kuntai Du, Jiayi Yao, Shan Lu, Ganesh Ananthanarayanan, et al. Cachegen: Kv cache compression and streaming for fast large language model serving. Proceedings of the ACM SIGCOMM 2024 Conference, pages 38-56, 2024.
12

---

[35] Zechun Liu, Changsheng Zhao, Forrest landola, Chen Lai, Yuandong Tian, Igor Fedorov, Yunyang Xiong, Ernie Chang. Yangyang Shi. Raghuraman Krishnamoorthi, et al. Mobilellm: Optimizing sub-billion parameter language models for on-device use cases. In Forty-first International Conference on Machine Learning, 2024.
[36] Pan Lu, Liang Qiu, Kai-Wei Chang. Ying Nian Wu, Song-Chur Zhu, Tanmay Rajpurohit, Peter Clark, and Ashwin Kalyan. Dynamic prompt learning via policy gradient for semi-structured mathematical reasoning. arXiv preprint arXiv:2209.1480 2022.
[37] Mathematical Association of America (MAA). American Invitational Mathematics Examination (AIME). https://maaoorg/
[38] Grégoire Mialon, Clémentine Fourrier, Thomas Wolf, Yann LeCun, and Thomas Scialom. Gaia: a benchmark for general ai assistants. In The Twelfth International Conference on Learning Representations, 2023.
[39] Avanika Narayan, Dan Biderman, Sabri Byuboglu, Avner May, Scott Linderman, James Zou, and Christopher Re. Minions: Cost-efficient collaboration between on-device and cloud language models. arXiv preprint wwxxiv2502.1596 2025.
[40] Charles Packer, Vivian Fang. Shishir_ G Patil, Kevin Lin, Sarah Wooders, and Joseph_ E Gonza- lez. Memgpt: Towards Ilms as operating systems. 2023.
[41] Rui Pan, Yinwei Dai, Zhihao Zhang, Gabriele Oliaro, Zhihao Jia, and Ravi Netravali, Specrea- son: Fast and accurate inference-time compute via speculative reasoning. arXiv preprint (.Xiv:2504.0789) 2025.
[42] Joon Sung Park, Joseph O'Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceed- ings of the 36th annual acm symposium on user interface software and technology, pages 1-22, 2023.
[43] Shishir G Patil, Tianjun Zhang, Xin Wang, and Joseph E Gonzalez. Gorilla: Large language model connected with massive apis. Advances in Neural Information Processing Systems, 37:126544- 126565, 2024.
[44] Alexandre Roucher, Adrià Villanova del Moral, Merve, Thomas Wolf, and Clément Fourrier. Open Deep Research: Freeing Our Search Agents. httpss//uugginggaaeeccoo/oooobee earch February 2025. Hugging Face Blog.
[45] Vishnu Sarukkai, Zhiqiang Xie, and Kayvon Fatahalian. Self-generated in-context examples improve Ilm agents for sequential decision-maker making tasks. arXiv preprint arXiv:2505.00234, 2025.
[46] Luis Gaspar Schroeder, Shu Liu, Alejandro Cuadron, Mark Zhao, Stephan Krusche, Alfons Kemper, Matei Zaharia, and Joseph E Gonzalez. Adaptive semantic prompt caching with vectorq. arXiv preprini arXiv:2502.03777 2025.
[47] Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute opti- mally can be more effective than scaling model parameters. arXiv preprint wxXiv:2408.033/4 2024.
[48] Luca Spalzzi. A survey on case-based planning. Artificial Intelligence Review, 16(1):3-36. 2001.
[49] Theodore Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas Griffiths. Cognitive architec- tures for language agents. Transactions on Machine Learning Research, 2023.
[50] Junlin Wang, Jue Wang, Ben Athiwaratkun, Ce Zhang, and James Zou. Mixture-of-agents enhances large language model capabilities. arXiv preprint arXiv:2406. 2024.
[51] Zora Zhiruo Wang, Jiayuan Mao, Daniel Fried, and Graham Neubig, Agent workflow memory. arXiv preprint arXiv:2409.0744 07429, 2024.
[52] Anjiang Wei, Allen Nie. Thiago SFX Teixeira, Rohan Yadav, Wonchan Lee, Ke Wang, and Alex Aiken. Improving parallel program performance through dsl-driven code generation with Ilm optimizers. arXiv preprint arXiv:24100 15625, 2024.
[53] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24888 2022.
13

---

[54] Michael Wornow, Avanika Narayan. Krista Opsahl-One Quinn McIntyre, Nigam H Shah, and Christopher Re. Automating the enterprise with foundation models. arXiv preprint arXiv:2405.03710, 2024.
[55] Michael Wornow, Avanika Narayan, Ben Viggiano, Ishan Khare, Tathagat Verma, Tibor Thomp- son, Miguel Hernandez, Sudharsan Sundar, Chloe Trujillo, Krrish Chawla, et al. Wonderbread: A benchmark for evaluating multimodal foundation models on business process management tasks. Advances in Neural Information Processing Systems, 37:1 15911-1166612111 2024.
[56] Guanlong Wu, Zheng Zhang, Yao Zhang, Weili Wang, Jianyu Niu, Ye Wu, and Yinqian Zhang. I know what you asked: Prompt leakage via kv-cache sharing in multi-tenant Ilm serving. In P Proceedings of the 2025 Network and Distributed System Security (NDSS) Symposium. San Diego, CA, USA, 2025.
[57] Zhiqiang Xie, Hao Kang, Ying Sheng, Tushar Krishna, Kayvon Fatahalian, and Christos Kozyrakis. Ai metropolis: Scaling large language model-based multi-agent simulation with out-of-order execution. arXiv preprint arXiv:2411.03519 2024.
[58] Zhiqiang Xie, Ziyi Xu, Mark Zhao, Yuwei An, Vikram Sharma Mailthody, Scott Mahlke, Michael Garland, and Christos Kozyrakis. Strata: Hierarchical context caching for long context language model serving. arXiv preprint arXiv:2508. /8572, 2025.
[59] Wujiang Xu, Zujie Liang, Kai Mei, Hang Gao, Juntao Tan, and Yongfeng Zhang. A-mem: Agentic memory for Ilm agents. arXiv preprint urXiv:2502.12110, 2025.
[60] Jingbo Yang, Bairu Hou, Wei Wei, Yujia Bao, and Shiyu Chang. Kvlink: Accelerating large language models via efficient kv cache reuse. arXiv preprint arXiv:2502.66002, 2025.
[61] John Yang, Carlos Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. age-atent: Agent- compttc interfaces enable automated software engineering. Advances in Neural Information Processing Systems, 37:50528-5006 2024.
[62] Jiayi Yao, Hanchen Li, Yuhan Liu, Siddhant Ray, Yihua Cheng, Qizheng Zhang, Kuntai Du, Shan Lu, and Junchen Jiang. Cacheblend: Fast large language model serving for rag with cached knowledge fusion. In Proceedingy of the Twentieth European Conference on Computer Systems, pages 94-109, 2025.
[63] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023.
[64] Genghan Zhang, Weixin Liang, Olivia Hsu, and Kunle Olukotun. Adaptive self-improvement IIm agentic system for ml library development. arXiv preprint arXiv:2502.02534 2025.
[65] Qizheng Zhang, Changran Hu, Shubhangi Upasani, Boyuan Ma, Fenglu Hong, Vamsidhar Ka- manuru, Jay Rainton, Chen Wu, Mengmeng Ji, Hanchen Li, et al. Agentic context engineering: Evolving contexts for self- self-improving language models. arXiv preprint arXiv:2510.04615 2025.
[66] Qizheng Zhang, Ali Imran, Enkeleda Bardhi, Tushar Swamy, Nathan Zhang, Muhammad Shahbaz, and Kunle Olukotun. Caravan: Practical Online Learning of In-Network ML Mod- els with Labeling Agents. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pages 325-345, 2024.
[67] Yusen Zhang, Ruoxi Sun, Yanfei Chen, Tomas Pfister, Rui Zhang, and Sercan Arik. Chain of agents: Large language models collaborating on long-context tasks. Advances in Neural Information Processing Systems,
2024.
[68] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36:46595 2023.
[69] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Livia Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. Sglang: Efficient execution of structured language model programs. Advances in Neural Information Processing Systems, 17:62557-62588 2024.
[70] Shuyan Zhou, Frank Xu, Hao Zhu, Xubui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al. Webarena: A realistic web environment for building autonomous agents. arXiv preprint arXiv 13854, 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims we make in the abstract and in the introduction session ( accu- rately reflect the research problem we target, the solution we propose, and the contribution of our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We present discussion of the limitations of this work in Appendix E
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer:
[NA]
Justification:
This paper does not contain theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We present our experiment setup in $4.1 which contains all necessary infor- mation to reproduce the main results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The data and code of this work will be open-sourced upon publication of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (htnss//nips.cc/ppbiicgu
dess/CodeSubmissioooollyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (htips
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment settings, along with why they are set up in the current way, are disclosed in and in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
We properly discuss the statistical significance of our results in and in the Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report the resources we use for running the experiments (e.g. compute resources, AI API resources) in $ and in the Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't itdn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:://eeuip..cccooollchhhhhhce
Answer: [Yes]
Justification: We confirm that the research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We present a discussion the broader impact and socictal implications of this work in Appendix H
Guidelines:
18

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not involve the release of data or models that have risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We credit the models and the datasets we use directly via citations/URLs in 4.. and in the Appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets. paperswitheode. https/tthoodeecco/atttteseee com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce new assets (except for data and code, which will be open-sourced upon publication of the paper).
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing experiments or research with human subjects.
Guidelines:
20

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: In $ we describe how LLMs are used in our system as novel method for certain tasks (e.g. data filtering).
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy https///eeurssccccccmmmeeeee//// for what should or should not be described.
21

---

A Extended Discussion of Methods
A.1 Algorithms for Framework Design
In this section, we provide more algorithmic details of the agentic plan caching framework. To start with, the end-to-end workflow is provided in Algorithm
Algorithm 1 Agentic Plan Caching: End-to-End Framework
Require: Query q, Context ctz, Cache C
Ensure: Output o, Updated Cache C"
1: keyword &- Extractkeyword(y)
b Extract keyword using a small LM
2: if keyword C' then
Cache hit (Figure 2 aa)
3:
o,C² HandleCachcHit(q, ctv, ('keooord,, C))
> Algorithm
4: else
Cache miss (Figure
5:
0, C" + HandleCacheMiss(q, cta, keyword, C)
>> Algorithm
6: end if
7:
return o, C²
b Return response and possibly updated cache
The case of cache hit demonstrated Algorithm
Algorithm 2 Cache Hit
Require: Query ς, Context ctr, Plan Template template, Plan Cache C
Ensure: Output o, Cache C
1: responses f- (
Initialize actor LM response to be empty Adapt the retrieved template to
2: plan, o + Lig template, responses)
task-specific plan using lightweight model
3: Assert: is None
4: while is None do
5: response + (c ctc, plan)
b Execute the plan based on context
6: responses responses U response
7: plan, o LightLM(gg, template, responses) > Generate the final output or a new adapted
plan
8: end while
9: return o,
The case of cache miss is demonstrated in Algorithm
Algorithm 3 Cache Miss
Require: Query q, Context cla, Plan Template template, Plan Cache C
Ensure: Output o, Updated Cache C'
1: log 6
Initialize the execution log be empty Initialize actor LM response to be empty Generate initial plan with full model
2: responses +- 0
3: plan, PlannerLM(g.. responses)
4: Assert: o is None
5: while None do
6: response + ActorLM(g, ctæ, plan)
b Execute the plan based on context
7: responses responses U response
8: log + log U (plan, ctz, response))
> Update the log Generate the final output or new plan
9: plan, Plannerl.M(q, responses)
10: end while
log t- log (o)
Update the log Create reusable plan template based on
12: template +- Generate/Temllaee///e keyword)
execution log
13: C" CC
14: C'Kkeyword] f- template
Store template in cache
15: return C"
22

---

B Extended Description of Experiment Setup
B.1 Platform
The prototype of agentic plan caching framework, which implemented on a Runpod server with dual-socket Intel Xeon Gold 6342 CPUs (96 vCPUs, 2.80GHz base clock, 3.5GHz max turbo) and 512MB total L1, 60MB L2, and 72MB L3 cache. The server supports AVX-512 and runs in a 2x48-core NUMA configuration. For memory, the server is equipped with 503GB of system RAM and swap space.
to experiments, is
B.2 LLM API Usage and Pricing
All language model inferences in our prototype are performed via third-party APIs. While it is feasible to run inference locally when model weights are available, we use API access to quantify cost in dollar terms for this study. If metries such latency throughput were preferred, running all inferences locally would help eliminate variability introduced by external services, especially when they are hosted remotely. We use the Python APIs for OpenAI (v1.74.0), Together Al (v1.5.8), and Anthropic (v0.49.0), For all experiments, we set temperature to O (if supported) and max_ tokens to 4096. Table g lists the per-token pricing of all models used in experiments the time of evaluation.
Model Name
API Provider S/ Million lnput Tokens
$ Miilioo Output Tokens
GPT-4o (gpt-4o)
OpenAl
2,50
10.00
GPT-4o-mini (gpt-4o-mini)
OpenAl
0,15
0.60
Claude Sonnet (claude------mmmm--000000000
Anthropic
3,00
15,00
Llama-3. 1-8B (Neta-Llana-3. 1--8--nsttrut--uurtee
Together AI
0.18
0.18
Lluma-3.22 3.2-3-3.2-BB (Llama-3, 2----3..23-11a0 Sere---nnttuut--rtteeee
Together AI
0.06
0.06
Qwen-2.5-7B (Qwen2. 5- IerB-I-nttuuctTurbee
Together Al
0.30
0,30
Table 8: LLM API pricing used in experiments.
B.3 Datasets
FinanceBench. We use an augmented version of the FinanceBench test split from HuggingFace Following the Minions project, we filter for numerical reasoning questions and randomly sample 200 questions for evaluation. Each question requires long-context financial reasoning and is paired with a company-specific document essential for answering. The planner LM does not have access to the financial document, while the actor LM does.
TabMVP. We sample 200 questions from the test split of the TabMVP dataset provided by the authors Each question involves numeric reasoning and is paired with a required table; the question cannot be answered without the associated tabular data. The planner LM does not have access to the tabular data, while the actor LM does.
B.4 Prompts
B.4.1
Agent Prompts
We use the same prompts from the Minion protocol in the Minions project (39
B.4.2
LLM-as-a-Judde Prompt
As discussed in the results section ()4). standard metrics like exact match Fl score are often inadequate for evaluating numeric or long-form responses. For LLM-as-a-judge evaluation, we provide the prompt used assess answer correctness. We closely follow the FinanceBench dataset's original evaluation criteria and define rules for acceptable numeric deviations according to what the
23

---

FinanceBench dataset paper proposes, specifying what qualifies as correct answer. These rules are applied consistently across both FinanceBench and TabMWP evaluations.
Correctness Evaluation Prompt: You are judge that grades numeric answers to data-
intensive reasoning problems.
This is the question: (task).
This is the reference answer: {gt_answer).
This is the answer given by language model: fresponse).
Please grade it. Requirements:
(1) Please allow minor deviations, such as
(i) giving the answer in billions when the unit was given in the question as millions.
(ii) giving the answer in percentage when the ground truth answer is floating point.
Please also allow small rounding errors small numerical errors.
(2) Incorrect answers vary, from calculations that are off by small margins several orders of magnitude, and from making up legal information
giving the wrong direction for an effect (e.g. reporting negative growth when it is actually positive).
(3) Just answer '1" for correct answers, 'O' for incorrect answers.
B.4.3 Keyword Extraction Prompt
Can you help me summarize what is the 'task' 'keyword" describing higher-level goal intent this query? Please answer only with the task keyword, which must be independent from problem-specffit details. {query)
Keyword Extraction Prompt:
B.4.4
Cache Generation Prompt
You will see filtered JSON trace that shows the complete workflow of how a planner language model solves complex task by collaborating with actor language model. Clean up the element of each item in the workflow, so that we can reuse variables like company
Cache Generation Prompt:
this trace as a reference template (independent from name or fiscal year) when we meet similar tasks later.
Requirements:
(1) the first element in each "workflow" item can only "message", "output", or "answer",
(2) the task and the workflow should not contain problem-specific details or numbers, and
(3) return the result in JSON format that can be parsed by Python's json.loads().
IMPORTANT: The workflow must maintain the sequence of message->loppouttuut >message/answer) to ensure proper functioning. Always start with "message" and end with an "answer".
JSON trace: (trace}
B.4.5 Cache Adaptation Prompt
You are an intelligent language model that works with another model to solve complex tasks, like data-intensive reasoning questions. Please construct a follow-up action plan (in the form of a message) based on the task and the reference template.
Cache Adaptation Prompt:
Reference task: {cached_ (aached_task)
Reference follow-up action plan (as a message): (next_ finet_itmm____ iimn_innceaa wacheccccdd__.. templeeetem
Your task is to adapt the reference follow-up message to the current context, maintaining the same inquiry structure but customizing it for the specific details of the current question and model output. Make sure the message asks for information not contained past messages. Format your response as JSON object with a "reasoning" field set "N/A" and "message" field containing your action plan message.
Current task: (task)
Past action plans (as messages): (past_messages)
Past actor responses: (past_actes actor (ictorrrssosssss Current message:
24

---

C Extended Results
We evaluate the robustness of agentic plan caching under different choices of large planner LMs, small planner LMs, and actor LMs. Our key findings are:
Consistent Gains Across Models: Agentic plan caching consistently reduces cost and maintains high accuracy across variety of model choices, beyond those presented in $4
Model Selection Matters: Despite consistent gains of our method, choosing the right model remains crucial. For example, in most cases, Claude 3.5 Sonnet outperforms GPT-44o in accuracy
as the large planner LM but incurs significantly higher cost (Table (.. Similarly, smaller or cheaper
models do not always yield better accuracy-cee cestuccyycstttt tradeoffs. For example, using Llama-3.2-3B as the
actor LM often leads to both higher cost and lower accuracy compared to Llama-3. 1-8B due to insufficient response quality that triggers more Plan-Act iterations (Table 11.
FinanceBench
TabMWP
Method
Large Planner LM
Small Planner LM
Actor LM
Costl / Accurncyt
Cost./ / Accuracy!
Accuracy Optimal
GPT-4o
LJama-3.1 3.1-8B
$4.03 /91.0%%
S3.35 83.00%
Accuracy Optimal
Clande 3.5 Sonnet
Laama-3 3.1 1-88B
$5.77 94.50%
$5.09 85.50%
Cost-Optinal
Llama-3,1-8B
Llama-3.1-8B
$0.21 54.00%
$0.19 55.50%
Cost-Optimal
Llama-3.2-3B
Llama-3.1-8B
$0.09 63.00%
$0.08 57.00%
Full-History Caching
GPT-4o
Llama-3.1-88
Llama-3.1-40 1-8B
$1.99 72.00%
$2.24 62.50%
Full-History Caching
Claude 3.5 Sonnet
Llama-3.1188
Llama-3.1
$3.13 68. 00%
S2.80/ / 65.00%
Agentic Plan Caching (Ours)
GPT-4o
1.1ma-3.1-88
3-188
85.50%
82.00%
Agentic Plan Caching (Ours)
Clande 3.5 Sonnet
IJama-3. 3.188
Lama--3 1-8B
$2.56 / 88.00%
$2.73 6..33/8..00 81.50%
Table 9: Sensitivity Analysis of Large Planner LM: Results.
FinanceBench
TabMWP
Method
Large Planner LM
Small Planner LM
Actor LM
Costl Accurucy?
Cost./ Accuracy?
Full- History Caching
GPT-4o
LJama-3,1-88 3,1-88
Llama-3.1-8
$1 99. 72.00%
S2.24 / 62,50%
Full-History Caching
GPT-4o
Qwen-2.5-7B
IJama-3.1
$2.34 72.50%
$2.15 67.50%
Histor Caching
GPT-4o
1.1mma3.22-38
IJama-3.
67.00%
S1.67 56.00%
Agentic Plan Caching (Ours)
GPT-44
Llama-3.1 3.1-8B
Llama-3 3.1 3.1-8B
$1.86 85.50%
$2.03 / 82.00%
Agentic Plan Caching (Ours)
GPTT-4o
Qwen-2.5-7B
Llama-3.1-88
$1 (6/ 90.00%
$1.75 80.50%
Agentic Plan Caching (Ours)
GPT-4o
Llama-3.2-3B
Llama-3.1-8B
$1.62 84.00%
$1.88/ 80.00%
Table 10: Sensitivity Analysis of Small Planner LM: Results.
FinanceBench
TabMWP
Method
Large Planner I.M
Small Planner LM
Actor L.M
Costl/ / Accuracy?
Cost./ Accuracy?
Accuracy-Opeee Optimal
GIT--4o
Llama-3.1 1-188
$4.03 /91.0%%
$3.35 83. 0.00%%
Accuracy-Optimll
GPT-4o
Qwen-2.5-7B
$3.97 (9197/91000 /9100% 1.00%
$3.06 87, 50.00%
Accuracy-Optimal
GPT-4o
Llama-3.2-3B
$4.16 61.508
$4.43 / 74.00%
Cost-Opiine Cost-Optimal
1.
IJama-3.1
54.00%
$0.19 55.50%
Cost-Optimal
Llama-3,1-88
Qwen-2.5-7B
$0.23 58.50%
$0.17 65.50%
Cost-Optimal
1.ama-3.1-88
1aama-3.2.3
$0.17 53.00%
S0.24 / 57.005.
Full-Histery Caching
GPT-4o
Llama-3.1-88
Llama-3.1-88
$1.99 72.00%%
$2.24 62.50%
Full-History Caching
GITT-4o
Llama-3.1-8B
3.1-8B
Qwen-2.5-78
$2.31 70.50%
$1.77 60.50%
Full History Caching
GPT-44
Llama-3.1 3.1-8B
Llama-3 Llama-3.2-3B 3.2-3B
$2.20 60.00%
$2.22 / 58.00%
Agentic Plan Caching (Ours)
GPT-4o
Llama-3.1-8B
Llama-3.1-8B
$1.86 85.50%
$2.03 82.00%
Agentic Plan Caching (Ours)
GPT-4o
Llama-3.1-8B
Qwen-2.5-7B
$1.77 990.50%
S1,76/ 84.00%
Agentic Plan Caching (Ours)
GPT-40
1lama-3.1-88
1lama-3.2-39
$1 85 80.000
$2.18 73.00%
Table 11: Sensitivity Analysis of Actor LM: Results.
25

---

D Example Agent Workflows and Cached Plan Templates
This section illustrates example agent workflows and their corresponding cached plan templates for data-intensive reasoning tasks. We begin with a simple single-turn task (more complex multi-turn examples are presented our experiments):
Task: What is FY2019 working capital ratio for Costco? Define working capital ratio as total current assets divided by total current liabilities. Round your answer to two decimal places. Give response to the question by relying on the details shown in the statement of financial position.
Context: pooetco_finaccial..
Below is the full agent workflow between large planner LM and actor LM, executed without caching (prompts omitted for brevity):
Planner: 1. Decompose the Task: The task requires calculating the working capital ratio for Costco for FY2019. This involves two main components: identifying the total current assets and the total current liabilities for FY2019 from the statement of financial position.
Explain Each Component:
Identify Total Current Assets: This is important because it represents the resources that Costco can convert into cash within a year. Knowing this figure is essential for calculating the working capital ratio.
Identify Total Current Liabilities: This represents the obligations that Costco needs to settle within a year. This figure crucial determining the working capital ratio as provides the denominator in the calculation.
Calculate Working Capital Ratio: This step involves dividing the total current assets by the total current liabilities. The result will give the working capital ratio, which is measure of Costco's short-term financial health.
3. Formulate Focused Message: The next step to ask the small language model for the specific figures of total current assets and total current liabilities for Costco in FY2019. This will allow us to perform the calculation.
4. Conclude with Final Answer: Once have the figures,
calculate the working capital ratio and provide the final answer rounded to two decimal places.
Generated plan (as a message to the actor LM): Please provide the total current assets and
total current liabilities for Castco for FY2019 9 from the statement of financial position.
Actor: Based the provided statement of financial position for Costco Wholesale Corporation
of September 2019, the total current assets and total current liabilities are:
Total current assets: $23, 485 million
Total current liabilities: $23, 237 million
Planner: 1. What information we have gathered: We have obtained the total current assets
and total current liabilities for Costco as of September 1, 2019. The total current assets are $23,485 million, the total current liabilities are $23,237 million.
2. Whether it sufficient answer the question: Yes, this information is sufficient to calculate
the working capital ratio for Costco for FY2019.
3. If not sufficient, what specific information is missing: Since we have both the total current
assets and total current liabilities, no additional information is needed.
4. sufficient, how we would calculate derive answer: To calculate the working capital ratio, we divide the total current assets by the total current liabilities. The formula is: Working Capital Ratio Total Current Assets Total Current Liabilities
Substituting the given values: Working Capital Ratio $23,485 million $23,237 million Calculating this gives approximately 1.01 when rounded
decimal places.
Conclusion: The working capital ratio for Costco for FY2019 1.01.
The following plan template extracted from this successful workflow and stored in the cache:
Keyword: working capital ratio
Plan Template: 1. Plan (round 1): Retrieve total current assets and total current liabilities from the statement of financial position.
2. Expected response from actor LM (round 1): Total current assets and total current liabilities.
3. Plan (round 2): The working capital ratio can be determined by: Working Capital Ratio Total Current Assets Total Current Liabilities.
26

---

Later, for tasks with the same extracted keyword, such as the example below:
What is FY2021 working capital ratio for Best Buy? Define working capital ratio as total current assets divided by total current liabilities. Round your answer to two decimal places. Please base your judgments the information provided primarily in the statement of financial position.
Task:
Context:
We reuse the cached plan template and adapt it using a small planner LM:
(Using cached plan template) Please provide the total current assets and total current liabilities for Best Buy in FY2021 from the statement of financial position, can calculate the working capital ratio.
Planner:
Actor: According to the Consolidated Balance Sheets, the total current assets for Best Buy FY2021 are $12,540 million, and the total current liabilities are $10,521 million.
Planner: (Using cached plan template) The FY2021 working capital ratio for Best Buy is calculated by dividing the total current assets by total current liabilities. With total current assets of $12,540 million and total current liabilities $1 $10,521 million, the working capital ratio $12,540 million $10,521 million = 1.19. Therefore, the working capital ratio is 1.19, rounded to two decimal places.
Using the cached template significantly shortens the agent execution log, reducing token usage for expensive planner LMs. This efficiency gain comes from:
Avoiding redundant planning for repeated tasks. Knowing when sufficient information has been gathered to terminate the workflow, thus avoiding unnecessary Plan-Act iterations.
E
Extended Discussion of Limitations, Societal Impact, and Future Directions
Limitations and Challenges First, we focus on two-stage Plan-Act agent architecture in this work. More complex multi-agent systems could present new challenges for maintaining cache consistency across multiple components. Second, for highly dynamic workloads with frequent task variations, the benefits of caching may diminish as historical plans may be less applicable. Finally, our evaluation primarily emphasizes cost reduction. Future work could consider additional system metrics such as latency, throughput, and computational overhead.
Broader Impact and Societal Implications We believe that the proposed agentic plan caching framework has broader implications for AI accessibility and democratization. By reducing LLM serving costs, this framework could enable smaller enterprises, academic institutions, and individual developers to deploy agentic Al systems without incurring prohibitive API costs. Additionally, plan caches generated by advanced, commercial LLMS could potentially be shared adapted for with open- source models (as shown in our experiments), facilitating greater access to state-of-the-a agentic capabilities without direct reliance on expensive. dosed-source APIs (e.g., from OpenAI). This approach also raises questions about the long-term impact on data privacy, especially in cases where plan caches contain sensitive or proprictary information. Ensuring cache privacy and data security in LLM agents requires further research.
Future Directions Several future directions could extend the utility of agentic plan caching. First, more advanced cache look-up and plan adaptation methods (like aurreval-auumentte generation) might further enhance the relevance of cached plans in complex workflows. Second, enabling user-configurable cache parameters (e.g., cache size, eviction strategies, fuzzy matching policies) could provide more control over caching strategies and allow for tailored cost-perfone cost-performance trade-offs. Finally, integrating the idea of agentic plan caching into existing LLM and agent serving frameworks at production scale would further enhance its applicability and impact. Overall, we hope this work inspires further research on optimizing the efficiency and cost-effectivenes of agentic AI systems.
27


Reviews:
[{"review_id": "Gv9LttAA8k", "reviewer": "Reviewer_7A5h", "summary": "This work proposes a new technique to do plan caching. Previous works have done caching to save KV parameters of the LLM, or the whole task including all parameters and keywords. The novelty of this approach is that the abstract plan or “plan template” is cached. The keywords are abstracted or removed before doing the caching. This makes the plan applicable for a wide range of parameters, and not just the single task it was originally meant for.  \n\nThe advantage of the approach is that it saves the cost of using LLMs for plan generation every time, many of which are usually unnecessary. Experimental comparison with other caching techniques show that the cost is substantially reduced in two domains with little loss of plan quality.", "questions": "1. When there are multiple possible items in the cache matching the new task, how are they ranked? Have you encountered any such cases?\n2. In Figure 1, why is there no link from the context to the planner?\n3. In 2.2 (1) Model Specific constraints, why would one want to use a different LLM agent for a task of one agent?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is generally well written and easy to follow. The paper is also well motivated. The existing caching techniques in LLMs are explained well with figures.\n\nThe proposed method is relatively straighforward and makes sense. The concept of saving the abstract plans is not new and has been explored extensively in the case based reasoning and case based planning literature.\n\nBorrajo, Daniel, Anna Roubíčková, and Ivan Serina. \"Progress in case-based planning.\" ACM Computing Surveys (CSUR) 47, no. 2 (2015): 1-39.\n\nSpalzzi, Luca. \"A survey on case-based planning.\" *Artificial Intelligence Review* 16 (2001): 3-36.\n\nBergmann, Ralph, and Wolfgang Wilke. \"On the role of abstraction in case-based reasoning.\" In *European Workshop on Advances in Case-Based Reasoning*, pp. 28-43. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996.\n\nGiven the simplicity of the technique, I was expecting a deeper dive into the issues of abstraction and I was also expecting a more elaborate experimental evaluation. \n\nWhen there are multiple possible items in the cache matching the new task, how are they ranked? Have you encountered any such cases?\n\nA planner usually takes in the current context as a part of the initial state. So, why is there no link from the context to the Planner LM in the Plan-Act flow chart?\n\nThe main weakness I see is the lack of experimental domains and analysis.", "was_revised": true, "final_justification": "The authors have clarified my doubts about the originality compared to classical case based planning literature, and promised to include a discussion of it in the revised version. They have also answered my questions related to the approach convincingly. In light of that, I am increasing my score.", "rebuttal": "We thank the reviewer for the kind words and helpful feedback! We address each concern/question below. \n\n**#1: The concept of saving abstract plans is not new and has been explored extensively in the case‑based reasoning / planning (CBP) literature.**\n\nAlthough our work indeed shares the high‑level intuition of “store & reuse”, it targets a fundamentally different setting than classic symbolic CBP: LLM‑based, neural agents executing open‑ended natural‑language actions. In particular, our system differs from CBP in two key ways: \n(1) Automatic plan template extraction at test time from unconstrained and open-ended LLM generations, instead of storing hand‑crafted symbolic plans, and\n(2) Leveraging plan storage and reuse for cost-efficient inference of LLM agents. \nWe will add an explicit discussion contrasting these ideas and citing the survey papers you helpfully provided (Borrajo et al., Spalzzi 2001, Bergmann & Wilke 1996). \n\n**#2: Depth of abstraction discussion, and potential lack of experimental domains / analysis.**\n\nSection 3.2 motivates some key design choices behind the simple abstraction of “store & reuse”, like why we abstract executions into templates and why simple keyword keys minimize false positives / negatives. \n\nWe have done a lot of additional in-depth microbenchmarks and analysis of our caching system to show how it could be adopted in practice, like scalability and online cache management, fuzzy keyword match v.s. exact keyword match, end-to-end latency analysis and breakdown, the cold-start effect of our system, etc. Due to space constraint, we won't be able to fit everything in this rebuttal response. Please feel free to take a look at our additional results under other reviews --- We are happy to answer any questions you may have about them! \n\nWe have also added experiments that apply our system to a wider set of tasks: long‑context reasoning and math reasoning, and we are also working to incorporate more benchmarks in agentic function calling and tool use. The results show that our plan‑act approach generalizes well across these domains, delivering lower cost while preserving accuracy. In the camera‑ready version, we will also discuss additional domains that could benefit most from our system and those where its impact may be limited.\n\n| Category | Benchmark | Method | Cost | Accuracy |\n|-------|-----|-------|-------|-------|\n| Long-context reasoning | QASPER (200 random samples) | Accuracy-Optimal | $2.14 | 58.00% |\n| | | Cost-Optimal | $0.21 | 53.00% |\n| | | **Ours** | **$0.78** | **57.00%** |\n| Math reasoning | AIME 2024 (all 30 queries) | Accuracy-Optimal | $1.14 | 64.52% |\n| | | Cost-Optimal | $0.65 | 48.39%  |\n| | | **Ours** | **$0.85** | **61.29%** |\n| Math reasoning | AIME 2025 (all 30 queries) | Accuracy-Optimal | $1.34 | 61.29% |\n| | | Cost-Optimal | $0.60 | 48.39% |\n| | | **Ours** | **$0.81** | **58.06%** |\n\n**#3: When there are multiple possible items in the cache matching the new task, how are they ranked? Have you encountered any such cases?**\n\nWe have encountered such cases, especially when agentic queries share similar task intent. Our cache is highly configurable: users can choose to store multiple entries per task keyword or just one. When multiple entries are kept, any or all of them can be provided to the lightweight Planner LM, similar to multi-shot in-context learning. Users may also implement ranking strategies, e.g., ranking entries by recency might help handle domain shifts. In our long-context reasoning experiments, we keep a single entry per task keyword, as extracted task templates tend to be similar across shared intents. This may not hold in other applications. \n\n**#4: In Figure 1, why is there no link from the context to the planner?**\n\nWe agree that some metadata about the Context may be useful for the Planner LM. However, we view this as an implementation detail that would unnecessarily clutter the diagram and is not essential for the common tasks we consider. For instance, to answer the query “What is FY2019 working capital ratio for Costco?”, the Planner does not need to read the entire 10-K to devise a strategy for answering the question. Still, it may be helpful for the Planner to know in advance that the Context is a 10-K report and have general knowledge of what such reports typically contain. We will adjust the diagram accordingly in the camera-ready version, e.g. by adding a dashed line between Context and Planner. \n\n**#5: In 2.2 (1) Model Specific constraints, why would one want to use a different LLM agent for a task of one agent?**\n\nEven for single-agent tasks, users may choose different base models based on performance goals. For example, OpenAI o3 for stronger reasoning, GPT-4.1 for better long-context handling, or 4o-mini for cost efficiency. The main challenge for KV cache sharing is that it remains difficult to transfer knowledge between agents with the same architecture but different base models. \n\n**Finally:** We really appreciate your insightful suggestions, which have already helped us strengthen both the analysis and presentation of this work. We hope the above clarifications resolve the concerns. If the response is helpful, we would be grateful if you could consider adjusting your score accordingly. We are committed to incorporating all promised additions in the camera‑ready version to make the paper as valuable as possible to the community."}, {"review_id": "mLBvwSuQ6Y", "reviewer": "Reviewer_AHQG", "summary": "This paper proposes a cost-efficient serving strategy for LLM-based agents through plan caching. Instead of relying on conventional context or semantic caching, the authors introduce a method that caches structured plan templates extracted from past executions. New tasks are matched to cached plans using keyword-based similarity, and a smaller LLM is used to adapt these plans to the current context. Experiments on two agentic benchmarks demonstrate that this approach reduces serving costs significantly (by ~46%) while maintaining high task performance.", "questions": "Please see Weaknesses above.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n- The paper is overall well-written and includes clear, helpful figures.\n\n- The analysis is thorough, especially in justifying design choices such as using keyword-based cache search instead of query-based methods, and showing the benefit of plan caching over semantic or full-history caching.\n\n## Weaknesses:\n\n- The TabMWP dataset feels a bit too simple. It would make the paper more impactful to evaluate on more complex math datasets like AIME.\n\n- There is a lack of analysis on how the caching method performs as task diversity increases. For example, how would it perform on a benchmark with very diverse tasks, such as GAIA? Would it still outperform other caching strategies?", "was_revised": true, "final_justification": "The paper is well-written with good empirical results. Most of my concerns were addressed during the rebuttal. Therefore, I am maintaining my score.", "rebuttal": "We thank the reviewer for the kind words and constructive feedback! Below, we address each concern in detail.\n\n**#1: TabMWP is too simple, need to evaluate on more complex math datasets like AIME.**\n\nWe have added results on AIME 2024 and AIME 2025, each consisting of 30 math reasoning problems. Although our system was not specifically designed for math tasks, we find that caching plans in the form of meta problem-solving strategies (such as reusable tricks and heuristics) significantly boosts performance of smaller reasoning LMs on new problems within similar domains (e.g., algebra, geometry). For these experiments, we use o3 as the large planner LM, and o3-mini as the small planner LM and the actor LM, since reasoning capability is quite important in these benchmarks. \n\n| Category | Benchmark | Method | Cost | Accuracy |\n|-------|-----|-------|-------|-------|\n| Math reasoning | AIME 2024 (all 30 queries) | Accuracy-Optimal | $1.14 | 64.52% |\n| | | Cost-Optimal | $0.65 | 48.39%  |\n| | | Ours | $0.85 | 61.29% |\n| Math reasoning | AIME 2025 (all 30 queries) | Accuracy-Optimal | $1.34 | 61.29% |\n| | | Cost-Optimal | $0.60 | 48.39% |\n| | | Ours | $0.81 | 58.06% |\n\n**#2: Potential lack of analysis on increased task diversity, e.g. on GAIA.**\n\nWe have added more experiment results to include tasks across diverse domains, including long-context reasoning, math problem-solving, etc. We are also actively working to incorporate benchmarks from domains like function calling and web agents. For these experiments, we use GPT-4o as the large planner LM, and Llama-3.1-8B-Instruct as the small planner LM and the actor LM. Below, we show one of the long-context benchmarks from the Minions paper: \n\n| Category | Benchmark | Method | Cost | Accuracy |\n|-------|-----|-------|-------|-------|\n| Long-context reasoning | QASPER (200 random samples) | Accuracy-Optimal | $2.14 | 58.00% |\n| | | Cost-Optimal | $0.21 | 53.00% |\n| | | **Ours** | **$0.78** | **57.00%** |\n\nWhile our approach to plan caching is generally applicable to agentic tasks that benefit from reuse of reasoning patterns, we have not included GAIA due to its highly heterogeneous task queries, which limit opportunities for cache reuse. We will include a discussion in the camera-ready version on domains that benefit most from our method, as well as those where impact may be limited. \n\nIf you have more benchmarks in mind, feel free to let us know! \n\nWe have done a lot of additional in-depth microbenchmarks and analysis of our caching system to show how it could be adopted in practice, like scalability and online cache management, fuzzy keyword match v.s. exact keyword match, end-to-end latency analysis and breakdown, the cold-start effect of our system, etc. Due to space constraint, we won't be able to fit everything in this rebuttal response. Please feel free to take a look at our additional results under other reviews --- We are happy to answer any questions you may have about them!\n\n**Finally:** We really appreciate your insightful suggestions, which have helped us strengthen the evaluation part of our work. If the response is helpful, we would be grateful if you could consider adjusting your score accordingly. We are committed to incorporating all promised additions and experiment results in the camera‑ready version to make the paper as valuable as possible to the community."}, {"review_id": "XHjTfUqn1R", "reviewer": "Reviewer_c5yq", "summary": "This paper proposes an agentic plan caching algorithm that reduces costs by nearly 50% and nearly maintains the original optimal accuracy. Previous caching methods are limited because they (1) have model-specific constraints; agentic flows typically use various models while caching methods are for specific models (2) reuse cached responses while agentic flows have data-dependent outputs (3) are limited in adaptability sometimes requiring exact text matches. The agentic plan caching framework, intended for use in Plan-Act frameworks that utilize a large LM for high level planning and a small LM to carry out the plan, generates a plan template on cache misses to be followed by a small LM during cache hits. Evaluation is conducted on methods optimal for accuracy and cost and semantic caching and agentic plan caching is shown to reach the best tradeoff between cost and accuracy.", "questions": "- On the discussion between exact matching versus fuzzy matching, an argument is made that fuzzy matching could make cache lookups slower and costly. An empirical evaluation of this claim would make this point stronger.\n  - Additionally, there is no study of the speed of the agentic plan caching algorithm. Surely given a plan template is generated this would be much slower than other approaches.\n- What is the major bottleneck in keeping the costs low but the accuracy high? The agentic plan caching is nearly close to optimal in some cases (Table 1 TabMWP) which is impressive but what would close this gap further?\n  - I am interested in more information regarding the rule-based filter and specific failure modes of the plan template that lead to unexpected behavior and the lower performance", "limitations": "The authors have clearly addressed the limitations of this work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Quality:** The baselines and experiments effectively demonstrate the usefulness of agentic plan caching.\n\n**Clarity:** The paper is written clearly, with the shortcomings of previous caching approaches clearly demonstrated.\n\n**Significance:** The cost-effectiveness of this caching strategy is very significant but is limited to two-stage Plan-Act agent architectures whereas other caching strategies can be applied agnostic to architectures.\n\n**Originality:** This caching approach is a unique addition to previous approaches like KV caching and semantic caching.", "was_revised": true, "final_justification": "My initial concerns were regarding latency of the overall system as well as understanding where the bottleneck in the system lies. Comprehensive evaluations were introduced that fully addressed all my concerns regarding latency and I understand the bottleneck to be the capabilities of the small planner LM. I have decided to increase my score.", "rebuttal": "We thank the reviewer for the kind words and constructive feedback! Below, we address each concern in detail.\n\n**#1: On the discussion between exact matching versus fuzzy matching, an argument is made that fuzzy matching could make cache lookups slower and costly. An empirical evaluation of this claim would make this point stronger.**\n\nThank you for this insightful question. For exact-match cache lookup, our cache uses Python’s native dictionary implementation, which is highly optimized. Both lookup and insertion have an average-case time complexity of O(1). To empirically validate the performance, we measured wall-clock latency for cache hits and misses with increasing cache sizes. We cleared the CPU cache before each run and averaged each measurement over 100 trials. For exact match (used in our experiments), lookup latency remains low up to a cache size of 10^6: \n\n| Cache size | Avg. cache hit latency (μs) | Avg. cache miss latency (μs) |\n|----|-------|-------|\n| 10^2 | 13 | 14 |\n| 10^3 | 15 | 15 |\n| 10^4 | 16 | 17 |\n| 10^5 | 22 | 18 |\n| 10^6 | 56 | 37 |\n\nIn contrast, fuzzy matching usually incurs significantly higher latency (depending on implementation detail of the fuzzy match algorithm), which grows rapidly with cache size. We implemented a semantic similarity-based fuzzy cache using ```SentenceTransformer('all-MiniLM-L6-v2')``` from the ```sentence_transformers``` library, with a similarity threshold of 0.8 for hit detection: \n\n| Cache size | Avg. cache hit latency (μs) | Avg. cache miss latency (μs) |\n|-------|-----|-------|\n| 10^2 | 57 | 24 |\n| 10^3 | 75 | 70 |\n| 10^4 | 581 | 554 |\n| 10^5 | 10388 | 10317 |\n| 10^6 | 148449 | 148147 |\n\nThese results confirm that fuzzy matching introduces substantial overhead and scales poorly compared to exact match. This is one of the key reasons we adopt exact keyword matching in our system, as discussed in Section 3.2. Additional factors include the difficulty of selecting a universal similarity threshold, which is a common challenge in semantic caching. \n\nTo further investigate, we implemented fuzzy keyword matching in our prototype. Specifically, we use semantic embeddings to measure similarity between keywords, treating a cache lookup as a hit if the similarity exceeds a predefined threshold. Below, we report the empirical results: \n\n| Similarity threshold | Cache hit rate | Cost | Accuracy | Planning latency (s) | End-to-end latency (s) | \n|-------|-----|-------|-------|-------|-------|\n| =100% | 46% | $1.86 | 85.50% | 1011.82 | 1424.82 |\n| >80% | 54% | $1.15 | 83.00% | 875.31 | 1219.73 | \n| >60% | 64% | $0.93 | 77.00% | 720.29 | 1044.50 |\n\nAs we can observe, lowering the similarity threshold increases the cache hit rate and reduces cost and latency, but at the expense of accuracy. This highlights the inherent trade-off in fuzzy matching: While more aggressive matching improves efficiency, it risks introducing less relevant cached plans. \n\nThe good news is that our cache interface is highly reconfigurable. Users can flexibly enable fuzzy matching and tune the similarity threshold to fit their application's tolerance for semantic drift and performance requirements.\n\n**#2: Speed of the proposed system?**\n\nWe evaluated the wall-clock latency of our system and compared it to both accuracy-optimal and cost-optimal baselines. Additionally, we provide a detailed breakdown of latency incurred by each component in our plan caching pipeline. This microbenchmark is based on 100 randomly sampled queries from the FinanceBench dataset, with a cache hit rate of 46% (i.e., cached plans were used for 46 of the 100 queries). As shown in the table below, most of the additional latency in our system comes from LLM-powered cache generation, which takes an average of 3.99 seconds per entry. To further mitigate this overhead, we (1) automatically disable caching when the hit rate is consistently low, and (2) are exploring optimizations such as parallel cache generation and speculative next-query inference. \n\n| Method | Plan latency (s) | Act latency (s) | Keyword extraction latency (s) | Cache lookup latency (s) | Cache generation latency (s) | End-to-end latency (s) | \n|-------|-----|-------|-------|-------|-------|-------|\n| Accuracy-Optimal | 1813.41  |  94.39   | N/A | N/A | N/A | 1959.24 |\n| Cost-Optimal   |  856.75  |  93.31   | N/A | N/A | N/A | 1004.79 |\n| Ours | 1011.82 | 131.44 | 42.29 | < 1s | 215.80 | 1424.82 |\n\nOur system offers a favorable performance trade-off: We achieve significantly lower cost than the accuracy-optimal baseline while preserving high accuracy at the cost of moderate latency, most of which is attributable to one-time cache generation. \n\n**#3: Major bottleneck in keeping the costs low but the accuracy high. Specific failure modes of the plan template that lead to unexpected behavior and the lower performance.**\n\nFor FinanceBench, a key challenge arises from the limited capacity of the small planner LM, which must not only follow the plan but also aggregate context across multiple agentic rounds. This includes retrieving relevant information from prior rounds and actor LMs, then synthesizing a final answer, often requiring arithmetic or simple reasoning. We find that even when the correct plan is generated from the template and all necessary information is collected, the small planner LM may still fail to produce the correct final answer due to issues such as hallucinations or arithmetic mistakes. Enhancing the small planner LM’s capability in long-horizon reasoning remains an important direction for future work.\n\nA second failure mode stems from the need for robustness when actor LMs return invalid outputs or errors. In such cases, the planner LM must re-execute earlier steps before proceeding (“retry”). While our template serves as an in-context guide, enabling the planner to handle such deviations, we observe that small planner LMs, especially those under 8B, sometimes fail to confirm successful completion of earlier steps before moving forward. This can lead to cascading errors. We believe that adding stronger runtime checks would help ensure that the planner LM adapts to feedback from the actor LMs and environment, rather than rigidly following the cached plan.\n\n**Finally:** We really appreciate your insightful suggestions, which have helped us strengthen the design and the evaluation sections of our work. If the response is helpful, we would be grateful if you could consider adjusting your score accordingly. We are committed to incorporating all promised additions and experiment results in the camera‑ready version to make the paper as valuable as possible to the community."}, {"review_id": "mNOTcciitk", "reviewer": "Reviewer_RMgA", "summary": "The paper proposes agentic plan caching, a serving-time technique aimed at cutting the cost of Plan-Act LLM agents. After each completed run, the system extracts a plan template from the planner’s execution trace, stores it under a task-intent keyword, and later retrieves and lightly adapts that template—using a small model—when a semantically similar request arrives. Experiments on two data-intensive reasoning benchmarks (FinanceBench and Tabular-MWP) show a mean 46 % cost reduction while retaining 96 % of the accuracy of an all-large-LM baseline, with only ~1 % overhead for keyword extraction and cache management.", "questions": "1. Exact keyword matching avoids false positives but may miss near-duplicates. Have the authors explored lightweight embedding search or fuzzy matching, and how would that affect hit-rate, cost, and accuracy?\n\n2. The paper focuses on token cost; could end-to-end latency numbers be reported (cache lookup + rewrite)?", "limitations": "See weakness.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. The paper addresses the rising serving cost of multi-step LLM agents, a practical bottleneck that is less studied than model-side optimization. The distinction between query-level (chatbot) caching and task-level (agent) caching is well argued.\n\n2. The framework rests on off-the-shelf components and could be grafted onto other Plan-Act agents. \n\nWeakness:\n\n1. Scalability and cache management are not discussed. How does cost-saving scale with cache size? Is there a point of diminishing returns?\n\n2. Cold-start and domain drift is not discussed. What happens when the cache is empty or when tasks drift over time? Could you report accuracy and cost as a function of cache warm-up and domain shift would clarify the real-world usefulness.\n\n3. While cost is reduced, the extra keyword extraction, lookup, and template adaptation may add latency. Could the paper report end-to-end wall-clock times? In addition, storing plan templates might leak sensitive workflow information\n\n4. Generality is not discussed. The solution is demonstrated with a specific large planner and an 8 B re-planner. How well does the approach transfer if those models are swapped for smaller or fundamentally different LLM families?", "was_revised": true, "final_justification": "I am mostly concern about the cache capacity and end-to-end latency. The authors have addressed almost all of my previous concerns, clarifying key methodological choices and strengthening the interpretation of the results. In light of these improvements, I am willing to raise my score.", "rebuttal": "We thank the reviewer for the constructive feedback! \n\n**#1: Scalability and cache management are not discussed.**\n\nOur microbenchmark reveals two key findings on the scalability of plan caching and cache management. \n\n(1) Larger cache, more cost and latency reduction (until the point of diminishing return): On the FinanceBench dataset, we find that a larger cache size would lead to larger reduction in end-to-end cost and latency, which is aligned with our intuition since a smaller cache size means more cost and latency dedicated to cache eviction and re-generating evicted cache entries. We present some numbers with a simple LRU eviction policy: \n\n| Cache size | Cache hit rate | Cost | Accuracy | Planning latency (s) | Cache generation latency (s) | End-to-end latency (s) |\n|-------|-----|-------|-------|-------|-------|-------|\n| 1 | 2% | $3.97 | 92.00% | 1638.85 | 383.87 | 2232.76 |\n| 10 | 13% | $3.51 | 88.00% | 1381.89 | 334.61 | 1911.95 | \n| 20 | 28% | $2.95 | 85.00% | 1248.06 | 289.36 | 1772.61 |\n| 50 | 45% | $1.88 | 86.00% | 1015.12 | 204.99 | 1459.92 |\n| 100 | 46% | $1.86 | 85.50% | 1011.81 | 215.80 | 1424.82 |\n\n**Will there be a point of diminishing return?** Yes, when the cache size is large enough, e.g. larger than the unique number of task intents in the entire agentic dataset or workload, there will be no extra benefit of having a larger cache. In practice, users could flexibly adjust cache size cap based on speed and storage requirements.\n\n(2) Scalability of cache operations (lookup and insertion): For exact-match cache lookup, our cache uses Python’s native dictionary implementation, which is highly optimized. Both lookup and insertion have an average-case time complexity of O(1). To empirically validate the performance, we measured wall-clock latency for cache hits and misses with increasing cache sizes. We cleared the CPU cache before each run and averaged each measurement over 100 trials. For exact match (used in our experiments), lookup latency remains low up to a cache size of 10^6\n\n| Cache size | Avg. cache hit latency (μs) | Avg. cache miss latency (μs) |\n|-------|-----|-------|\n| 10^2 | 13 | 14 |\n| 10^3 | 15 | 15 |\n| 10^4 | 16 | 17 |\n| 10^5 | 22 | 18 |\n| 10^6 | 56 | 37 |\n\nIn contrast, fuzzy matching usually incurs significantly higher latency (depending on implementation detail of the fuzzy match algorithm), which grows rapidly with cache size. We implemented a semantic similarity-based fuzzy cache using ```SentenceTransformer('all-MiniLM-L6-v2')``` from the ```sentence_transformers``` library, with a similarity threshold of 0.8 for hit detection:\n\n| Cache size | Avg. cache hit latency (μs) | Avg. cache miss latency (μs) |\n|-------|-----|-------|\n| 10^2 | 57 | 24 |\n| 10^3 | 75 | 70 |\n| 10^4 | 581 | 554 |\n| 10^5 | 10388 | 10317 |\n| 10^6 | 148449 | 148147 |\n\nThese results confirm that fuzzy matching introduces substantial overhead and scales poorly compared to exact match. This is one of the key reasons we adopt exact keyword matching in our system, as discussed in Section 3.2. Additional factors include the difficulty of selecting a universal similarity threshold, which is a common challenge in semantic caching. \n\nOur cache provides a reconfigurable API that allows users to customize key settings, such as maximum cache size, eviction policy, and lookup rules (e.g., fuzzy keyword matching), to suit the needs of specific agentic applications. We will include a more detailed discussion of this API in the final version of the paper. \n\n**#2: Cold-start and domain drift is not discussed.**\n\nThank you for this important point. Cold-start is an inherent limitation of test-time plan caching (in contrast to offline plan caching), as the cache starts empty. During the early stages, the system incurs additional latency and cost from generating new cache entries. To study this, we conduct a time-series analysis of cache warm-up:\n\n| Query percentile | # cache entries | Cache hit rate | Cost | Planning latency (s) | Cache generation latency (s) | E2E Latency (s) |\n|-------|-----|-------|-------|-------|-------|-------|\n| 20th | 15 | 14.29% | $0.59 **(32.07%)** | 260.19 **(27.43%)** | 59.19 **(27.64%)** | 358.71 **(25.72%)** |\n| 40th | 27 | 24.39% | $0.97 **(52.72%)** | 484.88 **(51.12%)** | 130.29 **(60.86%)** | 689.49 **(49.44%)** |\n| 60th | 36 | 36.07% | $1.20 **(65.22%)** | 638.12 **(67.28%)** | 167.89 **(78.41%)** | 926.82 **(66.46%)** |\n| 80th | 42 | 40.75% | $1.63 **(88.59%)** | 820.94 **(86.56%)** | 195.59 **(91.35%)** | 1183.39 **(84.86%)** |\n| 100th | 46 | 48.00% | $1.84 **(100.00%)** | 948.36 **(100.00%)** | 214.11 **(100.00%)** | 1394.56 **(100.00%)** |\n\nAs the cache grows, hit rate increases, and marginal latency and cost decrease over time. In practice, if the target workload is known ahead of time, users can proactively warm up the cache using offline samples before deployment to mitigate cold-start effects.\n\nRegarding domain drift, we agree this is a practical concern for any caching-based system. Cached entries may become stale as task distributions shift. To address this, our system supports configurable cache invalidation policies (e.g., time-based expiration), allowing users to tailor freshness guarantees to their applications. While caching is most effective when domain drift is limited, we will include further discussion on how to mitigate drift in the final version.\n\n**#3: Storing plan templates might leak sensitive workflow information.**\n\nWe agree that security and privacy are important considerations when caching plans, especially when templates are shared across agents from different users. To mitigate this risk, we do not cache raw execution histories. Instead, we extract plan templates by filtering out query-specific details such as user or company names. We hope our work encourages further research on privacy-preserving agent systems and memory mechanisms. \n\n**#4: Generality is not discussed. The solution is demonstrated with a specific large planner and an 8 B re-planner. How well does the approach transfer if those models are swapped for smaller or fundamentally different LLM families?**\n\nThank you for raising this point! We address generality in Appendix C, where we conduct a sensitivity analysis using a range of commercial and open-source models as the large planner LM, the small planner LM, and actor LMs. Our results show that the system consistently improves performance across different model families (e.g., OpenAI, Claude, LLaMA, Qwen) and sizes.\n\n**#5: Exact keyword matching avoids false positives but may miss near-duplicates. Have the authors explored lightweight embedding search or fuzzy matching, and how would that affect hit-rate, cost, and accuracy?**\n\nWe have implemented fuzzy keyword matching in our prototype, and we present some results below. Specifically, we use semantic embeddings to measure similarity between keywords, treating a cache lookup as a hit if the similarity exceeds a predefined threshold. Below, we report the empirical results: \n\n| Similarity threshold | Cache hit rate | Cost | Accuracy | Planning latency (s) | End-to-end latency (s) | \n|-------|-----|-------|-------|-------|-------|\n| =100% | 46% | $1.86 | 85.50% | 1011.82 | 1424.82 |\n| >80% | 54% | $1.15 | 83.00% | 875.31 | 1219.73 | \n| >60% | 64% | $0.93 | 77.00% | 720.29 | 1044.50 |\n\nAs we can observe, lowering the similarity threshold increases the cache hit rate and reduces cost and latency, but at the expense of accuracy. This highlights the inherent trade-off in fuzzy matching: While more aggressive matching improves efficiency, it risks introducing less relevant cached plans. \n\nThe good news is that our cache interface is highly reconfigurable. Users can flexibly enable fuzzy matching and tune the similarity threshold to fit their application's tolerance for semantic drift and performance requirements.\n\n**#6: The paper focuses on token cost; could end-to-end latency numbers be reported (cache lookup + rewrite)?**\n\nWe thank the reviewer for pointing out that latency is an important metric in agent system performance measurement! We evaluated the wall-clock latency of our system and compared it to both accuracy-optimal and cost-optimal baselines. Additionally, we provide a detailed breakdown of latency incurred by each component in our plan caching pipeline. This microbenchmark is based on 100 randomly sampled queries from the FinanceBench dataset, with a cache hit rate of 46% (i.e., cached plans were used for 46 of the 100 queries). As shown in the table below, most of the additional latency in our system comes from LLM-powered cache generation, which takes an average of 3.99 seconds per entry. To further mitigate this overhead, we (1) automatically disable caching when the hit rate is consistently low, and (2) are exploring optimizations such as parallel cache generation and speculative next-query inference. \n\n| Method | Plan latency (s) | Act latency (s) | Keyword extraction latency (s) | Cache lookup latency (s) | Cache generation latency (s) | End-to-end latency (s) | \n|-------|-----|-------|-------|-------|-------|-------|\n| Accuracy-Optimal | 1813.41  |  94.39   | N/A | N/A | N/A | 1959.24 |\n| Cost-Optimal   |  856.75  |  93.31   | N/A | N/A | N/A | 1004.79 |\n| Ours | 1011.82 | 131.44 | 42.29 | < 1s | 215.80 | 1424.82 |\n\nOur system offers a favorable performance trade-off: We achieve significantly lower cost than the accuracy-optimal baseline while preserving high accuracy at the cost of moderate latency, most of which is attributable to one-time cache generation. \n\n**Finally:** We really appreciate your insightful suggestions, which have helped us strengthen the design and the evaluation sections of our work. If the response is helpful, we would be grateful if you could consider adjusting your score accordingly. We are committed to incorporating all promised additions and experiment results in the camera‑ready version to make the paper as valuable as possible to the community."}, {"review_id": "uGEbziWESR", "reviewer": "Reviewer_v2FN", "summary": "Current LLM caching methods (e.g., context or semantic caching) fall short for agentic tasks due to dependencies on external data and dynamic environments. To address this, the authors introduce *agentic plan caching*, a novel technique that captures, stores, and reuses structured plan templates from past executions. By leveraging keyword-based matching and lightweight adaptation models, the system efficiently tailors cached plans to new tasks with similar semantics. Experiments across real-world applications demonstrate a 46.62% average cost reduction while maintaining performance, providing a scalable and cost-effective enhancement for LLM agent deployment. This approach complements existing LLM serving systems, bridging the gap for agent-specific optimization.", "questions": "1. In line 195-199, The Figure 4a does not show the Plan-Act Framework. Maybe it should be Figure 1a?\n2. Could you include evaluation results from additional benchmarks?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper is well-structured, with rigorous experiments and clear methodology. The evaluation on two datasets (FinanceBench and TabMWP) provides strong empirical support for the claims.\n- The writing is clear, and the figures effectively illustrate the framework and results. The distinction between traditional caching and agentic plan caching is well-explained.\n- The idea of caching plan templates for agentic workflows is novel and interesting, which can fills a gap left by existing caching techniques, offering practical cost savings without significant performance degradation.\n\n**Weaknesses:**\n\n- The evaluation is limited to two datasets and a specific agent architecture (planner-actor). Broader applicability to more complex multi-agent systems or diverse workflows remains unexplored.\n- While cost reduction is the focus, other system metrics like latency and throughput are not discussed, which are important for real-world deployment.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive and helpful feedback! We address each concern/question below. \n\n**#1: In line 195-199, The Figure 4a does not show the Plan-Act Framework. Maybe it should be Figure 1a?**\n\nYes, this is a typo. It should be “Figure 1a”. Thank you so much for pointing it out! We will fix it in the final version of the paper. \n\n**#2: Could you include evaluation results from additional benchmarks?**\n\nWe have added more experiment results to include tasks across diverse domains, including long-context reasoning, math problem-solving, etc. We are also actively working to incorporate benchmarks from domains like function calling and web agents. For these experiments, we use GPT-4o as the large planner LM, and Llama-3.1-8B-Instruct as the small planner LM and the actor LM. Below, we show one of the long-context benchmarks from the Minions paper: \n\n| Category | Benchmark | Method | Cost | Accuracy |\n|-------|-----|-------|-------|-------|\n| Long-context reasoning | QASPER (200 random samples) | Accuracy-Optimal | $2.14 | 58.00% |\n| | | Cost-Optimal | $0.21 | 53.00% |\n| | | **Ours** | **$0.78** | **57.00%** |\n| Math reasoning | AIME 2024 (all 30 queries) | Accuracy-Optimal | $1.14 | 64.52% |\n| | | Cost-Optimal | $0.65 | 48.39%  |\n| | | **Ours** | **$0.85** | **61.29%** |\n| Math reasoning | AIME 2025 (all 30 queries) | Accuracy-Optimal | $1.34 | 61.29% |\n| | | Cost-Optimal | $0.60 | 48.39% |\n| | | **Ours** | **$0.81** | **58.06%** |\n\nIf you have a benchmark in mind, feel free to let us know! \n\nWe have done a lot of additional in-depth microbenchmarks and analysis of our caching system to show how it could be adopted in practice, like scalability and online cache management, fuzzy keyword match v.s. exact keyword match, the cold-start effect of our system, etc. Due to space constraint, we won't be able to fit everything in this rebuttal response. Please feel free to take a look at our additional results under other reviews --- We are happy to answer any questions you may have about them!\n\n**#3: While cost reduction is the focus, other system metrics like latency and throughput are not discussed, which are important for real-world deployment.**\n\nWe thank the authors for pointing out additional system metrics that are important in evaluation. We evaluated the wall-clock latency of our system and compared it to both accuracy-optimal and cost-optimal baselines. Additionally, we provide a detailed breakdown of latency incurred by each component in our plan caching pipeline. This microbenchmark is based on 100 randomly sampled queries from the FinanceBench dataset, with a cache hit rate of 46% (i.e., cached plans were used for 46 of the 100 queries). As shown in the table below, most of the additional latency in our system comes from LLM-powered cache generation, which takes an average of 3.99 seconds per entry. To further mitigate this overhead, we (1) automatically disable caching when the hit rate is consistently low, and (2) are exploring optimizations such as parallel cache generation and speculative next-query inference. \n\n| Method | Plan latency (s) | Act latency (s) | Keyword extraction latency (s) | Cache lookup latency (s) | Cache generation latency (s) | End-to-end latency (s) | \n|-------|-----|-------|-------|-------|-------|-------|\n| Accuracy-Optimal | 1813.41  |  94.39   | N/A | N/A | N/A | 1959.24 |\n| Cost-Optimal   |  856.75  |  93.31   | N/A | N/A | N/A | 1004.79 |\n| Ours | 1011.82 | 131.44 | 42.29 | < 1s | 215.80 | 1424.82 |\n\nOur system offers a favorable performance trade-off: We achieve significantly lower cost than the accuracy-optimal baseline while preserving high accuracy at the cost of moderate latency, most of which is attributable to one-time cache generation. \n\nWe agree that throughput is an important system metric for LLM serving systems. We did not evaluate throughput in this work because agentic workloads usually do not emphasize batched inference, which is the primary driver of throughput in traditional LLM serving systems. Currently, the community’s focus is primarily on reducing API cost and improving latency, which our system directly targets. We see exploring throughput improvements, especially through plan caching and reuse in batched settings, as an exciting direction for future work.\n\n**#4: Broader applicability to more complex multi-agent systems or diverse workflows remains unexplored.**\n\nThank you for raising this important point! We agree that agentic systems can exhibit a wide range of architectures and workflow patterns, making comprehensive coverage challenging in our evaluation. In this work, we focus on plan-act agents because this abstraction is widely adopted in both research and industry, e.g., ReAct and its variants, Minions, etc. Moreover, many complex multi-agent systems can be viewed as extensions of the plan-act paradigm, where planning and execution are distributed across agents. As a future direction, we plan to explore how plan caching can be generalized to support a broader range of agent architectures and workflows. \n\n**Finally:** We really appreciate your insightful suggestions, which have helped us strengthen the design and the evaluation sections of our work. If the response is helpful, we would be grateful if you could consider adjusting your score accordingly. We are committed to incorporating all promised additions and experiment results in the camera‑ready version to make the paper as valuable as possible to the community."}]

Author rebuttal:

Meta-review: # Summary 

This paper introduces a caching strategy aimed at enhancing the cost‑effectiveness of employing large language models (LLMs) as agents for complex tasks. The core concept involves **extracting a plan template** from an execution log and storing it in a cache keyed by a **specific keyword**. For subsequent queries, the system first identifies a relevant keyword; if the cache contains a matching entry, the cached plan template is combined with a smaller, more economical LLM to generate the response. If the cache does not contain a suitable entry, the system falls back to using a larger, more expensive LLM to carry out the task. 

The two major components in the proposed caching approach are: 
1. Extracting Keyword: An LLM is used for identifying the keyword t
2. Extracting plan-template:  First action strings are extracted from execution log using a rule-based approach and then LLM is used to remove all the problem-specific details from those action strings.

Their experiments on two benchmarks---FinanceBench and Tabular‑MWP---show an average 46% cost reduction while retaining 96 % of the accuracy of an all-large-LM baseline, with only ~1 % overhead for keyword extraction and cache management. During rebuttal, the authors augment the evaluation with additional domains---long‑context QASPER and math AIME---and provide extensive micro‑benchmarks on latency, cache scalability, fuzzy vs. exact matching, cold‑start, and domain drift. 



# Strengths 

- **Novel**: The problem focused by the paper is novel and would be increasingly important to address as more agentic solutions are adopted. Definetly something that the NeurIPS community would be interested in.  
- **Practical**: Proposed solution is straight forward, practical and adaptable. It uses off-the-shelf components at test-time and do not require a lot of investment/compute to adapt to different problems/domains.
- **Significant Empirical Evalutions**: The experiment results are strong and addition of experiments during the rebuttal make them even stronger.



# Weakness

- **Lack of Alternative Exploration**: The main concern I have is that the paper lacks an in-depth analysis of alternatives that could have been used for keyword extraction and plan-template extraction (or plan abstraction).  (Reviewer 7A5h)
- **Missing Failure Analysis**: It is unclear whether the failures stemmed from the actor LM, from false-positive cache hits, or from incorrect keyword matches. While the rebuttal offered some insight---suggesting that smaller LMs struggle with long‑context reasoning and may generate erroneous actions—a more comprehensive, quantitative analysis is still missing. (Reviewer c5yq)
- **Implications for Benchmarks that require Planning**: Finally, my last concern is about the utility of the proposed approach for benchmarks that specifically require planning. The benchmarks that are used for the analysis are complex reasoning benchmarks but not really planning benchmarks. 



# Unaddressed Minor Concerns from Reviewers 

- **Experiment limited to a Single Architechture**: The paper focuses on React style plan-act architecture. It is not immediately clear if this can be adopted to other architectures directly. (Reviewer v2FN)
- **Privacy/Security Concerns**: The cached plan may have privacy/security concerns, which are not addressed by the framework. (Reviewer RMgA )
- **Generality to other LLM families or smaller models**: The empirical evidence might not generalize to a different model family. (Reviewer v2FN)



# Recommendation Justification
 
The paper proposes a practically valuable and empirically validated technique for reducing serving costs of LLM‑based agents. Authors have addressed all major reviewer concerns with additional experiments and clarifications (Confirming with reviewer on this in a separate discussion). The remaining minor concerns (mentioned above) are natural avenues for future work and do not outweigh the contributions.  

Given the strong reviewer support (average rating 4.2, one “accept” and four “borderline accept”s), the thorough rebuttal, and the relevance to the community, I believe the paper merits inclusion in the conference.
Decision: Accept (poster)