How Far Should Tokenization Go? Predictive Effectiveness and Relational Losslessness

Yi Wang

cs.LGAug 18, 2026

How Far Should Tokenization Go? Predictive Effectiveness and Relational Losslessness

Authors: Yi Wang

Organizations: Department of Electronic Engineering, Tsinghua University

Abstract

GPT-style models have achieved remarkable success with finite vocabularies of reusable tokens, making the token interface a central component of modern sequence modeling. Symbolic music appears naturally compatible with this paradigm: it consists of discrete note events and recurring structures such as chords, motifs, and phrases. However, when tokenization moves beyond language, the interface must be specified for each domain. Existing work offers many effective designs, but no unified criterion for deciding what tokenization should represent and how far it should go. Using predictive codelength as a common criterion, we formulate the Effectiveness--Losslessness Framework to define where tokenization should begin and where it should end. The Fact--Token Boundary marks where observation-determined structure should enter the token interface, through operations such as coordinate construction. Within this interface, the resulting carrier may be reversibly recoded without changing the represented facts. The Token--State Boundary marks where tokenization should stop: relations that depend on context should remain for model-state computation rather than being fixed in advance by the tokenizer. We validate the framework through controlled multi-seed symbolic-music experiments, with an independent-corpus replication of the temporal intervention. Making musical time explicit consistently reduces predictive code and also improves pitch and duration prediction, while tonal-frame canonicalization and pitch factorization provide further gains. Fixed circle-of-fifths pitch coordinates instead increase predictive code, suggesting that imposing a fixed pitch relation before context can burden prediction. Reversible BPE substantially shortens the carrier but increases predictive codelength in every seed, showing that carrier compaction alone does not guarantee predictive gain.

Figures & tables

Panel of Figure 1 — Figure 1: The Effectiveness–Losslessness Framework. Predictive Effectiveness governs what enters the token interface, Relational Losslessness governs where it stops, and reversible carrier coding is evaluated separately.

Figure 2: Pop1K7 clean-test codelength per declared musical fact. Error bars show sample SD over three preregistered seeds. Panel (a) reports the staged A–D musical-time family. Panel (b) contains separate matched comparisons: D/H estimates pitch-factorization gain; D/E and H/I estimate relational excess for chromatic and fifths commitments, respectively. Panel (c) reports the matched F/G canonicalization family. G includes a conservative four-bit side code per window.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Item	Frozen value
Dataset	Pop1K7 constant-4/4 piano arrangements; source-song split before windowing
Songs / windows	1,378 / 18,460 train; 184 / 2,011 validation; 185 / 1,979 sealed test
Carrier and target	A–I: exact Note/REST stream with a separate termination target and Type $\rightarrow$ Time $\rightarrow$ Pitch $\rightarrow$ Duration factors; J/K: lossless Bar / Position /pitch-or- Rest /duration stream, with train-only reversible BPE in K
Accounting	numerator: all Note/REST factor bits, EOS overhead, and required per-sample side bits; denominator: declared Note/REST facts only
Backbone	16 Transformer layers, width 64, 4 heads, FFN 128, dropout 0; J/K use the same causal backbone with a serialized-token input/output head
Parameters	815,571 total; effective trainable counts are A 809,475; B 811,079; C 810,499; D/F/G 812,815; E/I 805,455; H 813,519. Vocabulary-dependent J/K totals are 689,349 / 804,675

Appendix

Table 1: Frozen source, learner, resource, and accounting contract.

Figure 3: Exposure-matched validation dynamics for the three frozen Pop1K7 representation families. Thin lines show individual preregistered seeds; thick lines show the three-seed mean; open markers identify the independently validation-selected checkpoint for each seed. The plot begins at 100 target-equivalent epochs to remove the initialization transient, while all source observations remain in the released curve table. Every run continues to the same 2,000-epoch maximum budget. A–D and D–H–I use the full split; F–G use their exactly matched high-confidence subset. Curves are rebased to declared facts; G includes the constant four-bit side charge per window. No test value enters training, plotting, or checkpoint selection.

Family	Arm	Active interface	Validation	Held-out test
Coordinate: time	A	raw pitch identity; generic sequence position	$6.98064\pm 0.01633$	$7.11618\pm 0.00765$
Coordinate: time	B	A + learned absolute onset/bar lookup	$6.32519\pm 0.02835$	$6.42223\pm 0.02730$
Coordinate: time	C	raw pitch; unary ordered and multi-scale metric time replacing generic/absolute position features	$6.23396\pm 0.04671$	$6.32662\pm 0.04850$
Coordinate: time	D	C + pairwise onset, meter, bar, and beat relations	$6.16952\pm 0.00681$	$6.26809\pm 0.01361$
Relation: chromatic	E	D time; chromatic-circle phase + absolute register replacing categorical pitch-class identity	$6.18494\pm 0.03436$	$6.27841\pm 0.03446$
Coordinate: canonicalization	F	original absolute pitch on the matched music21 high-confidence subset	$6.52727\pm 0.00848$	$6.48686\pm 0.01038$

Appendix

Table 2: Frozen Pop1K7 representation arms. A–E and H–I use the full original-pitch split; F–G use the exactly matched high-confidence tonal-frame subset. Values are bits per declared fact; G includes the conservative per-window side code. Absolute scores are compared only within matched families.

Ledger	F code	G code	$G_{\rm coord}(F\!\rightarrow\!G)$
Model code only	6.48686	6.36174	0.12512
4 bits / 8-bar window	6.48686	6.39631	0.09055
4 bits / source song	6.48686	6.36478	0.12208

Appendix

Table 3: Clean-test F/G side-information ledger in bits per declared fact.

Comparison	Class	Total	Type	Time	Pitch	Duration	Side
B $-$ A	$G_{\rm coord}$	$-0.693948$	$-0.020283$	$-0.248170$	$-0.243551$	$-0.181944$	$0$
C $-$ B	$G_{\rm coord}$	$-0.095607$	$-0.000855$	$-0.033450$	$-0.052890$	$-0.008412$	$0$
D $-$ C	$G_{\rm coord}$	$-0.058531$	$-0.000165$	$-0.005304$	$-0.043773$	$-0.009290$	$0$
D $-$ A	$G_{\rm coord}$	$-0.848087$	$-0.021304$	$-0.286924$	$-0.340213$	$-0.199646$	$0$
E $-$ D	$E_{\rm rel}$	$+0.010321$	$-0.000059$	$-0.006559$	$+0.017385$	$-0.000445$	$0$
G $-$ F	$G_{\rm coord}$	$-0.090548$	$+0.000003$	$+0.002641$	$-0.137238$	$+0.009474$	$+0.034573$

Appendix

Table 4: Held-out paired changes in bits per declared fact. Negative values favor the left arm. Class is assigned by intervention; Side is nonzero only for G.

Figure 4: Secondary context-relation probe. Replacing either side degrades compatibility prediction; replacing both approaches the target-only control.

Condition	bits/event	change from Full
Full	$3.5394$	—
Left	$3.8083$	$+0.2689$
Right	$3.8117$	$+0.2723$
Shuffled	$4.2084$	$+0.6690$

Appendix

Table 5: Fixed-target context intervention in its native predictive units.

Interface	serialized targets/fact	held-out bits/fact
J: uncompressed serialized coordinate stream	3.563	$5.96305\pm 0.10235$
K: J + train-only reversible BPE	1.538	$6.77367\pm 0.05643$
$K-J$	$-2.025$	$+0.81061\pm 0.15007$

Appendix

Table 6: Pop1K7 fixed-coordinate carrier-coding control. Serialized-target ratios count one EOS target per window; predictive bits include EOS and are normalized by declared Note/REST facts. Values are mean

\pm

sample SD over three preregistered seeds.

Comparison	mean difference	seed direction	interpretation
J–D	$-0.30504\pm 0.11508$	3/3 J below D	descriptive only
K–D	$+0.50558\pm 0.04366$	3/3 K above D	descriptive only

Appendix

Table 7: Descriptive Pop1K7 full-interface comparisons in the common paper ledger. Differences are left minus right; values are mean

\pm

sample SD.

Arm/seed	validation	clean test	test D $-$ A
A: raw sequence	$12.56786\pm 0.14342$	$12.33993\pm 0.14311$	—
D: musical-time coordinates	$\mathbf{12.39563\pm 0.15434}$	$\mathbf{12.22855\pm 0.18073}$	$-0.11139$
20260814	—	A: 12.37089; D: 12.34337	$-0.02752$
20260815	—	A: 12.18388; D: 12.02022	$-0.16366$
20260816	—	A: 12.46503; D: 12.32205	$-0.14298$

Appendix

Table 8: Frozen ComMU 4/4 A/D replication. Predictive bits include sequence termination and are normalized by declared Note/REST facts. Summary rows report mean

\pm

sample SD over three preregistered seeds; lower is better.

Tokenization

See all 45 papers

May 13, 2026

Effective Context in Transformers: An Analysis of Fragmentation and Tokenization

Transformers predict over a representation of a sequence. The same data can be written as bytes, characters, or subword tokens, and these representations may be lossless. Yet, under a fixed context window, they need not expose the same information to the model. This raises a basic question: how does the choice of representation change what a finite-context predictor can achieve? We study this question on Markov sources and uncover two complementary phenomena. First, we observe that moving to smaller representation units can hurt prediction even when the context window is enlarged to cover the relevant source history. To explain this, we introduce fragmentation: a lossless recoding that replaces each source symbol by several smaller units. We prove that fragmentation can strictly increase the optimal finite-context log-loss, showing that the gap is not merely an optimization or capacity issue, but can be intrinsic to the representation. This gives a theoretical account of the finite-context gap observed in byte- and character-level models such as ByT5 and CANINE relative to subword-tokenized models. Second, we study the opposite direction: greedy tokenization -- BPE, WordPiece, and related methods -- which groups source symbols into larger units. We show that tokenization can make a short token window behave like a longer source-context window, and we give a loss guarantee describing when this is achievable. The guarantee depends on how reliably token windows span the needed source history, together with the compression rate of the tokenizer. This also yields a simple diagnostic for real tokenizers: measuring how much source context a fixed token window reliably contains. Together, the two directions establish a finite-context information-theoretic framework for reasoning about representation choices in Transformers.

Amirmehdi Jafari Fesharaki, Mohammadamin Rami, Aslan Tchamkerten

Department of Communications and Electronics Institut Polytechnique de Paris

Language Modeling Subword Tokenization Tokenization

Ask PDF

Aug 18, 2026

TokEval: A Tokenizer Evaluation Suite

Language model tokenizers are typically selected with minimal evaluation, despite the fact that their design choices directly impact model capabilities. This can be partly attributed to a limited understanding of which tokenizer properties affect which aspects of downstream performance. We introduce TokEval, a framework of tokenizer evaluation metrics that goes beyond standard measures like fertility and compression rate to capture linguistically and structurally meaningful properties, e.g., UTF-8 character boundary integrity and digit place-value boundary alignment for mathematics. To validate whether these metrics are predictive of downstream model performance, we conduct controlled language model pretraining experiments, varying solely the tokenizers' training data mixture, pretokenization strategy, and training algorithm. We evaluate the resulting models on bits-per-byte (a tokenizer-agnostic version of perplexity) and several benchmarks, spanning linguistic understanding, mathematical reasoning, and code generation. Our experiments suggest that different intrinsic properties have different impacts on model abilities: information-theoretic metrics predict language modeling abilities (Spearman rho up to 0.80), while structure-sensitive metrics, such as those measuring digit and line-break handling, correlate with task accuracy. We hope TokEval enables more principled tokenizer evaluation, replacing pretraining sweeps with intrinsic measurement wherever the two agree.

Clara Meister

EPFL

LLM Evaluation Tokenization Tokenization in Language Models

Ask PDF

Aug 30, 2026

Learning Representations through Token Prediction: Geometry, Approximation, and Downstream Guarantees

Token prediction is a central pre-training objective for modern language models. Despite its empirical success, why token prediction learns broadly useful representations remains incompletely understood. We develop a statistical framework connecting token prediction with representation geometry, encoder approximation, and downstream performance. Under a softmax prediction head, we show that accurate token prediction organizes token embeddings according to similarities between the distributions of contexts in which different token types appear, as measured by Hellinger distance, with explicit errors governed by prediction accuracy and token frequency. Meanwhile, the contextual representation provides a low-dimensional coordinate for the conditional distribution of the target token relative to these embeddings. We further introduce a self-consistency principle showing that repeated applications of a shared representation block can progressively refine the contextual representation without introducing additional block parameters. Among representations with the same prediction accuracy, this recurrent construction favors those that can be stably reconstructed from their contexts. Finally, we establish downstream guarantees for token generation, token community recovery, and classification by a linear probe, showing how prediction accuracy and recovered geometry translate into performance beyond the pre-training objective. Together, these results explain how the simple objective of predicting tokens can recover semantic geometry and produce broadly useful representations. A controlled simulation illustrates the theoretical mechanisms.

Shulei Wang

Department of Statistics, University of Illinois at Urbana-Champaign, 605 E. Springfield Ave., Champaign, IL 61820

Language Model Pretraining Next-Token Prediction Predictive Representation Learning Representation Geometry in Language Models Semantic Representation Learning

Ask PDF

Abstract

Tokenization

Explore similar work

Effective Context in Transformers: An Analysis of Fragmentation and Tokenization

TokEval: A Tokenizer Evaluation Suite

Learning Representations through Token Prediction: Geometry, Approximation, and Downstream Guarantees