Asynchronous Verified Semantic Caching for Tiered LLM Architectures

Krites is an asynchronous semantic caching policy for tiered LLM architectures that expands the coverage of curated static responses by using an off-path LLM judge to verify borderline matches, thereby significantly increasing cache hit rates without compromising critical path latency.

The Gist

Imagine you run a massive, high-end restaurant (the LLM) that takes orders from thousands of customers every second. Cooking every single dish from scratch takes time, costs a lot of money, and uses up your best chefs.

To save time and money, you have a Caching System. Think of this as a "Ready-Made Meal" shelf in your kitchen. If a customer orders something you've made before, you just grab the pre-cooked dish and serve it instantly.

The Problem: The "Grey Zone" of Memory

Your kitchen has two types of shelves:

1. The VIP Shelf (Static Cache): These are dishes prepared by your head chef and taste-tested by food critics. They are perfect, safe, and high-quality. But, they are only kept if the order is exactly the same as before.
2. The Daily Special Shelf (Dynamic Cache): These are dishes made on the fly by your line cooks. They are fresh but might vary slightly in taste.

The Current Rule:
Your kitchen manager uses a simple rule: "If the new order sounds 95% similar to a VIP dish, serve the VIP dish. If it's less than 95% similar, ignore the VIP shelf and make a new dish."

The Flaw:
This rule is too strict.

• Scenario A: A customer asks, "Can my dog eat honey?"
• Scenario B: A customer asks, "What's the word on my dog having honey?"

To a human, these are the same question. But to the computer's "similarity meter," they might only be 92% similar. Because of the strict 95% rule, the kitchen ignores the perfect, pre-approved "Dog Honey" answer on the VIP shelf. Instead, it wastes time and money cooking a new dish from scratch, even though the old one would have been perfect.

This is the "Grey Zone": Questions that are clearly the same to a human, but fall just below the computer's strict cutoff.

The Solution: Krites (The Asynchronous Judge)

The paper introduces Krites, a clever new system that fixes this without slowing down the restaurant.

Here is how Krites works, using a Library Analogy:

1. The Critical Path (The Front Desk):
   When a customer walks in, the librarian (the system) checks the main index.

   • If the book is a perfect match? Serve it immediately. (No delay).
   • If the book is totally different? Go to the back to find a new one. (No delay).
   • The Krites Twist: If the book is almost a match (in the "Grey Zone"), the librarian still serves the customer immediately using the standard rule (or goes to the back). Crucially, the customer does not wait.

2. The Asynchronous Judge (The Night Shift Librarian):
   While the customer is walking away with their book, a Night Shift Librarian (an AI Judge) wakes up.

   • They look at the "almost match" request and the "almost match" book.
   • They ask a smart question: "Are these two actually the same thing?"
   • If Yes: The Night Shift Librarian takes the perfect VIP book from the back and places a sticky note on the "Daily Special" shelf saying, "Next time someone asks this, give them the VIP book!"
   • If No: They do nothing.

3. The Result:
   The next time someone asks that question, the system sees the sticky note on the Daily Special shelf and instantly serves the VIP quality answer.

Why This is a Big Deal

• No Waiting: The customer never waits for the Night Shift Librarian to check. The system is just as fast as before.
• Better Quality: Over time, the "Daily Special" shelf gets filled with the high-quality "VIP" answers, even for questions that were previously too "different" to match.
• Cost Savings: You stop cooking expensive meals from scratch for questions that could have been answered with a pre-made, perfect dish.

The Analogy Summary

• The Old Way: A strict bouncer who only lets you in if you look exactly like the VIP guest list. If you look 90% like them, you get turned away.
• Krites: The bouncer lets you in (or sends you to the kitchen) immediately. Meanwhile, a smart assistant in the back checks your ID. If they realize you are the VIP guest, they update the list for next time, so you get VIP treatment forever after.

In short: Krites allows AI systems to be smarter about reusing high-quality answers without making the user wait, effectively turning a "maybe" into a "yes" for the future.

Technical Summary

1. Problem Statement

Large Language Models (LLMs) are critical components in search, assistants, and agentic workflows, but their inference costs and latencies are high. To mitigate this, production systems use semantic caching, which reuses cached responses for semantically similar prompts rather than exact string matches.

Current production architectures typically employ a tiered design:

• Static Tier: Populated offline with curated, high-quality, human-vetted answers.
• Dynamic Tier: Populated online with fresh responses from the LLM backend.

The Core Challenge:
Both tiers are currently governed by a single global embedding similarity threshold ($\tau$). This creates a hard tradeoff:

• Conservative Thresholds: Miss safe reuse opportunities (low hit rate) because semantically equivalent but lexically different prompts fall below the threshold.
• Aggressive Thresholds: Risk serving semantically incorrect responses (high error rate) because the embedding space has a "grey zone" where distinct intents have high similarity.

Existing solutions like vCache demonstrate that embedding geometry alone cannot reliably separate paraphrases from distinct intents in this grey zone. Placing an LLM "judge" directly on the critical serving path to verify these borderline cases solves the accuracy issue but destroys the latency benefits of caching.

2. Methodology: Krites

The authors propose Krites, an asynchronous, verified semantic caching policy designed for tiered static-dynamic architectures. Krites decouples the serving decision from the verification process.

Key Architectural Components

1. Unchanged Critical Path:

   • Krites retains the standard baseline policy (e.g., GPTCache style) for the user-facing request.
   • If a prompt's nearest neighbor in the static tier has similarity $s \ge \tau_{static}$, it is a hit (served immediately).
   • If $s < \sigma_{min}$, it is a miss (served from dynamic tier or backend).
   • Crucially: The latency for the triggering request is identical to the baseline.

2. The Grey Zone Trigger:

   • Krites defines a "grey zone" where similarity falls between a lower bound ($\sigma_{min}$) and the static threshold ($\tau_{static}$).
   • Prompts in this zone are considered "ambiguous." They are not served immediately from the static tier, but they are flagged for asynchronous verification.

3. Asynchronous Verification Loop:

   • When a prompt falls in the grey zone, Krites schedules a background task (off-path) to invoke an LLM Judge.
   • The Judge: Receives the new prompt ($q$), the cached prompt ($h$), and the cached answer ($a$). It determines if $a$ is an acceptable response for $q$ based on strict rubrics (intent alignment, entity consistency, etc.).
   • Decision: The judge returns a binary APPROVE or REJECT.

4. Auxiliary Overwrite (Promotion):

   • If the judge approves the match, Krites performs an auxiliary overwrite: it inserts the pair $(q, a_{static})$ into the Dynamic Cache.
   • This effectively turns the dynamic cache into a "mutable pointer layer" over the static answers.
   • Result: Future requests for $q$ (or its paraphrases) will hit the dynamic tier and receive the high-quality, curated static answer, bypassing the LLM backend entirely.

3. Key Contributions

• Decoupled Verification: Krites is the first policy to separate the latency-critical serving path from the high-precision verification step, allowing for aggressive reuse of curated static answers without compromising response time.
• Dynamic Promotion Mechanism: It introduces a mechanism to "promote" verified static answers into the dynamic tier, expanding the reach of the static cache over time without requiring offline re-indexing.
• Tiered Architecture Optimization: It specifically targets the inefficiency in tiered systems where high-quality static answers are stranded behind conservative similarity thresholds.
• Judge-Agnostic Evaluation: The system is designed to work with any verifier (LLM or oracle), isolating the caching policy logic from specific model capabilities.

4. Experimental Results

The authors evaluated Krites using trace-driven simulations on two benchmarks derived from vCache:

• SemCacheLMArena: Conversational workloads (~60k prompts).
• SemCacheSearchQueries: Search-style workloads (~150k prompts).

Performance Metrics:

• Static-Origin Served Fraction: The percentage of requests served with curated, offline-vetted answers (either direct hits or promoted hits).
• Latency: Critical path latency remained unchanged compared to the tuned baseline.
• Error Rate: Maintained at the same level as the baseline (since the initial serving decision was unchanged).

Quantitative Gains:

Dataset	Baseline Static Hit Rate	Krites Static-Origin Fraction	Relative Gain
SemCacheLMArena (Conversational)	8.2%	19.4%	+136.5%
SemCacheSearchQueries (Search)	2.2%	8.6%	+290.3%

Note: The gains are particularly high for search queries, where paraphrasing is common but exact matches are rare.

5. Significance and Implications

• Safety and Reliability: In enterprise or medical contexts, replacing a dynamically generated (potentially hallucinated) response with an offline-vetted "gold" static answer significantly elevates safety. Krites unlocks this value for queries that were previously too "distant" in embedding space to be cached.
• Cost Efficiency: By increasing the fraction of requests served from the static tier (which has zero inference cost), Krites reduces the load on expensive LLM backends.
• Practical Deployment: The asynchronous nature ensures that the system does not suffer from the latency penalties of synchronous LLM judging, making it viable for real-time interactive workloads.
• Scalability: The system handles the compute cost of the judge by offloading it to background workers, allowing operators to tune the verification volume (via $\sigma_{min}$) based on available compute budgets without impacting user experience.

In summary, Krites solves the "similarity grey zone" problem in LLM caching by using asynchronous LLM judges to validate borderline matches, thereby safely expanding the coverage of high-quality static caches without sacrificing the low-latency benefits of semantic caching.