Implement SAVE Eviction Algorithm

�
SAVE_IEEE_Paper (5).pdf
Main Idea
The paper proposes SAVE (Semantic-Aware Vector Eviction), a new cache eviction algorithm designed specifically for vector databases and semantic caching.
Traditional policies such as LRU, LFU, FIFO, and SIEVE mainly consider how recently or frequently an item was accessed. SAVE additionally considers where the vector is located in the embedding space—particularly whether it represents a dense semantic cluster. �
SAVE_IEEE_Paper (5).pdf
Problem
Vector databases use expensive Approximate Nearest Neighbor (ANN) searches. Every cache miss can require disk I/O and graph traversal, increasing latency.
The paper argues that traditional eviction policies are “geometry blind.” They may remove a vector that is a central representative of a semantic cluster, causing many related future queries to become cache misses. �
SAVE_IEEE_Paper (5).pdf
How SAVE Works
SAVE calculates a utility score for each cached vector using three factors:
Semantic density – how close the vector is to other vectors in the cache.
Recency – how recently the vector was accessed.
Frequency – how often the vector has been accessed.
These are converted into percentile ranks and combined:
Utility = density weight + recency weight + frequency weight
The algorithm then evicts the vector with the lowest utility score. �
SAVE_IEEE_Paper (5).pdf
SAVE also dynamically adjusts the importance of these factors every 50 requests, allowing it to respond to changing workloads. �
SAVE_IEEE_Paper (5).pdf
Experimental Setup
The authors tested SAVE against LRU, LFU, and SIEVE using:
CLINC150: 22,500 utterances, 150 intent classes
TREC: 5,952 questions, 50 classes
384-dimensional embeddings
10,000 queries
Three cache capacities: 5%, 15%, and 30%
Three locality levels: weak, medium, and strong �
SAVE_IEEE_Paper (5).pdf
Results
CLINC150: SAVE achieved the highest hit ratio in 7 of 9 experimental conditions. LFU performed slightly better in two very-low-capacity conditions. �
SAVE_IEEE_Paper (5).pdf
TREC: SAVE achieved the highest hit ratio in all 9 conditions, with improvements over SIEVE of up to 10.2% and over LFU of up to 8.0% in the reported settings. �
SAVE_IEEE_Paper (5).pdf
Performance Trade-off
SAVE takes more time to make an eviction decision—roughly 40–202.5 µs, compared with about 7–62.6 µs for the baseline policies.
However, the paper argues that this extra microsecond-level cost is outweighed by avoiding backend ANN searches that can take 5–15 ms. In one example, SAVE reduced average end-to-end latency by 168.5 µs (8.1%). �
SAVE_IEEE_Paper (5).pdf
Conclusion
The paper's central contribution is that cache eviction for vector databases should consider semantic geometry, not just time and frequency. SAVE combines semantic density + recency + frequency and dynamically adapts their weights.
The experiments reported in the paper show improved semantic cache hit ratios over LRU, LFU, and SIEVE, while the additional eviction computation is reported to be amortized by the reduction in expensive backend searches. �
SAVE_IEEE_Paper (5).pdf
In one sentence:
SAVE keeps vectors that are not only popular or recent, but also semantically important to a cluster, helping vector caches serve more queries without accessing the expensive backend.