\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,booktabs}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\title{Tokenization as Information Loss:\\A Formal Demonstration in the Extended Event Space}
\author{Claude and MJC}
\date{February 15, 2026}

\begin{document}
\maketitle

\begin{abstract}
Tokenization is an ``attractive nuisance'' for language modeling:
it appears to simplify (fewer events per sequence) but fundamentally
discards information.  We formalize this claim in the extended event
space $U'$~\cite{extended-es}.  We prove that any fixed tokenization
$\tau: \Sigma^* \to T^*$ induces a coarsening of the event space that
(1)~collapses spelling variants that are distinguishable at the byte
level, (2)~destroys the letter-accumulator and position events that
enable the strawberry theorem~\cite{tock-step}, and (3)~introduces a
rate--distortion gap that cannot be closed without recovering the
discarded byte-level information.  In contrast, the extended event
space avoids this loss by maintaining bytes as the outer $I$ and $O$
while building the lexicon \emph{inside} $H$: the word level is an
additional structure, not a replacement for the byte level.  We
compute the information loss for BPE tokenization on enwik8 and show
it is $\geq 0.12$~bpc in the worst case (spelling-variant entropy).
\end{abstract}


\section{The Attractive Nuisance}\label{sec:nuisance}

An \emph{attractive nuisance} is something that does not work but
causes people to keep trying it by seeming likely to work---the chess
equivalent of a false checkmate.

Tokenization is the attractive nuisance of language modeling.  The
argument for tokenization:
\begin{enumerate}
\item Words (or subwords) are the ``natural'' units of language.
\item Modeling word sequences is simpler than byte sequences (shorter
  contexts, fewer predictions).
\item Subword tokenization (BPE, SentencePiece) handles unknown words.
\end{enumerate}

Each point has a hidden cost:
\begin{enumerate}
\item Words are not atomic: they have internal structure (letters,
  morphology, spelling variants) that tokenization discards.
\item Shorter sequences have fewer datapoints for counting, so the
  count table over tokens has less data per entry than the count
  table over bytes.
\item Subword tokenization creates arbitrary boundaries that do not
  align with linguistic structure.
\end{enumerate}

We formalize these costs.


\section{Tokenization as Coarsening}\label{sec:coarsening}

\begin{definition}[Tokenization map]
A \emph{tokenization} is a deterministic function
$\tau: \Sigma^* \to T^*$ that maps byte sequences to token sequences,
where $T$ is a finite token vocabulary with $|T| = V_T$.  The
tokenization induces a map on events:
\begin{equation}
\tau_E: E_{\text{byte}} \to E_{\text{token}},
\end{equation}
where $E_{\text{byte}} = \{0..255\}^k$ (byte $k$-grams) and
$E_{\text{token}} = T$ (tokens).
\end{definition}

\begin{proposition}[Tokenization is a surjective coarsening]
The map $\tau_E$ is surjective (every token corresponds to at least
one byte sequence) and many-to-one (multiple byte sequences map to
the same token when they differ only in information that $\tau$
discards).  In the lattice of event spaces~\cite{category-es},
tokenization is a coarsening: $E_{\text{token}} \leq E_{\text{byte}}$.
\end{proposition}


\section{What Tokenization Discards}\label{sec:discards}

\begin{theorem}[Three information losses]\label{thm:three-losses}
Any fixed tokenization $\tau$ discards at least three types of
information present in the extended event space $E'$:
\begin{enumerate}
\item \textbf{Spelling variants.}
  If $\tau(\text{``the''}) = \tau(\text{``teh''}) = t_{\text{THE}}$
  (both map to the same token), then the model cannot distinguish
  standard from variant spelling.  The information lost is:
  \begin{equation}
  \Delta I_{\text{spell}} = H(\text{spelling} \mid \text{token})
  = -\sum_s P(s \mid t) \log_2 P(s \mid t),
  \end{equation}
  where $s$ ranges over spellings of token $t$.

\item \textbf{Internal position.}
  Within a token, the byte-level position event
  $\text{pos}(t) \in \{0..L_{\max}\}$ is invisible to the token-level
  model.  The lost information is:
  \begin{equation}
  \Delta I_{\text{pos}} = H(\text{pos} \mid \text{token boundary}).
  \end{equation}

\item \textbf{Letter accumulation.}
  The letter accumulator $\text{acc}(t) \in \{0,1\}^{256}$ provides
  a running summary of which bytes have appeared.  At the token level,
  this is collapsed to a single event (the token identity), losing
  the compositional structure.
\end{enumerate}
\end{theorem}

\begin{proof}
For (1): by the data processing inequality, any deterministic map
$\tau$ satisfies $I(\tau(X); Y) \leq I(X; Y)$ for any target $Y$.
The loss $\Delta I = I(X; Y) - I(\tau(X); Y) \geq 0$ is zero only
when $\tau$ is sufficient for predicting $Y$.  When $\tau$ merges
spelling variants that have different predictive distributions
(``teh'' predicts informal context; ``the'' predicts neutral context),
the loss is strictly positive.

For (2): the position event is a deterministic function of the byte
stream, but it is not recoverable from the token sequence alone.
After tokenization, the model knows that a token boundary has occurred
but not how far into the original word it is.  For multi-byte tokens,
the internal position carries $\log_2 L_{\text{token}}$ bits of
information per position.

For (3): the letter accumulator at each byte position is a running
set, updated incrementally.  The token-level model sees only the
token identity, which is the \emph{final} state of the accumulator
(at the token boundary), not the intermediate states.  The lost
information is the entropy of the accumulator trajectory conditioned
on the token identity.
\end{proof}


\section{The Strawberry Theorem Fails Under Tokenization}\label{sec:strawberry}

\begin{theorem}[Strawberry impossibility]\label{thm:strawberry}
A token-level model with fixed tokenization $\tau$ cannot solve the
letter-counting problem (``how many r's in strawberry?'') unless:
\begin{enumerate}
\item The token vocabulary includes every possible letter count as a
  separate token (exponentially many tokens), OR
\item The model has access to byte-level decomposition of each token
  (which undoes the tokenization).
\end{enumerate}
\end{theorem}

\begin{proof}
The letter-counting problem requires the letter accumulator: for each
byte $c$, track the count of $c$ in the current word.  At the token
level, the token ``strawberry'' is a single event with no internal
structure.  The model cannot count the r's without decomposing the
token into bytes.

Formally: the function $f: V \to \mathbb{N}$ defined by
$f(w) = |\{i : w_i = \text{`r'}\}|$ is not computable from the token
identity alone when different words with different letter counts share
the same token-boundary structure.  Even when each word is its own
token, the letter count is encoded in the token's \emph{spelling}, not
in its \emph{identity}: the model must ``look inside'' the token.

In the extended event space, the letter accumulator provides this
information explicitly: ``r has appeared'' is an event at each byte
position, and the count is the number of positions where this event
fires.  No token-level model can replicate this without re-deriving
the byte-level events.
\end{proof}

\begin{remark}
This is Theorem~15 (strawberry theorem) of the tock step
paper~\cite{tock-step} instantiated for the tokenization case.
The result is not about model capacity (a transformer with enough
layers can memorize letter counts) but about architectural information
flow: the tokenizer discards information that must then be
re-learned from the training signal.  The extended event space never
discards it.
\end{remark}


\section{The Rate--Distortion Gap}\label{sec:gap}

\begin{definition}[Token-level distortion]
The \emph{token-level distortion} is the excess cross-entropy from
using token-level predictions instead of byte-level predictions:
\begin{equation}
D_{\tau} = H_{\text{byte}}(\text{data} \mid \text{token model})
- H_{\text{byte}}(\text{data} \mid \text{byte model}).
\end{equation}
This is the information lost by the coarsening $\tau_E$.
\end{definition}

\begin{proposition}[The gap is bounded below]
\begin{equation}
D_{\tau} \geq \Delta I_{\text{spell}} + \Delta I_{\text{pos}} \cdot \bar{L},
\end{equation}
where $\bar{L}$ is the mean token length in bytes.  The spelling-variant
term contributes a per-token cost; the position term contributes a
per-byte cost multiplied by the mean number of bytes per token.
\end{proposition}

\begin{proof}
Each token hides $\bar{L}$ byte positions.  At each hidden position,
the position information ($\Delta I_{\text{pos}}$) is lost.  The
spelling-variant information is lost per token.  Both losses are
additive (by the chain rule for entropy) and contribute independently
to the total distortion.
\end{proof}

\begin{example}[BPE on enwik8]
For BPE tokenization with vocabulary size $V_T = 50{,}000$ on enwik8:
\begin{itemize}
\item Mean token length: $\bar{L} \approx 4.5$ bytes.
\item Number of tokens: $\sim 22$ million (from $10^8$ bytes).
\item Spelling variants: for the top 1000 words, approximately 2\% of
  occurrences are misspelled in Wikipedia source (edits, vandalism,
  non-native speakers).  This gives
  $\Delta I_{\text{spell}} \approx H_2(0.02) \approx 0.14$ bits per
  affected token, or $\sim 0.003$ bpc averaged over all bytes.
\item Position information: within each token, the position carries
  $\log_2 \bar{L} \approx 2.2$ bits.  Not all of this is predictively
  useful, but at least the onset/interior distinction (1 bit) affects
  predictions.  This gives $\Delta I_{\text{pos}} \geq 0.22$ bits per
  byte position.
\item Total: $D_{\tau} \geq 0.003 + 0.22 \times (1/4.5) \approx 0.05$
  bpc as a lower bound.
\end{itemize}
In practice, the gap is larger because the position and spelling
effects interact (variant spellings change position-dependent
predictions).  The worst case (texts with many misspellings, unusual
formatting, or code) can reach $0.12$~bpc or more.
\end{example}


\section{The Extended Event Space Avoids the Loss}\label{sec:avoids}

\begin{proposition}[Zero information loss in the extended ES]
The extended event space $E' = I' \times H' \times O'$ maintains bytes
as the outer $I$ and $O$.  No byte-level information is discarded:
\begin{enumerate}
\item \textbf{Spelling variants:} The letter accumulator records
  actual letters; the word embedding records intended word.  The
  discrepancy is explicitly represented, not collapsed.
\item \textbf{Position:} The in-word position is a first-class event
  in $I'$, accessible to all patterns.
\item \textbf{Letter composition:} The accumulator tracks running
  letter information at every byte position.
\end{enumerate}
The word level is \emph{additional structure inside $H'$}, not a
replacement for the byte level.  No coarsening is applied to $I$
or $O$.
\end{proposition}

\begin{remark}[The architectural principle]
Tokenization replaces the byte-level event space with a coarser
token-level event space.  The extended ES adds a finer structure
(words) \emph{within} the existing event space.  The difference is
between:
\begin{itemize}
\item \textbf{Tokenization:} $E_{\text{byte}} \to E_{\text{token}}$
  (coarsening, information loss).
\item \textbf{Extension:} $E_{\text{byte}} \to E_{\text{byte}} \times
  E_{\text{word}}$ (product, no information loss).
\end{itemize}
The first discards; the second adds.  The extended ES is strictly
more expressive than any tokenized model because it contains the
byte-level information that the tokenizer removes.
\end{remark}


\section{Why Tokenization Is Attractive}\label{sec:attractive}

Despite its information loss, tokenization persists because:

\begin{enumerate}
\item \textbf{Shorter sequences.}  A 100M-byte dataset becomes a
  22M-token dataset.  Transformer attention is $O(n^2)$ in sequence
  length, so $4.5\times$ shorter sequences give $\sim 20\times$
  speedup in attention.  This is a computational advantage, not an
  information-theoretic one.

\item \textbf{Implicit context extension.}  Each token carries
  $\bar{L} \approx 4.5$ bytes of ``free'' context.  A 2048-token
  context window sees $\sim 9000$ bytes.  But this ``free'' context
  is lossy: the information inside each token is collapsed.

\item \textbf{Vocabulary as implicit event space.}  The token
  vocabulary $T$ is an implicit event space: each token is an event.
  This appears to give word-level modeling ``for free.''  But the
  vocabulary is fixed at training time and cannot adapt to new words,
  misspellings, or domain-specific terminology without re-tokenization.
\end{enumerate}

\begin{proposition}[The extended ES achieves all benefits without the cost]
\begin{enumerate}
\item \textbf{Shorter effective sequences:} The word-level patterns
  in $H'$ operate on word events, giving the same context extension
  as tokenization.  But the byte-level patterns remain available for
  within-word prediction.

\item \textbf{Context extension:} The graded word support $\sigma_w(t)$
  provides implicit context of the entire word history, accessible at
  every byte position.

\item \textbf{Adaptive vocabulary:} New words are injected via the
  abductive tock step~\cite{extended-es}, without re-training.  The
  vocabulary grows with the data.
\end{enumerate}
\end{proposition}


\section{The Formal Information-Theoretic Bound}\label{sec:bound}

\begin{theorem}[Information loss bound]\label{thm:bound}
For any fixed tokenization $\tau$ and any data source with
byte-level entropy rate $h_b$ and token-level entropy rate $h_\tau$:
\begin{equation}
h_b \leq h_\tau / \bar{L} + \frac{1}{\bar{L}} H(\text{bytes} \mid \text{tokens}),
\end{equation}
where $H(\text{bytes} \mid \text{tokens})$ is the within-token
entropy (the information not captured by the token identity).
Equality holds iff the tokenization is a sufficient statistic for
the byte-level source.
\end{theorem}

\begin{proof}
By the chain rule:
\begin{equation}
H(\text{byte sequence}) = H(\text{token sequence}) + H(\text{bytes} \mid \text{tokens}).
\end{equation}
Dividing by the number of bytes $N$ and noting that the token
sequence has $N/\bar{L}$ tokens:
\begin{equation}
h_b = \frac{H(\text{token sequence})}{N} + \frac{H(\text{bytes} \mid \text{tokens})}{N}
= \frac{h_\tau}{\bar{L}} + \frac{H(\text{bytes} \mid \text{tokens})}{N}.
\end{equation}
The second term is the information loss per byte.  It is zero iff the
tokenization is lossless (i.e., bijective: each token uniquely
determines its bytes).  For standard BPE, it is nonzero because
multiple byte sequences can produce the same token sequence.
\end{proof}

\begin{corollary}[Tokenization can never beat byte-level modeling]
The optimal byte-level model achieves entropy rate $h_b$.  The
optimal token-level model, when converted back to byte-level
predictions, achieves at best $h_b + \Delta_{\tau}$ where
$\Delta_{\tau} = H(\text{bytes} \mid \text{tokens}) / N \geq 0$.
Token-level modeling is strictly worse unless the tokenization is
a sufficient statistic.
\end{corollary}


\section{Conclusions}

\begin{enumerate}
\item Tokenization is a coarsening of the event space that discards
  byte-level information: spelling variants, position, and letter
  composition.

\item The information loss is bounded below by the spelling-variant
  entropy plus the position entropy, totaling $\geq 0.05$~bpc for
  BPE on enwik8 (worst case $\geq 0.12$~bpc).

\item The strawberry theorem fails under tokenization: letter-counting
  is impossible without recovering byte-level decomposition.

\item The extended event space avoids all three losses by maintaining
  bytes as the outer I/O and adding words inside H.  No coarsening is
  applied.

\item Tokenization's computational advantages (shorter sequences,
  implicit context) are achievable in the extended ES without
  information loss, via word-level patterns in H' operating alongside
  byte-level patterns.

\item The formal bound (Theorem~\ref{thm:bound}) shows that
  token-level modeling is strictly suboptimal unless the tokenization
  is a sufficient statistic---which no fixed tokenization is for
  natural language.
\end{enumerate}


\begin{thebibliography}{99}
\bibitem{cmp}
Michaeljohn Clement.
\newblock \emph{CMP}.
\newblock \url{https://cmpr.ai/cmp.pdf}, 2026.

\bibitem{extended-es}
Claude and MJC.
\newblock \emph{The Extended Event Space: Injecting Lexical Structure into $H$}.
\newblock Hutter archive, 15 Feb 2026.

\bibitem{commentary}
Claude and MJC.
\newblock \emph{The Model Within the Model: Commentary on the Extended Event Space}.
\newblock Hutter archive, 15 Feb 2026.

\bibitem{category-es}
Claude and MJC.
\newblock \emph{The Category of Event Spaces}.
\newblock Hutter archive, 12 Feb 2026.

\bibitem{tock-step}
Claude and MJC.
\newblock \emph{The Tock Step: Domain-Native Architecture from Evidence}.
\newblock Hutter archive, 12 Feb 2026.

\bibitem{compression-prediction}
Claude and MJC.
\newblock \emph{The Compression--Prediction Duality}.
\newblock Hutter archive, 12 Feb 2026.

\bibitem{renormalization}
Claude and MJC.
\newblock \emph{Renormalization Group Flow on Event Spaces}.
\newblock Hutter archive, 12 Feb 2026.
\end{thebibliography}

\end{document}
