Prefill/decode disaggregation over NIXL

examples/pd-disaggregation/llmd_nixl_pull.sq models routing, prefill, KV transfer and decode on separate instances. Its key coupling is a lease: finished prefill blocks remain allocated until the decoder can receive them. Decoder memory pressure can therefore retain memory on the prefiller.

The source correspondence uses llm-d 8a2f37d, its inference scheduler 13eebdb, and vLLM 0c87a197 (ref/vllm). This is a reduced simulation model, without a two-scheduler differential oracle or hardware validation.

The figure is labelled in the words the program is written in (Engines on devices): pool D.reqs on D is the engine's running slots, pool D.kv on D's device its memory, admitted by D among its options, and tokens cap the tokens of one iteration.

The router picks a prefill instance and a decode instance, each a box with its engine, its NIC and its pools. The read crosses between them: it holds the prefiller's NIC and the decoder's at once, which is the bracket around P.nic[i] and D.nic[j], and moves the prompt's KV from the prefiller's leased blocks to the decoder's (P.kv[i] → D.kv[j]) after the decoder's read latency.

Configuration

The example has two prefill instances and two decode instances, block size 16, separate KV and request-slot pools, and a NIC per instance. Costs and capacities are illustrative; this is not the llm-d guide's gpt-oss-120b hardware configuration.

In serQ

examples/pd-disaggregation/llmd_nixl_pull.sq

// Prefill/decode disaggregation as llm-d runs it on vLLM: the llm-d router
// (llm-d/llm-d at 8a2f37d, llm-d/llm-d-inference-scheduler at 13eebdb) in
// front of NP prefill and ND decode instances that hand the KV over with the
// NIXL connector in its pull mode (ref/vllm at 0c87a197,
// `vllm/distributed/kv_transfer/kv_connector/v1/nixl/`).
//
// One request: the router picks a decode pod (the least busy) and asks its
// prefix-cache estimate how much of the prompt that pod already has; a long
// enough uncached suffix means a remote prefill, for which it picks a prefill
// pod (a cache-warm one, then the least loaded); a short one means the decode
// pod prefills the prompt itself. On a remote prefill the decode pod's sidecar
// sends the prompt to the prefiller with max_tokens = 1, waits for its
// answer, and only then sends the decode request to its own engine. The
// prefiller's scheduler frees the request's slot when the one token is
// sampled but keeps its blocks leased for the decoder's read; the decoder's
// scheduler takes the request when the whole prompt fits in its blocks and
// parks it (WAITING_FOR_REMOTE_KVS) while its worker reads the KV from the
// prefiller; the read done, the prefiller frees the lease (its full blocks
// stay cached), and the decoder's request queues once more for a running slot
// and a token of budget, recomputes the last prompt token for its logits,
// and decodes. docs/use-cases/pd.md has the line-by-line correspondence.
use "../../lib/vllm.sq";

use "std/args";

let NP = 2;            // prefill instances
let ND = 2;            // decode instances
let B = 8192;          // max_num_batched_tokens
let max_seqsP = 16;    // max_num_seqs on a prefiller
let max_seqsD = 64;    // max_num_seqs on a decoder
let blocksP = 10000;   // num_gpu_blocks on a prefiller
let bs = 16;           // block_size
let max_model_len = 16384;  // every KV pool holds one request of it: vLLM refuses to start otherwise (kv_cache_utils.py:864-900, called at kv_cache_utils.py:2742)
let a = 2e-5;          // compute per scheduled token (s)
let omega = 2e-4;      // weights read per iteration (s)
let beta = 2e-9;       // KV read per iteration per resident context token (s)
let c0 = 0;            // fixed cost per iteration (s)
let BwP = 2e5;         // NIXL bandwidth out of a prefiller, tokens/s (128 KB per token at 25 GB/s)
let BwD = 2e5;         // and into a decoder (one NIC each: the tensor-parallel fan-out of the read is not modelled)
let x0 = 0.002;        // per-read latency: posting the READ and the step that polls its completion (s; nixl/pull_worker.py:545-558)
let minp = 0;          // prefix-based-pd-decider promptTokens
let p = 0.9;           // continue after a turn
let Z = 3.0;           // tool time (s)

fn main() {
  let blocksD = args.number("blocksD", 10000);   // num_gpu_blocks on a decoder
  let thr = args.number("thr", 512);         // prefix-based-pd-decider nonCachedTokens (1: the guide's always-disagg-pd-decider)
  let Lambda = args.number("Lambda", 0.6);      // sessions per second

  // The deployment: what the router, the sidecar and the two schedulers do
  // with one request. The router and the sidecar are the gateway; each
  // scheduler is its queue's entries, and the two NICs of a read are links.
  queue gw : gateway {
    route {
      set prompt = K + n;
      // The router. Decode profile first: the least busy decode pod
      // (active-request-scorer). Then the decider: a remote prefill only when the
      // prompt's uncached suffix on that pod is long enough
      // (prefix-based-pd-decider: nonCachedTokens, promptTokens); the estimate is
      // the router's own prefix-cache picture of the pod.
      choose j in ND by (holders(D[j].kv) + queued(D[j].kv));
      set hitD = min(cachedin(D[j].kv), reusable(prompt, bs));
      set remote_prefill = prompt >= minp && prompt - hitD >= thr;
      branch (remote_prefill) {
        // Prefill profile: a pod that has the prefix (prefix-cache-affinity-filter),
        // then the least loaded (token-load-scorer).
        choose i in NP by (cachedin(P[i].kv) > 0 ? 0 : 1, work(P[i]) + queued(P[i].reqs));
        P[i].prefill (prompt);              // the sidecar: max_tokens = 1, wait for the answer
        set t1 = now;
        D[j].decode (prompt) from P[i];     // then the decode request, its KV read from P[i]
        observe lease = D.read_done - t1;   // how long the prefiller's blocks stayed leased
      } else {
        D[j].decode (prompt);
      }
      observe remote = remote_prefill;
    }
  }

  // A prefill instance: vLLM's engine on one device (examples/multi-turn/vllm.sq)
  // with no decode. The scheduler admits a request with a slot and the blocks
  // of its first chunk, and room for the whole prompt
  // (scheduler_reserve_full_isl). When the one token is sampled the request is
  // finished on the prefiller: the slot goes and the blocks stay leased for the
  // decoder's read (request_finished: delay_free_blocks), 30 s renewed by the
  // decoder's heartbeats while it waits, so in effect until the read.
  queue P[NP] : prefill {
    device gpu { compute (t) = t * a; hbm (k) = omega + beta * k; kv cap blocksP * bs; }
    engine on gpu {
      reqs cap max_seqsP;
      tokens cap B;
      schedule { advance running; admit waiting while (running.preempted == 0); }
      execute (c0 + max(hbm(batch.kv_decode + batch.kv_prefill), compute(batch.tokens)));
    }
    pool reqs on P { queue fifo; }
    pool kv on gpu { block bs; evict lru; preempt lifo; }
    nic ps(BwP);                          // the pod's NIC: the reads out of it share it
    prefill (prompt) {
      hold reqs (cost(reqs, 1)), kv (cost(kv, min(prompt, reused + budget_left(P)))) reserve (cost(kv, prompt))
           at admission (reused = min(cachedin(kv), reusable(prompt, bs))) {
        set c = cached;
        run P prefill (cost(P, prompt - c)) growing kv;      // chunked; one token is sampled and discarded
      } cache (cost(reqs, kv, prompt)) lease kv (inf);
    }
  }

  // A decode instance: vLLM's engine on one device, with two ways in. Its
  // scheduler serves its queues in this order: the requests whose KV has
  // arrived first (vLLM's `skipped_waiting`, scheduler.py:2383-2385), then the
  // new ones, and the first that does not fit stops the step's admissions.
  queue D[ND] : decode {
    device gpu { compute (t) = t * a; hbm (k) = omega + beta * k; kv cap blocksD * bs; }
    engine on gpu {
      reqs cap max_seqsD;
      tokens cap B;
      schedule { advance running; admit waiting while (running.preempted == 0); }
      execute (c0 + max(hbm(batch.kv_decode + batch.kv_prefill), compute(batch.tokens)));
    }
    pool reqs on D { queue fifo; }
    pool kv on D.gpu { block bs; evict lru; preempt lifo; }
    nic ps(BwD);                          // the pod's NIC: the reads into it share it

    // Decode only: the pod prefills the prompt itself (examples/multi-turn/vllm.sq).
    decode (prompt) {
      set produced = min(o, max_model_len - prompt);   // generation stops at max_model_len tokens (sched/utils.py:114-120)
      set kept = prompt;   // the most tokens an attempt had: a preemption keeps the outputs
      hold kv (cost(kv, min(known, reused + budget_left(D)))) reserve (cost(kv, known)), reqs (cost(reqs, 1))
           at admission (known = max(kept, computed + 1),
                         reused = min(cachedin(kv), reusable(known, bs))) {
        set kept = known;
        set c = min(cached, reusable(known, bs));
        observe local_tokens = known - c;
        run D prefill (cost(D, known - c)) growing kv;
        run D decode (cost(D, produced - 1 - (known - prompt))) growing kv;
      } cache (cost(kv, reqs, prompt + produced));
    }

    // With remote KV. The sidecar's decode request is taken when the whole
    // prompt fits the blocks, at a step with budget left and a running slot
    // free - it takes neither (the request is parked, not running) - and
    // reuses the full blocks it has of the prompt.
    decode (prompt) from P {
      set produced = min(o, max_model_len - prompt);   // generation stops at max_model_len tokens (sched/utils.py:114-120)
      set transferred = 0;   // one KV transfer per request (nixl/pull_scheduler.py:187-189)
      set kept = prompt;     // the most tokens an attempt had: a preemption keeps the outputs
      hold kv (cost(kv, known)) reserve (cost(kv, known)), reqs (cost(reqs, 0)) reserve (cost(reqs, 1))
           reuse (cost(kv, reqs, reusable(known, bs)))
           at admission (known = max(kept, computed + 1)) {
        set kept = known;
        set c = cached;
        branch (!transferred) {
          // WAITING_FOR_REMOTE_KVS: every block past the local hit is read
          // from the prefiller over NIXL, through its NIC and this pod's at
          // once; the read done, the prefiller's lease ends. The last prompt
          // token is recomputed for its logits.
          observe remote_tokens = prompt - c;
          transfer (prompt - c) from P to kv (prompt - 1 - c);   // over P's NIC and this pod's
          mark read_done;
          set transferred = 1;
          set c = prompt - 1;
        }
        // Back in the waiting queue: a running slot and a token of budget.
        // A request preempted on the decoder afterwards recomputes what it
        // lost here, as any local prefill would (do_remote_prefill is spent).
        hold reqs (cost(reqs, 1)) {
          run D prefill (cost(D, known - c)) growing kv;
          run D decode (cost(D, produced - 1 - (known - prompt))) growing kv;
        }
      } cache (cost(kv, reqs, prompt + produced));
    }
  }

  // The decoder's worker reads the KV (NIXL pull): it posts the READ and finds
  // it done at a later step, a fixed wait per read, and the bytes cross the
  // prefiller's NIC and the decoder's at once. How concurrent reads divide the
  // two NICs is UCX's and the fabric's, not vLLM's: max-min fairness is the
  // model, not a measurement (docs/design/bandwidth-sharing.md).
  D pull P latency x0 share maxmin;

  // The client: sessions arrive, each turn brings a prompt of n new tokens on
  // a context of K and wants o tokens back, and after a turn the session calls
  // a tool and comes back with probability p.
  workload {
    arrive poisson(Lambda);
    hidden o;              // the scheduler knows max_tokens, not the length (sched/utils.py:98-119)
    init { set K = 0; }
    turn {
      // Whole tokens, as vLLM counts them: a fractional length can leave a
      // request less than the one token its prefill samples (near
      // max_model_len, or preempted in its last fraction of a token).
      set n = ceil(K == 0 ? ~uniform(1000, 3000) : ~exp(500));
      set o = floor(~exp(200)) + 1;
      set more = ~bernoulli(p);
    }
    session {
      turn;
      while (more) {
        set K = prompt + D.produced;
        tool (~exp(Z));
        turn;
      }
    }
  }

  server {
    // vLLM refuses a prompt of max_model_len tokens or more before it is
    // scheduled (input_processor.py:512-536): the session ends there.
    observe too_long = K + n >= max_model_len;
    branch (K + n >= max_model_len) { end; }
    gw.route();
  }

  // How evenly the router spreads the decoders, read at every instant: the
  // time average of a spread is not the spread of the per-pod averages. The
  // KV usage is vLLM's `kv_cache_usage` (block_pool.py:879-890, of the free
  // blocks; a cached block nobody holds is one, block_pool.py:42-45) but for
  // its null block, which vLLM takes out of
  // num_gpu_blocks and the pool here does not; the load is the
  // active-request scorer's.
  gauge running_spread = max k in ND (used(D[k].reqs)) - min k in ND (used(D[k].reqs));
  gauge kv_usage_max = max k in ND (used(D[k].kv) / (used(D[k].kv) + free(D[k].kv)));
  gauge kv_usage_mean = sum k in ND (used(D[k].kv) / (used(D[k].kv) + free(D[k].kv))) / ND;
  gauge load_spread = max k in ND (holders(D[k].kv) + queued(D[k].kv))
                    - min k in ND (holders(D[k].kv) + queued(D[k].kv));
}

Routing

The gateway selects a decoder by holders + queued, then compares its uncached prompt suffix with thr. For remote prefill, it selects a prefiller with a cached prefix first, then by load. It runs the prefill entry before the decode entry. The router reads the model's actual cache state rather than a delayed or approximate cache index.

The model uses thr = 1 for always-remote prefill and larger thresholds to keep short uncached suffixes on the decoder. The server's max_model_len check and the decode entries' output cap limit request length.

Scheduler correspondence

vLLM	serQ	Where
a prompt of max_model_len tokens or more is refused before it is scheduled; a generation stops at max_model_len tokens; no KV cache smaller than one request of max_model_len is started	set accepted = K + n < max_model_len; branch (accepted) { gw.route(); } in server; set produced = min(o, max_model_len - prompt) in each decode entry; max_model_len = 16384 below every pool	input_processor.py:512-536; sched/utils.py:114-120; kv_cache_utils.py:864-900, called at kv_cache_utils.py:2742
the prefiller admits like any vLLM engine: a slot, the blocks of the first chunk, room for the whole prompt, the prefix hit looked up when the scheduler takes the request	hold reqs (cost(reqs, 1)), kv (cost(kv, min(prompt, hit + budget_left(P)))) reserve (cost(kv, prompt)) at admission (hit = …) in P's prefill entry	the waiting loop, scheduler.py:868-1128; the vLLM use case
the prefiller computes the prompt in chunks and samples one token, which the sidecar discards	run P prefill (cost(P, prompt - c)) growing kv	scheduler.py:624-823; the truncation for Mamba and MTP only, nixl/base_scheduler.py:409-436
the request finishes on the prefiller: its slot is freed, its blocks are not — request_finished returns delay_free_blocks and a lease of kv_lease_duration (30 s), renewed by the decoder's heartbeats while the request waits	} cache (prompt) lease kv (inf); — the scope ends, the slot goes, the blocks stay the session's	nixl/pull_scheduler.py:191-292; _free_request, scheduler.py:2628-2657; the renewal, nixl/base_scheduler.py:199-238, nixl/base_worker.py:3010-3030
the prefiller keeps every computed full block of the prompt cached once the lease ends	cache (prompt) on that hold, applied when the lease ends	_connector_finished, scheduler.py:2929-2982; kv_cache_manager.py:610-619
the decoder's scheduler looks at its waiting queue only at a step with budget left and a running slot free	pool reqs on D and pool kv on D.gpu: D admits both; reqs (0) reserve (1) — a slot must be free, none is taken	scheduler.py:872-879
the decoder's local prefix hit, then the connector: for a remote prefill every prompt token beyond the local hit is external and loaded asynchronously	kv (known) reserve (known) with reuse (reusable(known, bs)) in D's decode … from entry; c = cached is the local hit	scheduler.py:932-954; nixl/pull_scheduler.py:34-66
blocks are allocated for the whole prompt, and the request is parked, WAITING_FOR_REMOTE_KVS, holding them and no slot; one transfer per request	the hold on kv; transferred is do_remote_prefill, spent	scheduler.py:1199-1226, 1264-1294; nixl/pull_scheduler.py:108-189
the worker reads the blocks from the prefiller over NIXL (pull mode: a NIXL READ issued by the decoder)	transfer (prompt - c) from P to kv (prompt - 1 - c) in D's entry, and D pull P latency x0 share maxmin;: the decoder reads; a fixed wait, then the bytes out of the prefiller's NIC and into the decoder's at once, the two shared max-min fairly (a model, not a measurement: Bandwidth sharing)	nixl/pull_scheduler.py:168-177; the worker's _read_blocks, nixl/pull_worker.py:392-575
the read done, the blocks are cached, the last prompt token is marked uncomputed (its logits are needed), and the request is back in the waiting queue, served before new arrivals	the load D.kv[j] (cost(D.kv, prompt - 1 - c)) the transfer stands for; hold reqs (cost(reqs, 1)), with reqs declared before kv	_update_waiting_for_remote_kv, scheduler.py:3032-3077; _try_promote_blocked_waiting_request, scheduler.py:3079-3092; scheduler.py:2383-2385
the prefiller frees the leased blocks when the read completes	the release P.kv[i] the transfer stands for takes the lease	_update_from_kv_xfer_finished, scheduler.py:3113-3138
the decoder recomputes the last prompt token and decodes; a request preempted afterwards is rescheduled without a second transfer, prefilling locally what it lost	run D prefill (cost(D, known - c)) growing kv; run D decode (cost(D, o - 1 - (known - prompt))) growing kv; with known from computed	scheduler.py:1560-1561; nixl/pull_scheduler.py:187-189
a parked request is in no running list and is not preempted; nor is the prefiller's finished one	preempt lifo takes the last admitted resident of the engine	scheduler.py:742-813
the decoder keeps the prompt's and the output's full blocks cached	} cache (prompt + o)	kv_cache_manager.py:602-606

Writing xPyD

The deployment is queues: NP prefill instances and ND decode instances, each with its own KV pool, request-slot pool, engine and NIC, and one gateway selected by gw.route(); in the server.

queue gw : gateway { route { … } }                 // the router and the sidecar
queue P[NP] : prefill { device gpu { … kv cap blocksP * bs; } engine on gpu { … } pool reqs on P { … } pool kv on gpu { … } nic ps(BwP); prefill (prompt) { … } }
queue D[ND] : decode  { device gpu { … kv cap blocksD * bs; } engine on gpu { … } pool reqs on D { … } pool kv on D.gpu { … } nic ps(BwD); decode (prompt) { … } decode (prompt) from P { … } }
D pull P latency x0 share maxmin;                  // the decoder reads the KV from the prefiller

A queue's device, engine and pools are its members': P[i].kv is the KV of the i-th prefiller, engine on gpu is the member's engine, named after the queue (P), pool reqs on P means the member's own scheduler serves the pool, and pool kv on gpu counts the member's own blocks as its running requests' memory (batch.kv_decode, batch.kv_prefill). A decoder's request waits for its blocks, not for a slot, so its pool is on D.gpu: the decoder's scheduler admits it in an iteration, as vLLM's does. The family's size is the let the router chooses over (queue D[ND], choose j in ND), so the number is written once. Each pod's NIC is its own (nic ps(BwD);, the stage D.nic), and D pull P latency x0 share maxmin; is the transfer's topology and mode in one line: the decoder reads the KV from the prefiller, waits x0 before each read, and concurrent reads divide the two NICs max-min fairly.

The router is the gateway's two chooses, and the instance it picked is the queue the request is handed to: P[i].prefill (prompt), then D[j].decode (prompt) from P[i]. Inside an entry nothing is indexed — kv, reqs, P are the member's own. from P[i] is the pool P's entry leases, and the read's NICs are the relation's: the source member's P.nic[i] and the reader's own D.nic[j]. The transfer's load and release name the pool as the holds did, index included. The admission, the allocation and the two runs are the entries' and appear once each: the router's body has no hold.

Change NP and ND in the source to change the instance counts. The router and queue entries use these family sizes directly.

Pull and push

The pull example dispatches the prefill and decode entries serially. The prefiller leaves a lease; the decoder allocates its destination and reads across both NICs. transfer accounts for link work, loads the destination's computed KV, and releases the source lease.

The push example uses fork { P[i].prefill (prompt); } and joins before transfer. Decoder allocation can proceed while prefill runs, matching the concurrent dispatch in vLLM's push proxy (disagg_proxy_pushconnector_demo.py:227-270). The write waits for both prefill completion and destination registration (nixl/push_scheduler.py:128-205, nixl/push_scheduler.py:207-294). Under decoder pressure, both models retain the source lease until destination memory is available.

Limits

• Leases use inf: expiry, heartbeats and failure recovery are not modeled. vLLM grants and tracks a bounded lease (nixl/pull_scheduler.py:248-269) and extends it with heartbeats (nixl/base_worker.py:3010-3030).
• Transfers do not model bidirectional KV reuse between turns, accelerator host buffers or tensor-parallel fan-out.
• Prefix caches are per session, without cross-session content sharing.
• The router reads exact model state; stale or approximate routing metadata is not represented.
• Max-min NIC sharing and fixed read latency are modeling assumptions.

Run the example

serq run examples/pd-disaggregation/llmd_nixl_pull.sq --horizon 2000 --warmup 200 --seed 1 --json

At the defaults (seed 1, horizon 2 000 s, warm-up 200 s), the run gives:

Metric	Result
Remote-prefill fraction	57.7%
Mean TTFT	27.3 ms
Mean response	69.9 ms
Mean source lease	12.9 ms
Rejected / stuck sessions	0 / 0

These are simulation observations, not hardware measurements or intervals across seeds. The lease includes waiting for decoder capacity and the transfer. Use --dump to inspect per-request observations.

Validation

The vLLM correspondence is checked against the pinned source by scripts/check_citations.py. tests/pd_semantics.rs checks lease lifetime, release, load, transfer and the coupling between decoder capacity and prefiller occupancy. These are deterministic tests of the interpreter's semantics, not differential checks against two real vLLM schedulers.