Many Pasts, One Future: Spectral Boundary Discovery for Low-Resource Tokenizers

Subword tokenizers such as Byte-Pair Encoding (BPE) and SentencePiece Unigram build their vocabularies by counting frequent character chunks. They have no notion of where a meaningful unit ends, so they split words at arbitrary points, for example "unhappy" into "unh" + "appy". In morphologically rich, low-resource languages they also break words into many tiny pieces. We propose a different signal for placing token boundaries. A good boundary is a point in a word where many different beginnings lead to the same set of possible endings. After "walk", "jump", and "play", the same endings follow ("-ed", "-ing", "-s"). After "wal", the possible continuations are specific to that one prefix. This "many pasts, one future" property is exactly what spectral learning measures. Spectral learning estimates hidden-state sequence models from a matrix of prefix/suffix co-occurrence counts, called a Hankel matrix, using a single singular value decomposition instead of iterative likelihood climbing.

The proposal is to compute a low-rank Hankel decomposition over characters and give each prefix a vector describing the futures that can follow it. Boundaries go where prefix vectors cluster densely. We then build a tokenizer whose vocabulary consists of the segments between boundaries. The target regime is corpora of roughly 10^5 to 10^7 characters in agglutinative languages. There, neural boundary detectors overfit, human morphological analyzers do not exist, and spectral methods' main weakness does not apply. That weakness is sparse moment estimates over large vocabularies, and a character alphabet is small.

Core Claim

The claim is that whole-future state similarity, estimated spectrally from character substring statistics, is a better unsupervised boundary signal than next-character branching. We expect the advantage to be largest on small corpora. We also claim that one knob, the retained rank $k$ together with a density threshold, trades compression against boundary quality more smoothly than BPE's merge count.

This connects the two directions in a specific way. Methods of Moments for Learning Stochastic Languages shows that SVD on substring-count Hankel matrices ("Spec-Sub") recovers sequence models about 40x faster than EM, at comparable accuracy (60.43% vs. 59.8% word error rate on Penn Treebank tagging). It works over word or tag alphabets and never asks what the learned state geometry says about segmentation. Unsupervised Tokenization Learning finds word boundaries from "transition freedom", the number of distinct next characters after an n-gram. That is a first-order, local statistic. Our score replaces the next-character count with the full distribution over multi-character futures, compressed to $k$ dimensions.

Mechanism

Let $H[u,v]$ be the corpus count of the character string $u$ immediately followed by the string $v$. Rows $u$ range over frequent substrings up to length $L$ ending at a position, and columns $v$ range over frequent substrings up to length $L$ starting there, following the substring construction of Spec-Sub. Take a truncated SVD $H \approx U S V^\top$ with rank $k$. Define the state of prefix $u$ as $\phi(u)$, the row-normalized vector $U_u S$. This vector summarizes which futures $u$ predicts. Define the convergence score of $u$ as

$$c(u) = \frac{1}{f(u)} \sum_{u' \neq u} f(u')\, \exp\!\left(-\lVert \phi(u) - \phi(u') \rVert^2 / \tau\right),$$

where $f(u)$ is the frequency of $u$ and $\tau$ is a bandwidth. A high $c(u)$ means many other frequent prefixes share $u$'s future, the paradigm-like situation that marks a stem or affix boundary.

At a position $t$ in a word, the boundary score is the convergence score of the longest indexed prefix ending at $t$. Local maxima above a threshold become cut points. The vocabulary is the set of frequent inter-boundary segments, pruned to a target size. Encoding then uses standard Viterbi segmentation over this vocabulary, so the tokenizer can be dropped into any existing pipeline.

We never read probabilities off the spectral model. Only the geometry of $\phi$ is used. This sidesteps the negative and non-normalized probability estimates that the unified-comparison paper identifies as the main practical defect of SVD-based Hankel estimators. The linear-model limitation noted by Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning is also irrelevant here, because the spectral model is used only as a segmenter and not as the downstream language model.

Research Program

The work has three parts.

The first is a controlled recovery study. We generate words from known concatenative grammars (stems × affix slots, with controlled paradigm sizes and noise) and measure whether convergence peaks land on the true boundaries as corpus size shrinks. This tests the statistical-efficiency argument directly. Spectral estimators are consistent, whereas a neural character model of equal capacity needs more data to learn stable states.

The second is building the tokenizer at scale over many languages. A randomized SVD on a sparse Hankel matrix with $L \le 6$ and row/column bases capped at the $10^5$ most frequent substrings should run in minutes on a CPU. We will measure this rather than assume it.

The third is downstream evaluation at matched fertility (tokens per word), which is essential given the literature's central tension. Evaluating Morphological Alignment of Tokenizers in 70 Languages finds that boundary recall explains almost none of the downstream variance ($R^2 = 0.024$) and often correlates negatively with it, because aligned tokenizers over-segment. The Token Tax finds that fertility explains up to 50% of accuracy variance on AfriMMLU. That pair of results constrains the design: alignment gains count only if fertility is held fixed. So every comparison is made at an equal vocabulary size and reported on the fertility–alignment plane.

Evidence that boundaries still matter at fixed fertility comes from two places. Evaluating Subword Tokenization: Alien Subword Composition reports that morphological rather than "alien" compositions improve Word-and-Morphology accuracy by 2.7 to 7.2 points. The Aymara study, Tokenization as Cultural Erasure, shows a root-grounded tokenizer improving translation despite higher fertility.

Non-concatenative root-and-pattern morphology (Arabic, Ethiopic) is explicitly out of scope for the main claim. Our segments are contiguous. We will report Arabic results only to document the failure, which Morphological Misalignment in Subword Tokenization predicts for any contiguous segmenter.

Baselines

The naive reference is SentencePiece Unigram and BPE trained on exactly the same corpus at the same vocabulary size as our tokenizer. This is what a practitioner would do by default. We will also sweep vocabulary size for these baselines and report their best setting, giving them the same number of tuning runs as our $k$, $\tau$, and threshold search on a held-out development split. Beating them means lower alien-composition rate and higher boundary F-measure at equal fertility, plus a downstream gain outside seed variance.

The strongest unsupervised competitor is transition freedom from Unsupervised Tokenization Learning. It reports word-tokenization $F_1$ of 0.99 on English Brown and 1.0 on Russian, but only 0.71 on Chinese. It is strongest because it uses the same kind of unsupervised count statistics and is cheap. We found no reported result on Lacuna for transition freedom on SIGMORPHON morpheme segmentation, so we will run it ourselves with its published variants (variance, derivative, peak) and n-gram pruning, on the same corpora and with the same development-set tuning budget. Beating it means higher morpheme boundary F-measure on SIGMORPHON 2022 word-level data, especially in the smallest-corpus condition.

The key ablations isolate each ingredient. In the "next-character only" ablation, $L=1$ for suffixes, which collapses our score toward a transition-freedom-like quantity. If performance does not drop, whole-future information is not doing the work. In the "no rank truncation" ablation, raw suffix-count vectors replace $\phi$, which tests whether the low-rank step matters. In the "neural state" ablation, $\phi$ is replaced with hidden states of a character LSTM trained on the same corpus with a matched parameter budget and early stopping, and the identical convergence score is applied. This separates the value of the "many pasts, one future" criterion from the value of spectral estimation specifically.

As a supervised ceiling we cite DeepSPIN-3 from Beyond Characters: Subword-level Morpheme Segmentation, which reports an average word-level F-measure of 97.29 on SIGMORPHON 2022 Task 3. We do not expect to match a supervised system. The number calibrates how much of the gap an unsupervised method closes.

For Aymara, the strongest baseline is the manually grounded T1 tokenizer from Tokenization as Cultural Erasure. It reports +1.63 chrF globally and +1.95 chrF on complex compositional structures over an unfiltered Unigram tokenizer (overall chrF about 17). Matching T1 without its human complexity tiers would count as success, and exceeding it would be a strong result.

Why not just…?

Why not just use transition freedom? It is the most serious threat, because at many boundaries high branching and high future-sharing coincide. The two diverge where branching is high but futures are idiosyncratic, such as inside long stems with many lexical continuations, and in the opposite case of affix slots with few but shared continuations. The paper's own weak Chinese result (0.71 $F_1$) and its reported memory limits on longer n-grams suggest local counts miss structure. The $L=1$ ablation and the head-to-head on SIGMORPHON settle this directly. If transition freedom ties us, we will say so.

Why not just tune the vocabulary size or filter the training corpus for Unigram? Corpus filtering demonstrably helps in Aymara, but it required linguists to sort text into four complexity tiers, which does not transfer to unannotated languages. Vocabulary tuning alone is covered by giving BPE and Unigram the full vocabulary sweep. If a tuned Unigram matches us at equal fertility, the proposal's practical value collapses to the cases where filtering is impossible, and the experiments will show whether that is so.

Why not just take boundaries from a small character language model? This alternative could genuinely work as well, so we build it in as the neural-state ablation rather than argue against it. Our argument is statistical efficiency on tiny corpora and a deterministic, tuning-light estimator. The prediction is concrete: the gap should favor the spectral state at $10^5$ to $10^6$ characters and shrink or reverse at $10^7$. If the character model wins everywhere, the correct conclusion is that the convergence criterion is the contribution and spectral estimation is not, and we will report it that way.

Why not just drop tokenization and use byte-level models? Character and byte inputs have perfect boundary recall but no compression. The Token Tax analysis ties sequence inflation to quadratic growth in attention cost. Beyond Characters also found character-level segmenters slightly below subword ones (96.85 vs. 97.29). We therefore include a byte-level model only as a compute-normalized reference in the Aymara experiment.

Proposed Experiments

We evaluate on SIGMORPHON 2022 Task 3 word-level segmentation with boundary precision, recall, and F-measure, using unsegmented raw text of each language subsampled to $10^5$, $10^6$, and $10^7$ characters. We report MorphScore-style boundary alignment across the Universal Dependencies languages used in the 70-language study, always plotted against fertility. For English, we measure alien-composition rate with umLabeller and Word-and-Morphology accuracy from the OOV Generalization Challenge, where the 2.7–7.2 point morph-vs-alien gap gives the scale of an expected effect. For downstream translation, we run Spanish–Aymara on the 17,856-pair dataset with chrF overall and on the L3–L4 complex tiers, with three seeds per tokenizer and an identical model and training budget.

Two checks are decisive. First, on the synthetic grammars and on SIGMORPHON, the spectral score must beat both transition freedom and the $L=1$ ablation at the smallest corpus size. Otherwise the whole-future hypothesis fails. Second, on Aymara at equal fertility, the unsupervised spectral tokenizer must reach at least the T1 gain over the unfiltered baseline. Otherwise, better boundaries are not translating into better models in exactly the regime this proposal targets.