Machine learning and high dimensional vector search
Matthijs Douze, Meta FAIR · 2025
Read Machine learning and high dimensional vector search by Matthijs Douze, Meta FAIR (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-2502-16931.txt.
Introduction
Matthijs Douze reflects on why machine learning, for all its reach, has barely changed the craft of vector search, in an opinion paper from 2025. The two fields grew side by side in neighboring research towns. Big data fields around them were remade by learning, yet search over high-dimensional vectors kept its classic tools.
The essay walks the many bridges between the fields: learned indexes, compressed codes, and graph methods among them. It asks what kept those bridges lightly used, from speed demands to exactness needs. Douze writes from inside a major search library's team. The piece is short and pointed, meant to stir both camps. It closes by scanning where learning might still land.
Catalog record
| CREATOR | Matthijs Douze, Meta FAIR |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 13 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-16931
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Machine learning and high dimensional vector search Matthijs Douze, Meta FAIR Abstract Machine learning and vector search are two research topics that developed in parallel in nearby communities. However, unlike many other fields related to big data, machine learning has not significantly impacted vector search. In this opinion paper we attempt to explain this oddity. Along the way, we wander over the numerous bridges between the two fields. 1 Introduction Most high-dimensional vector search methods are based on statistical tools, signal processing approaches or graph traversal algorithms. Statistical tools include random projections [ 15 ] , dimensionality reduction (PCA and the SVD). Signal processing is employed primarily to compress vectors with quantization [ 30 , 4 , 22 ] Most recent indexing methods are rely on graphs [ 34 , 49 , 3 , 11 ] that are built with graph traversal heuristics. Vector search (VS) is used in machine learning (ML) for training data deduplication [ 39 ] and searching ML embeddings [ 28 , 5 ] . Therefore, there are many research teams around the world that are competent in both fields. In their seminal work The case for learned indexing structures [ 32 ] , Kraska et al. introduced a series of ML based algorithms to speed up classical indexing structures like hash tables and B-trees. These structures are building blocks of databases, e.g. a B-tree can be seen as a one dimensional VS index. They hoped to open “an entirely new research direction for a decades old field”. However, 7 years later, it is striking that ML has had very little impact on VS. No ML based method appears in the current VS benchmarks at any scale [ 2 , 47 , 46 ] . The most advanced ML tool that is widely used for VS is the k-means clustering algorithm. There is no deep learning, no use of high-capacity networks. In the following, we attempt to explain why this is the case. We work out a typical use case of VS (Section 2 ), then expose the fundamental limits of ML for VS (Section 3 ); in Section 4 , we review interesting applications in the other direction: VS for ML. 2 Information retrieval with machine learning Let’s start from a typical application of vector search: image retrieval. This is originally a classical ML problem, and we show how it converts to VS. We manage a collection of N images C=\{x_{1},\dots,x_{N}\} , where N is large, and possibly growing. From a given query image q , the objective is to find images in C that are relevant to it, for example because they represent the same object. N -way classifier. The most straightforward ML approach for this is to train a N -way classifier f_{1}(q)\in[0,1]^{N} that outputs a scalar score close to 1 for the images that are relevant and close to 0 for the others. The best matching item from the collection can be found without even accessing the images after the training phase: I_{1}=\mathrm{argmax}~f_{1}(q). (1) The model could be any standard image classification model, convolutional or transformer-based [ 25 , 19 ] . Note that processing images is inherently slow, since the raw pixels must be converted into semantically relevant information, which requires several neural net layers. More importantly, the model’s size needs to be proportional to the collection size N , and it is impossible to add or remove images from the collection after the model was trained. Pairwise comparison. Another approach is to design a function f_{2} that, given (x,x^{\prime}) returns a score that is high if x^{\prime} relevant to x and low otherwise. At search time, f_{2} is used to compare the query q with all the images from the collection (which must be accessible): I_{2}=\underset{i=1,\dots,N}{\mathrm{argmax}}~f_{2}(q,x_{i}). (2) The usual learning machinery can be deployed to train this function: given a training set of matching and non-matching images, the model is optimized to return 0 or 1 with, for example, a binary cross-entropy loss. This resolves the problem of the model size, that remains fixed, and adding/removing from the collection is painless. The issue with this approach is that the model f_{2} is still expensive to evaluate, and querying one image requires N evaluations (forward passes) of f_{2} . Therefore it is not tractable beyond a few hundred images. Embeddings. A way to avoid this is to force f_{2} to decompose as: f_{3}(x,x^{\prime})=S(E(x),E(x^{\prime})), (3) where E , the embedder (or feature extractor) is a function that computes a vector in d dimensions from an image, and S:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R} is a similarity function between embeddings. This is akin to kernel methods [ 6 , chapter 7] , and sometimes called a “two-tower” network. The feature extraction function E can be costly to evaluate, but it is performed beforehand, when the image is added to the collection: (e_{1},\dots,e_{N})=(E(x_{1}),\dots,E(x_{N})) is precomputed. At search time, we perform only simple vector comparisons with all N : I_{3}=\underset{i=1,\dots,N}{\mathrm{argmax}}~S(E(q),e_{i}) (4) From a ML point of view, since we impose a constraint on the function f_{3} , it is bound to be less accurate than the function f_{2} , that performs a direct comparison between items: there is an information bottleneck. The functions S and E are bound by an embedding contract [ 20 ] , that states that E should generate embeddings such that the comparison with S is semantically meaningful. Embedding extraction. There is a vast literature on embedding extraction for images. It started in the pre-deep era [ 31 , 40 ] . Later, image embedding models were first sampled from some layer of a classification model [ 5 ] , then trained specifically using a clustering supervision [ 9 ] , or variants of contrastive learning [ 16 , 10 , 12 , 29 ] . The embeddings can be specialized for different granularities of image matching: from class-level via instance-level to copy-level [ 7 , 41 ] . Embeddings can be extracted from other modalities as well, with slight variations. For text embeddings (like BERT [ 17 , 27 ] ) the size of the embedding vector is usually larger than the original text – embeddings are not guaranteed to compress the items they are computed from. These text embeddings are the basis for the retrieval augmented generation for LLMs [ 28 ] . Text and image embeddings can be matched together as with the CLIP embeddings [ 43 ] . Recommendation systems are often based on two-tower networks, with different embedding functions for the users and the items to recommend [ 38 ] . 3 Vector search with machine learning Performing the embedding search of Equation 4 is an operation whose complexity is \mathcal{O}(N\times d) for most similarity functions. The research on vector search aims at reducing the runtime when N becomes large, either by making it sub-linear or by reducing the linear factor. In the process, some accuracy can be sacrificed, and the brute force search of Equation 4 becomes an Approximate Nearest Neighbor Search (ANNS) task. Vector search is a linear classifier. Let’s assume that the similarity function, in Equation ( 4 ) is a dot product 1 1 1 This is without loss of generality: most standard distances can be reduced