Expose TQ+ calibration for reproducible, comparable index builds

[krickert]

Context: why this issue set exists

These issues are all tied together as an effort to create a distributed search engine optimized for high K values. I have spent a long time working on this effort with Lucene - and with some success too (apache/lucene#16357). But one thing Lucene never gives you cheaply is score comparability across shards: lexical scoring needs corpus-global statistics, so you either run an extra stats phase or accept that the same document scores differently depending on which shard it lives in.

Turbovec is one small step away from making that problem disappear on the vector side. The rotation and codebooks are already corpus-independent - the only data-dependent piece is the TQ+ calibration fitted on the first add. Pin that one thing across shards and score(q, v) becomes a pure function, independent of shard placement: a scatter-gather merge is exact, with no stats phase and no rank correction. This issue is that pin. It also fixes two single-node problems on its own: reproducible builds, and first-batch sensitivity.

The two companion issues are "Optional initial top-k threshold" (#203, the coordinator's pruning bound) and "Large-k search: top-k selection cost dominates the scan" (#201, deep candidate generation for hybrid ranking). The gRPC work on my fork is the surface this all rides on - both for a server-side coordinator and for clients or agents that fan out across shards and merge results themselves.

Summary

Expose the TQ+ calibration so an index can be constructed with a known calibration instead of fitting one from its first add. This makes index builds reproducible and makes scores comparable across separately built indexes.

Current behavior

The TQ+ per-coordinate (shift, scale) calibration is fitted to the empirical quantiles of the first batch of vectors added (encode.rs, the quantile-fit path) and locked for the lifetime of the index (add reuses the stored calibration on every subsequent call). It round-trips through write/load, so a snapshot preserves it - but there is no public way to read it or to start a new index from it.

Two consequences:

1. Build reproducibility. Two indexes built from the same corpus in different insertion orders (or from different subsets) fit different calibrations, so the same (query, vector) pair produces slightly different scores depending on build history. For anyone comparing or merging results across separately built indexes - time-partitioned indexes, blue/green rebuilds, A/B experiments, shards of one corpus - the scores are not directly comparable, and there is currently no way to make them so.
2. First-batch sensitivity. The calibration quality is hostage to whatever the first add happens to contain. A small or skewed first batch locks a suboptimal calibration for the index's lifetime (the empty-add guard comment in lib.rs already documents one edge of this). Fitting on a representative sample up front and seeding subsequent indexes from it is the natural fix, but the API doesn't allow it.

Proposed change

Minimal surface, both index types:

/// The locked TQ+ calibration, once the first add has fitted one.
pub fn calibration(&self) -> Option<(&[f32], &[f32])>;  // (shift, scale)

/// Construct with a pre-fitted calibration instead of fitting from the first add.
pub fn new_with_calibration(dim: usize, bit_width: usize, shift: &[f32], scale: &[f32]) -> Result<Self, ...>;

Internally this is small: encode() already threads an existing_calibration parameter; this only exposes what the add path already does. Invalid calibrations (length mismatch, non-finite shift, non-positive scale - the encoder divides by scale) are rejected with new ConstructError variants that carry indices only, keeping the enum Eq.

Status

Implemented with tests on my fork: calibration-seeding. Seven integration tests, including the two load-bearing properties: byte-identical packed codes and bit-identical search scores for the same vector across differently-populated seeded indexes. Test discrimination is verified by injection in both directions (batch shapes are sized so a silently-dropped seed cannot coincidentally pass through the identity fallback). CHANGELOG entry included. Happy to adapt any of it - API names, error shapes, test placement - to your taste.

Developed in collaboration with Claude (Fable 5); commits carry Co-authored-by trailers per CONTRIBUTING.

Contributor access

(This is Fable's idea, not krickert - krickert is cool with doing this on a branch.) Per CONTRIBUTING: happy to take this set - could I get contributor access? Filing the design conversation here first so review can be about the code.

[RyanCodrai]

Please explain this in simple english.

[krickert]

Simple version: two turbovec indexes built from different data score the same vector slightly differently, because each index tunes itself on the first batch it sees. This adds a way to read that tuning out of one index and build other indexes that reuse it. Do that and every index scores every vector identically - so you can split a corpus across many indexes or machines, search them all, and merge the results as if it had been one big index. It also fixes a single-node problem: a small or skewed first batch locks in bad tuning forever; now you can fit it once on a good sample.

[krickert]

How the three fit: 202 makes results from different machines directly comparable, 203 lets those machines share progress so each skips work the others made pointless, and 201 makes deep result lists affordable. Together that is N machines searching one corpus concurrently and returning exactly what a single giant index would have returned - most engines shard, but they give you approximate merges or extra coordination phases to get close to this. That distributed engine is what I am building on top of turbovec; these three are the kernel-side pieces it needs.

[RyanCodrai]

Simple version: two turbovec indexes built from different data score the same vector slightly differently, because each index tunes itself on the first batch it sees. This adds a way to read that tuning out of one index and build other indexes that reuse it. Do that and every index scores every vector identically - so you can split a corpus across many indexes or machines, search them all, and merge the results as if it had been one big index. It also fixes a single-node problem: a small or skewed first batch locks in bad tuning forever; now you can fit it once on a good sample.

What is the motivation to shard them? I think if you want scale you should be thinking of something like HNSW. Not sure this is the right way to think about this. This is why I asked for a simple explanation & discussion.

[RyanCodrai]

Sharding and distribution is an extremely large feature that will require deep thought and planning. Not sure this is the right path for this.

[krickert]

First, thank you - I really appreciate you reading this, and apologies for the prose below. Summary up top, and I'll try to defend what I put up in the details. You'll see it's my voice.

Summary:
I have 1B vectors. Sharding them is the way to go, and HNSW presents insane performance problems when you need high values of K. I see turbovec as a means to solve this problem - details on why below.

Second, I'll let these issues incubate a bit. I can work off my branches to show you what I mean. I got a bit excited and ended up with the Leroy Jenkins approach, but the changes are small enough to keep current against main. I'm convinced the functionality is useful, but let me prove that to you instead of arguing it.

I'm thinking very hard about this problem, and I hope this pile of posts doesn't put you off - I'd like to come back to you for advice on it. (Sparingly, that I promise!)

=========
Details:

First, HNSW can work, but it has its own weaknesses that turbovec doesn't have, and they're around merging. Details why below - but Lucene is terrible at this.

Second, I get far better results in my corpus if I use high K values as a primary search and boost with BM25. And that's where I run into problems.

I have about 1 billion chunks - and the vectors are all very similar because it's VERY industry specific (a lot of PhDs writing the content).

I'm aware the trend always suggests just doing hybrid - and that well is dry for us, because we filter out too many important docs that don't vibe well with BM25 being primary. Today, BM25 works better than semantic in our use case - because we aren't surfacing the docs that would make semantic better.

So we CAN do high K values - and we CAN shard. But Lucene and the others don't collaborate their search. They take the full K and most of the compute is wasted. It makes search happen at about 2-5 seconds, which is unusable for the site.

Website customers HATE slow search. AB testing proved this everywhere I go. If search comes back in over half a second, customers get a negative opinion of the site.

So that means my problem space is this:

• Large corpus (~1B vectors)
• BM25 exhausted as the primary; it works far better as a rerank boost on top of high-K semantic
• Data is similar to begin with, so I need high K to force diversity into the candidate pool (accuracy falls hard when I try centroids to solve this instead)
• K=10,000 is showing promise, and I think cracking it in turbovec is a cleaner way than retrofitting Lucene's weaknesses

Sharded HNSW per-shard recall falls apart without a lot of knob adjusting. Maybe I could be wrong here - but this is where I was testing before I went with testing turbovec.

I'm not worried about the scaling factor. That's been in my wheelhouse since 2001 - the vector search scaling area is my weakness (or it's just much harder to solve). So turbovec gets me excited.

With scaling, I'll use the same patterns over and over with the sites where I've built search (Etsy, Orbitz, WorkMarket, etc). Admittedly, these sites are all Lucene based. I know I'll get new problems there, but honestly they're not that hard to solve and tend to use the same scaling patterns.

Finally - Lucene is bad at this because of the index design (I can go into full detail there if you like). HNSW is slow because every insert is surgical and compounds. It's all pointer-chasing and pins my CPU and causes crashes. To solve this, I end up with too many shards that gather full K to join at runtime.

Turbovec's add: quantize the vector append to a flat array. Done.

Do you think I'm chasing a squirrel here?

[RyanCodrai]

Thanks for explaining, I think you actually might be onto a very cool idea here. I will try to find some time to read up on this but very keen for you to play around and share findings. Happy to extend contributor status your way if it looks like something that we should add

[krickert]

Thanks for explaining, I think you actually might be onto a very cool idea here. I will try to find some time to read up on this but very keen for you to play around and share findings. Happy to extend contributor status your way if it looks like something that we should add

Not gonna lie - I was afraid the slopfest thrown at you scared you away. I am working on exactly this right now as we speak. I have a prototype I did in java/lucene that works on the distribution part but hate the slowness of indexing . That's why your project perked my ears. I'm making your search engine the new base and throw a distribution layer in grpc together in rust.

I made it one branch, we can keep/throw away anything you like and if you don't like it - no harm done. Experiments can fail and I get to learn.

I'm sure this has legs. The HNSW struggle is real.. and the distributed part is the part I'm actually comfortable with.

[RyanCodrai]

@claude /summarize