# M3.8 — Batched prefill across requests (the real TTFT lever)

> Discovered 2026-05-07 from B.1.2 falsified hypothesis + server log
> evidence. M_b.2 (FP8 prefill TileLang) and B.1.2 (prefill async sync)
> were both wrong direction. The real TTFT gap to vLLM lives in
> **prefill batching across requests**, not kernel speed and not CPU sync.

## P0 finding (the math that disproves the kernel hypothesis)

> **2026-05-07 correction**: the original draft of this section
> read the server-log `batch=N` field as the prefill batch size.
> Code-survey (`infer/src/scheduler/cuda/execution.rs:671`)
> confirmed `batch=N` is `self.active_len()` — total active
> requests in the scheduler, NOT the per-step prefill batch.
> The `batch=1` value I observed was simply the FIRST step where
> only Request 0 was active (Requests 1-3 still queueing). After
> all 4 requests were admitted, the value would have been 4.
>
> Re-reading the qwen3/prefill.rs source confirms cross-request
> token packing IS implemented (L295: `let mut sequences =
> Vec::with_capacity(requests.len());`, L417: `packed_tokens` from
> all requests). And `prefill_max_requests` defaults to `None`
> (unbounded). So **the cross-request batching IS available**.
> The TTFT gap to vLLM is then either:
>   (a) a kernel/algorithm efficiency gap at the SAME batched
>       shape, or
>   (b) the scheduler not actually filling the prefill batch
>       width when candidates are queued (admission policy).
>
> The Phase 0 task below is now to **bench a configuration
> that should expose this** — find a server log step where
> multiple requests are mid-prefill simultaneously, check the
> per-step `prefill_rows` metric, see if it's > 1 chunk's worth.

ARLE server log during longctx 8k/c=4 bench (2026-05-07-prefill-trace):
```
step breakdown: plan=prefill admission=109us decode=0us emit=0us prefill=430821us total=430930us batch=1
```

Per chunk (2048 tokens, observed step):
- GPU prefill time: **430.8 ms** for THIS step
- If this step packed N requests' chunks (N×2048 tokens):
  per-token time = 430 / (N×2048) ms
- If N=1: 0.210 ms/token (single-request equivalent)
- If N=4: 0.053 ms/token — significantly faster than vLLM's 0.29

But ARLE TTFT for 8192-token prompt at c=4:
- 4 chunks/request × c=4 requests = **16 chunk-units serialized** at batch=1
- 16 × 430 ms = **6.9 s of GPU prefill time per "first 4 requests"**
- Measured TTFT mdn = 4961 ms → matches the serialization model

vLLM TTFT = 2367 ms at same shape, with `--max-num-seqs 8`. vLLM
clearly batches multiple requests' prefill chunks into one step:
- 2367 ms / 0.21 ms/token (assume ARLE-equivalent per-token cost) ≈
  11.3k tokens of work per request worth of GPU time
- For 8k tokens × 4 reqs = 32k tokens total, 32k / (TTFT × parallelism)
  → vLLM's effective parallelism is roughly **8× ARLE's batch=1**

## Hypothesis (NOT yet falsified — to be tested cheaply)

If ARLE's prefill scheduler `step_prefill_batch` only ever processes
ONE request's chunk per step (batch=1), then the TTFT-vs-vLLM gap
**disappears** when prefill batches across requests at batch ≥ 4.

Falsification cost: ~10 lines added log + 60s bench. If `batch=N>1`
shows up in the prefill step log lines after this, the hypothesis is
already half-supported (scheduler CAN batch but isn't); if not, we
need to add the cross-request batching to scheduler.

## Why B.1.2 didn't help (post-mortem)

B.1.2 removed prefill `cuStreamSynchronize`, expecting -800 ms TTFT.
Actual: -28 ms.

Reason: even if the per-step CPU sync goes away, **the next step
still processes one request's chunk**. The serialization is
algorithmic (scheduler choice), not synchronization (CPU wait). 16
serial chunks × ~430 ms each = 6.9 s GPU time, period.

The trace evidence we DID have (Phase 1 nsys for high-conc) showed
the per-step `cuStreamSynchronize` problem applies to **decode**
(where it was 65 ms wait per tick = 80% of step_total). That data
did NOT generalize to prefill because prefill chunks dominate GPU
work themselves (430 ms each), so the CPU sync wait was
proportionally tiny.

## Proposed design

### Phase 0 — quick instrumentation + bench-trace verification (30 min)

1. Add a `batch=N` line to the prefill step log (already there per the
   2026-05-07-prefill-trace log). Verify `batch=1` is universal at the
   8k/c=4 workload by grep-ing the server log.
2. Check `infer/src/scheduler/cuda/prefill.rs::step_prefill_batch` for
   the actual batching logic. Is there a per-step cap of 1, or is it
   "select all candidates that fit in budget"? The code may already
   support batching — the `prefill_max_requests` flag from M3.6 §F1
   plan controls this.
3. If `prefill_max_requests` defaults to 1, **bumping it to N** is a
   1-line config change. Bench at the same workload to see if TTFT
   drops as expected.

### Phase 1 — true cross-request batched prefill (if Phase 0 doesn't fix it)

If the scheduler is structurally limited to batch=1 per prefill step:

1. **Scheduler change**: `step_prefill_batch` already takes a
   `Vec<PrefillCandidate>`. The constraint is the kernel:
   `prefill_attention_paged_qk_norm_rope_hd128_kernel` only handles
   ONE request's tokens per launch. The TileLang prefill kernel
   (`batch_prefill_paged_hd128.py`) DOES support `batch_size > 1`
   and `total_q_tokens > one_request_worth` — confirmed by HD128
   prefill template's symbolic int args (`batch_size`,
   `total_q_tokens`, `q_indptr`).

2. **Plumb cross-request prefill into the existing TileLang HD128
   prefill path**: change `step_prefill_batch` to pack multiple
   candidates' Q tokens into one tensor and one launch. Use the
   `q_indptr` parameter (already in the wrapper FFI ABI for HD128
   prefill) to delineate per-request boundaries.

3. **Page-table coordination**: each request has its own page list;
   batched prefill needs a `kv_indptr` describing per-request page
   ranges. Already supported by ATTENTION_PUBLIC_PARAMS (kv_indptr,
   kv_indices). The kernel writes K/V to each request's pages
   independently.

4. **Mix with decode**: existing `step_mixed_launch` already mixes
   prefill chunks with decode rows. After M3.8, `step_mixed_launch`
   can mix prefill chunks from multiple requests with decode rows.

## Tasks

| # | Task | File | LOC est. | Owner |
|---|---|---|---|---|
| Phase 0.1 | Survey: is `prefill_max_requests` defaulting to 1? Check `step_prefill_batch` logic | `infer/src/scheduler/cuda/prefill.rs::step_prefill_batch` | 0 (read) | Claude |
| Phase 0.2 | If defaulting to 1: bump default + bench | `infer/src/main.rs` (config default) + bench | ~5 + bench | Claude |
| Phase 1.1 | Plumb cross-request Q packing into prefill launch | `model/qwen3/prefill.rs` + `ops/attention.rs` | ~150 | Codex |
| Phase 1.2 | Update `step_prefill_batch` to call batched path with multiple candidates | `scheduler/cuda/prefill.rs` | ~80 | Codex |
| Phase 1.3 | Bench longctx 8k/c=4 — expect TTFT 4961 → ~2000 ms | bench | 0 | Claude |
| Phase 1.4 | nsys re-trace (with the right bench shape this time — high-conc + many simultaneous requests for nsys to actually capture activity) | scripts | 0 | Claude |

## Acceptance

- Server log `step breakdown: plan=prefill ... batch=N` shows N≥4
  at c=4 workload after Phase 0.
- `cargo test --features cuda --test e2e` passes.
- `cargo test --features cuda --test greedy_consistency` passes
  (numerical equivalence: cross-request batched prefill must
  produce identical token outputs to single-request prefill).
- Bench TTFT mdn at longctx 8k/c=4 ≤ 3000 ms (target: close 70%
  of ARLE-vs-vLLM gap from 4961 → 2367).

## Risks + retreat

- **R1 — Q packing breaks per-request RoPE / position encoding**:
  `prefill_attention_paged_qk_norm_rope_hd128_kernel` applies RoPE
  inside the kernel based on per-request position offsets. Cross-
  request batching must pass per-request `position_start` (already
  in the per-chunk metadata). Mitigation: greedy_consistency test
  verifies byte-exact output.
- **R2 — Page-allocation contention across requests in same step**:
  if request A and B both need new pages mid-prefill, the page
  allocator must serve both consistently. ARLE's `paged_kv_pool`
  has been mostly used in single-request-per-step mode; need to
  verify atomic allocation. Mitigation: pre-allocate all chunk's
  pages BEFORE launching the batched prefill.
- **R3 — Memory: batched Q tensor for N requests at chunk_size 2048
  is 2048*N*hidden_dim*2 bytes**. At N=4, hidden=2560 (Qwen3-4B):
  ~40 MB. Negligible.

## Rule

- **Bench evidence + log evidence > plan estimates**. Both F4-Small
  and the M3.8 hypothesis here came from concrete numbers
  (Phase 1 trace showing 65ms sync; server log showing batch=1).
  Both B.1.2 and original M_b plans came from "the kernel must be
  the bottleneck because it shows up large in the trace top-N",
  which doesn't account for CPU/scheduler-level inefficiencies.
- **Read the server log lines before reaching for nsys.** ARLE
  emits structured step breakdowns that already contain the
  bottleneck signal in many cases. Cheaper than nsys, and (based
  on this iteration) sometimes more reliable for low-concurrency
  shapes where nsys capture buffers don't reliably populate.
