\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}

\title{Memory Traces, Integration, and Explanatory Sufficiency}
\author{Hutter RNN Project}
\date{2026-01-31}

\begin{document}
\maketitle

\section{Setup: Adding Time to the Universal Model}

The CMP framework defines $u = (E, T, P, f, \omega)$ for static models. To handle sequences, we introduce \textbf{time}.

\subsection{Definitions}

Let $x_1, x_2, \ldots, x_t$ be a sequence of observations (bytes).

\begin{description}
\item[Memory Trace] The complete history up to time $t$:
\[
M_t = (x_1, x_2, \ldots, x_t)
\]

\item[Sufficient Statistic] A compression $h_t = \phi(M_t)$ such that:
\[
P(x_{t+1} | M_t) = P(x_{t+1} | h_t)
\]
If $h_t$ is sufficient, it captures all predictive information in $M_t$.

\item[Integration] The update rule that computes $h_t$ from $h_{t-1}$ and $x_t$:
\[
h_t = g(h_{t-1}, x_t)
\]
This is the RNN recurrence.

\item[Explanatory Sufficiency] A statistic $h_t$ is \textbf{explanatorily sufficient} if:
\[
I(x_{t+1}; M_t | h_t) = 0
\]
That is, $h_t$ screens off the future from the past.
\end{description}

\section{Memory Traces in Log-Space (N)}

Working in $\mathbb{N}$ (log-space), the memory trace becomes a thought vector:
\[
\mathbf{t}^{(M_t)} \in \mathbb{N}^{|E|}
\]

Each component $t^{(M_t)}_e$ is the log-support for event $e$ given history $M_t$.

\subsection{Integration as Pattern Application}

Given patterns $P$ and update function $f_P$, integration is:
\[
\mathbf{t}^{(t)} = f_P(\mathbf{t}^{(t-1)}, x_t)
\]

In CMP terms:
\[
t^{(t)}_j = \max_i \min(t^{(t-1)}_i, p_{ij}) + \delta_{j, x_t} \cdot \text{obs\_strength}
\]

The $\delta$ term adds support for the observed event.

\section{Factored Memory Traces}

For an RNN with hidden state $\mathbf{h} \in \mathbb{R}^H$, the memory trace factors:
\[
M_t \approx h_t = (h_t^{(1)}, h_t^{(2)}, \ldots, h_t^{(H)})
\]

Each hidden unit $h_t^{(i)}$ is a \textbf{partial trace} capturing some aspect of history.

\subsection{ES as Coarse Traces}

Our ES features are coarse memory traces:
\[
ES_t = \pi(x_t) \in \{0, 1, 2, 3, 4\}
\]

The ES-level memory is:
\[
M^{ES}_t = (ES_1, ES_2, \ldots, ES_t)
\]

This is a lossy compression of $M_t$.

\section{Explanatory Sufficiency}

\subsection{Definition}

A representation $h_t$ has \textbf{explanatory sufficiency} for predicting $x_{t+1}$ if:
\[
H(x_{t+1} | h_t) = H(x_{t+1} | M_t)
\]

Equivalently, the mutual information between future and past, given $h_t$, is zero:
\[
I(x_{t+1}; M_t | h_t) = 0
\]

\subsection{Levels of Sufficiency}

\begin{enumerate}
\item \textbf{Full sufficiency:} $h_t = M_t$ (store everything)
\item \textbf{Markov sufficiency:} $h_t = x_t$ (only last observation)
\item \textbf{$k$-Markov sufficiency:} $h_t = (x_{t-k+1}, \ldots, x_t)$
\item \textbf{ES-Markov sufficiency:} $h_t = ES_t$
\item \textbf{RNN sufficiency:} $h_t = \mathbf{h}_t$ (learned compression)
\end{enumerate}

\subsection{Measuring Sufficiency Gap}

The \textbf{sufficiency gap} of representation $h_t$ is:
\[
\Delta_h = H(x_{t+1} | h_t) - H(x_{t+1} | M_t)
\]

For ES-Markov:
\[
\Delta_{ES} = H(x_{t+1} | ES_t) - H(x_{t+1} | x_t) = ?
\]

\section{Empirical Questions}

\begin{enumerate}
\item What is the sufficiency gap for 1-Markov (single byte)?
\item What is the sufficiency gap for ES-Markov?
\item How much does the RNN hidden state reduce the gap?
\item At what depth $k$ does $k$-Markov become sufficient?
\end{enumerate}

\section{Connection to Compression}

Explanatory sufficiency relates directly to compression:
\[
\text{Optimal code length} = H(x_{t+1} | M_t)
\]

If we use $h_t$ instead of $M_t$:
\[
\text{Achievable code length} = H(x_{t+1} | h_t) \geq H(x_{t+1} | M_t)
\]

The gap $\Delta_h$ is the \textbf{compression penalty} for using the coarse representation.

\end{document}
