Fair Scheduling for Multi-Tenant AI Workloads: Prevent Noisy Neighbors

A queue ordered only by arrival time is fair only when every request costs the same. LLM workloads do not. One tenant can submit long contexts, high output limits, tool loops, and expensive models while another waits for a short classification.

Fair scheduling protects latency and capacity across tenants without pretending every plan or request deserves identical service.

Estimate Work Before Admission

Use a conservative cost unit rather than raw request count. A practical estimate can combine input tokens, reserved output tokens, model weight, tool budget, and concurrency footprint.

function estimatedCost(r: Request) {
  return r.inputTokens
    + r.maxOutputTokens * 1.5
    + r.maxToolCalls * 2_000;
}

The estimate will be imperfect. Record actual cost and recalibrate by model and route. Underestimation creates overload; extreme overestimation wastes capacity.

Reject or defer work before it enters the expensive path. Admission control should check tenant quota, queue depth, deadline feasibility, and global capacity. Return a retry hint or asynchronous job ID rather than allowing an unbounded queue.

Isolate Tenants With Separate Queues

A logical queue per tenant prevents one backlog from occupying every head position. The scheduler chooses among tenant queues, then selects the next request inside the chosen tenant.

Weighted fair queuing gives paid tiers or critical services more share while guaranteeing progress for others. Deficit round robin is easier to implement for variable-cost jobs:

for (const tenant of activeTenants) {
  tenant.deficit += tenant.quantum;
  while (tenant.peek() && tenant.peek().cost <= tenant.deficit) {
    dispatch(tenant.pop());
    tenant.deficit -= job.cost;
  }
}

Large jobs eventually accumulate enough deficit to run, so they do not starve. Cap the maximum request size separately; fairness should not make an unsafe job acceptable.

Combine Tokens and Concurrency Quotas

Token budgets control throughput, while concurrency limits control simultaneous pressure on memory, connections, and downstream tools. Use both.

A token bucket supports bursts: credits refill at a sustained rate up to a cap. Separate buckets for input, output, and expensive models may improve accuracy. Deduct an estimate at admission and reconcile after completion.

Concurrency limits should be scoped per tenant and globally. Reserve a small emergency pool for recovery or human-support workflows so batch traffic cannot block incident handling.

Distributed limiters need an explicit consistency tradeoff. A central store improves coordination but adds latency and dependency risk. Local approximations are faster but may briefly overshoot. Design the global safety margin for that overshoot.

Add Priority Without Starvation

Priority classes are useful for interactive, background, and safety-critical work. Strict priority is dangerous: a continuous stream of high-priority jobs can starve everything below it.

Use weighted shares and aging. A background job waiting beyond a threshold can gain effective priority. Limit how much capacity any priority class can consume, even if its tenant has credits.

Deadlines should influence admission, not automatically jump the line. If a job cannot finish before its deadline, fail fast or offer asynchronous completion instead of wasting capacity.

Apply Backpressure End to End

Scheduler fairness fails if an upstream service continues creating work faster than the system can drain it. Publish queue budgets to producers, cap agent tool loops, and propagate provider 429 responses into admission decisions.

Batch and interactive paths should use different queues. Pause speculative work first. Reduce optional retrieval fan-out or output limits only through a declared degradation policy; silently changing quality can violate the product contract.

Do not retry throttled requests immediately. Use exponential backoff with jitter and charge retries to the originating tenant, otherwise one tenant’s failure storm becomes shared load.

Measure Fairness, Not Just Utilization

High accelerator utilization can coexist with terrible service. Track per tenant and cohort:

• queue delay and end-to-end latency;
• admitted, deferred, and rejected cost units;
• actual-to-estimated cost ratio;
• concurrency and token-share utilization;
• starvation age of the oldest job;
• deadline misses and retry amplification.

Compare achieved service share with configured weight over rolling windows. Investigate tail latency, not only averages. Keep tenant identifiers protected and avoid logging raw prompts.

Failure Modes to Test

Load tests should include one tenant sending maximum-size requests, many small tenants arriving together, provider throttling, limiter-store failure, retries after timeouts, and workers completing after leases expire.

Fail closed for hard cost or safety limits. For soft fairness coordination, a bounded local allowance may preserve availability when the central limiter is unavailable. Document the degraded mode and alert immediately.

Rollout Checklist

1. Define a cost unit and validate it against actual usage.
2. Put tenant work in isolated logical queues.
3. Use weighted deficit scheduling with a starvation bound.
4. Enforce token, request-size, and concurrency limits.
5. Add admission control and honest retry guidance.
6. Separate interactive, batch, and recovery capacity.
7. Propagate backpressure and charge retries correctly.
8. Monitor service share and tail latency per cohort.

Fair scheduling is not equal scheduling. It is a transparent allocation policy that keeps one customer’s success from becoming every other customer’s outage.