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.

Buckets hide the shape inside each bar, so here's the same index as a continuous curve. Sort every term by document frequency and plot it: each analyzer becomes one line, and the area under that line is its posting entries, so the traversal cost is the shape rather than a stack of shares.

Char bigram sits on a plateau at 35,390 documents out of 51,677 all the way to rank ~300, then falls off a cliff. In the histogram that was one bar. Here it reads as a ledge. Word's curve drops to the df=1 floor at rank 51,386 and runs flat along it for the remaining 65% of its vocabulary, terms that can never separate two documents. Normalized BPE reaches that floor only at 74% of a vocabulary less than a third the size.

Switch to by token ID for something the bars can't show at all. Words and char n-grams have no numeric ID, but a BPE token does, and BPE assigns IDs in merge order, which tracks frequency in the tokenizer's own training corpus. Plot doc frequency against that ID on NanoBEIR, a corpus the tokenizer never saw, and the ordering holds: above ID 256 it decays from ~3,400 documents down to ~9 at the top of r50k's 50k vocabulary, and from ~2,200 to ~5 across o200k's 200k. Spearman ρ = -0.59 for r50k against -0.34 for o200k, because most of o200k's vocabulary is non-English tokens that never fire here.

The trough on the left is worth reading closely. Below ID 256 there are no merges at all, only BPE's single-byte fallback, and it splits in two: IDs up to ~95 are printable ASCII (c, e, t, each in 1,000–3,000 of the 52k documents, since almost every document contains the letter e), while IDs ~96–255 are lone non-ASCII bytes, not valid UTF-8 on their own, appearing in 2 to 165 documents. Merge order starts at 256 and doc frequency jumps straight back to ~3,400 with at, it, and ␣f. Those 256 tokens are a rounding error against a 30k–48k vocabulary, so cutting them moves ρ by only 0.001. The trough shows up in the curve without doing much to the correlation.

So the ID is already a rarity estimate, available before you have a single corpus statistic. Feeding that prior to BM25 as a weight on top of local IDF is worth about +0.006 NDCG@10 (CI [-0.006, +0.016], 9 wins / 3 losses), so the ordering is real but there's no retrieval gain to collect from it.

The loose ordering isn't inherent, though, and token-storage already has the fix. That post's +freq trick relabels every token by its descending-frequency rank, so the most-used token becomes ID 0, purely so a variable-length integer codec can pack the IDs smaller. Switch the chart to by +freq rank and the same remap does something for search: the jagged curve straightens into a monotone slide from 47,396 documents down to the df=1 floor, and the byte trough disappears because the byte tokens sort into their actual place.

The table here is built held out, on 4M tokens of that post's C4 prose corpus and applied to NanoBEIR unchanged, which is what a deployed static rank table is. At the head the transfer is exact: the table's top eight ranks (␣the, ␣and, ␣to, ␣of, ␣a, ␣in, ␣is, ␣for) are the same eight terms as this corpus's eight highest document frequencies, for both tokenizers, just shuffled slightly within the set (␣to is the table's rank 3 but only 6th by document frequency here). Across the whole vocabulary it tightens the ordering for both tokenizers, most for the one whose raw IDs were worst:

o200k goes from the worst ordering to the best, because its raw IDs are the ones scrambled by the 200k multilingual vocabulary while its frequency ranks are not.

The gap from -0.81 to -0.99 isn't the tokens the table never saw, which was my first guess. Those are 11,052 of 48,157 index terms, 23% of the vocabulary, but they carry only 0.7% of the postings: they're rare in NanoBEIR too, so parking them at the tail happens to be about right, and the correlation over just that group is -0.04, no information either way. Only 3 of this corpus's 2,000 most frequent terms are missing from the table at all. Restricting to the terms it did see gives a worse ρ of -0.75, so the headline -0.81 is slightly flattered by that correctly-parked tail.

The real gap is mis-ranking terms it has seen, and the misses are the domain vocabulary you'd guess:

General web prose has little use for ␣vitro or ␣mediated, and NanoBEIR is largely biomedical and scientific (␣rebut is ArguAna's debate text). The table puts them 10-20k ranks too low, which is exactly the mismatch token-storage flags for compression, showing up here as ranking error instead of lost bytes. Which is the argument for doing the remap in the tokenizer itself, where every downstream index inherits a table built on something much broader than one corpus.

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 (amber) 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 normalized BPE gets close to a word index

Normalization means split into words, then encode each one alone with a leading space: enc.encode(" " + word). So storage is always [ storage], in a query or mid-sentence.

That one rule makes it a word index. storage is a single token, so matching the token is matching the word:

query  storage       ->  [ storage]
doc    ...storage...  ->  [ storage]        same token, matches

Most words are single tokens, so most matches are exactly word matches. Keep each word's tokens as one term instead of bagging them and you score 0.526, identical to word.

Bagging the subwords adds the one thing a word index can't do: a split word shares a piece with a shorter relative.

query  token            ->  [ token]
doc    ...tokenization  ->  [ token][ization]    shares [ token], partial match

token and tokenization are different words, so a word index scores them zero, but they share [ token]. Free stemming, no stemmer.

It's flaky, though, because the split is up to BPE, not the stem. civilization is one whole token, so it matches neither civil nor civilize. And in r50k, normalize and denormalize share only [ize], the suffix every -ize verb carries, and miss the real stem:

civil -> [ civil]            civilize -> [ civil][ize]          civilization -> [ civilization]
normalize -> [ normal][ize]  denormalize -> [ den][ormal][ize]  share only [ize]

That sharing fires only about 4% of the time (details below), real but weak. So normalized BPE ties word on the median query. o200k ties on the hard queries too, but only because it barely splits anything. r50k really splits words, and gives up about 0.02 at the weak-query quartile (p25 0.202 vs word's 0.219).

This is char n-gram retrieval (McNamee & Mayfield, 2004) on the model's own tokens. Unlike a stemmer's hard merge, subword tokens are a knob you can weight, and that plus un-fragmenting rare words closes the −0.02 gap to Porter below. The match also holds at every depth, so there's no hidden wider net. The exception is char 4-grams, wider but deeper:

Closing the stemming gap, token-natively

Normalized token-BM25 already matches a plain word index. A Porter-stemmed analyzer still edges it by about 0.02, small enough that the benchmark can't call it significant, but consistent across 10 of the 12 datasets. Most of that gap is stemming. The analyzer collapses race/racing/raced into one term, and the token index keeps them apart. Two token-native fixes close it, and neither one stems the documents:

Fix 1: stop fragmenting rare words. A rare word like belvidere (in 10 docs) splits into [ bel][vid][ere], and BM25 scores each piece on its own IDF:

belvidere    word  df 10    IDF 8.50   (its own IDF, one rare hit)
  [ bel]     token df 223   IDF 5.44   also in 102 other words
  vid        token df 46    IDF 7.01   also in 16 other words
  ere        token df 203   IDF 5.54   also in 100 other words
  sum of the three piece IDFs = 17.99  ->  2.1x too much

Two things go wrong. The word punches 2.1x above its weight (17.99 vs its real 8.50), so one rare word drowns out the rest of the query. And its pieces leak. bel and ere each appear in ~100 unrelated words, so a belvidere query hands partial credit to documents that never mention it. The fix is to score each word once, keyed by its whole token tuple ( bel, vid, ere) so it carries a single IDF. There is no word index here, just a table from the token tuple to its IDF (which is only that tuple's own document frequency), so the tokens are the whole key.

Which un-fragmentation wins? All of them beat the fragmented baseline, GroupCov by the most:

Observations:

1. Un-fragmenting lifts the mean from 0.522 to 0.531, with GroupCov the winner. word-tuple (0.528) is close behind. Both replace the baseline's summed subword IDFs with the whole word's own IDF, and GroupCov adds a coverage term for partial subword matches on top.
2. max_idf is the cheap shortcut that under-delivers. Capping a word's IDF at its rarest subword needs no word-df, but a word is always rarer than any of its pieces, so it under-weights the multi-token words that are most of the vocab. It recovers only half the gain (0.525) and dents the tail. Its p25 (0.213) drops below even the baseline, and it loses where rare terms carry the query (SciFact −0.027, NQ −0.013), while helping a little on common-word sets. Can you estimate the missing IDF from the subtokens instead? Mostly no, and the exception is instructive:

Fix 2: stem by expansion, not merging. race is [ race] and racing is [ racing], different single tokens that share nothing, so a query racing scores a doc that says race at zero, same as a word index. A classic analyzer fixes this by running Porter over both sides, hard-merging race/races/racing/raced all into the single stem race in the document index. Token-natively I never stem the documents. Fix 1 keys the index by whole words (each a token-ID tuple), so up front I stem those word-terms and bucket them by stem. At query time racing pulls up its bucket and weights each sibling by how common it is, df_variant / (df_variant + 0.5·df_query):

query word  racing   df 285   weight 1.00
  variant   race     df 648   weight 0.82
  variant   races    df 149   weight 0.51
  variant   raced    df  23   weight 0.14
(racer/racers are a different Porter stem, so not in this bucket)
(df across the pooled 51,677-doc corpus)

Then for each document, racing's score is the single best variant that document contains, weight × BM25(variant, doc), taking the max so the same stem never double-counts. A doc with race but not racing scores 0.82 × BM25(race), most of what race itself would earn, instead of zero. A common variant like race is trusted almost fully, a rare one like raced barely moves the score. That trust is only safe because the candidates are real stem-mates. A fuzzy lookalike list would drop rack into the bucket, and 0.8 weight on rack floods a race query with rock-climbing docs. The weighting earns its keep: drop it and give every variant full credit (weight 1), and the score falls to 0.525, below un-fragmentation alone, because rare and tangential stem-mates now match at full strength. That's the SPLADE view: stemming is weighted expansion with clean candidates.

With un-fragmentation in place, stem-expansion (Fix 2) plus the stopword list it enables closes the gap to Porter:

Observations:

1. Expansion lifts the Fix-1 winner past Porter on the body. GroupCov's 0.531 rises to 0.547 with stem-expansion (+0.016), over word+Porter's 0.545 on the mean and median (p50 0.605 vs 0.592). The firm win is the +0.025 over the token baseline. Reaching Porter itself reads as a tie.
2. The weighting makes expansion work, and the tail still favors Porter. Drop the attestation weighting (shown above) and expansion turns net-negative. Porter keeps the weak-query tail (p25 0.264 vs 0.237), so this closes the gap, it doesn't beat the stemmer. That tie is also the argmax of a ~7-variant sweep on these 12 sets, so read it as a tie, not an edge.

GroupCov is the un-fragmentation I'd ship: it keeps the subword partial-matching the multilingual result depends on, unlike collapsing each word to one atomic term. The 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}
}