Skip to content

Generative Caching for Structurally Similar Prompts and Responses

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

GenCache is a client-side LLM caching system that handles structurally similar (but not identical or semantically equivalent) prompts by generating reusable Python programs that synthesize correct, variation-aware responses at runtime. Instead of storing responses verbatim, it caches a program that extracts variable parts from new prompts and fills a response template. On agentic benchmarks it achieves 83% cache hit rate with ~34% latency reduction.

Problem

Exact-match caches miss structurally similar prompts with minor variations; semantic caches (e.g., GPTCache) over-match and return incorrect responses because they ignore variation-critical differences. Neither handles the case where prompt structure is regular, variability is controlled, and responses must co-vary with the prompt—the regime typical of repeatable agentic workflows and SRE automation.

Method

GenCache operates as a three-phase pipeline:

  1. Clustering: Incoming prompt-response pairs \((P, R)\) are embedded via SentenceTransformer; a new pair is assigned to cluster \(C = \arg\max_{C^p \cap C^r}(s_p + s_r)\) where \(s_p\) and \(s_r\) are cosine similarities to cluster centroids for prompt and response embeddings respectively, both exceeding thresholds \(T^p = 0.8\), \(T^r = 0.75\).

  2. Program generation: Once a cluster accumulates \(\nu \geq 4\) exemplars, a CodeGenLLM (GPT-4o) is prompted with those pairs via in-context learning to synthesize a Python function that uses regex to extract variable keywords from a prompt and construct the corresponding response. A regex characterizing valid prompt structure is also stored alongside the program.

  3. Validation and cache hit: ValidLLM checks program-generated responses against exemplar ground truth; if fewer than \(\gamma = 50\%\) match, reflection-based retry is triggered (up to \(\rho = 30\) retries). At runtime, new prompts are matched to a cluster by embedding similarity, the stored regex validates structural conformance, and the Python program is executed locally via interpreter to generate the response.

Key Contributions

  • GenCache: a generative cache that synthesizes novel responses rather than replaying stored ones, enabling cache hits on structurally similar but content-varying prompts.
  • A dual-similarity clustering scheme (prompt + response embeddings) for grouping prompt-response pairs with coherent structural patterns.
  • A program-generation-and-validation loop (CodeGenLLM + ValidLLM with reflection) that converts exemplar clusters into verified, executable cache entries.
  • Empirical evaluation integrated into two production-style agentic frameworks (Laser web-navigation, FLASH SRE), showing practical gains in hit rate and latency.

Results

  • Param-Only synthetic dataset (10k prompts): GenCache 97.81% hit rate; GPTCache 90.92% hit but 100% incorrect; ExactCache 0%.
  • Param-w-Synonym synthetic dataset: GenCache 83.66% hit rate with 92.16% correct hits; GPTCache 88.71% hit but 100% incorrect.
  • Positive/negative hit: GenCache negative hit rate (incorrect cache responses) ≤7.84% vs. GPTCache 100%.
  • Laser agent (WebShop): ≥83% cache hit rate, ≥35% cost savings.
  • Agentic integration: ~20% higher cache hit rate and ~34% lower end-to-end latency vs. standard prompt matching.
  • FLASH SRE agent (298 incidents): high recurring task rate (top-2 scenarios = 93% of incidents) makes caching particularly effective.

Limitations

  • Not suitable for free-form chatbot interactions or tasks with high prompt diversity—semantic caching remains preferable there.
  • Targets reversible actions; correctness guarantees are weaker for non-reversible agent actions.
  • Program generation requires a minimum cluster size (\(\nu\) exemplars) before the cache becomes active; cold-start latency incurs full LLM cost.
  • CodeGenLLM programs can overfit to exemplar keywords; mitigation relies on regex structural checks and error-handling blocks, not formal verification.
  • Evaluated only with simple prompt-based agents; integration with more complex, multi-step agent frameworks is left as future work.
  • Program generation itself incurs additional LLM calls (CodeGenLLM + ValidLLM), creating upfront overhead that must be amortized.

Relevance to Harnesses / Meta-Harnesses

Meta-harnesses that orchestrate repeated LLM calls—daily digest pipelines, SRE automation loops, multi-step agentic scaffolds—pay both latency and dollar cost proportional to the number of LLM invocations. GenCache directly targets this regime: it treats the harness's templated prompts (system messages + variable slots) as exactly the "structurally similar with controlled variability" pattern it is designed for. By caching executable programs rather than response strings, it is architecturally compatible with harnesses that use dynamic prompt construction, since the cached program re-runs with new slot values rather than requiring verbatim prompt replay. The dual-LLM generate-validate loop also mirrors a meta-harness pattern itself, offering a concrete implementation reference for harness designers who want to add program-synthesis-based caching layers.