Chunked Prefill Scheduling Alongside Decode

MediumLLMs & GenAI

Problem statement

In modern LLM serving systems, there are two key operations: prefill (processing the input prompt tokens) and decode (generating output tokens one at a time). Long prefill requests can block ongoing decode requests, increasing generation latency. Chunked prefill solves this by breaking large prefill requests into smaller chunks and scheduling them alongside decode tokens within the same batch, respecting a per-step token budget.

Implement a function chunked_prefill_schedule that simulates this scheduling strategy.

Inputs:

  • prefill_requests: A list of dicts, each with keys 'id' (string), 'prompt_tokens' (int, total tokens to prefill), and 'decode_tokens' (int, number of decode steps needed after prefill completes).
  • decode_requests: A list of dicts, each with keys 'id' (string) and 'remaining_decode' (int, remaining decode tokens to generate).
  • max_batch_tokens: An int representing the maximum number of tokens that can be processed in one step.
  • max_chunk_size: An int representing the maximum number of prefill tokens that can be processed as a single chunk.

Scheduling Rules (per step):

  1. Active decode requests are scheduled first. Each decode request consumes exactly 1 token per step.
  2. Any remaining token budget is used to schedule prefill chunks from the front of the prefill queue. Multiple prefill requests can be chunked within the same step if budget allows.
  3. When a prefill request finishes all its prompt tokens, it joins the active decode pool starting from the next step (only if its decode_tokens > 0).
  4. Decode requests that have exhausted their remaining tokens are removed.
  5. Simulation ends when no prefill or decode work remains.

Return: A list of dicts, one per step, each containing:

  • 'step': Step index (starting from 0)
  • 'prefill_chunks': List of tuples (request_id, chunk_size)
  • 'decode_ids': List of request IDs being decoded this step
  • 'total_tokens': Total tokens processed this step

Precise rules:

  • Decode: walk the active decode list in order and give each request 1 token while the step budget allows; requests that do not fit wait for the next step in the same order.
  • Prefill: while budget remains, take the request at the front of the queue and schedule a chunk of min(remaining prompt tokens, max_chunk_size, remaining budget). A request gets at most one chunk per step. If the chunk finishes the request, remove it and continue with the next request in the queue; otherwise stop prefilling for this step.
  • The next step's active decode list is the unfinished carried-over decodes (in order) followed by the requests whose prefill finished this step (in completion order).
  • If both inputs are empty, return [].

Example

Input:

prefill_requests = [{'id': 'P1', 'prompt_tokens': 10, 'decode_tokens': 1}]
decode_requests = [{'id': 'D1', 'remaining_decode': 3}]
max_batch_tokens = 8, max_chunk_size = 4

Output:

[{'step': 0, 'prefill_chunks': [('P1', 4)], 'decode_ids': ['D1'], 'total_tokens': 5},
 {'step': 1, 'prefill_chunks': [('P1', 4)], 'decode_ids': ['D1'], 'total_tokens': 5},
 {'step': 2, 'prefill_chunks': [('P1', 2)], 'decode_ids': ['D1'], 'total_tokens': 3},
 {'step': 3, 'prefill_chunks': [], 'decode_ids': ['P1'], 'total_tokens': 1}]

Reasoning: Step 0: D1 takes 1 token (decode), leaving 7 budget. P1 is chunked to min(10,4,7)=4 tokens. Total=5. Step 1: D1 takes 1, P1 gets another chunk of 4 (6 remaining). Total=5. Step 2: D1 takes 1 (last decode), P1 gets remaining 2 tokens, completing prefill. Total=3. Step 3: P1 has now joined the decode pool with 1 token to generate. Total=1. D1 finished after step 2, P1 finishes decoding at step 3.

Show hint

Which kind of work in an LLM step is latency-critical for users already receiving tokens, and should therefore claim the budget first?

Relevant roles: LLM Engineer, MLOps Engineer, AI Engineer and Gen AI Engineer.

Related free problems