docs/methodology.md

# Methodology and limitations

## What is simulated

InferScale models request arrival, queueing, admission, prefill, autoregressive decode, dynamic batch membership, KV-cache memory, and request completion.

For P/D disaggregation it additionally models independent prefill/decode worker pools and explicit prompt-KV transfer before decode admission. Metrics are computed from per-request virtual timestamps.

## Scheduler semantics

- `static_fcfs`: admits one colocated batch and drains it before admitting new requests.
- `continuous_fcfs`: admits FCFS work whenever decode slots become available.
- `continuous_sjf`: prioritizes shorter estimated jobs at admission.
- `continuous_slo`: uses least-slack-style ordering from the E2E deadline and an analytical remaining-service estimate.
- `chunked_slo`: combines least-slack ordering with chunked prompt prefill.

These are transparent approximations, not line-by-line reproductions of vLLM or SGLang. Static batching is excluded from P/D comparisons; a requested static P/D run is converted to continuous semantics with an explicit warning.

## Workload semantics

Poisson arrivals use exponentially distributed inter-arrival times. Constant arrivals are evenly spaced. Bursty arrivals alternate lower and higher rate periods. Prompt/output lengths use log-normal distributions parameterized by mean and coefficient of variation.

All generated arrival modes are **open-loop**: arrival scheduling does not wait for prior responses to finish. This preserves queueing delay under overload instead of allowing client backpressure to hide tail latency.

Exact trace replay accepts rows with:

```text
arrival_time, prompt_tokens, output_tokens
```

and preserves those values directly. Capacity search is intentionally disabled for exact traces because changing `request_rate_rps` would not change a fixed arrival sequence.

## Shared-prefix model

The simulator models one reusable exact prefix:

1. cache hits use a separate seeded RNG so enabling cache does not alter the arrival/prompt/output trace;
2. a hit reduces prefill work by the reusable-prefix length, bounded by prompt length;
3. shared prefix KV consumes one persistent allocation per serving worker instead of being duplicated per request;
4. decode still uses the full logical context for attention-cost estimation.

This isolates exact prefix reuse without implementing radix-tree lookup, eviction, or cache-aware routing.

## P/D disaggregation

P/D uses a global event queue with four main event classes:

```text
arrival
prefill_done
transfer_done
decode_done
```

Prefill workers batch queued requests independently. Completed prompt state enters a serialized transfer link. Decode workers admit transferred requests only between decode iterations, preserving continuous-batching semantics.

The transfer model is:

```text
(base_latency + bytes / bandwidth) x transfer_scale
```

where transferred bytes correspond to newly computed prompt KV. With a cache hit, shared-prefix state is assumed resident in both role pools and only the uncached suffix is transferred.

The model does not claim protocol-level fidelity to PCIe, NVLink, RDMA, NIXL, NCCL, or any particular production transport.

## Latency model

The default reference model is roofline-inspired:

- dense transformer FLOPs scale with parameter count and processed tokens;
- attention adds context-length-dependent work;
- decode includes weight traffic and context-dependent KV reads;
- time is approximated from compute/memory costs plus a launch/scheduling proxy;
- conservative efficiency factors prevent peak hardware specifications from being treated as achieved throughput.

Prefill and decode expose multiplicative sensitivity scales. These default to 1.0 and are used only by research stress tests unless explicitly supplied.

This creates useful qualitative dynamics but is **not empirically calibrated**.

## KV cache

KV bytes per token are approximated as:

```text
2 x layers x KV heads x head dimension x 2 bytes
```

for K and V with FP16 KV state. Paged allocation rounds live sequence lengths to `kv_block_tokens`. Static batching reserves full prompt+requested-output capacity.

## Capacity search

Each offered rate is evaluated over deterministic seed offsets and is feasible only when **every repetition**:

1. reaches the configured SLO-attainment target; and
2. fully drains all generated requests.

The result retains mean, worst, best, and standard-deviation evidence. A bounded binary search estimates the highest feasible rate and a recommended load after user-selected headroom.

## Design-space explorer

The browser-safe sweep evaluates:

- three colocated continuous schedulers over batch sizes 8/16/32;
- one cached SLO-aware colocated point at the current batch size;
- optionally P/D worker splits 1P:1D, 1P:2D, and 2P:1D, each with cache off/on.

A candidate is performance-Pareto-optimal when no other candidate has both at least as much goodput and no worse p95 TTFT, with at least one strict improvement. An independent efficiency frontier replaces raw goodput with goodput per accelerator.

This is a bounded interactive design study, not exhaustive global optimization.

## Paired A/B studies

A paired study compares one controlled system change repeatedly. Baseline and treatment receive the same seed on every repetition. This is the common-random-numbers variance-reduction idea: both alternatives see the same sampled workload, so the paired delta is less contaminated by workload randomness.

For each metric InferScale reports:

- baseline and treatment means;
- mean and median paired delta;
- treatment win rate;
- mean relative change;
- 95% percentile-bootstrap interval over paired deltas.

The bootstrap interval is an uncertainty summary for the simulated repeated experiment. It is not evidence that the analytical hardware profile itself is empirically correct.

## Analytical-model sensitivity

The robustness study draws shared multiplicative prefill/decode/transfer scales inside a user-defined band and applies each draw to both alternatives. It reports how often the treatment wins TTFT/goodput/E2E and how often each alternative satisfies the SLO.

The perturbation distribution is deliberately described as a **sensitivity analysis**, not a calibrated posterior over real hardware. Its purpose is to identify conclusions that reverse under modest model error.


## Stateful agent sessions

Agent mode is a separate program-level discrete-event model. Session arrivals are open-loop. Each session receives a deterministic number of turns, token increments, outputs, and tool gaps from a seeded trace. A later turn cannot become ready until the prior turn completes and its tool gap elapses.

Each simulated replica is a serial analytical service station in this mode. This is deliberate: dynamic batching remains covered by Serving Lab, while Agent Sessions isolates four stateful effects:

1. **cross-turn reuse:** a resident KV entry means the next turn prefills only appended tokens;
2. **tool-gap residency:** retained KV occupies memory while the program waits outside the model;
3. **routing locality:** session-affinity can preserve reuse but may trade against load balance;
4. **eviction:** TTL expiry and LRU-style memory-pressure eviction can force full-history recomputation.

The cache working set is tracked independently on each replica. The simulator integrates occupancy over virtual time and reports `HBM GB-seconds`, peak KV, mean KV, cache-hit rate, recomputed history tokens, routing-locality rate, and eviction counts.

The TTL sweep replays one identical agent-program trace for every TTL and reports the non-dominated frontier minimizing both p95 turn TTFT and mean KV residency. It is a controlled what-if study, not an optimizer over a measured production system.

## Empirical validation

`validation.py` accepts externally measured cases and compares them against simulator predictions. Supported observations include p95 TTFT, p95 E2E, goodput, request throughput, and SLO attainment. The report contains per-case residuals, MAPE, median APE, and maximum APE.

No measured benchmark values are bundled as truth with the project.

## Stateful host-tier KV model

Agent-session experiments can move idle cross-turn KV from the modeled HBM tier to a host-memory tier. Transfer time is represented as:

```text
transfer_time = base_latency + KV_size / host_bandwidth
```

Offload begins when an LLM turn completes and can overlap the simulated tool gap. If the next turn becomes ready before offload completion, the remaining offload time is exposed before restore. Restore is serialized with the turn service model in this reference implementation. Host capacity is finite and uses LRU-style pressure eviction.

This is a deliberately transparent what-if model, not a PCIe/NVLink/NIXL/DMA simulator. Its purpose is to compare three costs under the same program trace:

- recompute history after eviction;
- retain KV in scarce HBM during tool gaps;
- offload KV and pay data movement on reuse.

## Bounded-affinity routing

Strict session affinity always routes a turn to the replica that already holds its HBM KV. Least-load routing ignores locality. Bounded affinity interpolates between them:

1. find the least-loaded replica;
2. find the replica holding the session KV, if any;
3. estimate the extra queue/busy-horizon penalty of following locality;
4. keep affinity only if that penalty is at most `affinity_slack_ms`.

The estimator is intentionally simple and labeled as such. The Affinity Frontier sweeps the slack on one common program trace to show where additional locality stops being worth the load imbalance.

## Finite-HBM budget stress

The memory-budget experiment first runs a full-retention reference trace and records the unconstrained peak per-replica KV working set. It then expresses stress budgets as multiples of that trace-specific peak rather than arbitrary fractions of total accelerator VRAM. This makes the experiment meaningful even for small models whose default VRAM headroom would otherwise be far larger than the generated KV working set.

Failed turns and incomplete sessions count against SLO attainment; latency percentiles remain conditional on turns/sessions that actually complete and are accompanied by failure counts in the experiment table.