Architecture

How Orleans.Lattice.Vector is built, why the index structure was chosen, and how the durable form is laid out on a Lattice tree.

The index structure: inverted file (IVF)

The core is an inverted file index. A seeded k-means pass partitions the corpus into roughly sqrt(n) cells, each with a centroid. A query ranks the centroids, then scores only the vectors in the cells it probes.

A graph-based structure (HNSW and relatives) was the main alternative. IVF was chosen against five criteria:

Criterion	IVF as built	Graph alternative
Build cost	Bounded k-means over a capped sample, so the iterative refinement stops scaling with the corpus past the cap; the final pass that assigns every vector to its nearest centroid and re-lays the cells still grows with the corpus and the partition count. About 10.7 s for 1,000,000 vectors at dimension 384.	Incremental graph construction, materially heavier and not capped.
Query cost	Sub-linear: `C` centroid comparisons plus `probes * (n / C)`. Measured speedup over exhaustive grows from about 3x at 10,000 to about 14x at 1,000,000.	Also sub-linear, typically with a better constant factor.
Memory per vector	`dimensions * 4 + 12` bytes. No per-vector object header and no adjacency structure.	Adds a whole adjacency graph per vector.
Incremental insert	Assign to the nearest centroid and append. No retrain needed for correctness.	Supported, but each insert mutates shared graph structure.
Delete	First class and constant time in the corpus size: the cell's hole is backfilled with its last member, which copies one vector's worth of floats regardless of how many vectors the index holds. Never a tombstone, so a deleted vector cannot resurface.	The known weak point, usually tombstones plus periodic rebuild.

The criterion that actually decided it is durability. An IVF cell is a natural bounded chunk, and a query provably touches only the cells it probes, so a partial load is not merely possible - it is the normal mode. A graph traversal hops arbitrarily across the structure, so there is no bounded subset provably sufficient to answer a query, and the durable layer would be forced to hold the entire graph resident. Since the whole point of the package is to make a restart cheap, the structure was chosen for the seam rather than for the best possible constant factor.

Two properties that are load-bearing

These are not tuning choices. Changing either silently destroys the package's reason to exist.

Cells own their vectors contiguously

The first implementation used posting lists of slot identifiers into one global vector block - the textbook layout. Measured during development it reached only about 2.6x speedup at 1,000,000 vectors and was slower than exhaustive at 50,000, because the probe scan is cache-hostile: every scored vector is an indirection into a different part of a large array. (That figure describes a superseded implementation, so it is not reproducible from the committed harness; the qualitative point is what matters.)

Rewriting so that each cell owns its members' vectors contiguously in its own block took the same algorithm to about 14x. Do not reintroduce an indirection here.

The probe count must not be a fixed fraction of the partitions

Total query cost is C + probes * (n / C). With C = sqrt(n), a probes term proportional to C puts n straight back into the second term, and the index becomes linear in the corpus again while still looking like an approximate index.

The default is therefore clamp(2 * ceil(sqrt(partitionCount)), 8, partitionCount), which makes the fraction of the corpus scanned fall as the corpus grows: about 25% at 5,000 vectors, about 6% at 1,000,000. The recall harness reports that scanned fraction at each corpus size, so the property is visible in the committed evidence. A future "probe more for better recall" change must not turn this back into a fraction.

Determinism

The same corpus and configuration always produce the same result set, so downstream suites are not flaky. Three mechanisms deliver that:

Results are totally ordered by descending score, then ascending key.
Training collects the live set sorted by key before sampling, so sampling and centroid seeding depend on contents rather than on insertion history.
The k-means mean recomputation is deliberately serial in ascending order (only the pure per-vector nearest-centroid search is parallelised), so floating-point addition order is fixed.

Randomness is explicit: VectorIndexOptions.Seed is public, is surfaced again on the index and in every snapshot header, and the generator is a hand-rolled seeded xorshift128+ rather than System.Random, whose algorithm is an implementation detail that may change between runtimes. An index must reproduce bit-for-bit from its seed on any machine and any release.

The durable layer

DurableVectorIndex persists the core on a Lattice tree. Everything lives under a caller-chosen key prefix.

Two counters

A generation covers a whole partitioning. Training - the build's training step and RetrainAsync alike - changes every cell's membership, so it writes a fresh generation, flips the manifest to it, and only then deletes the generation it superseded, rather than editing the live one. Each half of that commit records its progress: a retry after a failed write writes only what the failed attempt did not commit (or what has changed since), a retry after a failed delete only deletes, and neither starts yet another generation. A writer that reopens an index whose build committed its new generation but had not finished the delete reports Persisting and finishes it on its next build step. A rebuild is different: it deletes every generation first and starts again from the store of record.
An epoch covers one flush inside a generation. A dirty partition's changed chunks are written under a new epoch and committed by rewriting that partition's state record, which records the epoch each of its chunks lives under - so one cell's chunks can span several epochs. An interrupted flush leaves an uncommitted epoch the loader ignores. Nothing sweeps such an epoch directly: its chunks are reclaimed only if a later flush commits under the same epoch number and the partition later moves past it, or when its generation is superseded or discarded. The chunk keys a committed flush superseded are reclaimed after its state swap.

Both are zero-padded so ordinal key order is numeric order, and neither is reused while the index's durable state survives: only a discard - the recovery path, or RebuildAsync - resets them, and it first deletes the manifest, the build checkpoint, every generation, the retirement journal and the identifier mapping under the prefix. The identifier watermark alone is kept (rewritten, never rewound), so a rebuild never hands out a key a previous build already used.

Write order is the durability mechanism

No multi-key atomicity is required from Lattice. Records are written in a fixed order - content records first, then the per-partition commit record, then the manifest last - and a loader reads exactly the chunk count a partition's commit record claims, addressed by key rather than discovered by scanning. A chunk written but not committed is therefore simply never read.

Every record - manifest, chunk, partition state, build state, identifier mapping - is wrapped in one 24-byte envelope carrying a marker, the layout version, the payload length, and a checksum. Truncation, a flipped bit, a wrong key and a future version all collapse to the same answer: the unwrap fails. There is exactly one place that decides whether a persisted byte sequence may be believed.

No record grows with the corpus: a chunk is written at the largest item count that fits a fixed 64 KiB byte ceiling, capped by MaxItemsPerChunk, and a test asserts every persisted record stays under the bound that implies.

Lazy partial load

Opening an index lazily walks its identifier mapping and reads each partition's commit record, but applies only the centroid chunks, which are small (partitionCount * dimensions floats), and no vector chunk. A query then selects the partitions it would probe and fetches only those vector chunks. The answer is identical to the fully resident index - asserted across a query sweep - because a query is scored against exactly the cells it selects, and because a chunk is a slice of one contiguous cell rather than a gather across the corpus.

At 250,000 vectors this is about 0.52 s to open and about 75 ms for the first query, after which roughly 12% of the corpus is resident and repeated queries over the same cells touch the store not at all. The box warms as it serves.

Incremental persistence

Each partition carries a version stamp that advances whenever a vector enters or leaves it, and the index carries an overall version that advances on every mutation. A flush persists only the partitions whose stamp moved. Rendering a chunk fails if the index has moved since the snapshot was planned, so a torn snapshot cannot be written.

Within a dirty partition the unit of persistence is one chunk: each rendered chunk is content-hashed and only the chunks whose bytes changed are rewritten, so re-embedding one vector rewrites a few chunks rather than its whole cell. A flush with nothing dirty costs a single write (the manifest); a flush after one update costs a handful. Each touched cell still costs its commit record, so a maintenance loop that batches before flushing pays for the distinct chunks and cells it touched rather than for the updates it applied.

Build checkpoints

A background build ingests into the single cell of an untrained index, and while that cell is only ever appended to, every chunk but the last is immutable once written. Each build step therefore ends at a checkpoint that writes only the complete chunks that arrived since the previous one (the checkpoint that finishes the ingest also writes the partial last chunk), so the whole ingest costs one pass over the corpus rather than one per checkpoint, and no complete committed chunk is rewritten; the durable cursor lags by less than a chunk, which the next step re-consumes.

The identifier mapping follows the same order. A build slice assigns keys as it ingests but buffers their mapping records, and writes them in one batch before the slice's checkpoint rather than one write per vector. Because that batch lands first, the mapping can run ahead of the committed cells but never behind them; a batch that fails part-applied leaves only mappings no committed cell refers to yet, and its retry rewrites the same identifiers to the same keys.

A replacement or a removal during the build - one the build streams itself, or an UpsertAsync that replaces a vector or a RemoveAsync that retires one in the meantime - costs the cell that property, because it backfills or re-appends positions a committed chunk already holds. The next checkpoint then falls back to an incremental flush of the current generation: every chunk's content hash is compared with the one stored at the same position, and only the chunks that differ are written, under a fresh epoch. A checkpoint that faults part-way is retried against what was last committed, so the retry writes only what still differs rather than an image of the whole cell. A plain append from outside the build does not cost the property.

Coherence with the store of record

The index is a derived projection, never authoritative. That asymmetry is what makes its recovery story simple: every inconsistency is settled by discarding index state and recomputing, and nothing in the durable layer ever writes to a store of record.

The rules it enforces:

No ghosts. A retired vector never appears again, including across a restart that interrupted the deletion. A durable tombstone is written before the in-memory removal and dropped only once that removal is durable, and the journal is replayed against every cell a lazy reader fetches later, not only at load.
Lag only in the missing direction. The index is never ahead of the source, and outstanding work is reported rather than hidden.
Verified load, no middle path. The manifest, every checksum, every partition's chunk set and the declared count must all agree, or the index is rebuilt and never partly served.
Absent means absent on every read path. A record the commit chain names but a read did not return is re-read by point read and by prefix scan before anything is deleted. If either returns it, the store merely could not answer consistently - as under a WAL replay-permit storm - so the load throws VectorIndexRecordUnavailableException, keeps the durable index and its banked progress, and is retried. Only a record every path agrees is missing, or one that was returned and cannot be decoded, triggers the rebuild.
A reader must not repair what it cannot maintain. A lazily loaded handle that finds unverifiable state refuses to serve it and leaves the store alone, rather than discarding an index a writer elsewhere may be building.

A source-side deletion the index was never told about is explicitly not covered by these rules; a bounded reconciliation sweep exists for that, and always settles in the source's favour.

Table of Contents