# V1 Chunked Prefill Scheduling Policy: how prefill would be scheduled? **URL:** \ **Category:** Scheduling\ **Created:** [March 20, 2025, 11:22pm UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146 "2025-03-20T23:22:09Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![liuzijing2014](https://avatars.discourse-cdn.com/v4/letter/l/bb73d2/32.png) [@liuzijing2014](https://discuss.vllm.ai/u/liuzijing2014)\ **Post date:** [March 20, 2025, 11:22pm UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/1 "2025-03-20T23:22:09Z")
Hi guys, some question about V1 chunked prefils scheduling policy: it seems that it would prioritize decode at first. 1. After we schedule as much as “decode”, how do we determine which prefill to be scheduled first? Is it first come first server or shorter prefill comes firsrt? 2. If it is first come first serve, does it mean we could at most have 2 partial prefills? 1 from the previous iteration that is chunked, and another one from the current iteration that we just chunked to fill into the batch. 3. If it is shorter comes first, how do we prevent a long prefill gets waiting forever? ---
**Author:** ![comaniac](https://yyz2.discourse-cdn.com/flex036/user_avatar/discuss.vllm.ai/comaniac/32/5_2.png) [@comaniac](https://discuss.vllm.ai/u/comaniac)\ **Post date:** [March 20, 2025, 11:27pm UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/2 "2025-03-20T23:27:01Z")
1. It’s currently FCFS, but we plan to support more scheduling policies. 2. Currently no. We will finish prefill of the current request and start prefilling the next one. However, if there are still token budgets after scheduling the rest prompt tokens of the current request, we can batch the next prefill request. For example, assuming the chunk size is 10: Time 1: - Req 1 comes with 14 prompt tokens - Schedule a batch with 1-10 tokens of Req 1. Time 2: - Req 2 comes with 10 prompt tokens - Schedule a batch with 11-14 tokens of Req 1, plus 1-6 tokens of Req 2. Time 3: - Schedule a batch with 1 decode token of Req 1, plus 7-10 tokens of Req 2. 1. The current policy (FCFS) won’t have starvation. ---
**Author:** ![liuzijing2014](https://avatars.discourse-cdn.com/v4/letter/l/bb73d2/32.png) [@liuzijing2014](https://discuss.vllm.ai/u/liuzijing2014)\ **Post date:** [March 20, 2025, 11:47pm UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/3 "2025-03-20T23:47:54Z")
cc @comaniac Thanks for the explanation! I couldn’t think of an example where at a given time step: there would be more than 2 partial prefills? ---
**Author:** ![comaniac](https://yyz2.discourse-cdn.com/flex036/user_avatar/discuss.vllm.ai/comaniac/32/5_2.png) [@comaniac](https://discuss.vllm.ai/u/comaniac)\ **Post date:** [March 20, 2025, 11:52pm UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/4 "2025-03-20T23:52:57Z")
In the current policy no. Another example in Time 2: - Req 2 comes with 3 (\<10) prompt tokens. - Req 3 comes with 10 prompt tokens. - Schedule a batch with 11-14 tokens of Req 1, plus 1-3 tokens of Req 2, plus 1-3 tokens of Req 3. In this case we still have 2 partial prefills (Req 1 and Req 3). As a result, it will never have more than 2 patrial prefills. ---
**Author:** ![comaniac](https://yyz2.discourse-cdn.com/flex036/user_avatar/discuss.vllm.ai/comaniac/32/5_2.png) [@comaniac](https://discuss.vllm.ai/u/comaniac)\ **Post date:** [March 20, 2025, 11:56pm UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/5 "2025-03-20T23:56:52Z")
Oh actually it might be possible with multi-modality inputs: Assuming a prompt with images looks as follows: ```auto 10 text tokens + 100 image tokens + 20 text tokens ``` In this case after scheduling the first 10 text tokens, we have to schedule an encoder request to encode the 100 images tokens. However, if there are too many images already so that we don’t have encoder budget to schedule this image, then we cannot continue prefilling this request. In this case, we will pause this request and schedule the text tokens of a new prefill request. As a result, we will have more than one partial prefills. ---
**Author:** ![liuzijing2014](https://avatars.discourse-cdn.com/v4/letter/l/bb73d2/32.png) [@liuzijing2014](https://discuss.vllm.ai/u/liuzijing2014)\ **Post date:** [March 21, 2025, 1:07am UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/6 "2025-03-21T01:07:43Z")
Make sense, thank you! ---
**Author:** ![RookieChenTaoYu](https://yyz2.discourse-cdn.com/flex036/user_avatar/discuss.vllm.ai/rookiechentaoyu/32/37_2.png) [@RookieChenTaoYu](https://discuss.vllm.ai/u/RookieChenTaoYu)\ **Post date:** [March 23, 2025, 7:54am UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/7 "2025-03-23T07:54:54Z")
Thanks for your examples, but I have a question here. Considering your example here, If using the `step_with_batch_queue()` function in `/vllm/v1/engine/core.py`, And I have two requests in `waiting` queue: `[R1 (14 tokens), R2 (10 tokens)]`, the `token_budget` is `10`. And `step_with_batch_queue()` says that it won’t execute the `update_from_output()` until all the requests are scheduled. Let’s assume the `batch_queue` is large enough. Time 1: - Schedule the 1-10 tokens in `R1`, because `token_budget` (10 tokens) constraint. And then, the `R1` moved from `waiting` queue to the `running` queue. In the meantime add the `R1` into `scheduled_req_ids` which recording the request until call the `update_from_output` which will remove requests from the `scheduled_req_ids`. So now the `scheduled_req_ids` is `{R1}` - After scheduling successfully, the `batch_queue` become `[R1 (10 tokens)]`, the `running` queue is `[R1]`, the `waiting` queue is `[R2]`. Time 2: - Because there exists unscheduled request `R2` (10 tokens), so instead of waiting the `model_executor` to output `model_output`, the `step_with_batch_queue()` will decide to schedule the `R2` to the `running`. And then add the `R2` to `batch_queue`. - After scheduling, the `batch_queue` is `[R1 (10 tokens), R2 (10 tokens)]`, and the `running` queue is also `[R1, R2]`, the `scheduled_req_ids` is `{R1, R2}`, the `waiting` is `[]` (i.e. empty). Time 3: - At this time, the `scheduled_req_ids = {R1, R2}`, so `step_with_batch_queue()` will block and waiting for the `model_output`. - Once the `model_output` is available, we call `update_from_output()` and remove the `R1` from `scheduled_req_ids`, the `running` queue will remain `[R1, R2]`, but the `scheduled_req_ids` become `{R2}`, and `waiting` is remain empty. Time 4: - Because after output the first `R1` with 10 tokens, the `R1` is not in the `scheduled_req_ids`, so instead of waiting the `model_executor` to output `R2`, the `step_with_batch_queue()` will schedule the `R1` with its left 4 tokens. Then add the `R1` to `scheduled_req_ids` also to the `batch_queue`. - **It’s worth to notice that** in this time, the `running` queue is `[R1, R2]`, but the batch\_queue is `[R2 (10 tokens), R1 (4 tokens)]`. So we can see that the internal order of `running` queue and `batch_queue` is not same. (i.e the schedule priority of `R1` is larger than `R2`, but the execute order is not same in this time point) Time 5: - The `R2` finished in `batch_queue`, and prepare to schedule the one decode token of `R2` … So in this case, can there be multiple chunked prefill in different batch? Simply, like the `R1` has 15 tokens, `R2` has 15 tokens, `R3` has 15 tokens. They are all in the `waiting` queue, the `token_budget` is 10, and after multiple scheduling in `step_with_batch_queue()`, there will be 3 partial prefills in different batches at `batch_queue`: `[R1 (10), R2 (10), R3 (10)]`? And I agree that there are at most 2 partial prefills in the same batch like what you said. So whether your example is specify the `setp()` method in `core.py`, not the `step_with_batch_queue()` method? ---
**Author:** ![comaniac](https://yyz2.discourse-cdn.com/flex036/user_avatar/discuss.vllm.ai/comaniac/32/5_2.png) [@comaniac](https://discuss.vllm.ai/u/comaniac)\ **Post date:** [March 23, 2025, 5:55pm UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/8 "2025-03-23T17:55:01Z")
Yes you are absolutely right. I didn’t cover the cases with batch queue, because it is only used when pipeline parallelism is enabled. When PP is enabled and batch queue is used, then we may have many partial prefill requests on the fly. ---
**Author:** ![RookieChenTaoYu](https://yyz2.discourse-cdn.com/flex036/user_avatar/discuss.vllm.ai/rookiechentaoyu/32/37_2.png) [@RookieChenTaoYu](https://discuss.vllm.ai/u/RookieChenTaoYu)\ **Post date:** [March 25, 2025, 8:03am UTC](https://discuss.vllm.ai/t/v1-chunked-prefill-scheduling-policy-how-prefill-would-be-scheduled/146/9 "2025-03-25T08:03:35Z")
Thanks very much for your explanation