Semantic Cache Hit Rate at a Similarity Threshold

1. Background Knowledge

Semantic caching is a technique used in AI applications to optimize latency and reduce computational costs by storing previously generated responses. Unlike traditional exact-match caching, which relies on identical string keys, semantic caching uses vector embeddings to determine if a new query is "similar enough" to a cached one. This allows the system to serve a relevant answer even if the user's phrasing differs slightly from previous queries. The core metric for this comparison is cosine similarity, which measures the cosine of the angle between two non-zero vectors in an inner product space.

Cosine similarity ranges from $-1$ (exact opposite) to $1$ (exact same direction), with $0$ indicating orthogonality (no similarity). In the context of text embeddings, vectors are typically normalized, but raw vectors may vary in magnitude. The formula for cosine similarity between vectors $\mathbf{a}$ and $\mathbf{b}$ is:

$$\text{similarity} = \frac{\mathbf{a} \cdot \mathbf{b}}{\lVert \mathbf{a}\rVert \lVert \mathbf{b}\rVert}$$

where $\mathbf{a} \cdot \mathbf{b}$ is the dot product and $\lVert \mathbf{a}\rVert$ is the Euclidean norm (magnitude). A critical edge case is the zero vector, which has no direction. By convention in this problem, if either vector is all zeros, the similarity is defined as 0.0.

The threshold parameter is the hyperparameter that controls the trade-off between cache hit rate and accuracy. A high threshold requires high similarity, resulting in fewer hits but higher confidence in the served answer. A low threshold increases hits but risks serving irrelevant answers. This problem simulates the evaluation of such a system by replaying a query log and tracking performance metrics.

2. Algorithm Approach

The problem requires simulating a sequential insertion and lookup process. Since the cache state changes dynamically (new entries are added on misses), you cannot pre-compute all similarities. Instead, you must process queries one by one, maintaining the current state of the cache.

The core algorithmic pattern is linear scan with dynamic state update. For each incoming query:

1. Iterate through all currently stored entries in the cache.
2. Compute the cosine similarity between the incoming query vector and each cached vector.
3. Identify the maximum similarity.
4. Compare the maximum similarity against the threshold to determine if it is a hit or a miss.
5. Update the cache and statistics accordingly.

This approach is essentially an online algorithm where decisions are made based on the current state without knowledge of future queries. The "ties go to the earliest inserted entry" rule implies that the order of insertion matters, so the cache should be maintained as an ordered list (e.g., a Python list) to preserve insertion order.

3. Step-by-Step Strategy

1. Initialize State Variables:

• Create an empty list for the cache to store entries. Each entry should retain its id and vec.
• Initialize counters: hits = 0, misses = 0.
• Initialize hit_map as an empty list to store [query_id, serving_entry_id] pairs.

2. Process Each Query:

• Loop through each query in the input queries list.
• Extract the current query's id and vec.

3. Compute Similarities:

• Initialize max_sim = -1.0 (since cosine similarity is $\ge -1$) and best_entry_id = None.
• Iterate through each cached_entry in the cache.
• Calculate the cosine similarity between the current query vector and the cached_entry vector.
• Handle the zero-vector edge case: if either vector has a norm of 0, similarity is 0.0.
• Otherwise, compute $\frac{\mathbf{a} \cdot \mathbf{b}}{\lVert \mathbf{a}\rVert \lVert \mathbf{b}\rVert}$.
• Round the similarity to 6 decimal places using round(sim, 6). This is crucial for reproducibility.

4. Determine Best Match:

• If the current sim is strictly greater than max_sim, update max_sim and best_entry_id.
• If sim equals max_sim, do not update. This preserves the "earliest inserted" tie-breaking rule because we iterate in insertion order and only update on strict improvement.

5. Evaluate Hit or Miss:

• If max_sim >= threshold:
• Increment hits.
• Append [query_id, best_entry_id] to hit_map.
• Do not add the query to the cache.
• Else:
• Increment misses.
• Append the current query (id and vec) to the cache.

6. Final Calculations:

• Calculate hit_rate: if len(queries) == 0, return 0.0. Otherwise, round(hits / len(queries), 4).
• cache_size is len(cache).
• Return the dictionary with hits, misses, hit_rate, hit_map, and cache_size.

4. Common Pitfalls

• Floating-Point Precision: The problem explicitly requires rounding similarities to 6 decimal places before comparison. Failing to do this can lead to incorrect hit/miss decisions due to tiny floating-point errors. Always use round(sim, 6).
• Zero Vector Handling: If a vector is all zeros, its norm is 0, leading to division by zero. You must check for this case explicitly and return 0.0 similarity.
• Tie-Breaking Logic: The rule "ties go to the earliest inserted entry" means you should only update the best match if the new similarity is strictly greater than the current maximum. If you use >=, you will incorrectly update to the later entry.
• Cache Update Timing: On a hit, you must not insert the query into the cache. The cache only grows on misses. Inserting on hits will corrupt the cache size and future similarity calculations.
• Hit Rate Rounding: The final hit_rate must be rounded to 4 decimal places. Ensure you handle the empty query list case separately to avoid division by zero.
• Vector Norm Calculation: Remember that the Euclidean norm is the square root of the sum of squared elements. Do not forget the square root.

5. Time & Space Complexity

• Time Complexity: $O(N \cdot M \cdot D)$, where $N$ is the number of queries, $M$ is the maximum size of the cache (which is at most $N$), and $D$ is the dimensionality of the vectors. In the worst case (all misses), the cache grows to size $N$, and for each query, we compare against all previous entries. Each comparison takes $O(D)$ time to compute the dot product and norms.
• Space Complexity: $O(N \cdot D)$ to store the cache. In the worst case, all queries are misses, so we store all $N$ vectors, each of dimension $D$. The hit_map also takes $O(N)$ space in the worst case (all hits).