Unsupervised Morphological Tree Tokenizer (2025)

Abstract: As a cornerstone in language modeling, tokenization involves segmenting text inputs into pre-defined atomic units. Conventional statistical tokenizers often disrupt constituent boundaries within words, thereby corrupting semantic information. To address this drawback, we introduce morphological structure guidance to tokenization and propose a deep model to induce character-level structures of words. Specifically, the deep model jointly encodes internal structures and representations of words with a mechanism named MorphOverriding to ensure the indecomposability of morphemes. By training the model with self-supervised objectives, our method is capable of inducing character-level structures that align with morphological rules without annotated training data. Based on the induced structures, our algorithm tokenizes words through vocabulary matching in a top-down manner. Empirical results indicate that the proposed method effectively retains complete morphemes and outperforms widely adopted methods such as BPE and WordPiece on both morphological segmentation tasks and language modeling tasks.

## introduction tokenization, the initial step of language modeling, segments natural language into manageable units. while this process is crucial for representing natural language, research on new tokenization methods has remained limited, particularly in contrast to the rapid advancements in language model architectures and learning approaches. currently, the de-facto tokenizers are bpe @xcite and wordpiece @xcite , which have been widely adopted by stateof-the-art language models such as gpt @xcite tokenizes a word through a bottom-up greedy merging approach given pre-learned merge operations, while ours (bottom) tokenizes a word via a top-down vocabulary matching while traversing a global parse tree. @xcite and @xcite . however, numerous studies have challenged these methods @xcite @xcite , arguing that they cannot adequately capture linguistic information. they often disrupt constituent boundaries within words, leading to unnatural and fragmented token representations. figure 1 (top) demonstrates an example where bpe fails to identify the appropriate boundaries in a word. according to linguistic theories, both words and sentences are believed to have internal structures @xcite @xcite . while sentence-level grammar induction methods based on deep neural networks are highly effective, whether these methods can be applied equally well to words remains underexplored. in this work, we systematically evaluate neural grammar induction methods at the word level, propose a hypothesis explaining their suboptimal performance, and empirically validate this hypothesis. building on these insights, we introduce the first effective unsupervised neural grammar induction model at the word level and present a more morphologically aligned tokenizer that leverages our model as shown in figure 1 (bottom). our approach draws inspiration from syntactic composition models @xcite , where a sentence is encoded as a weighted sum over all composed root representations of its underlying binary parse trees via dynamic programming. instead of composing a sentence from words, we apply composition models on characters in a word to induce its morphological parse tree. to train the composition model, we propose two self-supervised objectives akin to next token prediction and span prediction that effectively leverage both contextual information at the sentence level and semantic information at the subword level. thus the model can learn to assign higher probabilities to morphological constituents of a word and induce the underlying morphological parse tree. however, character sequences present a unique challenge to composition models because morphemes, the smallest meaning-bearing units in a language @xcite , are indecomposable. while we can represent a constituent by composing its sub-constituents in most cases, we cannot represent a subword by composing its components if the subword is a morpheme. for example, the meaning of windsurf can be decomposed to wind+surf, but wind is a morpheme whose meaning is not a function of its components. to address the challenge, we propose a mechanism named morphoverriding. during the bottom-up composition process in our model, upon identifying a subword that matches an entry in a heuristically constructed morpheme vocabulary, we compute the subword representation from both its components and the corresponding morpheme embedding, i.e., the model may learn to mix or override the composition with the morpheme embedding. our experiments show that such a mechanism is critical in morphological structure induction. building upon the resolution of morphological structure induction, we introduce a novel tokenization algorithm named treetok, which includes both vocabulary construction and word segmentation. during vocabulary construction, treetok first utilizes a tree-based bpe variant to build an initial vocabulary and then applies a tree-based unigram variant to prune the initial vocabulary to a specified size. because treetok operates in a top-down manner, it does not need to retain all intermediate tokens produced by merge operations in the vocabulary as bpe does. by this means, we can build a more compact vocabulary by pruning less important subwords. during word segmentation, we employ a lightweight parser with compact pa-rameters distilled from the composition model to parse a word into a character-level binary tree and then apply top-down vocabulary matching to enhance the tokenizer's alignment to morphological structure, as illustrated in figure 1 . in our experiments, which mainly focus on english, we train treetok and baselines on the wikitext-103 corpus @xcite and assess their performance on morphological segmentation tasks and language modeling tasks. evaluation results indicate that treetok consistently outperforms bpe and wordpiece across all the tasks. in conclusion, our contributions are three-fold: • we conduct empirical study on character-level neural parsing, identifying its limitations and proposing a novel explanation-lack of mor-phoverriding-to account for its suboptimal performance. ## related work subword tokenizers. subword tokenization, with typical methods such as bpe @xcite and wordpiece @xcite , has become customary in most nlp fields. bpe builds its vocabulary by repeatedly merging the most frequent subword unit pairs, whereas wordpiece selects pairs using the highest mutual information. during tokenization, bpe applies learned merge operations in the same order to new text initialized with characters while wordpiece iteratively finds the longest match in the vocabulary. unigram @xcite , another popular tokenizer, builds its vocabulary in the opposite direction: it starts with a large set of potential subwords and prunes them based on delta entropy in a unigram language model. our tokenizer aims to build upon the advantages of these effective statistical tokenizers and augment them with unsupervised induced tree structures. ## methodology to tokenize a word @xmath0, x 2 , ..., x n } where x i is the i-th character, we aim to parse it into a binary tree and then tokenize it via top-down vocabulary matching. the parser is a deep composition model capable of jointly modeling the internal structures and representations of words. it is trained on sequences of words sampled from the corpus and optimized with self-supervised objectives that capture both intra-word compositionality and inter-word contextual dependencies. in the following sections, we sequentially introduce the composition model, training objectives, and the tree-based tokenization algorithm. ## experiments we focus on english in most of the experiments, but we also evaluated the composition model on chinese in 4.2 and evaluated the tokenizer on german, which is a morphologically richer language than english, in a machine translation experiment in 4.1. we evaluate the performance of treetok against the de-facto tokenizers such as bpe, word-piece, and unigram as primary baselines. training setups. for a fair comparison, we train all tokenizers from scratch on the lowercase version of the wikitext-103 corpus @xcite without any word boundary marker and set the same vocabulary size of 30,000. for bpe, wordpiece, and unigram, we use the implementation and default training paradigm provided by the huggingface library 3 . regarding the composition model, we train it with a context window of up to 512 characters. we use gpt2 implemented from huggingface foot_2 as our causal language model when computing the auto-regression loss. we present detailed configurations of our model and training setup in appendix a.5. ## conclusion our work introduces the first effective unsupervised neural model for character-level structure induction. we discovered that recognizing the indecomposability of morphemes is key, and to address this, we developed a composition model with a morphoverriding mechanism alongside two selfsupervised objectives. treetok induces tree structures that closely match human-labeled morphology and consistently outperforms baselines like bpe and wordpiece across various tasks, offering new insights into unsupervised morphological segmentation.