Multi-Tenant LLM Serving in Production: Fair-Share Scheduling, Dynamic KV Cache Quotas, and Noisy Neighbor Isolation

Operating a shared, multi-tenant large language model (LLM) serving cluster differs fundamentally from traditional stateless web tier hosting. In conventional microservices, tenants consume CPU cycles and static memory footprints in predictable, linear increments. In LLM serving, however, requests exhibit severe non-uniformity across multiple competing hardware dimensions: compute-bound prefill operations, memory-bandwidth-bound autoregressive decoding, and persistent High-Bandwidth Memory (HBM) allocations for Key-Value (KV) caches.

When multiple internal teams or external API customers share a cluster of GPU instances without dedicated tenant isolation, naive first-come-first-served (FCFS) schedulers fail. A single tenant issuing large batch prompt evaluations or generating thousands of output tokens can monopolize tensor cores, exhaust GPU HBM, and cause cascading preemption for concurrent users. Solving multi-tenancy in modern inference engines requires fair-share token scheduling, dynamic memory quota boundaries, and side-channel-resistant cache isolation.

The Multi-Dimensional Resource Bottleneck

The fundamental challenge in multi-tenant LLM serving stems from the structural asymmetry of transformer execution phases:

1. Prefill Phase (Compute-Bound): Processing prompt tokens requires dense matrix-matrix multiplications (GEMMs). A burst of long prompts from Tenant A consumes nearly 100% of GPU compute capacity, causing severe Time-to-First-Token (TTFT) degradation for Tenant B incoming queries.
2. Decode Phase (Memory Bandwidth-Bound): Generating tokens sequentially requires loading entire model weights from HBM to SRAM for every single token. Memory bus saturation limits batch throughput and increases Inter-Token Latency (ITL).
3. KV Cache Footprint (HBM Capacity-Bound): Unlike traditional stateless calls, an ongoing LLM generation holds allocated KV cache memory across hundreds of decoding iterations. A tenant sending concurrent 32,000-token queries hoards physical GPU pages, forcing the engine into memory exhaustion.

In standard implementations of vLLM and HuggingFace TGI, the scheduler operates on an FCFS basis. Under high load, this introduces head-of-line (HoL) blocking. If Tenant A floods the request queue with 500 requests, Tenant B latency-critical single request is delayed until Tenant A backlog clears. Furthermore, when KV cache memory fills up, vanilla schedulers preempt active requests arbitrarily, discarding intermediate KV states and forcing expensive recomputations.

Fair-Share Scheduling: Moving Beyond FCFS

To prevent tenant starvation while maximizing GPU utilization, production serving architectures implement fair-share scheduling algorithms designed specifically for token iteration dynamics.

1. Virtual Token Counter (VTC)

Proposed in research on fairness in LLM serving, the Virtual Token Counter (VTC) adapts generalized processor sharing to tokenized workloads. Instead of tracking wall-clock execution time, VTC quantifies resource consumption in normalized token units.

Because prefill tokens and decode tokens impose different computational loads, VTC computes weighted resource usage:

Total Usage = (alpha * Prefill Tokens) + (beta * Decode Tokens)

Here, alpha and beta represent the relative cost coefficients of prefill versus decode iterations. The scheduler maintains a virtual clock for each tenant:

Virtual Time = Total Usage / Tenant Weight

where Tenant Weight reflects priority (e.g., enterprise tier vs. free tier). In each iteration, the engine schedules requests from the tenant with the lowest virtual time. If an aggressive tenant bursts traffic, its virtual clock advances rapidly, allowing lower-volume tenants to immediately jump the queue without being blocked.

2. Deficit Round Robin for Iteration Batches

Locality-aware Fair Scheduling extends Deficit Round Robin (DRR) to continuous batching. Each tenant is allocated a quantum of token credits per round. As the engine forms the next execution batch, it extracts requests from tenant queues until their token deficits are consumed. Unused credits carry over to subsequent rounds, preventing bursty clients from starving steady-state background workloads.

3. Chunked Prefill Integration

Fair scheduling at the queue level is ineffective if a single scheduled request executes an unchunked 64,000-token prefill that blocks the GPU for hundreds of milliseconds. Modern engines employ chunked prefills (such as in Sarathi-Serve and vLLM), dividing large prompt evaluations into discrete token chunks (e.g., 512 or 1,024 tokens) co-scheduled alongside active decode tokens. This enforces bounded iteration times, ensuring high-priority tenant decodes maintain strict ITL guarantees.

Dynamic KV Cache Quotas and Preemption Isolation

Because GPU memory is finite, multi-tenant architectures must enforce memory boundaries to prevent noisy neighbors from triggering system-wide out-of-memory (OOM) evictions.

Soft vs. Hard Memory Watermarks

Production clusters partition physical PagedAttention KV cache pools using dynamic watermarks:

• Hard Quotas: Allocate a fixed maximum percentage of physical KV blocks to each tenant. While hard quotas guarantee absolute isolation, they reduce global memory efficiency by stranding idle capacity when low-volume tenants are inactive.
• Dynamic Soft Quotas with Eviction Priorities: Tenants are assigned soft target allocations (e.g., 25% of total pool). When total memory utilization is below a safety threshold (e.g., 80%), tenants can burst into unallocated memory. When aggregate memory reaches saturation, the scheduler selects eviction candidates exclusively from tenants exceeding their soft quota.

+---------------------------------------------------------------+
| GPU High-Bandwidth Memory (HBM) KV Cache Pool (e.g., 64 GB)   |
+-------------------------------+-------------------------------+
| Tenant A (Allocated: 45%)     | Tenant B (Allocated: 25%)     |
| [Over-Quota: Eviction Target] | [Within Guaranteed Quota]     |
+-------------------------------+-------------------------------+
| Shared Dynamic Buffer (15%)   | Reserved System Headroom (15%)|
+-------------------------------+-------------------------------+

Preemption Mechanics: Recompute vs. Swapping

When memory pressure forces preemption, the engine can either swap KV blocks to host CPU memory via PCIe or abort the sequence and recompute tokens later.

In a multi-tenant environment, swapping introduces PCIe bus contention that can degrade throughput for other tenants. As demonstrated in FastServe, fine-grained iteration-level preemption paired with token-budgeted recomputation avoids memory bus saturation while maintaining isolation guarantees.

Cross-Tenant Prefix Caching and Security Side Channels

Prompt caching (using Radix trees in engines like SGLang and vLLM) delivers 2x to 5x throughput gains by reusing KV blocks across identical prompt prefixes. However, in multi-tenant environments, global prefix sharing introduces severe security vulnerabilities.

Timing Side-Channel Attacks: PROMPTPEEK

Recent security research on PROMPTPEEK demonstrated that shared KV caches expose timing side channels. An adversary sharing a cluster with other tenants can issue crafted probe prompts and measure TTFT variations with millisecond precision:

• A near-zero TTFT indicates a cache hit, confirming that another tenant recently processed identical prefix text (such as confidential system prompts, sensitive customer IDs, or proprietary source code).
• By iteratively appending candidate tokens and monitoring TTFT drops, an attacker can reconstruct private prefix contexts across tenant boundaries.

Adversary Query:   "Confidential Record ID: 9841..." --> TTFT: 12ms (Cache Hit)
Adversary Query:   "Confidential Record ID: 9842..." --> TTFT: 145ms (Cache Miss)
Result: Attacker infers Tenant B queried Record ID 9841.

Mitigation Strategies

To maintain cache efficiency without compromising tenant confidentiality, production platforms implement layered isolation:

1. Namespace-Isolated Radix Trees: Prefix cache nodes are keyed by a composite hash of Tenant ID, Organization Salt, and Token Hash. KV blocks are never shared across organizational boundaries, eliminating cross-tenant timing attacks.
2. Selective Public Cache Promotion: Systems like SafeKV verify and whitelist globally immutable system prefixes (e.g., public base model system templates) for shared reuse while restricting dynamic user prefixes to private per-tenant partitions.
3. Synthetic Latency Normalization: Artificially clamping minimum TTFT responses prevents micro-architectural timing variance from leaking cache residency status.

Two-Tier Architecture: Gateway Admission Control and Engine Scheduling

Achieving robust multi-tenancy requires coordinating two distinct layers: an external API Gateway and an internal Engine-Level Scheduler.

[ Client Requests ]
        |
        v
+-----------------------------------------------------------------+
| Layer 1: API Gateway (Stateless Admission Control)             |
| - Tenant Authentication and Role Identification                 |
| - Token Bucket Rate Limiting (RPM, TPM, Max Concurrent Tokens)  |
| - Dynamic Request Queueing and Tenant Quota Enforcement         |
+-----------------------------------------------------------------+
        |
        v (Dispatched Requests)
+-----------------------------------------------------------------+
| Layer 2: LLM Engine Scheduler (Stateful GPU Iteration Control)  |
| - Virtual Token Counter (VTC) Fair-Share Queue                  |
| - Chunked Prefill and Continuous Batching Orchestrator          |
| - Tenant-Partitioned PagedAttention KV Memory Manager           |
| - Isolated Radix Cache Namespaces                               |
+-----------------------------------------------------------------+

Layer 1: API Gateway Admission Control

The gateway intercepts incoming HTTP/gRPC requests before they reach the GPU cluster. It enforces:

• Tokens-per-Minute (TPM) and Requests-per-Minute (RPM): Leaky-bucket algorithms throttle sustained over-consumption.
• Concurrent Active Token Limits: Gating requests based on estimated prompt length plus requested max_tokens prevents memory oversubscription before requests enter GPU queues.
• Priority Tiering: Routing requests into distinct priority tiers (e.g., Tier-1 Interactive vs. Tier-2 Batch vs. Tier-3 Background).

Layer 2: Engine-Level Iteration Scheduling

The GPU runtime scheduler manages iteration-level execution across active batches:

• Dynamically selects candidate requests using weighted fair queuing (WFQ).
• Enforces chunked prefill budgets to guarantee sub-50ms iteration steps.
• Manages PagedAttention physical block allocations and executes targeted preemption against over-quota tenants during memory spikes.

Architectural Approaches and Trade-Offs

Production teams typically evaluate four deployment configurations:

• Vanilla FCFS (Global Shared Pool): Maximizes raw GPU utilization with zero scheduling overhead, but offers no TTFT/ITL isolation and exposes tenants to timing side-channel leaks.
• Static Hardware Partitioning (Dedicated GPU Instances or MIG): Provides absolute tenant isolation and deterministic latency, but causes high GPU underutilization and expensive stranded memory.
• Virtual Token Counter (VTC) with Global Cache: Delivers high token throughput and equitable queueing under burst loads, but remains vulnerable to cross-tenant cache probing unless namespaced.
• Two-Tier Architecture (Gateway Token Buckets + VTC Scheduler + Namespaced KV): Delivers optimal cluster utilization, strict SLO enforcement, and cryptographic tenant isolation at the cost of higher control-plane complexity.

Summary and Implementation Priorities

Deploying multi-tenant LLM infrastructure requires balancing resource utilization against strict isolation boundaries:

1. Replace FCFS with Fair Queuing: Transition engine scheduling to Virtual Token Counter (VTC) or Deficit Round Robin (DRR) to prevent bursty tenants from inducing queue starvation.
2. Implement Chunked Prefills: Enforce strict prompt chunking budgets (e.g., 512 tokens) to eliminate TTFT spikes caused by massive single-request matrix multiplications.
3. Enforce Soft KV Quotas: Partition PagedAttention memory pools dynamically, targeting over-quota tenants first when memory pressure necessitates sequence preemption.
4. Isolate Cache Namespaces: Enforce tenant-salted prefix hashing to protect proprietary context against timing-based side-channel reconstruction.

Sources

• Fairness in Serving Large Language Models (Sheng et al., 2024)
• FastServe: Iteration-Level Preemptive Scheduling for Large Language Model Serving (Wu et al., 2023)
• Locality-aware Fair Scheduling in LLM Serving (Zhang et al., 2025)
• Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al., 2023)
• Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve (Agrawal et al., 2024)
• PROMPTPEEK: Prompt Leakage via KV-Cache Sharing in Multi-Tenant LLM Serving (NDSS 2025)
• Selective KV-Cache Sharing to Mitigate Timing Side-Channels in LLM Inference (Ye et al., 2025)
• LLM Serving Fairness: No More Noisy Neighbors (Cohere Engineering, 2025)