fix(server): a chunked prefill is starved until the decode batch drains #1011

Summary

BatchScheduler::decide_action returns Decode whenever any sequence is active. A prompt admitted into a busy batch and routed to the chunked-prefill path therefore makes no progress at all until the active batch drains. With streams arriving continuously, that wait is unbounded, so the admitted request's TTFT has no ceiling.

Evidence

Measured on M1 Ultra with mlx-community/Meta-Llama-3.1-8B-Instruct-4bit, --parallel 8 --prefill-chunk-size 512. Four 400-token decode streams start, then one ~10k-token prompt (19 chunks at 512) is admitted at t=6s. Sampling /metrics every 5s:

The prefill runs one chunk and then stops for 20 seconds while decode advances 256 steps. It resumes only at t=30s, once decode has drained to its ceiling. Reproduce with scripts/bench/starvation_probe.sh baseline (landed in PR #1010).

Where it is pinned

The behavior is already asserted as a fixed point by the test chunked_prefill_starves_until_active_batch_drains in src/server/batch/tick_policy_tests.rs. The policy itself is one pure function, decide_tick over a flattened TickState, in src/server/batch/tick_policy.rs, called by both BatchScheduler::decide_action and the scheduler tests, so there is a single place to change. That test will need updating as part of the fix; it currently documents the defect rather than forbidding it.

Why it was invisible

The scheduler tests previously asserted against a mirrored copy of the policy rather than the policy itself, so a test could pass while describing behavior the server did not have. PR #1010 removed the mirror; the helpers in scheduler_tests.rs now delegate to decide_tick.

Scope of the fix

Grant a parked chunked prefill a tick under a fairness policy so the admitted request's TTFT is bounded while the batch decodes. This issue owns the policy choice, the default, and the tuning. Candidates:

1. A grant counter: give the prefill one tick every N decode ticks. Cheapest, no forward-path change.
2. A starvation deadline: grant a tick once a parked prefill has waited longer than some bound.
3. A prefill-priority mode: an operator-selected policy for TTFT-sensitive deployments.
4. MixedStep, the MLXCEL_MIXED_STEP prototype from Mixed prefill/decode step execution: design spike and prototype #908, which advances both workloads every tick. It demonstrably removes the starvation (all 19 chunks complete by t=20s instead of t=40s, with decode reaching the same step count), but it is the most aggressive point on the frontier and is not proposed as the default.

What must be measured before choosing a default

Changing which workload wins a contended tick changes the latency profile of every concurrent workload. The number this needs is the admission-window ITL p95 inflation for the decoding streams under each candidate policy, which ADR 0005 lists as an open cell and deliberately did not measure, since it belongs to whichever policy ships. The harness exists: scripts/bench_mixed_step_admission.py reports per-stream ITL p50/p95 split into a quiet window and an admission window, plus the admitted request's TTFT, and it refuses to print a table when counter attribution fails. Run it on a quiet machine; the ADR's own run was on a loaded one and says so.

Acceptance Criteria

• A fairness policy is chosen from the candidates above (or an equivalent), with the rationale recorded.
• decide_tick grants a parked chunked prefill a tick under that policy, so a prefill admitted into a busy batch has a bounded TTFT.
• chunked_prefill_starves_until_active_batch_drains is replaced by a test that forbids the starvation instead of pinning it.
• scripts/bench/starvation_probe.sh shows prefill_chunks_total advancing while decode is active, and the ~10k prompt completing well before the decode batch drains.
• Admission-window ITL p50/p95 for the decoding streams is measured with scripts/bench_mixed_step_admission.py on a quiet machine, for the shipped policy and for the baseline, and the inflation is reported.
• ADR 0005 is updated with the measured number and the shipped default.
• The policy default and any operator-facing flag or environment variable are documented, and the change is exercised end to end through mlxcel-server rather than in the policy unit test alone.

Technical Considerations

• The policy is a single pure function, so the change is confined to decide_tick plus its state; the forward path does not need to change for candidates 1 through 3.
• Candidate 4 changes the executed step shape, not just the tick decision, so it carries a larger validation surface.
• Any grant policy needs a rule for multiple parked prefills so the fix does not merely move starvation from prefill-versus-decode to prefill-versus-prefill.

Context

Found by the #908 design spike, which set out to fix a different symptom and discovered the premise was inverted: tick alternation does not stall decode, because the alternation never happens. See ADR 0005 (docs/adr/0005-mixed-prefill-decode-step-execution.md), issue #908, epic #909, and docs/benchmark_results/mixed-step-prototype-m1ultra-2026-08-03.md.