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 using none of its machinery — no stopword list, no stemmer, no per-language config — and 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 is that 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. A specialized tool, matched by a more general one.

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); 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

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.

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.

The index it builds is also bounded, and it consolidates. Across the 12 corpora (52k docs) a word analyzer needs 146k distinct terms and keeps growing with every new document; naive tokenization uses 74k token terms, and normalizing merges the case/space variants (The/ the/the) down to 48k — capped forever at the tokenizer's fixed 200k, so no query ever hits an out-of-vocabulary term. Fewer terms means longer posting lists: average document-frequency climbs 32 → 79 → 109 across word, naive, and normalized.

Where those posting lists sit tells the same story — the share of index terms whose list spans each many documents (toggle the representation):

Observations:

1. Word indexing is a pile of singletons — 53% of word terms appear in exactly one document (English hapax), short lists that barely help ranking. Subwords are shared, so only 17% are singletons.
2. Normalization consolidates. Merging The/the/ the shifts mass out of the short buckets into the 101–1k range (normalized 8.8% at 101–300 vs naive's 6.6%) — the same content in fewer, longer posting lists, which is exactly why a query term now lands on its document.
3. Even the analyzer Elasticsearch ships stays singleton-heavy. word + stem (word_en: Porter + English stopwords) has fewer distinct terms (114k — stemming merges variants) but more singletons than plain word (57% vs 53%): stemming only merges already-rare forms, and dropping stopwords strips the long lists, tilting the tail further. Subword tokenization is the only thing here that fundamentally consolidates the posting lists.

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

Three things in that chart matter:

1. Normalized BPE (green) sits right on top of plain word-BM25 (gray), for both 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: keep each word as a single term equal to the tuple of its token IDs instead of bagging subwords, and nothing moves — proof the token-ID representation is irrelevant, and the only thing that moves quality is whether you decompose words into subwords.

(The cyan char-4-gram bar sits right next to normalized BPE, too — more on that below.)

The macro-avg even undersells that break. Naive BPE returns nothing at all for 31% of queries (vs 20% for plain word), half again as many total failures — a gap the mean smooths into ten points. (Reading the distribution instead of the mean is a separate rabbit hole; here it just confirms the naive break is a tail catastrophe, not a uniform dip.)

Is "within noise" actually parity?

"The bars look the same" isn't a statistical claim, so I ran a cluster bootstrap on the per-query delta. It puts normalized BPE within noise of plain word (−0.004, 95% CI [−0.014, +0.006]) — a statistical tie, not proven equal. Against the stronger Porter-stemmed analyzer (word_en) it's −0.02 behind — not significant, but it loses 10 of 12 datasets, so a hair behind a real stemmer, not parity.

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 really char n-gram retrieval — subword n-gram indexing does the same decomposition, and McNamee & Mayfield showed in 2004 it recovers morphology without a stemmer, especially across languages. The free stemming is a 20-year-old subword-IR result, not new to BPE. Three reasons to run it on the model's own tokens anyway:

• A BPE vocabulary is a language-agnostic analyzer you already have — no stopword list, stemmer, or per-language segmenter, and the same one for every language.
• It's the same vocabulary the model reads and writes (token-native storage): the lexical index and the stored text share one representation.
• Subword tokens are a knob a stemmer doesn't have. A stemmer hard-merges variants; subword tokens let you weight them instead — 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 a plain word analyzer but leans −0.02 below Porter — a gap the benchmark can't even call significant (+0.019 [−0.006, +0.045], ns), though consistent (normalized loses 10 of 12 datasets). I traced roughly three-quarters of it to stemming (the rest splits between the plain-word gap and stopwords). Two token-native fixes recover it, neither a hard stem-merge:

Fix 1 — stop fragmenting rare words. When BPE splits belvidere into bel·vid·ere, BM25 adds each subword's IDF independently, so a rare word draws 1.3–2.3× the IDF it deserves and pays full credit for partial matches — noise exactly where ranking is most sensitive. The fix is to score each word once: key the term by the whole word's token-ID tuple, or group its subwords under one word-level IDF plus a coverage term for partial matches (I call the latter GroupCov).

Fix 2 — stem by expansion, not by merging. A classic analyzer runs Porter over both sides, hard-merging race/races/racing into one term in the document index. Token-natively the index stays pure token IDs — Porter never touches the documents — and stemming moves query-side: expand each query word to its stem-group variants and score the set by max (soft-OR), weighting each variant by how well-attested it is — df_variant / (df_variant + k·df_word). A common, well-attested variant is trusted almost fully; a rare, coincidental one is damped. This is the SPLADE view of stemming: stemming is just weighted expansion with clean candidates — and how hard you can weight is bounded by how clean the candidate list is. Porter's stem groups are clean, so you can weight them hard; a fuzzy surface-similarity list can't (weight it hard and race→rack floods the results).

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

Observations:

1. Both recipes reach word_en (0.5446) — word-tuple + expansion 0.5454, GroupCov + expansion 0.5471, Recall@100 on par too (GroupCov 0.794 vs word_en 0.794). Every per-query cluster-bootstrap CI against the stemmer straddles zero: a statistical tie. Per-dataset the two split it about evenly (word-tuple loses 9/12 by a hair, GroupCov wins 7/12) — but that split is the argmax of a sweep over ~7 fragmentation variants on these same 12 sets, so read it as a tie, not an edge.
2. The firm result is vs the token baseline, not vs Porter. Both fixes clear zero against plain normalized token-BM25 — word-tuple +0.023 NDCG@10 (bootstrap CI [+0.001, +0.045], clear of zero), GroupCov higher still. Reaching Porter reads as a tie only because Porter-vs-plain is itself within noise on this suite; the fixes-vs-baseline gain is the part that's actually significant.
3. The headline: a general recipe matched a hand-tuned English analyzer — soft expansion did what Porter's hard stem-merge does, on the model's own vocabulary, no linguistic rules. It's a statistical tie, not a clean win (that needs full-size BEIR), and two pieces stay query-side — a stopword list (automated next) and Porter to group candidates, neither touching the document index; config-free comes with the multilingual result below.

The tie holds on the tail, too. Read as percentiles, word-tuple + expansion actually edges the stemmer there — a 16.9% zero-rate vs word_en's 17.2%, and p25 0.28 vs 0.26 — so the soft expansion rescues failing queries at least as well as Porter's hard merge, not just the easy ones. (p10 is a flat 0.000 for every method here, the same hard tail as everywhere.)

GroupCov is the one I'd ship: unlike the word-tuple collapse, it keeps the subword partial-matching the multilingual result below depends on, while still un-fragmenting the rare words that hurt precision. (I ran GroupCov + expansion only on English — the expansion candidates are Porter-grouped, so that half is English-only for now.)

Dropping the stopword list, too

Of the two hand-built pieces the recipe still leans on — Porter to group the stem candidates, and that stopword list — the list I can drop.

A stopword isn't really a linguistic category, it's just a word that's common everywhere — the, of, is turn up in every document no matter the topic. That's a frequency fact, so I can measure it instead of maintaining a list. I down-weight each term by its global rarity: a normalized log(T/cf) (T = total tokens in a big background collection, cf = how often the term occurs in it), raised to a power γ that sets how hard the common words get squashed. Note this is collection frequency — total occurrences, not IDF's document count — and using it directly is what makes this a stopword prior and not just IDF again.

You can read the weights straight off. At γ=1: the gets 0.00, of 0.045, is 0.10, will 0.25 — squashed toward zero — while running 0.50, vitamin 0.48, quantum 0.61, and our friend belvidere 0.79 pass through nearly intact. No list, and because the background is 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 (+0.0002), and it takes the best Recall@100 of the bunch at 0.8009. One frequency parameter does the same work as a curated list, with nothing to maintain.
2. Don't suppress too hard. Crank γ to 2 and it overshoots to 0.5271 (−0.018, loses 9 of 12) — a harder exponent starts shaving mid-common content words a list leaves alone (Vitamin C → both vitamin and c get damped). γ=0.5 is the sweet spot: kill the true stopwords, spare the borderline content.
3. This half is language-agnostic. The NLTK list is English; token frequencies exist in every language, so the stopword step folds straight into the multilingual result below. That leaves Porter — grouping the stem candidates — as the last hand-built piece.

The real payoff: one analyzer, every language

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. 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 metric (top row) and the language (bottom) — the zero-rate view is the one that lands:

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 — or than a production engine's own Chinese analyzers (Elasticsearch's cjk 0.49, its default character segmentation 0.52), both still under o200k's 0.53.

But Chinese is the exception, and the honest picture — once you add Elasticsearch's built-in per-language analyzers (cjk/hindi/thai, the production version of "reach for the language-specific tool") — is more interesting than "BPE wins":

• Where a language has a mature analyzer, configuring it still beats token-native. ES's hindi analyzer (a real Hindi stemmer + stopwords) hits 0.63 vs naive o200k's 0.55; ES's thai word-breaker hits 0.61, beating naive BPE (0.56) and tying char 4-grams. On Chinese there's no such tool that helps (jieba loses to characters), so token-native wins; on Hindi and Thai there is, and it wins.
• The best variant flips by language, and normalization is an English trick. normalized o200k wins Chinese; naive o200k wins Hindi (normalization hurts — \w+ forces boundaries Devanagari lays out differently, collapsing it to 0.27); char 4-grams win Thai. Naive BPE is the robust config-free choice — best-or-near-best everywhere — but not always the ceiling.
• Tokenizer coverage is decisive. r50k has no Devanagari or Thai merges, so it collapses — 0.007 on Hindi, 0.04 on Thai (the storage-post failure again). o200k, trained multilingually, handles both.

So the real payoff isn't "one tokenizer beats every analyzer." It's zero-config universality that never collapses: one BPE tokenizer gives you a strong, never-catastrophic baseline in every language with no per-language setup — and where a language has real tooling (Hindi, Thai), you can still do better by configuring it. The failure lens makes the point cleanest: word \w+ returns nothing for 98% of Chinese queries, the wrong tokenizer (r50k) for ~95% of Hindi and Thai; token-native's win is that it's never that catastrophe, in any language, for free.

And it's not only human languages — code is the same story, sharper. On CodeSearchNet (Python, docstring → function), a Porter stemmer hurts: 0.944 NDCG@10 vs plain word's 0.963, because English stemming rules mangle identifiers instead of matching them. Token-native wins — GroupCov 0.972 — subwording getUserById into get·User·By·Id the way it does morphology. On English the stemmer is a tie; on code it's a liability.

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 — 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 — 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 the stopword list I replaced with 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 really 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) — 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: on Chinese, \w+ word tokenization collapses to 0.01 NDCG@10 while the config-free naive o200k tokenizer beats the jieba segmenter, 0.49 vs 0.40 (a \w+ presplit lifts it to 0.53 but wrecks Hindi). Directional — one MIRACL dev set; on Thai char n-grams win, and r50k dies on Devanagari/Thai where o200k holds.
• One representation, shared: token-BM25 keys postings by the same token IDs the model reads, writes, and stores — lexical search, stored payload, and generation on one vocabulary, 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}
}