Token Search

Looking for TL;DR? Check key takeaways

In Token-Native Storage I argued that if agents are the biggest readers and writers of your database, you should store text the way they read it: as BPE token IDs, not UTF-8 bytes. But then while looking at the interface I proposed, I had a realization that it looks very similar to text search engines and they also tokenize the data per-language to keep it searchable. Instead of Lucene's English analyzer turning "running" into the stemmed word run and giving that an ID, what if the index terms were the model's own token IDs, representing it as run + ##n + ##ing? How does that do on BM25 — and could it beat existing solutions in some way?

I built it and benchmarked it against plain BM25. The short version: the naive way is badly broken, a normalized version lands within noise of a standard word analyzer — which turns out to be the same idea as character n-gram retrieval from 2004, so the quality isn't the story. The real payoff shows up in other languages, where a BPE tokenizer replaces a per-language word segmenter and sometimes beats it.

Why this might work at all

A BM25 inverted index maps a term to a postings list. In Lucene the term is an English word after an analyzer runs: lowercase, split on non-word characters, drop stopwords, Porter-stem. BM25 then scores documents by how many rare query terms they contain, saturated by term frequency and length.

Nothing in BM25 requires the term to be a word. It just needs to be a hashable symbol whose document frequency means something. So the swap is: run the BPE tokenizer over the text, and use each token ID as a term. "storage" is one token; "tokenization" is two (token + ization); the whole index vocabulary is now the model's fixed 50k–200k tokens instead of an unbounded pile of English words.

If this reaches parity with word-BM25, lexical search inherits the token-native benefits: a bounded fixed vocabulary, no language-specific analyzer to configure, and the same representation the model already reads and writes.

The naive version is broken

Here's the first thing I tried. It fails in an instructive way — the fix falls right out of it.

BPE is space- and case-sensitive. The document "The cat sat" tokenizes to [The][ cat][ sat] — note the leading-space tokens. The query "cat" tokenizes to [cat], a different token ID than [ cat]. So a query for cat never matches the cat in the document. Same problem with Cat vs cat. The term that should connect query and document tokenizes to two different integers depending on where the word sat in the sentence.

Across 12 NanoBEIR datasets (599 queries), naive token-BM25 loses −0.10 to −0.11 NDCG@10 versus a plain word analyzer — it loses on every one of the 12 datasets, well outside the confidence interval. Tokenizing your text and indexing the raw IDs is strictly worse than doing nothing clever.

The fix: normalize before you tokenize

The mismatch is entirely about inconsistent tokenization between query and document. So make it consistent: lowercase the text, split it into words on word boundaries, and encode each word in isolation with a fixed leading space — enc.encode(" " + word). Now "cat" produces the exact same token IDs whether it's a one-word query or buried mid-sentence in a document. I bag all the resulting subword tokens and run ordinary BM25 over them.

That one change moves naive's −0.11 gap to essentially zero. Here's the full ladder, macro-averaged over the 12 datasets. Toggle the tokenizer on the right:

Three things in that chart matter:

1. Normalized BPE (green) sits right on top of plain word-BM25 (gray), for all three tokenizers.
2. Naive BPE (red) is far below everything — the space/case break.
3. The purple "word-tuple" bar is exactly equal to plain word-BM25. That's a control: instead of bagging subwords, I keep each word as a single term equal to the tuple of its token IDs. Keying BM25 by token-ID-tuple instead of by string changes nothing — proof that the token-ID representation is irrelevant, and the only thing that moves quality is whether you decompose words into subwords or not.

(The cyan char-4-gram bar sits right next to normalized BPE too — hold that thought, it matters later.)

Is "within noise" actually parity?

I want to be careful here, because "the bars look the same" is not a statistical claim. Parity is an equivalence claim, and absence of a significant difference is not evidence of equivalence. So I ran a cluster bootstrap (resample datasets, then queries within each — respecting the fact that queries aren't independent, they clump into datasets) on the per-query NDCG@10 delta, with a pre-registered equivalence margin of ±0.01.

Normalized BPE is statistically indistinguishable from plain word-BM25: the confidence interval is tight and straddles zero. It's not tight enough to pass a strict ±0.01 equivalence test, so I'll call it "on par / within noise," not "proven equal." Against the stronger Porter-stemmed analyzer it's about −0.02 behind — not significant, but it loses on 10 of 12 datasets, so I won't pretend that's parity either. It's a hair behind a real stemmer. Note that word_en here uses NLTK's English stopword list and Porter stemmer — a genuinely strong Lucene-EnglishAnalyzer-style baseline, not the handicapped lowercase-only one.

Why does normalized BPE match a word analyzer?

Because bagging subwords gives you stemming-like matching for free. tokenization and tokenize share the token subword; running and runner share run-ish pieces. Two words a Porter stemmer would collapse to one stem tend to share a subword token, so BM25 sees partial overlap where a plain word index sees none.

I checked this directly instead of assuming it: across the corpus vocabulary, two words in the same Porter-stem class share a subword 68–112× more often than two random words — but only ~4–5% of the time in absolute terms. So it's a real but partial stemmer, which is exactly what the retrieval numbers show — indistinguishable from plain word, a hair behind Porter.

This is char n-gram retrieval, and I should say so

Here's the uncomfortable part. Look back at the ladder chart: the char 4-gram bar (cyan) behaves exactly like normalized BPE — within noise of plain word, a hair behind the stemmer, on every comparison. Character n-gram indexing does the same subword decomposition, and McNamee & Mayfield showed in 2004 that character n-grams recover morphological matching without a stemmer, especially across languages. So "BPE subwords give free stemming" is a 20-year-old result about subword IR, not something new about BPE.

Which means the retrieval quality is not the reason to do this. On English, token-BM25 is a slightly-worse-than-stemming, exactly-like-char-n-grams lexical index. If that were the whole post, the honest conclusion would be "use a stemmer."

The reason to care is different, and it's two things:

• A BPE vocabulary is a language-agnostic analyzer you already have. No stopword list, no stemmer, no per-language segmenter to configure — the tokenizer is the analyzer, and it's the same one for every language.
• It's the same vocabulary the model reads and writes. If you already store payloads as token IDs (token-native storage), the lexical index and the stored text share one representation.

The first of those is testable, and it's where this stops being a tie. But before that, one more question about the tie itself.

The recall ceiling: a wider net, ranked worse

Everything above is measured at rank 10. A colleague pushed back: maybe subwords cast a wider net — retrieve more of the relevant documents, just rank them worse — so @10 washes out even if deep recall differs. It's a fair hypothesis, because subword matching can connect a query to a document that share no whole word but do share a fragment. So I measured recall at increasing depth, and reachability: the fraction of relevant documents that get any nonzero score, independent of rank.

Two clean results. Normalized BPE tracks plain word at every depth — the curves sit on top of each other, so it has no wider net; a word-aligned subword index reaches the same documents a word index does. Char 4-grams are the exception, and they behave exactly as the hypothesis predicts:

Char 4-grams reach 4.8% of relevant documents that word-BM25 scores a hard zero, and miss none that word finds — a strictly wider net (reachability 0.97 vs 0.92). But their Recall@10 is lower (0.595 vs 0.613): the extra documents they reach land deep in the ranking, lifting Recall@1000, not the top 10. Wider net, worse ranking — exactly the predicted trade. The spurious fragment-matches that widen the net also add noise near the top.

Note the contrast with the stemmer: word + Porter has the best Recall@10 but the lowest reachability (0.889). It's a precise net — it collapses genuine morphological variants and nothing else. Char n-grams are a noisy net — they reach the most documents, but many of the extra ones are junk. Two opposite ways to widen recall.

The implication is the useful part: if you want the wider net, go finer-grained than BPE (char n-grams), accept that ranking degrades, and treat it as a candidate generator feeding a reranker, or fuse it with word-BM25 — not as a drop-in BM25 replacement. Word-BM25 structurally caps at 0.922 reachable here; it cannot retrieve the ~8% it scores zero, no matter how good the reranker. (Caveat: NanoBEIR pools are 2–5k documents, so Recall@1000 is close to reachability; treat these as directional.)

The real payoff: when a word analyzer needs a language pack

Everything above splits text on \w+ before tokenizing. That regex is a word segmenter — and it only works for languages that put spaces between words. Chinese doesn't. Thai barely does. And even for a spaced language, a \w+ split with no stemmer leans on morphology the analyzer doesn't know. This is exactly where a word analyzer reaches for a language-specific tool and a BPE tokenizer doesn't.

I ran the same experiment on MIRACL dev sets (self-contained retrieval pools built from the inline positive/negative passages). For Chinese I added jieba, the standard Chinese segmenter, as the "proper analyzer" baseline. These are single dev sets scored on judged-passage-only pools, so treat the numbers as directional — I didn't bootstrap them the way I did the English results. Toggle the language:

The Chinese result is the whole argument in one bar chart:

• \w+ word tokenization collapses to 0.0117 NDCG@10. With no spaces, the regex swallows entire runs of characters into single terms, so queries and documents almost never share a term. Word-BM25 simply does not work on Chinese without a segmenter.
• jieba fixes it to 0.40 — that's the cost of a language-specific dependency.
• GPT-4o's o200k tokenizer beats jieba with zero language configuration. Normalized o200k hits 0.53 (13 points over jieba); even the fully config-free naive o200k, the version that comes straight off the model with no \w+ split at all, gets 0.49 — still 9 points over jieba. BPE segments Chinese into shared subwords the same way it does English, and a good multilingual vocabulary does it better than the dedicated segmenter here.

Three honest caveats the other languages surface:

On Thai, BPE does not win — char 4-grams do. Thai has enough embedded spaces that the plain \w+ word baseline already reaches 0.57; char 4-grams top the table at 0.62, and naive o200k (0.56) merely ties the word baseline. So the "BPE beats the analyzer" headline is a Chinese result, not a universal one — on a language where word tokenization half-works, BPE is a wash and classic char n-grams are better.

Which token variant wins flips by language. On English the \w+ pre-split (normalized) is essential; on Hindi and Thai it hurts — naive:o200k gets 0.55 on Hindi vs normalized's 0.27. The normalization I added to fix English is a word-segmenter in disguise, and forcing word boundaries on a script that lays them out differently is worse than letting BPE segment the raw stream. Why does naive win so hard on Hindi, a spaced language, even over the word baseline (0.55 vs 0.39)? Devanagari packs heavy inflection onto each word; BPE breaks those inflected forms into shared subwords the way it does English morphology, so it matches variants the word index treats as unrelated. The config-free method is naive BPE with a multilingual tokenizer — which is also, conveniently, exactly what the model emits.

Tokenizer coverage is decisive. r50k has no Devanagari or Thai merges, so it falls back to bytes and collapses — 0.007 NDCG@10 on Hindi, 0.04 on Thai. This is the exact failure I hit with r50k on Hindi in the storage post. o200k, trained on a multilingual corpus, handles both fine. If you're going to search on token IDs across languages, the tokenizer choice is not cosmetic.

Note that none of this needs a new engine. A sparse-vector index — Qdrant's BM25 / sparse API, or Lucene's terms-as-bytes — already keys postings by arbitrary integer dimensions. The token ID is the sparse dimension, so token-BM25 drops in with no changes: it's the same vocabulary SPLADE puts learned weights on, just with BM25 weights instead.

What about latency?

Not a selling point, and I'll be precise about what I did and didn't measure. Analyze cost is a wash — one short query is 2µs for words, ~20µs for BPE, and indexing runs >4k docs/s/core either way. But analyze cost isn't query latency, and I didn't measure the part that differs at scale: token documents run 1.2–1.4× longer with higher-DF subword terms, so postings traversal costs more per query, and my ~1.5k-doc Python BM25 can't see it. Treat "search is a wash" as unproven above small scale. And "the model gives you the tokens for free" only holds for naive tokenization, which retrieves badly. The honest win is config, not milliseconds: no per-language stemmer, stopword list, or segmenter to maintain.

Limitations

• This doesn't beat BM25 on quality — it matches it (English) or replaces a segmenter (multilingual). To actually beat BM25 you need learned weights: SPLADE, on essentially this same token vocabulary. Token-BM25 is its unweighted floor.
• It's char n-gram IR (known since 2004). BPE's only novelty is reusing the model's own analyzer.
• Small, directional evaluation. NanoBEIR is 50 queries/dataset and the MIRACL pools use judged passages only; I used an exact-float Python BM25, not a production engine, so absolute numbers would shift.
• k1/b were fixed at (1.5, 0.75) for both sides. I didn't tune per-representation, on purpose — but token docs are longer, so tuning could move either side ±0.01–0.02, the size of the whole English effect.
• The English normalization is a hidden analyzer. Pre-splitting on \w+ re-introduces the language-specific step the pitch removes; the config-free story needs naive tokenization plus a multilingual vocabulary, at a small English quality cost.

Key Takeaways

• Naive token-BM25 is broken: BPE's space/case sensitivity makes a query word tokenize differently than the same word in a document, costing −0.10 to −0.11 NDCG@10 on every one of 12 NanoBEIR datasets.
• Normalized token-BM25 (encode each lowercased word with a fixed leading space) lands within noise of a standard word analyzer, and about −0.02 behind a Porter-stemmed one. A word-tuple control equals word-BM25 exactly, so the token-ID representation is irrelevant — only subword decomposition matters.
• The mechanism is free but partial stemming: same-stem words share a BPE subword 68–112× more than chance, and gains correlate with a real stemmer at r = 0.35. This is character n-gram retrieval, known since 2004 — so the quality is not the story.
• The payoff is multilingual and config-free: on Chinese, \w+ word tokenization collapses to 0.01 NDCG@10 while GPT-4o's tokenizer beats the jieba segmenter (0.53 vs 0.40) with zero language setup. Caveats: on Thai it only ties word-BM25 (char n-grams win), the best token variant flips by language, and r50k dies on Devanagari/Thai where o200k holds.
• Finer subwords buy recall, not ranking: char 4-grams reach 4.8% more relevant documents than word-BM25 scores nonzero, missing none (reachability 0.97 vs 0.92) — but rank them deep, so Recall@10 drops. A wider but noisier net, best used as a candidate generator + reranker or fused with word-BM25, not a drop-in.
• To actually beat BM25, add learned weights (SPLADE) on this same token vocabulary. Token-BM25 is the unweighted floor; its real value is being one representation shared with token-native storage and the model itself.

Acknowledgements

Benchmarks use tiktoken, ranx, NanoBEIR, MIRACL, and jieba. The char-n-gram framing is due to McNamee & Mayfield (2004).

Citation

@misc{kumar2026tokensearch,
  author       = {Kumar Shivendu},
  title        = {Token Search: BM25 over BPE Token IDs},
  year         = {2026},
  url          = {https://www.kshivendu.dev/blog/token-search},
  note         = {Blog post}
}