Tokenizers split text into the pieces a language model actually reads. Standard tokenizers such as Byte-Pair Encoding (BPE) choose those pieces from corpus counts alone, so they often cut words at meaningless places. The cost is highest for languages with long, many-part words. One recent alternative trains the tokenizer itself with reinforcement learning (RL): the segmenter is a policy that decides, character by character, whether to place a boundary, and it is rewarded by how well the downstream model does (You Can Learn Tokenization End-to-End with Reinforcement Learning). That work treats the policy optimizer as a black box, using standard policy-gradient training with ordinary learning-rate schedules.
This proposal argues that the black box has a known failure mode, and a known fix from optimization theory. A segmentation policy is a softmax over "cut / don't cut" at each position. Most of these decisions quickly become near-certain. Once the softmax saturates, its gradient shrinks roughly as $\pi(1-\pi)$, where $\pi$ is the probability of the chosen action. This holds even when the policy has saturated on the wrong boundary, for example committing early to "unh|appy". Theory for softmax policies shows that constant or decaying step sizes then crawl at sublinear rates. It also shows that step sizes growing geometrically over iterations restore linear convergence (Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies; A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence). We propose to test whether this mechanism governs learned tokenizers, whether it hits high-fertility languages hardest, and whether a growing schedule that resets when the reward shifts reaches better segmentations at equal sample cost.
Core Claim
Learned segmentation policies stall at a small set of confidently wrong boundary decisions. This stalling is an optimization artifact, not a limit of what the model can represent, and it is concentrated in languages where words fragment into many tokens.
A natural policy gradient update, which takes steps measured in the space of policies rather than raw parameters, can fix this. If its step size grows geometrically, as $\eta_k = \eta_0 \rho^{k}$ with growth factor $\rho > 1$ and iteration $k$, it keeps a constant effective step in policy space. It therefore reaches lower suboptimality per sample than PPO (proximal policy optimization) or REINFORCE with standard schedules.
The tokenization setting is not stationary: the reward comes from a language model that is itself training. So pure geometric growth risks locking in early mistakes. Our method resets the schedule to $\eta_0$ whenever the measured per-iteration improvement in reward stops matching the rate the theory predicts. This replaces the known-discount-factor requirement of Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization, which the research file flags as brittle, with an observable signal.
How This Sits Relative to Prior Work
Two strands supply the method. The first is the policy-gradient convergence literature. Large steps or line search give linear rates in finite problems (On the Linear Convergence of Policy Gradient Methods for Finite MDPs). Adaptively increasing steps give superlinear rates for natural policy gradient (On the Linear convergence of Natural Policy Gradient Algorithm). The policy mirror descent framework (AMPO) extends geometric schedules to neural parameterizations. Nesterov momentum combined with growing steps directly counters saturation (Accelerated Policy Gradient). All of this work is validated on classic control or toy problems with stationary rewards. We bring it to a structured, high-dimensional, non-stationary policy whose optimum can be computed exactly in a controlled variant.
The second strand motivates the problem. Fragmentation tracks downstream loss: on AfriMMLU, fertility explains up to 50% of accuracy variance, and each extra token per word can cost up to 18 points (The Token Tax). Type-level fragmentation is worst for languages like Hindi, as measured by single-token retention rate, the share of common words kept as one token (Beyond Fertility).
One result constrains the proposal and must be faced directly. Why do language models perform worse for morphologically complex languages? finds that tokenizers align with morphemes better in agglutinative languages, measured by MorphScore. It also finds that the performance gap largely disappears once training data is scaled for the byte premium, meaning the extra bytes per character that non-Latin scripts cost in UTF-8. We therefore do not claim that more morpheme-aligned tokens will raise downstream scores. Our primary outcome is the optimization objective itself (reward reached per sample) and byte-normalized perplexity at matched data. MorphScore is only a diagnostic.
Charformer learns soft subwords with gradients instead of RL (Charformer). It sidesteps discrete saturation, at the price of a fixed downsampling structure. It is a comparison point, not the object of study. Work on the softmax bottleneck in small language models (Why do small language models underperform?) concerns the rank of the output layer, not step sizes, and is orthogonal.
Research Program
The program has three stages, in order of increasing realism.
Stage 1: an exactly solvable testbed. The reward is fixed: the log-likelihood of the segmentation under a frozen unigram vocabulary model plus a per-token cost. Under this reward the optimal segmentation of every word can be computed by Viterbi dynamic programming. This lets us measure the true suboptimality gap at each iteration. We can then plot its logarithm against iterations to tell linear from sublinear convergence. We can also count "wrong-saturated" positions, where the policy puts more than 0.99 probability on a boundary decision that disagrees with Viterbi. The prediction is specific. Under constant-step PPO, wrong-saturated positions persist and make up a larger share of decisions in high-fertility languages. Under geometric natural policy gradient they are resolved, and the log-gap falls linearly.
Stage 2: the end-to-end setting. We reproduce the end-to-end RL tokenizer training of You Can Learn Tokenization End-to-End with Reinforcement Learning, with a small language model co-trained on the segmenter's output. We then swap only the policy optimizer. The comparison covers PPO with the original schedule, natural policy gradient (or AMPO with a negative-entropy mirror map) at constant step, the same with pure geometric growth, and the same with the reset-triggered geometric schedule.
Stage 3: downstream transfer. Tokenizers from Stage 2 are frozen. Small encoders are trained on top of them and evaluated downstream.
The reset rule is the one new algorithmic piece. The schedule tracks the ratio of observed to predicted reward improvement over a short window. It multiplies the step by $\rho$ while that ratio stays above a threshold, and returns to $\eta_0$ when the ratio fails. The constant $\rho$ and the threshold get the same tuning budget as the baselines' learning rates.
Languages are chosen to separate the mechanism from confounds. Turkish and Basque are agglutinative. Hindi has low single-token retention. English is fusional. Japanese has the suffix byte-fallback pathology described by Gambardella et al.. Arabic and Amharic are non-concatenative: their words are formed by interleaving vowels into consonant roots, which Heinzerling and Strube argue no segmentation into contiguous substrings can model. For Arabic and Amharic we therefore predict that optimizer gains should be small, so they serve as a built-in negative control.
Baselines
The do-nothing reference is a fixed BPE or Unigram tokenizer with vocabulary size matched to the learned tokenizer's average vocabulary use, trained on the same text. It tells us whether RL tokenization is worth anything at our scale, separately from which optimizer drives it.
The strongest direct competitor is the end-to-end RL tokenizer as published, trained with PPO and its standard schedule. It is the only existing system that learns segmentation from task reward. For it, no reported result found on Lacuna for the RL tokenization method's benchmark scores, so we rerun it ourselves rather than quote it. Fairness means three things. All optimizers see the same text from FLORES-200 and the same co-trained language model architecture. They use the same number of environment samples. Each gets the same number of hyperparameter trials, about 20 per method, drawn from comparable ranges. Beating it means one of two things at the matched sample budget. In Stage 1, a lower final suboptimality gap with non-overlapping confidence intervals across five seeds. In Stage 2, lower byte-normalized perplexity on held-out FLORES-200 text.
Two optimizer baselines are strong because they attack saturation by other means. The first is Adam on the policy gradient with constant learning rate. Its per-coordinate normalization partly undoes vanishing gradient magnitudes. Note that The Implicit Bias of Adam on Separable Data shows this already speeds up margin growth over plain gradient descent. The second is entropy-regularized natural policy gradient with constant step, the textbook way to keep a softmax from saturating.
Two ablations isolate our ingredients. Constant-step natural policy gradient isolates the geometric schedule. Geometric growth without resets isolates the reset rule. We expect the no-reset ablation to win in Stage 1, where the reward is fixed, and to lose in Stage 2, where it is not.
As a tokenization-free reference on downstream data we include a CANINE-style character encoder (CANINE). That paper reports CANINE-S outperforming a comparable mBERT by 2.8 F1 on TyDi QA passage selection, with 28% fewer parameters. We do not expect a small learned-tokenizer model to match that absolute result. It anchors what removing tokenization altogether buys at similar parameter count.
Why not just…?
Why not just use Adam, which already rescales small gradients? This is the most serious threat. Adam's normalization is per-coordinate, not per-decision, so it cannot tell a wrong-saturated position from a correctly settled one that share the same parameters. Still, it may be enough in practice. Stage 1 settles this. If Adam at constant step clears wrong-saturated positions as fast as geometric natural policy gradient, we will report that the saturation pathology is already handled by adaptive optimizers. The contribution then narrows to the diagnostic testbed.
Why not just add entropy regularization so the policy never saturates? Entropy bonuses change the objective. The optimum shifts toward softer, more ambiguous segmentations, and the bonus weight must be decayed by hand. Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies obtains linear rates without any such regularization. Stage 1 measures the cost directly: the final Viterbi gap of the entropy-regularized policy at its best tuned weight, against the unregularized geometric schedule.
Why not just run PPO longer? Under saturation, constant-step convergence is sublinear, so more samples help but with sharply diminishing returns. We report full suboptimality-versus-samples curves rather than single endpoints. If PPO's curve reaches ours within a modest constant multiple of samples, for example under twofold, the practical case weakens and we will say so.
Why not skip RL and fit a Unigram tokenizer with expectation-maximization, or a supervised morphological segmenter? For the fixed objective of Stage 1, expectation-maximization over a unigram model is a strong, cheap solver. We include it there as an upper reference. Its limit is the end-to-end setting, where the reward comes from a co-trained model and has no closed form. The supervised-segmenter route is constrained by the MorphScore findings above: gold-morpheme alignment does not reliably predict downstream gains.
Proposed Experiments and Decisive Checks
The first decisive check is in Stage 1. On FLORES-200 text for the seven languages, geometric natural policy gradient should show a straight-line decline in log suboptimality, while constant-step methods bend toward a plateau. The count of wrong-saturated positions under PPO should correlate across languages with baseline fertility and single-token retention rate measured on the 1000MostCommonWords list. That correlation is what links the optimization story to the tokenization literature. If it is absent, the claim that saturation is a multilingual issue fails, even if the schedule still helps.
The second check is in Stage 2, the end-to-end setting. At equal samples, we compare byte-normalized held-out perplexity of the co-trained model. Per-token perplexity is uninformative when fertility differs across tokenizers. The reset-triggered schedule should beat both PPO and pure geometric growth in agglutinative languages and Hindi, and show little gain on Arabic and Amharic. A uniform gain across all languages, including the non-concatenative controls, would point to a generic optimizer effect rather than the boundary-saturation mechanism.
The third check is downstream. With tokenizers frozen, small encoders are fine-tuned on TyDi QA and MasakhaNER under identical budgets. We report F1 per language alongside fertility, single-token retention rate, and MorphScore of each learned tokenizer. Given the byte-premium result, we will treat improvements in perplexity without downstream gains as a legitimate and reportable outcome, not a failure to explain away. AfriMMLU and IrokoBench are reserved for a final check: grafting the best learned tokenizer onto a small pretrained multilingual model via vocabulary adaptation, following the recipe of Optimizing LLMs for Italian. That check would be reported only if it clears the near-chance floor such models sit at on these benchmarks.
References
- You Can Learn Tokenization End-to-End with Reinforcement Learning
- Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies
- A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergence
- Linear convergence for natural policy gradient with log-linear policy parametrization
- On the Linear Convergence of Policy Gradient Methods for Finite MDPs
- On the Linear Convergence of Natural Policy Gradient Algorithm
- Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning
- The Token Tax: Systematic Bias in Multilingual Tokenization
- Beyond Fertility: Analyzing STRR as a Metric for Multilingual Tokenization Evaluation
- Why do language models perform worse for morphologically complex languages?
- Charformer: Fast Character Transformers via Gradient-based Subword Tokenization
- Why do small language models underperform? Studying Language Model Saturation via the Softmax Bottleneck
- Inconsistent Tokenizations Cause Language Models to be Perplexed by Japanese Grammar
- Sequence Tagging with Contextual and Non-Contextual Subword Representations: A Multilingual Evaluation
- The Implicit Bias of Adam on Separable Data
- Canine: Pre-training an Efficient Tokenization-Free Encoder for Language Representation
- Optimizing LLMs for Italian: Reducing Token Fertility and Enhancing Efficiency Through Vocabulary Adaptation