Multi-Tenancy Is a Scheduling Problem
On this page7
Part 5 ended by handing over a question it couldn’t answer: when the pool is full, who gets evicted? That question has no hardware answer. Neither does “whose request runs next”, or “how much of the machine is this tenant entitled to”.
This is the post where the series stops describing a machine and starts writing policy. Everything from here is a decision somebody makes, and the machine will enforce whatever you decide, including nothing.
Continuous batching is the enabling mechanism
Static batching forms a batch, runs it to completion, and starts the next one. Every sequence in the batch finishes when the longest one does.
Static and continuous batching, same four sequences
The waste is obvious once drawn. A slot whose sequence completed in three steps sits idle for five more, holding capacity you are paying for, because the batch is a unit that ends together. With response lengths varying by an order of magnitude between tenants — which is normal — most of the batch spends most of its time waiting on its slowest member.
Continuous batching makes the batch’s composition mutable. Each decode step, finished sequences leave and waiting ones join. No sequence waits on another’s completion.
The throughput win is the usual reason to care. There’s a second consequence that matters more for this post:
The scheduler runs every step
Under static batching, scheduling happens once per batch — a decision made every few seconds. Under continuous batching it happens every decode step, hundreds of times a second.
That reframes what policy is affordable. Per-tenant accounting, fair-share arithmetic, priority comparisons — these have to be cheap enough to run at step frequency, on the host CPU that Part 2 already identified as the thing most likely to starve the accelerator. A fairness algorithm that is correct but slow is not a fairness algorithm you can deploy here.
What “fair” actually means
Everyone agrees the scheduler should be fair. Almost nobody says fair in what unit, and the choices give genuinely different systems.
| Unit | A tenant’s share is | Gameable by |
|---|---|---|
| Requests | equal number of requests | sending fewer, much larger requests |
| Tokens | equal tokens generated | holding long sequences that generate slowly |
| Blocks | equal KV pool footprint | many short-lived sequences that never accumulate |
| Block-seconds | equal pool footprint over time | not much — this is the actual scarce resource |
Requests are the worst unit and the most common one, because they’re what the API counts. A tenant sending one 100k-token request and a tenant sending a hundred 200-token requests are not consuming remotely comparable amounts of machine, and a request-fair scheduler treats them identically.
Block-seconds — pool footprint integrated over time — is the honest unit, because it is what tenants are actually competing for. A tenant holding 40 blocks for 10 seconds has consumed the same scarce thing as one holding 400 blocks for 1 second. It’s also more bookkeeping than the alternatives, which is presumably why it’s rare.
The mechanism to spend it through is not exotic: deficit round robin over block-seconds gives each tenant a quantum per round, lets unused quantum carry forward within a bound, and picks the tenant with the largest deficit. It’s O(tenants) per scheduling decision, which at the step frequency above is the constraint that matters.
Priority tiers, and how they starve people
Tiers are the first thing anyone asks for: paid tenants ahead of free ones, interactive ahead of batch. They’re also the easiest way to build a system that works perfectly in testing and starves someone in production.
Strict priority starves. If a higher tier always wins, and the higher tier has enough traffic to saturate the machine, the lower tier gets nothing — not “less”, nothing, for as long as the load lasts. This is not an edge case; it’s the defined behavior of strict priority under sustained load.
Two ways out, and they compose:
- Aging. A request’s effective priority rises with time spent waiting, so anything eventually reaches the front. Bounds worst-case wait, and blurs the tiers you sold.
- Floors. Each tier gets a guaranteed minimum share it obtains regardless of what higher tiers want — weighted fair share rather than strict ordering. Preserves the tiers as a ratio instead of an ordering.
Floors are what most people actually mean when they say “priority”, and it’s worth catching the difference at design time, because the two behave identically until the machine is saturated, which is exactly when you find out.
Rate limits belong on tokens, not requests
Part 2 put admission control on the host, ahead of everything expensive. What it admits against should be a token budget, not a request count, for the same reason requests are the wrong fairness unit: a request is not a unit of cost.
A token bucket per tenant, refilled at their contracted rate, debited by prompt tokens at admission and generated tokens as they’re produced. Which surfaces the same tension Part 2 flagged and didn’t resolve — you don’t know the token count until you’ve tokenized, and tokenizing is work you’d rather not spend on a request you’re about to refuse. Estimating from byte length is the usual compromise, and it is a compromise.
Choosing who to evict
Part 5’s handover. The pool is full, a request needs a block, something must be reclaimed.
The victim choice is where a scheduler’s values become visible:
- Largest sequence. Frees the most blocks per eviction. Also reliably punishes whichever tenant is doing the most substantial work, which is usually backwards.
- Newest sequence. Preserves work already done, and makes the system unfair to whoever arrived most recently rather than to whoever is consuming most.
- Lowest priority. Respects the tiers, and inherits every starvation problem above.
- Most over fair share. Evicts from the tenant most exceeding its entitlement. The only one of the four whose behavior matches what a fairness policy claims to do, and the only one that requires the accounting from the previous section to already exist.
The failure mode to design against
Evict a sequence, and it gets rescheduled, re-prefills, allocates blocks again, and pressures the pool right back into the state that caused the eviction. Now do that repeatedly.
The machine stays busy and makes no progress — every cycle spends prefill compute re-deriving KV that was just discarded. It looks healthy on throughput (the chip is doing work!) and terrible on every latency percentile, which is a good reminder of why Part 1 refused to let throughput be reported without a latency bound.
The defense is hysteresis: don’t evict unless it frees enough to matter, don’t immediately readmit what you just evicted, and treat repeated eviction of the same sequence as a signal to reject rather than retry.
The three-way fight
Everything in this post pulls on one knob, and the pulls are in different directions.
Throughput wants large batches. More sequences per step amortizes weight reads and keeps the array occupied (Part 3).
Latency wants small batches. Each additional sequence makes every decode step do more work, which widens inter-token latency for everyone in it.
Isolation wants bounded per-tenant footprint, which caps how much of the batch any one tenant may occupy — and therefore caps the batch size available to a tenant with legitimate burst demand.
There is no configuration that maximizes all three. The objective from Part 0 is what adjudicates: maximize tenants served within SLA, which prices latency and isolation explicitly and makes throughput the thing you spend rather than the thing you maximize.
What the hardware has to settle
- Whether block-seconds accounting is cheap enough to run at step frequency, or whether the host cost eats the fairness it buys
- Where the batch-size sweet spot sits for the objective, rather than for throughput alone
- Whether eviction thrash actually shows up under a realistic workload, or only under a deliberately hostile one
- What a genuinely abusive tenant does to the other tenants’ p99 under each policy — the only test of isolation that means anything
Part 7 turns to model-level speedups — speculative decoding, MoE serving, early exit — each of which has to be evaluated against the constraint that has governed every post so far: whatever it wants, it has to fit in the same pool.