# SOAR: Improved Indexing for Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 16 references that are in the map.
- First posted on arXiv 31 Mar 2024.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)

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

- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Synthetic bootstrapped pretraining](https://mlsanity.com/paper/2509.15248/) (2025)
- [LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.18926/) (2024)
- [Studying Classifier(-Free) Guidance From a Classifier-Centric Perspective](https://mlsanity.com/paper/2503.10638/) (2025)
- [SmartChunk Retrieval: Query-Aware Chunk Compression with Planning for Efficient Document RAG](https://mlsanity.com/paper/2602.22225/) (2025)
- [Amortized Maximum Inner Product Search with Learned Support Functions](https://mlsanity.com/paper/2603.08001/) (2026)
- [Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces](https://mlsanity.com/paper/2506.06557/) (2025)
- [Large-Scale Graph Building in Dynamic Environments: Low Latency and High Quality](https://mlsanity.com/paper/2507.10139/) (2025)
- [Welfarist Formulations for Diverse Similarity Search](https://mlsanity.com/paper/2602.08742/) (2026)
- [SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor framework](https://mlsanity.com/paper/2602.17330/) (2026)
- [PRAG: End-to-End Privacy-Preserving Retrieval-Augmented Generation](https://mlsanity.com/paper/2604.26525/) (2026)
- [Region-Aware CLS Token Augmentation for Fine-Grained Image Retrieval](https://mlsanity.com/paper/2610.10991/) (2026)

## Abstract (arXiv)

This paper introduces SOAR: Spilling with Orthogonality-Amplified Residuals, a novel data indexing technique for approximate nearest neighbor (ANN) search. SOAR extends upon previous approaches to ANN search, such as spill trees, that utilize multiple redundant representations while partitioning the data to reduce the probability of missing a nearest neighbor during search. Rather than training and computing these redundant representations independently, however, SOAR uses an orthogonality-amplified residual loss, which optimizes each representation to compensate for cases where other representations perform poorly. This drastically improves the overall index quality, resulting in state-of-the-art ANN benchmark performance while maintaining fast indexing times and low memory consumption.