Part 4. TANREN — an Evolved Scheduler Patched into vLLM Halves Tail Latency Under Heavy Load

This is Part 4 of the TANREN series. The project overview is here, and Part 3 (improving vLLM’s prefix cache) is here. Same hardware, same method — this time the target is closer to the heart of the engine: the order in which requests get processed.

The Conclusion First

These are A/B measurements on a real vLLM (Llama-3.1-8B, NVIDIA GB10), replaying real-world request arrivals from BurstGPT traces. Against vLLM’s default FCFS (first-come-first-served), the evolved scheduling policy performed as follows:

At the heaviest load point (sparse trace × 280x time compression), response times were cut in half.

What I Did

vLLM processes incoming requests in FCFS (first-come-first-served) order by default. Under congestion, short requests pile up behind long prompts and the whole queue drags. The question of “what order to process requests in, and what to postpone when overloaded” was evolved with the same method as Parts 2 and 3:

1. Grow the policy in a loop of verifier (a serving simulator) and evolution.
2. Pass a final judgment on held-out traces from a different period, never used during evolution — still in simulation (15/16 wins, p=2.6×10⁻⁴).
3. Only then patch it into the real vLLM as a one-file patch and A/B test on hardware.

The resulting policy is 117 lines of Python (excluding blanks), and its mechanism is readable: it detects the load level automatically and adapts how far to lean toward SJF (shortest-job-first). When a backlog builds, it favors short jobs to clear the congestion; when the server is idle, it behaves like the default FCFS and breaks nothing.

All 16 Hardware Configurations

Four trace windows × two load levels × two repeats = 16 pairs, with the identical arrival sequence replayed to both policies in each pair.

Window / compression / repeat	mean TTFT: FCFS → evolved	p99 TTFT: FCFS → evolved
sparse / ×175 / r1	16.8s → 13.6s (−18.8%)	27.2s → 23.3s (−14.5%)
sparse / ×175 / r2	17.0s → 13.5s (−20.4%)	27.6s → 23.1s (−16.2%)
sparse / ×280 / r1	32.0s → 16.2s (−49.3%)	51.5s → 26.9s (−47.9%)
sparse / ×280 / r2	32.0s → 16.3s (−49.1%)	51.6s → 27.0s (−47.6%)
window B / ×3 / r1	0.48s → 0.47s (−1.0%)	1.20s → 1.14s (−5.0%)
window B / ×3 / r2	0.49s → 0.48s (−2.1%)	1.24s → 1.11s (−9.9%)
window B / ×5 / r1	11.5s → 7.4s (−35.6%)	29.7s → 22.9s (−22.9%)
window B / ×5 / r2	11.4s → 7.4s (−35.1%)	29.4s → 22.8s (−22.5%)
window C / ×75 / r1	8.9s → 8.3s (−6.1%)	22.8s → 22.4s (−1.5%)
window C / ×75 / r2	8.8s → 8.0s (−8.9%)	22.7s → 21.7s (−4.2%)
window C / ×120 / r1	20.3s → 11.6s (−42.7%)	43.2s → 30.5s (−29.3%)
window C / ×120 / r2	20.6s → 13.2s (−35.9%)	43.4s → 32.7s (−24.6%)
window A / ×14 / r1	0.27s → 0.27s (−0.6%)	0.44s → 0.43s (−0.9%)
window A / ×14 / r2	0.27s → 0.27s (+0.1%)	0.45s → 0.45s (+1.6%)
window A / ×22 / r1	0.79s → 0.78s (−0.3%)	1.97s → 1.97s (+0.1%)
window A / ×22 / r2	0.79s → 0.78s (−0.5%)	1.91s → 1.98s (+3.7%)

Hardware tests (16 pairs, 8B, GB10)	Result
mean TTFT	15/16 wins, p=2.6×10⁻⁴
p99 TTFT	13/16 wins, p=0.011
No-pressure configurations	±0% (every loss is a +0.1-3.7% sliver on an idle configuration) = zero harm
Heavy-load configurations	mean and p99 both −35-49%
Policy errors	0

Note where the losses occur: every one of them is a difference of a few percent on an idle configuration, where there is no queue to fix in the first place. The policy behaves like the default when the server is idle, and changes its behavior only under congestion — exactly as designed, now confirmed on hardware.

The Ranking Against the Classics — What “Zero Tail Violations at the Top” Means

Scheduling has strong classical approaches. The SJF family shrinks the mean nicely, but it keeps pushing long jobs back, sacrificing the tail — some user ends up waiting without bound. In the final simulator judgment (held-out traces, summed over 16 configurations, comparing single policies):

Policy	Total score (FCFS = 0 baseline)	Tail-constraint violations
Evolved	+1.35	0
aged-SJF (decay 0.003)	+0.53	0
aged-SJF (decay 0.001)	+0.24	0
FCFS (vLLM default)	0.00	0
aged-SJF (decay 0.01-0.1)	−1.1 to −19.6	1-7
LAS	−41.1	13
SJF (prompt length)	−41.4	14

The aggressive SJF variants earn large gains on some configurations but pile up tail violations and sink overall. The evolved policy tops the table while keeping violations at zero (about 2.5× the runner-up’s score). Evolution found the narrow path where congestion gets cleared without sacrificing either the mean or the tail.

What I Most Want to Write About: Six Failures Before the Win

This policy was not born in one attempt. The first run (run1) dominated its training windows — and went 0 for 6 on unseen data. Six rounds of diagnosis and correction followed, and every failure fed into the next design:

1. Cliff-shaped penalties breed risky candidates. Individuals evolve to skate right along the constraint boundary → start the penalty earlier than the judgment line, with a continuous gradient.
2. Constants written in absolute seconds get locked to the training window’s characteristics. → Replace thresholds with relative, observed quantities.
3. Add a verification gate. If the best selection candidate misses the bar, the run honestly records “did not reach” and goes no further.
4. Diversify training windows by the distribution of winners, not by count — choose windows so that different load conditions favor different classics.
5. “Pick the strongest classic per configuration, in hindsight” turned out to be a baseline that cannot actually be deployed. Production runs one single policy, so the contest was redefined as “one policy’s total over 16 configurations” — this redefinition was the breakthrough.
6. Double the penalty gradient and re-evolve → final judgment: 15/16 wins.

Winning in simulation and collapsing on hardware is the norm — Part 3 measured that firsthand. This time, the lessons from Part 3 — matching the simulator’s behavior to the real engine, finding the knee, and removing measurement contamination (prefix caching disabled) — were applied before going to hardware, and the machine reproduced what the simulator predicted.

What It Is Good For

• The TTFT tail (p99) is central to user experience and SLAs in LLM serving. A property like “acts only under congestion, does no harm when idle” feeds directly into deployment decisions.
• The policy is 117 lines of Python (excluding blanks): why it processes requests in this order is readable, auditable, and fixable.
• The system (verifier × evolution × diagnosis) is domain-independent — after cache eviction and prefix caching, the scheduler is the third case.

Honest Notes

• The baseline is vLLM’s default FCFS. Against the strongest classic hand-tuned per configuration in hindsight, the evolved policy is in the same range (6 wins, 2 ties, 8 losses, p=0.79) — I do not claim it beat every classic. The precise claim is: top of the single-policy table with zero tail violations.
• Arrivals are real BurstGPT traces, but load is created by time compression (speedup) — a custom protocol.
• Hardware measurements were taken with prefix caching disabled and request-unique headers, to isolate the scheduling effect.
• The model is 8B on a single GPU (GB10). Whether the results extend to larger deployments is unverified.
• Cost (measured from run logs): six evolution runs including the failures, 310 generations in total, roughly 3,775 candidate programs evaluated. The mutator was gemini-2.5-flash-lite. I have not measured the billed amount, so I will not state one.

Protocol (for Fact-Checking)

• Hardware: NVIDIA GB10 / vLLM / Llama-3.1-8B. 4 trace windows × 2 load levels × 2 repeats = 16 pairs; identical arrival sequences replayed to both policies.
• Final simulator judgment: held-out BurstGPT traces from a different period, summed over 16 configurations, comparing single policies.
• The champions and verifiers from Parts 1-2 are public on GitHub.

---

Next in the series: back to the games — Breakout, where the system scored 6.5× a naive tracking policy and discovered the tunnel strategy on its own. Back to the project overview.