Bigram tokenization for CJK BM25: per-character tokens fix recall but cost precision

[heeoneie]

Follow-up to #12836 and #12837, opened at @sjrl's request so the design can be discussed before a PR.

The problem

#12837 makes the default BM25 tokenizer split CJK text one character per token. That fixes the recall failure from #12836, but single-character tokens carry very little meaning in Korean, and the ranking suffers. Querying 서울 (Seoul) against a corpus where five of six documents are unrelated:

1. [wrong]  1.250  서점 앞에서 울고 있는 아이를 보았다.   ("a child crying in front of a bookstore")
2. [right]  1.106  서울은 대한민국의 수도이며 인구가 가장 많다.
3. [wrong]  1.053  울타리 너머로 개가 짖고 있었다.        ("a dog barking beyond the fence")

The unrelated document wins because it happens to contain 서 (from 서점, "bookstore") and 울 (from 울고, "crying"). A Hangul syllable is closer to an English letter than to a word: 서 on its own can be 書 / 西 / 序, and 울 can be the verb stem "cry" or part of 울타리 ("fence"). This is why Lucene's CJK analyzer emits bigrams rather than unigrams.

Measurements

haystack-ai==3.1.1, same corpus and same code path, swapping only the tokenizer. Script at the bottom.

tokenizer	recall@10	top-1 correct	서울 precision	1-syllable query 산	tokens per KO sentence
current default	0/10	0/10	no results	0 hits	6
#12837 (unigram)	10/10	10/10	wrong doc at rank 1	3 hits	19
bigram	10/10	10/10	correct at rank 1	0 hits	13
unigram + bigram	10/10	10/10	correct at rank 1	3 hits	32

Pure bigrams recover the precision but lose single-character queries, which is what Lucene's outputUnigrams option exists for. Emitting both fixes that at the cost of token count.

Scope caveat: every number here is Korean. I have not measured Japanese or Chinese, where the same change would apply and where the tradeoffs may land differently.

What would need to change

self.tokenizer = re.compile(bm25_tokenization_regex).findall, and overlapping bigrams cannot be expressed that way. They need a lookahead capture, and then findall returns groups, so the Latin branch collapses to '' (with one group) or the result becomes tuples (with two):

re.compile(r"[^\W<CJK>]+|(?=([<CJK>]{2}))").findall("서울은 Luna 2026")
# ['서울', '울은', '', '']            <- Latin tokens lost
re.compile(r"([^\W<CJK>]+)|(?=([<CJK>]{2}))").findall("서울은 Luna 2026")
# [('', '서울'), ('', '울은'), ('Luna', ''), ('2026', '')]

Two ways out:

A. A callable tokenizer parameter. serialize_callable / deserialize_callable means it survives to_dict / from_dict by import path, so pipeline YAML still round-trips — but only for module-level functions; a lambda or a closure silently breaks that. Most flexible, largest surface.

B. A serializable mode. Something like bm25_cjk_tokenization: Literal["unigram", "bigram", "bigram_and_unigram"], with a shipped tokenizer per mode. It round-trips as a plain string with no callable-serialization caveats, at the cost of not being extensible by users.

I lean towards B for the default path, with A as a possible later addition: what most users need is a good default rather than an arbitrary tokenizer.

Open questions

1. Which default? Unigram as fix: default BM25 tokenizer splits CJK characters for bare-term retrieval #12837 ships it, with bigram opt-in, or bigram-and-unigram as the default once it has been measured on Japanese and Chinese too?
2. Is the token count of bigram_and_unigram (roughly 5x the current default for Korean) acceptable for an in-memory store, or does that argue for pure bigrams plus a documented caveat about single-character queries?
3. Should the benchmark live as a test, so that a future tokenizer change has to state its effect on recall and precision rather than being judged by eye?

Happy to implement whichever direction you prefer, and to contribute the benchmark as a test either way.

Benchmark script

r"""Tokenizer comparison for haystack PR #12837 (haystack-ai==3.1.1).

Swaps only the BM25 tokenizer, holding corpus, retriever and BM25 algorithm fixed:

  current  the released default,  r"(?u)\b\w+\b"
  unigram  this PR: one token per Hangul syllable / CJK ideograph / kana
  bigram   Lucene CJKBigramFilter style: overlapping 2-grams over CJK runs
  both     bigram + unigram, i.e. Lucene's outputUnigrams=true
"""

import re

from haystack import Document
from haystack.components.retrievers.in_memory import InMemoryBM25Retriever
from haystack.document_stores.in_memory import InMemoryDocumentStore

CJK = r"ᄀ-ᇿ㄰-㆏가-힯぀-ヿ一-鿿"
CURRENT = r"(?u)\b\w+\b"
UNIGRAM = rf"[^\W{CJK}]+|[{CJK}]"
SPLIT = re.compile(rf"[^\W{CJK}]+|[{CJK}]+")
CJK_RUN = re.compile(rf"[{CJK}]+")


def cjk_tokenizer(*, bigrams: bool, unigrams: bool):
    def tokenize(text: str) -> list[str]:
        out: list[str] = []
        for m in SPLIT.finditer(text):
            s = m.group(0)
            if not CJK_RUN.fullmatch(s):
                out.append(s)
                continue
            if bigrams:
                out.extend([s[i : i + 2] for i in range(len(s) - 1)] or [s])
            if unigrams:
                out.extend(list(s))
        return out

    return tokenize


def make_store(mode: str, docs: list[Document]) -> InMemoryDocumentStore:
    regex = CURRENT if mode == "current" else UNIGRAM
    store = InMemoryDocumentStore(bm25_tokenization_regex=regex)
    if mode == "bigram":
        store.tokenizer = cjk_tokenizer(bigrams=True, unigrams=False)
    elif mode == "both":
        store.tokenizer = cjk_tokenizer(bigrams=True, unigrams=True)
    store.write_documents(docs)
    return store


def search(store: InMemoryDocumentStore, query: str, top_k: int = 10) -> list[Document]:
    return InMemoryBM25Retriever(store, top_k=top_k, scale_score=False).run(query=query)["documents"]


# One natural sentence per city, mentioning it once with an attached particle.
CITIES = [
    ("서울", "서울은 대한민국의 수도이며 인구가 가장 많다."),
    ("부산", "부산은 대한민국 제2의 도시이자 최대 항구이다."),
    ("제주", "제주에는 화산 활동으로 만들어진 독특한 지형이 많다."),
    ("대구", "대구를 방문하면 근대 골목길을 걸어볼 수 있다."),
    ("인천", "인천에서 출발하는 국제선 항공편이 가장 많다."),
    ("광주", "광주의 5월은 역사적으로 중요한 의미를 가진다."),
    ("대전", "대전은 과학 연구 단지가 밀집한 도시로 알려져 있다."),
    ("울산", "울산에는 자동차와 조선 산업 단지가 모여 있다."),
    ("세종", "세종으로 여러 중앙 행정 기관이 이전하였다."),
    ("수원", "수원에는 조선 시대에 쌓은 화성이 남아 있다."),
]

# Unrelated sentences that happen to contain 서 or 울 inside other words.
DISTRACTORS = [
    "서점 앞에서 울고 있는 아이를 보았다.",
    "서류를 모두 제출해야 접수가 완료된다.",
    "울타리 너머로 개가 짖고 있었다.",
    "서열을 정하는 회의가 길어졌다.",
    "경기도는 서쪽 해안을 따라 갯벌이 넓다.",
]

SINGLE = ["산이 높고 물이 깊다.", "부산은 항구 도시이다.", "등산을 좋아한다."]

print(f"{'tokenizer':9} {'recall@10':>9} {'top-1':>7} {'서울 precision':>16} {'산 hits':>8} {'KO tokens':>10}")
for mode in ("current", "unigram", "bigram", "both"):
    store = make_store(mode, [Document(content=s, meta={"city": c}) for c, s in CITIES])
    recall = sum(1 for c, _ in CITIES if any(d.meta["city"] == c for d in search(store, c)))
    top1 = sum(1 for c, _ in CITIES if (r := search(store, c)) and r[0].meta["city"] == c)

    precision_docs = [Document(content=CITIES[0][1], meta={"relevant": True})]
    precision_docs += [Document(content=s, meta={"relevant": False}) for s in DISTRACTORS]
    ranked = search(make_store(mode, precision_docs), "서울", top_k=3)
    precision = "no results" if not ranked else ("correct@1" if ranked[0].meta["relevant"] else "WRONG@1")

    single = len(search(make_store(mode, [Document(content=s) for s in SINGLE]), "산", top_k=3))
    tokens = len(store._tokenize_bm25(CITIES[0][1]))
    print(f"{mode:9} {recall:>7}/10 {top1:>5}/10 {precision:>16} {single:>8} {tokens:>10}")

print("\nRanking for the query 서울:")
precision_docs = [Document(content=CITIES[0][1], meta={"relevant": True})]
precision_docs += [Document(content=s, meta={"relevant": False}) for s in DISTRACTORS]
for mode in ("unigram", "bigram"):
    print(f"  {mode}")
    for i, d in enumerate(search(make_store(mode, precision_docs), "서울", top_k=3)):
        print(f"    {i + 1}. [{'right' if d.meta['relevant'] else 'wrong'}] {d.score:6.3f}  {d.content}")

print("\nAverage document length, 20 Korean + 3 English documents:")
ko = [f"서울은 대한민국의 수도이며 인구가 가장 많다. 사례 {i}." for i in range(20)]
en = [
    "Seoul is the capital of South Korea and has the largest population.",
    "Busan is the second largest city in South Korea.",
    "The capital city hosts the national government.",
]
for mode in ("current", "unigram"):
    store = make_store(mode, [Document(content=c) for c in ko + en])
    avgdl = sum(len(store._tokenize_bm25(c)) for c in ko + en) / len(ko + en)
    scores = ", ".join(f"{d.score:.3f}" for d in search(store, "capital", top_k=3))
    print(f"  {mode:9} avgdl={avgdl:5.1f}  scores for the English query 'capital': {scores}")

[0xamlab]

We've measured this exact tradeoff while building a BM25 kernel: per-character CJK tokens inflate posting lists ~2–4× vs bigrams — which is where the precision loss comes from, since single-character matches carry almost no selectivity — and bigrams shift the cost to ~2× index size while keeping selectivity high. A hybrid (bigram primary, per-character fallback only when the bigram path yields zero hits) preserved both precision and recall in our testing. Happy to share the posting-list size math if useful.

Affiliation: we build a BM25 kernel at Algenta (thyn-ai); no relation to Haystack.

[heeoneie]

Thanks — the posting-list math would be useful, please do share it. I measured your hybrid against the same corpus I used above, and the result is not quite what either of us would expect, because of where this store tokenizes.

The zero-hit trigger is well defined here. bm25_retrieval drops documents scoring <= 0, so a query whose terms appear nowhere returns an empty list rather than a ranked list of noise. With a bigram-only index, the single-character query 산 returns 0 documents, which is exactly the case the fallback is for.

But documents are tokenized at write time, not at query time. InMemoryDocumentStore keeps per-document BM25 stats built when the document is written, so a fallback cannot re-tokenize the corpus per query. The unigrams have to be in the index already, which makes the hybrid an index of bigrams and unigrams with a two-stage query, not a bigram index with an occasional fallback.

And once the unigrams are in the index, the fallback stops firing for the case it was meant to rescue: a one-character run has no bigram, so the bigram tokenizer emits the character itself, which matches the unigram postings at stage 1.

configuration	recall@10	top-1 correct	서울 precision	산 (1 char)	tokens per KO sentence
per-character (this PR)	10/10	10/10	wrong doc at rank 1	3 hits	19
bigram only	10/10	10/10	correct	0 hits	13
bigram + unigram, both at query time	10/10	10/10	correct	3 hits	32
your hybrid (bigram first, unigram on zero hits)	10/10	10/10	correct	3 hits	32

In the last row the 산 query resolved at the bigram stage; the fallback never ran. So on this corpus the hybrid and the plain combined index are indistinguishable, and both cost ~2.5x the current default in tokens per Korean sentence rather than the ~2x a bigram-only index would.

Where I would expect the hybrid to earn its keep is precision on longer queries, by keeping unigram noise out of stage 1 scoring — my corpus is too small to separate that from the combined index. If your kernel indexes bigrams only and re-tokenizes at query time, that is a different tradeoff from what is available here, and worth saying explicitly in whichever direction this issue goes.

[0xamlab]

Fair point — you're right about the index-time constraint, and your measurement is the correct one: with write-time tokenization the zero-hit trigger never fires, so the "hybrid" degenerates to the combined index. I should have framed it as a scoring policy, not a tokenization fallback.

The posting-list math (why per-char precision drops): token counts per sentence are similar (19 vs 13 in your table) — the difference is the distribution. Per-char CJK concentrates mass on a few thousand distinct terms whose postings reach O(D) (common syllable components hit a large share of documents); bigrams spread the same mass over tens of thousands of distinct terms with 1–3-doc lists. BM25 scoring work per query ≈ Σ posting-list length over query terms — per-char queries do O(D)-scale accumulation per term, bigram queries touch a handful of docs. Index size is a wash; per-query work and selectivity are the costs.

Ours is also index-time tokenized (query time is just str→id mapping), so the re-tokenization variant doesn't exist there either. What does fit an index-time combined index is the scoring cascade: stage 1 scores bigram postings only; stage 2 adds unigram postings only for documents whose bigram score is exactly zero. That keeps unigram noise out of stage-1 scoring (the bigram-only precision property) while single-char queries resolve at stage 2 — same combined index, no re-tokenization. Possibly the version of the idea that fits Haystack's store.

Affiliation: we build a BM25 kernel at Algenta (thyn-ai); no relation to Haystack.

[heeoneie]

Thanks — the posting-list framing was the useful part, so I measured it instead of arguing about it. Public corpus so anyone can rerun: KorQuAD v1.0 dev (Korean Wikipedia paragraphs), as 964 paragraphs (mean 541 chars) and as the same text split into 6,500 sentences (mean 79 chars), to separate the effect of document length. Same NFC + lowercase preprocessing as the store, df counted per document.

	distinct terms	postings	terms with df ≥ 10%·D	lists ≤ 3 docs
paragraphs, D=964
per-character	4,217	143,993	347	68.4%
bigram	30,861	191,846	189	69.6%
sentences, D=6,500
per-character	4,207	276,298	110	65.6%
bigram	30,816	240,824	12	66.2%

Your main claim holds, and I was wrong to expect otherwise. Bigrams give 7.3× the distinct terms in both conditions — 30,861 against 4,217, so "tens of thousands" is right — and the O(D) head shrinks substantially: 347 → 189 terms above 10%·D on paragraphs, and 110 → 12 on sentences. The effect gets stronger as documents get shorter, not weaker.

One sub-claim does not hold: the share of 1–3 document lists barely moves (68.4% → 69.6%, and 65.6% → 66.2%). Both tokenizers are dominated by rare terms; the difference bigrams make is entirely in the head of the distribution, not in how many long-tail terms there are. Worth stating precisely, since "spread over tens of thousands of terms with 1–3-doc lists" suggests the tail is where the win is, and it isn't.

Query cost, summing posting-list lengths over query terms:

query	per-character	bigram
조선	1,041	79
경제	1,126	54
서울	1,063	95
대한민국	2,723	460
만들었다	3,050	711

So "bigram queries touch a handful of docs" is fair — 54 to 460 out of 964 — and 11–21× less accumulation on the two-syllable noun queries this issue is actually about.

On index size, your two comments are both right against different baselines. You said ~2× in the first and "a wash" in the second. Measured: bigram vs per-character is 1.33× on paragraphs and 0.87× on sentences (a wash, and below 1 once documents are short), while bigram vs the current default is 1.82×. Pinning the baseline matters for this issue, because the in-memory store's constraint is absolute size, not the ratio to a tokenizer we are not shipping.

The number the cascade has to defend. Stage 1 costs the bigram column, which is the win. But the index must hold both: 318,201 postings, 2.21× per-character and 3.02× the current default. That is the real price, and it is the one an in-memory store will be judged on.

Given all that, I would write the issue up as: default stays per-character; bigram_and_unigram is opt-in via the serializable mode string (option B above) rather than a callable; documented cost is ~2.2× the per-character index in exchange for roughly an order of magnitude less per-query accumulation and the precision fix. If that reads right to you, I will take the PR.

One thing I would still like your input on: everything above is index-side. Do you do anything at scoring time to keep a bigram match from being counted twice when its two unigrams also match, or does the cascade's stage 2 simply replace the stage 1 score rather than add to it?

[Rainmemery]

As the author of #12837, I'd back option B (a serializable mode string, default stays per-character, bigram / bigram_and_unigram opt-in). The deciding reason for me is the code path itself: because InMemoryDocumentStore builds BM25 stats at write time, any mode here is index-time, and a plain Literal[...] string round-trips through to_dict/from_dict with none of the serialize_callable caveats (lambda/closure silently breaking YAML). It keeps the surface minimal, which is what this default change really needs.

One design fork I don't think the mode string alone settles, and that @heeoneie's last question touches: with a combined index, whether stage-2 unigram scores replace vs. add to the stage-1 bigram score changes both the single-char recall behavior and the double-count risk (a bigram hit whose two unigrams also match). That's a scoring-time decision independent of tokenization, and I'd want it pinned before coding.

If the direction above is final and it's still unclaimed, I'm happy to take the follow-up PR ??I already have the tokenizer branch and the benchmark harness from #12837, and I can land option B plus the KorQuAD measurements as a regression test so the ~2.2x tradeoff stays visible in CI. Just flagging it here so I don't collide with @0xamlab's very useful numbers. @heeoneie, want me to open a draft against that spec, and is there any naming/default constraint you'd prefer for the mode values?

[heeoneie]

@Rainmemery — yes, please take it, and thank you for offering. #12837 just merged, and you hold the tokenizer branch and the benchmark harness it introduced, so you're best placed to land the mode param as a direct follow-up on top of it. I said above that I would take the PR if the direction held; handing it to you is the faster path, and I would rather spend my time on the spec and on reviewing the Korean behaviour than on the diff.

Answers to your two questions.

Scoring policy: make stage 2 replace, not add. I measured the fork rather than argue it, and the honest result is that it is a design call, not a benchmark call.

Setup: KorQuAD v1.0 dev, 400 paragraphs, 200 two-syllable queries with document frequency 2–8 so there is real competition, same NFC + lowercase preprocessing.

• The two policies pick a different top-1 document on 22 of 200 queries (11.0%), so the fork is not academic.
• But there is no measurable quality difference: the median top-1/top-2 score ratio is 1.084 under cascade and 1.086 under add. Without relevance judgments I cannot say which of those 22 is better, and I am not going to claim otherwise.
• Single-character recall is identical. For a one-character query both return the same 3/3, because a one-character run has no bigram and the bigram tokenizer emits the character itself.

So the case for replace is structural, not empirical:

1. Add double-counts by construction. For 서울 서울 서울 against the query 서울: bigram-only scores 1.213, unigram-only 0.627, and the combined additive index scores 1.830 — the bigram hit and its two component unigram hits all contribute to the same evidence.
2. Replace keeps an interpretable contract. "Bigram ranking when any bigram matches, unigram ranking when none does" is a sentence you can put in the docstring. Additive scores are not comparable to either pure index, so a user cannot reason about them.
3. There is no measured upside to additive to weigh against that.

I would state it in the PR as: stage 2 supplies scores only for queries where stage 1 returns nothing; it never contributes to a document already scored by stage 1. That also means a bigram hit and its component unigrams can never both count, which is the property worth pinning in a test.

Naming and the default. The one hard constraint is that the default must reproduce exactly what #12837 already shipped, so no existing user sees a ranking change from this PR:

bm25_cjk_tokenization: Literal["per_character", "bigram", "bigram_and_unigram"] = "per_character"

Reasons for those values: per_character says what the current default does rather than naming it after what it is not; bigram and bigram_and_unigram match Lucene's CJKBigramFilter vocabulary, where bigram_and_unigram is its outputUnigrams=true. A Literal also round-trips through to_dict/from_dict unchanged, which was your argument for option B and I agree with it.

Two smaller things, take or leave:

• Keep bm25_tokenization_regex working as it does today. Someone passing a custom regex should not have to learn the mode parameter, and the two should not silently fight — if both are set, the explicit regex wins.
• If you put the KorQuAD numbers in CI as you suggested, the one worth pinning is the index cost, not recall. Recall is already at ceiling for every mode; the number that will surprise a reviewer later is that bigram_and_unigram is ~2.2x the per-character index.

Happy to review, and I will verify the Korean behaviour on whatever you push. One flag: this all still depends on @sjrl confirming the direction — both of our offers were conditional on that, and nothing in this thread is a maintainer decision yet.

[anakin87]

Thanks for investigating and sharing your benchmarks.

• I actually found that bigrams can improve retrieval on the Korean sample I tested. I don't have conclusive evidence that the cascade approach performs better.

• The existing parameter bm25_tokenization_regex already supports customization. With the help of a coding agent, I easily managed to create regular expressions to extract bigrams or, alternatively, unigrams+bigrams using this document store.

• For more advanced linguistic analysis, I'd recommend Elasticsearch, OpenSearch, or Weaviate integrations. Each of them exposes plenty of configurations related to analyzers and tokenizers. Weaviate also has an embedded mode that allows to quickly experiment without a separate server.

• The InMemoryDocumentStore is intended for simple experimentation with Haystack and we don't recommend it for production. We want to keep its retrieval functionality and configuration surface small.
  Basic usability matters but adding specialized language features would increase maintenance a lot, while several existing integrations already offer solutions for these needs.

For now, we'd prefer keeping InMemoryDocumentStore as it is and limit customization to the existing parameters. We remain open to fixing general bugs.

(Briefly discussed with @sjrl)