Research map / Architectures and efficiency / Attention and transformers
Effective Context in Transformers: An Analysis of Fragmentation and Tokenization
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.
Studies how lossless representation changes the best finite-context log-loss on Markov sources, proving fragmentation can intrinsically increase loss and that greedy tokenization can make a short token window act like a longer source window, with a typical-span loss guarantee.
Problem
How does the choice of lossless representation (bytes, characters, subword tokens) change what a fixed finite-context predictor can achieve on sequence data, and when does tokenization extend effective context?
Approach
Formalizes fragmentation (lossless recoding into smaller units) and proves an exact decomposition of excess loss into context-deficit and phase-ambiguity terms; for greedy tokenizers, shows a predictor transfer from source context w_s to token window w and a typical-span tokenization gain bound L_tok(w) <= L_Y(w_s) + eps*R*log|Y|.
Key results
- Fragmented predictor converges to strictly larger loss than source-level predictor even when window covers the relevant source history (empirical, Markov source).
- Theorem: L_X^frag(Mw) - L_Y(w) = context deficit + M*phase ambiguity; context deficit vanishes for w>k.
- Tokenization gain: L_tok(w) <= L_Y(w_s) + eps*R*log2|Y| for (eps,w,w_s)-typical tokenizers; with budget-d learned greedy tokenizer, w_d ~ (3/4) w log d.
Surprising findings
- A globally lossless refinement (fragmentation) can strictly increase the optimal finite-context loss even when the window covers the nominal source span.
- Tokenization appears to improve convergence speed, though this is left open.
Limitations
- Results characterize achievable loss by any finite-context predictor, not whether Transformers realize or train to them.
- Typical-span criterion gives a tokenizer quality diagnostic, not a complete tokenizer design method.
- Experiments are on synthetic Markov sources; real tokenizers only addressed through diagnostic.
Experimental setup
Datasets: synthetic stationary Markov sources (binary order-12; finite-order sources)
Benchmarks: synthetic Markov source log-loss
Metrics: bits per source symbol log-loss entropy rate gap
Baselines: ByT5 CANINE
Builds on: BPE WordPiece LZW ByT5 CANINE
Closest papers by meaning
- An Analysis of Tokenization: Transformers under Markov Data (NeurIPS 2024 · similarity 0.91)
- Repeat After Me: Transformers are Better than State Space Models at Copying (ICML 2024 · similarity 0.89)
- Distilling Sequential Computation in Transformer Language Models (NeurIPS 2026 · similarity 0.89)
- Beyond Attention: Breaking the Limits of Transformer Context Length with Recurrent Memory (AAAI 2024 · similarity 0.88)
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.88)
- Compress, Gather, and Recompute: REFORMing Long-Context Processing in Transformers (NeurIPS 2025 · similarity 0.88)
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.