Core Engine¶

This page describes BLIS's single-instance discrete event simulation engine. For multi-instance cluster orchestration, see Cluster Architecture.

Canonical sources: System invariants (INV-1 through INV-19, plus INV-A, INV-A2, INV-W3, the LoRA family INV-L1-INV-L6, PD disaggregation INV-PD-* and pool/transfer INV-P2-*) are defined in docs/contributing/standards/invariants.md. If invariant descriptions here diverge, invariants.md is authoritative.

Overview¶

Each BLIS instance is a self-contained discrete event simulator. The engine maintains an event queue (min-heap), processes events in timestamp order, and advances a simulation clock. The core loop is:

while events remain and clock < horizon:
    event = pop earliest event from queue
    advance clock to event.timestamp
    execute event (may produce new events)

The engine models the full vLLM inference pipeline: request arrival, queueing, batch formation, step execution, KV cache management, and latency estimation — all without real GPU hardware.

Event Queue¶

The event queue is a min-heap ordered by event timestamp. Events represent state transitions in the simulation:

Event Type	Trigger	Effect
`ArrivalEvent`	Request enters system	Computes queueing delay (host overhead priced by the kernel), schedules `QueuedEvent`
`QueuedEvent`	Request enters wait queue	Adds request to wait queue; if no `StepEvent` exists, schedules one (work-conserving)
`StepEvent`	Batch ready for execution	Runs the 4-phase Step() cycle (see below)
`ScheduledEvent`	Request moves to running batch	Timeline marker for tracing (scheduling delay recorded in `scheduleBatch`)
`RequestLeftEvent`	Request completes	Timeline marker for tracing (E2E metrics recorded in `processCompletions`)

Clock monotonicity (INV-3): The simulation clock never decreases. Each processed event has a timestamp >= its predecessor's — except when restoring an optimistic advance after a lazily-cancelled event, where no event was processed. See invariants.md for the carve-out.

Work-conserving (INV-8): After every step completion, if the wait queue is non-empty, a StepEvent must exist in the event queue. The simulator never idles while work is waiting.

flowchart TD
    EQ["Event Queue (min-heap)<br/>Ordered by timestamp"] -->|Pop min| Clock["Advance clock<br/>to event.timestamp"]
    Clock --> Exec["Execute Event Handler<br/>Arrival → Queued → WaitQ<br/>Step → Step() phases<br/>Completion → metrics"]
    Exec -->|produces new events| EQ
    Exec -->|clock ≥ horizon<br/>or queue empty| Done["Simulation<br/>Complete"]

    style EQ fill:#fff9db
    style Clock fill:#a5d8ff
    style Exec fill:#b2f2bb
    style Done fill:#c8e6c9

Step Phases¶

The Step() function is a 4-line orchestrator that delegates to four phases:

flowchart TD
    P1["1. scheduleBatch<br/>Priority assignment<br/>Queue reordering<br/>Batch formation"]
    P2["2. executeBatchStep<br/>Latency estimation<br/>Prefill/decode progress<br/>TTFT at boundary"]
    P3["3. processCompletions<br/>Release KV blocks<br/>Record E2E metrics<br/>Schedule RequestLeft"]
    P4["4. scheduleNextStep<br/>Batch has work → Step<br/>Queue has work → Step<br/>Both empty → idle"]

    P1 --> P2 --> P3 --> P4

    style P1 fill:#d0bfff
    style P2 fill:#d0bfff
    style P3 fill:#d0bfff
    style P4 fill:#d0bfff

Phase 1: Schedule Batch (`scheduleBatch`)¶

Reorder the wait queue via the scheduling policy (e.g., FCFS, SJF, priority-FCFS). Request priorities are static — set once at enqueue via SLOPriorityMap.InvertForVLLM(SLOClass), not recomputed per step.
(step loop reordering — see above)
Invoke batch formation to select which requests enter the running batch
Record preemption metrics for any evicted requests
Schedule ScheduledEvent for any newly admitted requests

Phase 2: Execute Batch Step (`executeBatchStep`)¶

Compute step time via the latency model based on batch composition
For each request in the batch:
If in prefill phase: advance the progress index through input tokens (respecting chunked prefill limits)
If in decode phase: advance the progress index by one output token
Record TTFT at the prefill-to-decode boundary
Return the computed step time to Phase 4 for scheduling the next StepEvent (the clock itself advances only at the event-loop level when the next event is popped)

Phase 3: Process Completions (`processCompletions`)¶

Identify completed requests (all output tokens generated), release their KV blocks, record E2E metrics, and schedule RequestLeftEvent. Note: TTFT is already recorded in Phase 2 at the prefill-to-decode boundary, so Phase 3 only handles E2E and completion bookkeeping. This separation (TTFT in Phase 2, E2E in Phase 3) is the "two-pass" design that ensures TTFT is recorded before E2E.

Phase 4: Schedule Next Step (`scheduleNextStep`)¶

If the running batch still has requests, schedule the next StepEvent at now + stepTime
If the running batch is empty but the wait queue has requests, schedule the next StepEvent at now + stepTime (work-conserving)
If both are empty, do nothing (next event will be a future arrival)

Request Lifecycle¶

Requests follow a linear state machine with one exception (preemption):

stateDiagram-v2
    [*] --> Arrival
    Arrival --> Queued : host queueing delay
    Arrival --> DroppedUnservable : exceeds MaxModelLen or KV capacity

    state "Queued" as Queued
    note right of Queued
        EnqueueTime recorded
        Scheduler orders queue
    end note

    Queued --> Running : BatchFormation selects

    state "Running" as Running
    note right of Running
        ScheduleTime recorded
        TTFT at prefill→decode boundary
        KV blocks allocated
        ITL recorded per decode step
    end note

    Running --> Completed
    Running --> Queued : Preemption (KV eviction, re-enqueue front)

    state "Completed" as Completed
    note right of Completed
        CompletionTime recorded
        KV blocks released
        E2E = CompletionTime − ArrivalTime
    end note

    Completed --> RequestLeft
    RequestLeft --> [*]
    DroppedUnservable --> [*]

INV-5 (Causality): ArrivalTime ≤ EnqueueTime ≤ ScheduleTime ≤ CompletionTime

States¶

State	Description
Queued	In wait queue, not yet in running batch. Ordered by scheduling policy.
Running	In running batch, actively being processed. Progressing through prefill or decode.
Completed	All output tokens generated. KV blocks released. Metrics recorded.

Key Timestamps¶

These are the conceptual timestamps in a request's lifecycle. Some are stored as struct fields (e.g., ArrivalTime, FirstTokenTime), while others are computed at metric recording time.

Timestamp	When Recorded	Used For
Arrival time	Request creation	E2E and scheduling delay baseline
Enqueue time	After host queueing delay	Conceptual start of wait queue residence
Schedule time	Batch formation selects request	Scheduling delay = time in wait queue
First token time	End of prefill phase	TTFT = FirstTokenTime (stored on Request)
Completion time	All tokens generated	E2E = FirstTokenTime + sum(ITLs)

Causality invariant (INV-5): arrival_time <= enqueue_time <= schedule_time <= completion_time

Preemption¶

When KV cache pressure forces eviction, running requests are preempted: 1. Request is removed from the running batch. By default (--preemption-policy fcfs), the tail of the batch is evicted. With --preemption-policy priority, the running request with the lowest SLO tier priority is evicted first (background before sheddable before batch before standard before critical); among equal-priority requests, the most recently arrived is evicted. 2. Its KV blocks are freed 3. It is re-enqueued at the front of the wait queue (not the back) 4. A debug log is emitted and PreemptionCount is incremented

Preempted requests reset to the beginning of prefill (ProgressIndex = 0) and their KV blocks are freed. However, the freed blocks' prefix hashes are preserved in the KV cache's free list — when the request is re-scheduled, prefix caching may find these blocks (if not yet evicted by LRU), reducing recomputation. This matches vLLM's "recompute" preemption mode.

Dropped Requests¶

Requests are dropped as unservable at enqueue time (incrementing DroppedUnservable) via two guards:

MaxModelLen guard — requests whose total sequence length exceeds the context window are rejected. When the request declares an output budget (MaxOutputLen > 0), the check is input + budget > maxModelLen. Otherwise, input length alone is checked (vLLM defaults max_tokens to max_model_len - seq_len; the runtime stop in processCompletions handles output growth).
KV capacity guard — requests whose input tokens require more KV blocks than the total cache capacity are rejected. This prevents livelock where the simulator would endlessly preempt and re-enqueue a request that can never fit.

Both guards fire before the request enters the wait queue, mirroring vLLM's pre-engine rejection. Additionally, a proactive cap in FormBatch clamps token scheduling to maxModelLen - 1 - ProgressIndex (matching vLLM scheduler.py:773-774), a decode guard in executeBatchStep prevents phantom token generation when 0 tokens are allocated, and processCompletions force-completes any request whose ProgressIndex reaches MaxModelLen - 1. Output tokens per length-capped request: MaxModelLen - len(InputTokens), matching vLLM's check_stop (num_tokens >= max_model_len). ProgressIndex is BLIS's num_computed_tokens, which lags the generated-token count by one — BLIS charges the first output token to prefill completion, as vLLM's num_computed_tokens lags num_tokens by the token the forward pass has just appended — so the MaxModelLen - 1 boundary is reached with the final token already generated, and it is counted.

Batch Formation¶

BLIS models vLLM's continuous batching algorithm through the VLLMBatchFormation implementation.

Two-Phase Algorithm¶

Phase 1: Continuing Requests Process requests already in the running batch: - Apply chunked prefill limits (--long-prefill-token-threshold) - Allocate token budget for decode tokens - If KV allocation fails for a continuing request, preempt requests from the batch tail to free blocks

Phase 2: New Requests Dequeue requests from the wait queue: - Compute cached prefix blocks (prefix caching reduces allocation needs) - Allocate KV blocks for uncached prefix tokens being processed this step (bounded by chunked prefill threshold and remaining token budget) - Stop dequeuing when: max batch size reached (max_num_seqs), allocation fails (cache full), token budget exhausted, or a preemption occurred during Phase 1

Constraints¶

Constraint	Source	Effect
Max batch size	scenario `max_num_seqs`	Limits number of concurrent requests in the running batch
Token budget	scenario `max_num_batched_tokens`	Limits total new tokens across all running requests per step
Chunked prefill	`--long-prefill-token-threshold`	Splits long prefills across multiple steps

Preemption Strategy¶

When KV allocation fails for a continuing request: 1. Select a victim: by default (--preemption-policy fcfs), evict from the batch tail (reverse order of admission). With --preemption-policy priority, evict the running request with the lowest SLO tier priority (background before sheddable before batch before standard before critical); among equal-priority requests, the most recently arrived is evicted first. This matches vLLM's --scheduling-policy priority preemption behavior. 2. Free the victim's KV blocks 3. Re-enqueue evicted requests at the front of the wait queue 4. Retry allocation for the original request 5. Circuit breaker: Stop if allocation still fails after exhausting the batch, or if the request itself is unservable

KV Cache Management¶

The KV cache simulates GPU memory organized as fixed-size blocks. Each block holds the scenario's block_size tokens; the block budget comes from blis-latency-kernel's memory methods, per data-parallel rank.

Single-Tier Cache¶

The default KV cache operates entirely in GPU memory:

Block allocation: Requests are allocated blocks proportional to their token count
Prefix caching: Hierarchical block hashing enables prefix sharing across requests. Each block's hash chains with the prior block's hash, creating semantic prefix signatures. When a new request shares a prefix with an existing request, the cached blocks are reused rather than reallocated.
LRU eviction: Free blocks are managed via a doubly-linked list with LRU ordering
Reference counting: Shared blocks (prefix caching) are reference-counted and exempt from eviction while any request references them
Transactional allocation: Multi-block allocations are rolled back on failure (no partial allocation)

Conservation invariant (INV-4): allocated_blocks + free_blocks = total_blocks at all times.

Tiered Cache (GPU + CPU)¶

When --kv-cpu-blocks is set to a positive value, BLIS enables a two-tier cache:

GPU tier: Full KV cache with prefix caching and LRU eviction
CPU tier: Simple capacity store for offloaded blocks
Offload trigger: When GPU utilization exceeds --kv-offload-threshold (default: 0.9), blocks are offloaded to CPU
Reload: On GPU allocation failure, blocks are reloaded from CPU with a transfer latency penalty
Transfer latency: each reloaded block is charged a per-block reload time that blis-latency-kernel prices from the catalog cpu_dram device. Accumulated across all reloaded blocks; non-blocking (added to step time). See Tiered Caching.
Thrashing detection: Blocks offloaded and reloaded within 1000 ticks (1ms) increment a thrashing counter

Latency Models¶

Step time and host overheads come from blis-latency-kernel, through the sim.LatencyModel interface (adapter: sim/kernelmodel). The simulator decides when a step runs and which requests it holds; the kernel prices that batch from the model graph, chip and coefficients the scenario names. See the Latency Models guide.

Host overheads are charged around the GPU step, never on it:

Queueing time (tokenization, preprocessing) delays request enqueue but does not block the server; the simulation clock is not advanced by it.
Output token processing time (detokenization, streaming) is added to per-request ITL/TTFT metrics but does not block the next step.
Post-decode fixed overhead is charged once per request at completion.

This matches vLLM, where CPU post-processing runs concurrently with GPU execution.

Scheduling Policies¶

Scheduling policies control the order in which queued requests are selected for batch formation. They operate per-instance. To add a new scheduling policy, see Extension Recipes.

Policy	Ordering Rule	Use Case
`fcfs`	No reordering (arrival order)	Default, fair
`priority-fcfs`	Priority ascending (lower value = more urgent, vLLM convention), then arrival ascending	SLO-aware scheduling with `slo_class` in workload spec
`sjf`	Input token count ascending, then arrival ascending	Shortest-job-first for TTFT optimization
`reverse-priority`	Priority descending (highest value = least urgent scheduled first)	Pathological testing only

Request priorities are static — set once at enqueue via SLOPriorityMap.InvertForVLLM(SLOClass) (vLLM convention: lower integer = more urgent). Default mapping: critical=0, standard=1, batch=5, sheddable=6, background=7. No per-step recomputation.

Metrics¶

BLIS records per-request and aggregate metrics throughout the simulation.

Per-Request Metrics¶

Metric	Definition
TTFT	Time from arrival to first token: includes queueing delay, prefill step times, and per-token output processing overhead
E2E	`FirstTokenTime + sum(ITLs)`, where each ITL includes step time + per-token output processing
ITL	Observed time between consecutive decode steps (includes per-token output processing)
Scheduling Delay	Time from request arrival to entering the running batch (includes host queueing overhead + wait queue residence)

Aggregate Metrics¶

Metric	Aggregation
TTFT, E2E, ITL distributions	Mean, p90, p95, p99 in JSON output. Cluster-internal `Distribution` type also computes p50, min, max for fitness evaluation.
Throughput	Output tokens per second, requests per second
Preemption count	Total KV cache evictions
KV allocation failures	Failed block allocations
Dropped unservable	Requests too large for cache

Conservation Invariant (INV-1)¶

At simulation end, for a single-instance run: injected_requests == completed_requests + still_queued + still_running + dropped_unservable + timed_out

That five-term form is the single-instance specialisation, not the general rule. The canonical form is an eleven-term cluster equation: a cluster run adds six buckets for the embedded llm-d router's outcomes — routing rejections, flow-control queue depth and capacity rejections, in-flight eviction, TTL expiry, and encode-pool routing. Asserting the five-term form against cluster output is incomplete — see canonical INV-1 for the full equation and the shared helpers that implement it.

This is the fundamental accounting invariant that ensures no requests are silently lost.

Determinism¶

BLIS guarantees deterministic output: the same seed produces byte-identical stdout across runs (INV-6).

Key mechanisms: - Partitioned RNG: Each subsystem (workload generation, scheduling, etc.) uses an independent random stream derived from the seed, so adding randomness to one subsystem doesn't perturb others - Sorted map iteration: Where map iteration order affects output, keys are sorted first - Stdout/stderr separation: Deterministic results go to stdout; wall-clock timing and diagnostics go to stderr via logrus