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 an
M-series Mac:
at partitions a second insert maintain touched
12500 36 115952 20.4% 79.6% 5.3
50000 132 72013 39.4% 60.6% 6.9
200000 595 46917 58.7% 41.3% 5.5
800000 2141 42459 60.9% 39.1% 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.
Both halves of that took a fix to get there and they were different fixes.
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.
§What is not here yet
A .yo file. None of this is written down yet, and the format freezes at the
end of M6, so that is the next thing.
A search that fits in a millisecond. SIFT1M on a 13900K gets recall 0.9598 at
probe 64 rerank 16, which clears the gate, with p50 at 1.1 ms and p99 at 1.5
ms, which does not. examples/search.rs is the breakdown of where that 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.