[RFC]: Add API to restore free_block_queue allocation order for long-running RLHF / rollout sessions

[mrn3088]

Motivation.

reset_prefix_cache() is explicitly documented as intended for use in RLHF flows (to invalidate prefix caching after weight updates) and for benchmarking. In those flows it is natural to call it between logical rounds / rollout iterations while no requests are active. However, the current implementation only clears the prefix cache hash table; it does not restore the allocation order of free_block_queue. Over many rounds the linked list becomes progressively scrambled, which in turn scatters newly allocated block_table[req, :] entries across the physical KV pool and degrades attention-kernel locality on subsequent prefills. The net effect on long-running sessions is a monotonic prefill slowdown even when no recompilation, no new cache entries, and no KV pressure changes are occurring between rounds.

How the scrambling happens

• BlockPool.__init__ initializes free_block_queue as the strictly increasing sequence [1, 2, ..., N-1] (block 0 is the null block).
• popleft() takes blocks off the head at allocation time; on request completion, a request's blocks are appended back to the tail in reverse order of the request's own blocks (as described in FreeKVCacheBlockQueue's docstring: "we maintain this order by reversing the block order when free blocks of a request").
• After a handful of alloc/free rounds, the linked-list position of a block is fully decoupled from its block_id. Future popleft()s then hand out non-contiguous block_ids even when plenty of blocks are free.

Why this matters on the attention side

Downstream, block_table[req_id, logical_block_idx] stores the physical block_id that backs each logical KV block of a request. When allocations produce non-contiguous block_ids, successive logical KV blocks of the same request land on physically distant pages of the KV pool. Attention kernels that gather K/V through the block table (e.g. FlexAttention with paged KV) lose memory coalescing and effectively pay worse L2/TLB hit rates during prefill, where the Q × KV access volume is large. Decode is far less affected because each step only touches a small number of new KV pages.

Why reset_prefix_cache() alone is not enough

BlockPool.reset_prefix_cache() currently does the following and nothing else (confirmed against main at the time of writing):

self.cached_block_hash_to_block = BlockHashToBlockMap()
for block in self.blocks:
    block.reset_hash()
# ... metrics reset, kv_event ...

The linked list free_block_queue is untouched. Callers that rely on reset_prefix_cache() between rounds (RLHF/GRPO rollouts, benchmarking drivers) therefore still observe cumulative fragmentation of the allocation order across the lifetime of the LLM instance. There is no existing API to restore a canonical order.

Measured impact

We hit this while running a GRPO-style offline rollout driver (vLLM V1 offline LLM, FlexAttention backend, prefix caching on, chunked prefill off, 2 prompts with rollout.n=4 to share prefixes within each round, reset_prefix_cache() called between rounds). Same 8-request shape every round, same model, no recompiles in the middle of the run. Prefill latency (first_token_ts − scheduled_ts, batch-aggregate) per round:

Round	Prefill before	Prefill after
1	3.51 s	3.56 s
2	5.61 s	2.81 s
3	8.00 s	3.03 s
4	13.73 s	3.31 s
5	9.42 s	2.33 s
6	14.36 s	3.45 s

Before: ~5.7× prefill slowdown over 6 rounds. After rebuilding free_block_queue in canonical order on each inter-round reset: prefill becomes flat at ~3 s (round-to-round variation is now driven by prompt length, not session age). Decode latency is essentially unchanged by the fix, which is consistent with the locality story above.

Scope of affected users

Any caller that runs a long-lived LLM / AsyncLLM instance with enable_prefix_caching=True and periodically calls reset_prefix_cache() between logical rounds. The two canonical scenarios:

• RLHF / GRPO rollouts. reset_prefix_cache() is already the recommended way to invalidate the cache after a weight update (#9744, #12284). GRPO and RLOO-style samplers naturally produce repeated rollout rounds on the same engine.
• Benchmarking drivers that reset between trials.

Proposed Change.

Proposed Change

Add a narrowly-scoped way for callers to restore the canonical allocation order of free_block_queue when no requests are active. We see two reasonable shapes and would like maintainer input on which to land.

Option A — New standalone API (single-responsibility)

Add BlockPool.reset_free_block_queue_order() with the same "no live requests" precondition as reset_prefix_cache():

def reset_free_block_queue_order(self) -> bool:
    """Rebuild the free_block_queue linked list in canonical block_id order.

    Long-running sessions accumulate fragmentation in the free-block linked
    list; subsequent popleft()s produce non-contiguous block_ids and scatter
    block_tables across the physical KV pool, hurting attention-kernel
    locality. Call this when no requests are active (same precondition as
    reset_prefix_cache) to restore the canonical order.
    """
    num_used_blocks = self.num_gpu_blocks - self.get_num_free_blocks()
    if num_used_blocks != 1:  # null block counts as 1
        logger.warning(
            "Failed to reset free_block_queue order because some "
            "blocks (%d) are not freed yet",
            num_used_blocks - 1,
        )
        return False
    for block in self.blocks:
        block.prev_free_block = None
        block.next_free_block = None
    self.free_block_queue = FreeKVCacheBlockQueue(self.blocks)
    self.free_block_queue.popleft()  # skip null block (id=0)
    return True

Then plumb it up through the same chain reset_prefix_cache already uses:

BlockPool
  └── KVCacheManager.reset_free_block_queue_order()
        └── Scheduler.reset_free_block_queue_order()   (abstract on SchedulerInterface)
              └── EngineCore.reset_free_block_queue_order()
                    └── EngineCoreClient.{reset_free_block_queue_order,
                                          reset_free_block_queue_order_async}()
                          └── LLMEngine / AsyncLLM.reset_free_block_queue_order()
                                └── LLM.reset_free_block_queue_order()

Pros: single responsibility, zero behavioral change to reset_prefix_cache, callers that only want hash invalidation (e.g. hot-swap scenarios that may care about block-id stability) keep current semantics.

Cons: one extra method on the public LLM surface; RLHF/benchmark callers typically want both and must call them in sequence.

Option B — Opt-in flag on reset_prefix_cache

Extend reset_prefix_cache() with a keyword-only parameter, default-off for backward compatibility:

def reset_prefix_cache(
    self,
    reset_running_requests: bool = False,
    reset_connector: bool = False,
    reorder_free_queue: bool = False,
) -> bool:
    ...

When reorder_free_queue=True, after the existing hash-clearing logic, rebuild free_block_queue in canonical order (same body as Option A).

Pros: one call, no extra public API surface; RLHF/benchmark callers flip one flag.

Cons: conflates two distinct concerns on a single entry point; propagating the new kwarg all the way through core_client.call_utility("reset_prefix_cache", ...) (including the async variant) means touching every layer anyway.

Our preference

We implemented Option A in our fork because it keeps reset_prefix_cache semantically unchanged and lets the reorder operation be composed with sleep() / wake_up() / benchmark harnesses independently. We are happy to rework as Option B (or a combination — standalone API plus a flag on reset_prefix_cache that delegates to it) based on maintainer preference.

Preconditions and safety

• The num_used_blocks != 1 guard is identical to the one reset_prefix_cache already relies on; calling the new API between rollout rounds (where all requests have finished and LLM.generate() has returned) always satisfies it.
• No GPU-side state is touched. The operation only rewrites the Python-side doubly-linked list of KVCacheBlock objects. Physical KV memory layout is unchanged; the benefit comes from future allocations drawing contiguous block_ids again.
• No interaction with cached_block_hash_to_block: Option A explicitly does not clear hashes. Callers that want both should call reset_prefix_cache() first (so there are no live hashes that still reference the about-to-be-reordered list), then the new API.
• Compatible with both Scheduler and AsyncScheduler (the latter inherits).
• Works for both InprocExecutor (offline LLM) and the sync/async multi-process core clients via call_utility("reset_free_block_queue_order") / call_utility_async(...).

Testing plan

• Unit test against BlockPool in isolation: allocate and free in scrambled patterns across many simulated requests, assert that after reset_free_block_queue_order() a sequence of popleft()s returns strictly increasing block_ids starting from 1.
• Regression test that existing reset_prefix_cache semantics are untouched when the new API is not called.
• An end-to-end benchmark showing the flat-vs-monotonic prefill curve (we can contribute our repro, stripped of model-specific pieces).

Feedback Period.

Two weeks, or until maintainers indicate a preferred API shape.

CC List.

@WoosukKwon @zhuohan123 @youkaichao @robertgshaw2-redhat @comaniac @simon

Any Other Things.

Happy to open the PR directly against main once an API shape is agreed on. A reference implementation (Option A) is already working in our downstream fork with the plumbing path listed above.

Before submitting a new issue...

• Make sure you already searched for relevant issues, and asked the chatbot living at the bottom right corner of the documentation page, which can answer lots of frequently asked questions.

[robertgshaw2-redhat]

cc @LucasWilkinson @MatthewBonanni - this is a surprising finding

[mrn3088]

Hi @aoshen524 , the original problem occurs when we are using vLLM in verl. However as the example I shown, it could also be reproduced when running vLLM offline inference alone. Our workload have long input (70000+ token) + long output (4096). I can try to use open source model to write a example script to reproduce later.

[aoshen02]

Hi @mrn3088, my previous account got suspended so following up from here. Did you ever write up the repro script you mentioned for offline inference with long input/output? Want to reproduce on my side. Thanks.

[mrn3088]

Hi @aoshen02 , I hope to get it back to you by this weekend!

[aoshen02]

np

[aoshen02]

Hi, any follow up?

[mrn3088]

Hi, when I tried to replicate this last week, I found it hard to reproduce on the latest vLLM with gemma3. I need to figure out whether it is a vLLM version issue, or it is because of our customized attention calculation. I will update once there's some findings.

…

On Sun, May 10, 2026 at 5:27 PM aoshen02 ***@***.***> wrote: *aoshen02* left a comment (vllm-project/vllm#40244) <#40244 (comment)> Hi, any follow up? — Reply to this email directly, view it on GitHub <#40244 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AXHX25CWAITNTZIQBZQWR2342EM7TAVCNFSM6AAAAACX52UDUKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHM2DIMJWG42TGNRWGI> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[aoshen02]

Appreciate it.

[dajinge]

I can reproduce this with a non-trivial config where it's very pronounced — adding a data point since @WoosukKwon mentioned difficulty reproducing with Gemma3.

Environment

• Hardware: NVIDIA DGX Spark (GB10 SoC, 128 GB unified memory, ARM64)
• vLLM: 0.23.1 nightly (Docker)
• Model: Qwen3.6-35B-A3B-NVFP4 (MoE, 30 attention + 10 Gated DeltaNet layers, max-model-len=262144, NVFP4 quantization)
• KV pool: 2,724,425 tokens (52.77 GiB, ~85,000 blocks at block_size=32)
• Backend: auto-detected (FP4 Marlin kernel on GB10)

Workload

• Sequential (p=1), ISL=1024, OSL=65536, 2 warmup + 5 benchmark = 7 requests
• Each request allocates ~2,100 KV blocks, freed in reverse order between requests
• KV cache is fully flushed between requests — identical peak usage of 2.52–2.56% every cycle, confirmed by polling /metrics at 1 Hz

Observed TTFT degradation across the 7 requests

Request	TTFT	ITL	Delta
1 (warmup)	—	—	—
2 (warmup)	—	—	—
3 (bench #1)	178 ms	11.8 ms	baseline
4 (bench #2)	185 ms	13.9 ms	+4%
5 (bench #3)	377 ms	15.2 ms	+112%
6 (bench #4)	379 ms	16.7 ms	+113%
7 (bench #5)	411 ms	17.7 ms	+131%

Ruled-out causes

• GPU thermal: stable 66–68°C, 34–37W, SM% flat 94–96% throughout (nvidia-smi dmon)
• System memory: used DRAM drifted 87,287→87,872 MB over 83 min — negligible
• CPU load: 1.13–1.39, no I/O contention
• KV pressure: identical peak per cycle, fully freed
• TPOT: nearly flat (12.8→15.3 ms, +19%) — decode is largely unaffected, consistent with the prefill-vs-decode locality story in the RFC

Why I think this reproduces here but not with Gemma3

1. Hybrid architecture amplifies the effect. MoE + Gated DeltaNet creates more diverse attention-layer groups, so the scheduler touches more block_table entries per token. Each fragmented block_id lookup costs.
2. Long OSL (64K+). Each request uses ~2,100 blocks, so 7 cycles = ~14,700 alloc/free ops. The free_block_queue scrambles faster with more blocks per cycle.
3. Sequential benchmark. No concurrent requests mask the trend — each request observes the full post-fragmentation state.

This tracks the RFC's 5.7× prefill slowdown perfectly — just scaled to our smaller prompt (1K ISL vs their ~8K). The core mechanism (scrambled free_block_queue → non-contiguous block_id allocation → attention-kernel L2/TLB miss during prefill) matches exactly.

[aoshen02]

interesting.

[aoshen02]

I ran a two-repeat reproduction attempt for @dajinge's configuration on a single GB200. The short result is: I could not reproduce the monotonic TTFT degradation on GB200, but the runtime cache geometry turned out to be materially different from the GB10 report.

Environment

• Hardware: 1x NVIDIA GB200 (GPU 0 only)
• Image: vllm/vllm-openai@sha256:2bef153b9fa9a44149bbdff3d9de396fad462b4f5a8059d5e63e9fed8280c697
• Image tag/commit: cu129-nightly-a65f93fb2e295e501b929df3c291ec89c27d39e8
• vLLM: 0.23.1rc1.dev531+ga65f93fb2
• Model: nvidia/Qwen3.6-35B-A3B-NVFP4
• Model revision: 491c2f1ea524c639598bf8fa787a93fed5a6fbce
• TP=1, max-model-len=262144, user-specified block-size=32
• kv-cache-memory-bytes=56661356052 (52.77 GiB)
• Unspecified flags were left at this image's defaults:
  • enable_prefix_caching=false
  • enable_chunked_prefill=true
• Backend selected by vLLM: FlashInfer attention + Marlin NVFP4 MoE

The 52.77 GiB setting reproduced the reported capacity exactly:

GPU KV cache size: 2,724,425 tokens

However, /metrics reported:

user-specified block_size = 32
runtime-resolved block_size = 1056
num_gpu_blocks = 2619
kv_cache_size_tokens = 2724425

The log says vLLM changed the attention page size to 1056 tokens to align it with the hybrid Gated DeltaNet cache. So although the CLI configuration matched, this GB200 run did not have the ~85,000 physical 32-token blocks described in the GB10 result.

Workload

• Sequential, max_concurrency=1
• Exact ISL=1024, OSL=65536
• random-range-ratio=0, fixed seed=0
• ignore-eos=true
• 2 warmup requests + 5 measured requests
• Two independent repetitions, each starting from a fresh server container
• /metrics and GPU state sampled at 1 Hz

Run 1

Measured request	TTFT	Delta vs request 1	Mean ITL	E2E
1	131.885 ms	baseline	4.472 ms	293.198 s
2	137.528 ms	+4.28%	4.472 ms	293.207 s
3	132.536 ms	+0.49%	4.488 ms	294.236 s
4	133.823 ms	+1.47%	4.474 ms	293.358 s
5	133.743 ms	+1.41%	4.471 ms	293.152 s

Aggregate output throughput: 223.34 tokens/s.

Run 2 (fresh server)

Measured request	TTFT	Delta vs request 1	Mean ITL	E2E
1	134.952 ms	baseline	4.443 ms	291.318 s
2	134.605 ms	-0.26%	4.442 ms	291.213 s
3	132.841 ms	-1.56%	4.460 ms	292.404 s
4	137.501 ms	+1.89%	4.456 ms	292.145 s
5	134.338 ms	-0.45%	4.444 ms	291.339 s

Aggregate output throughput: 224.68 tokens/s.

Controls/observations

• All 14 long requests across the two repetitions reached the same sampled peak KV usage: 2.521%.
• No request waited or failed; all produced exactly 65,536 output tokens.
• GPU utilization was 99% during generation.
• GPU temperature stayed at 30-31°C after warmup.
• TTFT and ITL were flat; neither repetition showed a monotonic trend.
• I did not call reset_prefix_cache() between requests, matching the workload as described in the GB10 comment. The standard OpenAI server in this image also exposes no reset/cache administration route.

Interpretation

This is a non-reproduction on GB200, not evidence against the GB10 result. The most important difference is the allocator geometry: 2619 x 1056-token runtime pages on GB200 versus the reported ~85k x 32-token blocks on GB10. With only 2619 physical blocks, seven sequential requests may not scramble the free queue in the same way or at the same rate.

A useful next step for isolating the mechanism on GB200 would be an offline LLM harness that logs the allocated physical block IDs and either forces true 32-token physical pages or compares a backend/cache layout that does not resolve the page size to 1056.