aiml

Lesson 9 of 20Module 3

Balance long-prompt prefill against streaming latency

Schedule prompt chunks around active decode work. Compare modeled token budgets with a real cached-forward experiment and explain added overhead.

Prerequisites

Python, basic causal attention, and the preceding inference lessons.

By the end, you can

  • Balance long-prompt prefill against streaming latency.
  • Explain how chunk size trades long-prompt first-token delay against gaps in active streams.
  • Compare long-prompt TTFT with the gaps experienced by active decodes.
Runtime
Python 3.12+
Dependencies
Standard library only

Lab code, tests and fixtures (ZIP, 107 KB)Quiz check your understanding

Progress is saved in this browser.

When you need this. A retrieval request brings a long source file while other users are still receiving completions. If the server processes the whole new prompt in one step, their next tokens can pause. Set a prefill token budget and check who waits.

What you run. A scheduler model, plus linked timings from a real model that runs chunked forwards. Only the scheduler model interleaves users; the real model run serves one request alone.

This lesson builds on schedule requests between decode iterations.

Schedule prompt chunks around decodes

Chunked prefill divides a prompt’s forward processing into segments while retaining its growing KV cache. In a scheduler, those segments can share iterations with active decodes. The token budget limits how much work the scheduler admits to an iteration; it does not fix how long that iteration takes.

Smaller chunks give the scheduler more chances to fit in decodes, but each chunk adds launch and scheduling overhead. They can also delay the long request’s own first token. The real model run processes chunks one after another with no other users. It shows cache continuation and chunk overhead; the scheduler experiment shows interleaving.

Pending promptToken budgetDecode and prefillprompt workbudgeted workremaining workPending promptToken budgetDecode and prefillprompt workbudgeted workremaining work
The return path represents state used by the next operation; the article distinguishes actual model state from the lab’s inspectable data structures.

ChunkedPrefillScheduler spends its iteration budget on active decodes and pending prompt chunks. live_inference.py in the first lab performs real chunked forwards with retained model cache. Check which execution mode produced a number before you interpret it.

The scheduling fixture has 4 active chat streams, a 256-token new chat prompt and a 100,000-token document prompt. In chunked mode, the scheduler gives each active decode one token of the iteration budget and fills the rest with pending prefill. Track how far the document has progressed and how long the chat streams wait between tokens.

Compare prefill budgets

Download the lab from this page, extract it, and run these commands from its directory. python3 lab.py runs the scheduler model locally. It does not download a model or call a paid API.

Run the local analysis and checksTerminal · bash
python3 lab.py
python3 -m unittest -v test_lab.py
Read lab.py
lab.pySource · pythonDownload
from __future__ import annotations

from dataclasses import dataclass, field
import json
from typing import Literal


@dataclass
class InferenceRequest:
    request_id: str
    prompt_tokens: int
    max_new_tokens: int
    arrival_ms: float = 0.0
    prefilled_tokens: int = 0
    generated_tokens: int = 0
    first_token_ms: float | None = None
    completion_ms: float | None = None
    decode_step_timestamps_ms: list[float] = field(default_factory=list)

    @property
    def is_prefill_complete(self) -> bool:
        return self.prefilled_tokens >= self.prompt_tokens

    @property
    def is_finished(self) -> bool:
        return self.is_prefill_complete and self.generated_tokens >= self.max_new_tokens


def estimate_step_latency_ms(
    decode_tokens: int,
    prefill_chunks: list[tuple[int, int]],
    base_weight_read_ms: float = 14.0,
    compute_ms_per_token: float = 0.0085,
    kv_attend_ms_per_1k_tokens: float = 0.00008,
    ridge_tokens: int = 128,
) -> float:
    """Estimate one forward-pass step duration on a tensor-parallel GPU node.

    - base_weight_read_ms: HBM weight-streaming floor paid once per forward pass.
    - compute_ms_per_token: GEMM compute cost for tokens beyond the roofline ridge point.
    - kv_attend_ms_per_1k_tokens: GQA causal KV attention cost per prefill token
      multiplied by its effective prefix length in thousands of tokens.
    """
    if decode_tokens < 0:
        raise ValueError("decode_tokens must be non-negative")
    total_prefill = sum(chunk_len for _, chunk_len in prefill_chunks)
    total_tokens = decode_tokens + total_prefill
    if total_tokens == 0:
        return 0.0

    extra_compute_tokens = max(0, total_tokens - ridge_tokens)
    gemm_ms = extra_compute_tokens * compute_ms_per_token

    attention_ms = 0.0
    for start_pos, chunk_len in prefill_chunks:
        avg_context_len = start_pos + (chunk_len / 2.0)
        attention_ms += (
            chunk_len * (avg_context_len / 1000.0) * kv_attend_ms_per_1k_tokens
        )

    decode_kv_ms = decode_tokens * 0.035
    return round(base_weight_read_ms + gemm_ms + attention_ms + decode_kv_ms, 4)


class ChunkedPrefillScheduler:
    """Step-level simulator comparing monolithic prefill vs Sarathi-style chunked prefill."""

    def __init__(
        self,
        mode: Literal["monolithic", "chunked"] = "chunked",
        token_budget: int = 2048,
        tpot_slo_ms: float = 50.0,
    ) -> None:
        if mode not in ("monolithic", "chunked"):
            raise ValueError(f"Unsupported mode: {mode}")
        if token_budget <= 0:
            raise ValueError("token_budget must be positive")
        self.mode = mode
        self.token_budget = token_budget
        self.tpot_slo_ms = tpot_slo_ms

    def run(self, requests: list[InferenceRequest]) -> dict[str, object]:
        cloned = [
            InferenceRequest(
                request_id=r.request_id,
                prompt_tokens=r.prompt_tokens,
                max_new_tokens=r.max_new_tokens,
                arrival_ms=r.arrival_ms,
                prefilled_tokens=r.prefilled_tokens,
                generated_tokens=r.generated_tokens,
                first_token_ms=r.first_token_ms,
                decode_step_timestamps_ms=list(r.decode_step_timestamps_ms),
            )
            for r in requests
        ]

        clock_ms = 0.0
        steps_log: list[dict[str, object]] = []

        while not all(r.is_finished for r in cloned):
            arrived = [
                r for r in cloned if r.arrival_ms <= clock_ms and not r.is_finished
            ]
            if not arrived:
                next_arrival = min(r.arrival_ms for r in cloned if not r.is_finished)
                clock_ms = next_arrival
                arrived = [
                    r for r in cloned if r.arrival_ms <= clock_ms and not r.is_finished
                ]

            active_decodes = [r for r in arrived if r.is_prefill_complete]
            pending_prefills = [r for r in arrived if not r.is_prefill_complete]

            scheduled_decodes: list[InferenceRequest] = []
            scheduled_prefills: list[tuple[InferenceRequest, int, int]] = []

            if self.mode == "monolithic" and pending_prefills:
                target = pending_prefills[0]
                remaining = target.prompt_tokens - target.prefilled_tokens
                scheduled_prefills.append((target, target.prefilled_tokens, remaining))
            else:
                if len(active_decodes) > self.token_budget:
                    raise ValueError(
                        f"Active decode count ({len(active_decodes)}) exceeds token_budget ({self.token_budget})"
                    )
                scheduled_decodes = list(active_decodes)
                remaining_budget = self.token_budget - len(scheduled_decodes)

                # Prioritize newly arrived short prefills at chunk boundaries so 100K prompts do not head-of-line block them
                ordered_prefills = sorted(
                    pending_prefills,
                    key=lambda r: (r.prompt_tokens - r.prefilled_tokens, r.arrival_ms),
                )
                for req in ordered_prefills:
                    if remaining_budget <= 0:
                        break
                    need = req.prompt_tokens - req.prefilled_tokens
                    take = min(need, remaining_budget)
                    scheduled_prefills.append((req, req.prefilled_tokens, take))
                    remaining_budget -= take

            step_ms = estimate_step_latency_ms(
                decode_tokens=len(scheduled_decodes),
                prefill_chunks=[
                    (start, length) for _, start, length in scheduled_prefills
                ],
            )
            clock_ms = round(clock_ms + step_ms, 4)

            for req in scheduled_decodes:
                req.generated_tokens += 1
                req.decode_step_timestamps_ms.append(clock_ms)
                if req.first_token_ms is None:
                    req.first_token_ms = clock_ms
                if req.is_finished:
                    req.completion_ms = clock_ms

            for req, _, chunk_len in scheduled_prefills:
                req.prefilled_tokens += chunk_len
                if req.is_prefill_complete:
                    req.generated_tokens += 1
                    req.decode_step_timestamps_ms.append(clock_ms)
                    req.first_token_ms = clock_ms
                    if req.is_finished:
                        req.completion_ms = clock_ms

            steps_log.append(
                {
                    "step_index": len(steps_log),
                    "clock_ms": clock_ms,
                    "step_ms": step_ms,
                    "decode_tokens": len(scheduled_decodes),
                    "prefill_tokens": sum(
                        length for _, _, length in scheduled_prefills
                    ),
                }
            )

        all_itls: list[float] = []
        per_request: dict[str, dict[str, object]] = {}
        for req in cloned:
            stamps = req.decode_step_timestamps_ms
            itls = [round(stamps[i] - stamps[i - 1], 4) for i in range(1, len(stamps))]
            if req.request_id.startswith("chat-"):
                all_itls.extend(itls)
            per_request[req.request_id] = {
                "prompt_tokens": req.prompt_tokens,
                "generated_tokens": req.generated_tokens,
                "ttft_ms": (
                    round(req.first_token_ms - req.arrival_ms, 2)
                    if req.first_token_ms is not None
                    else None
                ),
                "completion_ms": round(req.completion_ms or 0.0, 2),
                "max_itl_ms": round(max(itls), 2) if itls else 0.0,
                "mean_itl_ms": round(sum(itls) / len(itls), 2) if itls else 0.0,
            }

        max_chat_itl = round(max(all_itls), 2) if all_itls else 0.0
        mean_chat_itl = round(sum(all_itls) / len(all_itls), 2) if all_itls else 0.0
        return {
            "mode": self.mode,
            "token_budget": self.token_budget,
            "tpot_slo_ms": self.tpot_slo_ms,
            "total_steps": len(steps_log),
            "total_time_ms": round(clock_ms, 2),
            "max_itl_ms": max_chat_itl,
            "mean_itl_ms": mean_chat_itl,
            "short_chat_ttft_ms": per_request.get("chat-5", {}).get("ttft_ms"),
            "doc_100k_ttft_ms": per_request.get("doc-100k", {}).get("ttft_ms"),
            "tpot_slo_met": max_chat_itl <= self.tpot_slo_ms,
            "requests": per_request,
        }


def build_default_workload() -> list[InferenceRequest]:
    """Four active chat decode streams, an arriving 100K document prompt, and a short chat arriving at 10ms."""
    return [
        InferenceRequest(
            request_id=f"chat-{i}",
            prompt_tokens=512,
            max_new_tokens=60,
            arrival_ms=0.0,
            prefilled_tokens=512,
            generated_tokens=1,
            first_token_ms=0.0,
            decode_step_timestamps_ms=[0.0],
        )
        for i in range(1, 5)
    ] + [
        InferenceRequest(
            request_id="doc-100k",
            prompt_tokens=100_000,
            max_new_tokens=8,
            arrival_ms=0.0,
        ),
        InferenceRequest(
            request_id="chat-5",
            prompt_tokens=256,
            max_new_tokens=16,
            arrival_ms=10.0,
        ),
    ]


def simulate_long_prompt_arrival(
    token_budget: int = 2048, tpot_slo_ms: float = 50.0
) -> dict[str, object]:
    workload = build_default_workload()
    monolithic = ChunkedPrefillScheduler(
        mode="monolithic", token_budget=token_budget, tpot_slo_ms=tpot_slo_ms
    ).run(workload)
    chunked = ChunkedPrefillScheduler(
        mode="chunked", token_budget=token_budget, tpot_slo_ms=tpot_slo_ms
    ).run(workload)

    budget_sweep = []
    for budget in (512, 1024, 2048, 4096, 8192):
        res = ChunkedPrefillScheduler(
            mode="chunked", token_budget=budget, tpot_slo_ms=tpot_slo_ms
        ).run(workload)
        budget_sweep.append(
            {
                "token_budget": budget,
                "num_prefill_chunks": (100_000 + (budget - 5) - 1) // (budget - 5),
                "max_itl_ms": res["max_itl_ms"],
                "mean_itl_ms": res["mean_itl_ms"],
                "short_chat_ttft_ms": res["short_chat_ttft_ms"],
                "doc_100k_ttft_ms": res["doc_100k_ttft_ms"],
                "tpot_slo_met": res["tpot_slo_met"],
            }
        )

    return {
        "workload": {
            "active_chat_streams": 4,
            "arriving_short_chat_tokens": 256,
            "long_prompt_tokens": 100_000,
            "tpot_slo_ms": tpot_slo_ms,
        },
        "monolithic": monolithic,
        "chunked_2048": chunked,
        "stall_reduction_factor": round(
            monolithic["max_itl_ms"] / chunked["max_itl_ms"], 2
        ),
        "budget_sweep": budget_sweep,
    }


def main() -> None:
    report = simulate_long_prompt_arrival(token_budget=2048, tpot_slo_ms=50.0)
    print(
        json.dumps(
            {
                "execution_mode": "CPU algorithm with controlled inputs; any latency/capacity coefficients are assumptions",
                **report,
            },
            indent=2,
        )
    )


if __name__ == "__main__":
    main()

In the scheduler model, chunking makes the long request wait longer for its first token so that active decodes get steadier service. In the recorded budget sweep, 2048 is the largest budget that keeps the maximum gap under the 50 ms target; smaller budgets push the document’s first token later.

QuantityRecorded value
Monolithic maximum gap (ms, modeled)1292.21
Chunked maximum gap (ms, modeled)46.63
Monolithic long-prompt TTFT (ms, modeled)1262.91
Chunked long-prompt TTFT (ms, modeled)1907.21
Inspect the complete local result
Recorded local resultRecorded output · jsonDownload
{
  "execution_mode": "CPU algorithm with controlled inputs; any latency/capacity coefficients are assumptions",
  "workload": {
    "active_chat_streams": 4,
    "arriving_short_chat_tokens": 256,
    "long_prompt_tokens": 100000,
    "tpot_slo_ms": 50.0
  },
  "monolithic": {
    "mode": "monolithic",
    "token_budget": 2048,
    "tpot_slo_ms": 50.0,
    "total_steps": 61,
    "total_time_ms": 2113.03,
    "max_itl_ms": 1292.21,
    "mean_itl_ms": 34.52,
    "short_chat_ttft_ms": 1268.0,
    "doc_100k_ttft_ms": 1262.91,
    "tpot_slo_met": false,
    "requests": {
      "chat-1": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2113.03,
        "max_itl_ms": 1292.21,
        "mean_itl_ms": 35.81
      },
      "chat-2": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2113.03,
        "max_itl_ms": 1292.21,
        "mean_itl_ms": 35.81
      },
      "chat-3": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2113.03,
        "max_itl_ms": 1292.21,
        "mean_itl_ms": 35.81
      },
      "chat-4": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2113.03,
        "max_itl_ms": 1292.21,
        "mean_itl_ms": 35.81
      },
      "doc-100k": {
        "prompt_tokens": 100000,
        "generated_tokens": 8,
        "ttft_ms": 1262.91,
        "completion_ms": 1377.47,
        "max_itl_ms": 29.3,
        "mean_itl_ms": 16.37
      },
      "chat-5": {
        "prompt_tokens": 256,
        "generated_tokens": 16,
        "ttft_ms": 1268.0,
        "completion_ms": 1490.87,
        "max_itl_ms": 14.21,
        "mean_itl_ms": 14.19
      }
    }
  },
  "chunked_2048": {
    "mode": "chunked",
    "token_budget": 2048,
    "tpot_slo_ms": 50.0,
    "total_steps": 59,
    "total_time_ms": 2034.71,
    "max_itl_ms": 46.63,
    "mean_itl_ms": 34.44,
    "short_chat_ttft_ms": 51.51,
    "doc_100k_ttft_ms": 1907.21,
    "tpot_slo_met": true,
    "requests": {
      "chat-1": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2034.71,
        "max_itl_ms": 46.63,
        "mean_itl_ms": 34.49
      },
      "chat-2": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2034.71,
        "max_itl_ms": 46.63,
        "mean_itl_ms": 34.49
      },
      "chat-3": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2034.71,
        "max_itl_ms": 46.63,
        "mean_itl_ms": 34.49
      },
      "chat-4": {
        "prompt_tokens": 512,
        "generated_tokens": 60,
        "ttft_ms": 0.0,
        "completion_ms": 2034.71,
        "max_itl_ms": 46.63,
        "mean_itl_ms": 34.49
      },
      "doc-100k": {
        "prompt_tokens": 100000,
        "generated_tokens": 8,
        "ttft_ms": 1907.21,
        "completion_ms": 2006.43,
        "max_itl_ms": 14.18,
        "mean_itl_ms": 14.18
      },
      "chat-5": {
        "prompt_tokens": 256,
        "generated_tokens": 16,
        "ttft_ms": 51.51,
        "completion_ms": 565.89,
        "max_itl_ms": 35.96,
        "mean_itl_ms": 33.63
      }
    }
  },
  "stall_reduction_factor": 27.71,
  "budget_sweep": [
    {
      "token_budget": 512,
      "num_prefill_chunks": 198,
      "max_itl_ms": 18.6,
      "mean_itl_ms": 17.99,
      "short_chat_ttft_ms": 24.83,
      "doc_100k_ttft_ms": 3806.76,
      "tpot_slo_met": true
    },
    {
      "token_budget": 1024,
      "num_prefill_chunks": 99,
      "max_itl_ms": 26.6,
      "mean_itl_ms": 24.1,
      "short_chat_ttft_ms": 33.64,
      "doc_100k_ttft_ms": 2541.39,
      "tpot_slo_met": true
    },
    {
      "token_budget": 2048,
      "num_prefill_chunks": 49,
      "max_itl_ms": 46.63,
      "mean_itl_ms": 34.44,
      "short_chat_ttft_ms": 51.51,
      "doc_100k_ttft_ms": 1907.21,
      "tpot_slo_met": true
    },
    {
      "token_budget": 4096,
      "num_prefill_chunks": 25,
      "max_itl_ms": 79.26,
      "mean_itl_ms": 36.46,
      "short_chat_ttft_ms": 88.25,
      "doc_100k_ttft_ms": 1579.98,
      "tpot_slo_met": false
    },
    {
      "token_budget": 8192,
      "num_prefill_chunks": 13,
      "max_itl_ms": 144.22,
      "mean_itl_ms": 38.24,
      "short_chat_ttft_ms": 165.76,
      "doc_100k_ttft_ms": 1422.78,
      "tpot_slo_met": false
    }
  ]
}
Saved output report for balance long-prompt prefill against streaming latency; execution mode and values come from the linked raw result.

This report image is drawn from the saved run output. Open the full-resolution report or read the raw result.

Protect streams without hiding prompt delay

Steadier streaming can give the long prompt a later first token. A larger budget can raise throughput but also lengthen the longest gap between output tokens. A mean TPOT can hide one long pause: the monolithic run has a 34.52 ms mean gap and a 1292.21 ms maximum gap. Report the maximum gap next to the mean, and check how long the newly arrived chat request waits.

Uninterrupted long prefill. In the scheduling fixture, the monolithic long prompt pauses all four active chat streams. The cost coefficients are assumed values, not a GPU trace.

Large work budget. A larger prompt chunk can push the gap past the modeled target. The target and the token budget depend on the workload; they are not safe defaults.

Read the executable checks
Executable checksSource · pythonDownload
from __future__ import annotations

import unittest

from lab import (
    ChunkedPrefillScheduler,
    InferenceRequest,
    build_default_workload,
    simulate_long_prompt_arrival,
)


class TestChunkedPrefillLab(unittest.TestCase):
    def test_monolithic_100k_prefill_stalls_active_decodes(self) -> None:
        workload = build_default_workload()
        scheduler = ChunkedPrefillScheduler(
            mode="monolithic", token_budget=2048, tpot_slo_ms=50.0
        )
        result = scheduler.run(workload)
        self.assertFalse(result["tpot_slo_met"])
        self.assertGreater(result["max_itl_ms"], 1000.0)

    def test_oversized_chunk_budget_violates_tpot_slo(self) -> None:
        workload = build_default_workload()
        scheduler = ChunkedPrefillScheduler(
            mode="chunked", token_budget=8192, tpot_slo_ms=50.0
        )
        result = scheduler.run(workload)
        self.assertFalse(result["tpot_slo_met"])
        self.assertGreater(result["max_itl_ms"], 50.0)

    def test_decode_reservation_exceeding_token_budget_raises(self) -> None:
        workload = build_default_workload()
        scheduler = ChunkedPrefillScheduler(
            mode="chunked", token_budget=2, tpot_slo_ms=50.0
        )
        with self.assertRaises(ValueError):
            scheduler.run(workload)

    def test_chunked_2048_meets_tpot_slo_and_completes_all_requests(self) -> None:
        report = simulate_long_prompt_arrival(token_budget=2048, tpot_slo_ms=50.0)
        chunked = report["chunked_2048"]
        self.assertTrue(chunked["tpot_slo_met"])
        self.assertLessEqual(chunked["max_itl_ms"], 50.0)
        self.assertEqual(chunked["requests"]["doc-100k"]["generated_tokens"], 8)
        self.assertEqual(chunked["requests"]["chat-1"]["generated_tokens"], 60)

    def test_prefill_progress_exact_token_accounting(self) -> None:
        reqs = [
            InferenceRequest(
                request_id="chat-1",
                prompt_tokens=128,
                max_new_tokens=5,
                prefilled_tokens=128,
                generated_tokens=1,
                decode_step_timestamps_ms=[0.0],
            ),
            InferenceRequest(request_id="doc-5k", prompt_tokens=5000, max_new_tokens=3),
        ]
        res = ChunkedPrefillScheduler(
            mode="chunked", token_budget=1024, tpot_slo_ms=50.0
        ).run(reqs)
        self.assertEqual(res["requests"]["doc-5k"]["prompt_tokens"], 5000)
        self.assertEqual(res["requests"]["doc-5k"]["generated_tokens"], 3)


if __name__ == "__main__":
    unittest.main()


class GuardBoundaryTests(unittest.TestCase):
    def test_rejects_invalid_boundary_inputs_with_specific_reason(self):
        import lab
        cases = [('estimate_step_latency_ms(-1,[])', 'decode_tokens'), ('ChunkedPrefillScheduler(mode="bad")', 'Unsupported mode'), ('ChunkedPrefillScheduler(token_budget=0)', 'token_budget')]
        for code, reason in cases:
            with self.subTest(code=code):
                with self.assertRaisesRegex((ValueError, MemoryError, KeyError, RuntimeError), reason):
                    exec(code, vars(lab).copy())

The real cooperative scheduler record runs FIFO, interleaving, and chunked prefill with actual per-request model caches. Its source runs forwards one at a time, so it demonstrates interleaving; it is not an optimized continuous-batching engine.

Try a change and explain the result

Compare monolithic and chunked schedules, then inspect the real isolated request’s chunked TTFT. Explain why these experiments can point in different directions without contradicting each other.

Why might smaller prefill chunks worsen one isolated request’s TTFT?

Choose one answer, then check your reasoning.

Read the explanation

Chunking creates scheduling opportunities but adds work. Its main benefit may be to other requests.

Tune against both latency goals

Tune the budget against your own prompt and output lengths and your latency targets. Measure both the streams that are already running and the requests that just arrived. Pick the largest budget that meets your gap target, then check whether the long prompt’s TTFT is acceptable. Do not copy a token budget or occupancy watermark from a different model and treat it as safe everywhere.

References

Sources checked October 24, 2026. Runtime-specific commands and results apply to the recorded versions; linked rolling documentation can change. The application scenarios are teaching examples, not claims about an author’s production incident.

Written by Arjun Prabhulal.

Module 3

Batch requests and cache shared prompts