grip-rs walkthrough

GRIP in Rust

A graph index for sparse vectors. We follow the code, first the build and then the search.

PiPNNan idea from the PiPNN paper
GRIPan idea from the GRIP paper
grip-rsa choice made in this code
Arrow keys or click to move
The problem

Find the best documents, fast

A sparse vector has about 30,000 terms, and only 100 to 200 are not zero. A query wants the 10 documents with the highest score.

// the score is a sparse dot product
score(q, d) = sum over terms t of q[t] × d[t]

q = {7: 0.5, 12: 1.0}
d = {7: 0.4, 30: 0.9}
score = 0.5 × 0.4 = 0.2

Only shared terms count. Terms 12 and 30 add 0. This is why an inverted index works: it lists the documents of each term.

startbest

A graph index links each document to similar ones. A query walks the links toward better scores.

The big picture

The whole pipeline

The build runs once. The search runs for each query. Each box shows where the idea comes from.

Build, once
Partitionsplit into leavesPiPNN GRIP
→
Leaf edgesscores inside a leafGRIP
→
HashPruneedges in many directionsPiPNN
→
RobustPrunedrop covered edgesPiPNN GRIP
→
Graph64 neighbors for each document
Seed listswhere to start a queryGRIP
Routing sketchescheap scores for the walkGRIP grip-rs
Search, for each query
Entry pointsstart from query termsGRIP
→
Walkbeam search on sketchesGRIP
→
Fetch and rescoreexact scores, full vectorsgrip-rs
→
Top kthe final answer
Build · 1 of 4 PiPNNGRIP

Split the documents into leaves

A leaf is a group of at most 1024 documents. We pick random leaders and send each document to the leaders it scores highest with.

partition.rs

Leaders

A random sample of about 0.1% of the documents. We score a document against a leader with the sparse dot product.

Inverted index

The index covers the leaders, not the documents. A document looks up only the leaders that share a term with it.

Build · 1 of 4 PiPNNGRIP

Depth, fanout, and the fallback

Depth
The whole collection is depth 0. A group that is still too big is split again at depth + 1. We stop at 1024 documents or after depth 5.
Fanout
The number of leaders that a document joins: 10 at depth 0, 3 at depth 1, then 1. So a document lands in at most 10 × 3 × 1 = 30 leaves.
Fallback
If a document shares no term with any leader, all its scores are 0. We pick a leader from hash(id) % leader_count. The pick looks random but is the same in every run.
Merging
After a split, groups with fewer than 100 documents are merged at random until they reach 100. A leaf needs enough documents to give good neighbors.
Build · 2 of 4 GRIP

Find neighbors inside each leaf

PiPNN scores all pairs of a leaf with a dense matrix product. GRIP uses an inverted index of the leaf, so zeros cost nothing.

leaf.rs

Example: term 7

posting list:
A 0.5   B 0.4   C 0.2

      A     B     C
A     .    0.20  0.10
B     .     .    0.08

The work is about half the sum, over all terms, of (posting list length)². Documents with no shared term are never compared.

Build · 3 of 4 PiPNN

Why a small sketch is enough

HashPrune needs the direction from a document p to a candidate c. It gets the direction from 12-number sketches and never loads the full vectors.

r1r2 00 10 11 01 A B p

The idea

Take a random vector r. The sign of r · (c - p) tells on which side of a line through p the candidate c lies.

The shortcut

r · (c - p) = r · c - r · p. So we compute r · c once for each document. These numbers are the sketch.

The label

12 random vectors give 12 signs. That is a 12-bit label with 212 = 4096 possible cones. In the picture, the first bit is the side of r1 and the second is the side of r2. A and B share a cone, so only the better one stays.

Build · 3 of 4 PiPNN

From sketch to label

The matrix w holds one random normal number for each (term, bit). The sketch of a document is 12 sparse dot products, one for each bit.

hashprune.rs

Example with 3 bits

sketch(p) = [1, 2, 3]
sketch(c) = [2, 1, 5]
difference = [+1, -1, +2]
bits       = [ 1,  0,  1]
label      = 101

The sketch is 12 floats for each document, so 48 bytes.

Build · 3 of 4 PiPNN

One edge for each direction

Each document owns a reservoir. It is a list of at most 64 edges, with at most one edge for each label.

hashprune.rs · insert_in_reservoir

Order does not matter

The PiPNN paper proves that the final list is the same for any arrival order. So leaves run in parallel, and each reservoir sits behind a Mutex.

One slot

8 bytes: id (4), label (2), score as bf16 (2). The list stays sorted by label, so get is a binary search.

Build · 4 of 4 PiPNNGRIP

Drop the edges that are already covered

The reservoir can still hold neighbors that are close to each other. RobustPrune takes the best edge first and drops every candidate that this edge covers.

robustprune.rs

The rule

Drop c when q · c > α × (p · c). The score p · c is the stored one. Then q is closer to c than p is, so p reaches c through q.

Example

p has a (0.9) and b (0.6), and a · b = 0.8. Since 0.8 > 0.6, a covers b. With α = 1.5 the limit is 0.9, and b stays.

Build · also built GRIP

Seed lists and term_max

For each term, we keep the 64 documents with the highest weight for that term. A query starts its walk from these documents.

seeding.rs · build_seed_list

Example

The seed list of the term "volcano" holds the 64 documents where "volcano" weighs most.

term_max

The highest weight that a term has in the whole collection. It bounds how much that term can add to any score.

Build · also built GRIPgrip-rs

Routing sketches

The walk needs a fast score. Each document gets a routing sketch: its 80 largest terms, with each weight stored in one byte.

search.rs · make_routing_sketch

Not the hash sketch

The hash sketch has 12 floats and is used only in the build. The routing sketch has 80 terms and is used only in the search.

Why u32

The largest score is 80 × 255 × 255 = 5,202,000. A u16 would overflow.

Search · 1 of 3 GRIP

Pick the start nodes

The query is rounded with the same scale. Then the seed lists of its most important terms give the start nodes.

search.rs · search

Importance of a term

The weight of t in the query times term_max[t] is the most that t can add to a score. We keep the best 2 terms, so up to 128 start nodes.

Why a dense array

Two sparse lists need a merge with comparisons. With dense, each term of a node is one read.

Search · 2 of 3 GRIP

Walk the graph with sketch scores

Each step expands the best candidate and scores its unseen neighbors. A neighbor that enters the results becomes a candidate too.

search.rs · search

Two heaps

candidates pops the best score first. results keeps the best ef nodes with the weakest on top, so a new node is compared with one value.

The counter

Query 1 marks nodes with 1. Query 2 uses 2, so all old marks are stale and we never clear the array.

Search · 3 of 3 grip-rs

Fetch the full vectors and rescore

Sketch scores drop the small terms and round the weights, so the order of the best candidates can change. The exact score from the full vector fixes it.

search.rs and disk.rs

count (u64), scale (f32)
offset table: one u64 for each documentdocument 3: bytes 12 + 8 × 3 = 36
document 0len (u16), term ids (u32 × len), values (f32 × len)
document 1 ...
Sketches stay in RAM. Full vectors stay on disk, memory mapped.
We fetch 50 documents (top_k × rescore_factor), not all 100.