Why BM25 queries with more terms can be faster (and other scaling surprises)

Summary

Why BM25 queries with more terms can be faster (and other scaling surprises)January 07, 2026•Adrien Grand (Engineer)BM25 full-text search has very different scaling characteristics than vector search. Vector search latency is generally a function of vector dimensions, top-k, the size of the dataset, and the presence of filters. BM25 latency, on the other hand, also varies a lot by query, and in some surprising ways: Sometimes adding a new term to a query actually makes it faster The fastest query at top_k=10 may not be fastest at top_k=10000 This post discusses what I learned modeling BM25 query latencies across varying term counts, document counts, and top_k values. Background turbopuffer implements BM25 full-text search by indexing text data into an inverted index, a data structure that maps unique terms to the list of document IDs that contain these terms, which are called “postings”. term posting list ┌────────────┐ ┌───┬───┐ │ pufferfish ├───────────▶│ 1 │ 2 │ // "pufferfish" appears in few documents └────────────┘ └───┴───┘ ┌────────────┐ ┌───┬───┬───┬───┬───┐ │ fish ├───────────▶│ 1 │ 2 │ 4 │ 6 │ 9 │ // appears in more documents └────────────┘ └───┴───┴───┴───┴───┘ ┌────────────┐ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬─ │ to ├───────────▶│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ ••• // apears in many └────────────┘ └───┴───┴───┴───┴───┴───┴───┴───┴───┴─ ┌────────────┐ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬─ │ be ├───────────▶│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ ••• └────────────┘ └───┴───┴───┴───┴───┴───┴───┴───┴───┴─ ┌────────────┐ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬─ │ or ├───────────▶│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ ••• └────────────┘ └───┴───┴───┴───┴───┴───┴───┴───┴───┴─ term posting list ┌────────────┐ ┌───┬───┐ │ pufferfish ├─▶│ 1 │ 2 │ └────────────┘ └───┴───┘ ┌──────────┐ ┌───┬───┬───┬───┐ │ fish ├───▶│ 1 │ 2 │ 6 │ 9 │ └──────────┘ └───┴───┴───┴───┘ ┌────────┐ ┌───┬───┬───┬───┬───┬── │ to ├─────▶│ 1 │ 2 │ 3 │ 4 │ 5 │••• └────────┘ └───┴───┴───┴───┴─...