Advancements in image search and nearest neighbor algorithms from 2021 to 2026

The one-line version

Searching images is two problems wearing one coat. First, turn a picture into numbers in a way that puts similar pictures near each other. Second, given a new set of numbers, find the nearest ones among a billion without comparing against all billion.

Between 2021 and 2026 both halves changed, and a third thing changed underneath them that almost nobody planned for: the price of keeping the numbers anywhere at all.

If you only remember one sentence: the field spent five years discovering that the expensive part was never the search, it was the storage, and then reorganising everything around that.

Five years, briefly

How image search actually works

A model reads a photo and produces a list of numbers. Not a caption, not tags: just a long list, typically a few hundred to a few thousand of them. That list is called an embedding, and the useful property is that pictures which look alike, or mean alike, produce lists that are numerically close together.

Treat each list as coordinates. Two numbers give you a point on a page; a thousand numbers give you a point in a thousand-dimensional space that you cannot picture but can absolutely do arithmetic in. Every photo in the library becomes a point. Searching is then embarrassingly simple to state: turn the query into a point too, and find the points nearest to it.

The trouble is the word "find". Checking the distance to every stored point is exact and hopeless: at a billion images it is a billion distance calculations for every single search. So instead you build a map in advance. Connect each point to a few of its nearest neighbours, and you get a graph you can walk. Start anywhere, look at your neighbours, step to whichever one is closer to the query, repeat until no neighbour is an improvement.

That is the core trick, and the family of methods built on it, of which HNSW is the one you will meet most often, has dominated the field for the entire period. Watch the counters above and you can see why: roughly a dozen comparisons instead of all 120. At a billion points the gap is the difference between impossible and instant.

You also get the catch for free. Greedy walking can stop at a point that is closer than all its neighbours but is not the closest point overall. It gets the right answer most of the time, not every time. That is what "approximate" means, and it is why every paper in this field reports a recall number: the fraction of the time the search found what an exhaustive scan would have found. The entire discipline is a negotiation between recall, speed and size.

That negotiation has a knob, and it is worth turning yourself.

What you embed

In January 2021 you searched images with images. By March you could search them with sentences. CLIP trained a pair of models on hundreds of millions of image and caption pairs with one instruction: put a picture and its caption in the same place. The result was a shared space where "a dog on a skateboard" lands near photos of dogs on skateboards, with no tags, no labels and no training for that specific query.

That is the single most consequential thing in this whole story, because it turned image search into something ordinary people could use with words. It also quietly created a problem that took three years to name, which we will come back to.

The rest of the representation story is a split that has stayed remarkably stable. Two different jobs, two different winners:

Three developments matter beyond that split, and the first is the cheapest lever anyone has found. Matryoshka embeddings (2022) train the important information into the leading numbers, so you can simply cut the list short.

The second is ColPali (2024), which went the other way: instead of squeezing a document page into one vector, keep one for every patch of the image.

And third, a corrective. In 2025 the ILIAS benchmark hid 1,000 specific objects among 100 million unrelated photographs and found that models fine-tuned on one domain fall apart outside it, and that old-fashioned local feature matching, the pre-deep-learning technique everyone assumed was retired, still earns its place when the picture is cluttered. Big general embeddings did not make the careful second pass unnecessary. They just moved it later in the pipeline.

How you search it

HNSW was already the default in 2021 and is still the thing most systems ship. The diagram above showed a single graph, which is most of the idea but not all of it. The "hierarchical" part is a stack of graphs.

That structure has barely changed since 2018. What changed is everything around it.

Compression got a proof, then moved inside the graph

Storing a 1,536-number embedding as full-precision decimals costs about 6 kilobytes per image. Shrink each number and everything gets cheaper: less memory, less disk, and faster comparisons because you are moving fewer bytes. People had been doing this for years by feel. In 2024 RaBitQ showed how to squeeze each number down to a single bit with a mathematical bound on how wrong the result can be. A guarantee rather than a hope, which is what let it move from papers into products: Elasticsearch and Lucene ship it under the name BBQ.

The follow-on was structural. If compression is that good, why keep it as a separate step? SymphonyQG (2025) folded it into the graph traversal itself and dropped the traditional "re-check the shortlist at full precision" pass entirely.

An independent 2026 benchmark across 22 implementations and 19 datasets settled the argument: every top-performing method now uses compression somewhere, and a compressed HNSW beats a full-precision HNSW outright. Storing your vectors uncompressed is no longer the safe conservative choice. It is just the expensive one.

Compression stopped being how you saved money and became how you went fast.

The question CLIP created

Here is the problem that took three years to name. Every graph index is built on an assumption nobody wrote down: that queries look like the data. You build the map out of your stored images, so the map is shaped for journeys that start where images live.

Every index was built assuming the question would look like the answer.

A text query does not start there. It is a sentence embedding, aimed at an image collection. The two are comparable by construction, but they are not co-located, and the images that genuinely answer a text query turn out to sit far apart from each other rather than in a tidy cluster.

RoarGraph (2024) diagnosed this and attacked it the obvious way once you see it: build the graph using the query distribution as a guide, not the stored vectors alone. It reports a substantial speedup over general-purpose indexes on cross-modal workloads.

The honest postscript is that the problem is better named than solved. The 2026 VIBE benchmark ran the specialists against the generalists and found that on text and text-to-image workloads the best general-purpose methods still won, Glass, NGT-QG and SymphonyQG among them, even though those same methods degrade sharply on out-of-distribution queries. The specialists did win on a different class of workload. So this is a live argument, not a closed one, and possibly more a story about how much engineering has gone into the mature implementations than about the underlying idea.

The problems that replaced raw speed

The clearest signal of the field growing up is what the 2023 Big-ANN competition chose to measure. Not "who is fastest". Four tracks: search with filters, because nobody searches an unfiltered catalogue; search over sparse vectors; search over a changing index, because real collections gain and lose items; and search with out-of-distribution queries, the text-against- images problem above.

Those are all boring production concerns, which is precisely the point. Filtering in particular went from an afterthought to a research area of its own, because "find similar shoes, in stock, under fifty pounds, ships to the UK" defeats a naive graph walk in a way that pure similarity never does.

Two more worth knowing. MUVERA (2024) found a way to compress a whole set of vectors, the ColPali-style representation, into a single vector whose comparisons approximate the expensive set comparison, with a proof attached. And LEANN (2026) went the other direction entirely: throw the stored embeddings away and recompute them on demand, which sounds absurd until you see the number.

Where it lives

This is the part with no famous paper attached, and it may have decided more architectures than any algorithm in this post.

In 2021, serious vector search meant holding everything in memory, because that is where the speed was. Memory is the most expensive storage there is. Three things then lined up: solid-state drives got fast enough to be only a few times slower than memory while costing a fraction, and cloud object storage picked up the consistency guarantees that let you treat it as a real database rather than a filing cabinet.

The consequence shows up in what people build rather than what they publish. Search engines became stateless things sitting in front of object storage, with local disk used purely as a cache. Collections that were previously unaffordable to keep online became nearly free to leave sitting there, and workloads with many rarely-touched datasets, a per-customer index that gets opened once a week, went from the worst case to the ideal one. Amazon shipped a native vector layer on top of S3 in 2025, which is the clearest sign that the argument is over.

What you actually see

All of the above surfaced in one visible change: pointing your phone at something stopped returning a page of visually similar pictures and started answering questions about it.

The mechanism Google describes is worth understanding, because it explains why modern visual search feels different rather than just better. A photo is no longer one query. A model identifies the individual objects in the scene and how they relate to each other, then issues many searches at once, about the whole image and about each object in it, and composes the answers. Google calls it query fan-out, and by 2026 the visual version had reached the point where you can photograph an outfit and get every item in it looked up simultaneously rather than circling them one at a time.

So the retrieval step stopped being the product. It became one move inside a longer reasoning loop, which is also why the newest research direction is agents that decide what to search for, and re-run the search when the first answer is not good enough.

The six shifts that mattered

1. 01

   Language became the interface. CLIP made a sentence a valid query for a picture. It also created the mismatch problem that took until 2024 to name, and that is still being argued about.

2. 02

   Compression stopped being a compromise. RaBitQ gave it error bounds you can prove, which is what let it into production systems, and SymphonyQG then folded it into the search itself.

3. 03

   Boring problems became the frontier. Filters, updates and awkward queries replaced raw throughput as the thing worth publishing about.

4. 04

   Multi-vector went from too expensive to routine. ColPali proved keeping one vector per region was worth it. MUVERA made it affordable.

5. 05

   Storage moved from memory prices to object-storage prices. This changed what is buildable more than any single algorithm did.

6. 06

   Retrieval became a step, not an answer. A search result is now the input to a model that reasons about it, and often searches again.

A 2026 default stack

If you were building image search today, the uncontroversial choices, in order:

One thing that is not in the diagram because it depends on your traffic: if text-to-image is your main path, build the index with your query distribution in mind rather than from the stored vectors alone. It is the step most people skip, and the section above is why.

The GPU question is the one genuinely open choice. Building indexes on a GPU is dramatically faster, but the dataset has to fit in GPU memory, so the common production answer is to build on GPU and serve on CPU.

Still open

• Compressed graphs that accept fast updates. The layouts that make compressed search fast are the same layouts that make insertion painful.
• Filtering on compressed graphs. Papers optimise these two axes separately and they do not compose cleanly.
• Region-level retrieval. ColPali can point at a spot on a page, but the benchmarks still score whole pages.
• Out-of-distribution queries. Named in 2024, still not settled: purpose-built indexes lose to well-engineered general ones on exactly the text-to-image workload they were designed for.
• Better measurement. A 2026 paper argues recall is the wrong target, because it can drop a long way without the user noticing, and proposes measuring the quality of what you retrieved instead of its overlap with a perfect answer.
• Multi-vector indexes that fit ordinary databases. Right now they need specialist support.

Sources

Split by how much weight each deserves. "Peer-reviewed" here means I checked the venue record rather than assuming it from an arXiv link, and several papers moved into the preprint group when that check came back empty. A preprint is not a worse paper. It is an unrefereed one, and the quantization figures this post leans on hardest come from exactly there.