Corey James- 100Krows, the default cap on the training sample
- 4,096cells at most; a configuration outside the bounds is refused
- 32vectors at least in every cell
An approximate index trades exactness for speed, and most implementations trade reproducibility away with it: random seeds from the clock, training samples that depend on traversal order, floating-point reductions whose result depends on which thread finished first. When such an index returns different neighbours after a rebuild, nobody can say whether the data changed, the build changed, or something broke.
I wanted an index whose receipt is enough to rebuild it byte for byte.
Three hashes
Every build produces three hashes. The configuration hash is over a canonical binary encoding of the parameters, so two builds with the same settings have the same hash regardless of how the settings were written. The training-set hash is over the length-prefixed, sorted list of shard and row identifiers that were sampled, so it does not depend on the order in which the shards were walked. The artifact hash is over the body bytes of the index file, excluding the header, which carries a wall-clock timestamp that would otherwise make every build unique. A build is checked by recomputing the artifact hash from the written bytes before it is catalogued.
A sample that does not depend on order
The training sample is a reservoir sample over the shard set, seeded by a hash of the build seed, the sorted shard set, the sample cap and each shard's row count. The shard set is canonicalised first, sorted and de-duplicated, and the selections are sorted before hashing, so the same data in a different order yields the same sample and the same hash.
Fixed arithmetic
The seeding of k-means++ splits its work: the GPU computes each row's squared distance to the centroids chosen so far, and the host draws the next seed with a seeded generator, so the random step happens outside any floating-point reduction. Lloyd's algorithm then runs a fixed count of iterations with no early exit, with its reduction order fixed by the launch geometry of one block per centroid. Everything is single precision; half precision, bfloat16, FP8 and tensor-core paths are banned by a check in the build.
No early exit; one block per centroid fixes the reduction order.
Single precision only; half, bfloat16, FP8 and tensor-core paths fail a check in the build.
The test that proves it
An integration test builds the index twice and asserts a byte-identical artifact hash, then builds it again from the same data in a different order and asserts the same. A second test fixes a recall floor: the index must find a fixed share of what exact search finds.
One artifact hash, byte for byte.
On clustered fixtures; recall must also rise as more cells are probed.
What this demonstrates
Treating reproducibility as a property to be engineered into an approximate algorithm, with the receipt, the sample, the arithmetic and the test each closed against a source of variation, so that a changed result is always a question with an answer.
The determinism contract was my design; AI coding agents, a mix of frontier and open-source models, implemented and tested it under my governance system.