Savings from a Semantic Cache

mediumPROProduction: Cost, Caching & EvalsAI AgentsAI Agents 1

Problem Statement

A semantic cache serves a query from cache when a prior query's similarity exceeds a threshold, saving the cost of an LLM call. Given queries with pairwise similarity to earlier queries, compute total cost saved.

Background

Process queries in order. Query i is a cache hit if any earlier query j < i has similarity[i][j] >= threshold; then it costs nothing and saves cost dollars. Otherwise it is a miss: it costs cost and is added to the cache. The first query is always a miss. Return total dollars saved (num_hits * cost), rounded to 4 decimals.

Your Task

def cache_savings(similarity, threshold, cost):

similarity: n x n nested list; similarity[i][j].
Return dollars saved.

Input Format

similarity (nested list), threshold (float), cost (float).

Output Format

A float rounded to 4 decimals.

Sample

sim = [[1,0,0],[0.95,1,0],[0.1,0.2,1]]
print(cache_savings(sim, 0.9, 0.01))

Output:

0.01

Example

Input

sim = [[1,0,0],[0.95,1,0],[0.1,0.2,1]]
print(cache_savings(sim, 0.9, 0.01))

Output

0.01

Reasoning

Query 0 (Index 0): As the first query, there are no prior queries to compare against, so it is a miss. It is added to the cache.
Query 1 (Index 1): Compare with Query 0. The similarity is $0.95$ . Since $0.95 \ge 0.9$ (the threshold), this is a hit. No cost is incurred, and the query is not added to the cache.
Query 2 (Index 2): Compare with prior queries in the cache (only Query 0 exists). The similarity with Query 0 is $0.1$ . Since $0.1 < 0.9$ , it is a miss. It costs $0.01$ and is added to the cache.
Calculate Total Savings: There was 1 hit. The savings are calculated as $\text{hits} \times \text{cost} = 1 \times 0.01 = 0.01$ .
The final output is 0.01

Constraints

Query i hits if any j<i has similarity[i][j] >= threshold.
First query is always a miss; hits save cost each.
Round the total to 4 decimals.

Learn this in

Deployment & OptimizationLLM Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Cache Hit Rateeasy

Concept primerPREVIEW

1. Background Knowledge

A semantic cache stores the results of previous LLM queries. When a new query arrives, the system compares it against cached entries using a similarity metric (often cosine similarity over embeddings). If the similarity to any cached entry meets or exceeds a threshold, the cached response is returned, avoiding the expense of a new model inference. This is a common production optimization for reducing latency and API costs.

In this problem, the similarity matrix similarity[i][j] encodes how similar query $i$ is to query $j$ . The matrix is not necessarily symmetric in practice (though it often is), and the diagonal entries are typically 1.0 (a query is perfectly similar to itself). The key operational rule is that a query can only be served from cache if it was already stored — meaning only earlier queries ( $j < i$ ) are eligible cache sources. This temporal ordering is critical: a later query cannot "retroactively" make an earlier query a hit.

The cost model is straightforward: each cache miss incurs cost dollars, while each cache hit incurs zero marginal cost. The total savings is therefore the number of hits multiplied by the per-call cost. Rounding to 4 decimals handles floating-point imprecision in the final result.

2. Algorithm Approach

This is a sequential scan with a running set of cached indices. Process queries from index $0$ to $n-1$ . For each query $i$ , check whether any previously cached query $j < i$ satisfies similarity[i][j] >= threshold. If so, query $i$ is a hit (no cost, not added to cache — it was already covered). If no such $j$ exists, query $i$ is a miss: pay the cost and add $i$ to the set of cached queries.

The pattern is essentially a greedy online algorithm: at each step you make a local decision (hit or miss) based only on information available so far. There is no need for dynamic programming or backtracking because the decision for query $i$ depends only on the set of queries cached before $i$ .

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results