← All topics

Guide · Models · Topic 8 of 32

Retrieval and multimodal retrieval

Finding instead of generating: embeddings, ranking metrics, searching across text and images, large collections, and uses in robotics.

8 minute readBuilds on: Contrastive and multimodal learning

Finding instead of generating

Retrieval answers a question by finding the right item in a collection. A model that generates has to carry everything it knows in its weights. A model that retrieves can look things up, so its knowledge can be inspected, corrected and extended without retraining.

Two rows. Ahead of time: a collection passes through an encoder into an index holding one vector per item. At query time: a query passes through the encoder, the nearest vectors are looked up in the index to give the top 100, and a re-ranker narrows them to the top 10.
The standard pipeline. The collection is encoded once. Each query is encoded, matched against the stored vectors, and the short list is optionally re-ordered by a slower model.

Modern retrieval is built on embeddings. An encoder turns each item into a vector such that similar items have similar vectors, and searching becomes finding the nearest vectors to the query. The note on contrastive learning covers how such encoders are trained.

A worked example on robot data

The collection here is 1,516 camera frames, four from each of the 379 LIBERO demonstrations, embedded with a public CLIP image encoder. A query is one frame. A retrieved frame counts as relevant if it comes from a different episode of the same task.

Four query frames from different robot tasks, each followed by its five nearest frames from other episodes. All twenty retrieved frames are outlined in green, meaning they show the same task as the query.
Four queries and their five nearest neighbours from other episodes. Green means the same task.
Five retrieval metrics for two representations. Raw 16 by 16 pixels: recall at 1 of 92, recall at 5 of 98, precision at 5 of 90, mean reciprocal rank 95, mean average precision 70. CLIP image embedding: 96, 100, 95, 98 and 77.
The same test scored five ways, for CLIP embeddings and for a trivial baseline: each frame shrunk to 16 × 16 grey pixels.

CLIP retrieves a frame of the right task first 96% of the time. The more instructive number is the baseline. Shrinking each frame to 256 grey pixels and comparing those directly scores 92%. These scenes differ so much in overall appearance that almost anything can tell the tasks apart, so a high score here says little about the encoder. Without the baseline the 96% would have looked like an achievement. The first note’s rule applies: know what the trivial method scores.

Scoring a ranking

MetricQuestion it answersUse it when
Recall at kIs at least one relevant item in the top k?One good hit is enough, as in looking up an answer
Precision at kWhat share of the top k is relevant?The user reads the whole list
Mean reciprocal rankHow high is the first relevant item? Scores 1, ½, ⅓ … for ranks 1, 2, 3Only the first hit matters and its position counts
Mean average precisionAre all the relevant items near the top?There are many relevant items and all should be found
nDCGAs above, with graded relevance and a discount for lower ranksSome results are better than others

The figure shows why the choice matters. Recall at 5 is 100% for CLIP while mean average precision is 77%. The first hit is nearly always right, and the full set of relevant frames is not all ranked at the top. Which number to report depends on what the retrieved items are for.

The metrics, written out

For one query, let relk\mathrm{rel}_k be 1 if the item at rank kk is relevant and 0 otherwise, and let RR be the number of relevant items in the collection.

P@k=1k∑i=1kreliAP=1R∑kP@k⋅relkRR=1rank of the first relevant item\mathrm{P@}k = \frac{1}{k} \sum_{i=1}^{k} \mathrm{rel}_i \qquad \mathrm{AP} = \frac{1}{R} \sum_{k} \mathrm{P@}k \cdot \mathrm{rel}_k \qquad \mathrm{RR} = \frac{1}{\text{rank of the first relevant item}}
DCG@k=∑i=1k2gi−1log⁡2(i+1)nDCG@k=DCG@kDCG@k of the ideal ordering\mathrm{DCG@}k = \sum_{i=1}^{k} \frac{2^{g_i} - 1}{\log_2 (i + 1)} \qquad\qquad \mathrm{nDCG@}k = \frac{\mathrm{DCG@}k}{\mathrm{DCG@}k \text{ of the ideal ordering}}

Mean average precision and mean reciprocal rank are the averages of AP and RR over all queries. In nDCG, gig_i is a graded relevance score, so a perfect match can count for more than a partial one, and the logarithm discounts items lower in the list.

Multimodal retrieval

If two kinds of data share an embedding space, a query of one kind can retrieve items of the other. CLIP’s text encoder and image encoder were trained for this, so a sentence can search the same collection of frames.

Four text queries, each with the five best-matching robot frames from different episodes. A moka pot on a stove: all five show the moka pot scene. A microwave oven: one shows the microwave and four show a white cabinet. A wicker basket: all five show the basket scene. A book: two show the book and three do not.
Text queries against the same frames, top five from distinct episodes. No frame was ever labelled with these words.

The results are a fair picture of the technique. “A moka pot on a stove” and “a wicker basket” are found five times out of five. “A microwave oven” returns the microwave once and a white cabinet four times, which is a reasonable confusion for a boxy white appliance in a simulated scene. “A book” finds the book twice.

KindQueryReturnsExample
Text to imageA descriptionImages or videoFind every episode that contains a drawer
Image to imageA pictureSimilar picturesFind past scenes like the one in front of the robot
Image to textA pictureCaptions or documentsFind the manual page for this part
ComposedA picture and a modification in wordsImagesLike this scene, with the door open
Cross-sensorA reading from one sensorData from anotherFind the camera frames that match this touch pattern

Searching large collections

Left: time per query for exact search against collection size, rising from 3 milliseconds at 10,000 items to 86 at one million. Right: share of the true top 10 found against the share of the collection examined, reaching 97 percent after examining 8 percent and 99 percent after 11 percent.
Measured for this note. Left: comparing a query with every stored 512-number vector, on a desktop processor. Right: the robot-frame collection split into 32 clusters, searching only the clusters nearest the query.

Exact search compares the query with everything, so its cost grows in step with the collection: 9 ms at 100,000 items and 86 ms at a million here. Approximate nearest-neighbour search gives up a little accuracy to avoid that. In the right-hand panel, examining 8% of the collection found 97% of the true top ten.

  • Clustering (inverted file). Group the vectors into clusters ahead of time and search only the few clusters nearest the query. This is the method in the figure.
  • Graphs (HNSW). Link each vector to its neighbours and walk the graph toward the query. Very fast and accurate, at the cost of memory for the links.
  • Compression (product quantisation). Store each vector as a short code so that far more fit in memory, with some loss of precision.

Below about 100,000 items exact search is usually fast enough and has nothing to tune. Reach for an index when it stops being so.

Compressing the vectors

A million 512-number embeddings stored as 32-bit floats take two gigabytes. Memory, not arithmetic, is what limits large indexes, so vectors are stored in compressed form.

Share of the true ten nearest neighbours still found against bytes stored per item. 32-bit floats at 2,048 bytes are the reference. 8-bit integers at 512 bytes find 91 percent. One bit per number at 64 bytes finds 69 percent. Product quantisation finds 62 percent at 64 bytes and 49 percent at 4 bytes.
Measured on the robot-frame collection. Queries stay exact and only the stored vectors are compressed.
  • Scalar quantisation. Store each number in 8 bits instead of 32. A quarter of the memory for 91% of the true top ten here, with no training.
  • Binary codes. Keep only the sign of each number. A thirty-second of the memory and 69% of the top ten. Usually used to find candidates that are then re-scored.
  • Product quantisation. Split each vector into mm sub-vectors and replace each with the index of its nearest entry in a codebook of 256, so a vector becomes mm bytes. Distances are then approximated by table lookups: ∥q−x∥2≈∑j=1m∥qj−cj(x)∥2\| q - x \|^2 \approx \sum_{j=1}^{m} \| q_j - c_j(x) \|^2.

This test is a hard one, because the ten nearest neighbours of a frame are near-identical frames from similar episodes and small errors reorder them. On coarser questions, compressed vectors lose much less. The standard remedy is the same two-stage pattern as before: search the compressed vectors for a generous short list, then re-score that list with the exact ones.

Beyond one vector

  • Re-ranking. Retrieve a generous short list quickly, then score each candidate with a slower model that reads the query and the candidate together. It fixes many of the mistakes of single-vector matching at a cost that applies only to the short list.
  • Late interaction. Keep a vector for every token or patch instead of one per item, and match them in detail at query time. It is more accurate on long, specific queries and stores many times more data.
  • Hybrid search. Combine embedding search with keyword search. Embeddings find paraphrases and keywords find exact names and part numbers, and each covers the other’s blind spot.

Retrieval in robotics

  • Finding training data. Given a few demonstrations of a new task, retrieve similar episodes from a large unlabelled collection and train on both.
  • Checking coverage. Retrieve the nearest training episodes to a failure. If nothing is close, the policy was never shown that situation, as the failure triage note describes.
  • De-duplication and curation. Near-identical episodes sit close together in embedding space and can be found and removed.
  • Memory. Store what the robot has seen with where and when, and retrieve it to answer “where did I last see the keys?”.
  • Giving a language model facts. Retrieve relevant documents and place them in the prompt, so answers rest on a source that can be checked.
  • Recognising items. Match a camera view against a catalogue of known products or parts. My CaseID and maritime retrieval projects are both of this kind.

Common mistakes

  • Reporting a score with no baseline. On an easy collection a trivial method scores highly too.
  • Letting the query retrieve itself. Exclude the query, and near-copies such as frames of the same episode, from the results.
  • Choosing one metric by habit. Recall at 1 and mean average precision can tell different stories about the same system.
  • Building an index too early. Exact search is simpler and exact. Measure before replacing it.

Terms

Retrieval
Finding the items in a collection that best match a query.
Index
A stored structure that makes nearest-vector search fast.
Recall at k
The share of queries with at least one relevant item in the top k.
Mean average precision
A score that rewards ranking all relevant items near the top.
Approximate nearest neighbour
Search that examines part of a collection and accepts a small chance of missing a true neighbour.
Re-ranking
Re-ordering a retrieved short list with a slower, more accurate model.
Product quantisation
Compressing a vector by replacing each of its sub-vectors with a codebook index.

Further reading