# Inference Cost Foundations {#sec-vol3-appendix-inference}

An agent engineer does not build the serving system, but every design decision in an agent pays its prices: an output token that costs far more time than a prompt token, a context that occupies memory for as long as the trajectory lives, a tool wait that holds that memory idle, and a fleet whose capacity is set by how long trajectories last rather than how long calls take. The chapters state these consequences where they are first needed and price them in tokens, turns, seconds, and dollars. This appendix derives them, once, from how a model is served, so that a reader who wants to check a chapter's claim, or redo an estimate for a different model or accelerator, has the arithmetic in one place. Every number here comes from the same reference model and accelerator the chapters use, collected in @sec-vol3-appendix-inference-assumptions for substitution.

## How to Use This Appendix {.unnumbered}

Start from the agent-level question in @tbl-appdx-inference-lookup and jump to the section that derives its answer.

| If you need to know...                                                                      | Jump to...                               | What you get                                                                                 |
|:--------------------------------------------------------------------------------------------|:-----------------------------------------|:---------------------------------------------------------------------------------------------|
| Why an output token costs about two orders of magnitude more time than a prompt token       | @sec-vol3-appendix-inference-roofline    | The roofline, prefill and decode intensity, per-token floors, and where the ratio comes from |
| Why time to first token grows faster than linearly at long contexts                         | @sec-vol3-appendix-inference-roofline    | The attention term of prefill and the length at which it matches the weight term             |
| Why batching lowers the fleet's cost per token but not one trajectory's latency             | @sec-vol3-appendix-inference-roofline    | Step time as a function of batch size; the batch at which decode turns compute-bound         |
| Where sampling and grammar masks run, and why speculative decoding preserves the output     | @sec-vol3-appendix-inference-decode-loop | Logit versus token-identifier transfer, mask table sizes, and the acceptance rule            |
| How much memory a trajectory's context occupies, and how attention design changes it        | @sec-vol3-appendix-inference-kv-cache    | Bytes per token from model geometry, multi-head versus grouped versus multi-query attention  |
| How many trajectories are live at once, and how tool waits and utilization inflate capacity | @sec-vol3-appendix-inference-queueing    | Little's law with tool waits, resident versus active state, and the queueing knee            |
| Why database transactions do not extend to an agent's tools                                 | @sec-vol3-appendix-inference-distributed | Two-phase commit, sagas, and write-ahead logging as background                               |
| Which model, accelerator, and node values the book assumes                                  | @sec-vol3-appendix-inference-assumptions | The reference inputs, ready to substitute                                                    |

: **Question-to-Derivation Lookup**: Agent-level questions and the sections that derive their answers. {#tbl-appdx-inference-lookup tbl-colwidths="[42,26,32]"}

## Why Output Costs More Than Input {#sec-vol3-appendix-inference-roofline}

```{python}
#| label: calc-vol3-appendix-inference-serving-ref
#| echo: false
# ┌─────────────────────────────────────────────────────────────────────────────
# │ REFERENCE SERVING QUANTITIES (LEGO)
# ├─────────────────────────────────────────────────────────────────────────────
# │ Context: Every derivation in this appendix; the per-call estimate of
# │          @sec-vol3-foundation-model-cost and the KV geometry of
# │          @sec-vol3-kvcache-geometry use the same inputs, so their numbers
# │          and these must agree.
# │
# │ Goal: Derive the ridge point, decode and prefill floors, their ratio, the
# │       long-context attention crossover, bytes of attention state per token
# │       for three attention designs, and the per-node attention-state pool.
# │ Show: 591 FLOP/byte ridge; 21.1 ms and 71 us per token; ratio 295;
# │       crossover near 108,000 tokens; 327,680 bytes/token; 526.0 GB pool;
# │       48 trajectories at 32,768 tokens.
# │ How:  Roofline with 8-bit weights at the peak 8-bit rate; attention FLOPs
# │       2 L d S^2 for a causal prefill; calc_kv_cache_size on registry
# │       geometry. Model, accelerator, and node come from MLSysIM
# │       (Llama-3-70B, H100, DGX H100); the prose names none of them.
# └─────────────────────────────────────────────────────────────────────────────
from mlsysim import *
from mlsysim.fmt import fmt_memory_capacity

class ServingRef:
    # ┌── 1. LOAD (Constants & Parameters) ─────────────────────────────────
    model = Models.Language.Llama3_70B
    accel = Hardware.Cloud.H100
    node = Systems.Nodes.DGX_H100
    weight_bytes = 1  # 8-bit weights, bytes per parameter (as in the call-price estimate)
    kv_bytes = 2  # 16-bit keys and values, bytes per element
    runtime_reserve = 20 * GB  # scenario: activations and runtime buffers per node
    s_agent = 32_768  # scenario: context length of a long agent trajectory

    # ┌── 2. EXECUTE (Compute) ─────────────────────────────────────────────
    params = model.parameters.to(ureg.count).magnitude
    n_layers = model.layers
    d_model = model.hidden_dim
    n_heads = model.heads
    n_kv_heads = model.kv_heads
    d_head = d_model // n_heads
    bw = accel.memory.bandwidth.to(ureg.byte / ureg.second).magnitude
    peak = accel.compute.precision_flops["fp8"].to(ureg.flop / ureg.second).magnitude
    ridge = peak / bw  # FLOP per byte
    i_decode = 2 / weight_bytes  # FLOP per byte of weights, batch of one
    t_dec = params * weight_bytes / bw  # seconds per output token, batch of one
    t_pre = 2 * params / peak  # seconds per prompt token at the peak rate
    ratio = t_dec / t_pre
    b_star = peak * weight_bytes / (2 * bw)  # tokens per pass at which a pass turns compute-bound
    util_decode = i_decode / ridge
    s_cross = params / (n_layers * d_model)  # prompt length where attention arithmetic equals weight arithmetic
    attn_share_agent = s_agent * n_layers * d_model / params  # attention / weight arithmetic at s_agent

    m_token = calc_kv_cache_size(n_layers, n_kv_heads, d_head, 1, 1, kv_bytes).to(byte).magnitude
    m_token_mha = calc_kv_cache_size(n_layers, n_heads, d_head, 1, 1, kv_bytes).to(byte).magnitude
    m_token_mqa = calc_kv_cache_size(n_layers, 1, d_head, 1, 1, kv_bytes).to(byte).magnitude
    kv_agent_gb = s_agent * m_token / 1e9
    kv_agent_mha_gb = s_agent * m_token_mha / 1e9
    kv_agent_mqa_gb = s_agent * m_token_mqa / 1e9

    n_acc = node.accelerators_per_node
    node_hbm_gb = (n_acc * node.accelerator.memory.capacity).to(GB).magnitude
    weights16_gb = model.size_in_bytes(BYTES_FP16).to(GB).magnitude
    pool_gb = node_hbm_gb - weights16_gb - runtime_reserve.to(GB).magnitude
    conc_agent = int(pool_gb // kv_agent_gb)

    # ┌── 3. GUARD (Invariants) ───────────────────────────────────────────
    check(abs(ratio - b_star) / ratio < 1e-9, "The decode/prefill ratio must equal the compute-bound pass size")
    check(ratio > 100, f"An output token should cost two orders of magnitude more time than a prompt token, got {ratio:.0f}")
    check(int(m_token) == 327_680, "KV bytes per token must equal 2 * 80 * 8 * 128 * 2")
    check(conc_agent == 48, f"Node concurrency at 32k must match the KV chapter, got {conc_agent}")
    check(s_cross > s_agent, "Attention arithmetic should stay below weight arithmetic at the agent context length")

    # ┌── 4. OUTPUT (Formatting) ──────────────────────────────────────────
    params_b_str = fmt(params / 1e9, precision=1)
    n_layers_str = fmt_int(n_layers)
    d_model_str = fmt_int(d_model)
    n_heads_str = fmt_int(n_heads)
    n_kv_heads_str = fmt_int(n_kv_heads)
    d_head_str = fmt_int(d_head)
    bw_str = fmt(bw / 1e12, precision=2)
    peak_str = fmt_int(peak / 1e12)
    ridge_str = fmt_int(ridge)
    i_decode_str = fmt_int(i_decode)
    util_decode_str = fmt(util_decode * 100, precision=2)
    t_dec_val_str = fmt(t_dec * 1e3, precision=1)
    t_pre_val_str = fmt_int(t_pre * 1e6)
    ratio_str = fmt_int(ratio)
    s_cross_str = fmt_int(round(s_cross, -3))
    s_agent_str = fmt_int(s_agent)
    attn_share_agent_str = fmt_int(attn_share_agent * 100)
    m_token_str = fmt_int(m_token)
    m_token_mha_str = fmt_int(m_token_mha)
    m_token_mqa_str = fmt_int(m_token_mqa)
    m_token8_str = fmt_int(m_token / 2)
    kv_agent_str = fmt(kv_agent_gb, precision=1)
    kv_agent_mha_str = fmt(kv_agent_mha_gb, precision=1)
    kv_agent_mqa_str = fmt(kv_agent_mqa_gb, precision=2)
    n_acc_str = fmt_int(n_acc)
    reserve_str = fmt_int(runtime_reserve.to(GB).magnitude)
    pool_str = fmt(pool_gb, precision=1)
    conc_agent_str = fmt_int(conc_agent)
    acc_hbm_str = fmt_memory_capacity(node.accelerator.memory.capacity, unit=GiB)
```

Every model call does two kinds of work. It reads the prompt, a step called prefill, and it generates the reply one token at a time, a step called decode. The two run on the same accelerator and use the same weights, yet an output token costs about `{python} ServingRef.ratio_str` times as much time as a prompt token on the reference configuration. That ratio is the most consequential serving fact for agent design (principle \ref{pri-vol3-memory-bandwidth-decoding}), and it follows from one model of accelerator performance.

### The roofline

An accelerator has two limits, the rate $\pi$ at which it performs arithmetic (operations per second) and the rate $\beta$ at which its memory delivers data (bytes per second). A computation's **arithmetic intensity** $\mathcal{I}$ is the number of operations it performs per byte it moves. The roofline model [@williams2009] bounds attainable performance by whichever limit binds first:

$$P = \min\left( \pi, \; \mathcal{I} \cdot \beta \right)$$

The two limits meet at the ridge point $\mathcal{I}^* = \pi / \beta$. A computation with $\mathcal{I} < \mathcal{I}^*$ is limited by memory bandwidth, and adding arithmetic capacity does nothing for it; a computation with $\mathcal{I} \ge \mathcal{I}^*$ is limited by arithmetic. For the reference accelerator at 8-bit precision, $\pi$ = `{python} ServingRef.peak_str` trillion operations per second and $\beta$ = `{python} ServingRef.bw_str` TB/s, so $\mathcal{I}^* \approx$ `{python} ServingRef.ridge_str` operations per byte.

### Prefill and decode

A transformer with $N$ parameters performs about $2N$ operations per token, one multiply and one add per weight, and must read its $N b$ bytes of weights, where $b$ is bytes per parameter. What differs between prefill and decode is how many tokens share one read of the weights.

Prefill processes all $S$ prompt tokens in one pass, so one read of the weights serves $S$ tokens, and its intensity is about $2NS / Nb = 2S/b$. For any prompt longer than a few hundred tokens this is far above the ridge, prefill is limited by arithmetic, and its time per token approaches

$$t_{\text{prefill}} \approx \frac{2N}{\pi}$$ {#eq-appdx-prefill-time}

Decode for a single stream generates one token per pass, and each token depends on the one before it, so the pass cannot be widened. One read of all the weights serves one token, the intensity is $2/b$, which is `{python} ServingRef.i_decode_str` operations per byte at 8-bit precision and about `{python} ServingRef.util_decode_str` percent of the ridge, and the time per token is set by how fast the weights stream from memory:

$$t_{\text{decode}} \ge \frac{N b}{\beta}$$ {#eq-appdx-shuttle-floor}

For the reference model, with $N$ = `{python} ServingRef.params_b_str` billion parameters at 8-bit precision, @eq-appdx-shuttle-floor gives a decode floor of `{python} ServingRef.t_dec_val_str` ms per output token, and @eq-appdx-prefill-time gives about `{python} ServingRef.t_pre_val_str` µs per prompt token. The ratio of the two is

$$\frac{t_{\text{decode}}}{t_{\text{prefill}}} = \frac{N b / \beta}{2N / \pi} = \frac{\pi \, b}{2 \beta} = \frac{b}{2} \, \mathcal{I}^*$$ {#eq-appdx-decode-prefill-ratio}

which is `{python} ServingRef.ratio_str` for the reference configuration. The ratio depends only on the accelerator's ridge point and the weight precision, not on the model's size, so every model served on the same accelerator at the same precision sees the same ratio. The same number has a second meaning. It is the number of tokens a pass must process before the pass stops being limited by memory, a fact the batching and speculative-decoding arguments below both use.

Three agent-level consequences follow, and @sec-vol3-foundation-model-cost prices each of them. A call's latency is dominated by its output length, so output is the latency the agent controls. A trajectory's cost is dominated by the input it re-sends on every turn, since input tokens are cheap individually but numerous. And any design that turns output tokens into input tokens, such as a diff instead of a rewrite or a structured result instead of prose, moves work from the expensive side of @eq-appdx-decode-prefill-ratio to the cheap side.

### Long contexts

@Eq-appdx-prefill-time counts only the weights. Attention adds work that grows with the context itself. The token at position $s$ compares its query with $s$ earlier keys and combines $s$ earlier values, about $4 L d s$ operations for a model with $L$ layers and width $d$. Summed over a causal prefill of $S$ tokens, attention adds about $2 L d S^2$ operations to the $2NS$ of the weights, so

$$T_{\text{prefill}}(S) \approx \frac{2NS + 2 L d S^2}{\pi}$$ {#eq-appdx-prefill-long}

The quadratic term equals the linear one at $S^* = N / (L d)$, about `{python} ServingRef.s_cross_str` tokens for the reference model, with $L$ = `{python} ServingRef.n_layers_str` and $d$ = `{python} ServingRef.d_model_str`. At `{python} ServingRef.s_agent_str` tokens, attention already adds about `{python} ServingRef.attn_share_agent_str` percent to the prefill arithmetic, and beyond $S^*$ it dominates. This is why time to first token grows faster than linearly at long lengths (@sec-vol3-context-engineering-physics), and why a context kept near its working set is cheaper per token as well as in total.

### Batching and the fleet's cost per token

A server running many trajectories does not decode them one at a time. It batches their decode steps, so one read of the weights produces one token for each of $B$ streams. Ignoring the attention state each stream also reads, the time of one step is

$$t_{\text{step}}(B) \approx \max\left( \frac{N b}{\beta}, \; \frac{2 N B}{\pi} \right)$$ {#eq-appdx-batched-step}

and the step stays at the memory-bound floor until $B$ reaches $\pi b / 2\beta$, the ratio of @eq-appdx-decode-prefill-ratio. Up to that batch size, adding streams costs almost no time per step, so the fleet's time per generated token falls as $1/B$ toward $2N/\pi$, the same as a prompt token's. This is the sense in which a fleet's bill follows the total number of tokens it processes, and why, for agents, that bill is dominated by re-sent input (@sec-vol3-foundation-model-cost).

Batching does nothing for a single trajectory's latency. Each step of a batched stream still takes at least the memory-bound floor, and the trajectory still waits for each tool result before its next call, so an agent's critical path runs at single-stream decode speed however large the fleet's batches are. In practice the attention state limits batching before arithmetic does. Each stream reads its own keys and values on every step, $s \cdot m_{\text{token}}$ bytes for a context of $s$ tokens (@sec-vol3-appendix-inference-kv-cache), so long-context agent batches stay limited by memory well below the batch size @eq-appdx-batched-step predicts, and the memory that holds that state limits how many streams fit at all (@sec-vol3-appendix-inference-queueing).

### Chunked prefill

When a trajectory resumes after a tool wait, its new observation must be prefilled while other trajectories on the same server are decoding. Run as one pass, a large prefill is arithmetic-bound for its whole length and stalls every co-scheduled decode until it finishes, so each of those trajectories sees a long gap between tokens. Chunked prefill splits the observation into fixed chunks of $c$ tokens and runs one chunk per pass alongside the ongoing decodes [@agrawal2024sarathi]. Because the decodes alone use almost none of the arithmetic (@eq-appdx-batched-step), a chunk of up to about $\pi b / 2\beta$ tokens rides along nearly free, and the pass time stays near the decode floor. Chunks larger than that lengthen every co-scheduled step. The resuming trajectory waits slightly longer for its first token, and every other trajectory keeps a bounded gap between tokens (@sec-vol3-kvcache-chunked-prefill).

## Decode-Loop Mechanics {#sec-vol3-appendix-inference-decode-loop}

Three pieces of per-token work sit inside every decode step besides the forward pass: turning logits into a token, applying any grammar mask, and, when speculative decoding is used, checking drafted tokens. Each is cheap only if it stays beside the sampler. This section sizes them.

### Where sampling runs

At each step the model produces one logit per vocabulary entry. With a vocabulary of $|\mathcal{V}| = 128{,}000$ entries stored in 16-bit precision, one logit vector is

$$128{,}000 \times 2\text{ bytes} = 256{,}000\text{ bytes}$$

per stream per token. A server running $B = 64$ streams at $R = 40$ tokens per second per stream emits $B \cdot R = 2{,}560$ tokens per second, so shipping raw logits to a separate process for sampling would move

$$2{,}560 \times 256{,}000\text{ bytes/s} \approx 655\text{ MB/s}$$

across the host interconnect, in 2,560 small transfers per second, each paying fixed transfer and synchronization overhead on the decode critical path. Sampling on the accelerator reduces each step's output to one integer token identifier of 4 bytes, or about 10 KB/s for the same load, a reduction of $256{,}000 / 4 = 64{,}000\times$. The token identifier is therefore the natural unit of exchange between the model service and everything outside it, and it is what the call surface streams (@sec-vol3-foundation-model-contract).

### Grammar masks

A grammar-constrained decoder needs the set of legal tokens for the current automaton state at every step (@sec-vol3-foundation-model-grammar-constrained). Stored as one bit per vocabulary entry, a mask for $|\mathcal{V}| = 131{,}072$ occupies

$$\frac{131{,}072}{8} = 16{,}384\text{ bytes}$$

and a schema that compiles into $|Q| = 512$ automaton states needs $512 \times 16{,}384 = 8{,}388{,}608$ bytes, about 8.4 MB, for the full table. A table that size fits in an accelerator's on-chip cache, so applying the mask costs one table lookup and one element-wise addition fused into the sampling step.

The alternative is to advance the automaton in a separate host process. Each step then pays a transfer of the sampled token to the host, a host-side state transition, a transfer of the next mask back, and a relaunch of the next step. Summed, these are on the order of 20 µs per token under ideal conditions and can reach 50 to 150 µs under host contention. Over a 500-token output that is roughly 10 to 75 ms of stall on the critical path, a direct tax on decode throughput. Large or recursive grammars whose state space is too big for dense tables use compressed token tries and precompute masks for likely next states, but the principle is unchanged. The mask must be ready when the logits are. @Sec-vol3-app-b-logit-masking decides when constraining is worth this cost, and @sec-vol3-appendix-math-dfa proves that the constrained output always parses.

### Speculative decoding

Speculative decoding shortens the serial chain without changing the output distribution [@leviathan2023fast; @chen2023accelerating]. A small draft model $q$ proposes $k$ tokens $\tilde{x}_1, \dots, \tilde{x}_k$ one after another, which is cheap because the draft model is small. The target model $p$ then scores all $k$ positions in a single forward pass. That pass processes $k$ tokens against one read of the target's weights, so by @eq-appdx-batched-step it costs about as much time as generating one token, as long as $k$ is well below $\pi b / 2\beta$. Scanning left to right, candidate $\tilde{x}_j$ is accepted with probability

$$\alpha_j = \min\left(1, \frac{p(\tilde{x}_j \mid \cdot)}{q(\tilde{x}_j \mid \cdot)}\right)$$ {#eq-appdx-spec-accept}

At the first rejection, the remaining drafts are discarded and one replacement token is drawn from the normalized residual distribution

$$p_{\text{res}}(v) = \frac{\max\left(0,\; p(v) - q(v)\right)}{\sum_{w \in \mathcal{V}} \max\left(0,\; p(w) - q(w)\right)}$$ {#eq-appdx-spec-residual}

Together, the acceptance test of @eq-appdx-spec-accept and the resampling rule of @eq-appdx-spec-residual make each emitted token distributed exactly as if it had been sampled from $p$ alone. Each target pass therefore emits between one and $k + 1$ tokens, and the speedup depends on how often the draft agrees with the target. The serial dependence remains. The target still verifies the drafted tokens in order, and a rejection discards everything after it, so speculative decoding reduces the constant cost per emitted token rather than removing the chain. On a heavily batched server the verification pass competes with other streams for arithmetic, which is why the technique pays most when load is light (@sec-vol3-agent-economics-speculative).

## The Size of the Attention State {#sec-vol3-appendix-inference-kv-cache}

A model generating token $t$ attends to the keys and values of every earlier token. Recomputing them at every step would make each step's work grow with the whole prefix, so the serving system keeps them, in the KV cache of @sec-vol3-foundation-model-tokenization. Its size per token follows from the model's geometry.

### Bytes per token

For a decoder with $L$ layers, $H_{\text{kv}}$ key-value heads per layer, head dimension $d_{\text{head}}$, and $b_{\text{kv}}$ bytes per stored element, each token stores one key vector and one value vector per layer and key-value head:

$$m_{\text{token}} = 2 \cdot L \cdot H_{\text{kv}} \cdot d_{\text{head}} \cdot b_{\text{kv}}$$ {#eq-appdx-kv-cache-token-size}

and a context of $T$ tokens occupies

$$M_{\text{KV}}(T) = T \cdot m_{\text{token}}$$

For the reference model, with $L$ = `{python} ServingRef.n_layers_str`, $H_{\text{kv}}$ = `{python} ServingRef.n_kv_heads_str`, $d_{\text{head}}$ = `{python} ServingRef.d_head_str`, and 16-bit storage, $m_{\text{token}}$ = `{python} ServingRef.m_token_str` bytes, so a `{python} ServingRef.s_agent_str`-token context occupies about `{python} ServingRef.kv_agent_str` GB. @Sec-vol3-kvcache-geometry turns this into the number of trajectories one node can hold.

### Attention designs

The number of key-value heads is a design choice, and it changes $m_{\text{token}}$ directly. Multi-head attention gives every query head its own keys and values. Multi-query attention shares one key-value head across all query heads [@shazeer2019fast]. Grouped-query attention sits between them, sharing each key-value head across a group of query heads [@ainslie2023gqa]. @Tbl-appdx-kv-cache-scaling applies the three designs to the reference model's other dimensions.

| Design                      |                    Key-value heads                     |        Bytes per token (16-bit)       | At `{python} ServingRef.s_agent_str` tokens |
|:----------------------------|:------------------------------------------------------:|:-------------------------------------:|:-------------------------------------------:|
| **Multi-head attention**    | `{python} ServingRef.n_heads_str` (one per query head) | `{python} ServingRef.m_token_mha_str` |  `{python} ServingRef.kv_agent_mha_str` GB  |
| **Grouped-query attention** |          `{python} ServingRef.n_kv_heads_str`          |   `{python} ServingRef.m_token_str`   |    `{python} ServingRef.kv_agent_str` GB    |
| **Multi-query attention**   |                           1                            | `{python} ServingRef.m_token_mqa_str` |  `{python} ServingRef.kv_agent_mqa_str` GB  |

: **Attention State by Attention Design**: Bytes of keys and values per token, and for one long agent context, for the reference model's layers and head dimension under three attention designs. Storing keys and values at 8 bits halves every entry. {#tbl-appdx-kv-cache-scaling tbl-colwidths="[28,24,24,24]"}

Storing keys and values at 8 bits halves every entry, to `{python} ServingRef.m_token8_str` bytes per token for the grouped design, at some risk to accuracy. Discarding entries that receive little attention bounds the footprint further but makes the state lossy, so a later step cannot recover what was dropped (@sec-vol3-kvcache-geometry).

### Occupancy during a tool wait

Serving memory is priced by how much is held and for how long. A trajectory whose attention state stays resident through a tool wait of length $t_{\text{wait}}$ occupies

$$O = M_{\text{KV}}(T) \cdot t_{\text{wait}}$$

byte-seconds while generating nothing. Because agent tool waits are often much longer than the model calls between them, this idle occupancy can exceed the occupancy of active decoding, which is what makes the retain, evict, recompute, or offload decision of @sec-vol3-kvcache-swapping worth making per wait.

### Paged storage

Allocating each trajectory a contiguous region sized for its maximum context wastes most of the region, because agent contexts grow unpredictably and end early. Paged storage divides the pool into fixed blocks of $B_s$ tokens and maps each trajectory's positions to blocks through a table, so a trajectory holds only the blocks it has filled [@kwon2023]. The only waste is the unfilled tail of each trajectory's last block, on average

$$\mathbb{E}[\text{waste}] \approx \frac{B_s - 1}{2} \cdot m_{\text{token}}$$

per trajectory, a few kilobytes to a few megabytes regardless of context length. Blocks can also be shared, which lets forked branches and trajectories with a common prefix hold one copy of it (@sec-vol3-kvcache-pagedattention).

## Queueing for Trajectories {#sec-vol3-appendix-inference-queueing}

```{python}
#| label: calc-vol3-appendix-inference-trajectory-queue
#| echo: false
# ┌─────────────────────────────────────────────────────────────────────────────
# │ LIVE TRAJECTORIES AND THE QUEUEING KNEE (LEGO)
# ├─────────────────────────────────────────────────────────────────────────────
# │ Context: @sec-vol3-appendix-inference-queueing; cited by the capacity
# │          sections of @sec-vol3-agent-economics and @sec-vol3-sandboxes.
# │
# │ Goal: Apply Little's law to a trajectory workload with tool waits, compare
# │       memory for resident versus in-call attention state, and show how
# │       queueing delay rises with utilization.
# │ Show: 720 live trajectories; 120 in a model call; about 15 nodes to hold
# │       every context resident versus about 2.4 for those in a call; waits
# │       of 1.5, 3.5, and 13.5 service times at 50, 70, and 90 percent.
# │ How:  L = lambda W; per-node pool and per-trajectory state from ServingRef;
# │       Kingman's approximation for a single queue.
# └─────────────────────────────────────────────────────────────────────────────
class TrajectoryQueue:
    # ┌── 1. LOAD (Constants & Parameters) ─────────────────────────────────
    arrival_rate = 2.0  # scenario: trajectories started per second
    turns = 15  # scenario: turns per trajectory
    t_model = 4.0  # scenario: seconds of model time per turn (prefill plus decode)
    t_tool = 20.0  # scenario: seconds of tool time per turn
    kv_gb = ServingRef.kv_agent_gb  # attention state per trajectory at the agent context length
    pool_gb = ServingRef.pool_gb  # attention-state pool per node

    # ┌── 2. EXECUTE (Compute) ─────────────────────────────────────────────
    w_traj = turns * (t_model + t_tool)
    live = arrival_rate * w_traj
    model_share = t_model / (t_model + t_tool)
    in_call = live * model_share
    resident_tb = live * kv_gb / 1e3
    nodes_resident = live * kv_gb / pool_gb
    nodes_in_call = in_call * kv_gb / pool_gb

    # ┌── 3. GUARD (Invariants) ───────────────────────────────────────────
    check(abs(live - 720) < 1e-9, "Little's law example must give 720 live trajectories")
    check(nodes_resident > 5 * nodes_in_call, "Holding state through tool waits must multiply memory demand")

    # ┌── 4. OUTPUT (Formatting) ──────────────────────────────────────────
    arrival_str = fmt_int(arrival_rate)
    turns_str = fmt_int(turns)
    t_model_str = fmt_int(t_model)
    t_tool_str = fmt_int(t_tool)
    w_traj_str = fmt_int(w_traj)
    w_traj_min_str = fmt_int(w_traj / 60)
    live_str = fmt_int(live)
    in_call_str = fmt_int(in_call)
    model_share_str = fmt_int(model_share * 100)
    resident_val_str = fmt(resident_tb, precision=1)
    nodes_resident_str = fmt_int(round(nodes_resident))
    nodes_in_call_str = fmt(nodes_in_call, precision=1)

class QueueKnee:
    # ┌── 1. LOAD (Constants & Parameters) ─────────────────────────────────
    ca2 = 2.0  # scenario: bursty call arrivals
    cs2 = 1.0  # scenario: service times as variable as an exponential
    rho50, rho70, rho90 = 0.5, 0.7, 0.9  # utilizations to compare

    # ┌── 2. EXECUTE (Compute) ─────────────────────────────────────────────
    var = (ca2 + cs2) / 2
    w50 = var * rho50 / (1 - rho50)
    w70 = var * rho70 / (1 - rho70)
    w90 = var * rho90 / (1 - rho90)

    # ┌── 3. GUARD (Invariants) ───────────────────────────────────────────
    check(w90 > 3 * w70, "Wait must rise steeply between 70 and 90 percent utilization")

    # ┌── 4. OUTPUT (Formatting) ──────────────────────────────────────────
    ca2_str = fmt_int(ca2)
    cs2_str = fmt_int(cs2)
    var_str = fmt(var, precision=1)
    rho50_str = fmt_int(rho50 * 100)
    rho70_str = fmt_int(rho70 * 100)
    rho90_str = fmt_int(rho90 * 100)
    w50_str = fmt(w50, precision=1)
    w70_str = fmt(w70, precision=1)
    w90_str = fmt(w90, precision=1)
```

Capacity for agents is set by how long trajectories live, not by how long calls take, and every resource a trajectory holds for its lifetime must be sized from that lifetime.

### Continuous batching

A server batches decode steps from many trajectories (@eq-appdx-batched-step), and how it forms those batches decides how long a call waits. A static batch holds every request until the longest one finishes, so a short tool call waits behind a long plan. Continuous batching schedules at the granularity of one decode step [@yu2022orca]. A request whose output ends, whether at a stop token or a tool call, leaves the batch at the next step, and a waiting request, such as a trajectory returning from a tool with a new observation, joins at the next step. A call therefore waits for a free slot rather than for a batch to drain, and the server behaves like a queue with as many servers as it has batch slots. The rest of this section treats it that way.

### Little's law with tool waits

For any stable system, the mean number of items inside it equals their arrival rate times their mean time inside [@little1961]:

$$L = \lambda \cdot W$$ {#eq-appdx-littles-law}

A trajectory of $H$ turns spends each turn in a model call and then in a tool, so its time in the system is

$$W_{\text{traj}} = \sum_{k=1}^{H} \left( T_{\text{model}}^{(k)} + T_{\text{tool}}^{(k)} \right)$$

the duration accounting of @sec-vol3-intro-duration-accounting without the approval and runtime terms. As a worked case, let trajectories start at `{python} TrajectoryQueue.arrival_str` per second, each running `{python} TrajectoryQueue.turns_str` turns of `{python} TrajectoryQueue.t_model_str` s of model time and `{python} TrajectoryQueue.t_tool_str` s of tool time. Each lives `{python} TrajectoryQueue.w_traj_str` s, about `{python} TrajectoryQueue.w_traj_min_str` minutes, so @eq-appdx-littles-law gives `{python} TrajectoryQueue.live_str` live trajectories. Only `{python} TrajectoryQueue.model_share_str` percent of each trajectory's time is spent in a model call, so on average `{python} TrajectoryQueue.in_call_str` of them are calling the model at any moment.

The gap between those two numbers is the cost of holding state through tool waits. If every live trajectory keeps a `{python} ServingRef.s_agent_str`-token context resident, the attention state totals about `{python} TrajectoryQueue.resident_val_str` TB, about `{python} TrajectoryQueue.nodes_resident_str` nodes' worth of the reference pool of @sec-vol3-appendix-inference-assumptions. If only the trajectories in a model call hold it, the same work needs about `{python} TrajectoryQueue.nodes_in_call_str` nodes' worth, at the price of re-prefilling or reloading each context when its trajectory returns. That trade is the retain, evict, recompute, or offload decision of @sec-vol3-kvcache-swapping, and the same product of rate and lifetime sizes harness workers, sandbox leases, and rate-limit headroom (@sec-vol3-agent-economics-capacity, @sec-vol3-sandboxes-pooling).

### The queueing knee

A shared server, whether a model endpoint, a sandbox pool, or a verifier, makes callers wait more as it gets busier, and the wait rises steeply before the server is saturated. For a single queue with utilization $\rho$, mean service time $\mathbb{E}[S]$, and squared coefficients of variation $c_a^2$ for the time between arrivals and $c_s^2$ for service times, Kingman's approximation gives the mean wait:

$$W_q \approx \frac{c_a^2 + c_s^2}{2} \cdot \frac{\rho}{1 - \rho} \cdot \mathbb{E}[S]$$

The first factor is the workload's variability and the second its load. With bursty arrivals ($c_a^2$ = `{python} QueueKnee.ca2_str`) and exponential-like service times ($c_s^2$ = `{python} QueueKnee.cs2_str`), the variability factor is `{python} QueueKnee.var_str`, and the mean wait is about `{python} QueueKnee.w50_str`, `{python} QueueKnee.w70_str`, and `{python} QueueKnee.w90_str` service times at `{python} QueueKnee.rho50_str`, `{python} QueueKnee.rho70_str`, and `{python} QueueKnee.rho90_str` percent utilization. Agent workloads are variable on both counts, since trajectories fan out calls in bursts and generation lengths vary by orders of magnitude, so shared agent infrastructure is run well below saturation. For $c$ identical servers, the Allen-Cunneen approximation replaces $\rho/(1-\rho)$ with the probability that all servers are busy, from the Erlang C formula [@erlang1909telephone], divided by $c(1-\rho)$. Pooling many servers shortens the wait at a given utilization, but the knee remains. When service times are heavy-tailed, a few long trajectories dominate the wait, which is why schedulers separate them from short ones (@sec-vol3-appendix-math-queueing).

### How many trajectories fit

For a server with memory $M_{\text{HBM}}$, weights of $N b$ bytes, and a runtime reserve $M_{\text{runtime}}$, the memory left for attention state is

$$M_{\text{dynamic}} = M_{\text{HBM}} - N b - M_{\text{runtime}}$$ {#eq-appdx-mdynamic}

and the number of trajectories of average context $\bar{T}$ that can stay resident at once is

$$B_{\max} = \left\lfloor \frac{M_{\text{dynamic}}}{\bar{T} \cdot m_{\text{token}}} \right\rfloor$$ {#eq-appdx-max-batch}

For the reference node, @eq-appdx-mdynamic leaves `{python} ServingRef.pool_str` GB and @eq-appdx-max-batch admits `{python} ServingRef.conc_agent_str` trajectories at `{python} ServingRef.s_agent_str` tokens, the same count @sec-vol3-kvcache-geometry derives. Beyond $B_{\max}$ the server must move a waiting trajectory's state out. Recomputing it costs a prefill of its $T$ tokens, about $2NT/\pi$ seconds by @eq-appdx-prefill-time (more at long lengths, by @eq-appdx-prefill-long), and reloading it costs $T \cdot m_{\text{token}} / \beta_{\text{link}}$ over the link to wherever it was offloaded, so

$$\text{recompute when} \quad \frac{2 N}{\pi} < \frac{m_{\text{token}}}{\beta_{\text{link}}}$$

per token of context. The comparison does not depend on the context length to first order, which is why the break-even is usually set by the link and the model rather than by the trajectory. @Sec-vol3-kvcache-swapping adds the length of the wait, which decides whether either is worth doing.

## Classical Transaction Background {#sec-vol3-appendix-inference-distributed}

Databases solved a version of the agent's recovery problem long ago, and @sec-vol3-durable-execution and @sec-vol3-failure-recovery borrow from that solution while explaining why it does not transfer whole. This section summarizes the classical mechanisms for readers who have not met them.

### Transactions and two-phase commit

A database transaction makes a group of writes atomic. Either all commit or the engine aborts and undoes them all, using undo logs and locks so that no other client sees the intermediate state [@gray1981transaction]. Two-phase commit extends atomicity across several databases. A coordinator asks every participant to prepare, which means acquiring its locks and promising it can commit, and commits everywhere only if every participant agreed. Both rest on two assumptions. Every participant can hold a change in a prepared, invisible state, and locks can be held for as long as the transaction lasts.

Neither assumption holds for an agent's tools. A code forge, a cloud control plane, a payment service, or a mail server exposes no prepare phase and commits each request the moment it arrives, where other people and programs can see and act on it. And a trajectory lasts seconds per model call, minutes per test run, and hours for an approval, so locks held for its lifetime would block every other user of those resources. @Sec-vol3-sagas-acid-boundary develops the consequence for recovery.

### Sagas

A saga replaces one long transaction with a sequence of short ones, each committed immediately, and pairs each step $T_i$ with a compensating step $C_i$ that semantically undoes it [@garciamolina1987sagas]. If step $T_k$ fails, the saga runs $C_{k-1}, \dots, C_1$ in reverse order. Compensation restores the invariants the application cares about, not the exact prior state, and a step with no compensator, such as sending an email, is a pivot after which the saga can only complete forward. @Sec-vol3-sagas-architecture builds the trajectory saga on this pattern, and @sec-vol3-sagas-pivot places the pivot.

### Write-ahead logging

A database recovers its own pages after a crash with a write-ahead log. Every change is recorded durably before the page it changes is written, and each record carries a log sequence number and a pointer to the previous record of the same transaction. The ARIES algorithm [@mohan1992aries] recovers in three passes. It scans the log to find what was in progress, repeats history to restore every logged change, and undoes the changes of transactions that did not commit by restoring the prior values the log recorded.

An agent keeps the first half of this discipline and drops the second. Its runtime records the intent to act before the action leaves the host, so after a crash every effect is either known to have been intended or known not to have happened (@sec-vol3-persistence-wal). But its effects land in systems the log does not own, so the log can record an effect and never undo it by restoring a value. Undo becomes compensation, which is the saga's job, not the log's.

## Reference Values {#sec-vol3-appendix-inference-assumptions}

The estimates in this appendix, and the serving estimates in the chapters, use one reference model on one reference accelerator, whose values @tbl-appdx-hardware-constants collects. The chapters describe them only as a 70-billion-parameter model on a current data center accelerator, because the argument does not depend on the particular product. The values come from the MLSysIM registry. To redo an estimate for different hardware or a different model, substitute its values into the equations above; the ratio of @eq-appdx-decode-prefill-ratio and the byte counts of @eq-appdx-kv-cache-token-size are the two results most chapters depend on.

| Quantity                          | Symbol                  | Reference value                                                                                  | Used in                                 |
|:----------------------------------|:------------------------|:-------------------------------------------------------------------------------------------------|:----------------------------------------|
| **Parameters**                    | $N$                     | `{python} ServingRef.params_b_str` billion                                                       | Per-token floors, weights in memory     |
| **Layers**                        | $L$                     | `{python} ServingRef.n_layers_str`                                                               | Attention state, long-context prefill   |
| **Model width**                   | $d$                     | `{python} ServingRef.d_model_str`                                                                | Long-context prefill                    |
| **Query heads / key-value heads** | $H_q$ / $H_{\text{kv}}$ | `{python} ServingRef.n_heads_str` / `{python} ServingRef.n_kv_heads_str`                         | Attention state by design               |
| **Head dimension**                | $d_{\text{head}}$       | `{python} ServingRef.d_head_str`                                                                 | Attention state                         |
| **Weight precision**              | $b$                     | 1 byte (8-bit)                                                                                   | Decode floor, ridge-to-ratio conversion |
| **Key-value precision**           | $b_{\text{kv}}$         | 2 bytes (16-bit)                                                                                 | Attention state                         |
| **Accelerator memory bandwidth**  | $\beta$                 | `{python} ServingRef.bw_str` TB/s                                                                | Decode floor, ridge point               |
| **Accelerator peak rate, 8-bit**  | $\pi$                   | `{python} ServingRef.peak_str` trillion operations per second                                    | Prefill floor, ridge point              |
| **Accelerator memory**            | $M_{\text{HBM}}$        | `{python} ServingRef.acc_hbm_str`                                                                | Resident trajectories                   |
| **Accelerators per node**         | $n_{\text{acc}}$        | `{python} ServingRef.n_acc_str`                                                                  | Node memory pool                        |
| **Ridge point**                   | $\mathcal{I}^*$         | `{python} ServingRef.ridge_str` operations per byte                                              | Where passes turn arithmetic-bound      |
| **Decode floor per output token** | $t_{\text{decode}}$     | `{python} ServingRef.t_dec_val_str` ms                                                           | Call latency                            |
| **Prefill time per prompt token** | $t_{\text{prefill}}$    | `{python} ServingRef.t_pre_val_str` µs                                                           | Call latency, re-send cost              |
| **Attention state per token**     | $m_{\text{token}}$      | `{python} ServingRef.m_token_str` bytes                                                          | Memory per trajectory                   |
| **Attention-state pool per node** | $M_{\text{dynamic}}$    | `{python} ServingRef.pool_str` GB (16-bit weights, `{python} ServingRef.reserve_str` GB reserve) | Trajectories per node                   |

: **Reference Serving Values**: The model, accelerator, and node values behind the book's serving estimates, and the derived quantities the chapters use. All come from the MLSysIM registry; the derived rows follow from the equations of this appendix. {#tbl-appdx-hardware-constants tbl-colwidths="[30,14,32,24]"}