Semantic Cache Hit Rate at a Similarity Threshold

Problem Statement

An exact-match cache is useless in front of an agent - no two users phrase a question identically. A semantic cache embeds the query and serves a stored answer when the nearest cached query is close enough. The threshold is the whole design: too high and you never hit, too low and you confidently serve the wrong answer. Measuring the trade-off means replaying a query log and counting.

Background

Queries arrive in order. For each one:

1. Compute the cosine similarity against every entry currently in the cache.
2. Round each similarity to 6 decimal places before comparing - this keeps the boundary case reproducible.
3. Take the highest similarity; ties go to the earliest inserted entry.
4. If that best similarity is >= threshold, it is a hit - record which entry served it, and do not insert the query (the cache stores one representative per cluster).
5. Otherwise it is a miss - insert this query into the cache and move on.

Cosine similarity of $\mathbf{a}$ and $\mathbf{b}$ is $\frac{\mathbf{a} \cdot \mathbf{b}}{\lVert \mathbf{a}\rVert \lVert \mathbf{b}\rVert}$; if either vector is all zeros, define the similarity as 0.0.

Your Task

Implement:

def semantic_cache(queries, threshold):

• queries: list of {"id": str, "vec": list[float]}, in arrival order. All vectors have the same length.

Return:

• hits, misses: ints
• hit_rate: hits / len(queries) rounded to 4 decimal places (0.0 for an empty log)
• hit_map: list of [query_id, serving_entry_id] pairs, in arrival order
• cache_size: number of entries in the cache at the end

Input/Output Format

Returns the five-key dict. Do not use numpy-specific printing anywhere; every float in the output is rounded.

Sample

qs = [{"id": "q1", "vec": [1.0, 0.0]},
      {"id": "q2", "vec": [2.0, 0.0]},
      {"id": "q3", "vec": [0.0, 1.0]}]
out = semantic_cache(qs, 0.9)
print(out["hits"], out["misses"], out["hit_rate"])   # 1 2 0.3333
print(out["hit_map"])                                 # [['q2', 'q1']]

q2 points the same way as q1 (similarity 1.0) so it hits; q3 is orthogonal (0.0) and misses.