Generative Caching for Structurally Similar Prompts and Responses
Authors: Sarthak Chakraborty
Suman Nath
Xuchao Zhang
Chetan Bansal
Indranil Gupta
Venue: NeurIPS 2025 poster ()
Keywords: Generative Caching
Hit Rate Optimization
Repeatable Workflows
LLM Serving Systems
Primary area: infrastructure

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.

Generative Caching for Structurally Similar Prompts and Responses
Sarthak Chakraborty!*
Suman Nath²
Xuchao Zhang?
Chetan Bansal?
Indranil Gupta
Universiity of Illinois at Strbna-Chhmpaln Miicossoft Research
{sc134, Milliy@@illinoiii edu, {sumann, xuchaozhang, chetanb) Umi crosoft. com
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 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. agentic workflows, it improves cache hit rate by ~20% and reduces end-to-end execution latency by ~44% compared to standard prompt matching.
Introduction
AI applications, often composed of Al agents, augment Large Language Models (LLMs) with external tools [28, 40, 33], enabling them to interact with their environment and solve complex, multi-step tasks [45, 50, 41, 2, 31, 32, 59]. Many such applications repeatedly address similar task patterns, naturally leading to the construction of structurally similar prompts [21]. 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, 38, 58]. Furthermore, prompt engineering techniques often format prompts with reusable templates (called system messages for Al 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 [14, 63, 64, 43, 22, 21, 20, 57].
Existing client-side LLM caches are typically designed as key-value stores [7, 11, 12]. Traditional exact request (or prompt) matching returns cached value if the new prompt exactly matches stored prompt key [27, 39], while semantic caches return a cached response based on the semantic similarity of the new request with a stored prompt key [14, 20, 21). Semantic similarity is computed using vector embeddings, where two keys are considered similar if their cosine distance surpasses 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 predictable format, but differ across prompts, remaining correlated with the prompt variations. Consider web-shopping agent [31, 59, 24J that queries an LLM to decide its next action from the page content and user instructions. Two example user instructions that satisfy
Work done during internship at Microsoft Research.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

bateries from
buy AAA
Inteadion
ExactCache
1.go Amra2on com 2 STaarch("1 AAA bamorles) Press Enter
Istonction Iay batteres from
GPTCache
2o 3a Amaron.cam 2 Search 12 AAA tatteten tws Press
Instruction 12 AAA Arazzon
CenCache
2.go Amazznn.com
7..aarn01112 AA4 battorle?)
3. Press Erter
Siniluity
Natchh f
Instraction purchase USB-C calée from Arrzzon
go to Arnzzon coms Search"
2 USB-c cable
2. to Amazonn com Search)
Instuctiio2 purdicse a USB C table from Amsszn
1.go Amazon.ccom
LLB
Gashei
Costed Progiam
Cabler)
Press
from Amazon
3.Press
3.Presa Enter
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
these properties are: (1) buy 12 AAA batteries from Amazon, and (2) buy USB-C cable from Amazon. Exact prompt matching (ExactCache in short) treats the two prompts 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 [14] 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.
In this work, we propose Generative Cache (GenCache short), a new client-side caching technique that balances the performance ceermannce-coreetness trade-off. Unlike traditional caches that return stored LLM responses verbatim on a cache hit, CenCache 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 Al agents and repetitive workflows. In the earlier example, the two instructions share similar structure wverb-ite--phrsee with minor variations, in verb synonyms (huy 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 I depicts this workflow.
GenCache clusters structurally similar prompt-response pairs based on their embedding similarity and generates 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 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 synthetie dataset with higher structural similarity, cache hit rate is above 98%. When integrated with existing AI agents, it reduces the end-to-end exccution 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-awan 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 cases as follows.
Key Use Cases: Apart from the example in $1, other use cases are: (1) SRE agents [47, 38, 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 useast/" and "NSM to RNM connection is lost in uswestl" differ only by region, yet map to the same troubleshooting documentation, requiring identical actions by modifying the affected region. (2) Web agents managing

---

Google Maps often encounter recurring queries with slight variations, e.g., "How long does it take to walk from Univ of Pittsburgh to starbucks on Craig Street?" and "... from Carnegie Mellon University to Univ of Pittshurgh?.. These require generating similar API calls with different parameters. However, GenCache is less suitable for free-form chatbot interactions, which exhibit high prompt diversity, where semantic caching remains more effective.
GenCache is particularly effective for ReAct-style prompting [54] when the expected response is structured action. In this work, we target use cases involving reversible actions, common across many applications like system fault identification (only read queries are issued to databases), adding items a cart an e-commerce website (can be removed if incorrect), checking distances between two endpoints in a map (endpoints can be rectified), etc. GenCache operates only on the final prompt constructed by an agent, which includes all contextual and user-specific personalization logic.
Formal definition of Prompt Characteristies: Let æ be an individual request (or, user instruction) from a set of repetitive requests T. Let (x()) be the constructed prompt passed to the LLM by a client or agent, and (ar) be the corresponding response. Different characteristics of (x.)) and (()) for two requests 21, 22 E T provide distinct caching opportunities.
1. (Identical Prompts) If (xx1 (x2) and ((x1) ((x2), it implies identical input prompts generate the same LLM responses, ideal for exact prompt matching.
2. (Semantically Similar Prompts) If (<(21) ~ a(x2). but (x1) = 3ax2) implies Semantic Caching techniques like GPTCache [14], InstCache [64] and others [20, 21] are ideal.
3. (Structurally Similar Prompts) If a<x) = a2.2. and 3(x) = b1. fzx((2))bz where a1, 02 by, b2 are prompt phrases (e.g.. phrases like "buy" and "from Amazon" " in the prompt "buy item X from Amazon") ") and f(x) is a transformation on x: (e.g., extracting keywords like "item X" from the entire prompt using a regular expression) which are common over multiple requests, GenCache can automatically identify a1, 02 b,, b2 and f()) (may incorporate branching logic) from multiple examples using regex matching over (a()) and B(x)). This allows it to locally generate 3(xx) for any new request v. Unlike ExactCache and semantic caching, GenCache does not require that ((r.) = (x22)- Furthermore, since short prompts by nature exhibit only a handful of deviations in their way to write, GenCache can also capture such minor deviations (typically synonyms) in 01, 02 (for example, "buy" and "purchase"), by using an "OR" operator in the regex pattern.
4. (Structurally Dissimillar Prompts) When neither axx), nor ((x) show commonalities in their structure phrasing, GenCache does not generalize well
3 GenCache Design
3.1 Overview and Runtime Workflow
The overall workflow of GenCache (Figure 2) follows the general caching paradigm, i.e., for each incoming input prompt P. the system first identifies the relevant cache and attempts to reuse it. On cache hit, the response is directly generated by the cached program; otherwise, the prompt is processed by the LLM as usual. Before returning the LLM- LLM-eenerated response, both the prompt and its output are stored in a database so that a cache generation attempt can be made. Cache generation involves-()) cluster structurally similar prompts such that there is consistent pattern in the way an I.MM generates its responses, (II) infer the consistent pattern (we leverage an L.LM) for each cluster and convert it to program, and (III) validate the generated program before caching it for further use. For step II, we use in in-context learning [15, 34] to help the LLM learn the mapping between prompts and responses within each cluster and generate generalized program reflecting that relationship.
Along with the cached program, we store a regular expression that characterizes the structural pattern of prompts within its cluster, which aids in cache selection at runtime. For a new prompt P, at runtime, the system first identifies the closest cluster based on cosine similarity between its embeddings to the cluster center. The stored regex then verifies whether P conforms to the structural pattern of that cluster. If validated and cached program exists, GenCache executes it using runtime like Python interpreter and returns the generated response after sanity checks. Cached programs include sufficient exception-handling blocks to capture cases where the program does not apply to P.
3.2 Prompt Clustering
When a cache miss occurs, the LLM generates a response R for an input prompt P. Similar sets of (P, R) pairs are clustered based on embedding similarity. Since prompts in LLM systems often
3

---

C
Pronpe Yes ar osgent uradyce
PTONTIR
Ciet Cuedi
con pasars can geoeeate outuut foom
and
Cache Store
Classer DatADaan
CaamER inp and Irat Sornagerria Outnut
by:
p
Cache can
uoed??
R
The cote chould take nitrayy tsloving cure and
gralls
DESS ENTUr name
CodeGenLLM
Stineine
Sarniyy Chede
R
The dioult to as cupus spart trom the sode. The formet the ourput dhoud mazc soadiy ac the exappe outura
mould righ?
Program
(a) Runtime Workflow
(b) Generated Program and its prompt
Figure 2: GenCache workflow (solid lines: cache reuse, dotted lines: cache generation). Figure 2a illustrates the runtime workflow-For a new prompt P. the system finds the nearest cluster based on similarity threshold and checks for an available cache for reuse O If suitable cache found, it generates response R after passing sanity checks @ If not, an LLM generates R @ In this case, we store (P, R) in the cluster database ①. Once enough example pairs accumulate in cluster, CodeGenLLM attempts to generate program 2 and store in the cache store 3 after validation. Figure shows the prompt for CodeGenLLM and the generated program.
share large common templates (system messages), which can dominate the embeddings, making semantically unrelated prompts appear similar, considering both prompt and response similarities ensures more accurate clustering. GenCache performs online clustering without limiting the number of clusters. Each cluster is maintained as key-value store, where the key is the cluster ID and the value contains the prompts, their LLM- generrted responses, and corresponding embeddings.
Embedding Generation. Each prompt P is converted into an n-dimensional embedding ep using SentenceTransfforee [37]. However, responses R are typically JSON-structured rather than plaintext agentic settings, containing multiple key-value pairs that encode details about the "action" to be performed. To better capture this structure, we create an embedding array [e,] by computing n-dimensional embeddings for each value of the key-value pair of R. If no existing clusters are found, a new cluster Co is initialized with (P,R).
Similarity Computation. We compute two similarity scores between a new prompt P and each cluster C, one from prompt embeddings and another from response embeddings. The prompt similarity s is the cosine similarity between ep and the cluster prompt centroid e (the mean of all ep embeddings in C.). The response similarity s" is the average cosine similarity between [erl; and the corresponding cluster response centroid [c]], across all indices j. We also ensure that the number of key-value pairs in R matches that of the cluster response centroid.
Cluster Assignment. To assign the input prompt P to cluster C, both similarity scores s and s" must exceed their respective thresholds. Let CP denote clusters with s > TP, and C" denote clusters with s" T". Their intersection, Cint CD n C", represents clusters that meet both conditions. Among these, the final cluster is selected as the one maximizing the combined similarity, i.e., C argmax (s + s").
3.3 Program Generation for Cache
For each cluster C, we use an LLM (CodeGenLLM) to generate a Python program to be stored as cache. Similar ideas have been explored in prior work [16, 19], though primarily for mathemat- ical reasoning. The generated program takes a prompt P as input and produces a response R in the expected key-value format. To generate the program, we provide CodeGenLLM with suf- ficient prompt-response pairs from C as in-context exemplars [49] (or, exemplars) and instruct it to infer the underlying pattern that maps these prompts to responses. The underlying pattern must identify the variations, which are often keywords from the prompts themselves (c.g., in Fig- ure 1), in the structurally similar prompts and use these to generate the response. Since struc- turally similar prompts have a specific sentence structure, a regular expression can typically be used to extract those keywords. Thus, when consistent pattern is detected, CodeGenLLM gen- erates a program that extracts relevant keywords using a regex search and constructs the final response accordingly. Returning our running example Figure 1, CodeGenLLM encodes the con- sistent pattern with a regex r' buy purchase I get (item_name) from Amazon', constructs the response template as actions: (1) go to Amazon.com, (2) Search ( ("match. groups (0) "),

---

Cluster Database
Cache Store
Groud Truhh Resgoret
VoldLLM Prompt
Incaated exxerpiec
ValdLLM
LoL Promet
yes
C"aldd M.L....
if atleast
CodeGenLLM
Program
Retry with Rellccion
Figure Program validation process before storing it as cache. Step numbering remains consistent with Figure 2a, and we only show from ( onwards here. After program generation (): ValidLLM validates that the pegrram-generated responses match expected outputs by using in-context examples in the prompt + It produces arrry for each example 3 If less than y responses match, the system retries cache generation using reflection-bart -ased prompt O Otherwise, stores the validated program as cache ?
and (3) press enter', and writes these in a program which is eventually stored cache. Given user instructions like "buy (item] from Amazon", the program constructs the response by replacing the item name in match. grropsrrruus... (0).
CodeGenLLM's prompt (Figure 2b) includes both the system messages and the user instruction for each in-context example. Including the system message allows the LLM to infer how responses derived from input prompts. Multiple examples guide CodeGenLLM identify consistent pattern, synthesize a program with appropriate regex searches, and capture the necessary variations. The prompt also contains guidelines so that the synthesized program for appropriate error handling, output formatting, and a default [null] | response when regex matching fails. This ensure reliable and well-formed outputs, preventing potential disruptions during agent execution. The full prompt used for CodeGenLLM is included in Appendix. GenCache does not impose strict limits on P or R. length. While short P and R often exhibit the two properties discussed in $1, GenCache applies equally well to longer P and R generated by automated systems (e.g., SRE agents), as our evaluation shows.
A minimum number of exemplars, v, is required before invoking CodeGenLLM, If clusters contain more than & exemplars, all are used in the CodeGenLLM's prompt. However, each cluster is limited to at most 3 exemplars ($3.5), and hence the prompt does not grow indefinitely. Larger v enables CodeGenLLM to easily identify the patterns, but may introduce more noise from outliers in the cluster. We evaluated varying to study this trade-off. Once cluster contains at least y exemplars, program generation is invoked in the background without delaying the client response.
3.4 Program Validation
Before storing a generated program as cache, it is validated for correctness, specifically, whether can process the input prompt, extract relevant keywords, and generate response with appropriate variations in the required format. This validation step ensures that only reliable programs or those with proper exception handling cached.
We use separate LLM, ValidLLM, to validate each generated program. Using the same exemplars employed during program generation ($3.3), the program is executed locally via a Python interpreter to produce progran-generated responses. ValidLLM assesses whether each response matches its corresponding exemplar response, both in content and format. For textual components, it checks semantic equivalence and the presence of key information instead of strict matching (e.g.. "The user wants to purchase Item X" matches with "user wants to buy item X"). Vali ValidLLM returns boolean (0 or 1) indicating correctness for each exemplar, along with justification. This process verifies that the cached program produces correct program- -enerrtte responses for the exemplars.
fewer than a threshold 7 of the program-generann responses match their exemplars, we retry program generation using reflection, incorporating Valid justification feedback into the CodeGenLLM prompt. If at least 7 responses match, the program is accepted and stored as a cache. Figure 3 illustrates this workflow. GenCache limits the number of cache generation retries for each cluster to p to control the cost. The complete prompt for ValidLLM is included in the appendix.
The generated program may overfit to specific exemplars (e.g., contain hardcoded keywords). To address this, we (i) prompt CodeGenLLM to include appropriate error handling blocks ($3.3), (ii) verify that the input prompt conforms to the general prompt structure within the cluster using a stored regex before retrieving the cache ($3.1). On failure, GenCache defaults to using LLM for response.
5

---

3.5 Cache Management
Each cached program is typically under ~5KB so the total cache footprint capped at a few tens of MBs. When the cache is full, the eviction policy discards the least-recently used cache entry while retaining its associated cluster. Clusters are stored in a database allocated a few hundred MBs, though usage remained below 20 MB in all experiments. To prevent unbounded cluster growth, GenCache limits each cluster to 32/ prompt-response pairs. Once full, no new entries are added. We also avoid storing the prompts on cache hit, further reducing database size as hit rates improve. A cached program may still fail for a new request. In such cases, GenCache may regenerate the program for the corresponding cluster, but the total regeneration retries are capped at p.
Experiments
Setup: We implement GenCache as a library exposing an API interface through which clients issuc input prompts. It returns either rache-generatee response or, cache miss, invokes an LLM to generate the response. We evaluate GenCache in two scenarios: (1) standalone user prompts 1$4.1, $4.2) using synthetic data, and (2) integrate with two AI agents ($4.3). While GenCache is compatible with agents from any framework, we evaluate with simple prompt-based agents and leave the incorporation with more performant agent for future work. The first agent is an open- source web navigation agent Laser [31, 8J, built on the OpenAl Chat Completion [1] framework. It plans and executes webpage actions like "Search" and "Buy" to fulfil user instructions. The second agent, FLASH [58], is a cloud-operations agent built using LangChain [6] that diagnose recurring system faults. Given incident description, it retrieves relevant troubleshooting documents via RAG [28] and follows diagnostic steps until the root cause is identified (mitigation is disabled). Both agents use ReAct-style prompting [54]. We use 4P for CodeGenLLM and ValidLLM, with default parameters p = 30, = 50%. T = 0.8, and T = 0.75, unless stated otherwise. Task- specific adjustments are made to CodeGenLLM and Val dLLM prompts as needed. On cache misses, GenCache use CPT-4 to generate responses for FLASH, and GP for all other experiments. We run our experiments on cloud servers with 8-core Intel Xeon CPU and 64 GB memory.
Datasets: For experiments with Laser [8], we use the WebShop dataset [53], simulated e-commerce enviromment featuring 12000+ crowd-sourced user instructions. Experiments with FLASH use incident diagnosis data from Microsoft, collected over 2 months, comprising 298 incidents across five troubleshooting scenarios. The top-1 1 troubleshooting scenario accounts for 69% of incidents, and the t for 93%, indicating high recurring tasks that make caching particularly effective instead of repeated LLM calls. For standalone prompt evaluations, since GenCache targets repetitive tasks with structurally similar prompts, general language understanding benchmarks [44, 51, 60, 56] that evaluate an agent's 's comprehensiveness on diverse tasks are not suitable. Instead, we reuse WebShop instructions, augmenting each with a maximum price, resulting in consistent structure: purchase verb (e.g.. "I want to buy"), followed by an item description with attributes and a price limit. While item details and prices vary across prompts, the overall structure remains stable with only minor phrasing differences, making this dataset well-suited for evaluating GenCache. To evaluate scenario (I), we use WebShop's 's user instructions as seed data and prompt GPT-40 to generate two synthetic prompt sets with the below characteristics. These prompts are then issued to GenCache's 's API interface with the expected response of receiving just the (item name, price limit) tuple.
1. Paran-Only-only the parameters vary while phrasing remains identical. We use GPT-4o to extract the item description (LLM is allowed to rephrase this) and price. We then reformat the instruction using the template "I want to buy {item), under the price range of {price}
2. Param-w- w-ennn-w-yyyyg w-Synonyn--oon both parameters and the verb phrasing vary but the verb-ited ietee-rriccee semantics is maintained. We use GPT-4o to rephrase the instruction by adding some optional words (like "please") at the beginning for a few prompts or splitting the sentence into two. This alters the structure slightly without chaning the semantics.
We compare GenCache to ExactCache and GPTCache [14, 4], widely popular repre- sentative among semantic caching techniques. For ExactCache, we leverage hash-based indexing of prompts. GPTCache, however, uses embeddings similarity for prompt matching. We use the Sentence Bert embedding al1-MiniLM-L6--2 [37] for computing prompt embeddings and the FAISS [25] indexing strategy for similarity search with a similarity threshold of 0.95. We do not compare with prompt-prefix matching techniques [13, 22] as they focus on low-level decoding operations and are orthogonal to GenCache. Our baseline choices are well-detailed in the supplementary material.
Baselines:

---

Param Only
Param w S--nooyym
Method
Hit %
+ve
-ve
Hit
+ve Hit
-ve
ExactCache
( 0.0)
N/A
N/A
0 0.0)
N/A
N/A
GPTCache [14)
90.92 (== 0.02)
0 (1: 0.0)
100 (=: 0.0)
88.71 (=: 0.01)
0 (+: 0.0)
100 (#: 0.0)
GenCache
97.81 (= 0.96)
98.03 (+: 0.05)
1.97 (#: 0.05)
83.66 (#: 6.37)
92.16 021)
7.84 (#: 0.12)
MeeCache-feedback
82.35 (= 1.57)
99.63 (1 0.02)
0.37 (#: 0.02)
68.32 (2 4.85)
95.58 (#: 0.08)
4.4 (#: 0.08)
Table I: Baseline comparison of Hit Rate and its correctness with different prompt datasets
We evaluate GenCache in the following categories:
1. What is the cache hit rate, and how many times does the hit result in an incorrect response?
2. What is the overall cost in terms of the number of LLM calls and the token sizes to create a reusable cache? Does our cache generation cost exceed the savings we get?
3. How well does GenCache perform within repeatable agentic workflows?
4.1 Rit-Rate Measurements
We measure the cache hit rate of each method over 10,000 synthetic input prompts, and report the results in Table 1. Each experiment starts with an empty Cache Store and Cluster Database. The first y input prompts (default y = 4) are therefore used to populate the clusters before caching becomes possible. In addition to cache hit rate, we evaluated the response correctness generated by GenCache using GPT-4. with 5% responses validated through human feedback. GPT-4. 1 checks whether the cached item's 's name and price semantically match the ground truth and whether the item remains searchable in an e-commerce context. This indirectly measures the reliability of Vali i semantic comparison. Each cache hit is classified as either +ve Hit (semantically correct item name, attributes, and price) or a -ve Hit (incorrect or unsearchable entry). We also extend GenCache to reduce negative hits by incorporating feedback from GPT-4. 1 that acts as an oracle semantic correctness verifier. We name this method CeenCache-feedaaee When cache-gence ge-ereteeerdddeee response is identified as a negative hit, GenCache deletes the corresponding cached program, but retains the associated cluster that it can retry generating a new program.
We observe that GenCache achieves over 97% cache hit rate with ~2% negative hits for Param-Only dataset. Since only the parameters (i.e. item name and price) vary, CodeGenLLM effectively learns reusable patterns that can be cached as programs. The few negative hits arise mainly from long or complex item descriptions that lead to suboptimal e- e-Commerce search results, as flagged by GPT-4. and human feedback. For Param-w-Syye w-Synonym where verbs phrases may deviate, the cache hit rate drops to 84%, with a higher false positive rate. Beyond long item descriptions, false positives also arise due to cases where the entire user instruction is broken into multiple sentences. For example, cached pattern like r buy need ppurchase get (item name) ', misfires on the user instruction "want a wireless headphone. need it in black", returning "it in black" as the item. Incorporating feedback in SenCache-fcedbare decreases negative hits. This shows that if client (or an agent) can provide a feedback that the response from cache use resulted in an error, GenCache can adapt and modify the cache.
slightly reduces the overall hit rate due to cache deletions but also
ExactCache exhibits no cache hits, while all GPTCache's ' cache hits are negative. Since there are no prompt repetitions, no responses should be repeated as well. However, GPTCache returns a cached response corresponding to a prompt that shows high similarity to the new request (example in $1),
4.2 Cache Generation Cost vs Savings
GenCache incurs an initial cost for using CodeCenLLM and ValidLLM to generate and validate programs before caching. For caching to be effective, this cost must remain lower than the savings from subsequent cache hits. To evaluate this trade-off, we compute the ratio of LLM calls used for cache creation (cost) to the number of cache hits (savings, i.e., avoided LLM calls). We run GenCache with the default v = 4 on 5,000 input prompts for each dataset type and plot this ratio over time in Figure Initially, the ratio exceeds as GenCache incurs setup costs to build caches. Once the number of prompts surpasses v, cached programs are reused, sharply increasing cache hits and reducing the ratio. The Param-Oniy dataset achieves lower ratio due to higher cache reuse, while Param-w-Synonyn shows a higher ratio due to more variable phrasing.
While Figure 4 shows cost for a fixed v, varying u changes the number of in-context exemplars for CodeGenLLM, affecting the L.LM calls needed to generate reliable, reusable caches. As shown in Table 2 for Puram-w-Synonye prompts across five runs, increasing P consistently reduces LLM calls.
7

---

mnttin Cosl
Cuarre Man
(+ Catt Cactel) (Gaetve 190
Pazn-i Syoorym Paran-Oity
160
LLM calls
140
0-
125
35%
2
32.4
73%
100
4
29.6
6
21.2
10
17.2
15
18.8
2000
9.415
intructione Time
GenCashe
Figure 4: Ratio of no. LLM calls used for creating cache to number of cache hits plotted against incoming prompts in time
Table 2: Total no.
Figure 5: L.M token usage for caching com- pared against the baseline of 'Without Cache'. With no prompt repetitions, ExactCache incurs same cost as the baseline
LLM calls to cre- ate reusable caches
Cache Workflow
Time (s)
Cache lookup (includes identifying similar cluster) Cache retrieval & local program execution (reusing the cache)
0.112
0.064
Cache Miss Workflow
Time (s)
Cache lookup (to detect miss)
0.056
LLM call (to generate a new response)
3.520
Database insertion (to store the prompt-response pair)
0,075
Table 3: Cache Miss and Hit Workflow Times
More exemplars help CodeGenLLM detect recurring patterns and produce reusable programs. Contrary to expectations of diminishing returns, the structural similarity and consistency of prompts reduce noise, so additional exemplars continue to improve pattern reliability. This trend likely generalizes across domains, though longer prompts slightly increase program generation cost.
In addition to reducing the number of LLM calls, GenCache must also minimize token usage, as LLM pricing typically depends on input and output tokens [9]. To evaluate token usage cost, we vary y and compute the average tokens (input output) used per user request during cache creation across five runs (each with 2,000 prompts), comparing it against the cost from cache misses (Figure 5), As baseline, we plot the token usage without caching. Across all caching yields at least 35% token savings per request, reaching up to 73% for 2. As increases, cache construction cost rises due to longer in-context prompts for CodeGenLLM, but plateaus quickly as cache hits become more frequent than cache creations. The cost dip at y 10 because highly reused cache was stored with very few retries. Figure 5 also shows large standard deviations in cache construction and cache miss cost, mainly due to GPT-4o's variability across runs, which caused multiple retries in some cases. Improved prompt engineering like optimized prompting, ewer repeated guardrails, etc. or using a stronger model like GPT-4 can further reduce cache construction cost.
Breakdown of Computational Overheads: A call to GenCache 's API interface follows different steps depending on whether a cache hit or miss occurs. Each call begins with a cache lookup to identify whether a cache is present or not. The lookup consists of:
1. Embedding generation: converting the user prompt into an n-dimensional vector (~ 0.042s)
2. Cluster similarity search: matching the embedding to the nearest cluster (~ 0.009s)
3. Regex Validation: regex-based prompt validation before using the cache, and bookkeeping
During cache hit, all the above three steps for cache lookup executed, followed by retrieving the cache and running the program locally. The total latency is ~0.1 (detailed breakdown in Table 3). Embedding generation accounts for 26.16% of the cache hit workflow, while cluster similarity search adds 4.5%. In cache miss, regex validation is skipped during cache lookup because no cached entry found. However, the lookup overhead (0.056s) and database insertion of the prompt-response pair (~0.075s)) add only 2. % overhead, while an LLM call issued on a cache miss takes ~3.55 on average. Overall, elustering and cache reuse incur negligible overhead while providing significant savings over using an L.LM call to respond to a user request.
4.3 Impact on Agentic Workflows
We evaluate end-to-end performance impact of GenCache two agentic workflows. Since such workflows already leverage ExactCache by default, we deploy GenCache alongside to measure
8

---

Agent
Performance Metries
GenCachh++BrattCacto
ExactCache
No. of API calls
4725
4960
No. of LLM calls for Cache Creation
536
N/A
FLASH
% Cache Hits (ExactCache contribution)
54.7 % (31.1%)
34.4%
Execution Time
39.91s
53.45s
No. API calls
1315
1308
No. of L.IM calls for Cache Creation
100
I Laser
Cache Hits (ExactCache contribution)
(12.8%)
5.7%
Exccution Time
5.02s
5.16s
Table 4: Evaluating benefits of using GenCache in regular agentic workflows
800
Camulatve Count
1000
LLM Calls for Cache Gen.
500
LLM Calls for Cache Ger.
L
400
600
300
400
200
200
100
60
100
160
100
Prompte
(a) Cloud Operations Agent
(b) Web Navigation Agent
Figure 6: Comparison of LLM calls avoided due to cache hit (savings) with the LLM calls incurred for cache creation (cost). As more inputs are processed, the gap between savings and cost widens.
additional benefits. Table 4 summarizes improvements in cache hit rate and execution time, while Figure 6a compares the associated cost and savings.
Cloud-Operations Agent: diagnose an incident, FLASH [58] took 16 LLM calls on average,
including identifying the correct documents, generating coarse and fine-grained plan, and conducting the diagnosis. GenCache improved cache hit rate by 23% achieving 54% overall, compared to ~344 with ExactCache alone. Using GenCache also reduced the average diagnosis time of the agents by 255% Figure 6a illustrates that as more and more incidents are handled by FLASH, the number of LLM calls avoided due cache hits outweighs the LLM calls incurred to create cache which plateaus. The growing gap demonstrates GenCache's s long-term benefits. Out of 536 LLM calls made for cache creation, only 10.4% (56/536) resulted in reusable caches within the workflow; the remaining attempts were flagged as invalid by Val LLLMM. There were also failure cases; across 298 incidents, FLASH failed in only 3 cases (1 (1%) due mapping to incorrect troubleshooting document result of cache hit, but it was non-detrimental since we focused only on reversible workflows.
Web-Navigation Agent: We run Laser [31] on 200 requests from the WebShop dataset [53], which iteratively queries the LLM, first for a rationale, then for the corresponding action type. The workflow typically to search for an item, compare item descriptions to user requirements, and ultimately add it to the cart. Since rationales involve prompt-specific reasoning and structurally diverse, we disable GenCache for those steps. Instead, we enable GenCache only when the LLM selects an action type and its parameters. On average, Laser required 12 LLM calls per request, of which ~50% (1315 total) used GenCache's 's API interface. Using GenCache, we observed 37.2% cache hits (489/1315), with 12.8% of them (63/489) due exact prompt matching- Similar FLASH, see that the savings due to cache hit grow with more prompts while LIM calls for cache generation plateaus in Figure 6b. GenCache incurred additional 100 L.M calls for cache creation. Out of these 100 LLM calls, 34% resulted in creation of reusable caches, while 66% failed (number of retries capped p 30) since the exemplars that were clustered together were too different. Failure cases were: (i) 5.5% of prompts failed due to the cached program repeatedly returning the wrong item from the catalog, and (ii) 11% failed due to formatting errors in cached response- issues that can be addressed through improved prompting, output guardrails, or providing feedback to GenCache. Long and complex item descriptions. which were flagged as negative hits in Table 1. did not lead to failures here, since the multi-step workflow included intermediate LLM calls for generating rationales, which mitigates the impact of complex item descriptions.
4.4 Sensitivity Analysis
Similarity Threshold for Clustering: To analyze the effect of cluster similarity thresholds on

---

cache hit rate, we varied T and T (see $3.2). Experiments were con- ducted on the
TP
T
Hit
dataset with v/ 4 and y 50%. We observe in Table 5 that increasing 7 and T reduced the cache hit rate, as fewer prompts were clustered together, resulting in many small clusters with insufficient exemplars to generate reliable programs. Ei- ther new prompts were often assigned to clusters that did not have any associated cached programs, or in cases where the clusters had existing caches, they exhibited overfitting. In contrast, a low threshold grouped diverse prompts into single cluster, making it harder for CodeGenLLM to learn consistent patterns, again reducing cache hits. Overall, the cache hit rate remains high within a moderate range of similarity thresholds shown in the table.
0.75
0.7
79.72
0.75
0.75
84.48
0.8
0.75
83.66
0.85
0.85
60.02
Table 5: Hit Rate vs similarity threshold
Sensitivity to y: We vary 7, the threshold for the proportion of exem- plars that must match the on Srrrm--w-Syoonye
response, and evaluate
7
Hit %
+ve Hit
dataset using the same setup as in Table 1. We
40%
80.53
91.74
observe in Table that increasing y improves cache hit rate, indicat-
50%
83.66
92.16
ing that at a lower 7 the generated program was not general enough
70%
89.8
92.47
to cater to all the minor variations in the prompt. As y increased, CodeGenLLM created reliable programs by considering more patterns in the regex. At 50% threshold, the generated program may have re- sulted in more cache misses than at 70% or 90%, but observed that the positive hit rate remains similar. Thus, even though the recall is lower, the precision remains high. However, with higher y, more LLM calls are required early in the run, when the database contains only a few prompts, to create reliable caches. Once sufficient prompts are clustered and cached programs are generated, cache misses become rare.
90%
94.8
94.74
Table 6: Hit Rate vs (threshold for matching re- sponses during validation)
Related Works
While GPTCache [14] is a popular semantic caching approach, few works have focused on implementing a caching architecture to make semantic caching usable in real-world settings [17, 29, 35, 63]. SCALM [29] identifies requests frequently visited by users and selectively caches those requests, while [63] improves LLM inference by introducing model multiplexing along with semantic caching. However, [63] relies on the existence of some semantic eaching oracle that can group prompts without false positives. LangCache [20] innovates on the embedding layer by domain-adaptive fine-tuning of the embedding models. MeanCache [21] introduces user-centric semantic caching system that preserves user privacy, and hence employs federated learning to build different embedding models locally at each user device. InstCache [64] introduces predictive caching for short user prompts by predicting user instructions using LLMs and pre-populating the cache.
Semantic Caching:
Prompt Caching: Reusing attention states using Key-Value (KV) Cache is a popular LLM inference optimization for single prompt during autoregressive token generation
[36]. Prompt caching [22, 52, 13, 61, 55, 30] extends this idea to multiple prompts, where KV caches across multiple prompts are reused based on prompt prefix matching. Prompt Cache [22] designs an explicit structure for writing prompts to enable seamless detection of prompt prefixes. SGLang [61] and Chunk Attentonn [55] build efficient data structures for KV cache reuse, while works like Cache-Craft [13] and Cache- Blend [52] implement prompt caching for RAG systems by efficiently reusing and recomputing only the necessary cached chunks. Prompt caching also used in popular LLM services [10, 3) to reduce costs. However, these works orthogonal to GenCache, and they can be used in parallel to reduce costs when GenCache incurs a cache miss.
6 Summary and Discussion
We proposed GenCache, novel caching technique for structurally similar prompts that uses LLM to identify a common pattern to generate responses from similar prompts, and caches the patterns as programs after validation. On cache hit, stored program is executed to generate variation-aware responses. Future works include supporting structurally diverse prompts and non-reversible agent workflows, limitation of the current work. Furthermore, modifying Al agents to identify negative hits and relaying back the feedback to the caching layer can help improve cache accuracy over time. Designing structured human-LLM interaction schemas, like in [22] will enable better caching.
10

---

7 Acknowledgements
This work was supported in part by the Illinois Distinguished Fellowship from UTOC. We further appreciate the anonymous reviewers for their valuable and constructive feedback that greatly improved the manuscript.
References
[1] Chat completions. https://platform itt.ppplaaforoooomaa...... httpa////..//eeeeeaeeeee//a///aa 2025.
[2] Computer-using http:://pppaaalaccc/aaaaa/oo/ppp -aggapapteerrssiiiagggng/nn 2025.
[3] Effectively use prompt caching on amazon bedrock. https://awa amazon cot./ooon.ccmmmog/////o bacchiee-aamiingg/fffett......y 2025.
pwt--pppootptpppppeeeeee on- amazon- bedrook/,
[4] Gptcache A library for creating semantic cache for Ilm queries. readthedocs. 1i/ /lo/e//latst// 2025.
https://gptcache.
[5] Gptcache A library for creating semantic cache for Ilm queries. https:///ithhbb.cm com/ zilliztech/ hrtpccch/.tccche..commoo 2025.
[6] Langehain. attps://wwen www.walanncaainccmm/ 2025.
[7] Langchain model caches. http:://pychoo...nggccccccooo/oo htw.:aacaa..coo////////rrrrrstaa caching/, 2025.
[8] Laser: Llm agent with state-space exploration for web navigation. httpp://githubb.cm Mayer123/LASEN, 2025.
[9] Openai api pricing. https: htrps://openal com/api/pricing// 2025.
[10] Prompt caching with openai, anthropic, and google models. https://wwa https://www.rrompttaae us/
2025.
[11] Redis eaching. http:://rreaass..//eaaaaaaaaaaaa
[12] Sqlite caching.
2025.
[13] Shubham Agarwal, Sai Sundaresan, Subrata Mitra, Debabrata Mahapatra, Archit Gupta, Rounak Sharma, Nirmal Joshua Kapu, Tong Yu, and Shiv Saini. Cache-craft: Managing chunk-caches for efficient retrieval-aus -aummetedd generation. arXiv preprint arXiv:2502. 15734, 2025.
[14] Fu Bang. GPTCache:
An open-source semantic cache for LLM applications enabling faster answers and cost savings. In Liling Tan, Dmitrijs Milajevs, Geeticka Chauhan, Jeremy Gwin- nup, and Elijah Rippeth, editors, Proceedings of the 3rd Workshop for Natural Language Processing Open Source Software (NLP-OSS 2023), pages 212-218, Singapore, December 2023. Association for Computational Linguistics.
[15] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[16] Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. Program of thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. Transactions on Machine Learning Research, 2023.

---

[17] Soumik Dasgupta, Anurag Wagh, Lalitdutt Parsai, Binay Gupta. Geet Vudata, Shally Sangal, Sohom Majumdar, Hema Rajesh, Kunal Banerjee, and Anirban Chatterjee. wallmartcache: distributed, multi-tenant and enhanced semantic caching system for llms. In Pattern Recognition: 27th International Conference, ICPR 2024, Kolkata, India, December 1-5, 2024, Proceedings, Part VII, page 232-248, Berlin, Heidelberg, 2024. Springer-Verlag.
[18] Yuan Feng, Hyeran Jeon, Filip Blagojevic, Cyril Guyot, Qing Li, and Dong Li. Attmemo Accelerating transformers with memoization on big memory systems, 2023.
[19] Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. PAL: Program-aided language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 10764-10799, PMLR, 23-29 Jul 2023.
[20] Waris Gill, Justin Cechmanek, Tyler Hutcherson, Srijith Rajamohan, Jen Agarwal, Muham- mad Ali Gulzar, Manvinder Singh, and Benoit Dion. Advancing semantic caching for Ilms with domain-specific embeddings and synthetic data, 2025.
[21] Waris Gill, Mohamed Elidrisi, Pallavi Kalapatapu, Ammar Ahmed, Ali Anwar, and Muham- mad Ali Gulzar. Meancache: User-centric semantic cache for large language model based web services. arXiv preprint arXiv:2403.0266 2024.
[22] In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandelwal, and Lin Zhong. Prompt cache: Modular attention reuse for low-latency inference. In P. Gibbons, G. Pekhimenko, and C. De Sa, editors, Proceedings of Machine Learning and Systems, volume 6, pages 325-338, 2024.
[23] Zhibin Gou, Zhihong Shao, Yeyun Gong, yelong shen, Yujiu Yang, Nan Duan, and Weizhu Chen. CRITIC: Large language models can self-correct with coot-interective critiquing. The Twelfth International Conference on Learning Representations, 2024.
[24] Izzeddin Gur, Hiroki Furuta, Austin V Huang. Mustafa Safdari, Yutaka Matsuo, Douglas Eck, and Aleksandra Faust. A real-world webagent with plamning. long context understanding, and program synthesis. In The Twelfth International Conference Learning Representations, 2024.
[25] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535-544 2021.
[26] 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, SOSP '23, page 611-626, New York, NY, USA, 2023. Association for Computing Machinery.
[27] Ronny Lempel and Shlomo Moran. Predictive caching and prefetching of query results in search engines. Proceedings of the 12th International Conference on World Wide Web, WWW '03, page 19-28, New York, NY, USA, 2003. Association for Computing Machinery.
[28] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. ings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc.
generation for knowledge-intensive nlp tasks. In Proceed-
[29] Jiaxing Li, Chi Xu, Feng Wang, Isaac M von Riedemann, Cong Zhang, and Jiangchuan Liu. Scalm: Towards semantic caching for automated chat services with large language models. In 2024 IEEE/ACM 32nd International Symposium on Quality of Service (IWQoS), pages 1-10, 2024.
[30] Yuhan Liu, Yuyang Huang, Jiayi Yao, Zhuohan Gu, Kuntai Du, Hanchen Li, Yihua Cheng, Junchen Jiang, Shan Lu, Madan Musuvathi, and Esha Choukse. Droidspeak: Kv cache sharing for cross-llm communication and multi-llm serving, 2024.
12

---

[31] Kaixin Ma, Hongming Zhang, Hongwei Wang, Xiaoman Pan, Wenhao Yu, and Dong Yu. Laser: Lim agent with state-space exploration for web navigation. arXiv preprint :XXv:2309.08172. 2023.
[32] Sami Marreed, Alon Oved, Avi Yaeli, Segev Shlomov, Ido Levy, Aviad Sela, Asaf Adi, and Nir Mashkif. Towards enterprise-ready computer using generalist agent. arXiv preprint arXiv:2503.0186/ 2025.
[33] Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi- Yu, Asli Celikyilmaz, et al. Augmented language models: survey. arXiv preprint arXiv:2302.07844 2023.
[34] Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods Natural Language Processing, pages 11048-1 1064, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[35] Ramaswami Mohandoss. Context-based semantic caching for Ilm applications. In 2024 IEEE Conference Artificial Intelligence (CAI), pages 371-376, 2024.
[36] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. In D. Song, M. Carbin, and T. Chen, editors, Proceedings of Machine Learning and Systems, volume 5, pages 806-624- Curan, 2023.
[37] Nils Reimers and Iryna Gurevych. Sentence- BERT: Sentence embeddings using Siamese BERT- networks. In Kentaro Inui, Jing Jiang, Vincent Ng. and Xiaojun Wan, editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- IJCNLP, pages Hong Kong, China, November 2019. Association for Computational Linguistics.
[38] Devjeet Roy, Xuchao Zhang, Rashi Bhave, Chetan Bansal, Pedro Las-Casas, Rodrigo Fonseca, and Saravan Rajmohan. Exploring Ilm-based agents for root cause analysis. In Companion Proceedings of the 32nd ACM International Conference on the Foundations of Software En- gineering, FSE 2024, page 208-20 218-219, New York, NY, USA, 2024. Association for Computing Machinery.
[39] Patricia Correia Saraiva, Edleno Silva de Moura, Nivio Ziviani, Wagner Meira, Rodrigo Fonseca, and Berthier Ribeiro-Neto. Rank-preserving two-level caching for scalable search engines. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '01, page 51-58, New York, NY, USA, 2001. Association for Computing Machinery.
[40] Timo Schick, Jane Dwivedi- Yu, Roberto Dessí, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zeitlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: language models can teach themselves to use tools. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[41] Manish Shetty, Yinfang Chen, Gagan Somashekar, Minghua Ma, Yogesh Simmhan, Xuchao Zhang, Jonathan Mace, Dax Vandevoorde, Pedro Las-Casas, Shachee Mishra Gupta, Suman Nath, Chetan Bansal, and Saravan Rajmohan. Building ai agents for autonomous clouds: Challenges and design principles. In Proceedings of the 2024 ACM Symposium on Cloud Computing, SoCC '24, page 99-110, New York, NY, USA, 2024. Association for Computing Machinery.
[42] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflex- ion: language agents with verbal reinforcement learning. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances Neural Information Processing Systems, volume 36, pages 1634-8652. Curran Associates, Inc., 2023.
13

---

[43] Simranjit Singh, Michael Fore, Andreas Karatzas, Chachong Lee, Yanan Jian, Longfei Shang- guan, Fuxun Yu, Iraklis Anagnostopoulos, and Dimitrios Stamoulis. LIm-dcache: Improving tool-augmented Ilms with gpt-driven localized data caching. In 2024 31st IEEE International Conference on Electronics, Circuits and Systems (ICECS), pages 1-4, 2024.
[44] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. SuperGLUE: stickier benchmark for generalpurrpose language understanding systems. Curran Associates Inc., Red Hook, NY, USA, 2019.
[45] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):186345, 2024.
[46] Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka- Wei Lee, and Ee-Peng Lim. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. arXiv preprint arXiv:2305.0400/, 2023.
[47] Zefan Wang. Zichuan Liu, Yingying Zhang, Aoxiao Zhong, Jihong Wang, Fengbin Yin, Lunting Fan, Lingfei Wu, and Qingsong Wen. Reagent: Cloud root cause analysis by autonomous agents with toul-augeented large language models. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM '24, page 4966-4974, New York, NY, USA, 2024. Association for Computing Machinery.
[48] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. Chain-of-thouge prompting elicits reasoning in large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc.
[49] Shiguang Wu, Yaqing Wang, and Quanming Yao. Why in-context learning models are good few-shot learners? In The Thirteenth International Conference on Learning Representations. 2025.
[50] John Yang, Carlos E. Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. Swe-agent: Agent-computer interfaces enable automated software engineering. A. Globerson, I., Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 50528-50652. Curran Associates, Inc., 2024.
[51] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Mamning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Ellen Riloff, David Chiang. Julia Hockenmaier, and Jun ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2369-2380, Brussels, Belgium, October-Novente 2018. Association for Computational Linguistics.
[52] Jayy 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 Proceedings of the Twentieth European Conference on Computer Systems, EuroSys '25, page 94-109, New York, NY, USA, 2025. Association for Computing Machinery.
[53] Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20754-20757. Curran Associates, Inc., 2022.
[54] 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.
[55] Lu Ye, Ze Tao, Yong Huang, and Yang Li. Chunk pwefix-aware KV cache and two-phase partition. Lun-Wei Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational
Efficient self-attention with
14

---

Linguistics (Volume 1: Long Papers), pages 11608-11620) Bangkok, Thailand, August 2024.
Association for Computational Linguistics.
[56] Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to- task. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pages 3911-3921, Brussels, Belgium, October-Novembee 2018. Association for Computational Linguistics.
[57] Yifan Yu, Yu Gan, Nikhil Sarda, Lillian Tsai, Jiaming Shen, Yanqi Zhou, Arvind Krishnamurthy, Fan Lai, Hank Levy, and David Culler. Ic-cache: Efficient large language model serving via in-context caching. In Proceedings of the ACM SIGOPS s Symposium on Operating Systems Principles, SOSP '25, page 375-398, New York, NY, USA, 2025. Association for Computing Machinery.
[58] Xuchao Zhang, Tanish Mittal, Chetan Bansal, Rujia Wang, Minghua Ma, Zhixin Ren, Hao Huang, and Saravan Rajmohan. Flash: A workflow automation agent for diagnosing recurring incidents. October 2024.
[59] Yao Zhang, Zijian Ma, Yunpu Ma, Zhen Han, Yu Wu, and Volker Tresp. Webpilot: A versatile and autonomous multi-agent system for web task execution with strategic exploration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 23378-233866 2025.
[60] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric Xing, Joseph E. Gonzalez, Ion Stoica, and Hao Zhang. LMSYS-chat- A large-scale real-world LLM conversation dataset. In The Twelfth International Conference on Learning Representations, 2024.
[61] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, and Ying Sheng. Sglang: Efficient execution of structured language model programs. In A. Globerson, I.. Mackey, Belgrave, A. Fan, U. Paquet, Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 62557-62583. Curran Associates, Inc., 2024.
[62] Shuyan Zhou, Frank Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. Weharena: A realistic web environment for building autonomous agents. In The Twelffh International Conference on Learning Representations, 2024.
[63] Banghua Zhu, Ying Sheng, Lianmin Zheng, Clark Barrett, Michael Jordan, and Jiantao Jiao. Towards optimal caching and model selection for large model inference. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 39062-59094 Curran Associates, Inc., 2023.
[64] Longwei Zou, Tingfeng Liu, Kai Chen, Jiangang Kong, and Yangdong Deng. Instcache: A predictive cache for I1 serving. arXiv preprint 1.Xiv:2411. 13820, 2024.
15

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Have listed the contributions and the claims in the abstract and introduction, along with experimental numbers. These are reflected in the evaluation section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the
paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or 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 expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed in the conclusion section, while the scope limitations are mentioned in the Problem Formulation Section 2. We also discuss it in the Supplementary material.
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 separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (c.g.. independence assumptions, noiseless settings, model well-specification, 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 with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or sexech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed 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?
Answer: [NA]
Justification: There are no theoretical results in the paper Guidelines:
16

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Have tried our best provide all implementation details in the experiments section. We will include prompts that we use for the LLMs our design in the Supplementary material. We also include code along with the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not 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.
be accomplished in various ways. For example, the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
Depending the contribution, reproducibility
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., large language model), then there should either be way to access this model for reproducing the results 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 authors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We will include the code in the supplementary material. The data is open source and specify how generate synthetic data in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
17

---

Please see the NeurIPS code and data submission guidelines lhttps://nips: (bttp::///lps..ccppbbll
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurlPS code and data submission guidelines (httpa: seagiidee/oodSummiisse onPolicy) for more details.
//nips.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones 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 to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have written a 'Setup' subsection at the start of the Experiments section to specify the setting. Other details are presented in the Supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a 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, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, have reported standard deviation in main results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main
claims of the paper.
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 or the standard error of the mean.
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
It is OK report 1-sigma
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 of range (e.g. negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
18

---

Answer: [Yes]
Justification: Yes, have reported the server configuration which experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs 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 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 https://neurip::: cc/public/eetiecccccccc wtt.:iiccechiCuueeeeee.....
Answer: [Yes]
Justification: The research conforms to the Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws regulations in 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: The paper does not have any perceivable negative societal impact. The paper motivates the problem with the help of an application, hence its positive impact will help the applications that fall into the scope of the paper.
Guidelines:
The answer NA means that there 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 negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 generic algorithm for optimizing neural networks could enable people to 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.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.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 ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
19

---

Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators 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 cite the original paper and the librarics that we use. Libraries with specific versions will be included in the requirements file along with the code.
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 or dataset.
The authors should state which version of the asset is used and, if possible, include URL..
The name the license (e-g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode licenses for some datasets. Their licensing guide can help determine the license of dataset. For existing datasets that are re-pat re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
com/datasets has curated
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We share the code in the Supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their sub-
missions 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include 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, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
20

---

Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals 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 an equivalent approval/review based on the requirements your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve any crowdsoureing nor research with any human subjects
Guidelines:
The answer NA mcans that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research 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 we expect authors adhere to 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 the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
Justification: We have used LLM as a component our design and we describe the methodology. The prompts used for these LLMs included in the appendix section of the supplementary material
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: http:://neuui.eeeee wwweeo//eeeeeeee/////O/O/ should or should not be described.
for what
21

---

Appendix
Here, we provide detail about the following topics:
1. Code Link
2. Choice of Baselines
3. Limitations of GenCache
4. Prompts for the L.Mss used
5. Data for FLASH
6. Structural Modification to the Data
7. LLM token usage pattern over time
Code Link
Code link for GenCache available at https://github. wtt.ii...oo/aattteeeeeee coom/aathaa--Cae htaa//saraaakchhkkbbrrrr///
GenCache
Choice of Baselines
GenCache stores the input prompt along with the generated program in cache store. The program can then be executed locally via a runtime like Python interpreter to generate the correct response for the input prompt. Thus, the obvious candidate for baseline is the exact prompt matching (ExactCache), which returns the same response verbatim when the input prompt is identical.
Semantic caching is a widely used technique for LLMs where input prompts are matched to stored prompts based on embedding similarity, and cache hit returns the exact response associated with the matched prompt. There are multiple semantic caching techniques in the literature. We chose GPTCache [14] the representative approach due to its wide popularity and well oollmmannaaine library (over 7500 stars on Github [5]). Other approaches, such as Mean Cache and the method proposed by Gill al.[ improve semantic caching by customizing the embedding model via fine-tuning on domain- and user-specific data. However, these methods are not apen-sourced and, like GPTCache, suffer from a key limitation that datasets without prompt repetition, any cache hit results negative hit. InstCache [64] is recent predictive caching technique that predicts tokens likely to appear in an input prompt and precomputes responses for different token combinations using an LLM. Since InstCache does not have an available open-source code, reproducing its functionality is infeasible without knowledge of the exact prompting strategy used.
Zhu et.al. [63] introduce caching with model multiplexing to improve LLM inference. However, their caching technique is primitive, they check whether the request id is present in the cache or not. If so, it uses the same response verbatim, otherwise, uses LLM generate the response and chooses to add the request to the cache based on novel cache replacement policy. Since GenCache's 's main technique generating an appropriate reusable cache, rather than a cache replacement policy, [63] not an ideal baseline.
Prompt prefix matching is a common caching technique where, if new prompt shares a prefix with a stored prompt, the key-value (KV) caches of the stored prompt are reused to accelerate inference. Many works leverage this idea [22, 10, 26, 18, 55]. Other works like Cache Blend [52] and CacheCraft [13] extend this idea adapt within the RAG framework, while also selectively recomputing attention states when prompt prefixes differ slightly. However, these techniques op- erate at the level of KV cache reuse and represent low-level decoding optimizations, making them orthogonal to our approach. While such methods reduce inference latency, GenCache focuses on reducing the frequency of LLM calls altogether. That said, prompt prefix matching can integrated into GenCache as optimization during cache misses, when LLM invocations are required anyway
Limitations
We scope GenCache's applicability to Al agents that employ structurally similar prompts for repetitive tasks, such as fault diagnosis, web navigation, and computer-using agents. We find that GenCache particularly effective for agents following ReAct-style prompting [54], especially when LLM responses correspond to actions rather than rationales, as these exhibit consistent structural patterns across invocations. GenCache also performs well when variable user instructions are generated automatically (c.g.. by alert monitors in SRE agents), since such prompts naturally maintain high structural similarity.
22

---

Since GenCache relies LLMs to identify consistent patterns and store them as reusable caches, GenCache may identify an incorrect cache for few prompts and consequently generate erroneous responses. Therefore, we recommend using GenCache with strict guardrails and mechanisms to detect such errors. When an agent detects an incorrect secheegeeeatted response through downstream validation, it can provide feedback to GenCache, which then deletes the corresponding cache entry cenCCach-ffeebbccee Hence, agent reliability and the ability to identify or roll back incorrect executions are critical for ensuring GenCache's robustness in practice.
Although CodeGenLLM can identify branching patterns and generate programs with if if-else clauses when provided with sufficient exemplars, GenCache may fail when the number of branches is large, as too few exemplars exist to capture decisions for all branches. Hence, an adaptive strategy is needed modify the cached program dynamically whenever new branch detected, either through agent feedback upon failure or when cache remains unused.
Future works include expanding GenCache to more general prompting structure and agent designs. Prompting strategy for CodeGenLLM and ValidLLM could be improved reduce the number of LLM token usage for generating cache. Some common strategies that can be used to improve the prompting Reflexion [42]. Chain-of- Thought [48], Plan-and Wlan-nnd-Solve [46], self-critic [23], etc.
Prompts for the LLMs used
Note that the prompts are not optimized, and there will be multiple repetitions in the instructions provided. A more optimized prompt conveying the same message will improve the LLM token usage for CodeGenLLM and ValidLLM.
CodeGenLLM Prompt (for Web-Navigation Agent and with WebShop dataset; clients use OpenAl Chat Completion API to interact with the LLM)
You are an expert who can analyze a few example prompts and their corresponding responses and find a common intent from which the responses were generated by the prompts. Once you find the common intent, your task is generate Python program for it.
The example prompts will have a 'system' role, a 'user' role and might have 'function' descrip- tion. Your task analyze the 'text' part within the 'content' subfield of the 'user' role find a common pattern across the examples. The part that is to be analyzed will contain some static phrases and some variable phrases. You need to understand how these parts relate the response. If the responses across all examples are similar (e.g., searching a product), the common pattern must be able identify how to structure the response based on the static and the variable parts of the phrase.
Your job is to:
1. Identify a consistent pattern across examples
2. Generate a Python program that extracts key variables (e.g., item name, attributes, price) using regex and construets the response accordingly.
3. Ensure the program works for arbitrary prompts that follow the same overall structure, even with minor variations or synonyms.
Here are some guidelines for pattern extraction:
1. Write a regular expression that can extract the variable parts of the phrase from the user instruction
2. Find reusable structures the prompts, e.g. "buy (item) from Amazon". Identify and divide the human prompt into verb, item and price phrases.
3. For each part of the phrase, write regex containing synonyms using the examples provided (e.g., if the prompt says "find me", synonyms are "i want to buy" or "i am looking for"). Use up to a MAXIMUM of synonyms per phrase (no more), or the code may raise EOL errors.
4. Use the synonyms to write a regex to identify the item along with its attributes, and the price of the item
5. Generate regex that captures most prompts and is general enough to apply to new prompts, not just the seen ones (e.g. for keyword extraction, identify where the keyword appears in the sentence and extract them from the similar part of the sentence for any arbitrary user
23

---

instruction, but following the same prompt template). Please go through all the examples provided before coming up with the regex pattern. 6. Use re. DOTALL if needed (e.g., multi-line string matching).
Example Input Prompts and their Corresponding Responses
Guidelines for the code output format and other generic guidelines:
1. Analyze only the 'text' portion in the 'content' subfield of the 'user' role.
2. The code must produce an output in the exact format shown in the example responses. For responses in the format of dictionary, there should be no additional key-value pairs, otherwise, there will errors the downstream task that uses this output.
3. Put escape characters for single and double quotes wherever necessary to avoid syntax errors.
4. Replace \ \n with \n in the final code to handle newline characters correctly from the command line input of the prompt.
5. Put ample try/except blocks to catch errors. The code should not crash for any input prompt. If any error occurs, print 'None' and the error.
6. Every if/elif must be followed by an else to handle unmatched conditions. If no conditions are satisfied, the else block should print 'None' along with the reason.
7. The code should be complete with no EOL syntax errors.
Guidelines for Code Execution Format:
1. The code generated will be saved as 'runnable_code py'
2. It will be run as 'python3 runnable_code. py <input-prompe prompt>'
3. The code must execute without any manual intervention and take the entire prompt (save it in the variable name 'prompt') as command-line input <input-prompp which includes both the fixed and the variable parts
Final Instructions (strict):
1. Output only the complete Python code.
2. Do not print any explanation, description, or English text apart from the code
3. The output format should exactly match the format of the example responses.
Now Begin!!
CodeGenLLM Prompt (for Bloud-Operations Agent; clients use Langehain API to interact with the LLM)
You are an expert who can amalyze a few example prompts and their corresponding responses and find common intent from which the responses were generated by the prompts. Once you find the common intent, your task is to generate a Python program for it.
The example input prompts provided below will have prompt template, describing what the LLM was asked to do. This is the static part. It will also contain a dictionary of inputs where each key-value pair
be represented as [abccdeff+ To reconstruct the actual prompt that was used to query the LLM, replace each key ( (fabc") in the template with its corresponding value ('def') ?). The 'def part in the full prompt is the variable part. Your goal is analyze how this transformed prompt maps to the given output and find generalizable pattern that applies across all examples. If the responses across all examples some parameters), the common pattern must be able to identify how to structure the response based on the static and the variable parts.
similar (e.g., calling the same API with
Your job is to:
1. Identify a consistent pattern across examples
2. Generate a Python program that extracts key variables using regex and constructs the response accordingly.
24

---

3. Ensure the program works for arbitrary prompts that follow the same overall structure.
Here are some guidelines for pattern extraction:
1. The common pattern can be code to perform a task (extracting a substring from a string) or even text sentence if all the example responses are sentences with minor changes that do not alter the semantics.
2. For extracting a substring from string, strip leading/trailing whitespace from the string before matching.
3. Generate regex that captures most prompts and is general enough to apply to new prompts, not just the the sentence and extract them from the similar part of the sentence for any arbitrary user instruction, but following the same prompt template). Please go through all the examples provided before coming up with the regex pattern.
(e.g. for keyword extraction, identify where the keyword appears in
4. Use re. DOTALL if needed (c.g., multi-line string matching).
In the examples below, the input dictionary is written in the form:
KEY -> ABC VALUE -> def
Example Input Prompts and their Corresponding Responses
Guidelines for the code output format and other generic guidelines:
1. The code must produce an output in the exact format shown in the example responses without 'Thought'. For responses the format of dictionary, there should no additional key-value pairs, otherwise, there will be errors in the downstream task that uses this output.
2. Do NOT include 'Thought' in the code-generated output, even if it appears the examples.
3. Put ample try/except blocks to catch errors. The code should not crash for any input prompt. If any error occurs, print 'None' and the error.
4. Every if //llif must be followed by an else handle unmatched conditions. If no conditions are satisfied, the else block should print 'None' along with the reason.
5. The code should be complete with EOL syntax errors.
Guidelines for Code Execution Format:
1. The code generated will be saved as 'runnable_code coceeee_codppppp .py".
2. It will be
'python3 runnable_code. py <input-dict>>
3. The code must execute without any manual intervention and take the input dictionary in the form [abc:def] passed as string as command-ling input <input-dict>.
Final Instructions (strict):
1. Output only the complete Python code.
2. Do not print any explanation, description, or English text apart from the code
3. The output format should exactly match the format of the example responses.
Now Begin!!
25

---

ValidLLM Prompt
You are an expert evaluator tasked with comparing multiple LLM-generated outputs to their corre- sponding ground truth answers. Each answer may be a JSON object, string, code snippet. You should validate only the JSON or code portions; ignore any general English descriptions.
Some of the comparisons may be about API call searching for product description that users want to buy. In those cases, consider a match valid the key attributes are preserved, even phrased differently (e.g., "a blue headphone with active noise cancellation" and "blue headphone, active noise cancellation"). Often, the LLM-generated answer will be more verbose (former in the example) than the ground-truth answer (latter in the example).
Some important validation rules are:
1. If the ground truth response in the JSON format, all keys must be present the LLM- generated response well. Extra keys in the JSON mean the result is invalid.
2. If some values within the ISON contain English sentences, check semantic equivalence between the ground truth and the L..M-generated response, not exact wording (e.g. "The product is available in the store" and "The store the product available" are semantically equivalent).
3. For verbose (in LLM LeM--generated response) concise (in ground-truth response) sentences when comparing for certain keys in the JSON, ensure keywords from the concise form appear in the verbose one.
4. For short phrases or code blocks the response (e.g.. "Buy Item", "Search"), check for exact matches.
5. If the LLM-generated response contains 'null' for some keys in the response, while the ground-truth response contains 'None', treat them as equivalent.
6. Ignore punctuation numeric formatting (e.g.. 10 and 10.00 equal) when comparing.
7. Ignore quote style (single double quotes) (e.g.. "content" and 'content' are valid).
Expected Output Format:
"valid": [o 1],
"reason": "The output is correct/incorrect because ...."
}
"valid" list of Os and (length of the list number of comparisons done), where at i'th position means correct match for comparison 'i', and O means a mismatch.
"reason" should give a single combined explanation for why any outputs were incorrect (e.g., extra keys, wrong structure, mismatched values). Do not provide individual explanations per comparison, nor include the comparison number. If an -.LM-egeeraeed response for any comparison includes an error/exception (e.g.. "None: <error>"), include that reason. The objective of the reason field is to easily identify mistakes and rectify, hence be concise.
Do not output anything except the specified JSON.
Strictly follow the format and rules above. Now validate the given examples.
26

---

GPT-4.1 Prompt (used to measure negative hits in $4.1)
You are an expert at checking the correctness of two phrases. You will be given an instruction, and two phrases extracted from that instruction. One of the phrases is the ground truth answer, while the other an answer from our algorithm. The instruction is user request to buy an item within price limit. Both phrases will contain (item name, price limit) tuples.
Your task is to verify whether the extracted phrase from our algorithm matches the item description in the instruction. If the description contains some important attributes that will be required if it needs to be searched in an e-commerce website, but those attributes are missing in the extracted phrase, then it
a match.
The ground truth may have a different phrasing of the item description, which is fine, but the phrase from our algorithm should contain all the necessary information about the item.
You will be given the information the following format: Instruction:
(instruction))
Ground Truth Phrase: [ground_tmie [_ruth]]]
Algorithm Phrase: { ((aggorithm))
Your task is to answer with "yes" if the algorithm's 's response is correct and "no" otherwise. Do not include any other text.
Data for FLASH
For experiments with the Cloud-Operations Agent FLASH, show the distribution of the incidents that map to each troubleshooting scenario in Figure 7a. We see that the first troubleshooting scenario (TS-1) covers 69% of the incidents. Hence most incidents' diagnosis strategy remains same since they map to the same troubleshooting strategy document. We plot the number of repetitions for each incident in Figure 7b. Of the 298 incidents, 253 were unique. We see that 229 incidents never re-occurred, 15 unique incidents recurred twice, while one incident re-occurred times. This shows that using ExactCache cannot produce high cache hit rate.
TS-1 (69.6%%)
TS-2 (24.5%)
TS-3 (5.03%)
TS-4 (0.67%)
200
TS-5 (0.34%)
Num. Unique Incidents
1.50
50
Incident Repetttion Count
(a)
(b)
Figure 7: (a) Percentage of incidents that map to each troubleshooting scenario, (b) Number of repetitions for each incident
Structural Modification to the Data
To complete our experiments in $4.1, we also evaluated on a third dataset with prompt characteristics different from Param-Only and faram-w-Syoone
We call this variation in the prompt set structural, where we expressed each user instruction in 10 different ways with structural variations but semanti- cally identical. For example, "I want to buy Bluetooth headphones, under the price of 150 dollars" is expressed as "For under 150 dollars, want a Bluetooth headphone".
As shown in Table GenCache experiences drop in both eache hit rate and precision when there structural changes in the user instructions, compared to the results in Table 1. The reason for this is that most cached regular expressions fail to generalize when the user instruction structure differs.
27

---

Structural
Method
Hit %
+ve Hit
-ve Hil
ExactCache
0 (# 0.0)
N/A
N/A
GPTCache [14]
96.28 (+ 0.01)
20.72 (+ 0.01)
79.28 (+ 0.01)
GenCache
4.23 (#: 0.21)
72.4 (+ 0.12)
27.6 0.12)
Table 7: Baseline comparison of Hit Rate and its correctness when Prompts had Structural changes
ExactCache has 0% hit rate since prompts were repeated. Thus, argue that in domains with structurally diverse prompts, GenCache is less effective (which is not designed for), and reverting to ExactCache is preferable (hoping that prompts repeat). While GPTCache's negative hit rate continues to be high, it is not 100%, as it occasionally returns correct responses for semantically similar prompts with structural variations. We observe that when GPTCache shows positive cache hit for one user instruction, it tends to return positive hits for all structural variants of that instruction. However, the number of user instructions increases, its reliance approximate nearest neighbor search for semantic similarity often yields incorrect matches, leading to inaccurate cache hits. Since GenCache already experiences high negative hits, do not experiment GenCache-feedbac" on Structural prompt set.
LLM token usage pattern over Time
LUM call for Cache Generation
LLM cal Cache Gencration
LLM avorded with Cache Hif
25K
call avoided with Gache
800K
Qutput Tokan Count
200K
15K
Impult
10K
100K
5K-
1000
1600
2000
2000
1000
2000
2590
Usar Instructioo over Time
User Instructions
(a) Input Tokens
(b) Output Tokens
Figure 8: LLM tokens used for cache creation vs LLM tokens avoided due to cache hit for
LLM cal for Cache Generation
LLM avcided with Cache
300K
Output Tokan Count
3DK
200K
20K
Input
10k
call
0K
0K
call evoided Gache
1000
1750
1250
1750
User instructios over
Instructions over
(a) Input Tokens
(b) Output Tokens
Figure 9: LLM tokens used for cache creation LLM tokens avoided due cache hit for 15
In Figure we showed at least 35% token savings per request on using GenCache. We now show how the LLM token usage varies over time. Figure 8 and Figure 9 plots how the number of input and output tokens varies for 4 and y 15 respectively. For all the plots. the 'blue' line plots the token usage (input or output) when LLM was called for cache generation, while the 'orange' line plots the tokens (input or output) that were saved as a result of avoiding L.LM call due to cache hit. We observe that the LLM token usage during cache generation plateaus after initially being high, while the token savings continue increase as cache hits become more frequent than cache creations over time. While the benefits due to cache hit in input token usage surpass that of cache generation for both v, the output tokens used for creating the cache with v = are still higher than the savings due to cache hit after around 1800 user instructions (even though there is upward trend).
28


Reviews:
[{"review_id": "uPbeRxZJVu", "reviewer": "Reviewer_Wqw4", "summary": "The authors have introduced GenCache, a caching mechanism designed to reduce the number of LLM calls, say in agentic workflows, by caching structurally similar prompts and symbolic cache programs which generates variation-aware responses on cache hits. The core insight is that in specific usecases, structural similarity in prompts often correlates with predictable variations in their corresponding responses. To exploit this, GenCache uses additional LLM calls to identify consistent transformation patterns between prompts and responses within each cluster and learn a transformation program. These learned programs act as dynamic response generators, improving over ExactCache and GPTCache like methods which fail to capture subtle variations that demand different responses.", "questions": "- See Weaknesses Section\n- How are you selecting the exemplars from the cluster to prompt the CodeGenLLM for generating the cache program? \n- While the authors acknowledge that the use case of GenCache is limited to agentic workflows where structural similarities often occur between prompts and response, it is unclear how the proposed caching would perform in agentic use-cases with dynamic workloads where the responses while being structurally similar are data dependent. Imagine a similar use case from Figure 1 but now the plan to look up AAA batteries/USB-C cables on Amazon needs to incorporate specifying min-max cost limit which is user-dependent and must be determined via an external database of user’s expenditure budgets. Can your program learning incorporate such database retrieval or tool call to collect external information?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n- The paper shows a clear motivation for GenCache by comparing with the limitations of existing Semantic and Exact caching mechanisms. \n- GenCache is a promising direction in better weighing the trade-off between LLM-call cost optimisation and accuracy with caching.\n- The structurally similar assumption is showcased and validated in real-life use cases of agentic workflows., where saving on LLM-call is demonstrated with GenCache.\n- The authors have also showcased the limitations of GenCache with experiments when diverse structures start to appear in prompts during caching and the mechanism experiences lower cache hits, laying out the directions for future research and improvements.\n\n\n**Weaknesses**\n- Missing ablation with respect to similarity threshold, minimum prompts per cluster used to create clusters and corresponding cached programs. For instance, experiments to show how quickly each cached program converges and what happens when clusters contain outliers are missing. \n\n- No sufficient reasoning/evidence to support design decisions during program validation. \n    - What is the reasoning behind choosing 50% as the threshold on matched program-generated responses with exemplars? What happens when mismatched cases are mostly due to outliers?\n    - Alternately, what does the mismatch between program generated responses and corresponding exemplars during program validation actually signify? Does it mean that the learned program is less generalisable or there are outliers present? Consequently, how do you make sure that while retrying program generation with reflection, you are not overfitting to outliers and generalising well?", "was_revised": true, "final_justification": "The paper proposes a caching mechanism better than state of the art which would be a valuable addition for the research in this field. The authors have adequately addressed my concerns and based on the discussion, I recommend the paper be accepted.", "rebuttal": "Thank you for your thoughtful suggestions and insightful reviews. Here are our responses to the questions.\n\n1. **Missing ablation with respect to similarity threshold, experiments to show how quickly each cached program converges**\n\n**(Ablation 1) Similarity Threshold for Clustering**\n| $T^p$          | $T^r$                | Hit %  |\n| :---------------:| :------------------: | :------: |\n|  0.75            | 0.7                   | 79.72  |\n| 0.8 (default) | 0.75 (default)   | 83.66  |\n|  0.85            | 0.85                 | 60.02  |\n\nThank you for the valuable suggestions. We conducted an ablation study on the similarity thresholds ($T^p$ and $T^r$ in Section 3.2), which determine the most similar cluster for a given prompt. A new prompt is added to the cluster if the cosine similarity with the cluster centroid crosses the above thresholds. In Sections 4.1 and 4.2, we use default values of $T^p = 0.8$ and $T^r = 0.75$. For this ablation, we varied the thresholds--one lower, one higher.\n\nWe observed that with the higher thresholds, cache hit rate reduced significantly. Higher thresholds led to fewer prompts being grouped together, resulting in many small clusters that lacked the required number of exemplars ($\\nu$) to generate a program. For a new prompt, it often resulted in being mapped to a cluster where there were no cached prompts. Even when a cached program existed, the program failed to extract the item name using regex due to overfitting on limited exemplars.\n\nConversely, lowering the thresholds grouped more varied prompts (despite similar structure) into a single cluster. This variation made it difficult for CodeGenLLM to learn a consistent pattern, again reducing cache hits. \n\nAs suggested, we plan to include a more extensive sensitivity analysis of $T^p$ and $T^r$ in the final version of the paper.\n\n**(Ablation 2) Quick Convergence of each cached program**  \nTable 2 illustrates how quickly each cached program converges, i.e., how quickly a reusable program is created, against varying minimum numbers of exemplars. We see that as we increase the number of exemplars, it consistently reduces the number of the LLM calls required to generate a valid program. This is because the CodeGenLLM can infer the pattern better with more examples and reliably write a regex pattern that can work for a variety of prompts. This is referenced in Line 304. (We noticed a typo in the current version that incorrectly refers to Figure 2 instead of Table 2. We apologize for the oversight and will correct it.)\n\n2. **What is the reasoning behind choosing 50% as the threshold on matched program-generated responses with exemplars?**\n\nWe run a sensitivity analysis by varying the threshold for the proportion of exemplars that must match the program-generated response. We choose three threshold values--40%, 50% (default), and 70%, and run GenCache on Param-w-Synonym dataset (1000 user prompts) with the same setting as described for Table 1.\n\n| Threshold | Hit % | +ve Hit |\n| :-----: | :----: | :------: |\n|40% | 80.53 | 91.74 |\n|50% | 83.66 | 92.16 |\n|70% | 89.8 | 92.47 |\n|90% | 94.8 | 94.74 |\n\nWe see that increasing the threshold indeed increases the cache hit rate. This indicates that with a lower threshold, the CodeGenLLM was able to create a program, but was not general enough to cater to all the minor variations in the prompt, as the reviewer correctly suggested. As the threshold increased, the CodeGenLLM was able to create a reliable program by considering more patterns in the regex and making the program general for more prompts. At 50% threshold, the generated program may have resulted in more cache misses than at 70% or 90%, but the positive hit rate remains similar. Thus, even though the recall is lower, the precision remains high. However, we observed that with higher thresholds, more LLM calls are required early in the run, when the database contains only a few prompts, to create reusable caches. Once sufficient prompts are clustered and cached programs are generated, cache misses become rare.\n\nWe speculate that this sensitivity must also vary with $\\nu$, since $\\nu$ controls the total number of in-context examples used. With more in-context examples, it may be hard to create a reliable cache when the threshold is high.\n\nAs per suggestion, we intend to do a complete sensitivity analysis with more runs in the final version of the paper.\n\n3. **What does the mismatch between program generated responses and corresponding exemplars during program validation actually signify?**\n\nThe primary reason for the mismatch between program-generated response and the corresponding exemplar response is **formatting differences** between the responses.  LLM responses (R) for prompts (P) are structured as **JSON**, not plaintext, because the agents expect a specific format of responses from the LLM. Thus, the formatting differences arise when the exemplar responses are structured as JSON, but program-generated responses are in plain text or they may lack specific key-value pairs present in the exemplars. This resulted in ValidLLM flagging the program-generated response as incorrect.\n\nThe other reason, in certain cases, is that the LLM appeared to overfit to few exemplars from the list of exemplars provided during cache generation. As a result, responses aligned well with those few, but failed to generalize over the rest of the exemplars. This leads to regex mismatches and giving errors like “keyword not found” or only a subtring being extracted due to a more strict regex which does not correctly reflect the ground-truth exemplar response.\n\n4. **How do you make sure that while retrying program generation with reflection, you are not overfitting to outliers and generalising well?**\n\nThe reviewer has correctly pointed out that in some cases, the cached program might overfit to outliers, when the generated program relies on regex patterns that are overly tailored to a few examples (e.g., containing hardcoded keywords) rather than reflecting a generalizable structure.We tackle this in two ways. First, we prompt CodeGenLLM to include exception handling blocks at all steps in the program. If any step fails (e.g., regex does not match with the prompt), the program will return a specific keyword such as “None”. GenCache detects this failure and automatically falls back to the LLM to generate the response.\n\nSecond, after identifying the most similar cluster for a given prompt, we also do a regex check on the prompt structure itself before using the cache. If the incoming prompt structure does not match the prompt structure for which the code was generated, GenCache bypasses the cache and again defaults to the LLM for response generation.\n\n5. **How are you selecting the exemplars from the cluster to prompt the CodeGenLLM for generating the cache program?**\n\nCodeGenLLM is currently prompted using all exemplars within a cluster. For each cluster, we limit its size to 3$\\nu$ in the database, where $\\nu$ is the minimum number of exemplars that must be present in the cluster in order for CodeGenLLM to start generating a program. This constraint ensures that the number of in-context examples used in the prompt for CodeGenLLM is capped by 3$\\nu$.\n\nFurthermore, to prevent the prompt-response pair within a cluster from increasing indefinitely, we append a user prompt-response pair to the most similar cluster in the database only when there is a cache miss and LLM generates the response instead of the cache.\n\n6. **Imagine a similar use case from Figure 1 but now the plan to look up AAA batteries/USB-C cables on Amazon needs to incorporate specifying min-max cost limit which is user-dependent and must be determined via an external database of user’s expenditure budgets. Can your program learning incorporate such database retrieval or tool call to collect external information?**\n\nThank you for highlighting this interesting use case. We clarify that GenCache is designed as an API layer that the agent queries by providing a fully-formed prompt, and it returns a corresponding response. GenCache internally decides whether to use a cache or query an LLM for the response.\n\nImportantly, GenCache’s scope is to use the complete prompt as received from the agent. This prompt is expected to include all the contextual and user-specific information required by an LLM to generate a response. GenCache uses this prompt-response pair to generate a program that can be reused for cache hit. The **agent is responsible for constructing the full prompt**, including any logic to retrieve user profiles from a database, injecting guardrails, or adapting the prompt based on context. \n\nThus, GenCache acts as a caching layer that operates on the final prompt constructed by the agent. We believe that any database interaction or personalization logic falls within the agent's domain and not within the responsibilities of GenCache."}, {"review_id": "uVKwq1woNa", "reviewer": "Reviewer_znMf", "summary": "This paper proposes GenCache, a client-side caching technique for LLMs that clusters prompt–response pairs based on both prompt and response embedding similarities. Once a new prompt’s embedding is close enough to a cluster center, GenCache retrieves the small Python program stored for that cluster and executes it to generate a tailored response. \n\nTo build these programs, GenCache uses a CodeGenLLM with a handful of in-context prompt–response examples to infer the consistent mapping pattern, then validates the generated code by running it on the same examples and asking a ValidLLM to semantically compare each program output to its ground truth. If at least half of the outputs match, the program is accepted and cached; otherwise, it’s retried or discarded. Each cached program takes a prompt as input and produces the correctly formatted response, enabling high hit rates with minimal LLM calls.", "questions": "1. In line 138, the authors write “Since R often contains multiple key-value pairs… Therefore, we create an embedding array [er] by computing n-dimensional embeddings for each value of the key-value pair of R.” But if R is just free-form text (a sentence or paragraph), how should we interpret “key-value pairs”? Are they really embedding each token, or is this only for structured outputs?\n\n2. Do you apply the same multi-embedding approach to prompts, or do prompts always get a single sentencetransformer embedding? What motivated treating prompts and responses differently, especially since prompts can also be quite long?\n\n3. When you claim that “GenCache performs online clustering.” How much CPU/time overhead does this clustering add compared to simply issuing a new LLM call?\n\n4. Will giving more in-context examples (increasing ν) to CodeGenLLM always improve caching performance, or is there a point of diminishing returns?\n\n5. When you say “using the same exemplars from §3.3, we execute the program locally… to obtain program-generated responses,” are those exemplars the ones inside the cluster or the ones provided as in-context examples to CodeGenLLM?\n\n6. You describe validating a program as “error-free,” yet they accept it if only half of the outputs match. Isn’t that just 50% accuracy—why call it error-free?\n\n7. How reliable is ValidLLM’s semantic comparison in practice? Have you done any human evaluation to confirm its judgments?\n\n8. Even after a program is cached, it may still fail on new prompts. I wonder how frequently does that actually happen in their experiments?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "strengths\n\n1. It captures the real-life setting where prompts are structurally similar yet differ in key details; exact-match or vanilla semantic caches fail here, whereas GenCache’s program cache have the potential to returns the correct, variation-aware response.\n\n2. It introduces a “cache-the-program” strategy—store a concise function that transforms the incoming prompt into the answer instead of caching the raw response—keeping the cache lightweight while generalizing across similar prompts.\n\n3. Strong empirical evidence: GenCache achieves a higher hit rate than the baselines and also achieves latency and token savings.\n\nweaknesses\n\n1. Baselines rely on relatively small-context datasets; it is unclear how the regex-driven program will scale to long, multi-paragraph inputs or to irreversible agent actions?\n\n2. CodeGenLLM and ValidLLM both run on GPT-4o/4, which may be costly; demonstrating that a smaller, open model can handle synthesis and validation would strengthen practicality.\n\n3. Accepting a program when only half of the exemplar outputs match (and still called \"error-free\") seems brittle and risks incorrect cache hits in downstream use.", "was_revised": true, "final_justification": "Their response mostly addressed my questions. I main my accept ratings.", "rebuttal": "Thank you for your thoughtful suggestions and insightful reviews. Here are our responses.\n\n## Answer to Questions\n1. (and Q2) **But if R is just free-form text (a sentence or paragraph), how should we interpret “key-value pairs”? Do you apply the same multi-embedding approach to prompts, or do prompts always get a single sentence transformer embedding?**\n\nWe apologize for the confusion, and we will clarify this in the final version. In our case, LLM responses (R) for prompts (P) are structured as **JSON**, not plaintext, because the agents expect a specific format of responses from the LLM. Accordingly, the prompt itself instructs the LLM to produce responses in that exact JSON schema. This is particularly the case in ReAct prompting, where responses are treated as “actions” that the agent must perform. This is why the prompts and the responses are treated differently, where the responses are encoded in a multi-embedding approach, while we use a sentence transformer for prompts.\n\n3. **How much CPU/time overhead does this clustering add compared to simply issuing a new LLM call?**\n\nA GenCache API call consists of cache lookup (to identify whether a cache is present or not), retrieving the cache, and running the program locally. The **overall time for GenCache API call** if there is a cache hit is **0.176s** (detailed computation breakup is provided for the response to Reviewer 3, Q2). \n\nOn the other hand, the **time to issue a new LLM call** takes **~3.5s** on average, which is issued when a cache miss occurs. During cache miss, the cache lookup overhead is 0.056s, and we take an extra **0.075s** to enter the corresponding prompt-response pair into the database, thus incurring an **extra ~2.1% overhead**. Overall, clustering and reusing the cache incurs negligible overhead while providing significant savings over using an LLM call to respond to a user request.\n\n4. **Will giving more in-context examples (increasing $\\nu$) to CodeGenLLM always improve caching performance, or is there a point of diminishing returns?**\n\nAs more in-context examples are provided to the CodeGenLLM, it converges more quickly to generating reliable and reusable programs since it can identify recurring patterns via regex and handle a broader set of prompt variations. Intuitively, we might expect diminishing returns as more in-context examples introduces noise making it difficult for CodeGenLLM to identify a consistent pattern. However, since our prompts exhibit characteristics like (i) prompts follow a consistent format, (ii) while the structure remains stable, certain elements like the item name, price, or optional words like “please” can vary, and (iii) the responses also follow a consistent pattern so that the cached program can generate them by replacing keywords. These characteristics make in-context examples less noisy and hence more examples help in identifying reliable patterns. The trade-off is that increasing $\\nu$ increases the prompt’s context length, thus increasing the cost of program generation.\n\n5. **When you say “using the same exemplars from §3.3, we execute the program locally… to obtain program-generated responses,” are those exemplars the ones inside the cluster or the ones provided as in-context examples to CodeGenLLM?**\n\nWe use the same examples that were used to create the program. We want to verify whether the exemplars that were used to create the cache are giving correct program-generated responses or not. However, we do not want the program generation to stall for outliers. Hence, we accept a program as cache if atleast a proportion of exemplars match.\n\n6. **Accepting a program when only half of the exemplar outputs match (and still called \"error-free\") seems brittle and risks incorrect cache hits in downstream use.**\n\nWe run a sensitivity analysis by varying the threshold for the proportion of exemplars that must match the program-generated response. We choose three threshold values--40%, 50% (default), and 70%, and run GenCache on Param-w-Synonym dataset (1000 user prompts) with the same setting as described for Table 1.\n\n| Threshold | Hit % | +ve Hit |\n| :-----: | :----: | :------: |\n|40% | 80.53 | 91.74 |\n|50% | 83.66 | 92.16 |\n|70% | 89.8 | 92.47 |\n|90% | 94.8 | 94.74 |\n\nWe see that increasing the threshold indeed increases the cache hit rate. This indicates that with a lower threshold, the CodeGenLLM was able to create a program, but was not general enough to cater to all the minor variations in the prompt, as the reviewer correctly suggested. As the threshold increased, the CodeGenLLM was able to create a reliable program by considering more patterns in the regex and making the program general for more prompts. At 50% threshold, the generated program may have resulted in more cache misses than at 70% or 90%, but the positive hit rate remains similar. Thus, even though the recall is lower, the precision remains high. However, we observed that with higher thresholds, more LLM calls are required early in the run, when the database contains only a few prompts, to create reusable caches. Once sufficient prompts are clustered and cached programs are generated, cache misses become rare.\n\nWe speculate that this sensitivity must also vary with $\\nu$, since $\\nu$ controls the total number of in-context examples used. With more in-context examples, it may be hard to create a reliable cache when the threshold is high.\n\nAs per the suggestion, we intend to do a complete sensitivity analysis with more runs in the final version of the paper.\n\n7. **How reliable is ValidLLM’s semantic comparison in practice? Have you done any human evaluation to confirm its judgments?**\n\nWe do not directly measure the validity of ValidLLM’s semantic comparison. But its reliability indirectly reflects the correctness of GenCache, i.e, if ValidLLM determines that a proportion of program-generated responses matches the exemplar, then the CodeGenLLM-generated program can be reused as a cache. We assess the semantic correctness of the responses generated from the stored program.\n\nWe use GPT-4.1 (distinct from GPT-4o used for cache construction) to compare the ground truth exemplar response with program-generated response, classifying each cache hit as positive or negative. Additionally, we sample 5% of cache-hit responses for human evaluation. The combined evaluation (GPT-4.1+human) is reported as positive/negative hits in Table 1. However, we have not carried out a large-scale human evaluation to verify the semantic correctness in practice, though we could report the human-evaluated result separately from the GPT-4.1 evaluated result. We will also make the definitions of the evaluation indicators more explicit in the final version of the paper.\n\n8. **Even after a program is cached, it may still fail on new prompts. I wonder how frequently does that actually happen in their experiments?**\n\nA validated program stored in the cache can still fail on new prompts in two cases. First, regex matching during cache lookup may fail if the prompt structure differs from the one used during cache generation. In this case, we use LLM to generate the response which is then added to the database for program generation in the future. This behavior corresponds to the cache-miss rate in our evaluation (16.3% for Param-w-Synonym with GenCache, as shown in Table 1).\n\nSecond, the regex match may succeed, but the cache-generated response may be incorrect; reflected by the negative hit rate in Table 1. This issue can be resolved if the agent provides feedback indicating that its subsequent operation failed. Upon receiving such feedback, GenCache-feedback deletes the faulty cache and re-initiates the cache generation process for the corresponding cluster.\n\n## Answers to Other Concerns\n1. **Baselines rely on relatively small-context datasets; it is unclear how the regex-driven program will scale to long, multi-paragraph inputs or to irreversible agent actions?**\n\nWe agree with the reviewer that GenCache is effective when prompts exhibit three key characteristics: (1) **Structural Regularity:** prompts follow a consistent format, e.g., the item to purchase always appear between fixed phrases like “buy” and “under the price of X dollars.” (2) **Controlled Variability:** while the structure stays the same, elements like item names, fault regions in system alerts, or optional words like “please” can vary. (3) **Predictable Response Patterns:** the responses generated follow a consistent format, even if they are not identical. GenCache accelerates agents handling repetitive tasks by leveraging this regularity.\n \nImportantly, GenCache *does not limit prompt or response length*. While short, human-written prompts often exhibit the above characteristics, longer multi-paragraph automated prompts (e.g., generated by system monitors) can also show similar characteristics. \n\nCurrently, most humans interact with agents through a chatbot interface where prompts have high diversity. While GenCache may not be suitable for free-form chatbot interactions, we envision that LLM will be integrated into automated workflows where tasks will be repetitive. GenCache is *highly effective* for such use cases. \n\nFor irreversible actions, mistakes can impact the underlying system. Although GenCache-feedback achieves the lowest negative hit rate, we recommend using it only when prompts are fully structured, differing in only attributes. As shown in Section 4.3, multi-step workflows can tolerate some errors, as LLM-generated rationales in subsequent steps may correct errors from earlier steps caused by negative hits.\n\n2. **CodeGenLLM and ValidLLM both run on GPT-4o/4, which may be costly; demonstrating that a smaller, open model can handle synthesis and validation would strengthen practicality.**\n\nWe will definitely consider running GenCache with smaller models like GPT-4.1 mini, GPT-4.1 nano, GPT-3.5, Llama, etc. by replacing the LLM API call."}, {"review_id": "zw6eImLRnv", "reviewer": "Reviewer_7qKt", "summary": "This paper introduces GenCache, a novel generative caching mechanism designed to address the limitations of existing prompt caching techniques for structurally similar LLM prompts with critical subtle variations. Recognizing that recurring tasks in workflows, chatbots, and agents often reuse similar prompts but require variation-aware responses, GenCache identifies and caches validated generative patterns underlying these responses as executable programs. Upon a cache hit, it executes the stored program to efficiently synthesize a new, contextually appropriate response for the new prompt, rather than returning a potentially incorrect static cached response. The authors demonstrate that GenCache achieves a high cache hit rate (83%) with minimal negative hits on datasets lacking exact prompt repetition and significantly improves performance in agentic workflows.", "questions": "1. The author mentioned that the overall size of the cache is only tens of Mb, which is very exciting, but I noticed that after the cache is built, the clusters do not disappear, and the clusters contain a large number of dialogue inputs and outputs, as well as vectorized representations of these inputs and outputs. Obviously, the size of this information is much larger than the python files in the cache, and the author should add how much space this information will take up;\n2. Other computational overhead: The author experimentally proves that GenCache can effectively reduce the computational overhead caused by LLM reasoning. However, GenCache needs to calculate the n-dimensional vector representation of all inputs and calculate its similarity with all clusters. The author should take this part of the computational overhead into consideration;\n3. Experimental details: The experimental setting is unclear. The author did not explain how the specific synthetic prompt set in Table 1 was synthesized, what the specific content is, and how the evaluation indicators were calculated. It is recommended to refer to the explanation of the evaluation indicators in GPTCache to further supplement the experimental details.\n\n\nFormat error: 1) The author mentioned \" As shown in Figure 2 with Param-w-Synonym prompts \" in line 304, but it should refer to Table 2; 2) This seems to be a more serious error. The author mentioned \" The prompt used for ValidLLM is included in the supplementary material.\" in line 206, but I did not find any appendix in the article. The author also lacked an explanation of the experimental details and prompt content of the paper. Did the author forget to attach an appendix to the paper?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The first dynamic LLM cache: Previous studies could only retrieve static LLM replies by retrieving similar caches. GenCache generates Python code through LLM to achieve more flexible cache reading. Even when facing inputs that have never appeared before, it can extract key information through Python code and generate replies.\n2. Higher hit rate and efficiency: Experiments on synthetic data and webshop datasets show that GenCache has a higher hit rate and can effectively reduce the overhead of LLM reasoning.\n\nWeakness:\n1. As the author said, Python programs usually implement scalable LLM caches through regular expressions, which means that this method is often only suitable for short dialogue outputs with format requirements. However, regular expression-based methods often have little effect on open dialogues and long text tasks, because such dialogues usually do not have a strict format, and it is difficult to extract information from long texts through regular expressions.", "was_revised": true, "final_justification": "Thanks to the author for the response. It addressed the raised concerns. I have revised my score accordingly.", "rebuttal": "Thank you for your thoughtful suggestions and insightful reviews. Here are our responses to the questions.\n\n## Answer to Questions\n1. **The clusters do not disappear, and the clusters contain a large number of dialogue inputs and outputs, as well as vectorized representations of these inputs and outputs. Obviously, the size of this information is much larger than the python files in the cache, and the author should add how much space this information will take up**\n\nIt is true that we retain the clusters, which take up space. These clusters are necessary at inference time for matching a new prompt with the nearest cluster centroid. \n\nEach cached program is typically under 5 KB and often less than 1 KB. In our experiments, GenCache generated an average of three reusable cached programs per experiment, amounting to roughly *15 KB* of cache. In addition, the database size remained under *20 MB* on running GenCache‑feedback on the Param‑w‑Synonym dataset (Table 1).\n\nTo ensure cluster sizes remain manageable, we apply two key constraints: (1) We cap each cluster to hold no more than $3\\nu$ exemplars, and (2) We avoid storing prompts that result in cache hits, which helps eliminate redundant data. With higher cache hit rates in the Param‑Only dataset, fewer prompts are stored, resulting in even smaller cluster sizes compared to Param‑w‑Synonym.\n\n2. **However, GenCache needs to calculate the n-dimensional vector representation of all inputs and calculate its similarity with all clusters. The author should take this part of the computational overhead into consideration**\n\nThank you for the suggestion, we will consider it while reporting results in the final paper. For experiments on the Param‑w‑Synonym dataset (Table 1), here’s the GenCache API call timing breakdown based on cache hits vs. misses:\n\n\n| **Cache Miss Workflow**                                                 | **Time (s)** |\n|---------------------------------------------------------------------------|--------------|\n| Cache lookup (to detect miss)                                         | 0.056        |\n| LLM call (to generate a new response)                           | 3.520        |\n| Database insertion (to store the prompt-response pair)  | 0.075        |\n\n| **Cache Hit Workflow**                                                                  | **Time (s)** |\n|---------------------------------------------------------------------------------------|--------------|\n| Cache lookup (includes identifying similar cluster)                         | 0.112        |\n| Cache retrieval & local program execution (reusing the cache)     | 0.064        |\n\nThe Cache lookup itself consists of:  \n(1) *Embedding generation*: converting the user prompt into an n‑dimensional vector (avg 0.039 s)  \n(2) *Cluster similarity search*: matching this embedding to the nearest cluster (avg 0.008 s)  \n(3) Validating the user prompt by a regex check before reusing the cache, and additional bookkeeping accounts for the remainder\n\nThe time taken for cache lookup differs between cache-hit and cache-miss workflows. During a hit, all three steps are executed; during a miss, the regex validation step is skipped because no cached entry is found.\n\nEmbedding cost accounts for **22.16 %** (embedding generation cost / (cache lookup + cache retrieval and program execution)) of total cache reuse time, while cluster matching adds **4.5 %**.\n\n3. **The experimental setting is unclear. The author did not explain how the specific synthetic prompt set in Table 1 was synthesized, what the specific content is, and how the evaluation indicators were calculated.**\n\nWe are sorry for the confusion regarding the experimental setting. Here are some clarifications (will add in the final version). To generate synthetic prompts in Table 1, we used WebShop’s user instructions as seed data and prompted GPT-4o to create the required dataset. For example, consider the WebShop user instruction: *“Find me a high-speed dual-style package with a 12\\\" power amplifier car subwoofer, and price lower than 190.00 dollars.”*\n\n* **Param-Only**: We prompted GPT-4o to extract the item description (e.g., *“high-speed dual-style package with a 12\" power amplifier car subwoofer”*) and maximum price (e.g., “190 dollars”). The LLM was allowed to rephrase the item description. We then rephrases the instruction using the template: *“I want to buy {item name with attributes}, under the price range of {price}.”* This produces a new instructions such as *“I want to buy a car subwoofer with a high-speed dual-style package and a 12\\\" power amplifier, under the price range of 190.00 dollars.”* We applied this to all WebShop user instructions..\n\n* **Param-w-Synonym**: We extracted item name, attributes, and price and re-prompted GPT-4o to rephrase the instruction by adding the optinal word “please” at the beginning for 10% of the prompts or splitting the sentence into two for 5% (e.g., “Find me…car subwoofer. I want it under…190.00 dollars.”). This alters the structure slightly without changing its semantics. We didn’t explicitly enforce synonym replacement (e.g., replace 'buy' with 'purchase') since the WebShop instructions already include diverse phrasings (e.g., “buy”, “find me a”, “I’m looking for”, “I need a”).\n\n**Evaluation Indicators:**  \n* *Hit %*: a hit occurs when GenCache identifies a cluster with a corresponding cache.  \n* *+ve Hit*: the proportion of hits where the item name, attributes, and price are semantically correct.  \n* *-ve Hit*: the proportion of hits where the item name is not semantically correct for  search purposes.  \n\nSemantic correctness is evaluated using GPT‑4.1 (distinct from GPT‑4o used for cache construction) by comparing the ground truth exemplar response with the program-generated output. We’ve described this in Lines 270–272, but we will make these definitions more explicit in the final version of the paper.\n\n4. **Format Error**\n\n1) We apologize for the oversight and we will correct it  \n2) The appendix was added as supplementary material and was not part of the main pdf\n\n## Answers to Other Concerns\n1. **This method is often only suitable for short dialogue outputs with format requirements. However, regular expression-based methods often have little effect on open dialogues and long text tasks, because such dialogues usually do not have a strict format, and it is difficult to extract information from long texts through regular expressions.**\n\nWe agree with the reviewer that GenCache is effective when prompts exhibit three key characteristics: (1) **Structural Regularity:** prompts follow a consistent format, e.g., the item to purchase always appear between fixed phrases like “buy” and “under the price of X dollars.” (2) **Controlled Variability:** while the structure stays the same, elements like item names, fault regions in system alerts, or optional words like “please” can vary. (3) **Predictable Response Patterns:** the responses generated follow a consistent format, even if they are not identical. GenCache leverages the structure and consistency in the prompts and responses to accelerate agents workflows that handle repetitive tasks. \n\nImportantly, GenCache *does not impose strict limits on prompt or response length*. Human-written, short dialogue prompts often exhibit structural regularity and controlled variability; however, longer prompts generated by automated systems (like troubleshooting agents) can also show similar characteristics. \n\nAlthough GenCache is less suitable for free‑form chat interactions with varied prompt structures, it is *highly effective* for a growing set of use cases, e.g., in agentic systems dealing with short use instructions and automated workflows. As more agents automate repetitive tasks, such as API orchestration and system diagnostics, GenCache’s applicability will exapnd."}, {"review_id": "ohNVMtfwQ4", "reviewer": "Reviewer_6e2p", "summary": "This paper introduces GenCache, a method for leveraging previous LLM responses to handle partially matching prompts in LLM-based web agents that perform repetitive tasks. In a preprocessing stage, GenCache performs clustering of prompts in a dataset and generates a regular expression for detecting and preprocessing prompts in each cluster, and it generates code for common operations for the prompts in each cluster. During inference, it retrieves cached code and adapts it by appropriately substituting variables. Unlike existing caching methods that reuse cached responses without modification, GenCache caches code templates and dynamically adapts them to new inputs, although its current design is tightly coupled to a specific task, which may limit its applicability to broader use cases. Experimental results on the WebShop dataset show a high cache hit rate exceeding 80% and a low negative hit rate below 10%.", "questions": "Please let me know if there are any inaccuracies or misunderstandings in the points raised under Weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The main limitation of this paper lies in its narrow focus on the web agent task, and I recommend revising the title to better reflect this scope and avoid misleading readers. Nevertheless, the paper makes a meaningful contribution toward addressing the core challenge of leveraging prior LLM responses for similar prompts and proposes a practical and effective solution. Overall, I consider this work to be above the acceptance threshold.\n\n### Strengths\n\n* This paper targets a common and fundamental challenge of leveraging previous LLM responses for similar or partially matching prompts.\n* The proposed method offers a practical and effective approach to leveraging partial matches in LLM caching. Although it is tailored to a specific use case involving web agents performing repetitive tasks, the core idea has the potential to generalize to a broader range of applications.\n\n### Weaknesses\n\n* The method is designed for a specific application\n\nThe title suggests that this paper introduces a generalizable method. However, the work specifically targets LLM-based web agents performing repetitive tasks. I recommend either revising the title to more accurately reflect this narrow scope or extending the method to support a broader range of applications.\n\nThe proposed method relies on regular expressions to detect and preprocess prompts that match cached patterns, which restricts its applicability to tasks with limited prompt diversity. This constraint significantly limits the generalizability of the approach and is the primary reason I did not assign a higher score.\n\nAlthough the current method is reasonable as an initial step, I believe the proposed framework has potential for greater robustness. For example, incorporating a preprocessing of prompts or a post-hoc revision step to modify the code using small LLMs could help generalize the method while still maintaining low computational cost.\n\n* Limited evaluation domains\n\nThe proposed method is evaluated solely on a single dataset, WebShop, which appears to be particularly well-suited to the strengths of the approach. I recommend conducting evaluations on additional datasets that involve more diverse operations in order to better understand the limitations and generalizability of the method.", "was_revised": true, "final_justification": "The authors' response confirms that my initial understanding of the paper was largely accurate. Accordingly, **I have increased my confidence in my review and consider the quality of the paper to be above the threshold for acceptance.**\n\nHowever, I remain concerned that evaluation on a single dataset limits the persuasiveness of the empirical evidence. Therefore, I will maintain my current score and consider \"4: Borderline accept\" to be an appropriate assessment.", "rebuttal": "Thank you for your thoughtful suggestions and insightful reviews. Here are our responses to the weaknesses pointed out.\n\n1. **The proposed method relies on regular expressions to detect and preprocess prompts that match cached patterns, which restricts its applicability to tasks with limited prompt diversity. This constraint significantly limits the generalizability of the approach**\n\nWe agree with the reviewer that GenCache is effective when prompts exhibit three key characteristics: (1) **Structural Regularity:** prompts follow a consistent format, e.g., the item to purchase always appear between fixed phrases like “buy” and “under the price of X dollars.” (2) **Controlled Variability:** while the structure stays the same, elements like item names, fault regions in system alerts, or optional words like “please” can vary. (3) **Predictable Response Patterns:** the responses generated follow a consistent format, even if they are not identical. GenCache is designed to accelerate agents that handle repetitive tasks by leveraging the structure and consistency often found in their prompts and responses. \n\nCurrently, most humans interact with agents through a chatbot interface where prompts may have high diversity. While GenCache may not be suitable for free-form chatbot interactions which shows high prompt diversity, we envision that LLM will be integrated into automated workflows where tasks will be repetitive. GenCache is *highly effective* for such use cases. As more agents automate repetitive tasks, such as API orchestration and system diagnostics, GenCache’s applicability will exapnd.\n\n2. **I recommend either revising the title to more accurately reflect this narrow scope or extending the method to support a broader range of applications.**\n\nThank you for this thoughtful observation and we will consider revising the title. We agree that the current title may imply a broader applicability than what is demonstrated in the paper. While GenCache is a powerful technique, it is not a universal caching solution for all prompt-response scenarios. Its effectiveness relies on the prompt-response characteristics as described in the answer above. These allow GenCache to generate response suitable for the prompt by reusing cached programs, making it well-suited for repetitive agent workflows.\n\nTo better reflect this scope, we will consider narrowing the title accordingly. Additionally, we will include a “Future Work” section outlining how GenCache could be extended or used with other caching solutions to support more general applications.\n\n\n3. **Incorporating a preprocessing of prompts or a post-hoc revision step to modify the code using small LLMs could help generalize the method while still maintaining low computational cost.**\n\nWe agree that incorporating prompt preprocessing or post-hoc code modifications could help extend GenCache to support a broader range of prompt variations. This could enable GenCache to operate effectively even in scenarios with higher prompt diversity. However, identifying when users employ different templates to express semantically similar prompts is challenging, which itself *may* require an LLM call that we wanted to avoid in the first place. This variability can have two key implications:  \n(i) Cache creation cost *may* increase, as a wider range of prompt structures makes it harder for CodeGenLLM to detect consistent patterns;  \n(ii) Positive hit rate *may* decrease, since mismatches between prompt templates and cached entries may lead to incorrect cache selections.\n\nFor GenCache to be effective, we want to maintain a high positive hit rate and low cache creation cost, both of which rely on structural regularity and some predictability in prompts. That said, exploring how to balance generalizability with caching accuracy is a promising research direction for future work, and we plan to investigate this further.\n\n4. **Limited Evaluation Domain**\n\nThank you for your suggestion. We agree that evaluating GenCache on a wider range of datasets would strengthen its generalizability. In addition to WebShop, we have also experimented with a proprietary dataset on a cloud-operations agent that diagnoses recurring system faults. This dataset aligns well with our use case, as the prompts are generated from an alert monitoring system and follow a static template, making them ideal for GenCache’s strengths in handling repetitive, structured prompts.\n\nWe are actively exploring other datasets, where user tasks are repetitive and prompts follow a consistent format with minor variations. While many public datasets are designed to test agent capabilities across diverse and unstructured prompts, making them less suitable for GenCache, we recognize the value in expanding our evaluation. In particular, we plan to explore datasets such as WebArena and GAIA, which may offer a better fit for our methodology."}]

Author rebuttal:

Meta-review: This paper introduces a generative caching mechanism for LMs that targets structurally similar prompts. The primary contribution is a novel 'cache-the-program' approach where, instead of storing static responses, the system caches small, executable programs that generate variation aware outputs, improving hit rates and reducing latency in repetitive, agentic workflows.

All four reviewers are in agreement on the paper's acceptance, identifying its key strengths as the novelty of the generative caching approach, its practical utility for agentic workflows, and its strong empirical results. The initial reviews raised several points for clarification, questioning the method's limited scope beyond structured prompts, the lack of detail on computational overhead, and the absence of ablation studies for key hyperparameters. The reviewers were satisfied with the authors' detailed response, which provided new results and clarified the method's intended application.

For the camera-ready version, I recommend that the authors integrate the detailed clarifications and new results from their rebuttal into the main body of the paper. This includes: (1) the new ablation studies on key hyperparameters like clustering and validation thresholds, (2) the detailed breakdown of computational overheads for cache lookup and generation, and (3) the expanded discussion on the method's scope, clearly positioning it for structured, repetitive workflows rather than general-purpose chat.
Decision: Accept (poster)