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

\title{Scaling Byte-Level Kneser--Ney to 1.78\,bpc on enwik9:\\Zero Structure, Just Counting}
\author{Claude and MJC}
\date{February 12, 2026}

\begin{document}
\maketitle

\begin{abstract}
We scale interpolated Kneser--Ney smoothing on raw bytes from 10\,MB to 1\,GB
(full enwik9), achieving \textbf{1.784\,bpc} at order~6 with discount~$D=0.9$.
No structure is imposed: no tokenization, no neural network, no event spaces---just
exact $n$-gram counting with standard KN smoothing.  The improvement rate is
$\sim$0.07\,bpc per doubling at small scale, slowing to $\sim$0.03 at large.
Skip-offset models (d$>$6) and class-based output decompositions both fail to
improve over sequential byte KN.  This establishes a strong counting-only baseline
for the Hutter Prize and quantifies how much of text compression is pure local
redundancy versus structure.
\end{abstract}

\section{Method}

A single hash table stores all $n$-gram statistics up to order~$k$.
For each position $t$ and each order $o \in \{1,\ldots,k\}$, we record:
\begin{itemize}
\item $c(w_{t-o}^{t-1}, w_t)$: continuation count (key: context + byte value),
\item $c(w_{t-o}^{t-1}, \cdot)$: total count (key: context + sentinel 512),
\item $\tau(w_{t-o}^{t-1})$: type count (key: context + sentinel 513),
      incremented only when a new byte type appears in context.
\end{itemize}

\paragraph{Interpolated KN.}
The prediction builds bottom-up from the marginal:
\[
  P(w_t \mid w_{t-o}^{t-1}) = \frac{\max(c - D, 0)}{c(\cdot)} + \frac{D \cdot \tau}{c(\cdot)} \cdot P(w_t \mid w_{t-o+1}^{t-1}),
\]
recursing down to the unigram marginal $P(w_t)$.
All orders contribute, unlike standard (backoff) KN which stops at the highest
matching order.  Interpolated KN consistently outperforms backoff by 0.005--0.01\,bpc.

\paragraph{Hash table.}
Open-addressing with FNV-1a hashing, 12 bytes per entry (8-byte key + 4-byte count).
128M entries = 1.5\,GB.  At full enwik9 (800M train), order~6 fills the table to 99.9\%.
A 256M-entry table (3\,GB) would avoid saturation but requires $>$5\,GB total---above
our 7.8\,GB memory budget.

\section{Results}

\begin{table}[h]
\centering
\begin{tabular}{@{}rrrr@{}}
\toprule
Data & KN-5i best & KN-6i best & HT fill \\
\midrule
10M  & 2.286 & ---   & 5\% \\
20M  & 2.175 & ---   & 8\% \\
50M  & 2.093 & 2.093 & 24\% \\
100M & 2.038 & 2.001 & 32\% \\
200M & 1.984 & 1.927 & 48\% \\
400M & 1.960 & 1.889 & 73\% \\
800M & 1.945 & 1.859 & 97\% \\
1B   & 1.860 & \textbf{1.784} & 100\% \\
\bottomrule
\end{tabular}
\caption{Best interpolated KN bpc (bits per character) on held-out test data.
All use discount $D=0.8$ except 1B KN-6i which uses $D=0.9$.
HT fill is for KN-6 at the 128M-entry table.}
\end{table}

\paragraph{Diminishing returns.}
Per-doubling improvement for KN-6i: 0.074 (100M$\to$200M), 0.038 (200M$\to$400M),
0.030 (400M$\to$800M).  The rate is halving per doubling---logarithmic convergence.
Extrapolating, 10B data (if available) would give $\sim$1.7\,bpc.

\paragraph{Order saturation.}
At 100M, order~7 is worse than order~6 (2.008 vs 2.001)---overfitting.
At 200M, order~7 is slightly better (1.918 vs 1.927) but requires 92\% HT.
At 400M+, order~7 overflows the HT completely (100\% fill at 234M/320M train).
The optimal order grows sublogarithmically with data size.

\section{Negative Results}

\paragraph{Skip offsets add nothing.}
We built separate KN models on non-sequential offsets (d=7,8,9,10,11,12),
selected by mutual information.  At 20M: skip KN-4 alone = 4.65\,bpc.
Product-of-experts combination: best $\alpha=1.0$ (byte KN alone wins).
The sequential offsets d=1..6 completely dominate at byte level.

\paragraph{Class-based output decomposition fails.}
Decomposing $P(w \mid \text{ctx}) = P(\text{class} \mid \text{event ctx}) \cdot
P(w \mid \text{class}, \text{byte ctx})$ with frequency-based output classes
(K=4,8,16,32) never beats byte KN at any scale from 65K to 10M.
The Zipfian byte distribution makes classes extremely imbalanced.

\section{Implications for the Universal Model}

\paragraph{What 1.784\,bpc represents.}
This is the amount of enwik9 redundancy capturable by exact local pattern matching
up to 6 bytes.  No inter-word, no syntactic, no semantic structure is used.
The remaining $\sim$1.4\,bpc (from the $\sim$0.4\,bpc entropy floor) is ``structure''
in the CMP sense---it requires event spaces, not just byte counting.

\paragraph{Comparison to other methods.}
\begin{itemize}
\item sat-rnn (128 hidden, 110M train): 2.81\,bpc at byte level
      (0.079\,bpc at 100K with custom eval---different regime)
\item Byte KN-6i at 200M: 1.927\,bpc (already beats sat-rnn)
\item LSTM-based compressors: $\sim$1.3\,bpc
\item Transformers (GPT-scale): $\sim$0.9\,bpc
\end{itemize}

The KN baseline at 1.784 is remarkable---it captures $\sim$78\% of the
known-compressible redundancy ($\sim$8 - 0.4 = 7.6$ bpc range) using only
6-gram statistics.

\paragraph{The counting floor.}
As data $\to \infty$, byte KN converges to the $k$-th order entropy.
For English at order~6, this appears to be $\sim$1.7\,bpc.
The gap between this floor and transformer-level compression ($\sim$0.9\,bpc)
is the ``structural redundancy''---information that requires understanding
words, syntax, and semantics, not just byte patterns.

\paragraph{HT saturation as the real bottleneck.}
At 1B, the 128M-entry HT is 99.9\% full.  Many 6-grams are being lost to
hash collisions.  A 256M-entry table (3\,GB HT + 1\,GB data) was OOM-killed
on our 7.8\,GB machine.  With adequate memory, unsaturated order~6 would
almost certainly push below 1.75\,bpc; order~7 might reach $\sim$1.7\,bpc.
The algorithm is memory-limited, not data-limited.

\section{Conclusion}

Byte-level KN smoothing scales cleanly to full enwik9: 1.784\,bpc with no
structure beyond 6-gram counting.  This establishes both a practical baseline
and a theoretical reference point.  Everything below 1.784 requires the
Universal Model's event spaces, pattern chains, or learned representations.
The counting foundation is now solid; the structural frontier begins here.

\end{document}
