Cost-Efficient Serving of LLM Agents via Test-Time Plan Caching

Qizheng Zhang, Michael Wornow, Kunle Olukotun · 2025

Read Cost-Efficient Serving of LLM Agents via Test-Time Plan Caching by Qizheng Zhang, Michael Wornow, Kunle Olukotun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-14852.txt.

Introduction

Language model agents plan each task from scratch, and that repeated planning drives up cost and wait time. Qizheng Zhang and co-authors propose a memory system in 2025 that saves plans and reuses them for similar new tasks. Older caching tricks from chatbots do not fit agents, whose outputs depend on outside data and changing settings.

Their system pulls plan templates from finished runs, files them by keywords, and adapts them with a small model when a matching request arrives. Across several real agent applications, the cache cut costs by about half and wait time by about a quarter, with quality held steady. The authors offer the method as an add-on for existing serving systems.

Catalog record

CREATORQizheng Zhang, Michael Wornow, Kunle Olukotun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-14852

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cost-Efficient Serving of LLM Agents via Test-Time Plan Caching Qizheng Zhang, Michael Wornow, Kunle Olukotun Abstract LLM-based agentic applications have shown increasingly remarkable capabilities in complex workflows but incur substantial costs 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 agentic applications where outputs depend on external data or environmental contexts. We propose agentic plan caching, a novel approach that extracts, stores, adapts, and reuses structured plan templates from planning stages of agentic applications across semantically similar tasks to reduce the cost 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 agentic applications shows that our system can reduce costs by 46.62% on average while maintaining performance, offering a more efficient solution for serving LLM-based agents that complements existing LLM serving infrastructures. 1 Introduction Agentic applications based on Large Language Models (LLMs) have shown early promise in replicating human performance on a broad range of workflows, from coding [ 24 , 26 , 52 ] to web navigation [ 17 , 21 , 60 ] to open-ended research [ 3 , 8 ] . Many of these LLM-based agents follow a two-stage pipeline that alternates between [ 54 , 39 ] : (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 workflows executed [ 29 , 57 ] and need to interact with external tools and environments [ 38 ] . Specifically, the Plan stage is often implemented via test-time compute techniques [ 11 , 41 ] like chain-of-thought reasoning [ 46 ] , which can require numerous LLM queries and access to expensive LLMs ( e.g., reasoning models). This results in substantial costs for executing agentic workflows via APIs [ 13 , 35 ] or locally [ 33 ] . To reduce LLM costs, methods have been developed to optimize responses to individual queries [ 30 , 59 ] . In particular, caching has emerged as a popular approach, with two primary implementations: Context caching ( e.g., KV cache reuse and prompt caching [ 18 , 53 , 51 ] ) stores internal model states to speed up subsequent generations, while semantic caching [ 10 , 40 , 2 ] stores and reuses (input, output) pairs to accelerate the serving of queries that are similar to historical queries. These caching techniques, however, have significant limitations when applied to Plan-Act agents. These agents often require making data-dependent decisions , i.e., LLM 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 dataset” ) will result in similar high-level plans, but different specific details depending on the characteristics of the dataset provided. Similarly, 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 , which 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 is 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 to 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 task-specific contexts ( e.g., fiscal year and company name in financial data-intensive reasoning [ 35 ] ), rather than employing an expensive model. Although several memory architectures have been proposed to help agents store and learn from past experiences [ 42 , 50 , 44 , 36 ] , these efforts primarily focus on using such memories to improve the agent’s accuracy on completing workflows ( e.g., with fewer hallucinations [ 9 ] or with higher task success rate [ 44 ] ) 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 two applications and find that it reduces costs by 46.62% (on average) while maintaining 96.67% 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 AI 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 LLM-based agents). We design and implement a novel caching system that extracts, stores, adapts and reuses agent-generated plans at test-time. 3. Evaluation of Caching Techniques: We evaluate our agentic plan caching system on top of real-world agent architecture and two datasets/benchmarks, and find that our approach can reduce cost by 46.62% (on average), while maintaining 96.67% of optimal application performance. We open-source our code and artifact upon publication to facilitate further research in caching for efficient agentic AI applications. 2 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 [ 15 ] , math [ 22 ] , or coding [ 14 ] , these applications coordinate multiple models and queries to solve complex tasks, like data-intensive reasoning [ 35 ] , software engineering [ 55 , 45 ] , web navigation [ 60 ] , etc. Many such agentic AI applications, like multi-agent systems [ 43 , 20 ] and cloud-edge LLM systems [ 56 , 35 ] , follow

Read the complete text