---
title: "Architecture"
url: "https://nsta1.github.io/Orleans.Lattice/docs/lattice.vector/architecture.html"
source: "https://github.com/NSTA1/Orleans.Lattice/blob/release/9.9/docs/lattice.vector/architecture.md"
package: "Orleans.Lattice.Vector"
status: "unreleased"
documents: "Orleans.Lattice 9.9.0 (release line 9.9)"
built: "2026-10-04"
all-pages: "https://nsta1.github.io/Orleans.Lattice/llms.txt"
bundle: "https://nsta1.github.io/Orleans.Lattice/docs/lattice.vector/llms-full.txt"
---
# Architecture

Part of the [Vector documentation](README.md).

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.