mnemo_engine/index.rs
1//! IVF + PQ approximate-nearest-neighbour index (Phase 2 of the build plan).
2//!
3//! Exact search is `O(n)`. This module makes retrieval sub-linear:
4//!
5//! 1. **IVF** (inverted file): vectors are grouped into roughly `√n`
6//! partitions by k-means. A query scans only the `n_probe` partitions
7//! whose centroids are nearest to it.
8//! 2. **PQ** (product quantization): each vector is cut into `m` contiguous
9//! subspaces; every subspace is quantized to one of up to 256 learned
10//! codewords, so a whole vector collapses to `m` bytes. Candidate
11//! distances are summed from precomputed per-subspace lookup tables — the
12//! scan never touches a full float vector.
13//! 3. **Rerank**: the `n_rerank` closest candidates by PQ distance are
14//! returned to the store, which loads their exact vectors for final,
15//! precise ranking.
16//!
17//! All distances *inside* the index are squared-L2. The index only has to
18//! produce a good candidate *set*; the store reranks with the caller's actual
19//! metric (cosine / dot / L2). For embedding vectors — which tend to have
20//! similar norms — L2-nearest and cosine-nearest largely agree, and a
21//! generous `n_rerank` absorbs the rest.
22
23use rand::rngs::StdRng;
24use rand::seq::SliceRandom;
25use rand::{Rng, SeedableRng};
26use serde::{Deserialize, Serialize};
27
28use crate::error::{MnemoError, Result};
29
30/// Slot marker for an empty [`U128Map`] slot (values are partition or row
31/// numbers, so `u32::MAX` is never a real value).
32const VACANT: u32 = u32::MAX;
33
34/// Home slot of a ULID (or any `u128` id) in a table of `cap` slots.
35/// ULIDs carry 80 random low bits, so folding the halves and a
36/// multiplicative mix is enough; the high bits of `hash * cap` then pick
37/// the slot, so `cap` needn't be a power of two (a power-of-two table at
38/// <= 3/4 load can sit at 3/8, doubling its size for nothing).
39pub(crate) fn slot_home(k: u128, cap: usize) -> usize {
40 let x = (k as u64) ^ ((k >> 64) as u64).rotate_left(29);
41 let h = x.wrapping_mul(0x9E37_79B9_7F4A_7C15);
42 ((h as u128 * cap as u128) >> 64) as usize
43}
44
45/// The slot after `i`, wrapping at `cap`.
46pub(crate) fn next_slot(i: usize, cap: usize) -> usize {
47 if i + 1 == cap {
48 0
49 } else {
50 i + 1
51 }
52}
53
54/// Forward distance from slot `from` to slot `to`, wrapping at `cap`.
55fn cyclic_dist(from: usize, to: usize, cap: usize) -> usize {
56 if to >= from {
57 to - from
58 } else {
59 to + cap - from
60 }
61}
62
63/// Slot count that holds `n` entries at <= 3/4 load.
64pub(crate) fn table_capacity_for(n: usize) -> usize {
65 (n * 4 / 3 + 1).max(16)
66}
67
68/// PERF-1 step 4: a compact `u128 → u32` map (linear probing,
69/// backward-shift deletion) for the ANN's id → partition assignment. It
70/// takes 20 bytes a slot at <= 3/4 load, about 27 bytes an entry, against
71/// about 43 for `HashMap<u128, usize>` (whose 32-byte, 16-aligned slots
72/// dominate).
73#[derive(Clone, Debug, Default)]
74pub(crate) struct U128Map {
75 keys: Vec<u128>,
76 vals: Vec<u32>,
77 len: usize,
78}
79
80impl U128Map {
81 pub(crate) fn with_capacity(n: usize) -> Self {
82 let mut m = Self::default();
83 m.resize(table_capacity_for(n));
84 m
85 }
86
87 fn resize(&mut self, cap: usize) {
88 let keys = std::mem::replace(&mut self.keys, vec![0; cap]);
89 let vals = std::mem::replace(&mut self.vals, vec![VACANT; cap]);
90 self.len = 0;
91 for (k, v) in keys.into_iter().zip(vals) {
92 if v != VACANT {
93 self.insert(k, v);
94 }
95 }
96 }
97
98 fn find(&self, k: u128) -> Option<usize> {
99 if self.vals.is_empty() {
100 return None;
101 }
102 let cap = self.vals.len();
103 let mut i = slot_home(k, cap);
104 loop {
105 if self.vals[i] == VACANT {
106 return None;
107 }
108 if self.keys[i] == k {
109 return Some(i);
110 }
111 i = next_slot(i, cap);
112 }
113 }
114
115 #[cfg(test)]
116 pub(crate) fn get(&self, k: u128) -> Option<u32> {
117 self.find(k).map(|i| self.vals[i])
118 }
119
120 pub(crate) fn contains_key(&self, k: u128) -> bool {
121 self.find(k).is_some()
122 }
123
124 pub(crate) fn insert(&mut self, k: u128, v: u32) {
125 debug_assert_ne!(v, VACANT);
126 if (self.len + 1) * 4 > self.vals.len() * 3 {
127 let cap = (self.vals.len() * 2).max(table_capacity_for(self.len + 1));
128 self.resize(cap);
129 }
130 let cap = self.vals.len();
131 let mut i = slot_home(k, cap);
132 loop {
133 if self.vals[i] == VACANT {
134 self.keys[i] = k;
135 self.vals[i] = v;
136 self.len += 1;
137 return;
138 }
139 if self.keys[i] == k {
140 self.vals[i] = v;
141 return;
142 }
143 i = next_slot(i, cap);
144 }
145 }
146
147 pub(crate) fn remove(&mut self, k: u128) -> Option<u32> {
148 let i = self.find(k)?;
149 let out = self.vals[i];
150 let cap = self.vals.len();
151 // Backward-shift: pull later entries of the probe run into the
152 // hole when the hole lies on their path from home.
153 let mut hole = i;
154 let mut j = i;
155 loop {
156 j = next_slot(j, cap);
157 if self.vals[j] == VACANT {
158 break;
159 }
160 let home = slot_home(self.keys[j], cap);
161 let from_home = cyclic_dist(home, j, cap);
162 let from_hole = cyclic_dist(hole, j, cap);
163 if from_home >= from_hole {
164 self.keys[hole] = self.keys[j];
165 self.vals[hole] = self.vals[j];
166 hole = j;
167 }
168 }
169 self.vals[hole] = VACANT;
170 self.len -= 1;
171 Some(out)
172 }
173
174 #[cfg(test)]
175 pub(crate) fn len(&self) -> usize {
176 self.len
177 }
178
179 /// Heap bytes held by the two slot arrays.
180 #[cfg(feature = "dev-hooks")]
181 pub(crate) fn heap_bytes(&self) -> usize {
182 self.keys.capacity() * std::mem::size_of::<u128>()
183 + self.vals.capacity() * std::mem::size_of::<u32>()
184 }
185}
186
187/// Estimated heap bytes of a `HashMap<K, V>` with the given capacity:
188/// one `(K, V)` slot plus one control byte per bucket, with buckets
189/// rounded up from capacity at the 7/8 load factor. An estimate for the
190/// P-0 device budget, not an exact allocator figure.
191#[cfg(feature = "dev-hooks")]
192pub(crate) fn hash_map_bytes<K, V>(capacity: usize) -> usize {
193 if capacity == 0 {
194 return 0;
195 }
196 let buckets = (capacity * 8 / 7).next_power_of_two();
197 buckets * (std::mem::size_of::<(K, V)>() + 1)
198}
199
200/// Default RNG seed — fixed so index builds are reproducible.
201const DEFAULT_SEED: u64 = 0x4d_4e_45_4d_4f_49_44_58; // "MNEMOIDX"
202/// Training-set cap: k-means trains on at most this many sampled vectors.
203const TRAIN_CAP: usize = 50_000;
204/// Codewords per PQ subspace.
205const PQ_CODEWORDS: usize = 256;
206
207/// Tuning knobs for building and querying an [`IvfPqIndex`].
208#[derive(Clone, Copy, Debug)]
209pub struct IndexConfig {
210 /// Number of IVF partitions. `0` means auto (`ceil(√n)`).
211 pub n_partitions: usize,
212 /// Number of PQ subspaces. `0` means auto (`dims / 4`). Previously
213 /// `dims / 8` before PR ANN-1 — see [`IndexConfig::default`] for
214 /// why the bump.
215 pub pq_subspaces: usize,
216 /// Partitions scanned per query (the IVF accuracy/speed dial).
217 /// `0` means auto (`ceil(partitions / 2)`). Previously a fixed `8`
218 /// before PR ANN-1.
219 pub n_probe: usize,
220 /// Candidates handed back for exact reranking (the PQ accuracy dial).
221 /// `0` means auto (`500`). Previously a fixed `64` before PR ANN-1.
222 pub n_rerank: usize,
223 /// Lloyd-iteration count for every k-means run.
224 pub kmeans_iters: usize,
225 /// RNG seed for reproducible builds.
226 pub seed: u64,
227}
228
229/// Auto-pick `n_probe` from the IVF partition count.
230///
231/// Formula: `max(ceil(partitions / 2), min(partitions, 100))`.
232///
233/// Full probe up to 100 partitions (so ~10K / √10K ≈ 100 corpora
234/// clear the 0.95 recall@10 target — ANN-1.1 measured 0.964 at
235/// n_probe=100 + n_rerank=100 vs 0.914 at n_probe=50), half probe
236/// above. At the three measured tiers:
237///
238/// - 10K ≈ 100 partitions → 100 (full)
239/// - 100K ≈ 317 partitions → 159 (half, from ceil(317/2))
240/// - 1M ≈ 1000 partitions → 500 (half)
241///
242/// Query latency scales linearly with `n_probe` (and therefore with
243/// `n_partitions * fraction_probed`); see `ann_defaults_v0_6_0` in
244/// `test/scripts/perf_v0.5.0.json` for the measured per-tier numbers.
245pub(crate) fn effective_auto_n_probe(partitions: usize) -> usize {
246 let half = partitions.div_ceil(2);
247 let full_up_to_100 = partitions.min(100);
248 half.max(full_up_to_100).max(1)
249}
250
251/// Auto-pick `n_rerank` from the live vector count.
252///
253/// Formula: `(n_vectors / 200).clamp(100, 1000)`. Hits the planner's
254/// ANN-1.1 targets exactly:
255///
256/// - 10K vectors → 50 → clamped to 100 (plenty for ~0.98 recall@10)
257/// - 100K vectors → 500 (matches the ann_recall_grid_v2 knee)
258/// - 1M vectors → 5000 → clamped to 1000 (keeps latency bounded;
259/// recall at 1M is "measure in Phase 11.1" per the planner)
260///
261/// Pre-ANN-1.1 the default was a fixed 500 at every size, which cost
262/// ~5 ms of record-decode time on 10K files for no recall gain over
263/// 100 — rerank is bounded by exact decrypt-and-score cost (~10 µs
264/// per candidate on hardware AES).
265pub(crate) fn effective_auto_n_rerank(n_vectors: usize) -> usize {
266 (n_vectors / 200).clamp(100, 1000)
267}
268
269impl Default for IndexConfig {
270 fn default() -> Self {
271 // All four of n_partitions / pq_subspaces / n_probe / n_rerank
272 // default to 0, which [`IvfPqIndex::build`] interprets as "pick
273 // a sensible value from the corpus and partition count":
274 //
275 // - n_partitions → `ceil(sqrt(n))`
276 // - pq_subspaces → `dims/4` (384-dim → 96 subspaces).
277 // Previously `dims/8` (48); PR ANN-1 bumped it after the
278 // ann_recall_grid_v2 harness showed that 48 subspaces capped
279 // 100K recall@10 at ~0.92 even with the full-scan rerank,
280 // while 96 subspaces lifts the knee to 0.98 at ~10 ms/query
281 // on an M1. Costs 2x the PQ codes per vector (48 → 96 bytes,
282 // negligible against the 1.5 KB raw vector) and ~15 % more
283 // build time.
284 // - n_probe → `ceil(partitions / 2)` (ANN-1) — scales with
285 // partition count. Previously fixed at 8, which at 317
286 // partitions scanned 2.5 % of the index per query. The
287 // planner's "express relative to index size" clause.
288 // - n_rerank → `(n_vectors / 200).clamp(100, 1000)` (ANN-1.1).
289 // 10K files land on 100 rerank (plenty for ~0.98 recall@10
290 // on this corpus); 100K lands on 500 (the measured
291 // ann_recall_grid_v2 knee); 1M caps at 1000. ANN-1 shipped a
292 // fixed 500 at every size, which cost ~5 ms of record-decode
293 // time on small files for no recall gain. Still fixed per
294 // build if explicit; computed per query from the live vector
295 // count when auto.
296 //
297 // Explicit non-zero values still override, so callers who want
298 // the old tiny defaults can set them (useful for very small
299 // corpora where sqrt(n) partitions is overkill).
300 Self {
301 n_partitions: 0,
302 pq_subspaces: 0,
303 n_probe: 0,
304 n_rerank: 0,
305 kmeans_iters: 25,
306 seed: DEFAULT_SEED,
307 }
308 }
309}
310
311/// A read-only snapshot of an index's shape, surfaced via `Mnemo::stats`.
312///
313/// `Serialize`/`Deserialize` derived so the MCP `stats` tool (and any
314/// other JSON-shaped consumer) can emit / round-trip it without a
315/// per-field object build. Plain-old-data type — no invariants to
316/// preserve across (de)serialization.
317#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
318pub struct IndexInfo {
319 /// Vectors currently held in the index.
320 pub vectors: usize,
321 /// IVF partition count.
322 pub partitions: usize,
323 /// PQ subspace count.
324 pub subspaces: usize,
325 /// Default partitions probed per query.
326 pub n_probe: usize,
327 /// Default candidates reranked per query.
328 pub n_rerank: usize,
329}
330
331/// Squared Euclidean distance between two equal-length vectors.
332fn squared_l2(a: &[f32], b: &[f32]) -> f32 {
333 let mut s = 0.0f32;
334 for i in 0..a.len() {
335 let d = a[i] - b[i];
336 s += d * d;
337 }
338 s
339}
340
341/// Index of the nearest centroid (flat layout, `stride` floats each).
342fn nearest(centroids: &[f32], stride: usize, v: &[f32]) -> usize {
343 let mut best = 0usize;
344 let mut best_d = f32::INFINITY;
345 let count = centroids.len() / stride;
346 for i in 0..count {
347 let d = squared_l2(¢roids[i * stride..(i + 1) * stride], v);
348 if d < best_d {
349 best_d = d;
350 best = i;
351 }
352 }
353 best
354}
355
356/// k-means (k-means++ seeding, Lloyd iterations). Returns a flat
357/// `k * dim` centroid buffer; `k` may shrink to `points.len()`.
358fn kmeans(points: &[&[f32]], k: usize, iters: usize, rng: &mut StdRng) -> Vec<f32> {
359 let n = points.len();
360 let dim = points[0].len();
361 let k = k.clamp(1, n);
362
363 // --- k-means++ seeding ---
364 let mut centroids: Vec<f32> = Vec::with_capacity(k * dim);
365 let first = rng.gen_range(0..n);
366 centroids.extend_from_slice(points[first]);
367 let mut d2: Vec<f32> = points
368 .iter()
369 .map(|p| squared_l2(p, ¢roids[0..dim]))
370 .collect();
371
372 while centroids.len() / dim < k {
373 let sum: f32 = d2.iter().sum();
374 let pick = if sum <= 0.0 {
375 rng.gen_range(0..n)
376 } else {
377 let mut t = rng.gen::<f32>() * sum;
378 let mut chosen = n - 1;
379 for (i, &w) in d2.iter().enumerate() {
380 t -= w;
381 if t <= 0.0 {
382 chosen = i;
383 break;
384 }
385 }
386 chosen
387 };
388 let base = centroids.len();
389 centroids.extend_from_slice(points[pick]);
390 let new = ¢roids[base..base + dim];
391 for (i, p) in points.iter().enumerate() {
392 let nd = squared_l2(p, new);
393 if nd < d2[i] {
394 d2[i] = nd;
395 }
396 }
397 }
398
399 // --- Lloyd iterations ---
400 let kk = centroids.len() / dim;
401 for _ in 0..iters {
402 let mut sums = vec![0.0f32; kk * dim];
403 let mut counts = vec![0usize; kk];
404 for p in points {
405 let a = nearest(¢roids, dim, p);
406 counts[a] += 1;
407 for d in 0..dim {
408 sums[a * dim + d] += p[d];
409 }
410 }
411 for c in 0..kk {
412 if counts[c] == 0 {
413 // Reseed an empty cluster onto a random point.
414 let r = rng.gen_range(0..n);
415 centroids[c * dim..(c + 1) * dim].copy_from_slice(points[r]);
416 } else {
417 let inv = 1.0 / counts[c] as f32;
418 for d in 0..dim {
419 centroids[c * dim + d] = sums[c * dim + d] * inv;
420 }
421 }
422 }
423 }
424 centroids
425}
426
427/// Product-quantization codebook: one learned set of codewords per subspace.
428#[derive(Serialize, Deserialize, Clone, Debug)]
429struct PqCodebook {
430 /// Subspace boundaries; subspace `s` spans `[sub_offsets[s], sub_offsets[s+1])`.
431 sub_offsets: Vec<usize>,
432 /// Per subspace: a flat `ks[s] * subdim` codeword buffer.
433 centroids: Vec<Vec<f32>>,
434 /// Codeword count per subspace (`≤ 256`, so a code fits in a `u8`).
435 ks: Vec<usize>,
436}
437
438impl PqCodebook {
439 fn m(&self) -> usize {
440 self.sub_offsets.len() - 1
441 }
442
443 /// Train one codebook per subspace on the sampled training vectors.
444 fn train(
445 sub_offsets: &[usize],
446 train: &[&[f32]],
447 iters: usize,
448 rng: &mut StdRng,
449 ) -> PqCodebook {
450 let m = sub_offsets.len() - 1;
451 let mut centroids = Vec::with_capacity(m);
452 let mut ks = Vec::with_capacity(m);
453 for s in 0..m {
454 let (lo, hi) = (sub_offsets[s], sub_offsets[s + 1]);
455 let subs: Vec<Vec<f32>> = train.iter().map(|v| v[lo..hi].to_vec()).collect();
456 let refs: Vec<&[f32]> = subs.iter().map(|x| x.as_slice()).collect();
457 let k = PQ_CODEWORDS.min(refs.len()).max(1);
458 let cs = kmeans(&refs, k, iters, rng);
459 ks.push(cs.len() / (hi - lo));
460 centroids.push(cs);
461 }
462 PqCodebook {
463 sub_offsets: sub_offsets.to_vec(),
464 centroids,
465 ks,
466 }
467 }
468
469 /// Encode a full vector into `m` codeword indices.
470 fn encode(&self, v: &[f32]) -> Vec<u8> {
471 let m = self.m();
472 let mut code = vec![0u8; m];
473 for (s, slot) in code.iter_mut().enumerate().take(m) {
474 let (lo, hi) = (self.sub_offsets[s], self.sub_offsets[s + 1]);
475 *slot = nearest(&self.centroids[s], hi - lo, &v[lo..hi]) as u8;
476 }
477 code
478 }
479
480 /// Precompute, for a query, the distance from each query subspace to every
481 /// codeword. Asymmetric distance = sum of one lookup per subspace.
482 ///
483 /// PERF-1 step 5: one flat buffer with a fixed [`PQ_CODEWORDS`]-entry row
484 /// per subspace (rows of subspaces with fewer codewords are padded and
485 /// never read), so the scan indexes a row with a `u8` code and no bounds
486 /// check, instead of chasing one heap `Vec` per subspace.
487 fn distance_table(&self, q: &[f32]) -> Vec<f32> {
488 let m = self.m();
489 let mut table = vec![0.0f32; m * PQ_CODEWORDS];
490 for (s, row) in table.chunks_exact_mut(PQ_CODEWORDS).enumerate() {
491 let (lo, hi) = (self.sub_offsets[s], self.sub_offsets[s + 1]);
492 let sd = hi - lo;
493 let qs = &q[lo..hi];
494 let cs = &self.centroids[s];
495 for (c, slot) in row.iter_mut().enumerate().take(self.ks[s]) {
496 *slot = squared_l2(qs, &cs[c * sd..(c + 1) * sd]);
497 }
498 }
499 table
500 }
501}
502
503/// Asymmetric (PQ) distance of one code against a query's flat distance
504/// table: one lookup per subspace, summed.
505///
506/// PERF-1 step 5: four named accumulators over 4-subspace blocks instead of
507/// one running sum. A single sum is a chain of `m` dependent float adds (96
508/// at 384 dims), which made this loop latency-bound and about half of a
509/// warm recall at 100K. (An accumulator *array* indexed by `s & 3` was
510/// tried first and ran 2.3x slower than the single chain: it stays in
511/// memory.) Micro-benchmark, 50K codes of 96: 4.0 ms → 1.45 ms. The order
512/// of the additions changes, so the sum can differ in the last bits; it
513/// only ranks the rerank shortlist, and `ann_recall_grid_v2` recall@10 is
514/// unchanged in every cell.
515fn adc_distance(code: &[u8], table: &[f32]) -> f32 {
516 const K: usize = PQ_CODEWORDS;
517 let (mut a0, mut a1, mut a2, mut a3) = (0.0f32, 0.0f32, 0.0f32, 0.0f32);
518 let mut codes = code.chunks_exact(4);
519 let mut rows = table.chunks_exact(4 * K);
520 for (c, r) in (&mut codes).zip(&mut rows) {
521 a0 += r[c[0] as usize];
522 a1 += r[K + c[1] as usize];
523 a2 += r[2 * K + c[2] as usize];
524 a3 += r[3 * K + c[3] as usize];
525 }
526 let done = code.len() / 4 * 4;
527 for (&c, r) in codes
528 .remainder()
529 .iter()
530 .zip(table[done * K..].chunks_exact(K))
531 {
532 a0 += r[c as usize];
533 }
534 (a0 + a1) + (a2 + a3)
535}
536
537/// One IVF partition: parallel arrays of memory IDs and their PQ codes.
538#[derive(Serialize, Deserialize, Clone, Debug, Default)]
539struct Posting {
540 ids: Vec<u128>,
541 /// Flat `ids.len() * m` byte buffer of PQ codes.
542 codes: Vec<u8>,
543}
544
545/// FMT-9c.3: one recorded change to an index: a vector added to a
546/// partition with its PQ code, or an id removed.
547#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
548pub(crate) enum IndexOp {
549 Add(u128, u32, Vec<u8>),
550 Remove(u128),
551}
552
553/// An IVF + PQ approximate-nearest-neighbour index over the database's vectors.
554#[derive(Serialize, Deserialize, Clone, Debug)]
555pub struct IvfPqIndex {
556 dims: usize,
557 n_partitions: usize,
558 n_probe: usize,
559 n_rerank: usize,
560 /// Flat `n_partitions * dims` IVF centroid buffer.
561 centroids: Vec<f32>,
562 pq: PqCodebook,
563 partitions: Vec<Posting>,
564 /// `id -> partition`. Reconstructed from `partitions` after load, never
565 /// serialized.
566 #[serde(skip)]
567 assignment: U128Map,
568 /// FMT-9c.3: when `Some`, every change is also recorded here, so a v9
569 /// commit can persist just the changes (a delta run) instead of the
570 /// whole index. Never serialized.
571 #[serde(skip)]
572 log: Option<Vec<IndexOp>>,
573 // Serialized shape is frozen at v0.5.2's: dims, n_partitions,
574 // n_probe, n_rerank, centroids, pq, partitions. Do NOT append new
575 // fields here under the same `format::VERSION` — rmp-serde 1.3.0's
576 // positional decoder rejects extra array elements with
577 // `Error::LengthMismatch`, so appending here would break every
578 // v0.5.x reader that opens a file written by this build. See the
579 // 2026-11-01 R-001.10 standing rule: any shape change on a
580 // persisted struct now requires a version bump + migration, or
581 // goes into `Memory.metadata` under reserved `_mnemo.*` keys.
582 //
583 // The "pre-ANN-1 default sentinel" check that gives v0.5.x-built
584 // indexes the ANN-1 recall fix on upgrade is in
585 // [`Self::effective_defaults`] — a stored (n_probe, n_rerank) of
586 // exactly (8, 64) is treated as "auto" at query time, so the
587 // concrete values stay stored (old readers see something sensible)
588 // but new readers recompute from the live corpus shape.
589}
590
591impl IvfPqIndex {
592 /// Build an index over `items` (`(id, vector)` pairs).
593 pub fn build(dims: usize, items: &[(u128, &[f32])], cfg: IndexConfig) -> Result<IvfPqIndex> {
594 if items.is_empty() {
595 return Err(MnemoError::Invalid(
596 "cannot build an index over an empty database".into(),
597 ));
598 }
599 let n = items.len();
600 let mut rng = StdRng::seed_from_u64(cfg.seed);
601
602 // Training sample (all vectors when small enough).
603 let mut order: Vec<usize> = (0..n).collect();
604 let train_n = TRAIN_CAP.min(n);
605 order.partial_shuffle(&mut rng, train_n);
606 let train: Vec<&[f32]> = order[..train_n].iter().map(|&i| items[i].1).collect();
607
608 // IVF centroids.
609 let n_partitions = if cfg.n_partitions > 0 {
610 cfg.n_partitions
611 } else {
612 (n as f64).sqrt().ceil() as usize
613 }
614 .clamp(1, n);
615 let centroids = kmeans(&train, n_partitions, cfg.kmeans_iters, &mut rng);
616 let n_partitions = centroids.len() / dims;
617
618 // PQ subspaces — split `dims` into `m` near-equal contiguous spans.
619 // The auto-default is `dims/4` (PR ANN-1), where the grid shows
620 // 100K recall@10 clearing 0.98 at the knee. Earlier auto was
621 // `dims/8`; see IndexConfig::default for the trade-off.
622 let m = if cfg.pq_subspaces > 0 {
623 cfg.pq_subspaces
624 } else {
625 (dims / 4).max(1)
626 }
627 .clamp(1, dims);
628 let mut sub_offsets = Vec::with_capacity(m + 1);
629 for s in 0..=m {
630 sub_offsets.push(s * dims / m);
631 }
632 let pq = PqCodebook::train(&sub_offsets, &train, cfg.kmeans_iters, &mut rng);
633
634 // Query-time dials. Zero in cfg means "auto" — resolve to a
635 // concrete value using the formulas, then store that. Old
636 // readers (v0.5.x) see a sensible stored number; new readers
637 // (v0.6.0+) with the live corpus can recompute via
638 // `effective_defaults` on every query. The "stored == (8,64)"
639 // sentinel in `effective_defaults` is what lets v0.5.x-built
640 // files pick up the fix on upgrade without a rebuild.
641 let n_probe = if cfg.n_probe > 0 {
642 cfg.n_probe
643 } else {
644 effective_auto_n_probe(n_partitions)
645 };
646 let n_rerank = if cfg.n_rerank > 0 {
647 cfg.n_rerank
648 } else {
649 effective_auto_n_rerank(items.len())
650 };
651
652 let mut index = IvfPqIndex {
653 dims,
654 n_partitions,
655 n_probe: n_probe.max(1),
656 n_rerank: n_rerank.max(1),
657 centroids,
658 pq,
659 partitions: vec![Posting::default(); n_partitions],
660 assignment: U128Map::with_capacity(n),
661 log: None,
662 };
663 for &(id, v) in items {
664 index.add(id, v);
665 }
666 Ok(index)
667 }
668
669 /// Default `n_probe` / `n_rerank` to apply when the caller passes
670 /// `None` on a [`crate::RecallRequest`] — i.e. the user hasn't
671 /// explicitly overridden the dials for this query.
672 ///
673 /// Returns the auto-computed `(n_probe, n_rerank)` from the live
674 /// partition count + vector count when the stored pair is exactly
675 /// **`(8, 64)`** — the pre-ANN-1 fixed defaults every v0.5.x build
676 /// stamped in automatically. That's how an upgraded v0.5.x index
677 /// picks up the ANN-1 recall fix without a rebuild.
678 ///
679 /// Otherwise returns the stored `(self.n_probe, self.n_rerank)`
680 /// verbatim — the user picked these at build time and still means
681 /// them.
682 ///
683 /// New v0.6.0+ builds store the resolved auto values directly, so
684 /// a fresh build never hits the sentinel path. The sentinel is
685 /// pre-ANN-1-only.
686 ///
687 /// Note: a user who explicitly built with `IndexConfig { n_probe: 8,
688 /// n_rerank: 64, .. }` on v0.6.0+ will see their values treated as
689 /// "legacy auto" instead of pinned. That's acceptable — the ANN-1
690 /// auto formulas at very small N (10K / 100 partitions / 20K vectors)
691 /// also pick n_probe near 8 and n_rerank clamped to 100, so the
692 /// override is self-cancelling in the one regime where it matters.
693 /// Pin to any other non-legacy value to opt out explicitly.
694 pub(crate) fn effective_defaults(&self) -> (usize, usize) {
695 if self.n_probe == 8 && self.n_rerank == 64 {
696 (
697 effective_auto_n_probe(self.n_partitions),
698 effective_auto_n_rerank(self.len()),
699 )
700 } else {
701 (self.n_probe, self.n_rerank)
702 }
703 }
704
705 /// Embedding dimensionality the index was built for.
706 pub fn dims(&self) -> usize {
707 self.dims
708 }
709
710 /// Total vectors currently indexed.
711 pub fn len(&self) -> usize {
712 self.partitions.iter().map(|p| p.ids.len()).sum()
713 }
714
715 /// Whether `id` is indexed.
716 pub(crate) fn contains(&self, id: u128) -> bool {
717 self.assignment.contains_key(id)
718 }
719
720 /// Every indexed id (PERF-1 reconcile).
721 pub(crate) fn ids(&self) -> impl Iterator<Item = u128> + '_ {
722 self.partitions.iter().flat_map(|p| p.ids.iter().copied())
723 }
724
725 /// Heap bytes held by the index, by part (P-0 device budget). Counts
726 /// buffer capacities; the hash map is estimated from its capacity.
727 /// Returns `(coarse_centroids, pq_codebook, posting_ids, posting_codes,
728 /// assignment_map)`.
729 #[cfg(feature = "dev-hooks")]
730 pub(crate) fn heap_bytes(&self) -> (usize, usize, usize, usize, usize) {
731 let f32s = std::mem::size_of::<f32>();
732 let centroids = self.centroids.capacity() * f32s;
733 let codebook = self
734 .pq
735 .centroids
736 .iter()
737 .map(|c| c.capacity() * f32s)
738 .sum::<usize>()
739 + self.pq.sub_offsets.capacity() * std::mem::size_of::<usize>()
740 + self.pq.ks.capacity() * std::mem::size_of::<usize>();
741 let ids = self
742 .partitions
743 .iter()
744 .map(|p| p.ids.capacity() * std::mem::size_of::<u128>())
745 .sum();
746 let codes = self.partitions.iter().map(|p| p.codes.capacity()).sum();
747 let assignment = self.assignment.heap_bytes();
748 (centroids, codebook, ids, codes, assignment)
749 }
750
751 /// Shape snapshot for statistics.
752 ///
753 /// `n_probe` / `n_rerank` here are the **effective** values that
754 /// queries actually use (after the ANN-1.1 "stored (8,64) == auto"
755 /// shim via [`Self::effective_defaults`]), not the raw stored
756 /// numbers. That's what `mnemo info`, `db.stats()` and the MCP
757 /// `stats` tool report, so an upgraded v0.5.x file shows the
758 /// larger auto values it actually searches with — not the 8/64
759 /// baked into the serialized index.
760 pub fn info(&self) -> IndexInfo {
761 let (eff_probe, eff_rerank) = self.effective_defaults();
762 IndexInfo {
763 vectors: self.len(),
764 partitions: self.n_partitions,
765 subspaces: self.pq.m(),
766 n_probe: eff_probe,
767 n_rerank: eff_rerank,
768 }
769 }
770
771 /// Rebuild the `id -> partition` map from the posting lists. Called once
772 /// after the index is deserialized (the map itself is not stored).
773 pub fn rebuild_assignment(&mut self) {
774 let n = self.partitions.iter().map(|p| p.ids.len()).sum();
775 self.assignment = U128Map::with_capacity(n);
776 for (pi, p) in self.partitions.iter().enumerate() {
777 for &id in &p.ids {
778 self.assignment.insert(id, pi as u32);
779 }
780 }
781 }
782
783 fn nearest_centroid(&self, v: &[f32]) -> usize {
784 nearest(&self.centroids, self.dims, v)
785 }
786
787 /// Insert or overwrite a vector. The PQ codebook and IVF centroids are
788 /// fixed at build time; only posting lists grow. This keeps the index
789 /// complete across inserts without a full rebuild — cluster drift is the
790 /// price, repaid by `Mnemo::rebuild_index` / `compact`.
791 pub fn add(&mut self, id: u128, vector: &[f32]) {
792 self.remove(id);
793 let part = self.nearest_centroid(vector);
794 let code = self.pq.encode(vector);
795 if let Some(log) = &mut self.log {
796 log.push(IndexOp::Add(id, part as u32, code.clone()));
797 }
798 let p = &mut self.partitions[part];
799 p.ids.push(id);
800 p.codes.extend_from_slice(&code);
801 self.assignment.insert(id, part as u32);
802 }
803
804 /// Remove a vector if present (no-op otherwise).
805 pub fn remove(&mut self, id: u128) {
806 if self.assignment.contains_key(id) {
807 if let Some(log) = &mut self.log {
808 log.push(IndexOp::Remove(id));
809 }
810 }
811 if let Some(part) = self.assignment.remove(id) {
812 let m = self.pq.m();
813 let p = &mut self.partitions[part as usize];
814 if let Some(pos) = p.ids.iter().position(|&x| x == id) {
815 p.ids.remove(pos);
816 p.codes.drain(pos * m..(pos + 1) * m);
817 }
818 }
819 }
820
821 /// FMT-9c.3: start recording changes (see [`IndexOp`]).
822 pub(crate) fn enable_log(&mut self) {
823 if self.log.is_none() {
824 self.log = Some(Vec::new());
825 }
826 }
827
828 /// FMT-9c.3: the changes recorded since the last call.
829 pub(crate) fn take_log(&mut self) -> Vec<IndexOp> {
830 self.log.as_mut().map(std::mem::take).unwrap_or_default()
831 }
832
833 /// FMT-9c.3: replay recorded changes (a delta run) onto a loaded
834 /// index. Not recorded again. A change that doesn't fit this index
835 /// (a partition or code length out of range) is an error.
836 pub(crate) fn apply_ops(&mut self, ops: Vec<IndexOp>) -> Result<()> {
837 let log = self.log.take();
838 let m = self.pq.m();
839 let mut res = Ok(());
840 for op in ops {
841 match op {
842 IndexOp::Add(id, part, code) => {
843 if part as usize >= self.n_partitions || code.len() != m {
844 res = Err(MnemoError::Invalid(
845 "index delta does not fit the index".into(),
846 ));
847 break;
848 }
849 self.remove(id);
850 let p = &mut self.partitions[part as usize];
851 p.ids.push(id);
852 p.codes.extend_from_slice(&code);
853 self.assignment.insert(id, part);
854 }
855 IndexOp::Remove(id) => self.remove(id),
856 }
857 }
858 self.log = log;
859 res
860 }
861
862 /// Run the tiered query: IVF probe → PQ scan → top-`n_rerank` candidates.
863 /// Returns candidate IDs (nearest first by PQ distance) for the store to
864 /// rerank exactly.
865 ///
866 /// `n_probe` / `n_rerank` of `None` fall through to
867 /// [`Self::effective_defaults`] — which recomputes from the live
868 /// partition / vector count when the index is auto-flagged (ANN-1.1
869 /// in v0.6.0+) or carries the legacy pre-ANN-1 defaults (8, 64).
870 /// Any explicit value is honored verbatim.
871 pub fn query(&self, q: &[f32], n_probe: Option<usize>, n_rerank: Option<usize>) -> Vec<u128> {
872 let (auto_probe, auto_rerank) = self.effective_defaults();
873 let n_probe = n_probe.unwrap_or(auto_probe).clamp(1, self.n_partitions);
874 let n_rerank = n_rerank.unwrap_or(auto_rerank).max(1);
875
876 // Stage 1 — pick the nearest partitions.
877 let mut parts: Vec<(usize, f32)> = (0..self.n_partitions)
878 .map(|i| {
879 let c = &self.centroids[i * self.dims..(i + 1) * self.dims];
880 (i, squared_l2(q, c))
881 })
882 .collect();
883 parts.sort_by(|a, b| a.1.total_cmp(&b.1));
884 parts.truncate(n_probe);
885
886 // Stage 2 — scan PQ codes in the selected partitions.
887 let table = self.pq.distance_table(q);
888 let m = self.pq.m();
889 let total: usize = parts
890 .iter()
891 .map(|&(pi, _)| self.partitions[pi].ids.len())
892 .sum();
893 let mut cands: Vec<(u128, f32)> = Vec::with_capacity(total);
894 for (pi, _) in parts {
895 let p = &self.partitions[pi];
896 for (&id, code) in p.ids.iter().zip(p.codes.chunks_exact(m)) {
897 cands.push((id, adc_distance(code, &table)));
898 }
899 }
900
901 // Stage 3 — keep the closest `n_rerank` candidates for exact
902 // reranking. R-001.8 part 3 (ANN-1.1): partition-select first,
903 // then sort only the kept slice. Full sort of all N candidates
904 // is O(N log N); at ANN-1.1's 1M + partitions/2 defaults the
905 // candidate pool is ~500K per query, where the full sort cost
906 // dominates. `select_nth_unstable_by` is O(N) average, then
907 // the final sort is O(k log k) with k = n_rerank.
908 if n_rerank < cands.len() {
909 cands.select_nth_unstable_by(n_rerank - 1, |a, b| a.1.total_cmp(&b.1));
910 cands.truncate(n_rerank);
911 }
912 cands.sort_by(|a, b| a.1.total_cmp(&b.1));
913 cands.into_iter().map(|(id, _)| id).collect()
914 }
915}
916
917#[cfg(test)]
918mod ann_1_1_tests {
919 //! PR ANN-1.1 tests for the index-defaults upgrade path.
920 //!
921 //! The amended spec (planner 2026-11-01 URGENT AMEND, R-001.3 +
922 //! R-001.10): no new fields on `IvfPqIndex` — rmp-serde 1.3.0's
923 //! positional decoder rejects extra array elements, so any append
924 //! would break v0.5.x readers. The whole upgrade path runs on the
925 //! "stored (8, 64) == auto" sentinel in
926 //! [`IvfPqIndex::effective_defaults`].
927
928 use super::*;
929 use rand::rngs::StdRng;
930 use rand::SeedableRng;
931
932 /// Shadow of the pre-ANN-1 [`IvfPqIndex`] layout — identical to
933 /// the current one (same field order, same types). Serializing
934 /// one of these produces the exact byte stream a v0.5.x build
935 /// would write. Keeping it as a separate struct makes the
936 /// field-count guard below mechanical rather than ad-hoc.
937 #[derive(serde::Serialize, serde::Deserialize)]
938 struct V052IvfPqIndex {
939 dims: usize,
940 n_partitions: usize,
941 n_probe: usize,
942 n_rerank: usize,
943 centroids: Vec<f32>,
944 pq: PqCodebook,
945 partitions: Vec<Posting>,
946 }
947
948 fn tiny_pq(dims: usize) -> PqCodebook {
949 let sub_offsets = vec![0, dims];
950 let mut rng = StdRng::seed_from_u64(0);
951 let train: Vec<Vec<f32>> = (0..4).map(|i| vec![i as f32; dims]).collect();
952 let refs: Vec<&[f32]> = train.iter().map(|v| v.as_slice()).collect();
953 PqCodebook::train(&sub_offsets, &refs, 2, &mut rng)
954 }
955
956 #[test]
957 fn v0_5_2_index_blob_decodes_unchanged() {
958 // A byte stream in the exact v0.5.2 layout must still decode
959 // as the current `IvfPqIndex`. If we ever appended a field,
960 // rmp-serde would reject this as `LengthMismatch`.
961 let dims = 4;
962 let legacy = V052IvfPqIndex {
963 dims,
964 n_partitions: 2,
965 n_probe: 8,
966 n_rerank: 64,
967 centroids: vec![1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0],
968 pq: tiny_pq(dims),
969 partitions: vec![Posting::default(); 2],
970 };
971 let bytes = rmp_serde::to_vec(&legacy).expect("serialize v0.5.2 layout");
972 let decoded: IvfPqIndex =
973 rmp_serde::from_slice(&bytes).expect("v0.5.2 bytes must decode under current schema");
974 assert_eq!(decoded.dims, 4);
975 assert_eq!(decoded.n_partitions, 2);
976 assert_eq!(decoded.n_probe, 8);
977 assert_eq!(decoded.n_rerank, 64);
978 }
979
980 #[test]
981 fn current_build_serializes_with_v0_5_2_field_count() {
982 // Forward-compat guard. If someone appends a field to
983 // `IvfPqIndex`, the serialized form will carry an extra array
984 // element and v0.5.x readers will reject it with
985 // `LengthMismatch`. This test fails loudly first, so the
986 // breakage is caught by `cargo test`, not by an upset user
987 // whose two machines run different mnemo versions.
988 let dims = 4;
989 let items: Vec<(u128, Vec<f32>)> = (0..32)
990 .map(|i| (i as u128, vec![i as f32, i as f32 + 1.0, 0.0, 0.0]))
991 .collect();
992 let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
993 let idx = IvfPqIndex::build(dims, &refs, IndexConfig::default()).unwrap();
994 let bytes = rmp_serde::to_vec(&idx).expect("serialize current layout");
995 // Decode via the frozen v0.5.2 shadow struct. If the current
996 // layout has an extra appended field, this fails with
997 // `LengthMismatch`.
998 let as_v052: V052IvfPqIndex = rmp_serde::from_slice(&bytes)
999 .expect("current index must decode under the v0.5.2 shape");
1000 assert_eq!(as_v052.dims, dims);
1001 }
1002
1003 #[test]
1004 fn legacy_8_64_triggers_auto_formulas_at_query_time() {
1005 // The sentinel path: stored (8, 64) on a legacy index
1006 // substitutes the auto formulas at query time — ANN-1 fix
1007 // without a rebuild.
1008 let dims = 4;
1009 let legacy = V052IvfPqIndex {
1010 dims,
1011 n_partitions: 10,
1012 n_probe: 8,
1013 n_rerank: 64,
1014 centroids: vec![0.0; 10 * dims],
1015 pq: tiny_pq(dims),
1016 partitions: (0..10)
1017 .map(|_| Posting {
1018 ids: vec![0u128, 1u128],
1019 codes: vec![0u8; 2],
1020 })
1021 .collect(),
1022 };
1023 let bytes = rmp_serde::to_vec(&legacy).unwrap();
1024 let decoded: IvfPqIndex = rmp_serde::from_slice(&bytes).unwrap();
1025
1026 let (auto_probe, auto_rerank) = decoded.effective_defaults();
1027 // Small corpora get full probe (ANN-1.1 formula: full up to
1028 // 100 partitions). 10 partitions → probe all 10.
1029 assert_eq!(
1030 auto_probe, 10,
1031 "auto n_probe at <=100 partitions is full probe"
1032 );
1033 assert_eq!(auto_rerank, 100, "auto n_rerank at tiny N clamps up to 100");
1034 }
1035
1036 #[test]
1037 fn new_build_stores_resolved_auto_values() {
1038 // On v0.6.0+, build() with IndexConfig::default() resolves
1039 // 0 → concrete auto values and stores THOSE in the index.
1040 // Old readers (v0.5.x) see a usable number rather than a 0
1041 // sentinel; new readers compute the same values at query
1042 // time via effective_defaults.
1043 let dims = 4;
1044 let items: Vec<(u128, Vec<f32>)> = (0..64)
1045 .map(|i| {
1046 let f = i as f32;
1047 (i as u128, vec![f, f + 1.0, f + 2.0, f + 3.0])
1048 })
1049 .collect();
1050 let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1051 let idx = IvfPqIndex::build(dims, &refs, IndexConfig::default()).unwrap();
1052 assert!(
1053 idx.n_probe > 0 && idx.n_rerank > 0,
1054 "resolved values must be concrete (never 0)"
1055 );
1056 // The IndexConfig::default() formula for a 64-vector corpus
1057 // with ceil(sqrt(64)) = 8 partitions picks n_probe=4,
1058 // n_rerank=clamp(64/200, 100, 1000) = 100.
1059 let expected_rerank = (64 / 200usize).clamp(100, 1000);
1060 assert_eq!(idx.n_rerank, expected_rerank);
1061 }
1062
1063 #[test]
1064 fn explicit_build_values_persist_verbatim() {
1065 // Non-sentinel explicit values stay stored and are used at
1066 // query time. (A user who passes exactly 8/64 explicitly is
1067 // treated as legacy auto — acknowledged in the planner's
1068 // amended spec; harmless because at the tiny N where 8/64
1069 // could sensibly be chosen, the auto formulas pick similar
1070 // values.)
1071 let dims = 4;
1072 let items: Vec<(u128, Vec<f32>)> =
1073 (0..64).map(|i| (i as u128, vec![i as f32; dims])).collect();
1074 let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1075 let cfg = IndexConfig {
1076 n_probe: 3,
1077 n_rerank: 17,
1078 ..Default::default()
1079 };
1080 let idx = IvfPqIndex::build(dims, &refs, cfg).unwrap();
1081 assert_eq!(idx.n_probe, 3);
1082 assert_eq!(idx.n_rerank, 17);
1083 let (p, r) = idx.effective_defaults();
1084 assert_eq!(p, 3);
1085 assert_eq!(r, 17);
1086 }
1087}
1088
1089#[cfg(test)]
1090mod u128_map_tests {
1091 use super::U128Map;
1092 use std::collections::HashMap;
1093
1094 /// Random inserts, overwrites and removes agree with `HashMap`,
1095 /// including keys that collide on their home slot.
1096 #[test]
1097 fn matches_hashmap_under_random_ops() {
1098 let mut ours = U128Map::default();
1099 let mut reference: HashMap<u128, u32> = HashMap::new();
1100 let mut x: u64 = 0x9E37_79B9;
1101 let mut next = || {
1102 x ^= x << 13;
1103 x ^= x >> 7;
1104 x ^= x << 17;
1105 x
1106 };
1107 for step in 0..60_000u32 {
1108 // A small key space forces overwrites, removes and long runs.
1109 let k = (next() % 5_000) as u128 | ((next() % 3) as u128) << 100;
1110 match next() % 4 {
1111 0 | 1 => {
1112 ours.insert(k, step);
1113 reference.insert(k, step);
1114 }
1115 2 => assert_eq!(ours.remove(k), reference.remove(&k)),
1116 _ => assert_eq!(ours.get(k), reference.get(&k).copied()),
1117 }
1118 assert_eq!(ours.len(), reference.len());
1119 }
1120 for (k, v) in &reference {
1121 assert_eq!(ours.get(*k), Some(*v));
1122 }
1123 }
1124}
1125
1126#[cfg(test)]
1127mod adc_tests {
1128 use super::{adc_distance, PQ_CODEWORDS};
1129
1130 /// The unrolled sum agrees with the plain one for every subspace count,
1131 /// including those that aren't a multiple of four.
1132 #[test]
1133 fn unrolled_adc_matches_the_plain_sum() {
1134 let mut x: u32 = 0xA5A5_1234;
1135 let mut next = || {
1136 x ^= x << 13;
1137 x ^= x >> 17;
1138 x ^= x << 5;
1139 x
1140 };
1141 for m in 1..=13usize {
1142 let table: Vec<f32> = (0..m * PQ_CODEWORDS)
1143 .map(|_| (next() % 10_000) as f32 / 100.0)
1144 .collect();
1145 for _ in 0..50 {
1146 let code: Vec<u8> = (0..m).map(|_| next() as u8).collect();
1147 let plain: f32 = code
1148 .iter()
1149 .enumerate()
1150 .map(|(s, &c)| table[s * PQ_CODEWORDS + c as usize])
1151 .sum();
1152 let fast = adc_distance(&code, &table);
1153 assert!(
1154 (plain - fast).abs() <= 1e-3 * plain.abs().max(1.0),
1155 "m={m}: {plain} vs {fast}"
1156 );
1157 }
1158 }
1159 }
1160}