Visual Search: Turning “Does It Look Alike” Into “Is It Close By”

In one line

The book's first case study, and what it really teaches is a problem transformation. Search-by-image looks like “make a model judge whether two images are alike”; the actual solution is representation learning — encode every image into a fixed-length vector so that visually similar becomes close in vector space. Once that transformation lands, the battleground moves off the model and onto retrieval: how do you find the nearest few dozen among a billion vectors in milliseconds?

Glossary

Where it sits

This is the first of the ten case studies in Part II of Machine Learning System Design Interview, and the first full run of the seven-step framework from Ch 1. It opens the book's single most reused skeleton — encode into vectors, retrieve with ANN, then re-rank — which Ch 4 (YouTube video search) and Ch 9 (similar listings) both inherit with a different modality bolted on. In the real world it maps to Pinterest Lens, Google Lens and Alibaba's image search.

What the chapter is solving

A user has an image and wants “things that look like this”, but cannot produce a keyword. Text search indexes words, and visual likeness does not translate into words — “three diagonal stripes near the toe” is neither writable nor matchable.

The second pain point is scale, and it bites harder. Take a library of 1 billion images, each encoded as a 256-dimensional float32 vector (float32 = 4 bytes per number): the vectors alone are 10⁹ × 256 × 4B ≈ 1 TB, and one exact search means computing the distance from the query to all billion — roughly 2.56 × 10¹¹ multiply-adds. Even at 10¹¹ operations per second that is several seconds per query, while the product needs p99 < 100ms. Without solving this you have built a demo that works on a hundred thousand images.

The core content, worked through

1. The decisive move: from “judge” to “encode”

The most natural first model is a binary classifier: feed in two images, output alike / not alike. Its fatal flaw isn't accuracy, it's the shape of the compute — answering one query means running a forward pass against every image in the library, a billion of them. That road does not exist in engineering terms.

The book splits it in two instead. Train an encoder; encode every library image offline, once, and store the vectors. At query time encode exactly one image, then do a vector search. The same semantic problem, re-modelled, goes from “a billion inferences per query” to “one inference plus one vector lookup”. That is the real lesson here: in ML system design the biggest performance wins usually come from reframing the problem, not from optimising the model.

2. Building the training data: where do positives come from?

Contrastive learning needs a tuple of (query image, 1 positive, n negatives). Negatives are easy — sample randomly from the library. Positives are the hard part, and the book gives three routes, each with a price (see Table 1 below): human annotation is accurate but expensive; data augmentation (rotate, crop, recolour the query image and call the result a positive) is free and unlimited, but the model learns “different renderings of the same photograph”, not “the same kind of object”; user interaction (whatever a user clicked after searching with this image counts as a pair) is plentiful and naturally aligned with the business, which is why the book makes it the workhorse — at the cost of noise and exposure bias.

3. How contrastive learning actually shapes the vectors

The mechanism is plain. The query and every candidate (1 positive plus n negatives) pass through the same encoder with shared weights and each comes out as a vector. Compute the similarity between the query vector and each candidate vector — usually just a dot product. Push those n+1 similarities through a softmax to get probabilities, then use cross-entropy to drive the probability of the positive towards 1.

The intuition: every training step pulls the positive a little closer and pushes the n negatives a little further away. After hundreds of millions of steps the whole vector space has been combed into clusters that follow visual semantics. The count of negatives n is an important dial — a larger n gives a richer “push away” signal and trains better, at a memory and compute cost that grows linearly in n.

4. Two pipelines: offline indexing and online prediction

The system lands as two independent pipelines, and that is the architectural skeleton of the whole chapter.

The indexing pipeline (offline) runs the entire library through the encoder and loads the vectors into an index; new uploads arrive incrementally. Being batch work, slowness is tolerable — but it carries a hidden constraint: change the encoder version and every vector in the library must be recomputed. Re-encoding a billion images is a multi-day job, which puts a hard ceiling on how often the model can be iterated.

The prediction pipeline (online) runs query image (with optional user crop) → preprocessing (resize to a fixed size such as 224×224, normalise pixel values) → encoder produces a vector → ANN retrieves top-k candidates → re-ranking service. Re-ranking is the step most often skipped, and it decides whether the thing can ship: among the “k most similar” that ANN returns are exact duplicates, policy-violating content, images their owners marked private, and posts from accounts this user has blocked. Vector distance stops none of them; only business rules in the re-ranking layer do.

5. Approximate nearest neighbour: the accuracy / latency / memory triangle

Exact search is O(N×D) for N vectors of D dimensions, which is out at billion scale. The book sorts ANN into four families: trees (recursively partition the space into cells — Annoy), locality-sensitive hashing (LSH) (design hashes so that nearby vectors are likelier to collide into the same bucket), clustering / quantisation (k-means the library into tens of thousands of clusters, scan only the nearest few, and compress each vector down to a code of a few dozen bytes), and graphs (wire the vectors into a navigable neighbour graph and greedily walk towards closer neighbours — HNSW). The libraries it names: Meta's Faiss, Google's ScaNN, Spotify's Annoy.

The one line worth saying out loud in an interview: ANN metrics are always a triple — recall, QPS/latency, and memory footprint. None of them means anything alone. “We hit 99% recall” is worthless if the price was scanning half the library.

6. Evaluation: why the offline metric is unusually hard to pick here

The book rules candidates out one at a time, and that passage is a good metrics lesson in itself. MRR (the reciprocal rank of the first hit) throws away every hit after the first — wasteful when the product is supposed to return a whole screen of similar images. recall@k needs to know how many relevant images exist in the entire library, and for visual similarity that denominator is simply unknowable. precision@k counts how many of the top k are right while ignoring order entirely, treating rank 1 and rank 10 as equals. nDCG handles graded relevance (“somewhat similar” versus “very similar”) but demands graded ground-truth labels, which are expensive. That leaves mAP: with binary relevance it counts both how many you hit and how high you ranked them, which makes it the right fit here.

Online metrics go back to the business: click-through rate on the suggested images, and average time users spend on them.

Key trade-offs

Table 1 · Where positives come from (this decides what “similar” ends up meaning)

Table 2 · Four ANN families and what each one trades

Table 3 · Picking the offline ranking metric (the book's elimination process)

All three tables point at one sentence: every choice in this problem buys accuracy with cost, latency or rigidity. What an interview actually tests is whether you can justify one choice given a library size, a latency budget and a memory budget.

Why it matters / in real systems

The skeleton — encode into vectors, retrieve with ANN, re-rank — stopped belonging to image search long ago. Semantic search, the retrieval stage of a recommender, the retrieval layer of RAG, dedup and fraud matching: all the same skeleton with a different encoder bolted on. Learning this chapter gets you the general template for modern retrieval.

Traps and open questions

• Modelling it as binary classification. Training an “are these two alike” model sounds reasonable and requires a forward pass over the entire library per query. It is the number-one way to fail this question.
• Using augmentation as the only source of positives. The resulting system only finds near-duplicates: upload a shoe and it returns ten crops of your own photo.
• Skipping re-ranking. Vector distance has no notion of “policy-violating”, “private” or “same image uploaded twice”. Without that layer the system cannot ship.
• Reporting recall without latency and memory. The three ANN numbers have to travel together; any one of them alone is trivially gamed.
• Forgetting the cost of rebuilding the index. A new encoder version invalidates every vector in the library. This alone kills a lot of “we'll iterate the model weekly” proposals.
• Exposure bias feeding itself. Positives come from clicks, and clicks only happen on images that were shown — so long-tail content never enters the training set and the system narrows over time. The book flags the risk but offers no systematic remedy.
• Dated in one respect. Written in 2023, the chapter's spine is still “single-modality image encoder plus a self-built index”. Two things have shifted the default answer since: CLIP-style shared image-text vector spaces became mainstream, letting search-by-image and search-by-text share one index; and vector databases pulled the index out of application code into a managed service, so hand-rolling ANN is no longer the default.

Takeaways