Computing the Hit Rate of Similarity Caching

Younes Ben Mazziane, Sara Alouf, Giovanni Neglia, Daniel Sadoc Menasché

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.

  1. 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.
  2. 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

Abstract

Similarity caching allows requests for an item \(i\) to be served by a similar item \(i'\). Applications include recommendation systems, multimedia retrieval, and machine learning. Recently, many similarity caching policies have been proposed, but still we do not know how to compute the hit rate even for the simplest policies, like SIM-LRU and RND-LRU that are straightforward modifications of classical caching algorithms. This paper proposes the first algorithm to compute the hit rate of similarity caching policies under the independent reference model for the request process. In particular, our work shows how to extend the popular TTL approximation from classic caching to similarity caching. The algorithm is evaluated on both synthetic and real world traces.
BibTeX
@inproceedings{mazziane2022computing,
  author = {Younes Ben Mazziane and Sara Alouf and Giovanni Neglia and Daniel Sadoc Menasché},
  title = {{Computing the Hit Rate of Similarity Caching}},
  booktitle = {GLOBECOM},
  year = {2022},
  url = {https://openreview.net/forum?id=f4wTWU5KK1D},
}

Loading related content...

Figure