Schedulers that do not know how long a job will take usually fall back on its age. A job that has already run a long time gets demoted, on the bet that it will run longer still. For mixed workloads this bet can be catastrophic at the extreme tail. Consider an LLM server where short chats share a GPU with reasoning requests spanning 10 to 10,000 tokens. Within each kind of request, an old job is close to finishing. Pooled together, though, old jobs look like they will never end. A scheduler that demotes by age alone therefore keeps preempting nearly finished jobs, and their 99th-percentile latency explodes. Queueing theory calls such a policy tail-pessimal: it can be excellent on average yet have the worst possible behavior at the extreme tail.
Neuroscience has a name for the cure we propose: feature-tuned inhibition. Cortical circuits do not suppress activity with a global volume knob. They aim suppression at specific feature coordinates, such as one stimulus or one contour configuration, and leave everything else untouched. We claim that tail-pessimality in mixed workloads is largely a blanket-inhibition failure, in which age-based demotion is applied uniformly across job types whose remaining-work profiles differ. The fix is to tune demotion jointly to cheap observable features of a request and to its age. We will make this precise in the M/G/1 queue (one server, random arrivals, general job sizes), characterize when feature-tuned demotion removes pessimality, and test it on LLM serving traces against the strongest current tail-aware scheduler.
Core Claim
The cleanest instance is the hyperexponential distribution. It is a mixture of exponentials, light-tailed but with decreasing hazard, so it lacks the "eventually new better than used in expectation" property. That property says, roughly, that older jobs eventually have no more expected remaining work than new ones.
When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail? proves that without this property the mean-optimal Gittins policy can be tail-pessimal, because it behaves like Foreground-Background (FB), the policy that always serves the least-served job. If the scheduler can see which exponential component a job came from, the picture changes. Each component is memoryless, so the class-conditional Gittins rank does not change with age. Demotion then disappears within a class and survives only across classes. Pessimality in this example is purely an artifact of pooling information, and supplying the class removes it.
We generalize this with a feature-conditioned Gittins rank. Here $x$ is the observable feature vector of a job (prompt embedding, request type, or an internal probe signal), $a$ is its attained service, and $S$ is its size:
$$r(x,a)=\inf_{\Delta>0}\frac{\mathbb{E}[\min(S-a,\Delta)\mid S>a,\,x]}{\mathbf{P}[S-a\le\Delta\mid S>a,\,x]}.$$
The scheduler serves the job with the lowest rank. Our central conjecture has two parts. First, the policy is tail-optimal whenever the size distribution conditioned on $x$ satisfies the per-class version of the Scully–van Kreveld conditions, meaning it is either NBUE (new better than used in expectation) or nicely heavy-tailed. This should hold even when the pooled distribution is badly behaved. Second, when features only partially reveal the class, the leftover tail penalty is governed by the mass of the slow class that the features misattribute. We will try to prove both statements and measure them.
What is new is not that side information helps the mean, which is classical. It is a tail theory of where suppression lands, together with a practical scheduler built on it.
Research Program
Theory. The theoretical part extends two existing analyses. The first is the worst-ever-rank analysis of When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail?. The second is the SOAP machinery of Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job Sizes, which analyzes any policy whose priority depends on attained service. We extend both to ranks that depend on $(x,a)$.
The closest theoretical relative is On the Gittins index for multistage jobs. It shows how state information reshapes Gittins indices but characterizes indices, not tails. We treat observed features as a static stage label and features revealed during decoding as stage transitions. We then ask how the tail's decay rate (how fast $\mathbf{P}[T>t]$ shrinks) and its tail constant (the multiplier in front of that decay) depend on how informative the features are.
For the light-tailed constant we also derive a feature-conditioned analogue of the boost function in Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1. That paper attains the minimal tail constant, but only when sizes are known at arrival. Our version uses features in place of sizes. The open question is how much of the gap between FCFS and its oracle constant can be closed by features alone.
Systems. We build the scheduler, called TunedBoost, inside the engine used by Beyond Prediction: Tail-Aware Scheduling for LLM Inference. We keep that paper's MemGuard rule, which re-ranks only at geometric token checkpoints to limit KV-cache thrashing, so that preemption cost is held fixed.
The rank lives in a table indexed by feature cell and age bin. We update it online with a local rule borrowed from the inhibitory plasticity model of The generation of cortical novelty responses through inhibitory plasticity. In that model, inhibition onto a population grows only when that population's own pattern recurs. That locality is what keeps the circuit sensitive to novel inputs, whereas blanket inhibition renders it deaf to them. In our scheduler the analogous rule is that a cell's demotion weight rises only when that cell's own observed completions show large remaining work. Cells with little data default to neutral rank rather than inheriting the pooled estimate.
We are explicit about the analogy's role. It supplies a design constraint (local, per-cell, homeostatic updates). It does not supply the mathematics, which is ordinary online estimation of conditional hazards.
Primary Afferent Depolarization and Frequency Processing in Auditory Afferents motivates one specific design choice. In that work, suppression in an auditory afferent is tuned to a frequency band offset from the band that drives it. Correspondingly, demotion should target feature×age cells where remaining work is large, not simply old jobs.
Features. Features come at two costs. The cheap option is a small classifier on the prompt, for example chat versus reasoning versus function call. The richer option is a linear probe on decoder hidden states, built from GeorgeMLP/reasoning-probing, which updates the class posterior as tokens are generated.
Baselines
Naive references. The do-nothing reference is FCFS with the engine's default continuous batching. FCFS is the textbook tail-minimizer for light tails, and every policy must at least match it at P99. We also run pure attained-service FB/LAS scheduling (always serve the least-served request) to exhibit the pessimality we claim to fix.
Strongest competitor. This is UniBoost from Beyond Prediction: Tail-Aware Scheduling for LLM Inference. It is a prediction-free soft priority over attained tokens, uses γ-Boost-style shaping with online adaptation of its softness parameter, and was evaluated on the same traces we use. It is the strongest because it already avoids hard-SRPT starvation and handles preemption cost. It is exactly the age-only, feature-blind policy our claim says leaves tail on the table.
The file reports its results only as relative numbers. It achieves 35–50% lower P99 time-to-last-token (TTLT) and 34–47% lower P99 time-to-first-token (TTFT) than SRPT with a perfect length oracle, with 1.01–1.12× throughput. No absolute reported result was found on Lacuna for UniBoost's P99 TTLT on any single trace. We will therefore reproduce it ourselves with its published mechanisms.
Beating UniBoost means a lower P99 TTLT on the mixed workloads with mean TTLT and throughput no worse. The comparison must hold under the same MemGuard bins, same hardware, same arrival replay, and the same hyperparameter-search budget for both systems.
Theory-side baselines. In the synthetic queue we compare against four policies. The first is q-approximate Gittins on the pooled distribution, which eliminates pessimality with mean cost within $1+\epsilon$ of Gittins according to When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail?. The second is Nudge from Nudge: Stochastically Improving upon FCFS, which reports 4–7% tail reductions over FCFS on common distributions. The third is γ-Boost with known sizes from Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1, which reports a 30–50% tail-constant reduction over FCFS. We treat it as an oracle ceiling, not a competitor. The fourth is SRPT with a perfect oracle.
Ablations. Three ablations isolate the key ingredient. Feature shuffling keeps the same rank table but randomly permutes features across requests, which recreates blanket demotion at identical model capacity. Static class priority uses features but ignores age. Pooled plasticity applies the same online rule to a single feature cell.
Why not just…?
Why not just train a length predictor from the same features and run SRPT or size-aware γ-Boost? This is the most serious threat, because it uses the same information. There is evidence it falls short. Beyond Prediction: Tail-Aware Scheduling for LLM Inference finds that even SRPT with a perfect oracle has a far worse P99 than UniBoost. Revisiting Size-Based Scheduling with Estimated Job Sizes shows that size-based policies need fallbacks once estimates are wrong. Point predictions also discard the conditional shape of the distribution, which is what determines pessimality. Size-aware γ-Boost fed with predicted sizes is nonetheless a fair rival. We run it with the identical feature model, and if it matches TunedBoost at P99 we will report that the gain comes from features, not from tuned demotion.
Why not just apply q-approximate Gittins to the pooled distribution? It provably removes pessimality without any features. However, its guarantee is relative to pooled Gittins, whose mean is worse than conditional Gittins. In the hyperexponential case it still delays nearly finished fast-class jobs during the stretch before its nudge activates. The synthetic experiment directly compares tail constants at matched means. If the two are indistinguishable, our core claim fails.
Why not just keep UniBoost and let its adaptive parameter track the mixture? Its adaptation turns one global knob. That is the computational analogue of the blanket inhibition that The generation of cortical novelty responses through inhibitory plasticity shows silences responses to everything. Scheduling for Cloud-Based Computing Systems to Support Soft Real-Time Applications likewise reports age-based schedulers becoming brittle under workload shifts. The shift experiment below tests whether per-cell adaptation reacts faster.
Why not just partition chat and reasoning into separate queues? This is the static-class-priority ablation. With hard partitioning, misrouted reasoning requests block the chat queue, and the large class is starved during bursts. We expect it to lose at P99 whenever the classifier is imperfect.
Proposed Experiments
Synthetic queue. We simulate M/G/1 queues with two- and three-phase hyperexponential and bounded-Lomax mixtures at loads from 0.5 to 0.95. Each job's true phase is revealed through a noisy label of controllable accuracy. We estimate the decay rate and tail constant from long runs, matching the scale of the Nudge evaluations.
The decisive check has three predictions. With perfect labels, feature-conditioned Gittins should match FCFS's decay rate on each class while pooled Gittins should not. The tail penalty should shrink monotonically as label accuracy rises. Its growth should track the misattributed slow-class mass predicted by our bound.
LLM serving. We replay arrival patterns from the Azure Conversation and Function traces, with request contents drawn from ShareGPT and WildChat (WildChat: 1M ChatGPT Interaction Logs in the Wild). We inject s1k reasoning requests in fixed ratios and in step changes of the ratio. The step-change test compares how quickly each policy's P99 recovers after the ratio shifts.
The metrics are P99 and P99.9 TTLT, P99 TTFT, mean TTLT, throughput, and the number of KV-cache swaps. The headline test asks whether TunedBoost lowers P99 TTLT relative to UniBoost on mixed workloads at matched mean and throughput, and whether the feature-shuffled ablation erases that gain. If the shuffled ablation performs as well, the gain is not from tuning.
We also test where the benefit lives. Our prediction is that on pure-chat traces, where the pooled distribution is already well behaved, TunedBoost and UniBoost tie. A gain that appears only where the theory says pooling causes pessimality is the strongest evidence that the mechanism is the one we claim.
References
- When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail?
- Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job Sizes
- On the Gittins index for multistage jobs
- Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1
- Beyond Prediction: Tail-Aware Scheduling for LLM Inference
- The generation of cortical novelty responses through inhibitory plasticity
- Primary Afferent Depolarization and Frequency Processing in Auditory Afferents
- Nudge: Stochastically Improving upon FCFS
- Revisiting Size-Based Scheduling with Estimated Job Sizes
- Scheduling for Cloud-Based Computing Systems to Support Soft Real-Time Applications
- WildChat: 1M ChatGPT Interaction Logs in the Wild