Research map / Large language models / Language, safety and interpretability
Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that tokenized LMs have a "tokenization bias" relative to their byte-level equivalents and proposes an inference-time next-byte sampling algorithm (via the Byte-Token Representation Lemma) that removes it, applied to FIM code infilling and cross-vocabulary model ensembles.
Problem
Tokenized language models assign next-byte predictions that differ from the statistically equivalent byte-level process, causing failures when prompts end mid-token (e.g., FIM code completion) and preventing ensembling of models with different vocabularies.
Approach
The Byte-Token Representation Lemma expresses the byte-level prefix probability as a sum over cover encodings of the prefix, enabling exact next-byte probabilities from any tokenized LM with an O(1) number of model runs per byte step, without retraining; byte distributions can then be averaged across models with different tokenizers.
Key results
- On HumanEval random-span FIM with CodeLlama-7b in SPM mode, byte-level prediction improves over token-level baselines by about 18% (per abstract), outperforming token healing.
- Ensembling Yi-Coder-1.5B and CodeLlama2-13b via byte-level averaging improves HumanEval by up to 3.7% over individual models.
- Beam search with byte-level predictions gives up to 2.9% further improvement, reaching 67.7 pass rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| next-byte prediction (byte-level sampling) instead of token-level prediction in SPM FIM mode | CodeLlama-7b · HumanEval Random Span FIM | pass rate: up to 18% improvement reported in abstract | Helped |
| beam search with width 2 and 4 added to byte-level FIM decoding (ablation) | CodeLlama-7b byte-level predictions · HumanEval Random Span FIM | pass rate: up to 2.9%, best 67.7 | Helped |
| ensembling top-2 models via byte-level averaging | Yi-1.5-6B and Mistral-7B-v0.3 (GSM8K divergent pair) · GSM8K | accuracy | Hurt |
| ensembling top-2 models via byte-level averaging | reasoning, knowledge, and coding benchmarks with comparable members · multiple knowledge, reasoning, coding benchmarks | accuracy: up to 3.7% on HumanEval for Yi-Coder-1.5B + CodeLlama2-13b | Helped |
| token healing as a fix for SPM FIM tokenization issues | CodeLlama-7b · HumanEval Random Span FIM | pass rate | No clear effect |
Surprising findings
- Byte-level greedy generation outperforms token-level greedy generation on FIM, despite tokens spanning multiple bytes.
- On GSM8K the ensemble underperforms when member models diverge strongly (Yi-1.5-6B outperforms Mistral-7B-v0.3 by 20%).
Limitations
- Notable memory consumption in the current implementation.
- Linear additional computational cost since one token covers multiple bytes.
- Analysis covers only single-token predictions and does not explain arithmetic failures or cumulative bias over long generations.
Experimental setup
Datasets: HumanEval Random Span infilling benchmark synthetic 3rd-order Markov chain data
Benchmarks: HumanEval Random Span infilling MMLU PIQA GSM8K HumanEval
Metrics: pass rate accuracy
Baselines: token healing token alignment next-token prediction voting
Builds on: token healing BPE BPE dropout
Closest papers by meaning
- From Language Models over Tokens to Language Models over Characters (ICML 2025 · similarity 0.90)
- Language Models over Canonical Byte-Pair Encodings (ICML 2025 · similarity 0.90)
- Model-Aware Tokenizer Transfer (NeurIPS 2026 · similarity 0.90)
- The Foundations of Tokenization: Statistical and Computational Concerns (ICLR 2025 · similarity 0.90)
- An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.89)
- From Bytes to Ideas: Language Modeling with Autoregressive U-Nets (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.