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 as BPE token IDs, not UTF-8 bytes. The interface I proposed looks a lot like a search engine, which also tokenizes text per-language to index it. So instead of Lucene's English analyzer stemming "running" to run and indexing that, what if the index terms were the model's own subword token IDs? How does that do on BM25, and can it beat existing analyzers?

Short version: BM25 on the model's own BPE token IDs matches a Porter-stemmed English analyzer with none of its machinery (no stopword list, no stemmer, no per-language config). Because the tokenizer is the only moving part, the same method beats a dedicated Chinese segmenter with zero setup, one analyzer for every language, on the vocabulary the model already reads, writes, and stores. The one catch: raw tokenization needs a one-line fix (−0.11 NDCG@10 without it), and two small token-native tricks, un-fragmenting words and stemming-by-expansion, close the last sliver to Porter.

The top lane is what a search engine does today: a hand-built analyzer, swapped out per language. The bottom lane is token-native search: one BPE tokenizer for every language, the same one the model already runs. Here's how.

Token IDs as index terms

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), and the whole index vocabulary is now the model's fixed 50k–200k tokens instead of an unbounded pile of English words.

First try: raw token IDs

The simplest thing to try is using raw token IDs, but it has a small problem. BPE is space- and case-sensitive: "The cat sat" tokenizes to [The][ cat][ sat] (leading-space tokens), but the query "cat" becomes [cat], a different ID than [ cat], so it never matches. Same problem with Cat vs cat. Across 12 NanoBEIR datasets, naive token-BM25 loses −0.10 to −0.11 NDCG@10 to a plain word analyzer, on every one of the 12.

The fix: normalize before you tokenize

The problem is inconsistent tokenization between query and document, so make it consistent: lowercase, split on word boundaries, and encode each word with a fixed leading spacethe form BPE learned from running text, where bare words fragment ~15% more and cost a little tail accuracy, like enc.encode(" " + word). Now "cat" gives the same IDs whether it's a query or buried mid-sentence. Bag the subwords, run ordinary BM25.

The index also consolidates. Across the 12 corpora (52k docs) a word analyzer needs 146k distinct terms and keeps growing. Normalizing merges the case/space variants (The/ the/the) down to 48k, capped at the tokenizer's fixed 200k, so no query hits an out-of-vocabulary term. Fewer terms, longer posting lists: average document-frequency climbs 32 → 109.

A query only traverses the posting lists its own terms point to, so where those lists sit is the cost. The chart defaults to posting entries per doc-frequency bucket (the traversal cost). Toggle to distinct terms for the vocabulary shape. Each bar's height is its share, the label is the raw count, and you can hover for example terms in that bucket:

Observations:

1. Char n-grams pile all their cost into one bar. Char bigram puts 90% of its postings (8.6M of 9.6M) in 10k+, 9k terms each spanning nearly the whole corpus. By term count it looks like word (49% vs 53% singletons), but where the postings live is the cost.
2. Word is a pile of singletons. 53% (78k) of its terms appear in one document, lists too short to rank. Subwords are shared, so normalized drops to 17%, the same content in fewer, longer lists, where a query term lands on its document.
3. Stemming barely lengthens lists. Elasticsearch's word+stem stays 57% (65k of 114k) singletons, since it only merges already-rare forms. Subword tokenization is the one thing here that fundamentally lengthens the lists.

What one search actually reads

How many posting entries a single query traverses, in a real 2,953-doc index. Toggle the query (log scale, since the bars span four orders of magnitude):

The rare, precise word "veal" costs 2 posting reads under word-BM25 (two documents contain it) and 13,799 under char bigram, because the bigrams ve, ea, al each span most of the corpus. Same search, ~7,000× the work, for a fuzzier result.

That normalization moves naive's −0.11 gap to essentially zero. Here's the full ladder for both tokenizers. Toggle the metric, and the naive break widens from a ten-point dip at the mean to p25 = 0.000 and a 31% zero-rate:

Observations (toggle the metric, the story is in the tail, not the mean):

1. Normalized BPE (green) ties plain word-BM25, both tokenizers. 0.522 / 0.520 vs word's 0.526, medians on top. Normalizing before you tokenize is the whole fix.
2. Naive BPE (red) breaks on the tail. The ten-point mean drop undersells it: p25 collapses to 0.000 and the zero-rate jumps to 31% vs word's 20%, half again as many queries returning nothing.
3. The word-tuple control (purple) is identical to plain word. Keep each word as one term equal to its token-ID tuple and nothing moves. The token-ID representation is irrelevant, only decomposing words into subwords changes quality.

Is "within noise" actually parity?

"The bars look the same" isn't a statistical claim, so I bootstrapped the per-query delta (resampling datasets, then queries within each). Normalized BPE lands within noise of plain word (−0.004, CI [−0.014, +0.006]), a tie but not proven equal, and −0.02 behind Porter-stemmed word_en, losing 10 of 12 datasets: a hair behind a real stemmer.

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 partial stemmer, exactly what the retrieval numbers show.

This is char n-gram retrieval: subword indexing does the same decomposition, and McNamee & Mayfield (2004) showed it recovers morphology without a stemmer. Not new to BPE, but on the model's own tokens it's a language-agnostic analyzer you already have (no stopword list, stemmer, or segmenter), on the same vocabulary the model reads, writes, and stores. And unlike a stemmer's hard merge, subword tokens are a knob you can weight. That, plus un-fragmenting rare words, closes the −0.02 gap below.

The tie holds at every depth, not just rank 10. Normalized BPE tracks plain word from 5 to 1000, so there's no hidden wider net. The lone exception is char 4-grams, which reach more documents but rank them deep:

Closing the stemming gap, token-natively

The base ties plain word but sits −0.02 below Porter (loses 10 of 12, ns). I traced about three-quarters of that to stemming. Two token-native fixes recover it, neither a hard stem-merge:

Fix 1: stop fragmenting rare words. BPE splits belvidere into bel·vid·ere, and BM25 adds each subword's IDF independently, so a rare word draws 1.3–2.3× the IDF it deserves. Score each word once instead: key it by the whole word's token-ID tuple, or group its subwords under one word-level IDF plus a coverage term (GroupCov).

Fix 2: stem by expansion, not merging. A classic analyzer runs Porter over both sides, hard-merging race/races/racing in the document index. Token-natively the index stays pure token IDs, and stemming moves query-side: expand each query word to its stem-group variants and max-score the set, weighting each by attestation (df_variant / (df_variant + k·df_word)) so a common variant is trusted and a coincidental one damped. This is the SPLADE view: stemming is weighted expansion with clean candidates, and Porter's groups are clean enough to weight hard.

Stack both, plus a stopword list that turns load-bearing once words are un-fragmented, and the gap closes:

Observations:

1. Both recipes reach word_en (0.545). Word-tuple + expansion 0.545, GroupCov 0.547, and every per-query bootstrap CI against the stemmer straddles zero, a statistical tie. (The per-dataset split, word-tuple loses 9/12 and GroupCov wins 7/12, is the argmax of a ~7-variant sweep on these same sets, so read it as a tie, not an edge.)
2. The firm win is vs the token baseline, not Porter. Both clear zero against plain normalized token-BM25 (word-tuple +0.023, CI [+0.001, +0.045]). Reaching Porter reads as a tie only because Porter-vs-plain is itself within noise here.
3. The tail agrees. Word-tuple + expansion even edges the stemmer there: 16.9% zero-rate vs 17.2%, p25 0.28 vs 0.26. Soft expansion rescues failing queries as well as Porter's hard merge. (p10 is a flat 0.000 for every method, the shared hard floor.)

I'd ship GroupCov: it un-fragments the rare words that hurt precision while keeping the subword partial-matching the multilingual result depends on. Expansion candidates are Porter-grouped, so this half stays English-only. Config-free comes with the multilingual post.

Dropping the stopword list, too

Of the two hand-built pieces left, Porter to group stem candidates and the stopword list, I can drop the list.

A stopword isn't a linguistic category, just a word that's usually common everywhere. Not always, though. Query vitamin A and a stoplist drops the A, so the vitamin A page and a vitamin C page score the same. It deleted the token that told them apart. So don't cut, down-weight by degree. I weight each term by its global rarity, a normalized log(T/cf) (T = tokens in a big background corpus, cf = the term's count), raised to a power γ that squashes the common words. Using collection frequency, not IDF's document count, is what makes it a stopword prior and not IDF again.

Read the weights off. At γ=1, the → 0.00, of 0.05, is 0.10, while running 0.50, quantum 0.61, and belvidere 0.79 pass through intact. No list, and since it's just token counts, it works in any language.

Observations:

1. The prior matches the list. 0.5456 vs the NLTK list's 0.5454, a tie, and the best Recall@100 here (0.801). One parameter, nothing to maintain.
2. Don't suppress too hard. Crank γ to 2 and it overshoots (0.527, loses 9/12): a harder exponent starts shaving mid-common content words too (Vitamin C → both vitamin and c damped). γ=0.5 is the sweet spot.
3. Language-agnostic. Token frequencies exist in every language, so this step folds into the multilingual result. That leaves Porter as the last hand-built piece.

The bigger payoff, one tokenizer for every language that retires the per-language analyzer stack entirely, is its own post: One analyzer, every language.

Beyond Porter: learned weights

Matching a stemmed analyzer is the ceiling for unweighted scoring on tokens, and swapping scorers doesn't push past it: I tried 67 variants (k1/b retunes, Dirichlet and PL2, TF·IDF, BM25-channel fusions) and the best apparent win was +0.018 NDCG@10 on the datasets I tuned it on, +0.0026 held out, textbook overfitting. The floor is hard because tokenizing barely touches the statistics BM25 was built to exploit: burstiness and document length both survive it (details below), and the only real weak spots are the two token defects the un-fragmentation and expansion above already target, which is why they reach Porter. To push past Porter you have to learn the term weights BM25 fixes at IDF × saturation, and that's SPLADE, on this same token vocabulary.

None of this needs a new engine, either. A sparse-vector index (like Qdrant's BM25 / sparse API, or Lucene's terms-as-bytes) already keys postings by arbitrary integer dimensions, and the token ID is the sparse dimension. Token-BM25 drops in with no changes, the same rails a learned SPLADE index runs on, just with BM25 weights instead of learned ones.

Limitations

• Reaching Porter is a statistical tie, not a proven win. On 12 tiny NanoBEIR sets the CI can't resolve GroupCov's nominal edge over the stemmer, so a full-BEIR run is needed to claim more. And going past Porter needs learned weights (SPLADE) on this same vocabulary.
• The precision recipe still leans on Porter. Un-fragmentation is config-free, and so is the stopword list, now a language-agnostic rarity prior. But the stem-group expansion still uses Porter query-side to group candidates (the document index stays pure token IDs), so the fully config-free story is the multilingual result, not the English-precision one.
• The base is char n-gram IR (known since 2004). The novelty is reusing the model's own analyzer, and going beyond it via weighted expansion.
• 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 multilingual story needs naive tokenization plus a multilingual vocabulary, at a small English quality cost.

Key Takeaways

• Normalizing before you tokenize makes token-BM25 match a plain word analyzer: encode each lowercased word with a fixed leading space, so a query word tokenizes the same as the same word mid-document. Skip it and BPE's space/case sensitivity costs −0.10 to −0.11 NDCG@10 on every one of 12 NanoBEIR datasets.
• That normalized base is char n-gram IR: bagging subwords gives partial free stemming (same-stem words share a subword 68–112× more than chance), so it matches a plain word index but leans −0.02 below a Porter-stemmed one (known since 2004).
• Two token-native fixes match a Porter-stemmed analyzer with none of the English machinery: un-fragment rare words (score each word once, not per subword) and soft-stem by weighted expansion query-side (weight stem-group variants by attestation instead of hard-merging both sides). They tie word_en (GroupCov 0.5471 vs 0.5446) and significantly beat plain token-BM25 (+0.023). It's a tie with Porter, not a win, and the document index stays pure tokens with Porter only a query-side hint. Pushing past Porter needs learned weights (SPLADE).
• The config-free payoff is multilingual: one tokenizer beats the per-language analyzers with zero config. That's the bigger story, in its own post: One analyzer, every language.
• One representation, shared: token-BM25 keys postings by the same token IDs the model reads, writes, and stores, so lexical search, stored payload, and generation run on one vocabulary, with no per-language analyzer to maintain.

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}
}