Generative Caching for Structurally Similar Prompts and Responses
Sarthak Chakraborty, Suman Nath, Xuchao Zhang, Chetan Bansal, Indranil Gupta · 2025
Read Generative Caching for Structurally Similar Prompts and Responses by Sarthak Chakraborty, Suman Nath, Xuchao Zhang, Chetan Bansal, Indranil Gupta (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-2511-17565.txt.
Introduction
Sarthak Chakraborty and four co-authors cache language model responses more cleverly for repetitive work. In agentic and workflow settings, prompts recur with small variations on a shared structure. Exact-match caching misses those near-hits, while semantic caching can return a response that ignores a critical difference. Their generative cache instead learns the reusable response patterns across similar prompt structures and synthesizes a customized answer for each new request, aware of what changed.
The system reached an 83 percent cache hit rate while keeping incorrect hits minimal on datasets without repetition. In agentic workflows it raised the hit rate by about twenty percent over standard prompt matching and cut end-to-end execution latency by about a third. The work targets a real cost center: organizations rerunning near-identical model calls thousands of times, where a smarter cache pays for itself quickly.
Catalog record
| CREATOR | Sarthak Chakraborty, Suman Nath, Xuchao Zhang, Chetan Bansal, Indranil Gupta |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-17565
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generative Caching for Structurally Similar Prompts and Responses Sarthak Chakraborty, Suman Nath, Xuchao Zhang, Chetan Bansal, Indranil Gupta Abstract Large Language Models (LLMs) are increasingly being used to plan, reason, and execute tasks across diverse scenarios. In use cases like repeatable workflows and agentic settings, prompts are often reused with minor variations while having a similar structure for recurring tasks. This opens up opportunities for caching. However, exact prompt matching fails on such structurally similar prompts, while semantic caching may produce incorrect responses by ignoring critical differences. To address this, we introduce GenCache , a generative cache that produces variation-aware responses for structurally similar prompts. GenCache identifies reusable response patterns across similar prompt structures and synthesizes customized outputs for new requests. We show that GenCache achieves 83% cache hit rate, while having minimal incorrect hits on datasets without prompt repetition. In agentic workflows, it improves cache hit rate by ∼ \sim 20% and reduces end-to-end execution latency by ∼ \sim 34% compared to standard prompt matching. 1 Introduction AI applications, often composed of AI agents, augment Large Language Models (LLMs) with external tools 24 ; 39 ; 29 , enabling them to interact with their environment and solve complex, multi-step tasks 45 ; 50 ; 40 ; 6 ; 27 ; 28 ; 59 . Many such applications repeatedly address similar task patterns, naturally leading to the construction of structurally similar prompts 12 . For instance, structured repetitive workflows like data entry or customer service agents encounter repetitive queries with minor variations, or cloud operations agents frequently diagnose recurring system faults 47 ; 37 ; 58 . Furthermore, prompt engineering techniques often format prompts with reusable templates (called system messages for AI agents), leading to similar prompts. Prior work has shown that caching and reusing prompts and their associated responses can substantially reduce latency and dollar cost in such repetitive workflows since the number of LLM calls is reduced 2 ; 63 ; 64 ; 42 ; 13 ; 12 ; 11 ; 57 . Existing client-side LLM caches are typically designed as key-value stores 20 ; 35 ; 43 . Traditional exact request (or prompt) matching returns a cached value if the new prompt exactly matches a stored prompt key 23 ; 38 , while semantic caches return a cached response based on the semantic similarity of the new request with a stored prompt key 2 ; 11 ; 12 . Semantic similarity is computed using vector embeddings, where two keys are considered similar if their cosine distance surpasses a predefined threshold. However, existing caching techniques fail in applications where prompt-response pairs exhibit three key properties: (a) Structured Regularity: prompts are not exact or semantically similar, but instead structurally similar , i.e. follow a consistent format (defined in § 2 ), (b) Controlled Variability: prompts show minimal yet important controlled variations, and (c) Predictable Response Pattern: the responses also follow a predictable format, but differ across prompts, remaining correlated with the prompt variations. Consider a web-shopping agent 27 ; 59 ; 17 that queries an LLM to decide its next action from the page content and user instructions. Two example user instructions that satisfy these properties are: (1) buy 12 AAA batteries from Amazon , and (2) buy a USB-C cable from Amazon . Exact prompt matching ( ExactCache in short) treats the two prompts as distinct, resulting in cache misses for both. Thus, it ensures correctness but reduces efficiency, since the prompts need to be identical for cache reuse. In contrast, a semantic caching method such as GPTCache 2 considers them semantically similar, producing a cache hit for instruction 2 but incorrectly reuses the same response from instruction 1, as shown in Figure 1 . Thus, semantic caching improves cache reuse at the risk of erroneous results, which is potentially dangerous if agents perform non-reversible actions. Figure 1 : Comparison of GenCache with existing caching techniques. treats both instructions as distinct and results in cache misses, hence uses LLM to generate responses for both. GPTCache encounters cache hit for Instruction 2, but incorrectly returns the already saved response for a similar prompt. GenCache on the other hand, executes the cached program locally on cache hit to generate the correct response tailored to the input In this work, we propose Generative Cache ( GenCache in short), a new client-side caching technique that balances the performance-correctness trade-off. Unlike traditional caches that return stored LLM responses verbatim on a cache hit, GenCache generates custom responses tailored to the prompt, achieving higher cache hit rates without compromising accuracy. This requires prompt-response pairs to satisfy the three key properties described above, common in AI agents and repetitive workflows. In the earlier example, the two instructions share a similar structure (verb-item-phrase) with minor variations, in verb synonyms ( buy and purchase ) and the item name. GenCache automatically discovers such structural similarity and generates a cache hit. On cache hit for instruction 2, GenCache synthesizes a custom response (similar in structure to the previous response) with the important variation in the item name. Figure 1 depicts this workflow. GenCache clusters structurally similar prompt-response pairs based on their embedding similarity and generates a program that takes the prompts as input and synthesizes the correctly formatted responses as output. This program captures a common pattern of how the prompt maps to the response across all the prompt-response pairs in the cluster, and saves it as a cache. A new prompt request is matched with an existing cluster based on its embedding similarity, and the stored program is executed locally via a runtime like Python interpreter to generate a response. Unlike existing caches that store prompts and their LLM responses, GenCache stores prompts and the program that can generate these responses. Our evaluations on the Webshop dataset 53 demonstrate over 83% cache hit rate and at least 35% cost savings. On a synthetic dataset with higher structural similarity, cache hit rate is above 98%. When integrated with existing AI agents, it reduces the end-to-end execution latency and achieves 20% higher hit rate. In summary our contributions are: • We propose a new caching technique, GenCache , for structurally similar prompts that can generate novel variation-aware responses for new prompts. • GenCache identifies common patterns of generating response from structurally similar prompts within a cluster, and encodes the pattern in the form a program. GenCache then validates the program for correctness and stores it as cache. • We compare our method with synthetic and benchmark datasets, and report our results by integrating it with two agent frameworks that perform repetitive tasks. 2 Problem Definition Repetitive tasks or tasks following a similar template 62 are ideal for GenCache to extract the common pattern between multiple prompt-response pairs. Some common use cases are as follows. Key Use Cases: Apart from the example in § 1 , other use cases are: (1) SRE agents 47 ; 37 ; 58 , which execute documented remediation steps based on system alerts that follow some standardized templates. For example, alerts such as "NSM to RNM connection is lost in useast1" and "NSM to RNM connection is lost in uswest1" differ only by region, yet map to the same troubleshooting documentation, requiring identical actions by