Source-linked AI summary
Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP
Sabrina J. Mielke, Zaid Alyafeai, Elizabeth Salesky, Colin Raffel, Manan Dey, Matthias Gallé, Arun Raja, Chenglei Si, Wilson Y. Lee, Benoît Sagot, Samson Tan
TL;DR
This survey asks which text units NLP models should use amid tensions between linguistic motivation, computational efficiency, and open-vocabulary coverage. It connects historical and neural work on word–character hybrids, learned segmentation, subwords, characters, and bytes. Its conclusion is that no single tokenization scheme fits all applications, so tokenization remains an important design choice.
Problem
NLP must choose atomic units that balance linguistic motivation, vocabulary size, efficiency, and the ability to represent rare or novel forms.
Method
The survey connects pre-neural and neural research on word–character hybrids, learned segmentation, subwords, multilingual vocabularies, characters, and bytes.
Results
The survey concludes that no singular tokenization solution covers the wide variety of NLP applications.
Takeaways & Limitations
Tokenization should remain an explicit modeling consideration because larger discrete tokens can be desirable for interpretability and efficiency, while characters and bytes suit some applications.
Takeaways & Limitations
Character- and byte-level approaches have application-dependent trade-offs, including longer sequences and language-dependent effects from Unicode representation.
Abstract
from arXiv · showhide
What are the units of text that we want to model? From bytes to multi-word expressions, text can be analyzed and generated at many granularities. Until recently, most natural language processing (NLP) models operated over words, treating those as discrete and atomic tokens, but starting with byte-pair encoding (BPE), subword-based approaches have become dominant in many areas, enabling small vocabularies while still allowing for fast inference. Is the end of the road character-level model or byte-level processing? In this survey, we connect several lines of work from the pre-neural and neural era, by showing how hybrid approaches of words and characters as well as subword-based approaches based on learned segmentation have been proposed and evaluated. We conclude that there is and likely will never be a silver bullet singular solution for all applications and that thinking seriously about tokenization remains important for many applications.
1 Introduction
Tokenization turns text into discrete units for NLP models, but what counts as a useful token is neither obvious nor fixed. The survey connects word-, character-, and subword-oriented approaches and argues that byte-level processing is not universally sufficient.
- NLP models represent text as sequences of discrete integer-indexed pieces, making token definition foundational to modeling.
- Word-like tokenization creates ambiguities around punctuation and contractions, exemplified by competing analyses of “don’t.”Possible segmentations include the unsplit form, “don ’ t,” or the Penn Treebank’s “do” and “n’t.”
- The survey reviews terminology, historical treatment, character-augmented word models, learned segmentation, subword units, and multilingual vocabulary sharing.
- Recent character- and byte-level models make maximally decomposed processing feasible for some domains and use-cases, but they retain drawbacks and biases.
2 Tokens, word-forms, and sub-words
Text units sit between linguistic ideals and technical approximations. Modern tokenization increasingly uses non-linguistically motivated subword units rather than traditional typographic or word-form boundaries.
- Microscopic text units balance linguistic annotation needs against the difficulty of consistently identifying linguistic units.
- Typographic tokens approximate linguistic units, but punctuation, morphology, named entities, numbers, and URLs complicate their definition.
- Neural language models and fixed-size vocabularies helped redefine atomic processing units as smaller subwords.
- For scripts without typographic separators, such as Chinese or Japanese, characters may serve as tokens.
- In contemporary terminology, old tokens are often called pre-tokens, while tokenization refers to further segmentation into subwords.
3 Pre-tokenization yields word-like typographic units
Pre-tokenization produces word-like typographic units as a compromise between purely typographic tokens and linguistically motivated word-forms. These tools may also normalize or otherwise alter the input, sometimes irreversibly.
- Pre-tokenizers occupy a middle ground between typographic tokens and linguistic word-forms.
- Longstanding tokenization tools include relatively simple systems and widely used implementations such as Moses and Hugging Face tokenizers.
- Tokenizers may modify raw text through normalization, spelling correction, or named entity detection rather than only segmenting it.
- Normalization and whitespace conflation can make tokenization irreversible, preventing definitive recovery of the original text.
4 Augmenting word-level pretokenizer tokens with character information
Word-level models provide interpretable units but struggle with rare and novel words, motivating character-informed representations and open-vocabulary generation. These approaches improve handling of unseen forms while retaining word-level structure in several settings.
- Word-level models are interpretable but closed-vocabulary systems that cannot adequately handle rare or novel words.Replacing unseen words with UNK is unacceptable for generation and limits useful representations of novel words.
- Rare-word removal is especially infeasible in morphologically productive languages with high type-token ratios.
- Character information can construct representations for word forms, with n-gram methods such as fastText enabling embeddings for novel words.
- Character-informed pretrained models have also been developed to improve robustness to spelling errors and transfer to domains such as medical text.
- Open-vocabulary generation uses character-level mechanisms to produce novel words when word-level models predict UNK.Mielke and Eisner’s two-stage model regularizes word embeddings with a character-level language model and generates unseen words on demand.
- Hierarchical recurrent architectures can run higher layers more slowly by skipping hidden-state updates, supporting learned word boundaries and segmentations.
5 Learning segmentations to find concatenative word-like pretokenizer tokens
This section surveys models that learn word-like segmentations as latent variables, balancing flexible segmentation with tractable inference through approximations or independence assumptions. Segmental neural language models make exact marginalization efficient by scoring substrings independently given character context.
- Character-level boundary learning: Character-level models can learn boundary decisions through hierarchical skip-or-update mechanisms, but reported segmentations and training stability are problematic.HM-RNN-based approaches were difficult to train, produced subpar segmentations, and did not consistently surpass competitive baselines.
- Learning segmentation as a latent variable: Learned segmentation treats token boundaries as latent variables whose exponentially many decompositions require approximate inference or simplifying independence assumptions.The latent vocabulary may contain overlapping strings of different lengths, producing multiple decompositions for the same input.
- Segmental neural language models: Segmental neural language models score every possible substring from character-context representations and use dynamic programming to find complete segmentations efficiently.Their tractability depends on the assumption that each segment score is independent of other segments, conditioned on surrounding characters.
- Segmental neural language models: Segmental language models extend the character backbone to language modeling by omitting input conditioning, while restricting segment lengths to keep computation feasible.Sun and Deng limit segments to four Chinese characters; Grave et al. likewise use bounded n-grams and report improved English perplexity without evaluating the resulting segmentation.
- Segmental neural language models: Additional segmental models combine character-level generation with learned substring inventories, improving perplexity or segmentation in some settings but remaining below stronger segmentation systems.Kawakami et al. report better perplexity and segmentation with image captions, suggesting multimodal supervision can help segmentation.
- Segmental neural language models: Transformer extensions to segment prediction do not consistently outperform RNN-based segmental neural language models.
6 Learning subword vocabularies and segmentations
Subword units bridge word-like and character-level modeling by maintaining finite vocabularies that can represent novel words. The section contrasts linguistic analyzers with data-driven segmentation and notes that suitable choices depend on language morphology and application goals.
- Subword units: Subword units provide a middle ground between word-level and character-level models while retaining the ability to represent unseen words through characters or bytes.The subword inventory is finite and learned from training data, but is assumed to include test-time characters or bytes.
- Learning subword segmentations: Data-driven subword segmentation learners are evaluated either for linguistic validity or for speed and downstream performance.The section distinguishes manually constructed linguistic rules from learned approaches motivated by linguistic criteria or practical heuristics.
- Language-specific constraints: Segmentation can be unsuitable for non-concatenative morphology, where character-level models or very small subword inventories may be preferable.Arabic and Hebrew are given as examples of languages for which ordinary segmentation may be a poor fit.
- Manually constructed linguistic analyzers: Finite-state morphological analyzers can induce segmentations and identify affixes by tracking which input spans produce output choices.These tools support both overt segmentation and analyses involving lemmas or other morphological units.
- Manually constructed linguistic analyzers: Morphological analyzers require manual annotation and are often considered slow and needlessly complicated, despite successful applications to noisy vocabularies.BITE converts inflected forms into lemma-and-tag representations to improve robustness on dialectal data.
- Manually constructed linguistic analyzers: Undoing derivational processes before tokenization can improve sentiment and topicality classification by enabling sharing across morphological forms.
6.2 Other Language-Specific Methods
Language-specific tokenization methods incorporate linguistic structure to address morphology, compounds, and cross-boundary processes. The survey traces unsupervised morphological segmentation from MDL models to structured Morfessor variants, while noting a practical shift toward simpler techniques.
- Language-specific challenges: German compounds and Sanskrit cross-word processes create tokenization challenges that ordinary whitespace-based segmentation does not resolve.
- Evaluation of segmentation: Early linguistic evaluation assessed subword segmentations against resources such as CELEX, grammars, and morphological analyzers rather than only downstream performance.
- Unsupervised morphological segmentation: Distributional regularity and phonotactic constraints provide useful signals for segmentation, motivating recursive and minimum-description-length approaches.These approaches seek linguistically plausible words or morphological units from observed text.
- Unsupervised morphological segmentation: Morfessor models add morphological categories and structure to early MDL segmentation, addressing over-segmentation and supporting semi-supervised learning.Morfessor CatMAP models sequential prefix, stem, and suffix categories, while later variants simplify or generalize the framework.
- Unsupervised morphological segmentation: Morfessor CatMAP was evaluated on concatenative morphology in English, Finnish, Turkish, and German through the Morpho Challenge.
- Evaluation of segmentation: Recent work has predominantly chosen lighter-weight segmentation techniques for their simplicity, despite earlier emphasis on linguistic validity.
6.4 Modern fast subword segmentation algorithms
Modern subword tokenizers prioritize efficient vocabulary learning and fast segmentation. BPE and WordPiece use deterministic merge or matching procedures, while Unigram LM and BPE-dropout introduce segmentation variability that can improve translation and transfer.
- BPE: BPE learns tokenizations by iteratively replacing the most frequent adjacent symbol pair with a new symbol and replaying the recorded merges at test time.
- BPE: Byte-Level BPE applies the same approach to raw bytes rather than characters and is used in GPT-2 and other models.
- WordPiece: WordPiece selects merges using language-model likelihood and segments each word with a left-to-right longest-match-first strategy for fast linear-time processing.
- Unigram LM: Unigram LM trains a language model over an oversized vocabulary and repeatedly prunes the lowest-probability subword items until reaching the desired vocabulary size.
- Subword regularization: Sampled segmentation improves machine translation performance, and related subword regularization methods also help monolingual tasks and multilingual transfer.BPE-dropout achieves variation by skipping individual BPE merges during segmentation.
- Tokenizer implementations: SentencePiece packages both BPE and Unigram LM and permits units to cross whitespace boundaries, supporting languages without whitespace-delimited words.
6.5 Comparing morphological segmentation to BPE and friends
Comparisons between morphological segmentation and BPE remain inconclusive: gold morphological analysis often helps, while unsupervised morphological subwords usually do not reliably outperform BPE. BPE’s strong performance may relate to its compression properties.
- Across studies, comparisons between linguistically motivated and data-driven segmentation lack conclusive results.
- UnigramLM reportedly segments better than BPE and improves BERT-style models slightly in English and substantially in Japanese.
- Gold morphological analysis improves language modeling for agglutinative languages and improves Turkish and Uyghur translation when applied before BPE.
- Only one cited study finds unsupervised Morfessor FlatCat outperforming BPE, while several translation studies find no reliable improvement.
- Morphological segmentation’s possible translation benefit may depend on language similarity, motivating combined approaches.
- BPE performs near the top among comparable compression algorithms, suggesting compression capacity as one explanation for its performance.
6.6 How many units do we need?
Choosing the number of subword units remains an open, task-, domain-, and language-dependent problem. Larger units increase memorization, while several proposed heuristics and adaptive methods aim to select vocabulary size automatically.
- The best number of merges may vary by task, domain, and language, and larger subword units lead to more memorization.
- Gowda and May propose maximizing merges while requiring 95% of subword units to appear at least 100 times.
- Salesky et al. increase vocabulary size during NMT training until returns diminish, initializing new embeddings by merging the original embeddings with an autoencoder.
- Subword size also differs somewhat systematically between languages in n-gram-based fastText embeddings.
- Entropy-based turning points can occur with far fewer merges than generally needed for good performance.
- Xu et al. select BPE vocabulary merges using optimal transport and often outperform a language-independent standard setting for translation.
7 Shared vocabularies in multilingual models
Multilingual tokenization must balance vocabulary sharing against unequal segmentation across languages. BERT tokenizers remain biased toward high-resource languages, and these granularity differences affect semantic-representation sharing.
- BERT-based tokenization remains biased toward high-resource languages despite oversampling low-resource languages.
- Tokenization fertility differs across languages, with English words generally split into fewer subwords than words in some other languages.
- Cross-language granularity differences greatly affect the sharing of semantic representations.
- Chung et al. select subword vocabularies for language clusters when retraining multilingual models from scratch, explicitly controlling allocation and sharing.
- When retraining is infeasible, proposed remedies include adding units for underresourced languages or forcing smaller existing units, but randomly initialized additions performed poorly in one study.
8 “Tokenization-free” character- and byte-level modeling
Character-, byte-, and visual-level models avoid or weaken conventional vocabulary assumptions, but each introduces trade-offs in sequence length, vocabulary size, computational cost, or language fairness. Recent results show strong performance and robustness in selected settings, without establishing a universal replacement for subwords.
- Characters?: Deep character-level Transformers can greatly outperform previous subword-based and hybrid open-vocabulary language models, while later work matches word- and subword-based results.
- Characters?: Character sequences are much longer than word- or subword-level sequences, making training and inference slower.
- Characters?: Character-level models have not consistently delivered better domain robustness or morphological generalization despite those motivations.
- Characters?: Character processing can ameliorate gender-tokenization disparities caused partly by male-biased data-driven BPE vocabularies.
- Characters?: Naive character-level modeling can create a very large vocabulary and out-of-vocabulary problems in massively multilingual settings.
- Bytes: Byte-level modeling provides fixed standardized coverage, while deep byte-level Transformers and downsampling architectures show strong language-modeling performance.
- Bytes: UTF-8 byte tokenization yields longer sequences for non-ASCII characters, potentially increasing computational costs unevenly across languages.
- Visual featurization: Pixels?: Sentence-level visual representations can perform competitively across languages and scripts for translation and are significantly more robust to induced noise.
9 Discussion and Conclusion
Tokenization has evolved substantially, but no single method satisfies all competing goals or applications. The survey therefore emphasizes choosing units according to practical needs while continuing to treat tokenization as an important design concern.
- Discussion and Conclusion: The survey traces tokenization’s evolution and connects major developments across otherwise disparate lines of research.It presents tokenization as both a changing process and an evolving concept.
- Discussion and Conclusion: No tokenization method is perfect: whitespace pre-tokens, learned subwords, and bytes each combine distinct strengths and drawbacks.The conclusion explicitly rejects a universally optimal approach.
- Discussion and Conclusion: Tokenization objectives can conflict, especially maximal decomposition for simple, robust processing versus computational efficiency and fairness across languages.The tension becomes particularly relevant as NLP considers environmental costs.
- Discussion and Conclusion: Characters, bytes, or pixels may suit some applications, while larger discrete tokens remain desirable for interpretability and efficiency in others.The appropriate granularity depends on the application rather than a single field-wide solution.
- Discussion and Conclusion: Recent work combines multiple tokenizations, uses larger-than-word units for low-resource machine translation, and recovers spelling information from subword-pretrained models.These examples show that subword approaches need not exclude richer or larger textual units.
- Discussion and Conclusion: Tokenization remains operationally separate from downstream tasks, requiring practitioners to verify compatibility between pretrained models and their tokenizers.The conclusion identifies this separation as evidence that end-to-end NLP remains incomplete.