Krites: Asynchronous Verified Semantic Caching for Tiered LLM Architectures

Paper: 2602.13165 Authors: Asmit Kumar Singh, Haozhe Wang, Laxmi Naga Santosh Attaluri, Tak Chiam, Weihua Zhu Categories: cs.IR, cs.AI

Abstract

As large language models become integral to production systems, semantic caching has emerged as a critical optimization for reducing inference costs and latency. This paper introduces Krites, an asynchronous caching policy designed for tiered LLM architectures that combines static (curated, offline-vetted) and dynamic (online-populated) caches. The key innovation lies in using an LLM judge to asynchronously verify near-miss cache entries that fall just below the static similarity threshold. When verified as semantically equivalent, these responses are promoted to the dynamic cache, enabling future queries to benefit from curated static answers. Krites maintains the same critical path behavior as standard threshold policies while expanding static coverage by up to 3.9x on conversational and search workloads.

Key Contributions

• Introduction of an asynchronous verification mechanism that decouples cache expansion from serving latency
• Design of Krites, a policy that uses LLM judges to safely expand static cache coverage without changing critical path decisions
• Demonstration that near-threshold misses represent significant untapped reuse opportunities in production workloads
• Trace-driven evaluation showing 2.5-3.9x improvement in static answer reuse across conversational and search scenarios
• Analysis of the cost-benefit tradeoffs between verification overhead and cache hit improvements

The Static-Dynamic Cache Tradeoff

Production LLM deployments face a fundamental tension in semantic caching. Static caches contain high-quality, human-vetted responses mined from historical logs, offering reliability and consistency. Dynamic caches populate online, providing flexibility but less quality control. Both tiers typically use a single embedding similarity threshold to determine cache hits.

This unified threshold creates a problematic tradeoff. Conservative thresholds (high similarity requirements) ensure semantic correctness but miss legitimate reuse opportunities—queries that are semantically equivalent but fall just below the threshold. Aggressive thresholds (low similarity requirements) increase hit rates but risk serving incorrect responses to semantically different queries.

The paper’s analysis reveals that near-threshold misses—queries with static neighbors scoring just below the threshold—represent a substantial fraction of traffic. These queries are often paraphrases or minor variations that could safely reuse static answers, but current policies treat them as complete misses requiring full LLM inference.

Krites Architecture and Mechanism

Krites operates through a three-stage pipeline that maintains critical path performance while expanding cache coverage:

Stage 1: Standard Threshold Check On the serving path, Krites behaves identically to a baseline static-threshold policy. It computes embedding similarity between the incoming query and static cache entries. If the nearest neighbor exceeds the static threshold $\tau_s$, the cached response is served immediately.

Stage 2: Asynchronous Verification When the nearest static neighbor falls in the near-miss zone (below $\tau_s$ but above a lower bound $\tau_v$), Krites triggers an asynchronous verification process. The query proceeds to normal LLM inference without delay. In parallel, an LLM judge evaluates whether the static response is semantically acceptable for the new query.

Stage 3: Promotion and Future Reuse If the judge approves the match, the system creates a new dynamic cache entry mapping the query to the verified static response. Future queries that are similar to this query can now hit the dynamic cache and receive the curated static answer, even though the original query didn’t meet the static threshold.

The verification uses a carefully designed prompt that asks the LLM judge to assess semantic equivalence between the query and the cached response’s original query. This judgment focuses on whether the cached answer would satisfy the new query’s intent, not just surface-level similarity.

Experimental Results and Analysis

The evaluation uses trace-driven simulation on two workload types: conversational assistant traffic and search-style queries. The key metric is the fraction of requests served with curated static answers, including both direct static hits and verified promotions.

For conversational workloads, Krites achieves 2.5-3.2x improvement in static answer reuse compared to tuned baseline thresholds. The gains are particularly pronounced for queries with high paraphrase rates—common in assistant scenarios where users rephrase questions when initial responses are unsatisfactory.

Search workloads show even stronger results, with up to 3.9x improvement. Search queries exhibit more semantic clustering, where multiple surface forms express the same information need. Krites effectively captures these clusters by verifying near-miss entries.

The paper demonstrates that verification costs are manageable. While each verification requires an LLM judge call, these happen asynchronously and only for near-miss queries. The amortized cost is offset by avoiding full inference on future similar queries. For workloads with moderate repeat rates, the break-even point occurs within hours to days.

Ablation studies reveal that the near-miss zone width (gap between $\tau_s$ and $\tau_v$) significantly impacts performance. Too narrow, and few candidates are verified; too wide, and verification costs escalate while approval rates drop. The optimal range varies by workload but typically spans 0.05-0.15 in cosine similarity space.

Implications for Production Systems

Krites addresses a practical challenge in production LLM serving: how to safely expand cache coverage without risking quality degradation. The asynchronous design is particularly valuable because it maintains the same latency guarantees as simpler policies while progressively improving hit rates.

The approach is complementary to other caching optimizations. It can combine with better embedding models, more sophisticated similarity metrics, or multi-tier cache hierarchies. The key insight—that near-misses represent safe expansion opportunities—applies broadly across caching strategies.

For organizations operating LLM services, Krites offers a path to reduce inference costs without the operational complexity of manually curating larger static caches. The system automatically discovers which near-miss queries are safe to promote, effectively crowdsourcing cache expansion through production traffic.

The paper also highlights the value of LLM judges in system optimization. While judges add computational cost, their ability to make nuanced semantic decisions enables policies that would be impossible with purely metric-based approaches. This pattern may extend to other system components where semantic understanding provides optimization opportunities.

Takeaways

1. Near-threshold cache misses represent significant untapped reuse opportunities in production LLM workloads, often accounting for queries that are semantically equivalent but fall just below similarity thresholds.

2. Asynchronous verification decouples cache expansion from serving latency, allowing systems to safely explore lower-confidence matches without impacting critical path performance.

3. LLM judges can effectively assess semantic equivalence for caching decisions, achieving 2.5-3.9x improvements in static answer reuse across conversational and search workloads.

4. The cost of verification is amortized over future cache hits, making the approach economically viable for workloads with moderate query repetition and paraphrasing.

5. Tiered caching architectures benefit from policies that bridge static and dynamic tiers, progressively expanding curated content coverage through production traffic analysis.