Skip to content

[FEATURE] Cost-based automatic rollout and bucketed prefill after #8497 #8785

Closed

Description

@SuperGoodGame

Context

Performance follow-up to #8497. Its aligned decode fronts remove padded prefill work, but prefilling every request separately adds substantial overhead. Ordinary no-CB generation also matters when the complete request set fits the active capacity.

A padding-ratio threshold is insufficient: 1×128 + 31×4 and 1×512 + 31×16 have the same ratio (16.25), yet favor different existing paths. Additional checks also showed short, highly uneven prompts losing badly with per-request prefill.

Related tracking issues: #8197 (HybridEngine rollout performance) and #8462 (decode-front alignment and trimming). The implementation builds on PRs #8368, #8494, and #8497.

Proposed follow-up

Add opt-in HybridEngineRolloutConfig(adaptive_prefill=True), disabled by default:

  • Compare eligible ordinary generation with CB using cost-based prefill buckets.
  • Sort admitted requests by effective length and use O(n²) dynamic programming to choose bucket count and membership. The candidates include one batch and one request per bucket.
  • Use ordinary left-padded tensors and two-dimensional attention masks. For 1×512 + 31×16, the short group can be [31,16] beside [1,512].
  • Replan newly admitted requests on every refill while keeping aligned decode/cache layout and surviving rows stable.

The additive cost includes fixed Forward overhead, padded-token work, quadratic attention work and KV traffic. Five configurable coefficients cover those terms plus the extra CB decode cost. Attention/KV terms read layer count, query/KV heads, head dimension and dtype size from the model. The DP minimizes estimated cost; coefficients need calibration for the target model/device.

An optional padded-token limit bounds each prefill Forward. Ordinary generation participates only when all requests fit active/token/context limits and no explicit cache capacity or trimming is requested. Otherwise Auto stays on CB. This adds neither packed/varlen kernels nor chunked prefill.

Evidence

The algorithmic approach has direct precedent: TurboTransformers, §5 uses length sorting, measured batch costs and O(n²) DP for variable-length inference; DynaPipe, §4 uses cost-based DP micro-batch construction for training. This proposal brings that approach to the existing HybridEngine rollout paths and cache constraints.

Workload Fastest legacy baseline Auto mean Auto / best Choice
Short, similar No-CB: 505.54 ms 501.77 ms 0.9925× No-CB
1×512 + 31×16 Aligned CB: 1682.10 ms 840.06 ms 0.4994× 2 buckets
1×20 + 31×1 No-CB: 501.74 ms 497.57 ms 0.9917× No-CB
1×128 + 31×4 No-CB: 897.17 ms 634.59 ms 0.7073× 2 buckets
16, 32, …, 512 Aligned CB: 2337.75 ms 1984.86 ms 0.8490× 6 buckets

Single GPU; Qwen/Qwen2.5-3B-Instruct, FP32 / SDPA. Each path receives one warmup and five interleaved timed calls, 32 requests and 16 output tokens each. Results are arithmetic means; every response matches independent single-request eager generation. The first two shapes follow #8497; the two threshold counterexamples and one spread case test the decision more broadly. Detailed path timings, throughput, memory and profiling are included in the accompanying PR.

Acceptance and scope

  • Preserve tokens, original repetition history, EOS/PAD masks, row order, positional configuration compatibility and active/cache bounds.
  • Across all five measured shapes, Auto must stay within 5% of the fastest available manual baseline; this is a measurement tolerance, not a universal hardware guarantee.
  • 105 related rollout/cache tests pass, including GPU tiny-Qwen bucket/refill regressions, both cache APIs, effective generation-config/legacy refresh, long-prompt position guards, and end-to-end profiling. One unrelated native extension test is excluded on a host without a CUDA compiler.
  • Single-process, greedy, one sample per prompt, supported cache-class model. Unsupported generation settings, CUDA Graph and shared-prefill combinations fail explicitly.
  • 64k prompts require a suitable model context limit and memory. The measured model is configured for 32k; real 64k performance is outside this validation.

Related foundation: #8368; existing profiling: #8494.

Implementation PR: #8786.

Review invitation

cc @nathon-lee @delock — thank you for the continuous-batching, profiling, and aligned-cache groundwork. Could you review this follow-up, especially the no-CB/CB cost comparison, per-refill bucket planning, and preservation of cache/generation semantics? Feedback on the opt-in API and default cost estimates would also be appreciated.

Activity

  1. delock commented on Nov 3, 2026

    @delock
    Collaborator

    Hi @SuperGoodGame CB and SegKI improved a lot over this month. We will review this PR again in current context, thanks!

  2. SuperGoodGame commented on Nov 5, 2026

    @SuperGoodGame
    ContributorAuthor

    Thanks @delock. Following the mid-November revisit, #8786 is refreshed onto current master (b62afa8) and is mergeable again as a single commit d9a2cc3.

    It now includes the decode-side work that landed over the last month: #8732 graph state, #8839 last-position prefill logits, #8933 accelerator-neutral graph calls and #8852 cache query offsets. #8980's accelerator opt-in is respected through the eager fallback.

    The scope has not grown: Auto stays default-off and remains mutually exclusive with graph capture, because the graph uses fixed physical slots while Auto requires aligned, bucketed prefill. That joint routing is the natural follow-up once the graph path and SegKI settle; SegKI is not part of this PR.

    Validation on one GPU of an 8×H20Z node (PyTorch 2.9.1+cu128, CUDA 12.8): 159 passed, 3 skipped (Transformers 5.20-only cases from #8852), 1 deselected (native kernel test), changed-file pre-commit passed.

    It would help to know which direction you want the joint story to take: keep the two paths separate for now, or design a fixed-slot bucketed prefill so one policy can choose either decode. I am happy to prototype the second if that matches where CB/SegKI are heading.

  3. added a commit that references this issue on Nov 15, 2026
    a7f1e4d
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions