# Ascent Similarity Caching with Approximate Indexes

arXiv: https://arxiv.org/abs/2107.00957 · HTML: https://mlsanity.com/paper/2107.00957/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 76 references that are in the map.
- First posted on arXiv 2 Jul 2021.

## Builds on (most cited first, 27 of 27)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Edge Intelligence: Paving the Last Mile of Artificial Intelligence with Edge Computing](https://mlsanity.com/paper/1905.10083/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Clipper: A Low-Latency Online Prediction Serving System](https://mlsanity.com/paper/1612.03079/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Adaptive Caching Networks with Optimality Guarantees](https://mlsanity.com/paper/1604.03175/) (2016)
- [Wireless Caching: Technical Misconceptions and Business Barriers](https://mlsanity.com/paper/1602.00173/) (2016)
- [Similarity Caching: Theory and Algorithms](https://mlsanity.com/paper/1912.03888/) (2019)
- [Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees](https://mlsanity.com/paper/2105.02510/) (2021)
- [Femto-Caching with Soft Cache Hits: Improving Performance through Recommendation and Delivery of Related Content](https://mlsanity.com/paper/1702.04943/) (2017)
- [Elastic Provisioning of Cloud Caches: a Cost-aware TTL Approach](https://mlsanity.com/paper/1802.04696/) (2018)
- [Geometric Approach to Subdifferential Calculus](https://mlsanity.com/paper/1504.06004/) (2015)
- [Worst-case Bounds and Optimized Cache on Mth Request Cache Insertion Policies under Elastic Conditions](https://mlsanity.com/paper/1812.07264/) (2018)
- [A Swiss Army Knife for Dynamic Caching in Small Cell Networks](https://mlsanity.com/paper/1912.10149/) (2019)
- [Adaptive Offline and Online Similarity-Based Caching](https://mlsanity.com/paper/2010.07585/) (2020)
- [Content Placement in Networks of Similarity Caches](https://mlsanity.com/paper/2102.04974/) (2021)

## Built on by (most cited first, 2 of 2)

- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Online Two-Stage Submodular Maximization](https://mlsanity.com/paper/2510.19480/) (2025)

## Abstract (arXiv)

Similarity search is a key operation in multimedia retrieval systems and recommender systems, and it will play an important role also for future machine learning and augmented reality applications. When these systems need to serve large objects with tight delay constraints, edge servers close to the end-user can operate as similarity caches to speed up the retrieval. In this paper we present AcCAI, a new similarity caching policy which improves on the state of the art by using (i) an (approximate) index for the whole catalog to decide which objects to serve locally and which to retrieve from the remote server, and (ii) a mirror ascent algorithm to update the set of local objects with strong guarantees even when the request process does not exhibit any statistical regularity.