Abstract
Similarity caching allows requests for an item to be served by a similar item already in the cache, a technique increasingly vital for recommendation systems, multimedia retrieval, and machine learning inference. Despite the practical benefits, calculating the hit rate for similarity-aware policies like SIM-LRU and RND-LRU has remained an open challenge due to the complex coupling between items. This paper introduces the first algorithm to compute these hit rates by extending the popular Time-To-Live (TTL) approximation—traditionally used for classic caching—to the similarity caching domain. Evaluated against synthetic and real-world datasets, the proposed fixed-point iterative algorithm demonstrates high accuracy and computational efficiency.
Introduction
In traditional caching systems, a request results in a "hit" only if the exact requested item is present in the cache. However, modern data-intensive applications often operate on the principle of similarity. In image retrieval or ML model serving, a "close enough" result is often as valuable as an exact match. Similarity caching leverages this by allowing a cached item $i'$ to satisfy a request for item $i$ if the distance between them is within a predefined threshold.
While similarity caching significantly improves system efficiency, it introduces a significant analytical hurdle: item coupling. In classic Least Recently Used (LRU) caches, an item’s presence is largely independent of others. In similarity caching, the probability of an item being cached depends on the request rates and cache status of all its "neighbors" (similar items). This paper addresses this gap by providing a robust mathematical framework to estimate performance metrics for similarity-aware policies.
The Analytical Challenge: Beyond Classic LRU
The primary difficulty in modeling similarity caching lies in how items are "refreshed" or inserted into the cache. In a standard LRU cache, an item is moved to the front of the queue only when it is specifically requested. In similarity caching, an item can be refreshed by a request for any item within its similarity radius. This creates a dependency network where the "On-period" (the time an item spends in the cache) is extended by proxy requests.
Existing models like Che’s approximation (the TTL approximation) work well for independent items by assuming each item stays in the cache for a deterministic "characteristic time" $t_C$. To apply this to similarity caching, one must account for the fact that $t_C$ is influenced by the aggregate request rates of a neighborhood, yet items within that neighborhood compete for the same cache space.
Methodology: The Fixed-Point Iterative Algorithm
The authors propose an algorithm that adapts the TTL approximation through a two-step fixed-point iteration. The core idea is to model the interaction between item occupancy and the effective request rates.
- Step A (Occupancy Calculation): Given an estimate of the rates at which items are requested and refreshed, the algorithm calculates the probability that each specific item is currently in the cache.
- Step B (Rate Update): Using these occupancy probabilities, the algorithm updates the estimated request and refresh rates. For instance, if a neighbor is likely to be in the cache, it may "shield" other items from being cached or refreshed.
The algorithm iterates between these steps until the values for $t_C$ and the occupancy probabilities stabilize (converge). This approach allows the model to capture the "similarity gain"—the boost in hit rate provided by approximate matches—without requiring exhaustive simulations.
Experimental Evaluation
The researchers validated their model using two distinct datasets:
- Synthetic Grid Trace: 10,000 items arranged on a $100 \times 100$ 2D grid. Dissimilarity was defined by Euclidean distance, and item popularity followed a Zipf distribution.
- Amazon Product Trace: A real-world dataset comprising approximately 10,000 products. Items were represented by 100-dimensional image embeddings. Request rates were inferred from product review counts, providing a realistic test of the algorithm's performance on high-dimensional, non-uniform data.
Key Insights
The study revealed several critical aspects of similarity caching dynamics:
- Extended Characteristic Time: In similarity caching, the characteristic time $t_C$ is significantly larger than in classic LRU. Approximate hits keep items "alive" in the cache longer than they would stay if they only responded to exact matches.
- Failure of Naive Aggregation: A common shortcut is to sum the request rates of all neighbors and treat the cache as a standard LRU (the "LRU-agg" approach). The authors demonstrate that this consistently underestimates the hit rate because it ignores the nuanced competition and "shielding" effects between similar items.
- The "Chessboard" Effect: The theoretical model predicts a symmetric, chessboard-like occupancy pattern where a popular item remains cached while its immediate neighbors do not (as the popular item satisfies their requests). While real-world data is less perfectly symmetric, the approximation remains remarkably accurate in predicting aggregate hit rates.
Results and Performance
The proposed algorithm ("Ours-SIM" and "Ours-RND") significantly outperformed standard LRU models and greedy static allocation benchmarks. On the Amazon dataset, the algorithm’s predictions closely tracked empirical hit rates across various cache capacities. Furthermore, the method is computationally efficient, typically reaching convergence in fewer than 50 iterations, making it a practical tool for system designers.
Conclusion and Future Work
This work provides the first successful application of TTL approximations to similarity caching. By accounting for the coupling of items, the authors have turned a previously intractable problem into a manageable iterative calculation.
Future research will address current limitations, such as "simultaneous caching"—where the model currently struggles to account for the fact that two extremely similar items are rarely cached simultaneously. Additionally, the authors plan to explore the asymptotic behavior of the TTL approximation as catalog and cache sizes scale toward infinity, further refining the accuracy of this new analytical frontier.
Summary updated