pub struct Tuning {
pub posting: usize,
pub probe: usize,
pub rerank: usize,
pub sweep: usize,
pub widen: usize,
pub patience: usize,
pub spill: usize,
pub slack: f32,
}Expand description
The knobs, all of which have a defensible default and none of which anybody should have to touch.
Fields§
§posting: usizeHow many members a partition wants. It splits past twice this and merges under a quarter of it.
This is what sets how many partitions a collection ends up with, and so it trades the cost of ranking centroids against the cost of scanning a posting. A few hundred is where those two are near enough even.
probe: usizeHow many partitions a search scans.
rerank: usizeHow many candidates are reranked per answer asked for.
Four is the number the recall table was measured at: one bit codes put the true ten inside the best forty better than 98 times in a hundred.
sweep: usizeHow many neighbouring partitions a split sweeps for members that should move.
This is the cost of never drifting. Zero would make a split free and would make recall fall off over a long write stream, which is the thing this index exists to not do.
widen: usizeHow much further than probe a filtered search will go looking when the
filter is selective enough that the nearest partitions do not hold k
members that pass, as a multiple of probe.
This is the only knob here with a genuinely hard trade behind it. Too small and a filter matching one document in a thousand returns nothing while the answer sat two partitions further out. Too large and the same filter reads the whole collection to prove there is nothing there.
patience: usizeHow many partitions in a row may add nothing to the answer before the search stops reading, once it has enough candidates to answer with.
Tuning::probe is a budget every query spends whether it needs to or
not, and queries do not need the same amount. A query sitting deep inside
one partition has found everything it is going to find after two or three
of them, and a query on a boundary is still turning up better answers
forty partitions in. This is what lets one search cost what it needs
rather than what the slowest query needs, and it is the whole of the
difference between a mean probe depth and a fixed one.
It keys off the answer rather than off the geometry, which is deliberate.
The obvious rule is to stop once the next centroid is more than some
fraction further away than the nearest one, and that rule is useless
here: the measurement is on the private spill_into, which is where the
same rule was tried and dropped on the write path, and the short version
is that distances concentrate, every centroid a query can see is
within a few percent of every other, and there is no setting of the
fraction between pruning nothing and pruning everything.
A partition counts as adding nothing when not one of its members was good
enough to displace an answer already held. The count resets the moment one
is, so a run of empty partitions followed by a good one buys the search
its patience back. Zero switches this off and every search reads probe
partitions.
It cannot change how many candidates come back, only which ones, because it is only allowed to fire once there are already enough. A filtered search that is widening because it does not have enough is never cut off by it.
§Where the default comes from
Eight, which is the same as the default probe, and that is not a
coincidence: a search that only reads eight partitions cannot have eight
quiet ones in a row before it runs out, so the default settings are the
settings this does nothing under. It starts to matter exactly when
somebody raises probe, which is when it should.
On SIFT1M at probe 128 and rerank 16, where the fixed sweep recalls
0.9757 reading all 128, eight reads 96.9 of them for 0.9750, four reads
65.6 for 0.9704, and three reads 53.3 for 0.9641, against a fixed probe
of 64 which reads all 64 for 0.9665. So a quarter of the reads go away for
seven ten thousandths of recall, and the settings in between fill in a
ladder that probe can only climb by doubling.
spill: usizeHow many partitions one vector may be written into, at most.
One is no replication and is what the index did before this existed. It
is not the default, and src/miss.rs is why.
A vector belongs to the partition whose centroid it is nearest, and on some data that is a much weaker statement than it sounds. Measured on a million MS-MARCO passage embeddings, only 0.8952 of the true nearest neighbours of a query sat in one of the 128 partitions the search reads, and the recall the search actually returned was 0.8942, so the whole of the miss was neighbours nobody looked at rather than anything the estimator did. A vector near the boundary between two partitions is one query away from being in the wrong one, and no amount of scanning fixes that because the scan never gets there.
So a vector near a boundary goes in both, which is SPANN’s answer.
Raising this raises recall and costs memory and scan time in proportion
to how many vectors actually qualify, which is what Tuning::slack
controls.
slack: f32How much further than the nearest centroid a vector will still be copied into, as a fraction.
A vector goes into every one of its Tuning::spill nearest partitions
whose centroid is within 1 + slack of the nearest one, so zero is no
replication whatever spill says and a large value replicates
everything into everything. It is a distance ratio rather than a count
because the thing being asked is whether a vector is genuinely near a
boundary, and a vector sitting squarely inside its partition should cost
one copy however large spill is.