Expand description
The partition index, and the in place update protocol that means it never
has to be rebuilt (10 sections 2, 4 and 5).
A vector index is two decisions and the quantiser was the easy one. This is the other: what holds the codes, and what happens to it when the collection changes.
The answer is not a graph. Redis shipped HNSW vector sets in 8.0 in May 2025 and they were still beta three minor releases later, which is the vendor’s own evidence about how that goes. The reason is the update path: a graph index tombstones a delete, degrades as the tombstones pile up, and only gets better again when somebody rebuilds it, which on a collection anyone cares about is an outage with a nicer name.
So this is partitions. Every vector belongs to the partition whose centroid it is nearest, the centroids are resident, and a partition’s members are a flat run of codes that the scan walks end to end. An insert is an append. A delete takes a member out and moves the last one into the hole. Neither one touches anything else.
§Search
Rank the centroids, take the nearest probe of them, scan those partitions
with the estimator, keep the best rerank candidates, and then look up the
full precision vectors for exactly those and measure them properly. Rerank
costs nothing structurally here, because the vector is already in the record
log at an address the id resolves to. Every other system that quantises has
to keep the raw vectors somewhere on purpose.
The scan is the shape hardware likes, a linear walk over contiguous bytes, and that is why an index of this family beats a graph on a modern core even though it looks at more candidates.
§It never rebuilds
This is SPFresh’s LIRE, and it is four bounded operations rather than a background rebuild.
A posting that grows past twice its target splits, by two means over its own members. A posting that falls under a quarter of its target merges, by handing its members to whichever centroid is nearest now. Both are bounded work on one partition.
The third is the one that matters and it is what LIRE actually contributes. After a split, the members of the partitions around the one that split may now be nearer one of the two new centroids than the one they are filed under. Nobody told them, and a plain partitioned index just lets that drift, which is why a plain partitioned index measures beautifully on a freshly built corpus and badly after a week of writes. So a split is followed by a sweep of the neighbouring partitions, and anything whose nearest centroid has changed is moved. The test for this writes a stream and checks recall at the end of it rather than on a fresh build, because a fresh build is exactly the measurement that hides the problem.
§Everything here is in rotated space
The rotation is linear, so rotate(v - c) is rotate(v) - rotate(c), and
distances and angles come through it unchanged. That means a centroid can be
stored already rotated and a query can be rotated once, and then meeting a
partition is a subtraction rather than another rotation. The rotation is the
expensive half of preparing a query, so on a search that probes tens of
partitions this is most of what preparation costs.
§What it costs to build
examples/ingest.rs measures the rate at every doubling and splits it
between the insert and the maintenance, because a rate that falls as the
collection grows and a rate that is just low need different work and a single
number cannot tell them apart. On 128 dimensional vectors on one core of a
13th Gen Intel Core i9-13900K with nothing else running:
at partitions a second insert maintain touched
12500 36 132060 20.7% 79.3% 5.3
50000 132 94166 31.0% 69.0% 6.9
200000 595 67764 49.1% 50.9% 5.5
800000 2141 64107 52.8% 47.2% 4.4
1600000 4337 59040 53.7% 46.3% 4.4touched is how many vectors maintenance moved or looked at per vector
inserted. It is flat, and that is the number which says the update protocol
is doing bounded work rather than quietly turning into a rebuild.
Five fixes got it there and they were five different problems.
Maintenance was 80 percent of the time and most of it was sweep measuring
every member it looked at against every centroid in the collection, which is
not what LIRE says and is several full scans per vector inserted. The insert
was the other half and it was a scan over every centroid by definition, which
is why the coarse layer in src/coarse.rs is there, and that file is where
the reasoning about it lives. Before either fix, the rate halved on every
doubling and was 13563 a second by 800 thousand.
The third was the squared distance itself, which by then was half of an
entire ingest across the two copies of it that existed, and it was slow for
a reason that had nothing to do with the index: a bounds check the compiler
could not remove was stopping the loop vectorising. There is now one copy in
src/dist.rs and that file is where the reasoning lives. It doubled the
rate on its own, 21183 a second to 40318 over the whole 1.6 million on the
same machine, and it cut the insert half by three times, 45.9 seconds to
15.3, which is why insert and maintenance have swapped places in that table.
The fourth was Partitions::job, which used to ask its two questions by
walking every partition twice, once per vector inserted. That is the same
quadratic the coarse layer exists to remove, hiding one level up, and by 1.6
million vectors it was around a fifth of an ingest spent deciding there was
nothing to do. It is the two candidate lists now.
The fifth was the rotation, in src/rotate.rs, which unpacked a sign bit
with a shift and a mask inside the loop and then branched on a random bit
per pair. Turning a pair is the same as flipping the sign of its second
coordinate, so the branch folds into the sign table at build time. Those two
together took the whole 1.6 million from 40318 a second to 64647, and the
maintenance half from 24.4 seconds to 11.6.
So G13’s fifty thousand a second per core is met on the machine it is called on, and it is met at every size in the table rather than only at the small end. The two halves are close to even now, 53.7 percent insert against 46.3 percent maintenance at the far end, so neither one is the obvious next thing to go and look at.
§What is not here yet
A checkpoint that writes the image out. crate::image is the layout and
the two halves of the round trip, and the seam it comes back through is a
pair of crate private calls further down this file, so an index survives a
restart without requantising anything. What is still missing is the shard
side: deciding when to write one, and pointing a checkpoint entry at it.
MS-MARCO-v2. SIFT1M on a 13900K now gets recall 0.9597 at probe 64 rerank
16 with p50 at 638 us and p99 at 776 us, so both halves of G12 are met on
that dataset, and the same run before the src/dist.rs change was 808 us
and 996 us for the same recall, which was inside the millisecond by so
little that nobody should have called it. The other dataset the gate names
has not been run.
examples/search.rs is the breakdown of where the remaining time goes and
the answer is that two thirds of it is the estimator meeting one code at a
time.
The commands that put all of this on the wire are the rest of M6.
Structs§
- Any
- The filter that lets everything through, which is what an unfiltered search runs.
- Hit
- An answer: a document id and how far it really is, not how far it was estimated to be.
- Partitions
- A collection of vectors, quantised, partitioned, and updated in place.
- Signature
- A tag built by setting one bit per attribute value, so that a conjunction of required values is a subset test.
- Tuning
- The knobs, all of which have a defensible default and none of which anybody should have to touch.
- Work
- What one search actually read.