A graph index for sparse vectors. We follow the code, first the build and then the search.
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.
Only shared terms count. Terms 12 and 30 add 0. This is why an inverted index works: it lists the documents of each term.
A graph index links each document to similar ones. A query walks the links toward better scores.
The build runs once. The search runs for each query. Each box shows where the idea comes from.
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.
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.
hash(id) % leader_count. The pick looks random but is the same in every run.PiPNN scores all pairs of a leaf with a dense matrix product. GRIP uses an inverted index of the leaf, so zeros cost nothing.
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.
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.
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.
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.
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.
Each document owns a reservoir. It is a list of at most 64 edges, with at most one edge for each label.
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.
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.
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.
For each term, we keep the 64 documents with the highest weight for that term. A query starts its walk from these documents.
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.
The walk needs a fast score. Each document gets a routing sketch: its 80 largest terms, with each weight stored in one byte.
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.
The query is rounded with the same scale. Then the seed lists of its most important terms give the start nodes.
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.
Each step expands the best candidate and scores its unseen neighbors. A neighbor that enters the results becomes a candidate too.
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.
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.
top_k × rescore_factor), not all 100.