When RLVR, RLHF, and Agents Fight Over KV Cache: Admission Control for Mixed Rollouts

Paper: 2608.11152 Authors: Zetao Hong, Song Yuan, Yuanhao Ding, Yibo Zhu, Daxin Jiang, Zhibin Wang, Chen Tian Categories: cs.DC, cs.LG

The Gap

Here’s the setup. Modern RL post-training for LLMs isn’t one workload anymore. You’ve got RLVR (math and code problems with a verifier — long chain-of-thought generations, single turn, moderate prompt), RLHF (reward-model-scored preference data — often shorter generations, multiple samples per prompt), and agentic rollouts (tool calls, environment feedback, many turns with long stalls in between while the sandbox runs your Python or the browser loads). The trainer wants all three mixed in some specified ratio because that’s what makes the resulting policy good. All three hit the same asynchronous inference service.

The state of the art on the serving side is prefix-aware routing. The vLLM Router, SGLang’s cache-aware load balancer, and similar systems all do roughly the same thing: when a request arrives, look at its prefix, figure out which replica already has that prefix in its KV cache, and send it there. Balance load so no replica gets swamped. This works well and it’s the right idea — prefix reuse in RL rollouts is enormous, since you sample multiple completions per prompt and agentic turns share the entire conversation history.

But notice what prefix-aware routing is a policy about: it decides where a request goes. It says nothing about whether a request should be let in right now, or how much of the cache a class of requests deserves to hold. And in mixed rollout serving, that’s where the pain is. An agentic session that’s on turn 7 of 15 is sitting on a fat KV block and will keep sitting on it through the next tool call — maybe 2 seconds, maybe 30. Meanwhile an RLVR request wants to stream 8K tokens of reasoning and needs cache the whole time. RLHF requests come and go fast. Under a pure prefix-locality policy, whichever class happens to arrive in bursts wins the cache, preemptions cascade, and the effective throughput collapses even though the router’s cache-hit-rate dashboard looks great.

Worse, there’s a second-order failure. If you naively fix congestion by throttling whatever class is causing it, you silently change the mixture the trainer asked for. Now you’ve got a systems fix that quietly damages learning. That coupling — serving efficiency versus mixture fidelity — is the actual gap.

   [ PROBLEM ]
   Mixed RLVR + RLHF + agentic rollouts share one
   async inference service. Prefix-aware routers
   (vLLM Router, SGLang cache-aware LB) pick WHERE
   a request goes, not WHETHER it is admitted.
        |
        v
   [ OBSERVATION ]
   Classes differ in three axes, not one:
     (a) sequence structure  (prompt vs gen length)
     (b) interaction pattern (1-turn vs N-turn)
     (c) KV residency time   (how long blocks are held)
   Prefix locality only sees (a). Blindness to (c)
   is what causes preemption cascades.
        |
        v
   [ ASSUMPTION ]
   Congestion is controllable at the ROUTING LAYER,
   before requests reach engine schedulers, IF you
   account for KV footprint x residency, per class.
   And it must be done without distorting the
   trainer-specified workload mixture.
        |
        v
   [ METHOD: MISA-T ]
   +-- adaptive session admission
   +-- workload-aware KV capacity allocation
   +-- residency-time-aware KV accounting
        |
        v
   [ EVIDENCE ]
   rollout-only ablation:
     Step3.7        : +53.3% throughput vs tuned vLLM Router
     Qwen3.6-35B-A3B: +43.6%
   end-to-end, 50 iters, Step3.7:
     +35.6% rollout throughput
     -22.8% mean iteration time
     mixture ~ trainer target ; task scores comparable
        |
        v
   [ CONCLUSION ]
   Rollout scheduling is an admission-control problem,
   not just a placement problem. Prefix locality is
   necessary but insufficient.

The Increment

One sentence: Before this paper, mixed-domain RL rollout serving was tuned by picking a good *placement policy and hoping the engine’s scheduler sorted out the rest; after it, the router itself is a resource-allocation authority that decides which sessions enter and how much KV each workload class may hold — with the trainer’s mixture treated as a hard constraint rather than collateral damage.

Core Mechanism

MISA-T lives entirely at the routing layer, which is the pragmatic design choice here: no engine forks, no vLLM/SGLang internals surgery. It sits between the trainer’s rollout dispatcher and the pool of inference replicas, and it does three things that compose.

Adaptive session admission. Instead of forwarding every request the moment it arrives, MISA-T maintains a notion of what each replica can actually sustain and gates entry. Note the word *session, not request — an agentic rollout is admitted as a unit with an expected multi-turn lifetime, because admitting turn 1 commits you to holding cache through turns 2..N. Adaptive means the gate moves: it tightens when observed pressure rises (queueing delay, preemption events, cache eviction rate) and loosens when headroom appears. This is the difference between a bouncer with a clicker and a bouncer who watches how full the room actually feels.

Workload-aware KV capacity allocation. The KV budget on each replica is partitioned by workload class rather than served first-come-first-served. RLVR gets a share, RLHF gets a share, agentic gets a share. Crucially the shares are derived from the trainer’s target mixture and each class’s per-session cost, so that the *consumed mixture stays near target. This is the mechanism that decouples “fix congestion” from “distort the data recipe.” If agentic sessions are hogging, you don’t just choke them — you choke them to the level their mixture share entitles them to, which is a defined, defensible number rather than a knob.

Residency-time-aware KV accounting. This is the conceptual core. Existing accounting treats KV cache as a *space resource: this request needs N blocks. MISA-T treats it as a space-time resource: this request needs N blocks for T seconds, so its true cost is roughly N x T. An agentic session with a modest block count but a long stall between turns can be more expensive than an RLVR request with a bigger block count that finishes fast. Under space-only accounting these look reversed, which is precisely why prefix-aware routers get mixed workloads wrong. Once you account in block-seconds, admission and allocation decisions become comparable across classes.

   TRAINER (specifies mixture: e.g. 50% RLVR / 30% RLHF / 20% agentic)
        |
        |  rollout requests, tagged with class
        v
  +==========================================================+
  |                      M I S A - T                         |
  |                   (routing layer)                        |
  |                                                          |
  |  [1] CLASS TAGGER / SESSION TRACKER                      |
  |      request --> which class? new session or turn k?     |
  |      keeps per-session state: turns so far, blocks held   |
  |                     |                                    |
  |                     v                                    |
  |  [2] RESIDENCY-AWARE COST MODEL                          |
  |      cost = blocks x expected_residency                   |
  |         RLVR      : med blocks x med time                |
  |         RLHF      : low blocks x short time              |
  |         agentic   : med blocks x LONG time (stalls)      |
  |                     |                                    |
  |                     v                                    |
  |  [3] KV BUDGET ALLOCATOR (per replica, per class)        |
  |      budget_c derived from trainer mixture + cost_c      |
  |      +-----------+-----------+-----------+               |
  |      |  RLVR pot |  RLHF pot | agentic   |               |
  |      |  ~~~~~~   |  ~~~~     | ~~~~~~~~  |               |
  |      +-----------+-----------+-----------+               |
  |                     |                                    |
  |                     v                                    |
  |  [4] ADMISSION GATE (adaptive)                           |
  |      does class c have block-seconds left in its pot?    |
  |          yes -> admit, then apply prefix-aware placement |
  |          no  -> hold in class queue (do NOT starve;      |
  |                 mixture debt is tracked and repaid)      |
  |                     |                                    |
  |                     v                                    |
  |  [5] PREFIX-AWARE PLACEMENT (retained, not replaced)     |
  |      pick replica with best prefix overlap among those   |
  |      with headroom  ==> keeps cache hit rate high        |
  +==========================================================+
        |                    ^
        |  admitted reqs     |  feedback: queue delay, preemptions,
        v                    |  eviction rate, actual residency
   +---------+  +---------+  +---------+
   | replica |  | replica |  | replica |    (vLLM / SGLang, unmodified)
   |  KV     |  |  KV     |  |  KV     |
   +---------+  +---------+  +---------+

The metaphor: a hotel that had been run as a valet stand.

Think of each inference replica as a hotel and the KV cache as its rooms. Prefix-aware routing is the valet at the door: its whole job is deciding which hotel to send you to, and it’s good at it — it sends you to the hotel where your family is already staying, so you can share their suite (that’s cache reuse). But the valet never asks whether the hotel has rooms, or how long you plan to stay. Everyone who shows up gets sent somewhere, and the front desk deals with the fallout by kicking guests out of rooms mid-stay (that’s preemption and eviction).

MISA-T is the front-desk manager the hotel never had, and its three components are three things a real hotel manager knows:

First, you book a stay, not a night. A business traveler checking in for one night and a family checking in for a two-week trip with day excursions are not the same commitment — the family will keep the room keys while they’re out at the museum. That’s the agentic session holding KV cache through a tool call. Adaptive session admission means the manager commits to the whole stay up front, or not at all, instead of discovering on day four that there’s no room.

Second, the hotel runs room blocks per group. The conference has 50 rooms reserved, the tour group has 30, walk-ins get 20. This is workload-aware KV allocation, and the sizes come from a contract — the trainer’s mixture — not from whoever queued at the desk earliest. When the tour group tries to squeeze in ten extra people, the manager doesn’t evict the conference; he tells the tour group they’re at their block limit. The conference still gets its rooms. The mixture survives.

Third, the manager bills in room-nights, not rooms. One room for fourteen nights costs more than two rooms for one night. This is residency-time-aware accounting, and it’s the piece that makes the other two coherent — without it, the manager would think the family of four in one room is a cheap booking and the four business travelers in four rooms are expensive, which is exactly backwards. Prefix-aware routers count rooms. MISA-T counts room-nights.

And notice: MISA-T doesn’t fire the valet. Placement is still prefix-aware; the front desk just tells the valet which hotels have availability first. That’s why cache hit rates stay high while throughput goes up.

Key Concepts

• KV cache as a space-time resource (block-seconds): When an LLM generates text, it stores intermediate attention state for every token processed so far — that’s the KV cache, and it’s the real scarce resource in inference, more than compute. Everyone knows it’s measured in blocks (chunks of tokens). What people under-model is *duration. Imagine a parking garage with 100 spaces. If you only count spaces, a car and a truck taking 1 space and 2 spaces look like a 1

  problem. But if the car parks for 8 hours and the truck for 10 minutes, the car is consuming 8 space-hours and the truck 0.33 — a 24
  problem in the other direction. Agentic rollouts are the all-day parkers: between turn 3 and turn 4 the model isn’t generating anything, but the cache must be held or you pay to recompute the whole conversation. Bill in block-seconds and suddenly the right decisions become obvious.

• Mixture fidelity as a first-class SLO: In normal serving you optimize latency and throughput. In RL rollout serving there’s an extra constraint nobody in the systems literature was tracking: the *composition of what you served has to match what the trainer asked for. If the trainer says “50% math, 30% preference, 20% agentic” and your scheduler quietly delivers 70/25/5 because agentic rollouts kept getting throttled, you’ve built a fast system that trains a worse model — and the failure is invisible in every systems metric. MISA-T’s contribution here is treating this as a constraint to be satisfied, with mixture debt tracked and repaid, rather than as an outcome to be hoped for. This is a genuinely useful framing shift: any time a systems layer sits underneath a learning process, ask what statistical property of the workload your optimization is silently deforming.

• Admission control vs. placement (the queueing-theory point): These are different levers and confusing them is common. Placement is “which server,” admission is “now or later.” Classic queueing theory tells you that when a system is near saturation and work is heterogeneous, *no placement policy saves you — you have to shed or delay work at the entrance, because past a threshold, letting work in makes total throughput go down (thrashing, preemption, recompute). Anyone who has seen a database die from connection-pool exhaustion knows the shape of this. Prefix-aware routers are pure placement policies operating in a regime where admission is what matters. That’s the paper’s real insight, and stated that plainly it sounds almost obvious — which is usually the sign of a good systems observation.

Framework Shift

  Before (prefix-aware routing):        After (MISA-T):

  trainer                               trainer + mixture contract
    |  all requests, unthrottled          |  requests, class-tagged
    v                                     v
  +--------------------+                +----------------------------+
  |  ROUTER            |                |  ROUTER                   |
  |  question asked:   |                |  questions asked:         |
  |   "WHERE?"         |                |   "SHOULD IT ENTER?"      |
  |                    |                |   "WHOSE BUDGET?"         |
  |  prefix overlap    |                |   "FOR HOW LONG?"         |
  |  + load balance    |                |   then "WHERE?"           |
  +--------------------+                +----------------------------+
    | everything in                      | only what fits, per class
    v                                     v
  +--------------------+                +----------------------------+
  | ENGINE             |                | ENGINE                    |
  | KV = one pot,      |                | KV = per-class pots,      |
  |      FCFS          |                |      billed in block-secs |
  |                    |                |                           |
  | [RLVR][ag][ag][ag] |                | [RLVR ][RLHF][agentic]    |
  |  <- bursty class    |                |  sized by mixture x cost  |
  |     eats the pot    |                |                           |
  |                    |                |                           |
  | preempt! evict!    |                | steady, few preemptions   |
  | recompute!         |                |                           |
  +--------------------+                +----------------------------+
    |                                     |
    v                                     v
  high cache hit rate,                  high cache hit rate AND
  low real throughput,                  high throughput,
  mixture drifts silently               mixture held to target

From placement to admission, the core shift is that the router stops being a traffic sign and becomes a resource governor — one that prices cache in block-seconds and answers to the trainer’s data recipe as a contract.

Expert Assessment

Problem choice: Real gap, and well-timed. The trajectory is clear: 2023-24 was “make rollouts fast” (continuous batching, PagedAttention), 2024-25 was “make rollouts cache-aware” (prefix routing, radix trees), and 2025-26 is “rollouts are now a heterogeneous mixed workload because everyone is training agents *and doing RLVR and still running RLHF in the same pipeline.” Mixed-workload interference at the KV layer is exactly the pain point that shows up when you scale that up, and the mixture-fidelity coupling is a genuinely under-noticed hazard — I’ve seen teams debug reward curves for weeks when the actual cause was the serving layer starving one data source. Naming that failure mode is worth something independent of the mechanism.

Method maturity: Honestly, this is the sensible engineering answer rather than a deep insight, and the paper is at its best when it doesn’t pretend otherwise. Residency-time accounting is the one idea with teeth — it reframes the resource correctly, and the reframing is portable. The other two components are competent applications of textbook material: token-bucket-flavored admission control and weighted fair queueing over a partitioned resource. That’s not a criticism of the result, but it does mean the intellectual delta is thinner than the throughput numbers suggest. Two things I’d want probed harder: first, expected residency has to be *predicted, and agentic turn counts and tool latencies are famously heavy-tailed — how badly does a mispredicted residency hurt, and is there any online correction beyond the feedback loop? Second, and this is the simpler-approach question: how much of the 53% is recoverable by just running separate replica pools per workload class, or per-class rate limits with no residency modeling? Static partitioning is the dumb baseline that often gets 70% of the win, and if the paper doesn’t include it, that’s the first ablation a reviewer should demand.

Experimental integrity: The baseline choice is fair and I want to credit it explicitly — “sweep-tuned cache-aware vLLM Router” means they tuned the baseline rather than shipping it at defaults, which is where most systems papers cheat. Two models, and the end-to-end 50-iteration run with reported task scores and consumed mixture is the right experiment; a lot of rollout-scheduling papers stop at the rollout-only microbenchmark and never show that learning survived. Reporting rollout-only (+53.3%) *and end-to-end (+35.6%) rather than quoting only the bigger number is honest. Now the caveats. The gap between 53% and 35.6% is Amdahl’s law showing up — the training step doesn’t speed up — so the headline should really be the 22.8% iteration-time reduction, and I’d have led with that. “Comparable task scores” over 50 iterations is a weak claim: 50 iterations is short, and scores are noisy at that horizon, so this establishes no catastrophe rather than no cost. The claim I’d most want to see stress-tested is mixture fidelity under adversarial load — “close to the trainer target” needs a number and a distribution, ideally under a burst pattern designed to break it. And single-cluster, two-model results mean I don’t know how this behaves at a different replica-count-to-workload ratio.

Writing quality: The abstract does the thing where three components are named in a list and the reader is left to guess which one carries the weight. It’s residency-time accounting; say so. My concrete suggestion: the paper needs a motivating measurement section that shows the interference and the mixture drift happening in a real trace — footprint versus residency plotted per class, preemption cascades correlated with agentic bursts, and the consumed-versus-target mixture curve diverging under a baseline router. That figure would convert the whole contribution from “we built a scheduler with three features” into “here is a failure mode nobody was measuring, and here is the accounting fix.” Same experiments, twice the impact. Also, “T” in MISA-T is never explained in the abstract, which is a small thing that reads as a rushed submission.

Verdict: weak accept — the residency-time reframing is correct and useful, the end-to-end validation with mixture and task scores is more rigor than this subfield usually shows, but the mechanism is largely known techniques recombined, and the missing static-partitioning baseline plus the thin mixture-fidelity evidence keep it out of strong-accept territory.

Takeaways

Specific things worth stealing:

Price cached state in space-time, not space. Any system holding per-session state under memory pressure — LLM KV cache, connection pools, GPU memory in multi-tenant serving, materialized query state, even CDN edge cache — probably measures footprint and ignores duration. The fix costs almost nothing: multiply by expected residency and let admission decisions compare across heterogeneous tenants on one axis. Block-seconds is the unit. If your eviction policy or admission gate currently reads “needs N units,” ask what it would decide if it read “needs N units for T seconds.”

Admit sessions, not requests. The moment your workload has multi-turn interactions with idle gaps, request-level scheduling is lying to you, because accepting turn 1 is an implicit commitment to hold resources through turn N. Make that commitment explicit at the entrance. This transfers directly to agent serving, long-running RPC sessions, and anything with a sandbox or human in the loop.

When a systems layer sits under a learning process, name the statistical property you might be deforming. This is the framing I’d take furthest beyond this paper. Optimizing throughput while silently shifting the data mixture is a bug that no systems dashboard catches and every ML metric blames on something else. The general move: make the learning-side invariant an explicit, measured constraint in the systems layer — track the debt, repay it — rather than an emergent property. Same logic applies to curriculum ordering, negative-sampling ratios, staleness distributions in async RL, and shard-level data balance. If your scheduler can starve a class, it can change your model.

Ceiling check before you build. Rollout-only +53% became end-to-end +35.6%. Before optimizing a stage, measure its share of wall-clock and compute your Amdahl ceiling. And the corollary for evaluating others’ work: when a paper reports both microbenchmark and end-to-end numbers, the ratio between them tells you how much of the pipeline they actually touched.

The dumb baseline you should always try first: static per-class resource pools. If a paper proposes adaptive, cost-modeled, feedback-driven allocation and doesn’t compare against fixed partitioning, run that comparison yourself before adopting the complexity. Sometimes the answer is separate replica pools and a cron job.