Source-linked AI summary
Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations
Brian Siyuan Zheng, Alisa Liu, Orevaoghene Ahia, Jonathan Hayase, Yejin Choi, Noah A. Smith
TL;DR
The paper asks whether language models trained with deterministic tokenizers can adapt at inference time to other valid tokenizations of the same text. The authors compare instruction-tuned models across benchmarks using random and character-level tokenizations, then test task-specific segmentations and examine robustness across training stages. On average across benchmarks, QWEN-2.5 retains 93.4% of its performance with random and 90.8% with character-level tokenization; for LLAMA-3.1-INSTRUCT, character-level tokenization yields up to +14% on string/code tasks and right-aligned digit groups +33% on large-number arithmetic.
Problem
The paper asks whether language models trained with deterministic tokenizers can adapt at inference time to other valid tokenizations of the same text.
Source: §1 · p. 1Method
The authors compare instruction-tuned models across benchmarks using random and character-level tokenizations, then test task-specific segmentations and examine robustness across training stages.
Source: §1 · p. 2Results
On average across benchmarks, QWEN-2.5 retains 93.4% of its performance with random and 90.8% with character-level tokenization; for LLAMA-3.1-INSTRUCT, character-level tokenization yields up to +14% on string/code tasks and right-aligned digit groups +33% on large-number arithmetic.
Source: §1 · p. 2, §2.3 · p. 4Takeaways & Limitations
Alternative tokenizations can be used at inference time to improve performance on some string, code, and large-number tasks without fine-tuning.
Source: §1 · p. 2The authors identify questions left for future work.
Source: §2 · p. 16
Abstract
from arXiv · showhide
Modern tokenizers employ deterministic algorithms to map text into a single "canonical" token sequence, yet the same string can be encoded as many non-canonical tokenizations using the tokenizer vocabulary. In this work, we investigate the robustness of LMs to text encoded with non-canonical tokenizations entirely unseen during training. Surprisingly, when evaluated across 20 benchmarks, we find that instruction-tuned models retain up to 93.4% of their original performance when given a randomly sampled tokenization, and 90.8% with character-level tokenization. We see that overall stronger models tend to be more robust, and robustness diminishes as the tokenization departs farther from the canonical form. Motivated by these results, we then identify settings where non-canonical tokenization schemes can *improve* performance, finding that character-level segmentation improves string manipulation and code understanding tasks by up to +14%, and right-aligned digit grouping enhances large-number arithmetic by +33%. Finally, we investigate the source of this robustness, finding that it arises in the instruction-tuning phase. We show that while both base and post-trained models grasp the semantics of non-canonical tokenizations (perceiving them as containing misspellings), base models try to mimic the imagined mistakes and degenerate into nonsensical output, while post-trained models are committed to fluent responses. Overall, our findings suggest that models are less tied to their tokenizer than previously believed, and demonstrate the promise of intervening on tokenization at inference time to boost performance.
1 Introduction
The paper asks whether language models can handle text encoded in non-canonical ways despite deterministic training tokenizers, and tests whether alternative segmentations can also help. Across benchmarks, instruction-tuned models retain substantial performance, while robustness generally declines with finer segmentation; some task-specific tokenizations improve results.
1 Introduction
- Deterministic subword tokenization obscures token orthography, a concern raised for numbers and morphologically rich languages; the paper tests adaptation to alternate tokenizations at inference time.A given string can have many valid token sequences using the same vocabulary, but their effect in generation has received less attention.Source: §1 · p. 1, §2.1 · p. 3
- Character-level tokenization improves string manipulation and code understanding by up to +14%, while right-aligned digit groups improve large-number arithmetic by +33%.The gains are reported for LLAMA-3.1-INSTRUCT without model fine-tuning.Source: §1 · p. 2
- The paper investigates why robustness appears after training: base and post-trained models perceive misspellings, but base models mimic them and produce nonsense while instruction-tuned models remain fluent.The authors locate robustness in supervised instruction-tuning and identify separation of instruction and response into distinct conversational turns as key.Source: §1 · p. 2
2.3 Results
- 93.4% of QWEN-2.5’s performance is retained with random tokenization and 90.8% with character-level tokenization; LLAMA-3.1 retains 87.7% and 79.4%, and OLMO-2 retains 73.1% and 62.0%.Retention rankings match the models’ rankings in absolute accuracy with canonical tokenization.Source: Table 1 · p. 3, §2.3 · p. 4
2.2 Setup
- The evaluation compares three instruction-tuned models across 20 benchmarks using random and character-level tokenization alongside canonical inputs.Random tokenization samples a more granular valid segmentation; character-level tokenization uses character tokens.Source: §2.2 · pp. 3–4
2.3 Results
- Models retain performance better on short-answer than multiple-choice benchmarks, and generally produce correctly tokenized outputs even after non-canonical inputs.The authors hypothesize that short-answer models benefit from conditioning on recent, correctly tokenized context.Source: §2.3 · p. 4
2.4 Analysis: How does granularity of the tokenization affect robustness?
- Finer-grained tokenizations generally reduce performance retention, with a statistically significant negative correlation across tasks (Kendall’s τ, p = 0.003).Granularity is measured by the token-length ratio relative to canonical tokenization; BPE dropout varies that ratio.Source: §2.4 · p. 4, Figure 2 · p. 4
3 Can non-canonical tokenizations improve model performance?
The section tests whether task-specific alternative tokenizations help, then traces robustness to non-canonical inputs to instruction tuning and dialogue formatting. It distinguishes recognizing those inputs from producing fluent continuations.
3.1 Tasks
- The task suite uses character-level inputs except for arithmetic, which uses right-to-left three-digit groups for 10-digit addition and subtraction.The arithmetic dataset contains 1,000 questions; the code-description task spans six programming languages.Source: §3.1 · p. 5
3.2 Results
- +14.3% on code description and +33.7% on arithmetic: alternative tokenizations outperform canonical inputs across all constructed tasks.The study uses character-level inputs for the first four tasks and right-to-left three-digit groups for arithmetic.Source: §3.2 · p. 5, Table 3 · p. 6
4.1 When does robustness appear in model training?
- Across OLMO2 and LLAMA-3.1, base models fail to produce sensible character-tokenized continuations, while post-trained models improve on all three generation metrics, mostly during SFT.Base models score at best 0.317 on spelling and 0.260 on grammaticality.Source: §4.1 · pp. 6–7, Figure 3 · p. 7
4.2 Why do instruction-tuned models become robust?
- Full-sequence gradients and a simple question-answer template preserve robustness to non-canonical tokenizations; removing the chat template causes incoherent generations and drops spelling from 0.786 in the no-ablation setting to 0.0698.Inserting the chat template into pretraining-style data while removing the instruction also leaves spelling and grammaticality low, at 0.181 and 0.158, respectively.Source: §4.2 · pp. 7–8
4.3 Disentangling understanding from generation
- Base and instruct models both score above 90% on Word Repeat and perform at random on misspelling identification, while base models mimic perceived errors in generation.The authors’ explanation is that both model types recognize the word but perceive non-canonical forms as misspelled; instruction-tuned models produce fluent responses despite that perception.Source: §4.3 · p. 8, Table 4 · p. 8
5 Related Work
Related work frames tokenization as both a potential obstacle to orthographic understanding and a setting where models may retain character-level knowledge. This work studies non-canonical inputs systematically and distinguishes them from partial-token generation failures.
Character-level understanding in tokenizer-based models
- Prior work has proposed linguistically informed tokenization [25] [71] and training-time tokenization variation [52] [60] to address tokenization-related challenges.Other evidence suggests larger models retain character-level information in embeddings [27] and compose arbitrary token sequences [19, 33].Source: §5 · p. 9
Partial token problem
- Partial-token failures concern prompts ending inside a valid token, whereas these results concern understanding non-canonical sequences in context [69] [66] [22].The paper notes that models may understand non-canonical context histories even when they are unlikely to generate non-canonical tokenizations.Source: §5 · p. 9
Non-canonical tokenizations
- Earlier work studied non-canonical tokenization in self-supervised evaluation [28] and adversarial attacks [29]; Geh et al. examined adversarial unsafe completions.This paper presents a systematic benchmark study of robustness and investigates its source.Source: §5 · p. 9
- Algorithms for character- or byte-level sampling from tokenizer-based models [50] [65] [3] [22] also show that models can condition on and produce sequences over another sub-vocabulary.Source: §5 · p. 9
6 Conclusion
The conclusion reports that instruction-tuned models accommodate non-canonical tokenizations and that alternative tokenizations can improve performance in some domains. The authors state that the abstract and introduction claims are supported by the paper.
6 Conclusion
- Instruction-tuned models accommodate token sequences unseen during training, and some alternative text representations improve performance in arithmetic or code.The conclusion also notes that base and instruct models perceive the semantics of non-canonical tokenizations, but only instruct models provide fluent continuations.Source: §6 · p. 9
- The conclusion presents post-training tokenization changes as a way to seek more optimal text representations after pretraining.The authors frame this as potential, not as a demonstrated general solution.Source: §6 · p. 9
1. Claims
- The authors answer yes when asked whether the abstract and introduction accurately reflect the paper’s contributions and scope.The paper’s checklist says its claims are supported in the paper.Source: §1 · p. 16
2. Limitations
The paper identifies future questions and distinguishes hypotheses from evidence-supported claims. It also reports that proof assumptions and experimental reproducibility information are provided in the appendix, and that code is planned for release.
2. Limitations
- The authors identify questions for future work and distinguish hypotheses from claims supported by evidence.The checklist marks discussion of the work’s limitations as present.Source: §2 · p. 16
3. Theory assumptions and proofs
- The authors report that the appendix contains a complete proof and its full set of assumptions.The checklist marks this item as satisfied.Source: §3 · pp. 16–17
4. Experimental result reproducibility
- The authors say experimental reproducibility information will be provided in the appendix.The checklist marks disclosure of information needed to reproduce the main results as satisfied.Source: §4 · p. 17
5. Open access to data and code
- The authors plan to open-source their code shortly after submission.The checklist marks open access to data and code as satisfied.Source: §5 · p. 18
6. Experimental setting/details
The checklist says experimental details and compute information will be provided in the appendix, and that the paper reports statistical significance information and conforms to the NeurIPS Code of Ethics. It marks broader impacts as not applicable because the work has no immediate societal impact.
6. Experimental setting/details
- The authors say experimental setting details will be provided in the appendix.The checklist marks the setting-details item as satisfied.Source: §6 · p. 18
7. Experiment statistical significance
- The authors report providing standard-deviation and statistical-significance information.The checklist marks the statistical-significance item as satisfied.Source: §7 · p. 18
8. Experiments compute resources
- The authors say compute-resource information will be provided in the appendix.The checklist marks the compute-resources item as satisfied.Source: §8 · p. 19
9. Code of ethics
- The authors state that their research conforms to the NeurIPS Code of Ethics.The checklist marks the ethics item as satisfied.Source: §9 · p. 19
10. Broader impacts
- The authors mark broader impacts as not applicable, stating that the work has no immediate societal impact.This is the stated basis for the checklist response.Source: §10 · p. 19
11. Safeguards
The checklist marks safeguards as not applicable because the paper’s data pose no high misuse risk. It also reports asset attribution and licensing, planned dataset release, no human-subject experiments, and no LLM use in the research.
11. Safeguards
- The authors mark safeguards as not applicable because no data from the paper has high risk of misuse.This is the stated basis for the checklist response.Source: §11 · p. 20
12. Licenses for existing assets
- The authors state that they cite asset creators and comply with the licenses of assets used.The checklist marks the asset-credit and licensing item as satisfied.Source: §12 · p. 20
13. New assets
- The authors say they will release the datasets they created.The checklist marks new-asset documentation as satisfied.Source: §13 · p. 21
14. Crowdsourcing and research with human subjects
- The authors state that they conducted no experiments with human subjects.The checklist marks the human-subjects item as not applicable.Source: §14 · p. 21
16. Declaration of LLM usage
- The authors state that they did not use LLMs to conduct the research.The checklist marks the LLM-usage item as not applicable.Source: §16 · pp. 21–22
A Random Non-Canonical Tokenization
The section presents a recursive method for randomly splitting canonical tokens into vocabulary-valid smaller tokens, then proves that every valid finer-grained segmentation has equal probability of selection.
A.1 Algorithm
- The algorithm recursively splits each canonical token into vocabulary tokens and selects among valid segmentations with equal probability.It weights each next-token choice by the number of valid completions from that point.Source: §A.1 · p. 23, A Random Non-Canonical Tokenization · p. 23
A.2 Proof
- The proof concludes that each complete segmentation of the whole token is selected uniformly, with probability 1/W(0).W(i) counts valid completions from index i; the child-choice factor cancels, making the probability independent of the chosen child.Source: §A.2 · pp. 23–24
A.1 Algorithm
- Memoized COUNTSEGMENTS counts valid completions, and BUILDSEGMENTS uses those counts as weights when choosing each next token.If no valid segmentation exists, SEGMENTTOKEN returns an empty result.Source: §A.2 · p. 24
B Evaluation Details
The evaluation details span multiple-choice, short-answer, and generation-judged benchmarks, with task-specific prompts and scoring procedures. The section also specifies sampling and evaluator choices for MMLU and Alpaca Eval.
B.1 General benchmarks
- Short-answer tasks use “You are a helpful assistant,” while the multiple-choice prompt requests only the answer without extra reasoning or explanation.Table 5 is identified as containing system prompts for the tasks.Source: §B.1 · p. 25, Table 5 · p. 26
- Alpaca Eval reports raw win rate for perturbed-model generations judged by Alpaca Eval GPT-4.The passage says this evaluator has the highest reported Spearman and Pearson correlations with human annotators.Source: §B.1 · p. 25
- Multiple-choice evaluations include commonsense, cause-and-effect, physical reasoning, natural continuations, and pronoun-reference tasks.Winogrande uses the Winograd format with more questions and greater difficulty.Source: §B.1 · pp. 25–26
- Other benchmarks cover string structure, passage reasoning, multistep commonsense, fictitious-unlearning retention, and context-supported true-or-false questions.WikidataQA tests completion of factual statements.Source: §B.1 · pp. 25–26
- Short-answer evaluations include Jeopardy questions, world knowledge, competition-level and grade-school math, and sampled MMLU questions.The MMLU evaluation sampled 500 questions and instructed models to output one answer without explanation.Source: §B.1 · pp. 25–26
B.2 Constructed Benchmarks
The constructed benchmarks test character counting, acronym generation, code comprehension, and arithmetic through task-specific prompts and output checks.
B.2 Constructed Benchmarks
- The character-counting task asks for occurrences of the most frequent character in a 10-character word and scores the last generated number.Responses without a number are incorrect.Source: §B.2 · p. 26
- The acronym task asks for words whose initials form a sampled five-character string and checks the first character of each whitespace-delimited word.Source: §B.2 · p. 26
- The code-line task asks the model to choose the best description of a code snippet from four options.Source: §B.2 · p. 26
- The arithmetic task tests addition or subtraction with 10-digit numbers and compares regex-extracted outputs with the ground truth.Source: §B.2 · p. 26
B.3 Metrics of generation quality
The section defines spelling, grammaticality, and win-rate evaluation procedures, then gives ablation-format and fine-tuning details. It also identifies a table reporting character-level robustness on Chinese text.
B.4 Ablation Settings
- Table 6 presents data-format examples for the §4.2 ablations, while Table 7 reports QWEN-2.5-7B-INSTRUCT’s robustness to character-level Chinese text.Source: Table 6 · p. 27, Table 7 · p. 28
B.3 Metrics of generation quality
- Spelling uses the 10,000 most frequent English words in Google’s trillion-word corpus, excluding single-character words.This avoids inflated scores when base models repeatedly generate one letter.Source: §B.3 · p. 27
- Grammaticality is scored only for generations with spelling scores of at least 0.5; otherwise, it is set to zero.The passage notes that repeated letters or counting can appear grammatical despite being gibberish.Source: §B.3 · p. 27
- Win rate compares against canonical-tokenization generations in §4.1 and No Ablation character-level generations in §4.2.No Ablation has a 50% win rate by construction.Source: §B.3 · p. 27
B.4 Ablation Settings
- Fine-tuning used a linear learning-rate scheduler, sequence length 4096, per-device batch size 2, 20 gradient-accumulation steps, and 8 L40S GPUs.The code was forked from allenai/open-instruct.Source: §B.4 · p. 27
B.5 Disentangling understanding from generation
The section reports that character-level tokenization causes only an approximately 3% performance drop on two Chinese tasks. It also describes prompts designed to distinguish word repetition with typo correction from misspelling recognition.
B.5 Disentangling understanding from generation
- B.5 uses 500 sampled English words to test whether models repeat them while correcting typos, with canonical and character-level examples.Examples include “guarantees” in the canonical form and “revelation” with character-level tokenization.Source: §B.5 · p. 28
- B.5 separately tests misspelling recognition using single-character insertions, deletions, or substitutions and asks models to choose the misspelled option.The examples contrast character-level “farmer” with canonical “farme,” alongside nine additional in-context examples.Source: §B.5 · p. 28
C.1 Evaluation on Chinese Benchmarks
- ∼3% performance drops on each of Chinese GSM and Chinese MMLU with character-level tokenization for QWEN-2.5-7B-INSTRUCT.LLAMA-3.1-8B-INSTRUCT and OLMO-2-7B-INSTRUCT were excluded because they do not officially support Chinese.Source: §C.1 · p. 28