简要回答

vLLM V1的RECOMPUTE抢占模式通过前缀缓存（prefix caching）和智能块管理实现低开销的内存回收。当KV缓存空间不足时，系统会驱逐部分缓存块，并在需要时重新计算被驱逐的部分，而不是将它们交换到CPU内存。

---

详细实现

核心机制

RECOMPUTE vs SWAP的区别：

• SWAP模式：将KV缓存块从GPU复制到CPU内存，需要时再复制回来
• RECOMPUTE模式：直接丢弃KV缓存块，需要时重新计算这些块 1

前缀缓存的优势：

• 前缀缓存允许KV缓存块在请求间隐式共享 2
• 块可以按需缓慢驱逐，被驱逐的提示部分可以重新计算 2
• 零开销的设计使得recompute策略更高效 3

实现细节

1. 统一调度器的token预算管理：
V1使用简单字典（如{request_id: num_tokens}）动态分配固定token预算，不再严格分离prefill和decode阶段 4

2. 块驱逐和重新计算：
当检测到无效块时，系统会：

• 截断num_computed_tokens到第一个无效块的位置
• 保持请求在运行队列中，准备重新计算
• 不释放已分配的块，确保重新计算时有足够资源 5

3. 全局缓存命中优化：

• 当所有token都被缓存时，调度器会减少num_cached_tokens 1个token，强制模型重新计算最后一个token 6
• 这确保了系统的正确性和性能平衡

性能优势

低开销的原因：

1. 避免内存拷贝：不需要在GPU和CPU之间传输大量KV缓存数据
2. 利用计算冗余：现代GPU的并行计算能力使得重新计算比内存传输更快
3. 智能缓存策略：前缀缓存确保常用的prompt部分被保留，只重新计算必要的部分

Chunked Prefill的配合：

• V1默认启用chunked prefill，允许将大prefill分解为小块处理 7
• 这使得重新计算的开销进一步降低，因为只需要重新计算被驱逐的块

配置和使用

RECOMPUTE是V1的默认抢占模式，无需额外配置。当系统遇到KV缓存空间不足时，会自动触发recompute机制，并输出相应的警告信息 8

Notes

• 传统的CPU交换功能已在V1中被完全移除 9
• 新的KV卸载机制（kv_offloading）提供了更灵活的内存管理选项，但与传统的CPU交换不同 10
• 前缀缓存默认启用（enable_prefix_caching: bool = True） 11

Wiki pages you might want to explore:

• Multimodal Processing Pipeline (vllm-project/vllm)

Citations

File: docs/configuration/optimization.md (L14-18)

```text
WARNING 05-09 00:49:33 scheduler.py:1057 Sequence group 0 is preempted by PreemptionMode.RECOMPUTE mode because there is not enough KV cache space. This can affect the end-to-end performance. Increase gpu_memory_utilization or tensor_parallel_size to provide more KV cache memory. total_cumulative_preemption_cnt=1

While this mechanism ensures system robustness, preemption and recomputation can adversely affect end-to-end latency.

**File:** docs/configuration/optimization.md (L28-29)
```markdown
In vLLM V1, the default preemption mode is `RECOMPUTE` rather than `SWAP`, as recomputation has lower overhead in the V1 architecture.

File: docs/configuration/optimization.md (L32-39)

Chunked prefill allows vLLM to process large prefills in smaller chunks and batch them together with decode requests. This feature helps improve both throughput and latency by better balancing compute-bound (prefill) and memory-bound (decode) operations.

In V1, **chunked prefill is enabled by default whenever possible**. With chunked prefill enabled, the scheduling policy prioritizes decode requests. It batches all pending decode requests before scheduling any prefill operations. When there are available tokens in the `max_num_batched_tokens` budget, it schedules pending prefills. If a pending prefill request cannot fit into `max_num_batched_tokens`, it automatically chunks it.

This policy has two benefits:

- It improves ITL and generation decode because decode requests are prioritized.
- It helps achieve better GPU utilization by locating compute-bound (prefill) and memory-bound (decode) requests to the same batch.

File: docs/design/metrics.md (L521-524)

Later, the concept of prefix caching was introduced, which allowed KV
cache blocks to be shared implicitly. This proved to be a better
option than CPU swapping since blocks can be evicted slowly on demand
and the part of the prompt that was evicted can be recomputed.

File: docs/design/metrics.md (L531-533)

In V1, with prefix caching being better (zero over head) and therefore
on by default, the preemption and recompute strategy should work
better.

File: docs/usage/v1_guide.md (L73-78)

    vLLM V1’s unified scheduler treats both prompt and output tokens the same
    way by using a simple dictionary (e.g., `{request_id: num_tokens}`) to dynamically
    allocate a fixed token budget per request, enabling features like chunked prefills,
    prefix caching, and speculative decoding without a strict separation between prefill
    and decode phases.

File: docs/usage/v1_guide.md (L160-161)

| **GPU <> CPU KV Cache Swapping**            | <nobr>🔴 Removed</nobr>                                                           |
| **Request-level Structured Output Backend** | <nobr>🔴 Removed</nobr>                                                           |

File: tests/v1/kv_connector/unit/test_invalid_blocks_correctness.py (L122-180)

    assert request.status == RequestStatus.RUNNING, (
        f"Request should remain RUNNING for recompute, got {request.status}"
    )

    # 2. num_computed_tokens should be truncated to first invalid block
    expected_truncated_tokens = invalid_block_idx * recompute_scheduler.block_size
    assert request.num_computed_tokens == expected_truncated_tokens, (
        f"num_computed_tokens should be truncated to {expected_truncated_tokens}, "
        f"got {request.num_computed_tokens}"
    )
    assert request.num_computed_tokens < original_num_computed_tokens, (
        "num_computed_tokens should be reduced after invalid block detection"
    )

    # 3. no output should be generated (request is still running)
    # the request should be skipped in the output loop
    assert len(outputs) == 0 or request.request_id not in [
        out.request_id for outs in outputs.values() for out in outs.outputs
    ], "No output should be generated for recompute requests"

    # 4. request should still be in running queue
    assert request in recompute_scheduler.running, (
        "Request should remain in running queue for recomputation"
    )

    # 5. request should still be in scheduler.requests (not deleted)
    assert request.request_id in recompute_scheduler.requests, (
        "Request should not be deleted from scheduler.requests"
    )

    # 6. blocks should NOT be freed - verify blocks are still allocated
    try:
        allocated_blocks = recompute_scheduler.kv_cache_manager.get_block_ids(
            request.request_id
        )
        assert allocated_blocks is not None
        assert len(allocated_blocks[0]) > 0, (
            "Blocks should still be allocated for recomputation"
        )
    except KeyError:
        pytest.fail(
            "Blocks were freed incorrectly! Running requests need their blocks "
            "to recompute invalid portions."
        )

    # 7. verify request can be rescheduled in next step
    scheduler_output_2 = recompute_scheduler.schedule()

    # request should appear in the new schedule to recompute invalid blocks
    scheduled_req_ids = [
        req.request_id for req in scheduler_output_2.scheduled_new_reqs
    ]
    if scheduler_output_2.num_scheduled_tokens:
        scheduled_req_ids.extend(scheduler_output_2.num_scheduled_tokens.keys())

    assert (
        request.request_id in scheduled_req_ids or len(recompute_scheduler.running) > 0
    ), "Request should be reschedulable for recomputation"

File: tests/v1/metrics/test_stats.py (L177-194)

def test_prompt_token_stats_full_local_cache_recompute():
    """Test full local cache triggers last token recomputation.

    When all tokens are cached, the scheduler reduces num_cached_tokens by 1
    to force the model to recompute the last token.
    """
    stats = PromptTokenStats()

    # Case 5: Full local cache (999 cached after reduction, 1 recomputed)
    stats.update_from_output(
        num_cached_tokens=999,
        num_external_computed_tokens=0,
        prompt_len=1000,
    )

    assert stats.computed == 1
    assert stats.local_cache_hit == 1000
    assert stats.recomputed_tokens == 1

简要回答

vLLM V1的RECOMPUTE抢占模式通过前缀缓存（prefix caching）和智能块管理实现低开销的内存回收。当KV缓存空间不足时，系统会驱逐部分缓存块，并在需要时重新计算被驱逐的部分，而不是将它们交换到CPU内存。

---

详细实现

核心机制

RECOMPUTE vs SWAP的区别：

• SWAP模式：将KV缓存块从GPU复制到CPU内存，需要时再复制回来
• RECOMPUTE模式：直接丢弃KV缓存块，需要时重新计算这些块 1

前缀缓存的优势：

• 前缀缓存允许KV缓存块在请求间隐式共享 2
• 块可以按需缓慢驱逐，被驱逐的提示部分可以重新计算 2
• 零开销的设计使得recompute策略更高效 3

实现细节

1. 统一调度器的token预算管理：
V1使用简单字典（如{request_id: num_tokens}）动态分配固定token预算，不再严格分离prefill和decode阶段 4

2. 块驱逐和重新计算：
当检测到无效块时，系统会：

• 截断num_computed_tokens到第一个无效块的位置
• 保持请求在运行队列中，准备重新计算
• 不释放已分配的块，确保重新计算时有足够资源 5

3. 全局缓存命中优化：

• 当所有token都被缓存时，调度器会减少num_cached_tokens 1个token，强制模型重新计算最后一个token 6
• 这确保了系统的正确性和性能平衡

性能优势

低开销的原因：

1. 避免内存拷贝：不需要在GPU和CPU之间传输大量KV缓存数据
2. 利用计算冗余：现代GPU的并行计算能力使得重新计算比内存传输更快
3. 智能缓存策略：前缀缓存确保常用的prompt部分被保留，只重新计算必要的部分

Chunked Prefill的配合：

• V1默认启用chunked prefill，允许将大prefill分解为小块处理 7
• 这使得重新计算的开销进一步降低，因为只需要重新计算被驱逐的块

配置和使用

RECOMPUTE是V1的默认抢占模式，无需额外配置。当系统遇到KV缓存空间不足时，会自动触发recompute机制，并输出相应的警告信息 8

Notes

• 传统的CPU交换功能已在V1中被完全移除 9
• 新的KV卸载机制（kv_offloading）提供了更灵活的内存管理选项，但与传统的CPU交换不同 10
• 前缀缓存默认启用（enable_prefix_caching: bool = True） 11

Wiki pages you might want to explore:

• Multimodal Processing Pipeline (vllm-project/vllm)

Citations

File: docs/configuration/optimization.md (L14-18)

```text
WARNING 05-09 00:49:33 scheduler.py:1057 Sequence group 0 is preempted by PreemptionMode.RECOMPUTE mode because there is not enough KV cache space. This can affect the end-to-end performance. Increase gpu_memory_utilization or tensor_parallel_size to provide more KV cache memory. total_cumulative_preemption_cnt=1

While this mechanism ensures system robustness, preemption and recomputation can adversely affect end-to-end latency.

**File:** docs/configuration/optimization.md (L28-29)
```markdown
In vLLM V1, the default preemption mode is `RECOMPUTE` rather than `SWAP`, as recomputation has lower overhead in the V1 architecture.

File: docs/configuration/optimization.md (L32-39)

Chunked prefill allows vLLM to process large prefills in smaller chunks and batch them together with decode requests. This feature helps improve both throughput and latency by better balancing compute-bound (prefill) and memory-bound (decode) operations.

In V1, **chunked prefill is enabled by default whenever possible**. With chunked prefill enabled, the scheduling policy prioritizes decode requests. It batches all pending decode requests before scheduling any prefill operations. When there are available tokens in the `max_num_batched_tokens` budget, it schedules pending prefills. If a pending prefill request cannot fit into `max_num_batched_tokens`, it automatically chunks it.

This policy has two benefits:

- It improves ITL and generation decode because decode requests are prioritized.
- It helps achieve better GPU utilization by locating compute-bound (prefill) and memory-bound (decode) requests to the same batch.

File: docs/design/metrics.md (L521-524)

Later, the concept of prefix caching was introduced, which allowed KV
cache blocks to be shared implicitly. This proved to be a better
option than CPU swapping since blocks can be evicted slowly on demand
and the part of the prompt that was evicted can be recomputed.

File: docs/design/metrics.md (L531-533)

In V1, with prefix caching being better (zero over head) and therefore
on by default, the preemption and recompute strategy should work
better.

File: docs/usage/v1_guide.md (L73-78)

    vLLM V1’s unified scheduler treats both prompt and output tokens the same
    way by using a simple dictionary (e.g., `{request_id: num_tokens}`) to dynamically
    allocate a fixed token budget per request, enabling features like chunked prefills,
    prefix caching, and speculative decoding without a strict separation between prefill
    and decode phases.

File: docs/usage/v1_guide.md (L160-161)

| **GPU <> CPU KV Cache Swapping**            | <nobr>🔴 Removed</nobr>                                                           |
| **Request-level Structured Output Backend** | <nobr>🔴 Removed</nobr>                                                           |

File: tests/v1/kv_connector/unit/test_invalid_blocks_correctness.py (L122-180)

    assert request.status == RequestStatus.RUNNING, (
        f"Request should remain RUNNING for recompute, got {request.status}"
    )

    # 2. num_computed_tokens should be truncated to first invalid block
    expected_truncated_tokens = invalid_block_idx * recompute_scheduler.block_size
    assert request.num_computed_tokens == expected_truncated_tokens, (
        f"num_computed_tokens should be truncated to {expected_truncated_tokens}, "
        f"got {request.num_computed_tokens}"
    )
    assert request.num_computed_tokens < original_num_computed_tokens, (
        "num_computed_tokens should be reduced after invalid block detection"
    )

    # 3. no output should be generated (request is still running)
    # the request should be skipped in the output loop
    assert len(outputs) == 0 or request.request_id not in [
        out.request_id for outs in outputs.values() for out in outs.outputs
    ], "No output should be generated for recompute requests"

    # 4. request should still be in running queue
    assert request in recompute_scheduler.running, (
        "Request should remain in running queue for recomputation"
    )

    # 5. request should still be in scheduler.requests (not deleted)
    assert request.request_id in recompute_scheduler.requests, (
        "Request should not be deleted from scheduler.requests"
    )

    # 6. blocks should NOT be freed - verify blocks are still allocated
    try:
        allocated_blocks = recompute_scheduler.kv_cache_manager.get_block_ids(
            request.request_id
        )
        assert allocated_blocks is not None
        assert len(allocated_blocks[0]) > 0, (
            "Blocks should still be allocated for recomputation"
        )
    except KeyError:
        pytest.fail(
            "Blocks were freed incorrectly! Running requests need their blocks "
            "to recompute invalid portions."
        )

    # 7. verify request can be rescheduled in next step
    scheduler_output_2 = recompute_scheduler.schedule()

    # request should appear in the new schedule to recompute invalid blocks
    scheduled_req_ids = [
        req.request_id for req in scheduler_output_2.scheduled_new_reqs
    ]
    if scheduler_output_2.num_scheduled_tokens:
        scheduled_req_ids.extend(scheduler_output_2.num_scheduled_tokens.keys())

    assert (
        request.request_id in scheduled_req_ids or len(recompute_scheduler.running) > 0
    ), "Request should be reschedulable for recomputation"

File: tests/v1/metrics/test_stats.py (L177-194)

def test_prompt_token_stats_full_local_cache_recompute():
    """Test full local cache triggers last token recomputation.

    When all tokens are cached, the scheduler reduces num_cached_tokens by 1
    to force the model to recompute the last token.
    """
    stats = PromptTokenStats()

    # Case 5: Full local cache (999 cached after reduction, 1 recomputed)
    stats.update_from_output(
        num_cached_tokens=999,
        num_external_computed_tokens=0,
        prompt_len=1000,
    )

    assert stats.computed == 1
    assert stats.local_cache_hit == 1000
    assert stats.recomputed_tokens == 1

vLLM V1 RECOMPUTE抢占模式完整实现流程

核心流程图

关键数据结构

1. Scheduler类 - 核心调度器 1

class Scheduler:
    def __init__(self, ...):
        self.waiting  # 等待队列
        self.running  # 运行队列  
        self.requests  # 所有请求字典
        self.kv_cache_manager  # KV缓存管理器

2. Request状态 - 请求状态管理 2

class RequestStatus(Enum):
    WAITING = "waiting"
    RUNNING = "running" 
    PREEMPTED = "preempted"
    FINISHED_STOPPED = "finished_stopped"

详细实现流程

1. 请求调度与抢占触发

当KV缓存空间不足时，调度器在schedule()方法中触发抢占： 3

# 尝试分配新块失败时
if new_blocks is None:
    # 选择要抢占的请求
    if self.policy == SchedulingPolicy.PRIORITY:
        preempted_req = max(self.running, key=lambda r: (r.priority, r.arrival_time))
    else:
        preempted_req = self.running.pop()
    
    # 执行抢占
    self._preempt_request(preempted_req, scheduled_timestamp)

2. 抢占实现 - _preempt_request

这是RECOMPUTE模式的核心实现： 4

def _preempt_request(self, request: Request, timestamp: float) -> None:
    assert request.status == RequestStatus.RUNNING
    # 释放KV缓存块
    self.kv_cache_manager.free(request)
    # 重置计算进度
    request.num_computed_tokens = 0
    # 改变状态
    request.status = RequestStatus.PREEMPTED
    # 重新加入等待队列头部
    self.waiting.prepend_request(request)

3. 无效块处理与重新计算

当检测到无效KV块时，系统会截断计算进度并准备重新计算： 5

def _update_requests_with_invalid_blocks(self, requests, invalid_block_ids):
    for request in requests:
        # 找到第一个无效块的位置
        for idx, block_id in enumerate(req_block_ids):
            if block_id in invalid_block_ids:
                # 截断到无效块之前
                request.num_computed_tokens = idx * self.block_size
                # 标记需要重新计算的token数量
                num_affected_tokens = req_num_computed_tokens - request.num_computed_tokens

4. 重新计算验证

测试用例展示了重新计算的关键行为： 6

# 关键断言验证recompute行为:
# 1. 请求保持RUNNING状态
assert request.status == RequestStatus.RUNNING
# 2. num_computed_tokens被截断
assert request.num_computed_tokens == expected_truncated_tokens
# 3. 块不被释放(仍需用于重新计算)
assert len(allocated_blocks[0]) > 0
# 4. 请求仍在running队列中
assert request in recompute_scheduler.running

队列管理机制

V1的统一调度器使用动态token预算管理： 7

• waiting队列: 存储等待调度的请求
• running队列: 存储正在执行的请求
• 动态预算: 使用{request_id: num_tokens}分配token预算

调度优先级： 8

1. 优先处理decode请求
2. 在token预算允许时处理prefill请求
3. 自动chunking大prefill请求

性能优化关键

1. 前缀缓存: 默认启用，允许块共享 9
2. 零开销: 避免GPU-CPU内存拷贝 10
3. 智能截断: 只重新计算必要的部分 11

Notes

• RECOMPUTE是V1默认模式，无需额外配置
• 传统CPU交换功能已被完全移除 12
• 抢占会输出警告信息但保证系统稳定性 13

Wiki pages you might want to explore:

• Engine Architecture (vllm-project/vllm)

Citations

File: vllm/v1/core/sched/scheduler.py (L63-139)

class Scheduler(SchedulerInterface):
    def __init__(
        self,
        vllm_config: VllmConfig,
        kv_cache_config: KVCacheConfig,
        structured_output_manager: StructuredOutputManager,
        block_size: int,
        mm_registry: MultiModalRegistry = MULTIMODAL_REGISTRY,
        include_finished_set: bool = False,
        log_stats: bool = False,
    ) -> None:
        self.vllm_config = vllm_config
        self.scheduler_config = vllm_config.scheduler_config
        self.cache_config = vllm_config.cache_config
        self.lora_config = vllm_config.lora_config
        self.kv_cache_config = kv_cache_config
        self.kv_events_config = vllm_config.kv_events_config
        self.parallel_config = vllm_config.parallel_config
        self.log_stats = log_stats
        self.observability_config = vllm_config.observability_config
        self.kv_metrics_collector: KVCacheMetricsCollector | None = None
        if self.observability_config.kv_cache_metrics:
            self.kv_metrics_collector = KVCacheMetricsCollector(
                self.observability_config.kv_cache_metrics_sample,
            )
        self.structured_output_manager = structured_output_manager
        self.is_encoder_decoder = vllm_config.model_config.is_encoder_decoder

        # include_finished_set controls whether a separate set of finished
        # request ids should be included in the EngineCoreOutputs returned
        # by update_from_outputs(). This is currently used in the multi-engine
        # case to track request lifetimes efficiently.
        self.finished_req_ids_dict: dict[int, set[str]] | None = (
            defaultdict(set) if include_finished_set else None
        )
        self.prev_step_scheduled_req_ids: set[str] = set()

        # Scheduling constraints.
        self.max_num_running_reqs = self.scheduler_config.max_num_seqs
        self.max_num_scheduled_tokens = (
            self.scheduler_config.max_num_scheduled_tokens
            if self.scheduler_config.max_num_scheduled_tokens
            else self.scheduler_config.max_num_batched_tokens
        )
        self.max_model_len = vllm_config.model_config.max_model_len
        self.enable_kv_cache_events = (
            self.kv_events_config is not None
            and self.kv_events_config.enable_kv_cache_events
        )

        # Create KVConnector for the Scheduler. Note that each Worker
        # will have a corresponding KVConnector with Role=WORKER.
        # KV Connector pushes/pull of remote KVs for P/D and offloading.
        self.connector = None
        self.connector_prefix_cache_stats: PrefixCacheStats | None = None
        self.recompute_kv_load_failures = True
        if self.vllm_config.kv_transfer_config is not None:
            assert not self.is_encoder_decoder, (
                "Encoder-decoder models are not currently supported with KV connectors"
            )
            self.connector = KVConnectorFactory.create_connector(
                config=self.vllm_config,
                role=KVConnectorRole.SCHEDULER,
                kv_cache_config=self.kv_cache_config,
            )
            if self.log_stats:
                self.connector_prefix_cache_stats = PrefixCacheStats()
            kv_load_failure_policy = (
                self.vllm_config.kv_transfer_config.kv_load_failure_policy
            )
            self.recompute_kv_load_failures = kv_load_failure_policy == "recompute"

        self.kv_event_publisher = EventPublisherFactory.create(
            self.kv_events_config,
            self.parallel_config.data_parallel_index,
        )
        self.ec_connector = None

File: vllm/v1/core/sched/scheduler.py (L434-480)

            # Schedule newly needed KV blocks for the request.
            with record_function_or_nullcontext("schedule: allocate_slots"):
                while True:
                    new_blocks = self.kv_cache_manager.allocate_slots(
                        request,
                        num_new_tokens,
                        num_lookahead_tokens=self.num_lookahead_tokens,
                    )

                    if new_blocks is not None:
                        # The request can be scheduled.
                        break

                    # The request cannot be scheduled.
                    # Preempt the lowest-priority request.
                    if self.policy == SchedulingPolicy.PRIORITY:
                        preempted_req = max(
                            self.running,
                            key=lambda r: (r.priority, r.arrival_time),
                        )
                        self.running.remove(preempted_req)
                        if preempted_req in scheduled_running_reqs:
                            preempted_req_id = preempted_req.request_id
                            scheduled_running_reqs.remove(preempted_req)
                            token_budget += num_scheduled_tokens.pop(preempted_req_id)
                            req_to_new_blocks.pop(preempted_req_id)
                            scheduled_spec_decode_tokens.pop(preempted_req_id, None)
                            preempted_encoder_inputs = scheduled_encoder_inputs.pop(
                                preempted_req_id, None
                            )
                            if preempted_encoder_inputs:
                                # Restore encoder compute budget if the preempted
                                # request had encoder inputs scheduled in this step.
                                num_embeds_to_restore = sum(
                                    preempted_req.get_num_encoder_embeds(i)
                                    for i in preempted_encoder_inputs
                                )
                                encoder_compute_budget += num_embeds_to_restore
                            req_index -= 1
                    else:
                        preempted_req = self.running.pop()

                    self._preempt_request(preempted_req, scheduled_timestamp)
                    preempted_reqs.append(preempted_req)
                    if preempted_req == request:
                        # No more request to preempt. Cannot schedule this request.
                        break

File: vllm/v1/core/sched/scheduler.py (L912-933)

    def _preempt_request(self, request: Request, timestamp: float) -> None:
        """Preempt a request and put it back to the waiting queue.

        NOTE: The request should be popped from the running queue outside of this
        method.
        """
        assert request.status == RequestStatus.RUNNING, (
            "Only running requests can be preempted"
        )
        self.kv_cache_manager.free(request)
        self.encoder_cache_manager.free(request)
        request.status = RequestStatus.PREEMPTED
        request.num_computed_tokens = 0
        if request.spec_token_ids:
            request.spec_token_ids = []
        request.num_preemptions += 1
        if self.log_stats:
            request.record_event(EngineCoreEventType.PREEMPTED, timestamp)

        # Put the request back to the waiting queue.
        self.waiting.prepend_request(request)

File: vllm/v1/core/sched/scheduler.py (L2038-2145)

    def _update_requests_with_invalid_blocks(
        self,
        requests: Iterable[Request],
        invalid_block_ids: set[int],
        evict_blocks: bool = True,
    ) -> tuple[set[str], int, set[int]]:
        """
        Identify and update requests affected by invalid KV cache blocks.

        This method scans the given requests, detects those with invalid blocks
        and adjusts their `num_computed_tokens` to the longest valid prefix.
        For observability, it also accumulates the total number of tokens that
        will need to be recomputed across all affected requests.

        Args:
            requests: The set of requests to scan for invalid blocks.
            invalid_block_ids: IDs of invalid blocks.
            evict_blocks: Whether to collect blocks for eviction (False for
                async requests which aren't cached yet).

        Returns:
            tuple:
                - affected_req_ids (set[str]): IDs of requests impacted by
                invalid blocks.
                - total_affected_tokens (int): Total number of tokens that must
                be recomputed across all affected requests.
                - blocks_to_evict (set[int]): Block IDs to evict from cache,
                including invalid blocks and downstream dependent blocks.
        """
        affected_req_ids: set[str] = set()
        total_affected_tokens = 0
        blocks_to_evict: set[int] = set()
        # If a block is invalid and shared by multiple requests in the batch,
        # these requests must be rescheduled, but only the first will recompute
        # it. This set tracks blocks already marked for recomputation.
        marked_invalid_block_ids: set[int] = set()
        for request in requests:
            is_affected = False
            marked_invalid_block = False
            req_id = request.request_id
            # TODO (davidb): add support for hybrid memory allocator
            (req_block_ids,) = self.kv_cache_manager.get_block_ids(req_id)
            # We iterate only over blocks that may contain externally computed
            # tokens
            if request.status == RequestStatus.WAITING_FOR_REMOTE_KVS:
                # Async loading. If num_computed_tokens is set it implies we
                # already processed some block failures for it in a prior step
                req_num_computed_tokens = (
                    request.num_computed_tokens
                    if req_id in self.failed_recving_kv_req_ids
                    else len(req_block_ids) * self.block_size
                )
            else:
                # Sync loading. num_computed_tokens includes new tokens
                req_num_computed_tokens = request.num_cached_tokens

            req_num_computed_blocks = (
                req_num_computed_tokens + self.block_size - 1
            ) // self.block_size
            for idx, block_id in zip(range(req_num_computed_blocks), req_block_ids):
                if block_id not in invalid_block_ids:
                    continue

                is_affected = True

                if block_id in marked_invalid_block_ids:
                    # This invalid block is shared with a previous request
                    # and was already marked for recomputation.
                    # This means this request can still consider this block
                    # as computed when rescheduled.
                    # Currently this only applies to sync loading; Async
                    # loading does not yet support block sharing
                    continue

                marked_invalid_block_ids.add(block_id)

                if marked_invalid_block:
                    # This request has already marked an invalid block for
                    # recomputation and updated its num_computed_tokens.
                    continue

                marked_invalid_block = True
                # Truncate the computed tokens at the first failed block
                request.num_computed_tokens = idx * self.block_size
                num_affected_tokens = (
                    req_num_computed_tokens - request.num_computed_tokens
                )
                total_affected_tokens += num_affected_tokens
                request.num_external_computed_tokens -= num_affected_tokens
                # collect invalid block and all downstream dependent blocks
                if evict_blocks:
                    blocks_to_evict.update(req_block_ids[idx:])

            if is_affected:
                if not marked_invalid_block:
                    # All invalid blocks of this request are shared with
                    # previous requests and will be recomputed by them.
                    # Revert to considering only cached tokens as computed.
                    # Currently this only applies to sync loading; Async
                    # loading does not yet support block sharing
                    total_affected_tokens += (
                        request.num_computed_tokens - request.num_cached_tokens
                    )
                    request.num_computed_tokens = request.num_cached_tokens

                affected_req_ids.add(request.request_id)

        return affected_req_ids, total_affected_tokens, blocks_to_evict

File: tests/v1/kv_connector/unit/test_invalid_blocks_correctness.py (L122-180)

    assert request.status == RequestStatus.RUNNING, (
        f"Request should remain RUNNING for recompute, got {request.status}"
    )

    # 2. num_computed_tokens should be truncated to first invalid block
    expected_truncated_tokens = invalid_block_idx * recompute_scheduler.block_size
    assert request.num_computed_tokens == expected_truncated_tokens, (
        f"num_computed_tokens should be truncated to {expected_truncated_tokens}, "
        f"got {request.num_computed_tokens}"
    )
    assert request.num_computed_tokens < original_num_computed_tokens, (
        "num_computed_tokens should be reduced after invalid block detection"
    )

    # 3. no output should be generated (request is still running)
    # the request should be skipped in the output loop
    assert len(outputs) == 0 or request.request_id not in [
        out.request_id for outs in outputs.values() for out in outs.outputs
    ], "No output should be generated for recompute requests"

    # 4. request should still be in running queue
    assert request in recompute_scheduler.running, (
        "Request should remain in running queue for recomputation"
    )

    # 5. request should still be in scheduler.requests (not deleted)
    assert request.request_id in recompute_scheduler.requests, (
        "Request should not be deleted from scheduler.requests"
    )

    # 6. blocks should NOT be freed - verify blocks are still allocated
    try:
        allocated_blocks = recompute_scheduler.kv_cache_manager.get_block_ids(
            request.request_id
        )
        assert allocated_blocks is not None
        assert len(allocated_blocks[0]) > 0, (
            "Blocks should still be allocated for recomputation"
        )
    except KeyError:
        pytest.fail(
            "Blocks were freed incorrectly! Running requests need their blocks "
            "to recompute invalid portions."
        )

    # 7. verify request can be rescheduled in next step
    scheduler_output_2 = recompute_scheduler.schedule()

    # request should appear in the new schedule to recompute invalid blocks
    scheduled_req_ids = [
        req.request_id for req in scheduler_output_2.scheduled_new_reqs
    ]
    if scheduler_output_2.num_scheduled_tokens:
        scheduled_req_ids.extend(scheduler_output_2.num_scheduled_tokens.keys())

    assert (
        request.request_id in scheduled_req_ids or len(recompute_scheduler.running) > 0
    ), "Request should be reschedulable for recomputation"

File: docs/configuration/optimization.md (L14-18)

```text
WARNING 05-09 00:49:33 scheduler.py:1057 Sequence group 0 is preempted by PreemptionMode.RECOMPUTE mode because there is not enough KV cache space. This can affect the end-to-end performance. Increase gpu_memory_utilization or tensor_parallel_size to provide more KV cache memory. total_cumulative_preemption_cnt=1

While this mechanism ensures system robustness, preemption and recomputation can adversely affect end-to-end latency.

**File:** docs/configuration/optimization.md (L32-39)
```markdown
Chunked prefill allows vLLM to process large prefills in smaller chunks and batch them together with decode requests. This feature helps improve both throughput and latency by better balancing compute-bound (prefill) and memory-bound (decode) operations.

In V1, **chunked prefill is enabled by default whenever possible**. With chunked prefill enabled, the scheduling policy prioritizes decode requests. It batches all pending decode requests before scheduling any prefill operations. When there are available tokens in the `max_num_batched_tokens` budget, it schedules pending prefills. If a pending prefill request cannot fit into `max_num_batched_tokens`, it automatically chunks it.

This policy has two benefits:

- It improves ITL and generation decode because decode requests are prioritized.
- It helps achieve better GPU utilization by locating compute-bound (prefill) and memory-bound (decode) requests to the same batch.

File: docs/design/metrics.md (L531-533)

In V1, with prefix caching being better (zero over head) and therefore
on by default, the preemption and recompute strategy should work
better.