🤖 machine learning

Cache-Aware Prompt Compression:A Two-Tier Cost Model for LLM API Caching

This paper introduces Cache-Aware Prompt Compression (CAPC), a strategy that combines query-agnostic compression with explicit cache control and tier-preserving bounds to overcome the limitations of query-aware methods, achieving significant cost reductions (up to 90%) while maintaining quality across diverse production LLM workloads.

Original authors: Yan Song

Published 2026-07-20

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Yan Song

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 are running a massive, super-smart library where a very expensive librarian (an AI) helps you find answers. To save money, the library has two special tricks. First, there's a "VIP Lounge" (caching): if you ask the librarian about the same book chapter over and over, they don't have to re-read the whole thing from the library shelves; they just glance at their notes, which is much cheaper. Second, there's a "Summarizer" (compression): instead of handing the librarian a 500-page novel, you give them a 50-page summary, which is also cheaper to process.

For a long time, people thought these two tricks were best used separately. You'd either use the VIP Lounge for big, boring books, or you'd use the Summarizer for short, tricky questions. But here's the catch: the Summarizer usually changes the story slightly every time you ask a new question to make it fit better. The problem is, the VIP Lounge is a stickler for rules. If the story changes even a tiny bit, the librarian says, "Sorry, that's a new book!" and throws away the notes, forcing you to pay full price to read the whole thing again. This paper asks a simple question: Can we use both tricks at the same time without breaking the rules?

The researchers at PayPal decided to test this on a real-world AI system called Sonnet 4.6. They discovered that the VIP Lounge isn't as perfect as everyone thought. It has a "hot zone" for short notes and a "persistent zone" for long ones, and if you get too clever with your summaries, you accidentally kick your notes out of the expensive hot zone. They found that the old way of doing things—changing the summary for every single question—actually wastes money because it keeps the librarian from using the cheap notes.

To fix this, they invented a new strategy called CAPC (Cache-Aware Prompt Compression). Think of it like this: instead of rewriting the story for every question, they create one perfect, compressed summary of the boring parts once and lock it in the VIP Lounge. Then, for every new question, they just add the specific question to that locked summary without changing the summary itself. It's like having a pre-written script that never changes, so the librarian can reuse their cheap notes every single time.

The results were surprising. In tests with 16 different types of documents, this new method was the cheapest option every single time, saving about 49% compared to just using the VIP Lounge and 64% compared to the old "change-the-summary" method. They also tested it on real-world jobs, like a robot that uses tools to fix computer code and a system that searches through huge knowledge graphs. In one case, they saved over 50% on costs without losing any quality. In another, they proved that the old "change-the-summary" method actually cost 40% more than doing nothing at all because it kept breaking the cache. The paper concludes that by being smart about when to compress and what to cache, we can make AI much cheaper to use without making it dumber.

Technical Summary: Cache-Aware Prompt Compression (CAPC)

Problem Statement

Modern Large Language Model (LLM) deployments increasingly rely on two distinct cost-reduction primitives: prompt caching (storing KV-states of a prefix to charge discounted rates for subsequent reads) and prompt compression (reducing the token count of the input). Historically, these techniques have been treated as separate optimizations. However, the dominant literature on prompt compression relies on query-aware methods, which generate a unique compressed prefix for every specific query.

This design choice creates a fundamental conflict with prefix-strict caching mechanisms (e.g., Anthropic's cache_control). Because the compressed prefix changes with every query, the cache key is invalidated on every call. Consequently, the system pays the full, non-discounted input rate for every request, effectively erasing the savings from both compression and caching. While existing literature often assumes an ideal cache hit rate ( $\rho = 1.0$ ), this assumption fails to account for the economic reality of real-world APIs, where cache behavior is non-trivial and query-aware compression can result in a net negative return on investment (ROI).

Methodology and Empirical Characterization

The authors address this gap through a combination of empirical measurement, cost modeling, and algorithmic design.

1. Empirical Characterization of Anthropic Sonnet 4.6

The paper first characterizes the caching behavior of Anthropic's Sonnet 4.6 API through controlled experiments ( $n=3$ trials, total cost $1.91). Key findings include:

Two-Tier Architecture: The cache is not uniform. It exhibits a sharp threshold near 3,500 tokens.
- Hot Tier (< 3.5k tokens): The hit rate ( $\rho$ ) plateaus at approximately 0.83 (specifically 0.833 for 2k tokens) even after 30 calls. It is not 1.0.
- Persistent Tier (> 3.5k tokens): The hit rate is effectively 1.0 from the second call onward.
Token-Strict Invalidation: Cache invalidation is strict to the token sequence. Even minor mutations (e.g., a single character change) result in a cache miss, though leading/trailing whitespace is normalized by the tokenizer.
Pricing Structure: The API charges a premium for cache writes ( $c_w$ ) compared to uncached inputs ( $p_{in}$ ), and a significant discount for cache reads ( $c_r$ ). On Sonnet 4.6, $c_w \approx 1.25 \times p_{in}$ and $c_r \approx 0.10 \times p_{in}$ .

2. Cost Modeling and Crossover Analysis

The authors derive a per-call cost model for four strategies:

A (Vanilla): No cache, no compression.
B (Cache-only): Full prefix cached, no compression.
C (Query-aware Compression): Compressed per query, no cache (cache misses every time).
D (CAPC): Query-agnostic compression + caching.

The model defines a crossover threshold ( $\rho_{cross}$ ) where the cost of caching (Strategy B) equals the cost of query-aware compression (Strategy C):
$\rho_{cross}(r) = \frac{c_w - p_{in}/r}{c_w - c_r}$
The analysis reveals that for high compression ratios ( $r \ge 6$ ), the required hit rate for caching to beat query-aware compression exceeds the empirical plateau of the Sonnet 4.6 hot tier ( $\rho \approx 0.89$ ). Thus, under realistic conditions, query-aware compression is often cheaper than naive caching, contradicting conventional wisdom.

3. The CAPC Algorithm

The proposed solution, Cache-Aware Prompt Compression (CAPC), combines three components:

Query-Agnostic Compression: A static document is compressed once (e.g., via sentence selection) into a fixed prefix $D'$ , ensuring the cache key remains constant across queries.
Tier-Preserving Ratio Bound: To prevent over-compression from pushing the prefix into the "hot tier" (where $\rho < 1$ ), the compression ratio $r$ is bounded by $r_{max} = \lfloor |D| / 3500 \rfloor$ . This ensures the compressed prefix remains in the persistent tier ( $\rho \approx 1.0$ ).
AdaptiveCacheBoundary: For evolving documents, a subroutine classifies sentence positions as STATIC, QUASI, or DYNAMIC based on mutation rates across versions, caching only the stable prefix.

Key Results

1. LongBench-v2 Synthetic Benchmarks

On 16 configurations (4 document sizes $\times$ 4 ratios), CAPC was the cheapest strategy in 16/16 cases.

Savings: Mean savings of 49% over cache-only, 64% over query-aware compression, and 90% over vanilla.
Quality: CAPC maintained quality within 0.05 of the uncompressed baseline at tier-preserving ratios.
Crossover Validation: At $r=6$ , query-aware compression was cheaper than cache-only in all 4/4 configurations, validating the crossover model's prediction.

2. Production Validation: Enterprise Tool-Using Assistant

Validated on a 94k-token static prefix (system prompt + 287 MCP tool definitions).

Cost Reduction: CAPC at $r=3$ achieved a 51.7% cost reduction over vanilla.
Quality: Tool-selection quality matched cache-only (0.700 vs 0.703).
Insight: Query-aware compression at $r=3$ actually performed worse on tool selection (0.603) because it discarded tool definitions relevant to the query. CAPC's query-agnostic approach preserved the full catalog, proving superior for tool-augmented agents.
Implicit Caching: The study revealed that Anthropic implicitly caches large tools= arrays even without explicit markers, reducing the marginal benefit of explicit caching for vanilla strategies but not negating CAPC's compression gains.

3. Knowledge-Graph RAG (Graphify)

Integrated with graphify for codebase indexing (FastAPI and httpx repositories).

Architecture: Layer 1 (cached, query-agnostic) contains graph metadata; Layer 2 (per-query) fetches source code.
Performance: CAPC delivered 9.3x cost reduction on FastAPI and 2.4x on httpx compared to "cache-all" (full graph skeleton), while maintaining stable 85%+ cache hit rates.
Quality: CAPC outperformed native graphify queries and embedding-RAG baselines, particularly on codebases where the model had weaker prior knowledge (httpx), delivering a 142% quality lift over vanilla.

4. Public Benchmark: $\tau$ -Bench Retail

Evaluated on 50 deterministic tasks with database-state rewards (no LLM judge).

Result: CAPC was the cheapest strategy, saving 7.9% over vanilla while achieving exactly the same task completion rate (36/50) as vanilla ( $z=0.00, p=1.00$ ).
Negative ROI of Query-Aware: Query-aware compression was 40.1% more expensive than vanilla, providing the first production confirmation that query-aware methods can have negative ROI on public benchmarks.

Significance and Claims

The paper claims to provide the first systematic characterization of prompt caching economics, moving beyond the idealized $\rho=1.0$ assumption. Its primary contributions are:

Empirical Reality: Demonstrating that LLM caches have a two-tier architecture with a non-trivial hit rate plateau below a specific token threshold.
Theoretical Inversion: Proving that at high compression ratios, query-aware compression is often cheaper than naive caching, inverting the conventional design hierarchy.
Practical Algorithm: Introducing CAPC, which unifies query-agnostic compression with explicit caching and a tier-preserving constraint.
Production Validation: Validating these findings across synthetic benchmarks, enterprise tool-use agents, knowledge-graph RAG pipelines, and public deterministic benchmarks.

The authors emphasize that CAPC is not a replacement for indexers (like graphify) but a complementary "last-mile delivery" layer that optimizes the economic cost of delivering index-derived context to an LLM. The total cost of all empirical work in the paper was $98.96, demonstrating that these findings are reproducible with modest resources.