When Tokenization Is Side Information: A Hardness Account of Unseen Word Forms

In a morphologically rich language such as Turkish, Finnish, Basque or Arabic, most grammatical word forms almost never appear in a training corpus. Each form combines a stem with several affixes, and the number of possible combinations grows multiplicatively. A language model therefore has to infer how an unseen combination behaves from the few combinations it has seen. That is a tensor completion problem: fill in a sparsely observed three-way table indexed by stem, first affix and second affix. Tensor completion has a well-studied computational-statistical gap. Roughly $n$ observed entries are enough in principle to pin down a low-rank $n \times n \times n$ table. Every known efficient algorithm, however, needs about $n^{1.5}$ entries, and beating that would refute long-standing hardness conjectures about random constraint problems.

This note proposes that the main thing a subword tokenizer does for morphology is supply, or withhold, the "weak side information" that is known to collapse this gap. When the tokenizer gives each affix its own token, the model can average an affix's effect across all the stems it attaches to. That per-mode average is exactly the extra signal that lets nearly linear sample sizes suffice. When the tokenizer fuses affixes into opaque stem-specific pieces, the average is unavailable. When the morphology itself carries no average effect, because a form's behavior depends only on how stem and affixes interact, no tokenizer can help. In that case data needs grow superlinearly, and no efficient learner is expected to avoid it. The proposal turns this into predictions about sample-complexity phase transitions. It tests them on controlled synthetic languages with small transformers, and then checks whether a corpus statistic derived from the theory explains multilingual accuracy gaps beyond what token counts already explain.

Core Claim

Let the latent behavior of word forms be a rank-$r$ tensor $T \in \mathbb{R}^{n \times n \times n}$, with entry $T_{s,a,b}$ describing how the form built from stem $s$ and affixes $a,b$ behaves in context. The corpus reveals $m$ such cells. Three regimes are expected. If the per-affix mode averages of the latent factors are bounded away from zero, and the tokenizer exposes affix identity, gradient-trained models should generalize to unseen forms once $m \approx n^{1+\epsilon}$. If those averages vanish, which is the parity-like or "orthogonal" morphology case, the generalization threshold should sit near $m \approx n^{1.5}$ for every tokenizer and architecture. A fused-word vocabulary should never generalize to unseen cells.

The first regime transfers the mode-averaging result of Tensor Completion with Nearly Linear Samples Given Weak Side Information. That paper projects a 3-tensor onto a dense matrix using one weight vector per mode and recovers from $O(n^{1+\epsilon})$ samples. It also proves the method collapses when factors are orthogonal to the weights, as in random 3-XOR. The second regime is the barrier tied to random CSP refutation in Noisy tensor completion via the sum-of-squares hierarchy and to sparse noisy linear equations in Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations. It is also achieved algorithmically at the threshold by Exact tensor completion with sum-of-squares.

The quantity the theory points to is the gap between observed cells and the relevant threshold. For a language, take the stems and two productive affix slots of a paradigm and count distinct attested forms $m$. The predicted generalization margin is then

$$ \beta = \frac{\log m}{\log n}, \qquad \text{with tractability expected when } \beta > 1 \text{ (regular, segmented) or } \beta > 1.5 \text{ (interaction-only)}. $$

Here $n$ is the paradigm's mode size. The two cutoffs come from the side-information and no-side-information thresholds above, ignoring rank and log factors.

What is new here is not that morphology-aware segmentation can help. The new parts are three. The proposal gives a falsifiable account of when segmentation helps. It separates a computational barrier, which no amount of tokenizer engineering can remove, from a statistical one. And it supplies a measurable corpus statistic that should predict failure on unseen forms.

Relation to Prior Work

The tokenization side motivates the question but does not pose it. The Token Tax shows that tokens per word explain up to 50% of accuracy variance on AfriMMLU across ten models. It treats fertility as the explanatory variable and offers no account of why fragmentation hurts generalization. We test whether paradigm density explains the variance that fertility leaves over.

The Foundations of Tokenization formalizes tokenizers as encoder–decoder stochastic maps and proves that consistency requires the decoder to invert the encoder on the data distribution. It explicitly gives no sample-complexity analysis. We work inside its exactness constraint: every tokenizer we compare is lossless. That way any differences reflect sample efficiency, not asymptotic bias.

Tensor Methods for Language Models surveys tensor methods across the language-model lifecycle and finds none applied at the tokenization stage. We do not propose a tensorized tokenizer. Instead, we use tensor recovery theory as an analysis lens on existing tokenizers. That also sidesteps the hardware realization gap the survey warns about.

Descriptive studies of morphological damage motivate the regime distinctions. These include affix fracturing in Aymara (Tokenization as Cultural Erasure), negative affixes split apart (Negative Affixes in Language Models), and the mismatch between substring merging and root-and-pattern morphology (BPEMorph). Templatic Arabic morphology is the natural real-world candidate for weak mode averages.

The tensor side supplies estimators we use as reference learners. The first is similarity-based collaborative filtering, whose $n^{1.5}$ threshold coincides with a graph-connectivity transition (Robust Max Entrywise Error Bounds...). The second is preconditioned nonconvex Tucker completion (Scaling and Scalability). The third is the side-information estimator of Yu and Xi. Square Deal constrains the design: it proves that unfolding into matrices costs $O(n^2)$ samples. A model that effectively treats stem and affix-pair as a two-way table should therefore be measurably worse.

Research Program

The first component is a family of synthetic agglutinative languages. Each word form is a concatenation of a stem string and two affix strings. These are drawn from inventories of size $n$ and given realistic character lengths, so that tokenization actually matters. A rank-$r$ CP tensor determines which of several context words follows each form. The construction has one dial: the mean of each affix factor across stems. At one end, each affix has a consistent effect ("regular" morphology with non-orthogonal mode averages). At the other, factors are zero-mean and effects exist only through interaction (the 3-XOR-like case). A training corpus reveals $m = n^{\beta}$ distinct forms in context, and evaluation uses held-out unseen forms.

Small transformer language models are trained under five lossless tokenizations:

  • a morpheme-aligned tokenizer that emits stem and affix tokens;
  • standard BPE trained on the corpus;
  • a fused-word vocabulary;
  • characters;
  • a byte model with learned merging in the style of MrT5.

For each setting we sweep $\beta$ from 1 to 2 at $n \in \{50, 100, 200, 400\}$ and locate the threshold $\beta^\*$ where held-out error falls below a fixed level. The theory makes specific predictions about $\beta^\*$:

  • near 1 for aligned tokens with regular morphology;
  • near 1.5 for every tokenizer with interaction-only morphology;
  • between these for BPE, depending on how often merges cross morpheme boundaries;
  • characters landing near the aligned case only if the model discovers segmentation.

The second component replaces the language model with explicit tensor estimators run on the same observed cells. These give algorithmic reference curves: the Yu–Xi side-information estimator, collaborative filtering, ScaledGD, and sum of nuclear norms. If transformers track the estimator that matches their information access, the tensor view is predictive. If transformers beat the $n^{1.5}$ curve on interaction-only languages, the framing is wrong, or at least the instances are not hard in the conjectured sense.

The third component carries the analysis to real languages. For languages with inflection tables and analyzers, such as Turkish, Finnish, Basque and Arabic, we build paradigm tensors from corpora and compute $\beta$ for the main slot pairs. We also estimate mode-average strength by how much a single affix's effect on model behavior is shared across stems. Pretrained models are then probed on held-out attested forms, comparing high-$\beta$ against low-$\beta$ paradigm regions.

Baselines

The naive reference point is standard BPE with no intervention, trained at matched vocabulary size. This is the setting the token-tax literature documents. Every other condition must beat its unseen-form accuracy at the same $\beta$ to count as an improvement.

The strongest existing learned alternatives are byte- and character-level encoders, since they remove the vocabulary entirely:

  • CANINE (CANINE) hashes codepoints and downsamples fourfold. It reports a +2.8 F1 passage-selection advantage over mBERT on TyDi QA, where mBERT's minimal-span F1 is 50.5 (TyDi QA).
  • MrT5 learns which bytes to delete. It reports 65.31% XNLI accuracy against 64.72% for full ByT5.

In the synthetic study, byte and character models are trained on identical corpora, with parameter count and training tokens matched by compute rather than by steps. Learning rate and depth get the same tuning budget as the subword models. "Beating" them means that morpheme-aligned tokens reach a lower $\beta^\*$ in the regular regime. The theory also requires that neither condition gets below roughly 1.5 in the interaction-only regime.

For the explicit estimators, the Yu–Xi side-information method is the strongest algorithmic baseline. No reported result was found on Lacuna for its numeric MSE at specific sparsity levels; the file reports only qualitative superiority over TenALS and HaLRTC. We therefore rerun it on our tensors.

The key ablation isolates side information. With the morpheme-aligned tokenizer held fixed, we only zero the mode averages of the affix factors. If the aligned tokenizer's advantage disappears exactly when the mode averages vanish, the advantage is the side-information mechanism and not a generic benefit of shorter or cleaner tokens. A second ablation keeps token boundaries aligned but randomizes affix token identities across stems. This destroys cross-stem averaging while preserving segmentation length.

Why not just…?

Why not just use a byte-level model and skip tokenizers? Byte models avoid fragmentation, but the theory predicts they buy nothing against the computational barrier. They also pay a sequence-length cost that CANINE and MrT5 handle with downsampling and deletion. MrT5 cannot delete at the first layer. If byte models match aligned tokens in the regular regime, they have learned segmentation internally, which is informative. If they cross $\beta \approx 1.5$ in the interaction-only regime, our hardness reading fails. The sweep settles both.

Why not just pre-segment with morphological analyzers? This is the real threat for the practical recommendation in regular languages, and we concede it. The theory predicts aligned segmentation wins there. Our contribution is the boundary of that win. Segmentation should help only in proportion to mode-average strength. It should help little for templatic or interaction-heavy morphology, where BPEMorph already finds substring methods mismatched. Analyzers also do not exist for most low-resource languages. The real-language study tests whether the predicted benefit tracks measured mode-average strength.

Why not just re-tokenize at inference time? Broken Tokens? shows that instruction-tuned models keep 93.4% of their canonical performance under random segmentation and gain from aligned digit grouping. However, re-tokenization changes only the model's input. Under our account, the side information matters during training, when the cross-stem averages are learned. We test this directly: we feed morpheme-aligned retokenizations to a BPE-trained instruct model on held-out unseen forms. Little gain would support the training-time account.

Why not just keep reporting fertility? Fertility already explains up to half the variance on AfriMMLU. The paradigm statistic earns its place only if it explains residual variance after controlling for fertility. If it does not, we report that it does not.

Decisive Checks

On the synthetic languages, the core test compares the fitted threshold $\beta^\*$ across tokenizer and morphology conditions, with bootstrap intervals over five seeds per $n$. The tensor framing is supported only if both of the following hold:

  • the gap between regular and interaction-only $\beta^\*$ under aligned tokens is near 0.5 and stable as $n$ grows;
  • the aligned tokenizer's advantage vanishes in the zero-mean ablation.

Any transformer consistently below $\beta \approx 1.4$ on interaction-only languages at the largest $n$ falsifies the hardness link.

On real data, accuracy on held-out forms is regressed on fertility and paradigm $\beta$ jointly, for Turkish, Finnish, Basque and Arabic slot pairs. We then ask whether the AfriMMLU language-level gaps, a 30-point average lag behind English per The Token Tax, are better predicted with $\beta$ added. This is done wherever corpora allow paradigm estimates. If $\beta$ adds no explained variance beyond fertility, the practical side of the claim fails even if the synthetic results hold.