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 caching system for LLMs that stores executable programs instead of verbatim responses, enabling correct cache hits for structurally similar but non-identical prompts. It targets agentic and repetitive workflows where exact matching misses and semantic matching over-matches. On agentic benchmarks it achieves ~20% higher cache hit rates and ~34% latency reduction versus standard prompt matching.

Problem

Existing LLM caching strategies fail in the regime of structurally similar prompts: exact-match caches (ExactCache) require identical prompts and therefore miss almost everything, while semantic caches (e.g., GPTCache) conflate structurally related but semantically distinct prompts (e.g., "buy 12 AAA batteries from Amazon" vs. "buy a USB-C cable from Amazon"), returning incorrect cached responses. This is dangerous when agents execute non-reversible actions based on those responses.

Method

GenCache replaces stored responses with stored Python programs. The pipeline has three stages: 1. Clustering: Incoming promptā€“response pairs are clustered using dual cosine similarity over SentenceTransformer embeddings of both the prompt and the structured response (key-value pairs). Cluster assignment requires both prompt similarity (sp > Tp = 0.8) and response similarity (sr > Tr = 0.75) to exceed thresholds. 2. Program generation (CodeGenLLM): Once a cluster accumulates ā‰„Ī½ exemplars (default Ī½=4), a CodeGenLLM (GPT-4o) uses in-context learning over those exemplars to infer a regex-based Python program that extracts variable keywords from a prompt and constructs the corresponding response. 3. Validation (ValidLLM): A separate ValidLLM checks that program-generated responses match at least Ī³=50% of exemplar ground truths semantically. On failure, reflection-based retry is used (up to Ļ=30 retries). On a cache hit at runtime, the stored regex first validates prompt conformance, then the Python interpreter executes the program locally (~0.176s total vs ~3.5s for an LLM call).

Key Contributions

  • Formalizes the "structurally similar prompt" category (distinct from exact-match and semantic-similarity cases) and identifies its prevalence in agentic workflows.
  • Proposes storing parameterized programs as cache entries rather than responses, enabling correct variation-aware responses without an LLM call.
  • Introduces a dual-embedding clustering scheme combining prompt and structured-response similarity.
  • Adds a reflection-based program validation loop using a separate ValidLLM to gate cache entry quality.
  • Demonstrates integration with two production-style agent frameworks (FLASH SRE agent, Laser web-navigation agent).

Results

  • Param-Only synthetic dataset (10k prompts): GenCache 97.8% hit rate, 1.97% negative hits; GPTCache 90.9% hit rate, 100% negative hits; ExactCache 0% hits.
  • Param-w-Synonym synthetic dataset: GenCache 83.7% hit rate, 7.8% negative hits; GPTCache 88.7% hit rate, 100% negative hits.
  • Token savings: At least 35% token reduction per request across all Ī½ settings; up to 73% at Ī½=2.
  • FLASH (cloud-ops agent, 298 incidents): GenCache+ExactCache achieves 54.7% cache hit rate vs. 34.4% for ExactCache alone; execution time reduced from 53.45s to 39.91s (~25% reduction).
  • Laser (web-navigation agent, 200 requests): 37.2% cache hit rate vs. 5.7% for ExactCache alone.
  • Cache hit latency overhead: ~0.176s per cache hit (vs. ~3.5s LLM call), ~0.131s on cache miss path.

Limitations

  • Only applicable when prompts exhibit structured regularity and predictable response patterns; explicitly unsuitable for free-form chatbot interactions or structurally diverse prompts.
  • Program generation can fail (66% of cache creation attempts failed for Laser due to insufficient structural consistency in clustered exemplars).
  • ~1% FLASH incident failures from incorrect cache hits mapping to wrong troubleshooting documents; authors restrict evaluation to reversible workflows to avoid catastrophic errors.
  • Regex-based pattern extraction breaks on complex or multi-sentence user instructions (e.g., item descriptions split across sentences produce wrong keyword extraction).
  • CodeGenLLM and ValidLLM are themselves LLM calls; initial warm-up cost exceeds savings until hit rate stabilizes.
  • Sensitivity to similarity thresholds: too high ā†’ too many small clusters with insufficient exemplars; too low ā†’ heterogeneous clusters that CodeGenLLM cannot generalize.

Relevance to Agentic AI / LLM Agents

GenCache directly targets the cost and latency bottleneck in agentic workflows that execute repetitive ReAct-style action loopsā€”a dominant architectural pattern in tool-using LLM agents. By replacing LLM calls with local program execution on cache hits, it addresses a practical deployment concern (API cost and latency) that scales quadratically with agent step count. The program-as-cache paradigm is a novel middle ground between KV-cache prefix matching (server-side, prefix-constrained) and semantic caching (client-side, correctness-unsafe), and the framework's integration points with LangChain and OpenAI completion APIs make it directly applicable to most production agent stacks. The failure mode analysis (regex misfires, multi-sentence decomposition) also surfaces important fragility patterns in structured agentic prompts that have broader implications for prompt engineering.