How full-text, BM25, and vector search actually work
Search looks opaque from outside, but most of it comes down to three plain ideas, with Infino’s implementation as the running example. The numbers at the end follow from those choices: 6.8 ms for text, 10.4 ms for vectors, 13.0 ms fused, all warm and reading files on real object storage.
There are three modes. Full-text search finds documents by their words, vector search by meaning, and hybrid search combines the two. They rank by different rules and fail in different ways, and the engineering lives in the seams.
Full-text search and the inverted index
Full-text search starts by turning text into terms. We tokenize each document into words and lowercase them, so Rust and rust become one token.
The core structure is the inverted index. Instead of storing each document’s words, you store, per term, the documents that contain it. That is a posting list. Alongside each document id it records the term frequency, how often the term occurs there.
A query looks up its terms, walks the matching posting lists, and scores each document it lands on. It is fast because you never touch documents that share no words with the query. Two structures set the speed: how you store the term dictionary, and the lists.
For the dictionary, Infino uses an FST, a finite-state transducer: a compact, sorted map from term to value that shares prefixes, so search, searching, and searchable reuse the same leading states. It is far smaller than a hash map of raw strings and supports prefix lookups.
Posting lists are delta-encoded: we store the gaps between consecutive document ids rather than the ids, since smaller numbers pack tighter, then bit-pack them into fixed 128-document blocks. A skip table stores, per block, its last document id, its byte offset, and block-max: an upper bound on the BM25 score any document inside could contribute. Blocks decode independently, so a scorer chasing the top-k can skip a whole block by byte offset, without decoding it, whenever its block-max provably cannot enter the results.
The FST buys two more things for almost nothing. A term in exactly one document gets no posting list: its single (doc_id, term-frequency) pair packs into the FST value, so the lookup returns the answer directly. And a single-term count query reads the document frequency, the number of documents containing the term, straight from the FST in constant time.
BM25, from intuition to formula
Now you rank the matching documents. The standard function is BM25, three intuitions made precise.
First, more mentions of your term mean more relevance, but with diminishing returns: one occurrence to two matters more than twenty to twenty-one. Second, a rare term is a stronger signal than a common one, so matching photosynthesis tells you more than matching the. Third, a long document should not rank highly just because its length gave it more chances to contain the term.
Each intuition becomes a factor we multiply. Inverse document frequency rewards rarity: idf(N, df) = ln(1 + (N - df + 0.5) / (df + 0.5)), where N is the document count and df the term’s document frequency. Length normalization is lengthNorm = 1 - b + b * docLength / averageDocLength, which is 1 at average length and rises for longer documents. The full term contribution is idf * tf * (k1 + 1) / (tf + k1 * lengthNorm). Here k1 controls how fast extra occurrences stop helping, and b controls the length penalty. We use the usual defaults, k1 = 1.2 and b = 0.75.
That is one division and a few multiplies per matching term per document, which adds up over millions of documents. Two choices keep it cheap. When the file opens we precompute each document’s length-normalization term once, so at query time it is a lookup. And we score four term-cursors at once with SIMD f32x4 lanes, four documents in lockstep, collapsing the hot loop to a single fused multiply-add.
One wrinkle lives here. A corpus spans many files, and each scores its documents from its own local N and df; we merge the per-file top-k by score. This is the classical sharded-BM25 approximation: a rare term in a small file can out-score the same term in a large one, so exact score order across files can wiggle. But for a top-k of ten or more over balanced files, the returned set still converges on the global answer even as its order shifts. A globally exact idf would cost a corpus-wide df table or a second pass, not worth it. Our oracle tests check set membership at k equal to ten against a single-file ground truth.
Choosing an algorithm per query
The fastest way to walk the posting lists depends on the shape of the boolean query, and the right thing to test is document frequency, not the score upper bound. A two-term OR with one rare term is a very different problem from a ten-term OR where every term is common.
So we route by query shape. A two-term OR uses WAND, which uses each list’s score bounds to leap over documents that cannot make the top-k, but only when one posting list is at least 16 times shorter than the other by document frequency, k is at most 128, and there is no negation. That short list is the anchor WAND pivots on to skip the long one; two comparable lists give it nothing to skip. A multi-term OR of three or more terms with no dominant term uses a windowed union scorer: it accumulates every term’s contribution into a fixed 4096-document window, one at a time, then drains each into the top-k heap. Everything else uses Block-Max MaxScore, the block-skipping scorer above.
On our benchmark a 10-term OR query dropped from 32 ms to 6.8 ms once we added the windowed union scorer. When no single term dominates, a document-at-a-time MaxScore has nothing to prune with: the bounds are all similar, so it cannot skip and scores the entire union of the lists. The windowed scorer stops paying that tax.
Vector search and approximate nearest neighbors
Full-text search matches words; vector search matches meaning. An embedding model maps text to a point in a high-dimensional space, so texts with similar meanings land near each other. Semantic search is then a nearest-neighbor query: embed the query, find the closest document points.
Exact nearest-neighbor search compares the query to every vector, O(N times dimension) work. At ten million vectors of dimension 384 that is far too slow per request. So we approximate, trading a tiny loss of accuracy for a large gain in speed.
Infino uses IVF, an inverted file. We run k-means clustering once to partition the space into cells, each summarized by a centroid, its average point. At query time we compare the query to the centroids, pick the nearest few cells, and search only inside those. The count of cells probed is nprobe, the main dial trading recall for latency. The candidates are then reranked.
Probing fewer cells is only half the saving. The other half is making each comparison inside a cell cheap, so we quantize. RaBitQ reduces each vector to one bit per dimension, keeping only each coordinate’s sign. A 384-dimensional vector becomes 384 bits, or 48 bytes, against the 1,536 bytes of its fp32 form: 32 times fewer bytes per candidate.
A naive sign bit estimates distance poorly, because variance spreads unevenly across dimensions. So first we apply a structured random rotation, built from repeated sign-flips and Walsh-Hadamard transforms, which spreads variance evenly and costs O(dimension times log dimension) rather than the O(dimension squared) of a dense matrix. The 1-bit codes then give an unbiased estimate of the rotated dot product; and because the rotation is orthogonal it leaves the dot product unchanged, so that estimate also estimates the original similarity.
Only the small candidate set that survives the coarse scan is reranked, using the full-precision vectors or the default 8-bit-plus-8-bit-residual codes, fetched at that point and no earlier.
Accuracy survives all of this. On a 10-million-vector table of dimension 384 on real S3, recall@10 is 0.995 at nprobe 64 with a rerank multiplier of 256, clearing our 0.99 acceptance gate. Recall@10 is how many of the ten true nearest neighbors the approximate search returned. And vector_search comes back in about 10.4 ms warm.
Hybrid search by reciprocal-rank fusion
Text and vector search are good at different things, so the natural move is to run both and combine them. The trap is combining by score. A BM25 score and a cosine distance share no zero and no unit, so adding them means inventing a normalization, which becomes a fragile tuning knob of its own.
Reciprocal-rank fusion avoids this by discarding the scores and keeping only the ranks. Each retriever produces an ordered list, and a document at zero-based rank r contributes 1 / (k + r + 1) to its combined score, where k is a rank-bias constant we set to 60, the value from the original reciprocal-rank-fusion paper. We sum those contributions per document id across the two lists, with a deterministic tie-break for stable results.
A document both retrievers rank highly rises to the top; one ranked deep, or returned by only one retriever, barely moves. The constant k flattens the weighting so the top few ranks do not dwarf everything below, and because we only ever compare rank against rank, we never reconcile a BM25 score with a cosine distance.
Running both retrievers and fusing them, warm hybrid_search comes back in about 13.0 ms at ten million documents: roughly the text and vector costs added together, plus a near-free fusion step.
No phrase index
One deliberate choice carries a real cost. Infino stores no token positions: we record which documents contain a term and how often, but not where the term sits. So there is no phrase index, and no way to ask the index directly for machine learning as an adjacent pair rather than the two words appearing anywhere.
Exact-string match still works, in two passes. A token-AND prune uses the index to find candidate rows that contain all the required tokens. Then we check each candidate’s stored value against the raw query string to confirm the phrase. That is correct, but it does more work than a positional index would, and it makes phrase-heavy relevance, where adjacency and word order carry most of the meaning, a genuine weakness of this design.
The default tokenizer is plain in a second way: it splits on non-alphanumeric bytes and lowercases, but does no stemming and drops no stopwords. So run and running stay separate terms, and a common word carries a posting list rather than being discarded. That keeps behavior predictable and fast, but a stemming, stopword-aware analyzer would score some queries differently. The tokenizer is a trait, so a language-aware one can slot in without touching index code; the shipping default just makes no such transformation.
Where this leaves us
None of these ideas is exotic. An inverted index is a map from terms to lists. BM25 is three intuitions multiplied together. Approximate nearest neighbor is clustering plus a cheap coarse scan and a full-precision rerank. Fusion is addition over ranks. The work is in the details: the FST-packed singletons, the block-max skips, the SIMD scoring loop, the document-frequency routing, and the Hadamard rotation before the 1-bit codes. On ten million documents over real AWS S3, that is 6.8 ms for text, 10.4 ms for vectors, and 13.0 ms fused, warm p50. The code is open source at github.com/infino-ai/infino.