Multi-Tenant LLM Inference Fair Scheduling in Production: Taming Noisy Neighbors with Token Cost Accounting, VTC, and Priority Lanes

Why Shared GPUs Expose Fairness Issues Before Throughput Problems

When an enterprise connects multiple applications, departments, or customer tenants to a shared LLM inference cluster, the most common first-generation governance approach is “each tenant gets at most N requests per second.” This works reasonably well for typical HTTP services, but it’s insufficient for LLMs.

The reason is straightforward: one request does not equal a fixed cost. A Q&A request with 200 input tokens and 50 output tokens, and an analytics request with a 20K context that generates 2K more tokens, both get counted as “1” by a QPS counter. If a tenant keeps submitting long-context or long-generation tasks, it can easily consume the majority of GPU service time without ever violating a request-count limit.

The OSDI 2024 paper Fairness in Serving Large Language Models starts from exactly this problem: LLM request lengths are unpredictable, and inference engines dynamically co-schedule multiple requests, so traditional notions of fairness based on request counts or fixed time slices don’t apply. The paper defines service amount using a cost function that accounts for input and output tokens, and proposes the Virtual Token Counter (VTC) for work-conserving fair scheduling.

Microsoft Research’s FairServe goes further, drawing on real multi-tenant workloads to show that different applications not only differ in token lengths but may also trigger different numbers of LLM calls per business request. Production governance therefore needs to combine throttling, service cost metering, and scheduling — not just bolt a QPS limiter onto the entry point.

Core Principle: Fairness Should Target “Consumed Service Amount”

Production systems need to distinguish three concepts that are often conflated:

Concept	Meaning	Problem It Solves
Quota	Maximum resources a tenant can use in a time window	Prevents a single tenant from consuming without bound
Priority	Which business tier should execute first under contention	Expresses business-tier ordering
Fairness	How multiple active tenants share service capacity per agreed shares	Share fairness under shared capacity

These three cannot substitute for one another.

Replace Pure Request Counting with Token Cost Accounting

The simplest production-ready service cost model can be written as:

service_cost = a * prompt_tokens + b * completion_tokens

Here a and b are the platform’s own metering coefficients. This isn’t an exact GPU cost model; it’s a consistent approximation for scheduling and quota purposes. Real compute costs aren’t perfectly linear across models, hardware, and context lengths, so production should keep the “fairness metering unit” separate from the “financial billing unit.”

If your system can already access the usage at request completion, use “estimate at enqueue + calibrate at completion”:

estimated_cost = prompt_tokens + expected_output_tokens
actual_cost = prompt_tokens + completion_tokens
debt_delta = actual_cost - estimated_cost

The estimate drives admission and queuing; the actual value corrects the tenant’s service counter. This way you don’t need to know the exact output length before generation finishes, and you avoid systematically underestimating large generation requests.

VTC’s Key Value: Don’t Waste Idle Capacity

A common problem with fixed quotas: when tenant A has no traffic today, its quota can’t be temporarily used by tenant B. The GPU sits idle while B is still throttled.

The value of work-conserving scheduling methods like VTC is that they allow other active tenants to keep consuming when idle resources exist, while restoring fairness based on each tenant’s already-received service when multiple tenants have sustained backlogs.

Production implementations don’t need to transplant the research algorithm verbatim into the model engine. A more realistic approach is to maintain per-tenant virtual service counters in the gateway or a standalone scheduler:

def choose_tenant(backlogged_tenants):
    return min(backlogged_tenants, key=lambda t: t.virtual_service / t.weight)

def on_request_finished(tenant, prompt_tokens, completion_tokens):
    cost = prompt_tokens + completion_tokens
    tenant.virtual_service += cost

This pseudocode captures the core idea: prefer the tenant that has received the least service on a normalized basis. In production you’ll also need to handle new tenant joins, counter alignment after long idle periods, request cancellation, streaming generation, weight changes, and cross-replica state synchronization.

Priority Is Not Fairness: Keep the Two Scheduling Layers Separate

vLLM currently supports fcfs and priority scheduling policies, and requests can carry priority via the priority field or the X-Vllm-Priority header — lower values are processed earlier.

This is great for implementing QoS lanes like “online chat beats offline summarization” or “paid interactions beat background batch jobs,” but don’t treat it as tenant fair scheduling. For example:

P0: interactive-critical
P1: interactive-standard
P2: async-batch

The correct composition is:

Select Priority Lane by business tier
    ↓
Within the same Lane, apply Weighted Fair Scheduling / VTC across tenants
    ↓
Pick the request
    ↓
Map to a priority the model engine understands

With only strict priority and no intra-lane fairness, a high-priority tenant that keeps sending requests can still starve other tenants in the same tier. With only fair scheduling, you can’t express business priorities like “interactive critical must precede nightly batch summarization.”

A Production-Ready Multi-Tenant Inference Scheduling Pipeline

Here’s a recommended five-layer decomposition of responsibilities.

1. Tenant Identity: Make Tenant Identity a Hard Constraint

Once a request enters the inference gateway, you must first resolve a stable identity:

tenant_id  application_id  service_tier  model  request_id

Don’t trust client-supplied priority. Priority should be mapped by the platform based on tenant, product plan, and business scenario — otherwise callers can mark every request as highest priority.

2. Admission: Decide “Can This Enter the Queue?”

The admission layer enforces hard boundaries:

• Maximum concurrent requests;
• Maximum queue depth;
• Per-minute / per-hour token budget;
• Per-request max input and max output;
• Tenant burst budget;
• Degradation or rejection policy under global overload.

This layer answers “we can’t let one tenant enter the system without bound” — it’s not the final fairness ordering.

3. Fair Queue: Maintain Per-Tenant Service Debt

Create one logical fair queue per model + priority_lane, and within that queue select the next batch of schedulable requests by tenant. Tenant state should include at least:

tenant_id: tenant-a
weight: 2
virtual_service: 183420
queued_requests: 12
estimated_queued_tokens: 9450
running_requests: 3
token_budget_remaining: 280000

weight can map to plan tier or internal business weight. A weight of 2 doesn’t mean “always twice as fast as weight 1”; it means a higher target service share under sustained contention.

4. Engine: Map Platform Decisions to vLLM and Other Inference Engines

If the engine supports request priority, map the platform’s lanes to engine priority. vLLM’s current docs explicitly support --scheduling-policy priority, and the OpenAI-compatible API supports request-level priority.

But the platform should still maintain its own tenant-level queuing and metering. The engine sees “requests”; the platform sees “tenants, plans, budgets, applications, and business SLAs.”

The Kubernetes Gateway API Inference Extension also introduces abstractions like serving priority, InferencePool, and Endpoint Picker at the inference gateway layer, showing that more scheduling decisions are moving from plain L7 load balancing toward inference-aware routing. These capabilities are well-suited for endpoint selection, while tenant fairness policy should remain explicitly controlled by the platform policy layer.

5. Metering: Write Back Actual Service Amount on Completion

After each request completes, is cancelled, or times out, record at minimum:

{
  "tenant_id": "tenant-a",
  "model": "qwen3-32b",
  "priority_lane": "interactive-standard",
  "prompt_tokens": 1820,
  "completion_tokens": 436,
  "queue_ms": 84,
  "ttft_ms": 312,
  "e2e_ms": 2410,
  "finish_reason": "stop"
}

The scheduling system’s most important output isn’t per-request logs — it’s per-tenant aggregations of:

• service_tokens / minute
• queued_tokens
• running_tokens
• p95 queue time
• p95 TTFT
• throttled_requests
• rejected_requests
• fairness debt
• budget utilization

Only with these can you tell whether “slowness” comes from the model itself, queue contention, or a specific tenant continuously consuming shared capacity.

Production Recommendation: “Dual Budget + Fair Queue”

A single token bucket struggles to satisfy both burst tolerance and long-term fairness. A more practical approach uses two budgets:

Short-cycle Burst Budget: e.g., control short bursts over 10 seconds or 1 minute to prevent instantly saturating the queue.

Long-cycle Sustained Budget: e.g., control cumulative token usage over 1 hour or 1 day to prevent a tenant from persistently over-consuming.

On top of both, let VTC / weighted fairness decide how requests already admitted to the system share current GPU capacity. The three layers are thus clear:

• Rate Limit / Quota: the maximum you can use;
• Fair Scheduler: how to divide when everyone needs it;
• Priority Lane: which business tier goes first.

Which Scenarios Fit This Approach Best

First: internal shared model platforms. When dev assistants, customer service, knowledge Q&A, and batch jobs share GPUs, QPS differences don’t represent real cost.

Second: SaaS multi-tenant model services. Different customer plans need different resource weights, but the platform wants idle capacity to be fully utilized by other customers.

Third: agent platforms. A single user action can trigger multiple model calls, so counting entry HTTP requests severely underestimates actual inference service volume. FairServe’s discussion of “different LLM call counts across applications” is especially worth studying.

Fourth: mixed online and offline workloads. Priority lanes matter here, but you still need fairness within each lane to avoid noisy neighbors inside the high-priority pool.

Common Pitfalls

Pitfall 1: “10 QPS per tenant is fair.” No. Request lengths, generation lengths, and the number of model calls per business operation can all differ. QPS only expresses request frequency, not actual service volume.

Pitfall 2: Charging quota directly by max_tokens. max_tokens is a ceiling, not actual generation. Billing by the ceiling systematically penalizes businesses that set large limits but usually stop early. It’s better suited for admission reservation; settle by actual usage at completion.

Pitfall 3: The highest-paying tier always gets the highest priority. Strict priority without starvation protection can leave lower-tier tasks unserved indefinitely. A safer design is “a limited number of lanes + weighted fairness within each lane + capacity protection per lane.”

Pitfall 4: Watching only GPU utilization. High GPU utilization only means the machines are busy, not that tenants are treated fairly. You must also track each tenant’s service share, queue time, rejection rate, and token debt.

Pitfall 5: “Fair scheduling will definitely reduce throughput.” There can be a trade-off between fairness and throughput, but it’s not simply “fair = slow.” VTC is designed to be work-conserving. What you actually need to load-test is whether your queue policy breaks batching, prefix locality, or GPU saturation — not assume fair scheduling is inherently inefficient.

Pre-Launch Checklist

Before going live, at minimum verify:

• Tenant identity can only be written by the trusted gateway;
• Request count, concurrency, and token budget are all limited;
• Prompt tokens can be accurately counted or reliably estimated before enqueue;
• Completion tokens are correctly settled on finish, cancel, and timeout;
• New tenant joins and long idle periods don’t cause “credit hoarding” in virtual counters;
• Weight changes in weighted fairness take effect smoothly;
• Priority lanes have starvation protection;
• Streaming disconnects still release running slots;
• The scheduler has a clear fail-open / fail-close policy on state loss;
• Monitoring exists for per-tenant p95 queue time, TTFT, throttle rate, and token share;
• Mixed load tests cover short requests, long context, long generation, and multi-call agent traffic;
• Fairness policies don’t significantly degrade batching efficiency.

FAQ

Why not just use traditional Weighted Fair Queuing? Traditional network scheduling usually knows packet sizes, but LLM output length is unknown when generation starts, and continuous batching interleaves multiple requests on the GPU. You can borrow WFQ’s “service share” idea, but metering, calibration, and scheduling timing must adapt to token-by-token generation.

Does VTC require modifying vLLM source code? Not necessarily. Research implementations can go deep into the engine scheduler; enterprise platforms more easily implement tenant queues and admission in an external gateway/scheduler, then hand selected requests to vLLM. Only consider moving down to the engine layer if external queuing can’t get fine-grained generation progress or causes significant batching efficiency loss.

Which comes first: quota or fair scheduling? Hard quotas and admission first, then fair scheduling. Without hard boundaries, fair scheduling only decides contention order — it can’t stop misconfigured or malicious tenants from endlessly creating queued requests. With only quotas and no fair scheduling, shared-capacity contention will produce unstable experiences.

References

1. Ying Sheng et al., Fairness in Serving Large Language Models, OSDI 2024 — https://www.usenix.org/conference/osdi24/presentation/sheng
2. Redwan Ibne Seraj Khan et al., Ensuring Fair LLM Serving Amid Diverse Applications (FairServe), Microsoft Research / arXiv, 2024 — https://www.microsoft.com/en-us/research/publication/ensuring-fair-llm-serving-amid-diverse-applications/ and https://arxiv.org/abs/2411.15997
3. vLLM, OpenAI-Compatible Server — request priority / X-Vllm-Priority — https://docs.vllm.ai/en/latest/serving/online_serving/openai_compatible_server/
4. vLLM, Serve CLI — --scheduling-policy=fcfs|priority — https://docs.vllm.ai/en/latest/cli/serve/
5. Kubernetes SIG Network, Gateway API Inference Extension — Introduction — https://gateway-api-inference-extension.sigs.k8s.io/
6. Kubernetes SIG Network, Gateway API Inference Extension — InferencePool — https://gateway-api-inference-extension.sigs.k8s.io/api-types/inferencepool/