Advanced

Storing vectors so search is fast

Scoring every chunk on every question is fine to ten thousand chunks and slow at a million. The fix is an index that trades a little accuracy for a large speed gain, and the trade is worth understanding because it is the reason a search sometimes misses.

What you will see

50000 and a time. That time is the baseline an index would be replacing, and it is the number to publish with the choice.

About 1 min of reading

Try It

Compare scan cost by size.

Time a scan

import time vecs = [[0.1] * 4 for _ in range(50000)] t = time.time() _ = sum(1 for v in vecs if v[0] > 0) print(len(vecs), round(time.time() - t, 3))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

50000 and a time. That time is the baseline an index would be replacing, and it is the number to publish with the choice.

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

An index trades accuracy for speed.

1 Normalise the vectors

↓

2 Cluster them into an index

↓

3 Search the nearby clusters

↓

4 Measure the recall the setting gives

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

import time sets nothing on screen

vecs = [[0.1] * 4 for _ in range(50000)] sets nothing on screen

t = time.time() sets nothing on screen

_ = sum(1 for v in vecs if v[0] > 0) sets nothing on screen

print(len(vecs), round(time.time() - t, 3)) 50000 and a time. That time is the baseline an index would be replacing, and it is the number to publish with the choice.

Why this works

Measure before you index

A flat scan on your real corpus is the baseline. If it answers in 40 milliseconds, an approximate index is a solution to a problem you do not have, and it adds a failure mode.

Keep the index and the text in step

An index built yesterday and documents changed today gives answers from deleted text. Storing the version with the chunk, or rebuilding on change, is what keeps the two honest.

Examples

Exact scan versus index

A flat scan compares against every vector and is exact. An approximate index clusters the vectors and searches the nearby clusters, which is much faster and can miss a vector that sits near a cluster edge.

The miss is the setting

Approximate indexes have a knob for how many clusters to search. Raising it costs time and reduces misses. The right value is found by measuring recall on your own questions, not by a default.

Normalise once at build time

If the vectors are scaled to unit length when stored, the comparison is a plain dot product. Doing that at build time removes a division per comparison, which is the difference between a slow scan and a usable one.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Checking a retrieval system

Previous Lesson

Checking a retrieval system

Next Lesson

Filtering by metadata

Filtering by metadata →