💬 NLP

Why Agent Caching Fails and How to Fix It: Structured Intent Canonicalization with Few-Shot Learning

This paper identifies that existing AI agent caching fails due to a misalignment between classification accuracy and cache key consistency, and proposes a solution using structured intent canonicalization (W5H2) with few-shot learning and risk-controlled selective prediction to achieve high precision, sub-millisecond latency, and up to 97.5% cost reduction.

Original authors: Abhinaba Basu

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Abhinaba Basu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a super-smart personal assistant (an AI agent) that does things for you, like checking your email, booking flights, or buying stocks. Every time it does something, it has to call a "brain" (a Large Language Model or LLM) to figure out what to do.

The Problem: The Expensive, Slow Phone Call
Every time your assistant calls this brain, it costs money (like a toll fee) and takes a few seconds. If you ask it 50 things a day, you're paying a small fortune and waiting around.

To save money and time, engineers tried to build a memory bank (a cache). The idea is simple: "If I asked 'Check email from Alice' yesterday, and today you ask 'Check email from Bob,' the brain is doing the exact same thing (checking email). Let's just remember the answer and skip the call!"

Why Old Methods Failed: The "Similarity Trap"
Previous attempts at this memory bank failed miserably. Here's why, using a simple analogy:

Imagine a librarian who only remembers books based on how similar the titles sound.

The Mistake: The librarian sees "Check Email" and "Send Email." The titles sound very similar, so she thinks, "Oh, these are the same! I'll give you the 'Check' answer for the 'Send' request."
The Disaster: You asked to send an email, but the assistant checked your inbox. You missed a deadline.
The Reality: In AI terms, "Check" and "Send" are semantically close (similar words), but they require completely different actions. Old systems were too eager to say "I've seen this before!" and gave the wrong answer.

The Solution: W5H2 (The "Who, What, Where" ID Card)
The authors of this paper realized that to make a good memory bank, you don't need to guess if two sentences sound alike. You need to strip them down to their core structure.

They invented a system called W5H2. Think of it like a driver's license for a request. Instead of looking at the whole sentence, the system extracts specific fields:

What: The action (e.g., "Check Email").
Where: The target (e.g., "Email").
Who/When/How: The details (e.g., "From Alice," "Now").

The system creates a "Cache Key" (a unique ID) using only the What and Where.

"Check email from Alice" → ID: (Check, Email)
"Check email from Bob" → ID: (Check, Email)
"Send email to Bob" → ID: (Send, Email) (Different ID! No confusion!)

Now, the system knows that checking email for Alice and Bob is the exact same task, so it can safely reuse the answer. But it knows checking is different from sending.

The Secret Weapon: SetFit (The "8-Example Genius")
To figure out these IDs quickly, they used a tiny, smart model called SetFit.

The Old Way: Use a giant, expensive super-computer (a huge LLM) to read every single request. It's slow and costs a lot.
The New Way: Teach a tiny, cheap model using just 8 examples per task.
The Analogy: Imagine teaching a child to recognize dogs. You don't need to show them every dog in the world. You show them 8 pictures of different dogs, say "This is a dog," and they learn the pattern instantly.
The Result: This tiny model is 700 times faster and cheaper than the giant super-computer, yet it gets the job done better (91% accuracy vs. 68% for the giant model).

The Five-Tier Security Guard System
The authors built a "funnel" to handle requests, like a security team at a concert:

Tier 0 (The Fingerprint): A super-fast check. If the request looks exactly like a known pattern, grab the answer instantly. (Handles 30% of requests).
Tier 1 (The Veteran): A trained expert (BERT) who knows the common requests perfectly. (Handles 40%).
Tier 2 (The Quick Learner): The tiny SetFit model we just talked about. It handles new, weird phrasings using just a few examples. (Handles 15%).
Tier 3 (The Cheap Intern): A small, cheap AI for tricky stuff.
Tier 4 (The CEO): The giant, expensive super-AI. Only used for truly unique, complex problems. (Handles 1%).

The Result: A Massive Savings
Because 85% of requests are handled by the cheap, fast tiers (0, 1, and 2), the user barely ever has to call the expensive "CEO."

Old Cost: ~$32 per month for a heavy user.
New Cost: ~$0.80 per month.
Savings: 97.5%.

The Big Takeaway
The paper teaches us that for AI agents, consistency is more important than being "smart."

It's better to be wrong but consistent (always giving the same answer for the same type of request) than right but variable (sometimes giving the right answer, sometimes the wrong one, confusing the cache).
By treating AI requests like database records (cleaning them up into "What" and "Where") rather than trying to understand the "vibe" of the sentence, we can make personal AI agents fast, cheap, and reliable.

In a Nutshell:
Stop trying to guess if two sentences are "similar." Instead, turn every request into a structured ID card. Use a tiny, fast learner to read the ID card. This saves you almost all your money and makes your AI assistant feel instant.

1. Problem Statement

Personal AI agents (e.g., custom assistants, OpenClaw) execute repetitive tasks via LLM APIs, incurring high costs ( $0.01–$ 0.10 per call) and latency (2–5 seconds). While caching is a standard optimization, existing methods fail in this specific domain:

Exact Caching: Fails on paraphrases (e.g., "Check email from Alice" vs. "Check email from Bob").
Semantic Caching (e.g., GPTCache): Relies on embedding similarity, which is too permissive. Semantically close queries like "check email" and "send email" have high cosine similarity but require completely different tool sequences, leading to dangerous false positives.
Agentic Plan Caching (APC): Relies on keyword extraction, which fails on short, parameter-heavy queries (3–8 words).
The Core Issue: Existing methods optimize for classification accuracy or semantic similarity, but agent caching requires key consistency (equivalent queries must always produce the same key) and precision (cache hits must be safe to execute).

2. Methodology

A. Theoretical Reframing: Canonicalization over Classification

The authors reframe the problem from intent classification to intent canonicalization.

Goal: Map surface text to a stable cache key ( $f: X \to K$ ).
Objective: Maximize reuse (completeness) subject to a safety constraint (homogeneity).
Metric Shift: Instead of accuracy, they evaluate cache keys using V-measure decomposition (from clustering theory):
- Homogeneity ( $h$ ): Precision (does one key map to only one intent?).
- Completeness ( $c$ ): Consistency (does one intent always map to the same key?).
- V-measure: The harmonic mean of $h$ and $c$ .

B. The W5H2 Framework

A structured intent decomposition framework that breaks user requests into seven fields: Who, What, When, Where, Why, How, How Much.

Cache Key: Only the canonicalized (What, Where) pair is used as the key.
Parameters: Entities like "Who" (e.g., Alice) or "When" are extracted separately and injected at execution time.
Benefit: This ensures that parameter variations (different senders, different dates) do not fragment the cache, while the core action and domain remain consistent.

C. The Five-Tier Cascade Architecture

To handle the trade-off between cost, latency, and accuracy, the authors propose a cascaded system:

Tier 0 (Fingerprint): <1ms. NER-based template hashing (e.g., "Check email from {Who}").
Tier 1 (Supervised BERT): ~5–10ms. Fine-tuned BERT for known patterns (97.3% accuracy).
Tier 2 (SetFit): ~2–5ms. Few-shot contrastive learning for novel phrasings. Uses only 8 examples per class.
Tier 3 (Cheap LLM): Structured extraction via small LLMs (e.g., DeepSeek V3, GPT-4o Mini).
Tier 4 (Deep Agent): Full LLM for complex, novel tasks.

Result: Tiers 0–2 handle ~85% of requests locally at zero marginal cost.

D. Risk-Controlled Selective Prediction

To ensure safety, the system uses confidence thresholds and Risk-Controlling Prediction Sets (RCPS).

Queries with low confidence are "abstained" from the cache and passed to the next tier.
The authors apply LTT (Least Trimmed Thresholds) and Empirical Bernstein bounds to provide finite-sample guarantees that the "unsafe hit rate" (serving a wrong plan) stays below a defined threshold $\alpha$ .

3. Key Contributions

W5H2 Structured Decomposition: A novel framework for agent plan caching that separates action/target from parameters, enabling language-agnostic partial matching.
SetFit for Agent Caching: The first application of contrastive few-shot learning (SetFit) to agent plan caching. It achieves high accuracy with only 8 examples per class.
Cache-Key = Clustering Observation: Demonstrating that cache-key evaluation is equivalent to clustering quality evaluation, utilizing V-measure to decouple precision and consistency.
Counter-Intuitive Findings:
- A 22M-parameter SetFit model outperforms a 20B-parameter LLM (91.1% vs. 68.8% accuracy) with >700x lower latency.
- Smaller NLI models (22M params) outperform larger ones (280M params) in compound query detection because larger models suffer from "over-entailment," destroying decision boundaries.
Cost Reduction Model: A projected 97.5% cost reduction for individual users ($0.80/month vs. $31.72/month for all-LLM).

4. Experimental Results

The authors evaluated on four benchmarks: MASSIVE (8 classes), BANKING77 (77 classes), CLINC150 (150 classes), and their new NyayaBench v2 (20 real-world agentic classes, 63 languages).

Benchmark	Method	Accuracy	Latency	Key Insight
MASSIVE (8 cls)	SetFit (8-shot)	91.1% ± 1.7%	~2–5ms	Outperforms 20B LLM (68.8%) and GPTCache (37.9%).
MASSIVE (8 cls)	GPT-oss-20b (0-shot)	68.8%	3,447ms	LLMs are too slow and less consistent for caching.
NyayaBench v2	SetFit (8-shot)	55.3% ± 1.0%	2.4ms	Harder task (20 classes, 528 intents). Rises to 62.6% with 16-shot.
NyayaBench v2	GPTCache (KMeans)	49.1%	~5ms	Lower accuracy and precision than SetFit.
Compound Detection	MiniLMv2 (22M)	94.4%	-	Outperforms mDeBERTa (280M) which scored 0%.

Cross-Lingual Transfer: SetFit trained on English only achieved a mean of 37.7% accuracy across 30 languages (zero-shot), with Indo-European languages performing best (~50%).
Rate-Distortion: SetFit operates near the information-theoretic limit (optimal compression), whereas GPTCache often undershards or overshards.

5. Significance and Impact

Paradigm Shift: Moves agent caching from "semantic similarity" to "structured canonicalization," aligning it with database fingerprinting and compiler optimization.
Economic Viability: Proves that personal AI agents can be economically viable for consumers by reducing API costs by ~97.5% through intelligent local caching.
Model Efficiency: Demonstrates that for specific, structured tasks like intent canonicalization, small, fine-tuned models (SetFit) are superior to massive generative models in terms of accuracy, speed, and cost.
Safety Guarantees: Introduces a rigorous statistical framework (RCPS) to guarantee cache safety, addressing the critical risk of executing wrong tool sequences.

In conclusion, the paper argues that the failure of current caching methods stems from optimizing for the wrong metric (accuracy/similarity) rather than consistency. By adopting structured decomposition (W5H2) and few-shot contrastive learning (SetFit) within a risk-controlled cascade, it is possible to build highly efficient, safe, and low-cost personal AI agents.