When the Vectors Live in a Bucket

The cheapest place to store a vector is also the worst place to search one. Object storage (S3, R2, GCS) gives you durable bytes at around two cents a gigabyte with effectively no ceiling, but you reach them one HTTP request at a time, and every request is tens of milliseconds and a sliver of a cent. A vector database wants the opposite: score an incoming query against millions of stored vectors and return the nearest handful before a human notices the wait. Bytes that are cheap to keep and slow to reach, against a search that wants all of them at once. That tension is the reason turbopuffer is interesting, and it's the whole subject of this post.

I should be exact about what is mine here, because most of it isn't. I did not build turbopuffer, and I did not write this database from scratch. I started from VecPuff, Karan Janthe's turbopuffer-inspired learning database, and forked it into something I call OpenVector. VecPuff handed me the skeleton, and it's a good one: writes batched into a log on S3, a background compactor that folds the log into indexed segments, an SPFresh index for approximate search, and a local cache. Karan wrote up that journey in his own post, and it's the right thing to read first.

What I added sits on top of that skeleton, and it answers one question: when the vectors live in a bucket, how do you search them without dragging them across the network on every query? The rest of this is that answer.

Why a naive query touches every vector#

The honest baseline for nearest-neighbor search is brute force: score the query against all N vectors, keep the top k. It's exact and it's simple, and on object storage it falls apart, because "score against all N" means reading all N vectors, which means a pile of GETs per query. Karan measured his early version doing fifty or more GETs per query. At a million vectors that arithmetic does not survive contact with a pricing page.

The usual fix is an approximate index that groups vectors into clusters and only searches the promising ones. That's what SPFresh gives us. Vectors are grouped into postings around a centroid, and a query ranks postings by how close their centroid is, then searches only the nearest few.

That cuts the work from "all N vectors" to "a few postings' worth". It does not solve the real problem, though, because a posting is still a blob of full-precision vectors sitting in S3, and searching the nearest few still means fetching them. The index tells you which bytes to read. It does not make the bytes cheap.

One bit per dimension#

Here is the move. Alongside every posting I keep a second, tiny copy of its vectors, quantized down to a single bit per dimension. The bit is the sign of each component after subtracting the posting centroid: positive is a 1, negative is a 0. A 128-dimension float vector is 512 bytes; its sketch is 16 bytes. That's the RaBitQ encoding, and the compression runs 16 to 32 times depending on whether you compare it against 16-bit or 32-bit floats.

// one bit per dimension: the sign of each centered component
for (i, &val) in residual.iter().enumerate() {
    if val >= 0.0 {
        bits[i / 64] |= 1u64 << (i % 64);
    }
    norm_sq += val * val;
}

The reason one bit is worth anything: in high dimensions, the Hamming distance between two sign-bit codes tracks the angle between the original vectors. XOR the two bit strings, count the set bits with a popcount instruction, and you have an estimate of how far apart the vectors are, computed in a handful of CPU cycles over 16 bytes instead of a network round trip over 512.

let hamming = bitwise_xor_popcount(&query.bits, &data.bits);
let agreement = 1.0 - 2.0 * hamming as f32 / d;   // +1 identical, -1 opposite
let estimated = 1.0 - agreement;                  // cosine distance
let error_margin = 2.0 * (2.0 / d).sqrt();        // tighter as d grows

RaBitQ's real contribution is not the estimate, it's the error bar around it. Every estimate arrives with a lower and an upper bound, and the bound tightens as the dimension grows, shrinking like one over the square root of d. That bound is what makes the next step safe instead of merely fast.

Guess with the bits, pay for the vector#

The estimate on its own would just be a faster, sloppier search. The bounds turn it into an exact search that reads almost nothing. The query holds a running top-k, and the worst distance in that top-k is a live threshold. For each vector in a posting I compute the 1-bit estimate and its lower bound. If even the lower bound is worse than the current worst top-k entry, that vector cannot belong in the answer, so I drop it without ever reading its full form.

// the sketch says the closest this vector could be is still
// worse than our current worst top-k: never read the full vector
if est.lower_bound >= current_worst {
    counters.rows_pruned += 1;
    continue;
}
rerank_indices.push(doc_idx);

Only the survivors, the vectors whose bounds still overlap the running top-k, get their full-precision vector loaded and their exact distance computed. The comment I left in the code states the intent plainly: shift the bottleneck from bandwidth-bound to compute-bound. The fastest read from a bucket is the one you skip.

There's a cheaper cousin of the same trick on the fallback path, for when a posting's sketch isn't in memory. Instead of the whole vector, compare only the first sixteen dimensions, then add a Cauchy-Schwarz term that accounts for everything you haven't looked at. If that partial lower bound already exceeds the worst top-k, skip the remaining dimensions too. Same idea on a different axis: prune on a prefix of one vector instead of a bitwise sketch of all of it.

Where the full vectors actually live#

"Load the full vector" is carrying a lot of weight in that sentence, so here is what it means. The data sits in a cache hierarchy with object storage at the bottom, and each tier holds a smaller, cheaper view than the one beneath it.

• L1 keeps the centroids in memory. They're small, and every query reads them to rank postings, so they stay hot.
• L2 keeps the 1-bit sketches, in memory or on local NVMe. This is the tier the guess-first pass reads, and because a sketch is 16 to 32 times smaller than the vector, far more of the dataset fits in the same budget.
• L3 keeps full-precision postings on local NVMe, written atomically with a temp-file-and-rename so a crash never leaves half a posting.
• S3 is the source of truth. A miss at L3 falls through to a GET, and on the way back the posting is written into L3, its centroid into L1, and a freshly computed sketch into L2, so the next query for that region pays nothing.

A residency check walks the tiers top to bottom and returns the first hit. The point of the layout is that the tiers you read on the hot path are the small ones, and S3 is where you go only when everything cheaper has missed.

What the numbers actually say#

Here is the part I'd rather not write, because the design is prettier than my measurements. Everything below is a single node, 128-dimension vectors, and datasets between two thousand and ten thousand rows: toy scale, run from my own machine against real S3.

The brute-force baseline does what it should, recall 1.0 at about 21 ms median for ten thousand vectors. The ANN path is faster, a 2.4 ms median at five thousand vectors, but on that same run recall fell to 0.21, the telemetry reported it reranked 100% of the vectors it considered, and it pruned zero postings. So at this scale the bounds do not bite yet: the probe looked at too few postings and missed most of the true neighbors, and the sketch never got the chance to skip a full-precision read. The quantize-and-bound machinery is a design intent I have not yet shown winning on a dataset large enough for it to matter.

The measurement that would settle the whole idea, S3 bytes and GETs per query, I'm not even capturing yet: the server-side byte counters are still null in every benchmark file. Until they exist, "reads almost nothing" is an argument about the code, not a result.

So this is a learning project, and it's the wrong choice for anything real. If you need a vector database in production, the honest recommendation is turbopuffer itself, or pgvector if you already run Postgres, or a dedicated engine. What a fork like this is good for is understanding, by building it, why turbopuffer's architecture is shaped the way it is.

The trade, restated#

Object storage does not make search cheap. It moves the cost from keeping bytes to reaching them, and it charges by the request instead of by the gigabyte of RAM. Once the tax is on reaching bytes rather than storing them, the game becomes arithmetic on how few bytes you can read and still be right. One bit per dimension, a bound tight enough to trust, and a running top-k to measure against: that's the arithmetic, and the cache hierarchy is where it gets to be physical. Whether my version of it holds at a hundred million vectors is the thing I still have to prove, which is why the benchmark files stay in the repo where they can embarrass me.