Savings from a Semantic Cache
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:
sim = [[1,0,0],[0.95,1,0],[0.1,0.2,1]] print(cache_savings(sim, 0.9, 0.01))
0.01
- 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≥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 hits×cost=1×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
costeach. - Round the total to 4 decimals.
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
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
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.