Skip to content

Generative Caching for Structurally Similar Prompts and Responses

🕒 Published (v1): 2025-11-14 00:22 UTC · Source: Arxiv · 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 stores executable Python programs—not verbatim responses—as cache entries, enabling correct reuse across structurally similar but not identical prompts. Unlike semantic caches that return wrong answers for parameter-varied queries, GenCache synthesizes variation-aware responses by executing the cached program locally. It achieves 83–98% cache hit rate on structured-task datasets with ≥35% cost savings.

Problem

Exact-match caching misses all reuse opportunities for prompts with minor variations; semantic caching (e.g., GPTCache) over-fires—returning a 100% incorrect hit rate on structured tasks because it treats "buy 12 AAA batteries" and "buy USB-C cable" as equivalent. Neither handles the regime where \(\alpha(x) = a_1 \cdot x \cdot a_2\) and \(\beta(x) = b_1 \cdot f(x) \cdot b_2\): structured regularity with controlled, correctness-critical variability.

Method

Clustering: incoming prompt-response pairs \((P, R)\) are assigned to clusters by requiring both cosine similarity of prompt embeddings \(s_p > T^p\) and response embeddings \(s_r > T^r\) against the cluster centroid. The final cluster is \(\arg\max_{C^{int}}(s_p + s_r)\).

Program generation: once a cluster accumulates \(\nu\) exemplars, CodeGenLLM (GPT-4o) is prompted in-context with all exemplar \((P, R)\) pairs to synthesize a Python program using regex extraction to map prompt variants to correctly formatted responses.

Validation: ValidLLM executes the program on the same exemplars and checks semantic equivalence of outputs; if fewer than \(\gamma\) match, a reflection-based retry appends ValidLLM's failure justifications to the CodeGenLLM prompt. Retry budget is capped at \(\rho\).

Runtime: new prompts are matched to the nearest cluster; a stored regex verifies structural conformance before the cached program is executed locally via Python interpreter. On failure or miss, the LLM is called normally.

Key Contributions

  • Program-as-cache paradigm: stores a Python regex-extraction program per cluster rather than fixed responses, enabling variation-aware cache hits.
  • Dual-similarity clustering (prompt + response embeddings) to avoid conflating structurally unrelated prompts that share large system-message prefixes.
  • LLM-driven program generation with a separate ValidLLM validation stage and reflection-based retry loop.
  • End-to-end evaluation integrated with two production-style agentic frameworks (Laser/WebShop and FLASH/cloud-ops).

Results

  • Param-Only synthetic dataset (10,000 prompts): GenCache 97.81% hit rate, 98.03% positive (correct) hits, 1.97% incorrect; GPTCache 90.92% hit rate, 0% correct; ExactCache 0%.
  • Param-w-Synonym (synonym + phrasing variation): GenCache 83.66% hit rate, 92.16% positive hits; GPTCache 88.71% hit rate, 0% correct.
  • Agentic integration: ~20% higher hit rate and ~34% lower end-to-end latency vs. standard prompt matching.
  • Cost: ≥35% reduction in LLM calls/tokens on WebShop; cluster database stays below 20 MB in all experiments.

Limitations

  • Inapplicable to free-form, high-diversity prompts (e.g., open-ended chatbots); requires structural regularity.
  • Cold-start: first \(\nu\) prompts per cluster cannot be served from cache; program generation is deferred until \(\nu\) exemplars accumulate.
  • Evaluated only on reversible actions; applicability to non-reversible agentic actions is explicitly deferred.
  • Program generation cost (CodeGenLLM + ValidLLM calls) must be amortized over sufficiently many cache hits to yield net savings.
  • GenCache-feedback (reflection enabled) shows lower overall hit rate than vanilla GenCache on some splits (82.35% vs. 97.81% on Param-Only), suggesting reflection can over-constrain programs.

Relevance to Harnesses / Meta-Harnesses

Meta-harnesses that invoke LLMs in tight loops over structurally templated sub-tasks—per-paper digests, per-incident SRE remediation, per-record data extraction—are precisely GenCache's target regime: the harness itself generates the structural regularity that GenCache exploits. GenCache can be inserted as a transparent middleware layer between a harness's dispatch logic and its LLM backend, reducing token spend and latency without any harness-level changes. The program-generation-and-validation inner loop (CodeGenLLM → ValidLLM → reflection retry) is itself a micro-harness pattern—a self-contained generate-verify-refine cycle—illustrating how harness design principles compose recursively. For harness builders, the key takeaway is that caching should be generative, not lookup-based, whenever the harness emits parametric prompt families.