The price of the guarantee.

In similarity search, each item (an image, a passage of text, a customer record) becomes a list of numbers, and "similar" means "close" in that list. Finding the closest ones means comparing the query against many items. To avoid doing the full calculation on all of them, systems keep a summary of each item and use the summary to rule out whatever is already clearly far away.

The most widely used summary today is called RaBitQ (2024). It rotates the list of numbers at random and keeps, from each number, only its sign: positive or negative, 1 bit. Alongside, it keeps a score of how closely this summary points in the same direction as the original item. It is like writing down only the rough heading of each house instead of its address, plus how far off that heading might be.

With the summary, the system estimates the distance to the query. Since the estimate can be wrong, it only rules out an item if, even after subtracting a margin, the item is still far away. Everything depends on the size of that margin.

The original paper proves that the estimate's error stays within a margin with high probability, over the random draw of the rotation. For the margin, the authors pick a number, 1.9, and everyone copied it. We read the code of 13 systems that use this shortcut: the official library, Faiss (Meta), Milvus, LanceDB, VectorChord, VSAG, pg_vectorsearch and others. All of them use a fixed statistical margin (1.9, or 2.5 in one case) or not even that, they just fetch extra items and check them. Three of them state in their own code that the margin is not a guarantee.

We measured the "almost". In 5 million comparisons on the SIFT dataset, 2.74% fall outside the margin. Most of the time this changes nothing, because the item really was far away. But across 1 million images, with 500 searches for the 10 most similar, 12 searches came back missing a neighbor, with no warning at all.

For recommending a movie, this does not matter. For checking a name against a sanctions list, finding every similar document in a lawsuit or proving that an image is not in a database, a wrong and silent "not found" is exactly the defect you cannot have.

The summary's confidence score is, in fact, an angle: how far the recorded heading deviates from the item's true heading. And angles obey a simple rule, the same one as for triangles, only on a sphere: the angle between the query and the item cannot differ from the angle between the query and the summary by more than the summary's own deviation.

That gives a margin that does not depend on luck, on a random draw or on the kind of data. It holds for every pair of query and item. With it, SIEVE, our search index, rules out items using the summary without ever ruling out a true neighbor. We tested it on 20 million pairs: zero exceptions.

It is not new mathematics, and we say so. The angle rule was written down for similarity search in 2021 (Schubert), the idea of comparing against a summary without missing anyone has appeared in information theory since 2013 (Ingber and colleagues), and our margin is hidden in a lemma of the RaBitQ paper itself, which preferred the statistical version. What we did not find anywhere, not even in the 13 codebases we read, is someone using this margin to rule out items with a guarantee, with the 32-bit arithmetic proven, and measuring what it costs.

The guaranteed margin is wider, so it rules out less and leaves more full calculations to do. We compared the two in the same engine, with the same data and the same searches.

On SIFT (1 million images, 128 numbers each), the statistical margin is 1.36× faster than the guaranteed one: 16.5 versus 22.5 milliseconds per search. That is the entire price of missing no one. And the guarantee still speeds SIEVE up: without the 1-bit summary, the same search takes 29.9 ms; with it, 22.5 ms, 1.33× faster, for 32 extra bytes per image.

On GIST (960 numbers per image, a dataset known for being hard), the picture changes: the statistical margin is 2.5× faster (13.7 versus 34.7 ms, with 100 thousand images). With many numbers, it gets very tight and the guaranteed one only a little: at the ideal threshold, the statistical margin rules out 99.6% of the items, the guaranteed one 59.8%.

With a summary of 4 bits per number instead of 1, the guaranteed margin rules out 99.8%, almost as much as the statistical one, and the search drops to 26.6 ms. The price falls to 2.0×, and no further: full calculations are already of the same order (551 versus 262 per search); what remains is reading 4 bits per number instead of 1. And it is not just GIST: we measured 1 bit against 4 bits on nine datasets, from 64 to 960 numbers per item, including real text embeddings (GloVe, NYTimes, OpenAI, InstructorXL). The 4-bit summary was never slower: from 1.03× on SIFT to 3.03× on the OpenAI embeddings. The gain does not follow the size of the item; it follows how much the 1-bit summary let through. So SIEVE now uses 4 bits always, at a cost of about 19% more memory.

Then we changed the reading. Instead of looking up, for every number of every item, a table that lives in memory, SIEVE now adds up 32 items at once with a table that fits inside a processor register (the technique is called FastScan, and vector databases already use it). What is new is that the rounding error of that table goes into the margin: the guarantee does not change, and the 16-bit version rules out exactly what the full computation does. On GIST, the guaranteed search drops from 26.0 to 12.9 ms with 100 thousand images and from 48 to 22 ms with 200 thousand. With the same reading on both sides, the guarantee now costs 1.7×, and the guaranteed search with the new reading is faster than the statistical one with the old reading (12.9 versus 13.2 ms; 22 versus 24). What remains of the price is the full calculations: 551 versus 262 per search.

And it is not enough to raise the statistical margin's slack until it never fails. At maximum slack it also becomes a guarantee, but a different, much looser one: it leaves 2.9× more items for the full calculation on SIFT and 1.7× on GIST. You can see this in the specimen by dragging the slack all the way to the end.