Precompiled normalizer uses grapheme-level shortest-prefix matching and diverges from SentencePiece on NFD input

[Incheonkirin]

The Precompiled normalizer's normalize walks the input grapheme by grapheme and (1) only does a whole-grapheme charsmap lookup for graphemes under 6 bytes, falling back to per-codepoint otherwise, and (2) calls Precompiled::transform, which returns the shortest prefix match. Native SentencePiece (NormalizePrefix) instead does a byte-stream longest-prefix match, with no grapheme split and no length cutoff. Both differences make the fast tokenizer's normalization diverge from the reference on NFD input, on the same precompiled_charsmap.

Reproduction

import unicodedata, sentencepiece as spm
from transformers import AutoTokenizer

mp   = AutoTokenizer.from_pretrained("xlm-roberta-base", use_fast=False).vocab_file
sp   = spm.SentencePieceProcessor(model_file=mp)            # reference
fast = AutoTokenizer.from_pretrained("xlm-roberta-base")    # tokenizers

def sp_norm_chars(s):
    return sp.normalize(s).removeprefix("▁")   # drop the dummy-prefix marker to compare the same stage

# (1) >=6-byte NFD grapheme: NFD Hangul 각 (U+1100 U+1161 U+11A8, 9 bytes)
h = unicodedata.normalize("NFD", "각")
print(sp_norm_chars(h), "|", fast.backend_tokenizer.normalizer.normalize_str(h))
# 각 | 각   -- same glyph, but the right side is still decomposed jamo:
print(sp.encode_as_pieces(h), "|", fast.tokenize(h))
# ['▁각'] | ['▁', 'ᄀ', 'ᅡ', 'ᆨ']

# (2) <6-byte NFD grapheme: NFD Vietnamese ắ (U+0061 U+0306 U+0301, 5 bytes)
v = unicodedata.normalize("NFD", "ắ")
print(sp_norm_chars(v), "|", fast.backend_tokenizer.normalizer.normalize_str(v))
# ắ | ă   -- combining acute dropped
print(sp.encode_as_pieces(v), "|", fast.tokenize(v))
# ['▁', 'ắ'] | ['▁', 'ă']

Case (1) is the 6-byte grapheme cutoff: the whole-grapheme rule is skipped, so the syllable stays decomposed. Case (2) is under the cutoff and still fails, purely because transform returns the shortest prefix (ă) instead of the longest (ắ).

Root cause

tokenizers/src/normalizers/precompiled.rs, Normalizer::normalize: a grapheme loop with if grapheme.len() < 6, then a per-codepoint fallback, both calling self.transform. spm_precompiled::transform returns results[0] from common_prefix_search, i.e. the shortest match. SentencePiece normalizer.cc NormalizePrefix selects the longest trie result and has no grapheme split or length cutoff. SpmConverter copies the charsmap verbatim, so the two should normalize identically, but the grapheme cutoff and the shortest-prefix match diverge. The in-source comment points reviewers at XNLI for parity, but XNLI-style parity checks can miss this because they don't include explicit decomposed NFD cases.

Impact

Fast tokenizers whose normalizer includes Precompiled: XLM-R, mBART-50, multilingual-e5, NLLB, BAAI/bge-m3, bge-reranker-v2-m3. (Verified the Precompiled normalizer and the divergence on xlm-roberta-base and intfloat/multilingual-e5-small. microsoft/mdeberta-v3-base is not affected — its normalizer is Replace + NFC + Strip, and NFD Hangul composes there.) NFD input is not exotic: it can arise from legacy HFS+ filenames, copied text, decomposed Unicode pipelines, or cross-platform file/data interchange — the same string then tokenizes differently depending on its normalization form.

Direction

A byte-position longest-prefix loop mirroring NormalizePrefix. That needs a "longest match + consumed bytes" lookup; spm_precompiled currently exposes only transform (shortest) and common_prefix_search (values, no consumed length). The tokenizers manifest declares spm_precompiled = "0.1.3" and the latest release is 0.1.4, but neither adds such an API — so a clean fix touches the spm_precompiled crate plus the offset handling in tokenizers. I have a prototype byte-position implementation that restores NFD↔NFC parity on the XLM-R charsmap with NFC unchanged. I can open a PR once the approach and the spm_precompiled dependency are agreed.