acceptodds
Under review as a conference paper at ICLR 2027

RIVET: Ragged Inference with Variable-Granularity Execution for Token-Tree Verification in Speculative Decoding

Abstract

As agentic applications use larger language models and longer interactions, autoregressive decoding incurs increasingly costly serial target-model passes. Tree-based speculative decoding reduces these passes by verifying multiple candidate continuations at once. This verification requires tree attention: each candidate sees the shared history and its own ancestor path, while the number of candidates and the tree topology vary across rounds. Conventional attention kernels use fixed query tiles, KV partitions, and general masks, leading to padded query work, inefficient KV scheduling, and repeated visibility checks even over the fully visible prefix. We present \method, a variable-granularity execution scheme for token-tree verification. It maps tree visibility to specialized regions, processing regular blocks with dense or causal attention while restricting ancestor checks to irregular blocks. It selects query tiles for the physical query shape and sizes KV partitions to balance parallelism against GPU resource and merge costs. Online-softmax merging preserves exact tree-attention semantics across regions and partitions. In nine kernel configurations, \method reduces attention latency by 51.6% on average relative to FlashInfer. Across 24 model–workload configurations, it improves output throughput by 7.6–50.5% and reduces median time per output token (TPOT) by 3.0–34.2% relative to the strongest baseline selected separately for each configuration and metric.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Speculative decoding, token-tree verification, Ragged Inference, KV splitting, CTA scheduling.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_eFE2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes RIVET, a variable-granularity execution framework for token-tree verification in speculative decoding. It combines structure-aware mask specialization, adaptive query tiling, and resource-aware KV partition scheduling to reduce redundant computation and improve GPU utilization. The method preserves exact tree-attention semantics through online-softmax merging. Experiments on Qwen3-8B and Llama-3.1-8B demonstrate improvements in both attention-kernel latency and end-to-end decoding performance.

Critical strengths
  1. The paper identifies concrete inefficiencies in existing tree-attention implementations, including query padding, KV scheduling imbalance, and redundant mask checks. The proposed framework addresses these issues in a coherent manner while preserving exact attention semantics.

  2. The implementation integrates with FlashInfer and SGLang, and the experiments demonstrate meaningful improvements over several representative attention backends. The evaluation includes both kernel-level and end-to-end measurements, with component ablations supporting the effectiveness of the proposed optimizations.

Critical weaknesses
  1. The main components largely adapt established techniques, including mask specialization, adaptive query tiling, and KV partition scheduling. More importantly, Appendix C shows that the topology-compiled region path is 4.2–4.9% slower than a simpler prefix–suffix hybrid on branching trees, while providing only a marginal improvement on chain structures. This raises questions about when the more elaborate heavy-path decomposition is actually beneficial and whether it is necessary for the reported gains.

  2. Although the kernel benchmarks cover batch sizes up to 32 and KV lengths up to 32K, the end-to-end experiments are restricted to batch sizes 8/16 and KV lengths 8K/16K on two 8B models using A800 GPUs. The generality of the reported improvements across longer contexts, larger batches, different hardware, and more diverse tree structures remains unclear.

  3. Equation (2) introduces a profiled cost model incorporating CTA execution times, scheduling waves, and merge overhead. While the ablation in Figure 6 demonstrates the benefit of KV-split scheduling, it does not establish whether the proposed model outperforms simpler tuned fixed-split or KV-length-based policies. A more controlled comparison would help justify the additional scheduling complexity.

Questions for authors
  1. Appendix C shows that topology-compiled regions are slower than the simpler prefix–suffix hybrid on branching trees. Under what conditions does heavy-path decomposition provide a clear advantage, and how much does it contribute when the other optimizations are held fixed?

  2. Can the authors clarify the expected performance under larger batches, longer KV contexts, and more diverse tree topologies? How representative are the evaluated speculative decoding workloads?

  3. How accurately does the scheduling cost model predict measured runtime, and how does it compare with simpler fixed-split or length-based scheduling policies under the same settings?

1 comment

We thank the reviewer for their careful comments on Appendix C, larger-scale evaluation, and CTA latency; we respond to each point below.

Q1. Appendix C. Hybrid denotes our topology-compiled method and Region the native masked path. A regression is possible only for the deliberately constructed chain with nearly equal request lengths; no such case appeared in the 864 measured requests.

Q2. Larger batch and context. We extend the five-way attention-kernel comparison beyond the paper's B32/32K range to batches of 64 and 128 and KV lengths of 64K and 128K. The table reports median latency in milliseconds.

Batch / KVRIVETFlashInferFlash-DecodingFlashAttention-2DeFT
64 / 64K1.2722.1832.5832.4822.202
64 / 128K2.5283.5325.1314.9284.178
128 / 64K2.7133.5325.1174.1484.223
128 / 128K5.4256.93910.1858.3228.322

RIVET has the lowest latency in all four configurations, reducing it by 21.8–41.7% relative to the fastest baseline at each point.

Q3. CTA latency. For a fixed Q template and KV interval, isolated CTA execution time is stable across repeated runs. We profile the GPU duration of one native-causal attention kernel per invocation, with exactly one CTA, no KV split, and no merge. The table gives median / scheduling cost model predicted latency in microseconds over 150 runs after warmup:

KV lengthQ16Q32Q64
2K35.615 / 35.64740.606 / 40.63967.518 / 67.551
8K121.661 / 121.693142.237 / 142.333252.410 / 252.474
16K237.147 / 237.179251.643 / 251.770451.958 / 452.054

Across these nine fixed-shape classes, scheduling cost model predicted latency is at most 0.09% above the median (coefficient of variation below 0.10%). A simpler fixed-split strategy would leave CTA workloads imbalanced, creating a long tail in execution time.

Reviewer_FCNsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

RIVET improves tree verification by changing how attention work is divided and scheduled on the GPU. It runs in FlashInfer and SGLang and shows improvements in throughput and token latency.

Critical strengths
  1. The paper studies a practical problem and shows useful end-to-end speedups.

  2. The ablations help explain the gains from query tiling and KV scheduling. The paper also reports their overhead and cases where a simpler method is faster.

Critical weaknesses
  1. I still cannot tell how much the finer tree decomposition helps. The current ablation also changes prefix processing, so the gains are hard to separate.

  2. The DeFT comparison needs to be clearer. Different implementations, tuning, or timing boundaries could affect the results.

  3. It is unclear what happens when KV-split planning is turned off, which makes this ablation hard to judge.

Questions for authors
  1. What tree shapes are used in the main experiments? How much does finer decomposition help over the simpler prefix–suffix approach?

  2. Which DeFT implementation is used, and how is it tuned? Do both timings include preparation and reduction?

  3. When KV-split planning is turned off, is KV splitting still enabled? How are the splits chosen?

1 comment

We thank the reviewer for their careful questions about the evaluation, DeFT implementation, and KV-split control; we respond to each point below.

Q1. Figures 4–5 and Appendix C. Figures 4–5 use the complete region-based execution of Section 4.2. The tree configurations vary dynamically across the 24 end-to-end configurations and 864 requests, covering most relevant cases. In Appendix C, Hybrid is our method and Region is the native masked path. The constructed adverse case, a chain with similar request lengths, never occurred in those requests.

Q2. DeFT implementation. Figure 4 uses the alternative Triton DeFT implementation from the FastTree artifact, acknowledged by the official DeFT repository, rather than the published DeFT-Flatten implementation. Timed DeFT_decode includes first-stage attention and second-stage reduction; preparation, allocation, and first-use compilation are excluded.

Q3. KV-split control. When KV-split planning is disabled, we retain KV parallelism and use the same default fixed-split strategy as FlashInfer and FlashAttention.

Reviewer_yzaVOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

RIVET accelerates tree-based speculative verification through structure-aware attention, adaptive Q tiling, and resource-aware KV partitioning. The reported end-to-end gains are promising, but the experiments do not sufficiently distinguish the benefits of the proposed mechanisms from existing scheduling techniques and the simpler dense-prefix optimization.

Critical strengths
  1. Clear motivation supported by preliminary execution analyses.
  2. Coherent design addressing masking, query padding, and KV scheduling.
  3. End-to-end speculative decoding evaluation demonstrating practical gains.
  4. Ablations, scheduling-overhead measurements, and topology-sensitivity experiments.
Critical weaknesses
  1. Limited isolation of scheduling improvements over existing adaptive strategies.
  2. No direct comparison of multi-tile Q combinations against the smallest fitting template.
  3. Unclear replacement policy when adaptive Q tiling is disabled.
  4. Missing candidate-tree and block-classification statistics for actual workloads.
  5. Main mask ablation conflates dense-prefix and candidate-tree optimizations.
  6. Limited evidence that topology compilation improves upon the simpler hybrid approach.
Questions for authors
  1. What specifically distinguishes the Q/KV scheduling policies from existing adaptive strategies, and what gains remain when the mask implementation is held fixed?
  2. Does selecting multiple smaller Q tiles outperform choosing the smallest fitting template? Under which query sizes, KV lengths, and cache conditions?
  3. What Q-tile selection policy replaces adaptive tiling in Figure 6a?
  4. What are the candidate-count, branching-factor, and heavy-path-length distributions in the end-to-end experiments? What fraction of blocks are classified as mixed?
  5. Can you compare generic masking, dense-prefix attention with a masked candidate suffix, and full topology compilation under identical Q/KV scheduling?
  6. Given the branching-tree results in Appendix C, when does topology compilation provide a net benefit, and how frequently do those conditions occur in the evaluated workloads?
1 comment

We thank the reviewer for their careful comments on our scheduling choices, workload characterization, and Appendix C; we respond to each point below.

Q1. Q/KV scheduling. Existing decode kernels process one query per request, so CTA work is relatively uniform and one global split size is sufficient. With variable-length token trees, CTA service times diverge and create load imbalance. This is why we use a heuristic Q/KV scheduling strategy.

Q2. Q-tile granularity. Leading implementations such as FlashInfer and FlashAttention favor a large Q tile for bandwidth utilization, whereas finer splitting creates more CTAs. We hold the effective packed Q count at 64 and force it into progressively smaller blocks. With 128 independent requests, GQA 8:1, and native causal attention, a single Q64 tile already supplies 128 CTAs; further Q splitting repeatedly traverses the same KV cache and increases latency:

KV length1×Q642×Q324×Q168×Q8-effective
8K466.9 μs578.6 μs (1.24×)876.5 μs (1.88×)1484.3 μs (3.18×)
16K802.8 μs922.1 μs (1.15×)1418.2 μs (1.77×)2380.3 μs (2.97×)
32K1552.9 μs1871.9 μs (1.21×)2773.5 μs (1.79×)4709.4 μs (3.03×)

Q3. Control policy. When adaptive Q tiling is disabled, we select one uniform Q tile according to the longest token tree in the batch.

Q4. Workload statistics. The 24 submitted end-to-end configurations cover 864 measured requests. Candidate counts vary dynamically from 8 to 64; with EAGLE's high acceptance, the heavy path nearly reaches its maximum length of 8. The mixed-block fraction varies by request and spans 0–50%.

Q5. Appendix C interpretation. Appendix C demonstrates the advantage of topology compilation. We clarify a terminology misunderstanding: Hybrid denotes our method, whereas Region denotes the native masked path.

Q6. Frequency of the adverse case. A regression can occur only when trees degenerate into chains and request lengths are nearly equal. We constructed this extreme case deliberately; it occurred in none of the 864 measured requests, so it should be rare in the evaluated workload.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.