Beyond Junk Tokens: Subsumed Tokens in Japanese Subword Tokenization¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: Pretraining
Keywords: subword tokenization, subsumed tokens, junk tokens, Japanese NLP, binary tree search
TL;DR¶
Addressing the suppression of valid words caused by longer dominant tokens in frequency-driven subword tokenization for languages without explicit boundaries, this paper formalizes the notion of subsumed tokens and develops a tokenizer-agnostic post-processing framework that searches optimal binary segmentation trees via dynamic programming to restore valid word statistics without altering tokenizer vocabularies.
Background & Motivation¶
In natural language processing, subword tokenization methods such as Byte Pair Encoding (BPE), WordPiece, and the Unigram Language Model (ULM) serve as the foundation for modern language modeling, effectively alleviating the out-of-vocabulary (OOV) challenge. These algorithms typically rely on corpus frequency statistics or likelihood maximization to construct vocabularies and segment text. However, when applied to unsegmented languages like Japanese or Chinese that lack explicit whitespace word delimiters, frequency-driven segmentation generates severe structural artifacts. Prior investigations have primarily focused on "junk tokens" or "fragment tokens"โmeaningless intermediate substrings formed during iterative merging (e.g., the Japanese particle-prefix fragment "ใฎๆ"), which carry negligible semantic value and receive unreliable representations due to low independent frequency.
The critical yet overlooked challenge lies in the systematic underrepresentation of valid words. When subword tokenizers learn longer, multi-word units crossing grammatical boundaries (referred to as dominant tokens, such as "ใๆใใ" spanning the accusative particle "ใ" and the verb "ๆใใ"), sentences containing that compound phrase are greedily or probabilistically tokenized into the single long unit. Consequently, the independent occurrences of the shorter, linguistically legitimate word "ๆใใ" are severely absorbed and suppressed. These valid words become "subsumed tokens," starved of training observations during representation learning despite being fundamental semantic building blocks.
Existing countermeasures largely either modify the tokenizer training objective to discourage fragments (requiring costly retraining and vocabulary alteration) or apply vocabulary pruning techniques like BPE-Knockout that compromise backward compatibility. While standard pipelines prepend a morphological analyzer (such as MeCab) to enforce boundaries, they still cannot eliminate within-word fragmentation or provide a flexible remedy for raw-text tokenizers. The angle of attack in this work is that tokenization artifacts stem from segmentation search preferences rather than vocabulary contents. Core idea: keep the base tokenizer vocabulary frozen and reframe tokenization as a dynamic programming search over binary character-span segmentation trees that aggregates corpus frequency and applies morphological word-span bonuses, actively penalizing meaningless fragment tokens and restoring suppressed subsumed tokens.
Method¶
Overall Architecture¶
The proposed method functions as a tokenizer-agnostic post-processing framework that refines segmentation candidates without changing the vocabulary \(V\) or token indices. Given an input sentence of length \(n\) and the empirical corpus token frequencies \(\text{freq}_V\) obtained from the base tokenizer, the pipeline operates in three stages. First, morphological segmentation (e.g., via MeCab) is optionally executed on the raw sentence to identify a set of valid word spans \(W\). Second, a scoring function evaluates every candidate character span based on its vocabulary corpus frequency and assigns a bonus if the span matches a detected morphological word. Third, an \(O(n^3)\) dynamic programming algorithm (analogous to the Inside algorithm in chart parsing) searches for the globally optimal binary segmentation tree, and a top-down traversal extracts the refined token sequence.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Raw Input Sentence & Frozen Vocabulary V"] --> B["Morphological Span Extraction<br/>MeCab Word Set W"]
B --> C["Span Scoring Mechanism<br/>Corpus Frequency + Morphological Bonus"]
C --> D["Binary Segmentation Tree DP Search<br/>Inside-style Optimization O(n^3)"]
D --> E["Tree Traversal Token Extraction<br/>Recursive Output Generation"]
E --> F["Refined Token Sequence<br/>Suppresses Fragments & Restores Subsumed Tokens"]
Key Designs¶
1. Categorization and Detection of Overlapping Tokens: Separating Fragments from Subsumed Words
To rigorously formalize tokenization artifacts, the paper introduces the overarching concept of overlapping tokens for a vocabulary \(V\). A token \(t \in V\) with length \(|t| > 1\) is deemed an overlapping token if there exists another distinct longer token \(t' \in V\) that contains \(t\) as a contiguous substring and satisfies \(\text{freq}_V(t) \le \text{freq}_V(t')\). Here, \(t'\) constitutes a dominant token belonging to \(D(t)\). The method categorizes \(t\) by evaluating the morphological sequence \(\text{list}(t)\) against \(\text{list}(t')\). If \(t\) yields an unknown word (UNK) or represents an incomplete morphological fragment (e.g., "ใฎๆ" segmented into [ใฎ, ๆ]), it is marked as a fragment token. If \(t\) is a valid word whose morphological breakdown is a contiguous proper subsegment of the dominant token's morphological sequence (e.g., \(t=\text{"ๆใใ"}\) yielding [ๆใใ] while \(t'=\text{"ใๆใใ"}\) yields [ใ, ๆใใ]), it is categorized as a subsumed token. This distinction isolates genuine morphological words from accidental subword junk.
2. Span Scoring with Morphological Word Bonus: Reshaping Segmentation Preferences
Base tokenizers select multi-word tokens because longer character spans often accumulate high raw corpus counts. To counteract this bias, the proposed framework scores each candidate span \(t\) by combining its base corpus frequency with a structural incentive for morphological validity:
where \(W\) is the set of word spans recognized by the morphological analyzer. Crucially, the bonus is fixed to the maximum corpus frequency in the base vocabulary, \(\text{bonus} = \max_{t \in V} \text{freq}_V(t)\). This hyperparameter-free calibration provides an intuitive, data-driven scaling that guarantees genuine words recognized by the analyzer receive an overwhelming advantage against unnatural boundary-crossing dominant tokens or obscure fragments.
3. Binary Segmentation Tree Dynamic Programming: Global Optimization in Polynomial Time
Given a sentence \(s\) of length \(n\), enumerating all possible hierarchical segmentations entails an exponential search space. Algorithm 1 applies interval dynamic programming to compute the optimal binary tree \(T\). Iterating over span lengths \(\ell\) from 2 to \(n\) and starting positions \(i\) with \(j = i + \ell\), the optimal score \(\text{DP}[i][j]\) is resolved across split candidates \(k \in (i, j)\):
Recording backpointers \(\text{BackPtr}[i][j] = k^*\) allows complete tree reconstruction. Subsequently, Algorithm 2 performs a top-down recursive traversal: if a node's character span is in \(V\) and not out-scored by deeper splits, it is directly emitted to the output sequence; otherwise, its left and right children are traversed. This ensures that token frequency redistribution occurs dynamically during decoding, reducing fragment and subsumed occurrences without permanent vocabulary excision.
A Worked Example¶
Consider the phrase "ๅญใๆใใ" (be blessed with a child): - Under baseline BPE/ULM direct tokenization, the dominant token "ใๆใใ" (e.g., \(\text{freq}=50\)) is preferred over the single verb, pairing with "ๅญ" (\(\text{freq}=10\)). The candidate tree score is \(\text{freq}(\text{"ๅญ"}) + \text{freq}(\text{"ใๆใใ"}) + \text{freq}(\text{"ใใ"}) = 70\). Because "ใๆใใ" crosses word boundaries, it does not exist in MeCab's word set \(W\) and receives no bonus. As a consequence, "ๆใใ" never surfaces independently. - In contrast, the proposed dynamic programming evaluates the alternative tree partitioning "ๅญใ" (\(\text{freq}=100\)) and "ๆใใ" (\(\text{freq}=40\)). Since "ๆใใ" matches a recognized word span in \(W\), its score is augmented with \(\text{bonus}\). The resulting tree score reaches \(\text{freq}(\text{"ๅญใ"}) + \text{freq}(\text{"ๆใใ"}) + \text{freq}(\text{"ใใ"}) + \text{bonus} = 150 + \text{bonus}\), decisively surpassing the dominant-token alternative. The suppressed verb "ๆใใ" is thereby restored as an independent unit.
Key Experimental Results¶
Main Results¶
The framework is empirically validated on the Japanese portion of the Wiki-40B corpus, split equally between vocabulary training (sizes ranging from 50K to 200K) and evaluation. Intrinsic word representation quality is tested using the JWSAN benchmark (395 shared word pairs evaluated across 10 random seeds with word2vec word similarity and relatedness correlations). Downstream utility is evaluated by pretraining standard 12-layer BERT-base models from scratch on tokenized Wiki-40B corpora and finetuning on JapaneseTopicWSD for Word Sense Disambiguation (WSD) and sequence-level sentence topic classification. Two operational setups are inspected: Setting 1 (direct subword tokenization without morphological pre-segmentation) and Setting 2 (standard MeCab pre-tokenization).
Table 1 presents the intrinsic embedding evaluation results on JWSAN:
| Vocab Size | Method | Similarity BPE (Setting 1) | Similarity ULM (Setting 1) | Relatedness BPE (Setting 1) | Relatedness ULM (Setting 1) | Similarity BPE (Setting 2) |
|---|---|---|---|---|---|---|
| 50K | Base | 0.640 | 0.663 | 0.688 | 0.716 | 0.610 |
| 50K | Ours | 0.643 | 0.661 | 0.688 | 0.703 | 0.613 |
| 50K | Ours+B | 0.650* | 0.662 | 0.694* | 0.707 | โ |
| 100K | Base | 0.651 | 0.659 | 0.697 | 0.713 | 0.617 |
| 100K | Ours | 0.649 | 0.664* | 0.696 | 0.708 | 0.618 |
| 100K | Ours+B | 0.664* | 0.669* | 0.708* | 0.716 | โ |
| 150K | Base | 0.659 | 0.648 | 0.711 | 0.704 | 0.620 |
| 150K | Ours | 0.661 | 0.670* | 0.711 | 0.716* | 0.619 |
| 150K | Ours+B | 0.667* | 0.672* | 0.716* | 0.723* | โ |
| 200K | Base | 0.656 | 0.631 | 0.709 | 0.693 | 0.622 |
| 200K | Ours | 0.657 | 0.661* | 0.710 | 0.704* | 0.624 |
| 200K | Ours+B | 0.657 | 0.661* | 0.710 | 0.713* | โ |
Note: * indicates statistically significant improvement over the corresponding baseline via one-sided paired t-test (\(p < 0.05\)).
Ablation Study¶
Table 2 provides the downstream macro F1 scores across token-level Word Sense Disambiguation (WSD) and sequence-level sentence topic classification, isolating the effect of word bonuses and tokenizer models:
| Vocab Size | Downstream Task | Baseline (BPE) | Ours (w/o Bonus) | Ours+B (w/ Bonus) | Baseline (ULM) | Ours+B (ULM) |
|---|---|---|---|---|---|---|
| 50K | WSD (Macro F1) | 0.659 | 0.656 | 0.654 | 0.658 | 0.668 |
| 50K | Sentence Clf (Macro F1) | 0.633 | 0.629 | 0.635 | 0.639 | 0.642 |
| 100K | WSD (Macro F1) | 0.648 | 0.655* | 0.677* | 0.653 | 0.671 |
| 100K | Sentence Clf (Macro F1) | 0.620 | 0.617 | 0.629 | 0.625 | 0.631 |
| 150K | WSD (Macro F1) | 0.649 | 0.650 | 0.652 | 0.656 | 0.659 |
| 150K | Sentence Clf (Macro F1) | 0.611 | 0.618 | 0.635* | 0.637 | 0.633 |
| 200K | WSD (Macro F1) | 0.656 | 0.655 | 0.657 | 0.654 | 0.647 |
| 200K | Sentence Clf (Macro F1) | 0.604 | 0.614* | 0.622* | 0.621 | 0.617 |
Overlapping token counts further illuminate the mechanism:
- Under Setting 1, baseline BPE exhibits heavy counts of both fragment and subsumed tokens. Baseline ULM produces substantially fewer fragment tokens (due to probabilistic candidate pruning) but retains a high count of subsumed tokens comparable to BPE. Applying Ours+B cuts both types by more than half for both tokenizers.
- Under Setting 2, morphological pre-tokenization prevents cross-word dominant units, essentially nullifying subsumed tokens; however, fragment tokens persist. Here, the proposed method provides slight, steady reductions in fragments.
Key Findings¶
- Subsumed token restoration drives representation gains: Significant improvements in word similarity, relatedness, and downstream task F1 occur primarily in Setting 1 with bonus scoring. In Setting 2, where subsumed tokens are naturally absent due to MeCab boundaries, gains are mutedโconfirming that recovering suppressed words is the main factor behind performance gains.
- ULM suffers equally from word subsumption: Despite being far less prone to junk fragments than BPE, ULM suffers from virtually identical rates of subsumed tokens, highlighting that likelihood maximization still heavily suppresses shorter valid words.
- Compression and entropy characteristics: Introducing the word bonus slightly inflates token counts by only 0.79%โ2.20% (negligible compression loss). Rรฉnyi entropy analyses reveal decreases at \(\alpha=0.5\) and increases at \(\alpha=3\), verifying that the method systematically redistributes probability mass between low- and high-frequency regions.
Highlights & Insights¶
- Conceptual broadening of token artifacts: Expands the understanding of subword deficiencies beyond meaningless junk fragments to include "subsumed tokens"โlegitimate lexical items starved of frequency observations by longer units.
- Tokenizer-agnostic post-processing: Operates strictly at inference/segmentation time without altering vocabulary entries, tokenizer weights, or downstream vocabulary indices, enabling retrofitting onto existing corpora.
- Natural bonus scaling: Setting the bonus to the maximum vocabulary token frequency \(\max_{t \in V} \text{freq}_V(t)\) eliminates manual hyperparameter tuning while providing the exact magnitude required to overturn unnatural dominant spans.
Limitations & Future Work¶
- Cubic runtime complexity: The Inside-style dynamic programming scales as \(O(n^3)\) with sentence length. Processing 10K sentences requires ~13.5s on an AMD Ryzen 9 9950X CPU (compared to ~0.15s for standard BPE/ULM), rendering tokenization of long unsegmented text documents computationally demanding.
- External morphological dependency: The bonus formulation relies on external analyzer dictionaries (MeCab with ipadic), restricting its straightforward porting to extremely low-resource languages lacking morphological tools.
- Scope of investigated tokenizers: Evaluations were limited to frequency- and likelihood-based subword schemes (BPE and ULM); behaviors on byte-fallback, WordPiece variations, or newer character-level models warrant further study.
Related Work & Insights¶
- vs Picky BPE / Scaffold-BPE: These methods intervene in the BPE merge process during training to prevent useless scaffolding tokens; the proposed approach leaves training intact, requires no vocabulary modifications, and directly addresses the restorative needs of subsumed tokens.
- vs BPE-Knockout / Trimmed BPE: These techniques discard tokens post-hoc, which risks OOV regression or breaks compatibility; this method preserves the full vocabulary while dynamically guiding segmentation.
- vs SuperBPE / Boundless-BPE: While multi-word tokenizers aim to maximize downstream inference speed via longer units, this paper exposes a critical trade-off: dominant multi-word units can systematically cannibalize foundational word frequencies.
Rating¶
- Novelty: โญโญโญโญโ [Pioneers the formalization of subsumed tokens and crafts a clean binary DP post-processing solution]
- Experimental Thoroughness: โญโญโญโญโ [Detailed coverage of intrinsic word2vec, multiple vocab scales, BERT pretraining, and downstream WSD]
- Writing Quality: โญโญโญโญโญ [Exceptional clarity, rigorous mathematical problem definition, and well-structured algorithmic descriptions]
- Value: โญโญโญโญโ [Highly valuable for improving NLP pretraining representations in unsegmented languages like Japanese and Chinese]