Formal Systems Invariants
The chapters state many results in one line, with the intuition an engineer needs to apply them, and leave the derivation for readers who want to check it or extend it. This appendix collects those derivations: the formal model of a trajectory, the conditions under which a runtime can guarantee that a loop ends, the statistics behind evaluation and release decisions, the mathematics of verification cadence, credit assignment, and imitation error, and the limits of voting and of high-dimensional retrieval. Each section states its result, derives it, and names the chapter that uses it, so a reader can move between the argument in the main text and the proof here without reading either in full.
How to Use This Appendix
Consult the section whose question matches the one in front of you.
- When you need the formal model of what an agent observes and decides, use section 1.1.
- When you need to prove that a runtime’s budgets and progress checks end every loop, use section 1.2.
- When you need to reason about how taint combines as untrusted data enters a context, use section 1.3.
- When long trajectories delay short ones, or trajectory lengths look heavy-tailed, use section 1.4 and section 1.5.
- When you need to choose how often to verify or checkpoint, use section 1.9 and section 1.13.
- When you need the estimators and tests behind evaluation and release gates, use section 1.11, section 1.14, and section 1.15.
- When you need the gradients or error bounds behind training on trajectories, use section 1.6, section 1.7, section 1.8, and section 1.17.
- When you need the limits of voting, multi-agent speedup, or escalation thresholds, use section 1.20, section 1.19, and section 1.18.
- When you need the mathematics of constrained decoding, repository ranking, low-rank compression, or high-dimensional search, use section 1.12, section 1.10, section 1.16, and section 1.21.
POMDP Formalization of Trajectories
Formally, an agent operates over a Partially Observable Markov Decision Process (POMDP) defined by the 7-tuple:
\[\langle \mathcal{S}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \Omega, \mathcal{O}, \gamma \rangle\]
where:
- \(\mathcal{S}\) is the set of hidden environment states (e.g., the complete virtual machine filesystem, remote database state, and network socket buffers).
- \(\mathcal{A}\) is the set of discrete actions available to the agent (e.g., shell commands, code edits, and HTTP requests).
- \(\mathcal{T}(s' \mid s, a) = \mathbb{P}(S_{t+1} = s' \mid S_t = s, A_t = a)\) is the state transition probability distribution of the external environment.
- \(\mathcal{R}(s, a)\) is the reward function evaluating progress toward the user’s objective.
- \(\Omega\) is the set of observations returned to the agent (e.g., stdout logs, compiler error messages, and API response JSON).
- \(\mathcal{O}(o \mid s', a) = \mathbb{P}(O_{t+1} = o \mid S_{t+1} = s', A_t = a)\) is the observation probability distribution conditioned on the underlying state.
- \(\gamma \in [0, 1)\) is the discount factor.
Because the agent cannot directly inspect the complete state \(s \in \mathcal{S}\), it maintains an internal belief state or trajectory context \(b_t \in \mathcal{B}\), represented by the sequence of past tokens:
\[b_t = (x_0, a_0, o_0, x_1, a_1, o_1, \dots, x_t)\]
where \(x_t\) denotes the reasoning tokens the model generated at step \(t\). The belief is built from what the agent has seen, not from what the environment now contains, so it can be stale the moment a tool or another writer changes the environment. That gap is why the runtime, not the model, is responsible for invalidating stale observations (Context Invalidation), and why a plan is treated as a revisable hypothesis rather than a fixed program (Plans as Revisable State).
Lyapunov Liveness Verification
To mathematically prove liveness and guarantee termination in a stochastic control graph, the runtime constructs a Monotonically Decreasing Variant Function (a Lyapunov or ranking function) \(V: \mathcal{S} \times \mathcal{B} \to \mathbb{R}^+\). A control topology satisfies guaranteed termination if, for every execution step \(t\), the expected value of \(V\) decreases by at least a strictly positive constant \(\delta > 0\):
\[\mathbb{E}\left[ V(S_{t+1}, b_{t+1}) \mid S_t, b_t \right] \le V(S_t, b_t) - \delta\]
The runtime enforces this condition by defining \(V\) over an explicit composite vector of execution resources:
\[V(t) = \mathbf{w}^T \begin{bmatrix} K_{\max} - k_t \\ T_{\text{budget}} - T_{\text{consumed},t} \\ \mathcal{D}_{\text{goal}}(S_t, S^*) \end{bmatrix}\]
where:
- \(K_{\max} - k_t\) is the remaining step ceiling.
- \(T_{\text{budget}} - T_{\text{consumed},t}\) is the remaining token and financial compute balance.
- \(\mathcal{D}_{\text{goal}}(S_t, S^*)\) is a metric measuring distance to goal state completion.
If an agent executes an action that fails to reduce \(\mathcal{D}_{\text{goal}}\), the step and token budget terms still make \(V(t)\) strictly decrease. When \(V(t) \le 0\), the runtime ends the trajectory. The budget terms are the per-trajectory ceilings of Budgets and Ceilings, and the distance term is the environment-based progress signal of Semantic Watchdog Timers. Because the budget terms alone guarantee termination, the distance term matters for detecting a loop early rather than for ending it.
Information Flow Security Lattice
An information flow security lattice formalizes how data and privileges can flow through an agentic system, modeled as a partially ordered set:
\[\mathcal{L} = \langle S, \sqsubseteq, \sqcup, \sqcap \rangle\]
where \(S\) is the set of security labels, \(\sqsubseteq\) defines the flow relation (“can flow to”), \(\sqcup\) is the join operator (least upper bound), and \(\sqcap\) is the meet operator (greatest lower bound).
In an autonomous agent runtime, we define two orthogonal label dimensions: Secrecy (Confidentiality) and Integrity (Trustworthiness). For our threat model, let integrity be represented by a dynamic taint tag \(\tau \in \{\text{Trusted}, \text{Untrusted}\}\):
\[\text{Trusted} \sqsubset \text{Untrusted}\]
- A user prompt authored by the verified system operator carries label \(\tau = \text{Trusted}\).
- Any text ingested from the environment, including web pages, issue comments, pull request diffs, compiler error output, and database records, carries label \(\tau = \text{Untrusted}\).
During context assembly, every segment \(x_i\) in the agent context window \(C_t\) has an associated taint tag \(\tau(x_i)\). The cumulative context taint \(\tau(C_t)\) is the join across all constituent tokens:
\[\tau(C_t) = \bigsqcup_{i=1}^{|C_t|} \tau(x_i)\]
If a single untrusted document enters the context window, the cumulative context transitions to \(\tau(C_t) = \text{Untrusted}\). Because the join is monotone, taint can only be cleared by a step outside the model, such as a quarantined reader that returns typed fields, and never by further context. Tracking Untrusted Data applies this rule to decide which tool calls may accept an argument derived from a tainted context.
Heavy-Tailed Queueing Theory
Queueing delay depends on the variability of service times, not only on their mean. In an \(M/G/1\) queue, the Pollaczek-Khinchine formula makes the mean wait proportional to the second moment of the service time \(\mathbb{E}[S^2]\):
\[\mathbb{E}[W_{\text{queue}}] = \frac{\lambda \mathbb{E}[S^2]}{2 (1 - \rho)}\]
Under heavy-tailed service times, \(\mathbb{E}[S^2]\) is very large or unbounded (section 1.5). In a cluster this appears as head-of-line blocking. When a first-in, first-out queue admits a 200-step trajectory, that trajectory holds its worker, sandbox, and cache memory for tens of minutes, and hundreds of two-step tasks behind it wait. Separating long trajectories from short ones, by priority lanes or by admission limits per class, is the remedy developed in Scheduling Concurrent Trajectories and Capacity for Trajectories.
Heavy-Tailed Pareto Service Times
A single model call has a length bounded by its output ceiling. A trajectory’s length in steps has no such bound, because the number of turns depends on what the agent finds, and trajectory lengths are often modeled as heavy-tailed. A Pareto model makes the consequence precise. The probability that a task requires more than \(x\) steps is
\[\mathbb{P}(N > x) \approx \left( \frac{x_{\min}}{x} \right)^\alpha \quad \text{for } x \ge x_{\min}\]
where \(x_{\min} \ge 1\) is the minimum task length, and \(\alpha\) is the Pareto tail index.
The tail index \(\alpha\) must be estimated from a workload’s own trajectory lengths. Whenever \(\alpha \le 2\), the variance of the step count is infinite:
\[\operatorname{Var}(N) = \begin{cases} \infty & \text{if } 1 < \alpha \le 2 \\ \text{undefined} & \text{if } \alpha \le 1 \end{cases}\]
With infinite variance, the mean wait in section 1.4 is unbounded however low the utilization, and sample means of trajectory length converge slowly, so capacity plans and budget ceilings should be set from measured percentiles rather than from averages (principle \(\ref{pri-vol3-heavy-tailed-scheduling}\)).
LoRA Matrix Decomposition
Parameter-Efficient Fine-Tuning (PEFT) techniques rely on decomposing dense weight updates into low-rank matrices. For a dense weight matrix \(W_0 \in \mathbb{R}^{d \times k}\), LoRA decomposes the accumulated weight update \(\Delta W\) into the product of two low-rank matrices \(B \in \mathbb{R}^{d \times r}\) and \(A \in \mathbb{R}^{r \times k}\), where the rank satisfies \(r \ll \min(d, k)\):
\[W = W_0 + \Delta W = W_0 + \frac{\alpha}{r} (B \cdot A)\]
where \(\alpha\) is a constant scaling hyperparameter.
During forward computation on an input activation vector \(x\):
\[h = W_0 x + \Delta W x = W_0 x + \frac{\alpha}{r} B (A x)\]
Matrix \(A\) is initialized from a Gaussian distribution \(\mathcal{N}(0, \sigma^2)\), while matrix \(B\) is initialized to zero, ensuring that \(\Delta W = 0\) at the start of training. Because the adapter holds \(r(d + k)\) parameters instead of \(dk\), a serving system can hold one copy of the base model and many small adapters, one per agent role, which is the deployment pattern of Adapters for Agents.
During backward propagation, gradients of the scalar loss \(\mathcal{L}\) with respect to the adapter projection matrices \(A\) and \(B\) are computed using the matrix chain rule:
\[\frac{\partial \mathcal{L}}{\partial A} = \frac{\alpha}{r} B^T \left( \frac{\partial \mathcal{L}}{\partial h} \right) x^T, \quad \frac{\partial \mathcal{L}}{\partial B} = \frac{\alpha}{r} \left( \frac{\partial \mathcal{L}}{\partial h} \right) (x^T A^T)\]
The frozen base weights \(W_0\) receive zero gradient accumulation, eliminating optimizer state memory for \(W_0\) while preserving exact activation gradients \(\frac{\partial \mathcal{L}}{\partial x} = W_0^T \left( \frac{\partial \mathcal{L}}{\partial h} \right) + \frac{\alpha}{r} A^T B^T \left( \frac{\partial \mathcal{L}}{\partial h} \right)\) to backpropagate through preceding layers.
Generalized Advantage Estimation and KL Divergence
In reinforcement learning trajectories governed by intermediate rewards \(r_t\) and potential terminal outcomes \(R\), temporal credit assignment is formally modeled using Generalized Advantage Estimation (GAE) (Schulman et al. 2016).
Let \(\delta_t^V = r_t + \gamma V(s_{t+1}) - V(s_t)\) denote the temporal difference (TD) residual at time-step \(t\), where \(\gamma \in [0, 1]\) is the discount factor. The generalized advantage estimator \(\hat{A}_t^{\text{GAE}(\gamma, \lambda)}\) is defined as an exponentially weighted average of \(k\)-step advantage estimators:
\[\hat{A}_t^{\text{GAE}(\gamma, \lambda)} = \sum_{l=0}^{\infty} (\gamma \lambda)^l \delta_{t+l}^V = \delta_t^V + (\gamma \lambda) \hat{A}_{t+1}^{\text{GAE}(\gamma, \lambda)}\]
where \(\lambda \in [0, 1]\) controls the bias-variance trade-off.
When optimizing policies such as in GRPO, the objective function constrains divergence from a reference model \(\pi_{\text{ref}}\) using a token-level Kullback-Leibler (KL) divergence penalty. This KL divergence is computed analytically or approximated via:
\[D_{\text{KL}}(\pi_\theta \parallel \pi_{\text{ref}}) = \frac{\pi_{\text{ref}}(o_{i,t} \mid q, o_{i,<t})}{\pi_\theta(o_{i,t} \mid q, o_{i,<t})} - \log \frac{\pi_{\text{ref}}(o_{i,t} \mid q, o_{i,<t})}{\pi_\theta(o_{i,t} \mid q, o_{i,<t})} - 1\]
The penalty keeps the optimized policy \(\pi_\theta\) close to the reference model \(\pi_{\text{ref}}\), which limits how far optimization can drift toward outputs the reward scores well but the reference model would rarely produce (Group Relative Policy Optimization). It lowers the risk of reward hacking without removing it; isolating the verifier is what removes the most direct routes (Isolating the Verifier).
Credit Assignment Variance in Trajectory Optimization
How credit for an outcome is assigned to the individual actions of a trajectory sets how many rollouts training needs.
Let an agent trajectory of horizon \(T\) be denoted by \(\tau = (s_0, a_1, s_1, \dots, a_T, s_T)\). In an Outcome Reward Model (ORM), credit is provided as a scalar terminal reward \(R_{\text{ORM}}(\tau) \in [0, 1]\) conditioned on task completion at leaf state \(s_T\). Under policy gradient optimization (REINFORCE), the gradient estimator with baseline \(b\) is:
\[g_{\text{ORM}} = \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_t \mid s_{t-1}) \cdot \left(R_{\text{ORM}}(\tau) - b\right)\]
Because the terminal reward \(R_{\text{ORM}}(\tau)\) is a function of the entire trajectory, it acts as a global multiplier across all step gradients. The variance of this estimator expands with the sum of all pairwise covariances between steps:
\[\operatorname{Var}\left(g_{\text{ORM}}\right) = \sum_{t=1}^T \operatorname{Var}\left(\mathbf{\psi}_t \Delta R\right) + 2 \sum_{1 \le t < t' \le T} \operatorname{Cov}\left(\mathbf{\psi}_t \Delta R, \mathbf{\psi}_{t'} \Delta R\right)\]
where \(\mathbf{\psi}_t = \nabla_\theta \log \pi_\theta(a_t \mid s_{t-1})\) and \(\Delta R = R_{\text{ORM}}(\tau) - b\). Because each action \(a_t\) affects the terminal outcome and conditions on all previous steps, cross-step correlations do not vanish. For an unguided trajectory of length \(T\), the number of covariance pairs scales quadratically:
\[\operatorname{Var}\left(g_{\text{ORM}}\right) = \mathcal{O}\left(T^2\right)\]
This \(\mathcal{O}(T^2)\) growth means that as trajectories grow to hundreds of turns, the signal-to-noise ratio of the policy gradient falls, and the number of rollouts needed for a gradient of given precision grows with the square of the horizon.
Conversely, a Process Reward Model (PRM) supplies dense, localized step rewards \(r_t = r_{\text{PRM}}(s_{t-1}, a_t)\). Under localized credit assignment, the policy gradient uses the step advantage \(\hat{A}_t = \sum_{k=t}^T \gamma^{k-t} r_k - V(s_{t-1})\):
\[g_{\text{PRM}} = \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_t \mid s_{t-1}) \cdot \hat{A}_t\]
By the law of total expectation and causality, future rewards are conditionally independent of past actions given intermediate state \(s_t\). For discount factor \(\gamma < 1\), the temporal horizon of correlation is bounded by the effective horizon \(1 / (1 - \gamma)\). Consequently, cross-step covariances decay exponentially with temporal separation \(|t' - t|\), collapsing the variance:
\[\operatorname{Var}\left(g_{\text{PRM}}\right) = \mathcal{O}\left(\frac{T}{1 - \gamma}\right) = \mathcal{O}(T)\]
The linear scaling under step-level rewards is the formal reason dense, per-step signals can make credit assignment over long trajectories more sample-efficient than a single terminal reward. It holds only if the step rewards are accurate; a learned step scorer with its own errors trades variance for bias, which is the trade Credit Across Turns weighs.
Continuous Cost Functions for Verification
Verifying after every step is too expensive, and verifying only at the end lets an early error waste every step after it. A cost function makes the trade explicit.
Let \(N\) denote the total trajectory length in steps. Let \(K\) denote the number of verification points scheduled across the trajectory. The total compute and latency cost of an agent task is modeled as:
\[C_{\text{total}} = N \cdot C_{\text{gen}} + K \cdot C_{\text{ver}} + \mathbb{E}[N_{\text{wasted}}] \cdot C_{\text{gen}} + \mathbb{E}[N_{\text{rollback}}] \cdot C_{\text{rollback}}\]
where:
- \(C_{\text{gen}}\) is the cost of generating a single action step.
- \(C_{\text{ver}}\) is the verification tax.
- \(\mathbb{E}[N_{\text{wasted}}]\) is the expected number of steps executed between the occurrence of an error and its detection.
- \(C_{\text{rollback}}\) is the overhead of rewinding state.
The optimal number of verifications \(K^*\) balances the marginal cost of verification against the expected cost of discarded forward progress:
\[K^* = N \sqrt{\frac{\lambda_{\text{error}} \cdot C_{\text{gen}}}{2 \cdot C_{\text{ver}}}}\]
where \(\lambda_{\text{error}}\) is the per-step error arrival rate. The number of verifications grows linearly with trajectory length, which is another way of saying that the optimal verification interval does not depend on how long the trajectory runs:
\[\frac{N}{K^*} = \sqrt{\frac{2 \cdot C_{\text{ver}}}{\lambda_{\text{error}} \cdot C_{\text{gen}}}}\]
A runtime therefore sets its cadence from the verification tax and the environment’s error rate alone, and does not need to know the trajectory length in advance.
Analytical minimization of discrete block latency
The same trade can be modeled discretely. Partition a run of \(N\) steps into blocks of \(m\) steps, verify at the end of each block, and restart a block whenever verification fails. With per-step reliability \(p\), step time \(T_{\text{step}}\), and per-block verification time \(T_{\text{ver}}\), the expected time is
\[T(m) = \frac{N}{m} \cdot \frac{m \cdot T_{\text{step}} + T_{\text{ver}}}{p^m} = N \cdot p^{-m} \left( T_{\text{step}} + \frac{T_{\text{ver}}}{m} \right)\]
To find the cadence \(m^*\) that minimizes \(T(m)\), we take the natural logarithm and differentiate with respect to \(m\):
\[\ln T(m) = \ln N - m \ln p + \ln \left( T_{\text{step}} + \frac{T_{\text{ver}}}{m} \right)\]
\[\frac{d}{dm} \ln T(m) = -\ln p - \frac{T_{\text{ver}} / m^2}{T_{\text{step}} + T_{\text{ver}} / m} = 0\]
Multiplying by \(m^2 (T_{\text{step}} + T_{\text{ver}} / m)\) yields the characteristic quadratic equation:
\[m^2 T_{\text{step}} (-\ln p) + m T_{\text{ver}} (-\ln p) - T_{\text{ver}} = 0\]
For high-reliability models (\(p \approx 1\)), we use the first-order Taylor approximation \(-\ln p = -\ln(1 - (1 - p)) \approx 1 - p\). Dividing through by \(T_{\text{step}} (1 - p)\):
\[m^2 + m \left(\frac{T_{\text{ver}}}{T_{\text{step}}}\right) - \frac{T_{\text{ver}}}{(1 - p) T_{\text{step}}} = 0\]
When the failure rate \((1 - p)\) is small, the constant term \(\frac{T_{\text{ver}}}{(1 - p) T_{\text{step}}}\) dominates the linear term \(m \frac{T_{\text{ver}}}{T_{\text{step}}}\). Solving for the positive root yields the first-principles square-root scaling law:
\[m^* \approx \sqrt{\frac{T_{\text{ver}}}{(1 - p) T_{\text{step}}}}\]
If a failure is instead detected where it occurs and costs on average the \(m/2\) steps since the last verification, rather than the whole block, the same balance produces the factor of 2 in Young’s checkpointing formula (Young 1974; Daly 2006):
\[m^* \approx \sqrt{\frac{2 \cdot T_{\text{ver}}}{(1 - p) \cdot T_{\text{step}}}}\]
The optimal verification cadence is therefore the same square-root law that sets checkpoint intervals in fault-tolerant computing, and Checkpoints uses it in that form (equation).
PageRank Symbol Graphing for Repository Maps
To build a compact repository map within a token budget, a runtime can model the codebase as a directed graph \(G = (V, E)\) of symbol definitions and references. The system computes the personalized PageRank vector \(\mathbf{r} \in \mathbb{R}^{|V|}\) over \(G\):
\[\mathbf{r} = (1 - d) \mathbf{p} + d A^T D^{-1} \mathbf{r}\]
where \(d \approx 0.85\) is the damping factor, \(A\) is the adjacency matrix, \(D\) is the degree matrix, and \(\mathbf{p}\) is a personalization preference vector initialized to bias toward files mentioned in the user’s issue description or recent git diffs.
Sorting symbols by score and packing them greedily until the budget is spent favors the definitions most referenced by, and closest to, the files the task names. Multi-Hop Retrieval uses this ranking for graph retrieval over code, and Agentic Retrieval pre-stages such a map before the agent searches.
Statistical Significance and Monte Carlo Bootstrapping
An agent’s outcome on a task varies from run to run (Resampling hierarchies), so a measured improvement is evidence only when it exceeds what that variation could produce by chance.
The required sample size \(N\) to detect an effect size \(\Delta p = p_2 - p_1\) with statistical significance \(\alpha\) and statistical power \(1 - \beta\) is formally governed by the two-proportion hypothesis test:
\[N \ge \frac{\left( z_{1 - \alpha/2} \sqrt{2 \bar{p}(1 - \bar{p})} + z_{1 - \beta} \sqrt{p_1(1 - p_1) + p_2(1 - p_2)} \right)^2}{(p_2 - p_1)^2}\]
where \(\bar{p} = (p_1 + p_2) / 2\), \(z_{1 - \alpha/2}\) is the standard normal critical value, and \(z_{1 - \beta}\) is the power critical value.
For an agent baseline success rate \(p_1\) of 0.30 and a targeted improvement to a \(p_2\) of 0.35 with \(\alpha = 0.05\) and \(\beta = 0.20\), the required \(N\) is 1,375 tasks per arm.
Metrics such as cost or turns per trajectory are often heavy-tailed, so intervals that assume a normal distribution can mislead. The nonparametric bootstrap (Efron and Tibshirani 1994) avoids that assumption by drawing \(B\) bootstrap resamples with replacement and computing the empirical percentile confidence interval:
\[[\theta_{\text{lower}}, \theta_{\text{upper}}] = \left[ \hat{\theta}^*_{\lfloor 0.025 B \rfloor}, \; \hat{\theta}^*_{\lfloor 0.975 B \rfloor} \right]\]
Finite-sample uncertainty uses these intervals, and the sample-size formula above, to decide how many tasks an evaluation needs before a difference can be trusted.
Deterministic Finite Automata and Grammar-Constrained Logit Decoding
Grammar-constrained decoding (Grammar-Guided Decoding) enforces formal-language compliance at each sampling step by compiling a regular grammar, such as one derived from a JSON schema, into a deterministic finite automaton (DFA) (Willard and Louf 2023). Context-free grammars need a pushdown automaton, but the masking argument below is unchanged.
Formally, let the target grammar be compiled into a DFA 5-tuple:
\[\mathcal{D} = \langle Q, \Sigma, \delta, q_0, F \rangle\]
where:
- \(Q\) is the finite set of parser automaton states.
- \(\Sigma\) is the input alphabet consisting of raw byte sequences (\(\Sigma = \{0, \dots, 255\}\)).
- \(\delta: Q \times \Sigma \to Q\) is the deterministic state transition function.
- \(q_0 \in Q\) is the designated start state.
- \(F \subseteq Q\) is the set of accepting states.
Let \(\mathcal{V}\) denote the model’s vocabulary of size \(|\mathcal{V}|\), where each token \(v \in \mathcal{V}\) corresponds to an immutable byte sequence \(s(v) = (b_1, b_2, \dots, b_m)\) with \(b_j \in \Sigma\). The extended transition function \(\delta^*: Q \times \Sigma^* \to Q \cup \{\bot\}\) evaluates the sequential consumption of a byte sequence from state \(q\):
\[\delta^*(q, \epsilon) = q, \quad \delta^*(q, (b_1, \dots, b_m)) = \delta^*(\delta(q, b_1), (b_2, \dots, b_m))\]
where \(\bot\) indicates an illegal transition (syntax error).
At generation step \(t\), let the automaton reside in state \(q_t \in Q\) after consuming prefix tokens \(x_{<t}\). The set of valid next tokens \(\mathcal{V}_{\text{valid}}(q_t) \subseteq \mathcal{V}\) comprises all vocabulary entries whose byte sequences do not lead to \(\bot\):
\[\mathcal{V}_{\text{valid}}(q_t) = \left\{ v \in \mathcal{V} \;\middle|\; \delta^*(q_t, s(v)) \ne \bot \right\}\]
Before the softmax, the unnormalized logit vector \(\mathbf{z}_t \in \mathbb{R}^{|\mathcal{V}|}\) is transformed elementwise:
\[z_{t, v}' = \begin{cases} z_{t, v} & \text{if } v \in \mathcal{V}_{\text{valid}}(q_t) \\ -\infty & \text{if } v \notin \mathcal{V}_{\text{valid}}(q_t) \end{cases}\]
The normalized probability distribution is:
\[\Pr(x_t = v \mid x_{<t}) = \frac{\exp(z_{t, v}')}{\sum_{w \in \mathcal{V}} \exp(z_{t, w}')}\]
Because \(\exp(-\infty) = 0\), the probability of sampling any token \(v \notin \mathcal{V}_{\text{valid}}(q_t)\) is strictly zero:
\[\forall v \notin \mathcal{V}_{\text{valid}}(q_t), \quad \Pr(x_t = v \mid x_{<t}) = 0\]
By induction over the sequence length, every completed generation \(x_{1:T}\) ending in \(q_T \in F\) belongs to the formal language \(\mathcal{L}(\mathcal{D})\) accepted by the grammar. The guarantee is syntactic only; a string in the language can still name a file that does not exist or do the wrong thing. At runtime the valid sets are precomputed into a bitmask per automaton state, \(\mathbf{M} \in \{0, 1\}^{|Q| \times |\mathcal{V}|}\), so the mask for a step is one table lookup. Decode-Loop Mechanics sizes that table and explains why it must sit beside the sampler.
Higher-Order Daly Checkpoint Cadence Derivation
Checkpoints sets the checkpoint interval with Young’s first-order balance between checkpoint overhead and lost work (equation):
\[T_{\text{opt}} = \sqrt{2 \cdot T_{\text{save}} \cdot M_{\text{MTBF}}}\]
When restart latency \(T_{\text{restart}}\) is non-negligible and the system is vulnerable to failure during the checkpoint commit phase itself, Daly (2006) extended Young’s model using a perturbation expansion over the Poisson failure process with arrival rate \(\lambda = 1 / M_{\text{MTBF}}\).
Let \(\tau\) denote the checkpoint interval. The total expected wall-clock time \(\mathbb{E}[T_{\text{total}}]\) required to accomplish a unit of useful work \(T_{\text{work}}\) under checkpoint serialization latency \(T_{\text{save}}\) and recovery restart latency \(R = T_{\text{restart}}\) satisfies:
\[\mathbb{E}[T_{\text{total}}] = T_{\text{work}} \cdot \frac{e^{\lambda (\tau + T_{\text{save}})} - 1}{\lambda \tau} + \lambda \mathbb{E}[T_{\text{total}}] \cdot R\]
Expanding the exponential term \(e^{\lambda (\tau + T_{\text{save}})}\) into a Taylor series up to second order in \(\lambda\):
\[e^{\lambda (\tau + T_{\text{save}})} \approx 1 + \lambda (\tau + T_{\text{save}}) + \frac{\lambda^2 (\tau + T_{\text{save}})^2}{2} + \mathcal{O}(\lambda^3)\]
Substituting into the expected execution time and differentiating with respect to \(\tau\) to solve for the minimizing interval \(\tau^*\):
\[\frac{\partial \mathbb{E}[T_{\text{total}}]}{\partial \tau} = 0 \implies \tau^* = \sqrt{\frac{2 T_{\text{save}}}{\lambda}} \left[ 1 + \frac{1}{3}\sqrt{\frac{\lambda T_{\text{save}}}{2}} \right] - T_{\text{save}} + \mathcal{O}(\lambda)\]
Substituting \(\lambda = 1 / M_{\text{MTBF}}\) yields Daly’s higher-order analytical equation:
\[T_{\text{opt}}^{\text{Daly}} = \sqrt{2 \cdot T_{\text{save}} \cdot M_{\text{MTBF}}} \cdot \left[ 1 + \frac{1}{3}\sqrt{\frac{T_{\text{save}}}{2 M_{\text{MTBF}}}} \right] - T_{\text{save}}\]
When checkpointing is fast relative to the time between failures (\(T_{\text{save}} \ll M_{\text{MTBF}}\)), the correction is small. For example, with \(T_{\text{save}} = 2.5\text{ s}\) and \(M_{\text{MTBF}} = 1{,}600\text{ s}\), the second-order term \(\frac{1}{3}\sqrt{\frac{T_{\text{save}}}{2 M_{\text{MTBF}}}} \approx \frac{1}{3}\sqrt{0.00078} \approx 0.0093\) changes the interval by less than 1 percent, so Young’s first-order formula is the practical rule for agent runtimes, whose checkpoints are small next to their failure intervals.
Unbiased Pass@\(k\) Combinatorial Derivation and Numerical Stability
Estimating pass@\(k\) by plugging a task’s observed success rate \(\hat{p} = c/n\) into \(1 - (1 - \hat{p})^k\) is biased when \(n\) is small. Chen et al. (2021) derived an unbiased estimator by treating evaluation as sampling \(k\) of the \(n\) attempts without replacement.
Let \(n\) denote the total number of candidate trajectories generated and evaluated for a given benchmark task (\(n \ge k\)), and let \(c\) denote the number of trajectories that successfully satisfy the verification oracle (\(0 \le c \le n\)).
Suppose an evaluation system selects a subset of \(k\) trajectories uniformly at random without replacement. The task is counted as solved under the Pass@\(k\) metric if at least one of the \(k\) selected trajectories succeeded. Conversely, the failure condition occurs if and only if all \(k\) selected trajectories were drawn from the pool of \(n - c\) failed trajectories.
The total number of ways to draw \(k\) trajectories from the candidate pool of size \(n\) is \(\binom{n}{k}\). If \(n - c < k\), the pool contains fewer than \(k\) failures, making it impossible to select \(k\) failing trajectories; thus, the probability of complete failure is strictly zero, and \(\text{Pass}@k = 1.0\).
If \(n - c \ge k\), the number of ways to draw \(k\) failures from the \(n - c\) failed trajectories is \(\binom{n - c}{k}\). Under uniform random sampling without replacement, the probability that all \(k\) drawn trajectories fail is:
\[\Pr(\text{all } k \text{ selections fail}) = \frac{\binom{n - c}{k}}{\binom{n}{k}}\]
The unbiased probability that at least one of the \(k\) trajectories succeeds is the complement:
\[\text{Pass}@k = 1 - \frac{\binom{n - c}{k}}{\binom{n}{k}}\]
Averaging across a test suite of \(M\) benchmark tasks yields the global unbiased estimator:
\[\text{Pass}@k = \mathbb{E}_{\text{tasks}}\left[ 1 - \frac{\binom{n - c}{k}}{\binom{n}{k}} \right]\]
Numerical stability via log-sum expansion
Evaluating binomial coefficients via direct factorials (\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)) rapidly causes floating-point overflow on standard 64-bit hardware, where factorials exceed IEEE 754 float limits at \(171! \approx 7.26 \times 10^{306}\). Expanding the ratio into a telescoping product:
\[\frac{\binom{n - c}{k}}{\binom{n}{k}} = \frac{\frac{(n - c)!}{k! (n - c - k)!}}{\frac{n!}{k! (n - k)!}} = \frac{(n - c)! (n - k)!}{n! (n - c - k)!} = \prod_{i=1}^k \frac{n - c - k + i}{n - k + i}\]
Computing this product directly can suffer from arithmetic underflow when \(k\) is large. Converting the product into the log-domain yields a numerically stable summation:
\[\ln\left( \frac{\binom{n - c}{k}}{\binom{n}{k}} \right) = \sum_{i=1}^k \ln\left( \frac{n - c - k + i}{n - k + i} \right)\]
Exponentiating and subtracting from unity yields the standard runtime formulation implemented in evaluation harnesses:
\[1 - \frac{\binom{n - c}{k}}{\binom{n}{k}} = 1 - \exp\left( \sum_{i=1}^k \ln\left( \frac{n - c - k + i}{n - k + i} \right) \right)\]
This formulation computes the estimator stably for large rollout counts (for example, \(n = 1{,}000\) and \(k = 100\)) in \(\mathcal{O}(k)\) time. Pass@k: The ceiling of best-of-k selection reads pass@\(k\) as the ceiling of best-of-\(k\) selection, and Latent potential decoupling reports it beside pass\(^k\).
The reliability estimator pass\(^k\)
Pass@\(k\) asks whether at least one of \(k\) runs succeeds. Reliability asks whether all \(k\) do. Drawing \(k\) of the \(n\) runs without replacement, all \(k\) succeed only if all are drawn from the \(c\) successes, so the unbiased estimator is
\[\text{pass}^k = \mathbb{E}_{\text{tasks}}\left[ \frac{\binom{c}{k}}{\binom{n}{k}} \right] = \mathbb{E}_{\text{tasks}}\left[ \prod_{i=0}^{k-1} \frac{c - i}{n - i} \right]\]
which is zero whenever \(c < k\) and matches equation. The product form avoids overflow in the same way as the telescoping product above. For a task with independent per-run success probability \(p\), \(\text{pass}@k = 1 - (1-p)^k\) rises with \(k\) while \(\text{pass}^k = p^k\) falls, which is why the two diverge as \(k\) grows and why an agent’s potential and its reliability must be reported separately.
Wald’s Sequential Probability Ratio Test (SPRT) Decision Boundaries
Staged canary deployments decides whether to promote or roll back a canary with Wald’s sequential probability ratio test (Wald 1945). This section derives the test’s statistic and its two stopping boundaries in the chapter’s convention.
Let \(x_1, x_2, \dots\) be the outcomes of successive canary trajectories, with \(x_i = 1\) for an accepted task and \(x_i = 0\) otherwise, independent with success probability \(p\). The test compares
\[H_0: p = p_0 \quad (\text{the acceptable success rate}), \qquad H_1: p = p_1 = p_0 - \Delta \quad (\text{the degraded rate the gate must catch})\]
A single outcome has probability \(P(x \mid p) = p^{x} (1 - p)^{1 - x}\). After \(n\) trajectories with \(d_n\) accepted, the log-likelihood ratio in favor of \(H_0\) is
\[\Lambda_n = \sum_{i=1}^n \ln \frac{P(x_i \mid p_0)}{P(x_i \mid p_1)} = d_n \ln \frac{p_0}{p_1} + (n - d_n) \ln \frac{1 - p_0}{1 - p_1}\]
Each success adds \(\ln(p_0/p_1) > 0\) and each failure adds \(\ln\big((1-p_0)/(1-p_1)\big) < 0\), so \(\Lambda_n\) is a random walk that drifts upward under \(H_0\) and downward under \(H_1\). The test promotes when \(\Lambda_n \ge A\), rolls back when \(\Lambda_n \le B\), and otherwise keeps sampling.
Deriving the boundaries
Let \(\alpha\) be the probability of promoting a degraded candidate, \(\Pr(\text{promote} \mid H_1)\), and \(\beta\) the probability of rolling back a good one, \(\Pr(\text{roll back} \mid H_0)\). Let \(\Omega_P\) be the set of outcome sequences that end in promotion. Every sequence \(\mathbf{x} \in \Omega_P\) satisfies \(P(\mathbf{x} \mid H_0) \ge e^{A} P(\mathbf{x} \mid H_1)\), so summing over \(\Omega_P\),
\[1 - \beta = \sum_{\mathbf{x} \in \Omega_P} P(\mathbf{x} \mid H_0) \ge e^{A} \sum_{\mathbf{x} \in \Omega_P} P(\mathbf{x} \mid H_1) = e^{A} \alpha \quad\Longrightarrow\quad A \le \ln\frac{1 - \beta}{\alpha}\]
Symmetrically, every sequence \(\mathbf{x}\) in the rollback set \(\Omega_R\) satisfies \(P(\mathbf{x} \mid H_0) \le e^{B} P(\mathbf{x} \mid H_1)\), so
\[\beta = \sum_{\mathbf{x} \in \Omega_R} P(\mathbf{x} \mid H_0) \le e^{B} \sum_{\mathbf{x} \in \Omega_R} P(\mathbf{x} \mid H_1) = e^{B} (1 - \alpha) \quad\Longrightarrow\quad B \ge \ln\frac{\beta}{1 - \alpha}\]
Neglecting the overshoot when \(\Lambda_n\) crosses a boundary, Wald’s approximation sets the boundaries at these limits:
\[A = \ln\frac{1 - \beta}{\alpha}, \qquad B = \ln\frac{\beta}{1 - \alpha}\]
which are the boundaries Staged canary deployments uses. Because the overshoot only makes the realized error rates smaller, the test is conservative.
Expected length of the test
Each step adds \(z_i = \ln\big(P(x_i \mid p_0)/P(x_i \mid p_1)\big)\). Under the degraded rate, \(\mathbb{E}_{p_1}[z] = p_1 \ln(p_0/p_1) + (1 - p_1) \ln\big((1-p_0)/(1-p_1)\big) < 0\), and by Wald’s identity the expected number of canary trajectories before a decision is
\[\mathbb{E}_{p_1}[N] \approx \frac{(1 - \alpha) B + \alpha A}{\mathbb{E}_{p_1}[z]}\]
The worked canary in Staged canary deployments evaluates this expression. Because the canary receives only a share of traffic, the expected number of trajectories converts into hours of exposure, which is what sets the canary’s traffic share.
Truncated SVD and Low-Rank Attention Approximations
Low-rank compression of the attention state is one of the model-design levers that lower the bytes stored per token (From Context Tokens to KV State). Its mathematical basis is the truncated singular value decomposition (SVD) of the key and value matrices.
Let \(\mathbf{K}^{(l)} \in \mathbb{R}^{S \times d_{\text{head}}}\) denote the uncompressed Key activation matrix for layer \(l\) across an active sequence of \(S\) tokens. The singular value decomposition factors \(\mathbf{K}^{(l)}\) into orthogonal singular vectors:
\[\mathbf{K}^{(l)} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T = \sum_{i=1}^{\min(S, d_{\text{head}})} \sigma_i \mathbf{u}_i \mathbf{v}_i^T\]
where \(\mathbf{U} \in \mathbb{R}^{S \times S}\) and \(\mathbf{V} \in \mathbb{R}^{d_{\text{head}} \times d_{\text{head}}}\) are orthonormal basis matrices, and \(\mathbf{\Sigma}\) contains ordered singular values \(\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_{\min(S, d_{\text{head}})} \ge 0\).
A rank-\(r\) truncated SVD approximation \(\hat{\mathbf{K}}_r^{(l)}\) retains only the top \(r\) principal components (\(r \ll d_{\text{head}}\)):
\[\hat{\mathbf{K}}_r^{(l)} = \mathbf{U}_r \mathbf{\Sigma}_r \mathbf{V}_r^T = \sum_{i=1}^{r} \sigma_i \mathbf{u}_i \mathbf{v}_i^T\]
By the classical Eckart-Young-Mirsky Theorem, the truncated matrix \(\hat{\mathbf{K}}_r^{(l)}\) is the mathematically optimal rank-\(r\) approximation to \(\mathbf{K}^{(l)}\) under both the spectral norm (\(\|\cdot\|_2\)) and the Frobenius norm (\(\|\cdot\|_F\)). Specifically, the minimum Frobenius reconstruction error is determined entirely by the discarded tail singular values:
\[\min_{\operatorname{rank}(\mathbf{A}) \le r} \|\mathbf{K}^{(l)} - \mathbf{A}\|_F = \|\mathbf{K}^{(l)} - \hat{\mathbf{K}}_r^{(l)}\|_F = \sqrt{\sum_{j=r+1}^{d_{\text{head}}} \sigma_j^2}\]
The fraction of total activation energy preserved by the rank-\(r\) subspace projection is:
\[\eta_r = \frac{\sum_{i=1}^r \sigma_i^2}{\sum_{i=1}^{d_{\text{head}}} \sigma_i^2}\]
When the singular values decay steeply, a rank well below \(d_{\text{head}}\) preserves most of the energy, and the error in every reconstructed attention score \(\mathbf{q}^T \hat{\mathbf{k}}\) is bounded by \(\|\mathbf{q}\|_2\) times the largest discarded singular value. How steeply the spectrum decays, and therefore what rank a model tolerates, must be measured per model and per layer; compression that looks free on average can still change which earlier tokens a step attends to most.
Quadratic Compounding Error in Trajectory Imitation
The error compounding bound of sequential imitation learning under autoregressive distribution shift was formally established by Ross et al. (2011). Here we provide the complete measure-theoretic derivation.
Let an agent policy \(\pi_\theta\) interact with a discrete-time Markov Decision Process over horizon \(H\). Assume the policy incurs an expected per-step 0-1 error rate bounded by \(\epsilon \in (0, 1)\) under the state distribution \(d_{\pi^*}^t\) induced by an optimal expert \(\pi^*\):
\[\mathbb{E}_{s \sim d_{\pi^*}^t} \left[ \mathbb{I}\left( \pi_\theta(s) \neq \pi^*(s) \right) \right] \le \epsilon\]
Let \(d_{\pi_\theta}^t\) denote the state distribution induced by running policy \(\pi_\theta\) up to time step \(t\). At step \(t\), the Total Variation distance between the student and expert state distributions is bounded by the probability that \(\pi_\theta\) has committed at least one mistake at any prior step \(\tau < t\):
\[D_{\text{TV}}\left( d_{\pi_\theta}^t, d_{\pi^*}^t \right) \le 1 - (1 - \epsilon)^t \le t \epsilon\]
The expected cumulative task loss \(\mathcal{J}(\pi_\theta)\) over horizon \(H\) evaluates to the sum of error expectations across all time steps:
\[\mathcal{J}(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=1}^H \mathbb{I}\left( \pi_\theta(s_t) \neq \pi^*(s_t) \right) \right] = \sum_{t=1}^H \mathbb{E}_{s \sim d_{\pi_\theta}^t} \left[ \mathbb{I}\left( \pi_\theta(s) \neq \pi^*(s) \right) \right]\]
Applying the variational inequality \(\mathbb{E}_{P}[f] \le \mathbb{E}_{Q}[f] + \|f\|_\infty D_{\text{TV}}(P, Q)\) where \(\|f\|_\infty = 1\):
\[\begin{aligned} \mathcal{J}(\pi_\theta) &\le \sum_{t=1}^H \left( \mathbb{E}_{s \sim d_{\pi^*}^t} \left[ \mathbb{I}\left( \pi_\theta(s) \neq \pi^*(s) \right) \right] + D_{\text{TV}}\left( d_{\pi_\theta}^t, d_{\pi^*}^t \right) \right) \\ &\le \sum_{t=1}^H \left( \epsilon + t \epsilon \right) \\ &= \epsilon H + \epsilon \frac{H(H+1)}{2} \\ &= \mathcal{O}\left( \epsilon H^2 \right) \end{aligned}\]
Under the DAgger algorithm, by collecting corrective demonstrations on states sampled from the policy’s own rollout distribution \(d_{\pi_{\theta_k}}\), the Total Variation penalty vanishes because the training distribution directly covers the student’s operational mistakes. The expected cumulative regret simplifies to:
\[\mathcal{J}(\pi_{\text{DAgger}}) \le \epsilon H + \mathcal{O}(1) = \mathcal{O}(\epsilon H)\]
recovering the optimal linear scaling bound as explored in Exposure Bias and On-Policy Data.
Optimal Supervisory Escalation Thresholds under Asymmetric Damage
Deciding whether a proposed action should wait at an approval gate (Approval Gates) rather than run automatically is a binary decision under uncertainty with asymmetric costs.
Let \(a \in \mathcal{A}\) denote a candidate action proposed by the model. The true outcome state is binary: success (\(Y = 0\)) or catastrophic invariant failure (\(Y = 1\)). The runtime has an estimate \(\hat{p} = \mathbb{P}(Y = 1 \mid \mathbf{x}, a) \in [0, 1]\) computed from features \(\mathbf{x}\) it can observe, such as the action’s authority level, recent error counts, or the task’s domain.
We define the loss matrix \(\mathbf{L}(d, y)\) for decision \(d \in \{\text{Auto}, \text{Escalate}\}\) and outcome \(y \in \{0, 1\}\):
- \(\mathbf{L}(\text{Auto}, 0) = C_{\text{compute}}\): The direct token and compute cost of autonomous execution.
- \(\mathbf{L}(\text{Auto}, 1) = C_{\text{compute}} + C_{\text{blast}}\): The compute cost plus the unrecoverable damage of external failure.
- \(\mathbf{L}(\text{Escalate}, 0) = C_{\text{compute}} + C_{\text{human}}\): The compute cost plus human supervisor inspection latency and labor cost.
- \(\mathbf{L}(\text{Escalate}, 1) = C_{\text{compute}} + C_{\text{human}}\): Human intervention prevents the failure, incurring only inspection cost.
Under risk-neutral Bayesian decision theory, the expected risk \(\mathcal{R}(d \mid \hat{p})\) of each action is:
\[\mathcal{R}(\text{Auto} \mid \hat{p}) = (1 - \hat{p}) C_{\text{compute}} + \hat{p} (C_{\text{compute}} + C_{\text{blast}}) = C_{\text{compute}} + \hat{p} \cdot C_{\text{blast}}\]
\[\mathcal{R}(\text{Escalate} \mid \hat{p}) = C_{\text{compute}} + C_{\text{human}}\]
The optimal decision rule escalates to a human supervisor (\(d^* = \text{Escalate}\)) if and only if \(\mathcal{R}(\text{Auto} \mid \hat{p}) > \mathcal{R}(\text{Escalate} \mid \hat{p})\):
\[\hat{p} \cdot C_{\text{blast}} > C_{\text{human}} \iff \hat{p} > \frac{C_{\text{human}}}{C_{\text{blast}}} \equiv P_{\text{threshold}}\]
Risk-averse escalation under estimator variance
When the estimated failure probability \(\hat{p}\) has nonzero estimation variance \(\sigma_p^2\) (such as during out-of-distribution prompts), risk-neutral thresholding underestimates tail risk. Under a minimax or Neyman-Pearson risk-aversion framework with significance level \(\alpha\), the runtime bounds the probability of an unhandled catastrophic failure:
\[\mathbb{P}\left( Y = 1 \land d = \text{Auto} \right) \le \epsilon\]
Using the upper confidence bound \(p_{\text{UCB}}(\hat{p}, \alpha) \approx \hat{p} + z_{1-\alpha} \sigma_p\), the risk-averse escalation condition becomes:
\[d^* = \text{Escalate} \iff p_{\text{UCB}}(\hat{p}, \alpha) > \frac{C_{\text{human}}}{C_{\text{blast}}}\]
As the uncertainty \(\sigma_p\) grows, in domains the estimator has seen little of, the rule escalates more actions without manual retuning. The rule decides when to ask for approval; it does not replace the gate for irreversible actions, which Pivot Action Irreversibility requires regardless of \(\hat{p}\).
Multi-Agent Amdahl’s Law Stationary Root Analysis
The delegation trade-off bounds the speedup of splitting a task across \(M\) agents with Amdahl’s law plus a coordination tax (equation):
\[\text{Speedup}(M) = \frac{1}{D(M)}, \qquad D(M) = (1 - f) + \frac{f}{M} + \sigma (M - 1) + \kappa M (M - 1)\]
where \(f \in (0, 1]\) is the fraction of the work that divides across agents, \(\sigma \ge 0\) the contention coefficient, and \(\kappa \ge 0\) the coherency coefficient, with \(\sigma + \kappa > 0\). This section shows that the speedup has a single peak and locates it.
Maximizing the speedup means minimizing \(D(M)\) over \(M > 0\). Differentiating,
\[\frac{d D}{d M} = -\frac{f}{M^2} + \sigma + \kappa (2M - 1)\]
and setting the derivative to zero gives the stationary condition
\[P(M) = 2\kappa M^3 + (\sigma - \kappa) M^2 - f = 0\]
- Exactly one positive root. The coefficients of \(P(M)\), in order, are \(2\kappa\), \(\sigma - \kappa\), \(0\), and \(-f\). Whether \(\sigma - \kappa\) is positive or negative, the sequence of nonzero signs changes exactly once, so by Descartes’ rule of signs \(P\) has exactly one positive real root \(M^*\). When \(\kappa = 0\) the condition reduces to \(\sigma M^2 = f\), so \(M^* = \sqrt{f / \sigma}\).
- The root is the global optimum. The second derivative, \[\frac{d^2 D}{d M^2} = \frac{2f}{M^3} + 2\kappa,\] is positive for every \(M > 0\), so \(D\) is strictly convex, \(M^*\) is its unique minimum, and \(M^*\) maximizes the speedup.
Two consequences matter for design. With \(\kappa > 0\), the speedup does not plateau; past \(M^*\) it falls, because the pairwise term grows as \(M^2\) while the gain \(f/M\) shrinks. And a split pays at all only if \(D(M) < 1\) for some \(M > 1\), which is the third deployment gate of Single-agent baseline benchmarking. In practice \(M^*\) is found by evaluating \(D(M)\) at the small integers a team would actually deploy, with \(\sigma\) and \(\kappa\) fitted from measured runs at two or three fleet sizes.
High-Dimensional Measure Concentration and the Curse of Dimensionality
As discussed in Hybrid Retrieval, high-dimensional vector retrieval breaks spatial partitioning trees (such as \(k\)-d trees and \(R\)-trees), degrading them into exhaustive linear scans. This section derives the closed-form volume of a \(D\)-dimensional continuous Euclidean ball and formalizes the loss of distance contrast under Beyer’s theorem.
Continuous hypersphere volume and shell concentration
The volume of a \(D\)-dimensional Euclidean ball of radius \(r\) is given by:
\[V_D(r) = \int_{\|\mathbf{x}\|_2 \le r} d\mathbf{x} = r^D \cdot V_D(1)\]
To compute the unit ball volume \(V_D(1)\), we integrate the separable Gaussian function \(\exp(-\|\mathbf{x}\|_2^2)\) over all \(\mathbb{R}^D\):
\[\int_{\mathbb{R}^D} e^{-\|\mathbf{x}\|_2^2} d\mathbf{x} = \prod_{i=1}^D \int_{-\infty}^{\infty} e^{-x_i^2} dx_i = (\sqrt{\pi})^D = \pi^{D/2}\]
Switching to spherical polar coordinates, with differential surface area \(S_{D-1}(r) = \frac{d}{dr} V_D(r) = D \cdot r^{D-1} V_D(1)\):
\[\int_{\mathbb{R}^D} e^{-\|\mathbf{x}\|_2^2} d\mathbf{x} = \int_0^\infty e^{-r^2} S_{D-1}(r) dr = D \cdot V_D(1) \int_0^\infty r^{D-1} e^{-r^2} dr\]
Applying the substitution \(u = r^2\) (\(du = 2r dr\)):
\[\int_0^\infty r^{D-1} e^{-r^2} dr = \frac{1}{2} \int_0^\infty u^{\frac{D}{2} - 1} e^{-u} du = \frac{1}{2} \Gamma\left(\frac{D}{2}\right)\]
Equating the Cartesian and spherical integrals:
\[\pi^{D/2} = D \cdot V_D(1) \cdot \frac{1}{2} \Gamma\left(\frac{D}{2}\right) = V_D(1) \cdot \frac{D}{2} \Gamma\left(\frac{D}{2}\right) = V_D(1) \cdot \Gamma\left(\frac{D}{2} + 1\right)\]
Solving for \(V_D(1)\) and scaling by \(r^D\) yields the closed-form volume:
\[V_D(r) = \frac{\pi^{D/2}}{\Gamma\left(\frac{D}{2} + 1\right)} r^D\]
For an outer shell of relative thickness \(\epsilon\) (\(0 < \epsilon < 1\)), the volume of the inner sphere of radius \(r(1 - \epsilon)\) is \(V_D(r(1 - \epsilon)) = (1 - \epsilon)^D V_D(r)\). The fraction of total volume contained in the outer shell is:
\[\frac{V_D(r) - V_D(r(1 - \epsilon))}{V_D(r)} = 1 - (1 - \epsilon)^D\]
As \(D \to \infty\), \((1 - \epsilon)^D \to 0\) exponentially fast. For \(D = 1536\) and \(\epsilon = 0.01\), over 99.99998 percent of the volume resides in the outer 1 percent of the radius.
Vanishing distance contrast (beyer’s theorem)
Beyer et al. (1999) established that nearest neighbor search becomes topologically ill-defined when the contrast between the nearest and farthest data points asymptotically vanishes.
Let \(\mathbf{x}_1, \dots, \mathbf{x}_N\) be independent random vectors in \(\mathbb{R}^D\) drawn from a distribution with finite moments, and let \(\mathbf{q}\) be an independent query vector. Define \(D_{\min}(N, D) = \min_{1 \le i \le N} \|\mathbf{x}_i - \mathbf{q}\|_p\) and \(D_{\max}(N, D) = \max_{1 \le i \le N} \|\mathbf{x}_i - \mathbf{q}\|_p\).
If the relative variance of pairwise distance scales sub-quadratically relative to the mean distance:
\[\lim_{D \to \infty} \frac{\operatorname{Var}(\|\mathbf{x} - \mathbf{q}\|_p)}{\mathbb{E}[\|\mathbf{x} - \mathbf{q}\|_p]^2} = 0\]
then for any fixed dataset size \(N\) and any \(\epsilon > 0\):
\[\lim_{D \to \infty} \mathbb{P}\left( \frac{D_{\max}(N, D) - D_{\min}(N, D)}{D_{\min}(N, D)} \le \epsilon \right) = 1\]
Under this condition, the ratio of distance to the nearest neighbor versus the farthest neighbor converges in probability to 1. In high-dimensional latent space, every stored memory vector is approximately equidistant from the query vector \(\mathbf{q}\). Consequently, a query bounding ball centered at \(\mathbf{q}\) must expand to encompass virtually all data points to guarantee finding the exact nearest neighbor, forcing spatial tree index structures to traverse every leaf node.