CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search

Xiaoya Li, Xiaofei Sun, Albert Wang, Chris Shum, Jiwei Li · 2025

Read CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search by Xiaoya Li, Xiaofei Sun, Albert Wang, Chris Shum, Jiwei Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-02091.txt.

Introduction

Xiaoya Li and four co-authors let a learning system write faster nearest-neighbor search code by treating speed itself as the reward. Approximate nearest-neighbor search underpins retrieval-augmented generation and agent systems, and hand-tuning its algorithms is slow expert work. Their framework, CRINN, reframes the tuning as reinforcement learning with contrastive signals.

The system generates candidate implementations and keeps the ones that run faster while holding accuracy. Across six standard benchmark datasets it took first place on three and tied for first on two more. The authors argue the lesson extends beyond search: language models with reinforcement learning can automate sophisticated algorithmic optimization. Code is released publicly.

Catalog record

CREATORXiaoya Li, Xiaofei Sun, Albert Wang, Chris Shum, Jiwei Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-02091

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search Xiaoya Li, Xiaofei Sun, Albert Wang, Chris Shum, Jiwei Li Abstract Approximate nearest-neighbor search (ANNS) algorithms have become increasingly critical for recent AI applications, particularly in retrieval-augmented generation (RAG) and agent-based LLM applications. In this paper, we present CRINN, a new paradigm for ANNS algorithms. CRINN treats ANNS optimization as a reinforcement learning problem where execution speed serves as the reward signal. This approach enables the automatic generation of progressively faster ANNS implementations while maintaining accuracy constraints. Our experimental evaluation demonstrates CRINN’s effectiveness across six widely-used NNS benchmark datasets. When compared against state-of-the-art open-source ANNS algorithms, CRINN achieves best performance on three of them (GIST-960-Euclidean, MNIST-784-Euclidean, and GloVe-25-angular), and tied for first place on two of them (SIFT-128-Euclidean and GloVe-25-angular). The implications of CRINN’s success reach well beyond ANNS optimization: It validates that LLMs augmented with reinforcement learning can function as an effective tool for automating sophisticated algorithmic optimizations that demand specialized knowledge and labor-intensive manual refinement. 🖂 🖂 🖂 footnotetext: Email: {xiaoya_li, xiaofei_sun, albert_wang, chris_shum, jiwei_li}@deep-reinforce.com Figure 1: QPS versus recall curves for different models across six datasets. CRINN achieves achieves best-in-class performance on three out of them (GIST-960-Euclidean, MNIST-784-Euclidean, and GloVe-25-angular) and matching state-of-the-art results on two (SIFT-128 and GloVe-25). 1 Introduction Approximate nearest-neighbor search (ANNS) [ 20 , 21 , 6 , 7 , 19 , 12 , 5 ] aims at finding data points that are closest to a query point in high-dimensional spaces while trading off a small amount of accuracy for significant speedup over exact search methods. ANNS is of growing importance due to the unprecedented popularity of retrieval-augmented generation (RAG) [ 16 , 10 , 23 ] and agent-based LLM applications [ 25 ] , which require fast retrieval of relevant information from massive vector databases. Existing widely-used open-source projects use fundamental algorithms such as Vamana [ 12 ] and HNSW [ 20 ] as the backbone: DiskANN and ParlayANN [ 21 ] build upon Vamana, while FAISS [ 6 ] , Vespa 1 1 1 https://docs.vespa.ai/en/nearest-neighbor-search.html , Weaviate 2 2 2 https://weaviate.io/blog/vector-search-explained , Qdrant 3 3 3 https://github.com/qdrant/qdrant , Milvus 4 4 4 https://github.com/milvus-io/milvus , and GLASS [ 29 ] 5 5 5 https://github.com/hhy3/pyglass leverage HNSW, proposing different levels of optimization to cater for various scenarios. Existing optimizations for ANNS are mostly manual, where humans identify bottlenecks through profiling tools, analyze cache miss patterns, hand-tune parameters like graph degree and search beam width, carefully design data structures for memory locality, and iteratively experiment with different algorithmic variants based on hardware characteristics. This process requires deep expertise in computer architecture, parallel programming, and the mathematical properties of ANNS algorithms. With the increasing power of LLMs in code generation [ 9 , 11 ] , a natural question arises: can LLMs facilitate optimization by automatically generating and testing algorithmic improvements, learning from the execution speeds of previous implementations to propose better solutions, and discovering novel optimization patterns that human engineers might overlook? In this paper, we propose CRINN, a reinforcement learning-augmented LLM framework for automated ANNS optimization. The core of CRINN is a contrastive RL model that performs comparative analysis of previously generated code variants alongside their execution metrics, enabling the model to learn by distinguishing between effective and ineffective optimization strategies and generate better solutions. Through this contrastive learning approach, CRINN develops an understanding of which code patterns lead to performance improvements and which cause degradation. The generated code variants are evaluated based on execution time, with faster implementations receiving higher rewards in the RL training process. This reward signal drives the LLM to iteratively generate progressively more efficient ANNS implementations. By learning from the performance outcomes of its own generated code, CRINN effectively transforms the manual optimization process into an automated search through the space of possible implementations. Our experimental evaluation demonstrates CRINN’s effectiveness across six widely-used NNS benchmark datasets [ 1 ] . When compared against state-of-the-art open-source ANNS algorithms, CRINN achieves best performance on three of them (GIST-960-Euclidean, MNIST-784-Euclidean, and GloVe-25-angular); tied for first place on two of them (SIFT-128-Euclidean and GloVe-25-angular). More importantly, the success of CRINN carries broader implications beyond ANNS optimization. It demonstrates that RL-augmented LLMs can serve as powerful tools for automating complex algorithmic optimizations that traditionally require deep domain expertise and extensive manual tuning. As the demand for efficient vector search continues to grow with the proliferation of RAG and agent-based LLM applications, automated optimization frameworks like CRINN will become increasingly valuable for maintaining competitive performance across evolving hardware architectures and application requirements. 2 Background: HNSW We use HNSW (Hierarchical Navigable Small World) [ 20 ] as the optimization backbone. HNSW is a state-of-the-art graph-based ANNS algorithm that achieves high recall rates with logarithmic search complexity. Here we describe the core modules that most HNSW-based implementations adopt, on which our RL optimization is performed. 2.1 Graph Construction In HNSW, we first need to build a graph for base vectors, where each vector is represented as a node in the graph. As the search is performed through this graph for a given query, graph construction is a key step in HNSW. The graph construction module builds the graph through incremental insertion of vectors. HNSW constructs a multi-layer graph where each element is assigned to multiple layers based on an exponentially decaying probability distribution. Each new base vector is assigned to layer 0 with probability 1, and to each subsequent layer l with probability p^{l} , where p is typically set to 1/2\ln(2) . This creates a hierarchical structure similar to skip lists, enabling efficient navigation during search. For each layer where a vector is present, the algorithm performs a greedy search from the layer’s entry point to find the M nearest neighbors. The search parameter ef controls the number of candidates explored during this neighbor selection process. The algorithm maintains M connections for upper layers and M\times 2 connections for the bottom layer (layer 0) to ensure rich connectivity. It is worth noting that ef is a crucial parameter in HNSW, controlling the tradeoff between recall and speed. Larger values of ef mean exploring more candidates during the search phase, thus achieving higher recall at the cost of reduced speed. HNSW employs a heuristic pruning strategy to optimize the graph structure. This strategy maintains connectivity while promoting the small-world property by prioritizing diverse connections over purely nearest neighbors. Redundant edges that don’t contribute to search efficiency are removed, resulting in a graph that balances accuracy with traversal efficiency. 2.2 Search Given a constructed graph and an input query, the search module performs k-nearest neighbor search through a two-phase hierarchical process. The search begins with the upper layer, starting from the global entry point at the top layer. The algorithm greedily traverses each layer to find the single nearest neighbor, using this neighbor as the entry point for the next lower layer. This process continues until reaching the bottom layer (layer 0), effectively narrowing down the search space. At layer 0, the algorithm switches to a more exhaustive exploration strategy. It initializes a candidate set with the entry point from layer 1 and maintains a priority queue of ef nearest candidates (where ef\geq k ). The search iteratively

Read the complete text