We thank the reviewer for the constructive and helpful feedback! We address each concern/question below.

#1: In line 195-199, The Figure 4a does not show the Plan-Act Framework. Maybe it should be Figure 1a?

Yes, 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.

#2: Could you include evaluation results from additional benchmarks?

We 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:

If you have a benchmark in mind, feel free to let us know!

We 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!

#3: While cost reduction is the focus, other system metrics like latency and throughput are not discussed, which are important for real-world deployment.

We 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.

Our 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.

We 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.

#4: Broader applicability to more complex multi-agent systems or diverse workflows remains unexplored.

Thank 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.

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.

We thank the reviewer for the constructive feedback!

#1: Scalability and cache management are not discussed.

Our microbenchmark reveals two key findings on the scalability of plan caching and cache management.

(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:

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.

(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

In 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:

These 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.

Our 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.

#2: Cold-start and domain drift is not discussed.

Thank 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:

As 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.

Regarding 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.

#3: Storing plan templates might leak sensitive workflow information.

We 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.

#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?

Thank 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.

#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?

We 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:

As 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.

The 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.

#6: The paper focuses on token cost; could end-to-end latency numbers be reported (cache lookup + rewrite)?

We 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.

Our 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.

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.

We thank the reviewer for the kind words and constructive feedback! Below, we address each concern in detail.

#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.

Thank 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:

In 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:

These 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.

To 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:

As 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.

The 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.

#2: Speed of the proposed system?

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.

Our 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.

#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.

For 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.

A 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.

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.

We thank the reviewer for the kind words and constructive feedback! Below, we address each concern in detail.

#1: TabMWP is too simple, need to evaluate on more complex math datasets like AIME.

We 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.

#2: Potential lack of analysis on increased task diversity, e.g. on GAIA.

We 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:

While 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.

If you have more benchmarks in mind, feel free to let us know!

We 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!

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.

I thank the authors for their detailed response. I think the paper is in good shape and it would be strengthened further with a thorough analysis of the trade-off between cache hit rate and the similarity between tasks. I believe the hit rate should be worse as the tasks become more diverse; this is expected and is not considered a weak point. However, it would be useful to see at what point the tasks are too diverse for this framework to remain effective. That said, I thank the authors again, and I will maintain my score.

We thank the reviewer for the kind words and helpful feedback! We address each concern/question below.

#1: The concept of saving abstract plans is not new and has been explored extensively in the case‑based reasoning / planning (CBP) literature.

Although 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: (1) Automatic plan template extraction at test time from unconstrained and open-ended LLM generations, instead of storing hand‑crafted symbolic plans, and (2) Leveraging plan storage and reuse for cost-efficient inference of LLM agents. We will add an explicit discussion contrasting these ideas and citing the survey papers you helpfully provided (Borrajo et al., Spalzzi 2001, Bergmann & Wilke 1996).

#2: Depth of abstraction discussion, and potential lack of experimental domains / analysis.

Section 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.

We 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!

We 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.

#3: When there are multiple possible items in the cache matching the new task, how are they ranked? Have you encountered any such cases?

We 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.

#4: In Figure 1, why is there no link from the context to the planner?

We 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.

#5: In 2.2 (1) Model Specific constraints, why would one want to use a different LLM agent for a task of one agent?

Even 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.

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.