PolyGraph lets one CUDA Graph serve adaptive speculative decoding
Adaptive speculative decoding changes the active batch size B and the draft length d from one decode step to the next. A CUDA Graph, by contrast, replays a fixed launch configuration. The resulting verification width M = B d leaves serving systems three options, according to the authors: pre-capture many shapes, capture new ones on the serving path, or pad every step to the largest draft.
The paper presents PolyGraph, a plan-buffer mechanism for custom Triton kernels that avoids that choice. It captures a single maximum-grid graph and, before each replay, writes the active shape to GPU memory. Kernels then skip the tiles beyond that shape. Graph topology, allocations, layouts, pointers and launch grids all stay fixed, and the per-replay update transfers only 28 bytes.
The evaluation ran on one NVIDIA H800, using a trace-driven prototype with Qwen2.5-3B dimensions. In it, PolyGraph replaces 64 shape-specific graphs with one. It matches the warmed baseline in observed step latency, at 17.7 ms against 17.8 ms at P50 (the median). It also cuts measured pre-serving graph-build time from 3,915 ms to 93 ms.
Fixed-draft controls are used to explain where the gain comes from. The authors say the benefit comes from avoiding padded payload. Against the MaxPad baseline, the P99 difference is negligible at zero padding waste, but it reaches an 18.7% reduction at 100% waste.
The authors are explicit about the limits. Their evidence establishes a bounded work-shape mechanism for custom kernels, not a production serving system, and it is limited to synthetic traces on one GPU.
Key facts
- PolyGraph captures one maximum-grid CUDA Graph and writes the active batch and draft shape to GPU memory before each replay; the update is only 28 bytes.
- In a trace-driven prototype with Qwen2.5-3B dimensions on one H800, it replaces 64 shape-specific graphs with one.
- Step latency matches the warmed baseline: 17.7 ms against 17.8 ms at P50.
- Measured pre-serving graph-build time falls from 3,915 ms to 93 ms.
- Against the MaxPad baseline in fixed-draft controls, P99 latency is about the same at zero padding waste and 18.7% lower at 100% waste.
Why it matters
CUDA Graphs cut launch overhead by replaying a fixed configuration, but adaptive speculative decoding keeps changing the shape of the work. Existing answers each cost something: many pre-captured graphs, capture on the serving path, or padding every step to the largest draft. PolyGraph tries to remove the trade-off by keeping one graph and varying only a small shape record in GPU memory. In the prototype that shrinks 64 graphs to one and graph-build time from 3,915 ms to 93 ms without a loss in median step latency.
Who it affects
The mechanism is aimed at people who write custom Triton kernels for LLM serving and who use adaptive speculative decoding, where batch size and draft length vary per step. The paper tests only Qwen2.5-3B dimensions on a single H800.
How to use it
The abstract describes the approach rather than a product. A kernel is written to read the active shape from a small buffer and skip tiles beyond it, while the graph is captured once at the maximum grid. The abstract does not say whether code is released.
How solid is it
The numbers come from a trace-driven prototype on one NVIDIA H800 with synthetic traces. The step latency match (17.7 vs. 17.8 ms) is at P50 only. The 18.7% figure is a P99 reduction against the MaxPad baseline at 100% padding waste, not against the warmed baseline; at zero waste the P99 difference is negligible. The authors state that the evidence supports a bounded work-shape mechanism, not a production serving system.
Risks and caveats
The work is limited to custom kernels, synthetic traces and one GPU. No results on real production traffic, multiple GPUs, or models other than Qwen2.5-3B dimensions are reported. No end-to-end throughput numbers are given, and the abstract makes no comparison with existing serving systems. The padding savings depend on how much waste the workload would otherwise carry.
“Our evidence establishes a bounded work-shape mechanism for custom kernels, not a production serving system, and is limited to synthetic traces on one GPU.”
— PolyGraph paper abstract (arXiv 2610.23861)