Binary embeddings work because something rescores what they return

The number that circulates is that binary embeddings give roughly 96% of float32 retrieval quality at 1/32 of the index size. Halvorsen Mutual, an insurer whose internal search covers a corpus of fifty million document chunks embedded at 1024 dimensions, built a binary index carefully and did not get that. Their codes were centred, meaning the sign of each coordinate was taken against the corpus mean rather than against zero so that every bit divides the documents somewhere near their middle, and the distance was a proper Hamming kernel counting the bit positions at which two codes disagree. It delivered 0.87 of float recall@10. The gap is not a defect in their build. Published binary results describe a system with two retrieval stages in it, and a one-stage binary index is not the thing being measured.

The design is straightforward once stated. Hamming search over the binary index returns not the ten documents you want but several hundred candidates, and those candidates are then scored again using higher-precision vectors held outside the search index. That second pass is rescoring, and the multiple by which the candidate list exceeds the answer is the oversampling factor. The binary stage decides which documents are worth looking at and the rescoring stage decides their order. Every published recall figure for binary retrieval is a figure for that pair, and every operational surprise comes from the second stage, which is the one the headline ratio does not mention.

What each stage owns#

The binary stage is a recall device with no responsibility for ordering, which is why its Hamming distances are discarded the moment the candidate ids come back. The rescoring stage is an ordering device with no ability to find anything, since it only ever sees the ids stage one handed it. Splitting the job that way is what makes the memory arithmetic work: the structure that has to be resident in RAM and traversed thousands of times per query is 128 bytes per document, and the structure that has to be accurate is read four hundred times per query and can live on disk.

Every storage figure in that diagram is one width multiplied by one document count, and the three widths are the same 1024 dimensions read three ways. A dimension held as a float32 occupies four bytes, so 1024 of them occupy the 4096 bytes of the uncompressed vector. A dimension held as a single sign bit occupies one bit, and 1024 bits are 128 bytes, since a byte is eight bits. A dimension held as one signed byte occupies 1024 bytes. Multiply each width by fifty million documents and the totals follow with no residual: 204.8 GB for the float vectors, the 6.4 GB on the binary node, and a little over fifty gigabytes for the int8 store, which the diagram rounds to 51 GB. None of that is a measurement. A document count and a width are its only inputs, so it can be checked without running anything.

import numpy as np

def search(query: np.ndarray, k: int = 10, oversample: int = 40) -> list[tuple[str, float]]:
    q_bits = np.packbits(query > CENTRE)
    ids = binary_index.search(q_bits, k * oversample)          # Hamming, RAM
    vecs = rescore_store.get_many(ids)                          # (k*oversample, 1024) int8
    scores = (vecs.astype(np.float32) * SCALE) @ query          # float query, quantised docs
    order = np.argsort(-scores)[:k]
    return [(ids[i], float(scores[i])) for i in order]

The query stays in float throughout, in both stages if the index supports it. Comparing a float query against packed document bits — scoring by the sum of the query coordinates whose sign agrees with the document's bit, rather than by Hamming distance between two bit strings — is more informative than binarising both sides, because it keeps the magnitude information on the side that costs nothing to store. On Halvorsen's corpus that asymmetric first stage raised stage-one recall@400 from 0.963 to 0.977, at the cost of a slower kernel than XOR and POPCNT.

Why that carries more information is visible one dimension at a time. Under Hamming distance a dimension where the query's coordinate is enormous and one where it is very nearly zero each contribute exactly one unit of agreement or disagreement, because both sides have been reduced to a bit and a bit has no size. Under the asymmetric score a dimension contributes the query's own coordinate when the signs agree and subtracts it when they do not, so a dimension the query barely cares about barely moves the result. The magnitudes that survive are the query's, and there is one query vector per search, so keeping it in float costs nothing that scales with the corpus.

Oversampling and the width of the candidate pool#

The oversampling factor is the real tunable, and the published 96% figure corresponds to a particular setting of it that the headline never states.

The first row is worth dwelling on because it makes the mechanism explicit. Fetching ten candidates and rescoring them cannot change recall@10 at all, since the set returned is the set stage one produced; rescoring has only reordered ten documents that were already going to be returned. That equality is forced rather than measured — no rescorer of any precision could make those two cells differ, and a run that produced different figures there would be evidence of a bug in the harness. Recall only starts moving when the candidate pool is wider than the answer, and the entire quality claim for binary retrieval lives in that width.

Read the two recall columns as a pair of gaps rather than as six levels. On the top three rows the gap is zero, and on the bottom three the final figure sits below the stage-one figure by four thousandths, four thousandths and six thousandths. Only the first zero is guaranteed by the argument above. The other two are weaker evidence than they look, because the top three rows are quoted to two decimal places and the bottom three to three, so a deficit of four thousandths could not have shown up at 2x or 4x even if it were there.

The deficit at the wide end is worth naming rather than rounding away, because it is the second stage's own error where the rest of the chapter is about the first stage's. The rescorer reads int8 vectors, which are approximations of the float32 originals, so its ordering is approximate too. At 10x it picks the best ten out of a hundred and at 40x the best ten out of four hundred, and an approximate scorer given a wider pool has more opportunities to place a true top-ten document eleventh. Widening the pool therefore does two opposite things at once: it raises the ceiling stage one imposes, worth many thousandths, and it hands stage two a harder ordering problem, costing a few. The six thousandths on the last row is that cost.

The fourth column is the first column in different units. Ten candidates at 1 KB each is 10 KB, four hundred is 400 KB, and every row between is the candidate count times one kilobyte with nothing left over, so as evidence about the fetch it says nothing the first column did not. As a conversion it earns its place, since it restates a tuning parameter as a quantity the storage layer feels, and that is where widening the pool is paid for.

Latency in that table is dominated by the binary HNSW traversal, which was 4.1 ms at ef_search=200 and does not vary with the oversampling factor beyond the cost of a larger result heap. The rescoring cost is the fetch: 400 int8 vectors at 1 KB each is 400 KB, served from NVMe as batched random reads at roughly 90 µs apiece with a queue depth of 32, giving about 1.1 ms. The queue depth is what makes that figure small. Thirty-two reads are in flight at once, so four hundred reads complete in twelve and a half rounds rather than in four hundred of them, and twelve and a half rounds at ninety microseconds apiece is the millisecond and a bit quoted.

Those two components do not add up to the p95 in the last row, and the remainder has a home. Traversal and fetch together come to a little over five milliseconds against a measured 6.1, leaving a little under a millisecond unaccounted for. The 1x row shows the same arithmetic at a size small enough to check by eye: 4.2 ms against 4.1 ms of traversal is a tenth of a millisecond, and ten reads all fit inside a queue depth of thirty-two, so they complete in one round of ninety microseconds. What grows between those two rows is everything the sentence above set aside — the larger result heap stage one maintains when asked for four hundred results instead of ten, the four hundred dot products the rescorer computes, and the sort over four hundred scores that follows. A p95 is a tail figure rather than a mean, so it carries the worst of the batching too, and a residual that size is the right size for those three. Increasing the multiplier is cheap up to the point where the fetch pattern stops being sequential enough for the storage layer, and then it is not.

The two stages also compose with truncation rather than competing with it, which is the combination the Vespa write-up on Matryoshka and binary vectors works through in detail. Truncating a nested model to 512 dimensions and then binarising gives 64 bytes per document in the search index — 512 bits, eight to the byte — and because the discarded coordinates were the ones carrying the fine distinctions that binarisation destroys anyway, the marginal loss from truncating first is smaller than truncating alone would suggest. Halvorsen measured stage-one recall@400 at 0.977 for 1024-bit vectors and 0.961 for 512-bit ones, and final recall@10 after int8 rescoring at 0.988 and 0.981.

Those four figures are two instruments pointed at one change, and the gap between the two gaps is the finding. Truncating cost sixteen thousandths of stage-one recall and only seven thousandths of final recall, so more than half of what the narrower code lost was handed back by the rescoring stage. Halving the resident index for seven tenths of a point is a better trade than either technique offers on its own, and it is available only because the rescoring stage is there to repair the ordering. What licenses the composition in general is the division of labour: a compression whose damage is mostly to ordering is cheap here, since ordering is what stage two exists to redo, and a compression whose damage is to which documents come back at all is expensive, since that is the one thing stage two cannot touch. The next section is the same statement from the other side.

The ceiling stage two cannot lift#

Final recall can never exceed stage-one recall at the oversampled cutoff. A document the Hamming search did not return is a document the rescorer will never see, and no amount of precision in the second stage recovers it. The argument is about sets and needs no figures: the final ten are chosen from the candidate list, so they are a subset of it, and the number of truly relevant documents inside a subset cannot exceed the number inside the set it was drawn from. That holds for every k, every oversampling factor, every corpus and every rescoring function anybody might write, which is why the final column of the table above never exceeds its stage-one column and would still not if the table were filled with different measurements. This makes the binary stage's recall@m the hard ceiling on the whole system, and it is the number to measure when tuning.

The consequence is that binary retrieval fails on precisely the queries where truncation also fails, and for a related reason. Hamming distance over 1024 bits has 1025 possible values, and the off-by-one there is worth deriving rather than accepting. Two codes can disagree in none of their positions, or in one of them, or in two, and so on up to disagreeing in all 1024. A run that includes both ends contains 1024 and also contains zero, which is 1025 distinct distances rather than 1024. The zero is the easy one to lose and it is a real outcome: two identical codes.

So the entire corpus is bucketed into 1025 similarity levels, and those levels are all the resolution the first stage has. Fifty million documents spread evenly across 1025 buckets would put an average of 48,000 in each. The spread is not even, since the distribution of distances is concentrated into a narrow band of levels, so occupancy in the busy middle levels runs far above that average and occupancy at the top of a query's ranking, out in the sparse tail, runs far below it. Halvorsen measured 3,100 documents sharing the same Hamming distance as the true rank-40 document for their median query — small against the 48,000 an even spread would give, and enormous against the forty ranks it is meant to be resolving. Stage one cannot order within a bucket; it returns whichever members of the tied bucket its graph traversal happened to reach, and the tie-breaking is effectively arbitrary. Widening the oversample is how you buy your way past ties, which is why the recall column climbs so steeply between 1x and 10x.

The general form of that is the belief this section exists to break. The resolution of the first stage is fixed by the width of the code and by nothing else: 1024 bits admit 1025 distances whether the index holds a thousand documents or fifty million. Doubling the corpus therefore doubles the documents per level and leaves the number of levels where it was, so a binary first stage that was comfortably precise at ten million documents can stop being precise at fifty million without a single thing about it changing. The defence that feels solid — the codes are centred, the kernel is correct, recall was measured and was fine — names properties of the code, and the ties are a property of the code against a corpus. One of those two grows and the other does not.

The second consequence is architectural. A metadata filter applied after retrieval interacts badly with an already-oversampled first stage, because the filter multiplies the required width. Halvorsen's marine-claims filter keeps 6% of documents, so a final list of ten needs roughly 170 surviving candidates from stage one at 10x oversampling, which means fetching around 2,800 ids before filtering. The last step of that is a division worth doing yourself: a filter that keeps 6% passes about one document in seventeen, so arriving at 170 survivors means starting with roughly seventeen times as many, and 170 times seventeen is a little under three thousand. Pre-filtering inside the index avoids this and requires the store to support filtered graph traversal over a binary index, which not all of them do. Filtering during traversal means the graph only ever visits eligible documents, so a request for a hundred candidates returns a hundred eligible ones and the multiplier disappears.

The float vectors did not go away#

The claim of a 32-fold reduction describes the search index. The system stores 128 bytes per document in the binary index and, in Halvorsen's build, another 1024 bytes per document in the int8 rescore store, for 1152 bytes against the 4096 bytes of the float32 index it replaced. That is a factor of 3.6 on total bytes. Both ratios describe the same system and differ only in the denominator: 4096 over 128 is the thirty-two the headline quotes, dividing by what sits in the search index, and 4096 over 1152 is 3.6 to the nearest tenth, dividing by everything the system has to keep somewhere.

Rescoring against float32 rather than int8 would make it 4224 bytes, which is more storage than the uncompressed index used. That sentence is worth taking apart, because the arithmetic in it settles a general case rather than this one. 4224 is 128 plus 4096, and the amount by which it exceeds 4096 is 128 exactly, which is the binary index itself. It could not have been anything else, since keeping the float32 vectors and adding a binary index beside them adds the binary index's bytes and removes none of the float32 ones. Written with a width instead of a number: a float32 vector of some size carries a binary code one thirty-second of that size, and a size plus one thirty-second of itself exceeds the size it started from for every positive size there is. A binary first stage over a float32 rescore store is a pure addition at any corpus size and any dimension count, so whatever it buys has to be bought as latency and can never be a storage saving.

The graph is a further omission from the ratio. An HNSW index with M=32 stores up to 64 neighbour ids at the base layer and a handful more above it, which at four bytes per id is around 264 bytes per document, or 13.2 GB across the corpus. That structure is identical whether the vectors it points at are 4096 bytes or 128, so in the float index it was 6% of the resident footprint and in the binary index it is twice the size of the vectors themselves.

Those two descriptions are one number held against two denominators. The numerator is 13.2 GB in both: against 204.8 GB of float vectors plus the graph's own bytes it is 6%, and against 6.4 GB of binary codes it is a little over two times. Per document it is the same statement, since 264 bytes against 4096 plus 264 is that same 6% and 264 against 128 that same little-over-two. The numerator does not move, because the number of neighbour ids a graph stores is a function of M and the document count and has nothing to do with how wide the vectors at the nodes are.

That invariance is the belief worth naming, because it survives being measured. Compressing the vectors thirty-two-fold feels like compressing the index thirty-two-fold, and the tempting part is that the compression genuinely is thirty-two-fold on what it was applied to; the ratio answers a narrower question than the one being asked. The graph is the quantity that stays constant while the dangerous property varies, so every successive compression of the vectors makes it a larger share of what remains, and the same 264 bytes that were a rounding error become the dominant term. Past a certain compression level you are no longer optimising vector storage at all, and the next thing to attack is the graph — lower M, a flat IVF index over the binary codes, IVF being the inverted-file scheme that groups vectors into clusters and scans only the few clusters nearest the query, or no index at all if a linear Hamming scan over 6.4 GB at 30 GB/s of memory bandwidth is fast enough, which for a corpus this size it very nearly is. That last option is one division: 6.4 GB read at 30 GB/s is a little over two tenths of a second of pure bandwidth, too slow for an interactive query and close enough that a smaller corpus or a narrower code would remove the graph from the bill entirely.

The economics still work, and they work for a reason that has to be stated in the right units. The binary index is the part that must be resident in memory and traversed thousands of times per query: 6.4 GB for fifty million documents, against 204.8 GB for the float index. The rescore store is read a few hundred times per query at known ids, which is a workload NVMe serves well and object storage serves badly. Halvorsen's memory-optimised instances cost roughly $4.80 per GB-month of RAM and their NVMe volumes $0.09 per GB-month, so moving 200 GB out of RAM and 51 GB onto disk was the saving, and it had nothing to do with the total byte count.

The right units are that price ratio rather than the bytes. RAM against NVMe is more than fifty to one per gigabyte-month here, so one gigabyte taken out of memory pays for more than fifty gigabytes added to disk, and a change that looks close to break-even in bytes is a large saving once each side is multiplied by what its bytes cost. A team whose float index already lived on disk with mmap gets a much smaller win, because the expensive side of that ratio was never being used. A team whose rescore store would have to be S3 gets a latency disaster: 400 individual GETs at 25 ms, even at 64-way concurrency, is 156 ms added to every query.

That last figure is the NVMe calculation with two of its three inputs changed. Both are a count of reads, divided by how many can be outstanding at once, times the cost of one read. The count stayed at four hundred. The concurrency doubled from thirty-two to sixty-four, which halves the waves and helps, so four hundred requests become six and a quarter waves and six and a quarter waves at 25 ms each is the 156 ms. The cost of a single read went from 90 µs to 25 ms, a factor of a few hundred, which does not help at all. Storage choice enters through one term of a three-term product, and it is the term with the largest range.

Where the two-stage shape does not fit#

At small corpus sizes the whole apparatus is overhead. A million 1024-dimension float vectors is 4 GB — the same width-times-count arithmetic with a much smaller count — and 4 GB fits in RAM on an ordinary machine. Exact brute-force search over them takes about 40 ms single-threaded, slower than HNSW and perfectly acceptable for many internal tools. The complexity of two stages, a centre vector, a calibration hash and an oversampling parameter buys nothing there. The two-stage design answers a corpus that does not fit in memory at full precision, and where that premise is false so is everything built on it.

High write rates are the other poor fit, and the mechanism is a short chain. Every document needs its bits in the binary index and its int8 vector in the rescore store, so one logical write is two physical writes to two stores. Stage one can return an id the moment the binary write lands, and stage two then resolves that id against the rescore store; if the second write has not landed the lookup misses, and the candidate is dropped or the query errors depending on how the fetch was written. Those two writes must therefore be transactionally consistent, which two independent stores do not give you for free. Systems that update embeddings continuously end up building reconciliation for a consistency problem the single-index version did not have, because a single index has one write and no window in which half a document exists.

There is also a version of this that is simply better for some corpora, which is int8 without a second stage. The int8 index from chapter 4, where scale calibration and the choice of distance kernel were what decided recall, reached 0.99 of float recall@10 at 1024 bytes per document, with one store, one kernel and no oversampling parameter. Against binary-plus-int8-rescore at 1152 bytes and 0.968, it wins on quality and on bytes; it loses on RAM residency, since 51 GB of int8 index is still eight times the binary index's 6.4 GB footprint. Which of those matters is a question about the shape of the bill rather than about retrieval, and the bill is rarely shaped the way the dimension ratio suggests.

The two-stage design is what the published binary numbers are numbers for, and reading them as numbers for a binary index alone is how a careful build comes in nine points short of a claim nobody was lying about. Stage one finds and stage two orders, which fixes what each can be blamed for: the recall you can ever reach is set by how wide a net stage one casts, and the ordering inside that net is set by the precision stage two reads. The oversampling factor connects them, and it is a decision about how much fetch bandwidth to spend rather than a default to leave alone.

Everything the design saves it saves in one place — the bytes that have to be resident in memory and walked thousands of times per query — and nowhere else. The float or int8 vectors still exist, still cost, and are now read four hundred times a query from wherever they were put, and the graph did not move at all. Whether the trade is worth making is settled by what a byte costs in each of the two places it can sit, which is a division to do against your own invoice rather than against a compression ratio, and it is the accounting the next chapter does line by line.