The Invisible Tax on Short LLM Requests

The Invisible Tax on Short Requests

Somewhere in a data center, a user asks a large language model to summarize a paragraph. Three sentences in, the model finishes. But the request has been sitting in a batch with a far longer query — one that demands fifty times more computational resources. And so the short request waits, its GPU time dominated not by its own modest workload, but by the towering presence of its batchmate.

This is the batching externality: a quiet inefficiency baked into how modern AI systems process requests. And it turns out to matter enormously — not just for latency, but for money.

The argument unfolds like this: Commercial LLM providers charge per token. A short response generates less revenue than a long one. But when short and long requests share a GPU batch, they share a computational fate — the batch runs at the speed of the longest request. The short request pays in GPU time what it does not recover in token-metered revenue. It is, in economic terms, cross-subsidized.

A new paper from Dayi Yao at the University of Washington and Zijie Zhou at HKUST names this problem precisely and proposes a solution. Their work formalizes the batching externality as a resource-fairness problem, designs an algorithm that constrains it, and proves that the algorithm retains high throughput while doing so. The results sit at the intersection of systems engineering, operations research, and the economics of AI infrastructure — and they offer a principled framework for anyone building or operating LLM services at scale.

The Mechanics of LLM Inference

To understand the problem, you need to understand how these models actually work. When you send a prompt to an LLM, the request moves through two phases.

The first is the prefill phase: the model processes your input tokens all at once, building up a key-value (KV) cache that stores the attention patterns for everything you've said. This is fast — the entire context is processed in a single forward pass.

The second is the decode phase: the model generates output one token at a time, autoregressively. Each new token requires a fresh forward pass that reuses the full KV cache from all previous tokens. This is slow, and it gets slower as the response grows longer. Every step must attend to every token generated so far; the compute and memory per step scale with accumulated context length.

Modern serving systems like vLLM and Orca exploit this structure by batching requests together during the decode phase. If five users are all waiting for tokens, the GPU can process them simultaneously — running one matrix multiplication that generates the next token for all five requests at once. This batching dramatically improves GPU utilization. Without it, most cores would sit idle while waiting for any single request to produce its next token.

But batching introduces a subtlety. The per-step computation is not additive across requests. The attention operation scales with the largest KV cache in the batch, not the sum. The feed-forward layers load projection matrices once for the entire batch regardless of how many requests share it. In hardware terms, the wall-clock time for a batch step is governed by whichever request has the most tokens generated so far.

This means a short request co-batched with a long one pays a latency tax. Its per-step cost is inflated by its batchmate's accumulated context. It receives tokens at a rate determined by someone else's workload.

The phenomenon is not hypothetical. Prior work (Sheng et al., 2024; Khan et al., 2024; Wei et al., 2025) has measured lower GPU utilization during decode, documented sensitivity to sequence length, and identified benefits from uniform micro-batches. What Yao and Zhou provide is a formal treatment — a mathematical framework that makes the externality precise and tractable.

A Fairness Constraint for Batched Inference

The core insight is that the batching externality can be controlled by bounding the heterogeneity of requests in any given batch. If all co-batched requests have similar KV-cache footprints — meaning they have generated similar numbers of output tokens — then no request is subsidizing another to a large degree. The largest footprint in the batch is close to everyone's footprint.

This leads to a fairness constraint. At any scheduling step, let $S(t)$ denote the set of requests in the active batch, and let $a_i(t)$ denote how many tokens request $i$ has generated so far. The constraint is:

$$\underset{i\in S^{(t)}}{\max }\{a_i^{(t)}\}-\underset{i\in S^{(t)}}{\min }\{a_i^{(t)}\}\le \alpha$$

In words: the gap between the most-advanced and least-advanced request in a batch cannot exceed $\alpha$ tokens. The parameter $\alpha$ is a resource-homogeneity budget — a dial the operator can turn to control how unfair batching is allowed to become.

When $\alpha$ is very small, the scheduler must form batches where everyone is nearly at the same stage of generation. This tightens cost alignment but restricts batching flexibility — the scheduler may struggle to fill batches with sufficiently homogeneous requests. When $\alpha$ is large, the constraint becomes loose, and the scheduler can approach the efficiency of unrestricted batching.

The formulation is elegant because it converts an ethical concern — fairness — into an operational control. This is not about equal outcomes or egalitarian welfare. It is about limiting a specific technical externality: the degree to which a request with a small resource footprint is processed in a batch whose resource profile is dominated by larger requests.

The Scheduling Model

Yao and Zhou model the problem as follows. A single GPU worker receives $n$ requests, each characterized by $o_i$ — the total number of tokens (input plus output) for request $i$. The worker processes tokens one at a time, advancing each request by one token per scheduling step. At each step, it can include at most $B$ requests in the active batch, where $B$ is the batch size (typically 16 or 32 on modern hardware).

The objective is throughput: the total number of tokens processed per unit time. Since the total token workload ${\sum }_i{o}_i$ is fixed for a given instance, maximizing throughput is equivalent to minimizing the makespan — the total time to complete all requests.

The scheduler faces two constraints: the capacity limit $|S(t)|\le B$ and the fairness bound $\max (a_i)-\min (a_i)\le \alpha$. The problem is NP-hard (Proposition 2.1), which motivates the design of approximation algorithms with provable performance guarantees.

To evaluate an algorithm, Yao and Zhou use the competitive ratio: the worst-case ratio of the algorithm's throughput to the optimal throughput achievable by any fair schedule. A ratio of 1 means the algorithm is always optimal; a ratio of 0.75 means the algorithm is guaranteed to achieve at least 75% of optimal throughput on every possible instance.

The authors assume that output token lengths $o_i$ are known at the time of admission — a standard assumption in offline scheduling that allows clean theoretical analysis. They later relax this in Section 3.4, extending the algorithm to the non-clairvoyant setting where only prediction intervals are available.

Two Scheduling Policies

The paper introduces two algorithms, presented in order of increasing sophistication.

Longest Job First (LJF) is the simpler baseline. It operates in discrete batches: select the $B$ longest requests from the queue, process them together, wait for the longest in the batch to finish, then select the next $B$ longest. LJF is provably fair — because all requests in a batch start together, their decode progress is identical at every step, satisfying the constraint for any $\alpha >0$. It is, in the authors' words, "universally fair."

But LJF pays a steep price for this fairness. Because it waits for the longest request in each batch to complete before admitting new requests, it leaves GPU slots idle while short requests finish. The algorithm sacrifices batching flexibility entirely in pursuit of homogeneous batches. As Theorem 3.3 establishes, LJF's competitive ratio is at least $\frac{B}{2B-1}$ — which converges to 0.5 as batch size grows. For $B=32$, this guarantees no worse than about 51.6% of optimal throughput, which is a significant bound to leave on the table.

The paper's main contribution is the Insert-Short-Jobs-with-Limit (ISJL) algorithm, a parameterized hybrid policy that explicitly trades off fairness and throughput. ISJL works by maintaining a batch of long requests, but allowing shorter requests to be inserted when they satisfy the fairness constraint — specifically, when their current decode progress is within $\alpha$ tokens of the batch's longest request. The key innovation is that ISJL admits new requests continuously, as slots free up, rather than waiting for an entire batch to finish. This preserves batching flexibility while still respecting the resource-homogeneity budget.

The algorithm's behavior can be understood through the "insert" metaphor. The scheduler keeps the batch populated with long requests, the backbone of efficient throughput. Into the gaps — when shorter requests have advanced enough to satisfy the fairness bound — it inserts smaller jobs. A short job cannot be inserted too early, because its small KV cache would violate $\alpha$; it must wait until it has caught up sufficiently. A long job cannot be inserted too late, because the batch would lose its efficiency advantage.

ISJL is not a brute-force heuristic. It is designed with the theoretical structure of the problem in mind, and its performance can be rigorously bounded.

The 3/4 Competitive Ratio

The paper's central theoretical result is a proof that ISJL achieves a competitive ratio of at least $\frac{3}{4}$ for any batch size $B\ge 2$. This means ISJL is guaranteed to achieve at least 75% of optimal throughput on any instance, regardless of request sizes or arrival patterns, while always satisfying the fairness constraint.

The proof distinguishes two adversarial strategies that could cause ISJL to underperform. An over-inserting adversary tries to make ISJL fill batches too aggressively with short jobs, causing idling when no requests satisfy the fairness constraint. An under-inserting adversary tries to make ISJL keep too many long jobs waiting, reducing batch fullness. The analysis shows that neither adversary can drive the competitive ratio below $\frac{3}{4}$.

This result is tight: the paper provides instances where ISJL achieves exactly the bound. But it is also a floor, not a ceiling. On typical workloads, ISJL performs far better than its worst-case guarantee — often achieving 90% or more of optimal throughput while maintaining fairness.

The paper further characterizes how the competitive ratio varies with the fairness budget $\alpha$. Let $\gamma =\alpha /o_1$ denote the normalized fairness parameter, where $o_1$ is the length of the longest request. As $\gamma$ varies from 0 to 1, the competitive ratio takes the piecewise form:

$$CR(\gamma )=\{\begin{array}{ll}\frac{1+\gamma }{1+2\gamma }& 0<\gamma \le \frac{1}{2}\\ \frac{2-\gamma }{3-2\gamma }& \frac{1}{2}\le \gamma <1\end{array}$$

This function is strictly decreasing on $(0,\frac{1}{2}]$, strictly increasing on $[\frac{1}{2},1)$, and attains its unique minimum of $\frac{3}{4}$ at $\gamma =\frac{1}{2}$. As $\gamma$ approaches 0 or 1, the competitive ratio approaches 1.

The intuition is this: when $\alpha$ is very small, the fairness constraint is tight, and ISJL cannot insert many short jobs — it behaves more like LJF, sacrificing throughput. When $\alpha$ is very large, the constraint becomes irrelevant, and ISJL approaches unrestricted batching, recovering optimal throughput. The worst case occurs in the middle, where the constraint is active enough to limit flexibility but loose enough to admit tricky adversarial sequences.

Figure 4 from the paper illustrates this U-shaped curve. The x-axis shows $\gamma$ from 0 to 1; the y-axis shows the competitive ratio from 0.7 to 1. The curve dips to 0.75 at the center and rises toward 1 at both extremes, confirming that ISJL's performance degrades gracefully from either direction.

What Happens When You Don't Know Output Lengths

The analysis so far assumes the scheduler knows each request's total token count $o_i$ upfront. This is standard in offline scheduling theory but unrealistic in practice — a user submits a prompt, and the model generates a response of unknown length. The paper addresses this gap with the Robust-ISJL algorithm, which enforces the fairness constraint using only observed runtime progress, requiring no knowledge of true output lengths.

Robust-ISJL works by tracking each request's current decode progress (how many tokens have been generated so far) rather than its remaining work. When a request has advanced to within $\alpha$ tokens of the batch's most-advanced request, it is eligible for insertion — regardless of whether it is actually finished. If the request turns out to be longer than expected, it simply continues in the batch; if shorter, it exits earlier without disrupting the constraint.

The theoretical guarantee for Robust-ISJL degrades gracefully with prediction error. If the scheduler has accurate predictions of output length, it recovers exactly the $\frac{3}{4}$ bound. As predictions become less reliable, the worst-case competitive ratio worsens, but smoothly — the algorithm does not collapse catastrophically when estimates are noisy.

This extension is important for deployment. Real LLM serving systems receive prompts of unknown length and must generate responses of uncertain duration. Robust-ISJL shows that the fairness constraint is practically enforceable without perfect foresight.

The Economics of Token-Metered Pricing

So far, the analysis has focused on throughput — a systems metric. The second half of the paper connects scheduling to the economics of commercial LLM APIs, where providers charge per token. This creates an interesting divergence.

Revenue under token-metered pricing is additive: each request generates $p_0\cdot o_i$ revenue, where $p_0$ is the per-token rate. Total revenue for a fixed set of accepted requests is independent of the schedule — the scheduler cannot affect how much money comes in, only how efficiently it processes the work.

But costs are not additive. The per-step cost of a batch is driven by the maximum KV cache in the batch, not the sum. This means the total inference cost of a schedule has three components:

$$C_{\mathcal{A}}(\mathcal{I})=\tau Q(\mathcal{I})+c{T}_{\mathcal{A}}(\mathcal{I})+\tau E_{\mathcal{A}}(\mathcal{I})$$

The first term, $\tau Q(\mathcal{I})$, is the intrinsic workload cost — the baseline cost of processing the token workload, independent of scheduling. This is unavoidable. The second term, $c{T}_{\mathcal{A}}(\mathcal{I})$, is the time/overhead cost — the cost of keeping the GPU running for the duration of the makespan. The third term, $\tau E_{\mathcal{A}}(\mathcal{I})$, is the batching externality: the schedule-induced excess cost arising from max-driven batch cost.

The fairness constraint directly bounds the batching externality. When the max-min progress gap is at most $\alpha$, no request's cost is inflated by more than $\alpha$ tokens per step. Formally: $E_{\mathcal{A}}(\mathcal{I})\le \alpha \cdot O(\mathcal{I})$, where $O(\mathcal{I})$ is the total token workload. This means tighter fairness translates to tighter cost alignment.

The ISJL throughput guarantee controls the time/overhead component. Since ISJL achieves at least 75% of optimal throughput, its makespan is at most $\frac{4}{3}$ times the optimal fair makespan. This bounds the second cost term.

Combining these bounds yields an additive profit guarantee relative to the optimal $\alpha$-fair profit schedule. The profit from a schedule is revenue minus cost; revenue is fixed for a given workload, so profit differences arise entirely from inference cost. ISJL is guaranteed to achieve a profit within a bounded factor of the best possible fair schedule.

Figure 5 from the paper visualizes this cost decomposition. The chart shows three stacked components across different scheduling policies: intrinsic workload cost (the baseline), time/overhead cost (proportional to makespan), and batching externality cost (the schedule-induced excess). FCFS — First-Come, First-Served, the standard policy in deployed systems — has large batching externality because it batches heterogeneous requests without any fairness constraint. LJF has minimal batching externality but suffers high time/overhead cost because its rigid batching strategy leaves GPU slots idle. ISJL sits in the middle: it substantially reduces FCFS's externality cost while preserving much of the batching flexibility that LJF sacrifices.

Figure 6 drills into the profit difference between ISJL and LJF as the per-step overhead $c$ varies. The chart shows that ISJL's profit advantage over LJF is significant across a wide range of overhead values, growing larger as $c$ increases. This matters because per-step overhead — the cost of keeping GPUs running — is a major component of inference expense at scale.

Experimental Results on Real Workloads

The theoretical analysis is complemented by experiments on the LMSYS-Chat-1M dataset, a collection of real-world LLM interactions. Yao and Zhou extract a fixed arrival sequence and evaluate schedulers using throughput and Average End-to-End Latency (AEL) as metrics, with batch sizes $B\in \{16,32\}$ and fairness budgets $\alpha \in \{50,100,150\}$.

The results are consistent with the theory. Across all tested $\alpha$ values, ISJL dominates the baselines, simultaneously increasing throughput and reducing AEL. The parameter $\alpha$ offers a tunable trade-off: smaller $\alpha$ tightens fairness (reducing batching externality) at the cost of slightly lower throughput; larger $\alpha$ relaxes fairness while approaching unrestricted batching efficiency.

These experiments confirm that ISJL delivers balanced performance in practice — not just in worst-case analysis, but on realistic, heterogeneous workloads with varying request sizes and arrival patterns.

Why This Matters

The paper's contribution is several-layered.

At the systems level, it provides a principled framework for thinking about fairness in batched inference. The batching externality has been observed anecdotally and measured empirically, but Yao and Zhou make it formal. By defining fairness in terms of resource consumption — specifically, the disparity in KV-cache footprints — they translate an intuitive concern into a tractable optimization constraint.

At the algorithmic level, ISJL offers a concrete scheduling policy with rigorous guarantees. The $\frac{3}{4}$ competitive ratio is a worst-case floor, not a typical performance, and the experiments confirm that ISJL performs well on real data. The extension to Robust-ISJL addresses a practical concern: real systems don't know output lengths in advance. That the algorithm degrades gracefully under prediction error is important for deployment.

At the economic level, the paper connects scheduling to pricing in a way that clarifies the incentive structure. Token-metered contracts are exogenous — they reflect market conditions and business strategy, not scheduling decisions. But understanding how scheduling affects inference cost under these contracts is essential for operators who want to align their operational expenses with their revenue. The cost decomposition and the externality bound give operators a tool for reasoning about the profit implications of different scheduling policies.

The analysis is also a reminder that efficiency and fairness are not always in tension — sometimes they can be aligned. The batching externality is inefficient by design: it wastes GPU resources on requests that don't need them. Constraining this externality through fairness does not merely redistribute resources; it reduces the total amount of resource misallocation.

Open Questions and Limitations

The paper is careful to acknowledge its scope. The model assumes a single computational worker, while production LLM serving typically distributes requests across clusters of GPUs. The analysis is offline in its main formulation, assuming knowledge of request sizes, though the non-clairvoyant extension partially addresses this. The demand model treats customer acceptance as exogenous — the results quantify cost alignment under a fixed pricing environment, not endogenous pricing or demand response.

These are natural directions for future work. Extending the analysis to multi-worker settings, designing online algorithms with tighter competitive ratios, and incorporating demand models where pricing affects request arrival rates would each extend the framework. The authors note that ISJL's behavior in adversarial arrival settings is already characterized; the online version, where requests arrive dynamically rather than being known upfront, remains an open problem.

There is also a systems dimension that the paper does not fully explore. The KV-cache footprint proxy used in the analysis assumes that memory scales linearly with decode progress. In practice, attention patterns, prefix caching, and speculative decoding introduce nonlinearities that complicate the resource model. The abstraction is clean and theoretically tractable, but its fidelity to deployed hardware is a question for future empirical investigation.

A Framework for Fair Inference

LLM serving is infrastructure. As these models become the foundation of search, coding assistants, customer service, and decision-support tools, the efficiency of inference systems becomes a matter of economic significance — and a matter of who bears the cost of computational resources.

The batching externality is, in some sense, a hidden tax on short requests. A user who asks a simple question pays in GPU time for the privilege of sharing a batch with users who ask complex ones. This is not a moral failing of any individual system; it is an emergent property of maximizing throughput without regard for resource allocation. The problem becomes more acute as GPU time becomes more expensive and request distributions become more heterogeneous.

Yao and Zhou's framework does not eliminate this tension. It makes it explicit, controllable, and optimizable. By treating fairness as a parameter — by allowing operators to choose $\alpha$ based on their business objectives — the model converts an ethical question into an engineering decision. The question is not "Should we be fair?" but "How much unfairness can we tolerate, and what does it cost us to reduce it?"

ISJL offers an answer: it costs you at most 25% of your optimal throughput in the worst case, and typically much less. In return, you get batching behavior that aligns computational cost with token-metered revenue. For operators building LLM infrastructure, this is a trade-off worth understanding.

The bigger lesson may be structural. LLM inference is a domain where the gap between mathematical abstraction and physical reality is unusually small. The KV-cache footprint is both a theoretical construct and a direct proxy for GPU memory usage. The batching externality is both a scheduling artifact and a measurable source of computational waste. Papers like this one narrow the gap between theory and practice — not by simulating reality, but by modeling it with enough precision to reason about solutions rigorously.

The invisible tax on short requests is now visible. What we do with that visibility is the next question.