\section{Mathematical Formulation}
\label{sec:formulation}

\subsection{Objects}
Let $\E$ be the set of (layer, expert) pairs, $|\E| = LE$, each of size $b$ bytes (3.375~MiB for OLMoE at 4 bits; equal
within an architecture). Let $\Nset = \{0,1,\dots,N\}$ be the nodes, node $0$ being the coordinator that runs attention, the
router and the KV cache, and let tier $\mathcal{T}_n = \{\mathrm{ram}, \mathrm{ssd}\}$ be the storage tiers of node $n$.
Tokens are steps $t = 1,2,\dots$; the router of layer $l$ at step $t$ selects $S_{t,l} \subset \E_l$, $|S_{t,l}| = K$.
Decision variables are binary and indexed by step:
\begin{align}
  x_{e,n,t} &\in \{0,1\} \quad \text{expert $e$ is resident in the memory of node $n$ at step $t$,} \\
  z_{e,n,t} &\in \{0,1\} \quad \text{expert $e$ is \emph{executed} on node $n$ at step $t$,} \\
  p_{e,n,t} &\in \{0,1\} \quad \text{a prefetch of $e$ into node $n$ is issued during step $t$.}
\end{align}
Every expert exists on the local NVMe of each node that holds a copy of the checkpoint (the SSD tier is unbounded for our
purposes and costs only time), so residency refers to memory.

\subsection{Constraints}
\begin{align}
  \sum_{e \in \E} b\, x_{e,n,t} &\le M_n \qquad \forall n, t && \text{(memory budget of node $n$)} \label{eq:mem}\\
  \sum_{n \in \Nset} z_{e,n,t} &= \ind[e \in S_{t,l(e)}] \qquad \forall e, t && \text{(every selected expert executed exactly once)} \label{eq:exec}\\
  z_{e,n,t} &\le x_{e,n,t} + m_{e,n,t} \qquad \forall e, n, t && \text{(execution needs residency or a demand miss $m$)} \label{eq:res}\\
  x_{e,n,t+1} &\le x_{e,n,t} + p_{e,n,t} + m_{e,n,t} \qquad \forall e, n, t && \text{(residency only grows by prefetch or miss)} \label{eq:dyn}
\end{align}
where $m_{e,n,t} \in \{0,1\}$ is the demand-miss indicator, itself a consequence of the router and of $x$. Constraint
\eqref{eq:exec} encodes the correctness invariant: the set of executed experts is the router's set, whatever the placement.

\subsection{Costs}
The per-step latency decomposes along the layer sequence, because layer $l$ cannot start before layer $l-1$'s output exists:
\begin{equation}
  \Lambda_t \;=\; \sum_{l=1}^{L} \Big[ \underbrace{\tau^{\mathrm{attn}}_{0}}_{\text{attention, node 0}}
  + \max_{n \in \Nset}\big( \underbrace{c_n \cdot \textstyle\sum_{e \in S_{t,l}} z_{e,n,t}}_{\text{expert compute on $n$}}
  + \underbrace{\rho_{0n}\,\ind[\exists e\!:\! z_{e,n,t}=1, n\neq 0]}_{\text{activation round trip}} \big)
  + \underbrace{\sigma_{t,l}}_{\text{stall}} \Big],
  \label{eq:latency}
\end{equation}
with $c_n$ the measured per-expert compute time of node $n$, $\rho_{0n}$ the measured round-trip time of a
$d$-dimensional activation and its result between node $0$ and $n$ (on our LAN, $0.5$--$1.0$~ms), and the stall
\begin{equation}
  \sigma_{t,l} \;=\; \max\Big(0,\; \max_{e \in S_{t,l},\, m_{e,n,t} = 1} \big( \lambda_{\mathrm{tier}(e)} - \eta_{e,t} \big) \Big),
  \label{eq:stall}
\end{equation}
where $\lambda_{\mathrm{tier}}$ is the fetch latency of the tier the expert comes from ($\lambda_{\mathrm{pc}} = 0.21$~ms page
cache, $\lambda_{\mathrm{ssd}} = 0.43$~ms cold NVMe, $\lambda_{\mathrm{lan}} \approx 28$~ms for 3.4~MB over 0.945~Gbit/s, all
measured on our hardware) and $\eta_{e,t}$ is the lead time between the moment a prefetch of $e$ was issued and the moment
$e$ is needed ($\eta = 0$ for a demand miss). Energy per step is $\Phi_t = \sum_n P_n \cdot \Lambda^{(n)}_t$ with $P_n$ the
package power of node $n$ measured by \code{powermetrics} during the run, and communication cost $\Gamma_t = \sum_{n \ne 0}
\beta_{0n}\,(\text{activation bytes} + \text{weight bytes moved})$.

\subsection{Problem}
\begin{equation}
  \min_{x,z,p}\; \Ex\Big[\sum_{t} \Lambda_t + \lambda\,\Phi_t + \mu\,\Gamma_t\Big] \quad \text{s.t. \eqref{eq:mem}--\eqref{eq:dyn}},
  \label{eq:problem}
\end{equation}
where the expectation is over the router's sequence $\{S_{t,l}\}$, which is revealed online: at step $t$, $S_{t,l}$ becomes
known only after layer $l-1$'s output is computed. The problem is a stochastic online integer program; its offline relaxation
with known $S$ is the paging problem with multiple caches and non-uniform fetch costs, for which Belady's furthest-in-future
rule is optimal per cache and which our simulator's \emph{oracle} predictor approximates.

\subsection{When can a prefetch pay?}
\label{sec:prefetch-condition}
Consider a predictor issuing, when layer $l-d$'s routing is known at step $t$, a set $\hat S_{t,l}$ of $m$ experts for layer
$l$, with recall $r = \Ex|\hat S \cap S|/K$ and precision $q = \Ex|\hat S \cap S|/m$. With per-layer decode time $\tau_\ell$
the lead time is $\eta = d\,\tau_\ell$. Per layer, the expected stall without prefetch is
$\sigma_0 = \lceil K(1-h)/w \rceil\, \lambda$ for hit rate $h$ and $w$ parallel loaders, and with prefetch
\begin{equation}
  \sigma_d \;\approx\; \lceil K(1-h)(1-r')/w \rceil\,\lambda \;+\; \lceil K(1-h)\, r'/w \rceil\,\max(0, \lambda - d\,\tau_\ell),
  \label{eq:prefetch-gain}
\end{equation}
where $r'$ is the recall among the experts that would have missed. The prefetch also adds $m(1-q)$ useless fetches whose
bandwidth and install cost $\kappa$ each is paid on the critical path when the loader is shared with demand misses.
A prefetch can only reduce latency if
\begin{equation}
  r'\,\min(\lambda, d\,\tau_\ell) \;>\; m(1-q)\,\kappa\;/\;K(1-h),
  \label{eq:condition}
\end{equation}
and it can \emph{remove} the stall only if $d\,\tau_\ell \ge \lambda$. On the laptop, $\tau_\ell = 0.128$~ms (489~\tps{} over
16 layers), so a page-cache fetch ($\lambda = 0.21$~ms) needs $d \ge 2$ and a cold-NVMe fetch ($\lambda = 0.43$~ms) needs
$d \ge 4$; a LAN fetch ($\lambda \approx 28$~ms) can never be hidden within a token on this model, which is why weights are not
moved over the LAN during decode in \titan{} and remote experts are instead executed where they reside. The one-layer online
experiment of Section~\ref{sec:results-prefetch} violated \eqref{eq:condition} ($d = 1$, $q \approx 0.5$) and lost throughput, as
predicted; the depth-$d$ experiments test the condition directly.

\begin{proposition}[Demand loading is $\mathcal{O}(1)$-competitive per layer only when the table exceeds the per-step
working set]
\label{prop:capacity}
With per-layer tables of capacity $C \ge K$, LRU eviction, and no prefetch, the number of demand misses at a decode step is at
most $K$ and at least $K - |S_{t,l} \cap S_{t-1,l}| $ when $C = K$; for $C \ge |\bigcup_{s \le \Delta} S_{t-s,l}|$ the misses at
step $t$ are exactly the experts not used in the last $\Delta$ steps at that layer.
\end{proposition}
\begin{proof}
With $C = K$ the table after step $t-1$ holds exactly $S_{t-1,l}$, so every expert of $S_{t,l} \setminus S_{t-1,l}$ misses and
no other does; misses are bounded by $K$ because $|S_{t,l}| = K$. For the second claim, LRU keeps the most recently used
$C$ distinct experts; if $C$ is at least the number of distinct experts used in the last $\Delta$ steps, all of them are
resident, so a miss at step $t$ is precisely an expert unused during those $\Delta$ steps.
\end{proof}
The proposition is elementary but useful: it says that the hit rate of LRU at capacity $C$ is the fraction of a step's
experts that recur within the $C$-recent window of that layer, a quantity we measure directly from traces
(Section~\ref{sec:results-locality}) and which, for OLMoE, is 0.57 at $C = 16$ and 0.80 at $C = 32$.