acceptodds
Under review as a conference paper at ICLR 2027

Request Forest: Jointly Growing Verification Trees for Speculative Decoding

Abstract

Block-parallel draft models can predict multiple future tokens in a single forward pass, yet the benefits of speculative decoding under high concurrency depend on how limited verification resources are allocated. Collapsing candidates into a single path and assigning a fixed verification window to each request limits the ability to accommodate differences in draft quality across requests and exploit alternative branches within each request, while increasing intermediate verification-state overhead in hybrid architectures. We propose Request Forest (RF), which jointly grows verification trees across requests under a shared budget. RF reuses the candidates and predecessor-conditioned scores provided by a block-parallel drafter, allowing eligible nodes across requests to compete for the budget according to their path priorities. This process jointly determines tree size, depth, and branching structure, yielding a prefix-closed verification forest. RF then packs the forest into a compact, branch-isolated layout, verifies it in a single target-model forward pass, and commits only the states along accepted paths. Theoretical analysis establishes that, under the specified scoring assumptions and budget constraints, this growth strategy maximizes the sum of priorities of selected candidates. Experiments on four hybrid-architecture models and four benchmarks demonstrate the effectiveness of RF. On Qwen3.8-27B at concurrency levels of 64–160, RF improves geometric-mean throughput by 56.6% over DFlash and 13.9% over DFlash2. At a concurrency level of 128, it reduces GPU Memory reserved for intermediate recurrent verification states per tensor-parallel rank by 50.4% relative to DFlash2.These results show that shared-budget tree growth effectively translates diffusion draft diversity into throughput gains under high concurrency.Code is available at https://anonymous.4open.science/r/Request-Forest-2844/.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Speculative Decoding, Block-Parallel Drafting, Cross-Request Budget Allocation, Tree-Based Verification

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_SkdvOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Request Forest, which jointly allocates verification nodes across concurrent requests and candidate branches using DFlash2’s candidates and path scores. It combines shared-budget tree construction with branch-isolated verification, recurrent-state commitment, and load-adaptive switching. The authors prove optimality for a fixed-score, unit-cost surrogate objective and evaluate four hybrid models on four benchmarks, reporting higher throughput and lower intermediate verification-state memory.

Critical strengths
  1. The paper addresses a practical bottleneck in high-concurrency speculative decoding. Reusing an existing drafter without retraining and supporting branch-specific recurrent states make the approach relevant to hybrid-model serving.

  2. The component ablations provide useful evidence. With the drafter, budget, and state reservation controlled, budget sharing improves throughput by about 7%, and allowing branches adds about 5% on the two ablated models.

Critical weaknesses
  1. The additional benefit over existing scheduling methods is not yet convincing. DSpark already globally ranks prefix extensions by cumulative survival probability and selects verification lengths using hardware costs. ECHO also combines cross-request allocation with tree depth and width control. Both are discussed but neither is evaluated. The ablation also lacks independently optimized trees with fixed per-request budgets, so it does not directly establish the benefit of joint forest allocation over separate tree construction.

  2. Output preservation needs clearer validation. Equation (7) specifies equality with target-only greedy decoding, but Table 20 reports different task results, including 1226 versus 1222 correct GSM8K answers for target-only and RF. Numerical differences may explain this, but no token-level agreement or divergence analysis is reported. Similar task accuracy does not establish output equivalence, and differences in generated lengths could also affect throughput comparisons.

Questions for authors
  1. Can you compare RF with DSpark- or ECHO-style scheduling and with fixed-budget per-request trees under controlled drafter, execution-backend, and verification-resource settings? Please distinguish adaptations of their scheduling policies from comparisons against the full systems.

  2. What causes the differences in Table 20? What are the token-level output-agreement rates against target-only decoding, and do differences in output length or truncation materially affect the throughput results?

6 comments
AuthorsOpenReview ↗

Response to Reviewer Skdv

Q1: Controlled comparisons with ECHO-style and DSpark-style scheduling

Response:
We thank the reviewer for suggesting these comparisons. ECHO and DSpark were not originally designed for diffusion language models, whereas our work focuses on scheduling for diffusion language models. This difference in scope motivated our original evaluation design, which did not include comparisons with ECHO or DSpark. Nevertheless, we agree that comparing against adaptations of their scheduling policies would help clarify RF’s additional benefits.

In response to your suggestion, We adapt ECHO-style and DSpark-style scheduling to the same Ornith target model, DFlash2 drafter, and verification backend, with matched verification-resource constraints.

ECHO-style uses confidence-gated, depth-first expansion with width extension; DSpark-style selects verification size using prefix-survival estimates and hardware execution costs. RF instead jointly selects path extensions and alternative branches across requests through a global candidate frontier ranked by cumulative path priorities.

Table R1. Throughput under controlled scheduling comparisons on Ornith with DFlash2 (tokens/s).

BatchBenchmarkRF ↑ECHO-style ↑DSpark-style ↑
128GSM8K5892.175760.732955.91
128MATH-5006457.416255.163272.78
128HumanEval6833.196532.993466.96
144GSM8K6344.286063.445351.34
144MATH-5007083.776850.766613.05
144HumanEval7473.107328.757120.04
160GSM8K6858.716728.356349.69
160MATH-5007224.576997.367155.28
160HumanEval7667.127522.297603.05

RF achieves higher throughput in all nine configurations, with a paired geometric-mean gain of 3.02% over ECHO-style across all nine, and 6.58% over DSpark-style across the six configurations at B = 144 and 160.

These results demonstrate RF’s incremental benefit under the tested settings. The comparisons evaluate adaptations of scheduling policies to a common backend, rather than reproductions of the complete original systems.


Q2(a): Why do the task results differ, and are the generated outputs identical?

Response:
Eq. (7) describes ideal-arithmetic equivalence, assuming identical prefixes, state-update semantics, greedy decoding rules, and stopping criteria. Our finite-precision implementation does not guarantee token-for-token identical outputs.

Different computation layouts and execution paths can introduce numerical differences. When token scores are close, these differences can change greedy decisions and subsequent generation, potentially affecting task accuracy. We will revise Eq. (7) and the accompanying text to explicitly delimit the equivalence claim.

As a supplementary quality check, RF’s perplexity differs from target-only autoregressive decoding (AR) by only +0.0108% (Table R2), indicating similar aggregate predictive quality.

Table R2. Perplexity under the evaluation settings.

MethodPPL ↓Change vs. AR
AR1.097617—
DFlash21.098079+0.0421%
RF1.097735+0.0108%

PPL: perplexity. Change vs. AR: relative PPL change compared with target-only autoregressive decoding.

AuthorsOpenReview ↗

Response to Reviewer Skdv

Q2(b): Do output-length or truncation differences materially affect throughput?

Response:
We agree that identical output limits do not guarantee identical generated lengths. We therefore compare RF and DFlash2 across 27 matched configurations: three benchmarks, batch sizes 128, 144, and 160, and output limits of 128, 256, and 512 tokens. We record end-to-end throughput and the fraction of requests reaching each limit.

RF achieves higher throughput in all 27 configurations, with paired geometric-mean gains of 13.19%, 15.45%, and 15.19% at the three output limits, respectively. The maximum difference in limit-hit rates is only 1.5 percentage points. For example, at B = 128 on HumanEval with a 512-token limit, both methods have a 56.4% limit-hit rate, yet RF improves throughput by 21.95%. At B = 144 on MATH-500 with a 128-token limit, both reach 98.4%, while RF remains 15.54% faster.

These results show that RF’s gains persist across output limits and cannot be explained solely by different limit-hit rates. However, each configuration was measured once, and similar limit-hit rates do not establish identical per-request output lengths. We therefore cannot fully exclude effects from output-length distributions and will clarify this limitation.

Table R3. Throughput and limit-hit rates across maximum output lengths.

BatchBenchmarkMethodLimit 128Limit 256Limit 512
128GSM8KRF6684.89 (74.2%)6979.36 (12.5%)6951.15 (0.2%)
128GSM8KDFlash25930.43 (74.6%)5971.38 (11.3%)6193.11 (0.2%)
128MATH-500RF6467.50 (98.6%)7384.94 (69.1%)7891.26 (24.6%)
128MATH-500DFlash25471.22 (98.0%)6417.79 (69.1%)6592.28 (25.4%)
128HumanEvalRF6317.42 (97.1%)7692.61 (87.5%)8487.25 (56.4%)
128HumanEvalDFlash25466.39 (97.3%)6409.63 (87.7%)6959.61 (56.4%)
144GSM8KRF7006.84 (74.0%)7341.02 (13.0%)7175.55 (0.0%)
144GSM8KDFlash26352.89 (75.5%)6477.58 (12.7%)6520.98 (0.2%)
144MATH-500RF6750.79 (98.4%)7624.68 (67.5%)8191.74 (26.0%)
144MATH-500DFlash25842.66 (98.4%)6675.17 (67.7%)7091.06 (24.8%)
144HumanEvalRF6526.36 (96.7%)8209.06 (90.5%)8931.45 (57.6%)
144HumanEvalDFlash25763.08 (96.9%)6649.93 (89.1%)7389.34 (57.8%)
160GSM8KRF7169.11 (74.7%)7556.95 (12.8%)7164.94 (0.3%)
160GSM8KDFlash26568.06 (74.7%)6813.74 (13.3%)6729.82 (0.0%)
160MATH-500RF6962.62 (97.8%)7997.49 (68.1%)8266.92 (25.3%)
160MATH-500DFlash26204.47 (98.8%)7102.43 (68.4%)7252.67 (24.7%)
160HumanEvalRF6693.52 (96.7%)8059.09 (88.6%)9020.75 (57.7%)
160HumanEvalDFlash25973.93 (97.2%)6967.36 (88.0%)7718.10 (57.7%)

Each entry reports throughput in tokens/s (percentage of requests reaching the output limit). Output limits are measured in tokens.


▪ We thank the reviewer for the constructive feedback. The scheduling comparisons in Weakness 1 are addressed in Q1, with the fixed-budget independent-tree comparison provided separately below. Weakness 2 is discussed in Q2(a) regarding output differences and the scope of equivalence, and Q2(b) regarding output-length and truncation effects on throughput. Any remaining concerns are addressed separately to avoid repetition.


Weakness: Benefits of joint forest allocation over independent trees

Response:
The original Table 2 shows that Global-Forest (GF) improves throughput over Global-Chain (GC) by approximately 5.0%, demonstrating the benefit of branching under a shared budget. To test whether budget sharing remains beneficial when branching is already enabled, we add Equal-Forest (EF).

EF and GF use identical candidate trees, drafter, scoring rules, total verification budget, and execution backend. EF assigns fixed per-request quotas and selects trees independently; GF jointly allocates the budget across requests and branches.

Table R4. Fixed-budget independent trees versus shared-budget forests (throughput: tokens/s).

ConfigurationQwen3.8-27B ↑Ornith-1.5-35B-A3B ↑
Equal-Chain (EC)2135.33860.8
Global-Chain (GC)2285.44130.7
Equal-Forest (EF)2270.14108.9
Global-Forest (GF)2398.84335.7

GF outperforms EF by 5.67% on Qwen and 5.52% on Ornith. Together, GC → GF isolates the benefit of branching, while EF → GF isolates the benefit of cross-request budget sharing when branching is already available. These comparisons demonstrate the additional value of joint forest allocation under matched verification resources.

AuthorsOpenReview ↗

Follow-up on Your Comments

Dear Reviewer Skdv,

Thank you for highlighting the need for stronger controlled comparisons and clearer output-preservation claims. We have added ECHO-style and DSpark-style scheduling comparisons under a common backend, together with the fixed-budget independent-tree baseline. We have also examined throughput and truncation rates across different output limits and clarified the distinction between ideal-arithmetic equivalence and finite-precision behavior in our revisions. Could you kindly let us know whether these experiments and clarifications address your main concerns, or if there are any points you would like us to clarify further? Thank you again for your time and helpful suggestions.

Best regards,
The authors

Reviewer_xhbkOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a speculative decoding method i.e, Request Forest (RF) designed to improve throughput when many requests are served at the same time. RF uses the top-k token candidates and their predecessor conditioned scores from the DFlash2 block diffusion draft model. Each candidate is assigned a priority score ρ(v)\rho(v), calculated by multiplying the edge scores after normalizing them across the candidate children of each node. This is done for all candidate paths in the draft tree. Then RF uses a single max heap across all requests to select the most promising candidates. It builds a verification forest while keeping the total number of nodes within a global budget ktk_t and limiting the number of nodes per request using Cb,tC_{b,t}. The selected candidates are then verified together in one target model forward pass. RF then uses separate attention and recurrent state slots for different branches to avoid mixing information. Only the states from accepted paths are kept. When there are only a few active requests the RF algorithm switches back to normal linear verification. Proposition 1 shows that the greedy selection method maximizes the sum of selected priority scores under the paper's selection contraints. Equation 11 explains that this sum represents the expected length of the correct prefix covered by the selected candidates. The authors evaluate RF on four hybrid SSM/attention models, on Qwen3.8-27B RF improves geometric mean throughput by 13.9% compared with DFlash2 at 64-160 concurrent request. It also reduces reserved intermediate SSM memory by 50.4% at 128 concurrent request.

Critical strengths
  1. The paper addresses an important problem of improving throughput when many concurrent requests are served. This is especially useful for hybrid models where verification states use GPU memory that could otherwise be utilized for KV cache.
  2. RF uses a single global max heap to decide how many candidates to select for each request, how deep the tree should grow and which branches to keep. It does not require retraining and is implemented in SGLang.
  3. Table 2 clearly shows the benefits of each component individually and hence presents a good ablation. Sharing the budget across requests improves throughput by 7.0% over equal-chains while adding branch selection gives another 5.0% improvement over global chains. Both improvements are observed across all 20 benchmark concurrency combinations.
  4. The paper reports mean results and standard deviations from four runs, geometric-mean throughput improvements (Eqs. D.3–D.5), out-of-memory (OOM) cases and the overhead of different components. It also evaluates load switching and checks the models output quality on full datasets.
  5. RF handles recurrent states by keeping separate temporary states for different tree nodes and saving only the states from accepted paths. This is a useful engineering improvement for models that use both attention and recurrent layers.
Critical weaknesses
  1. One of my concern is whether the priority scores are reliable when comparing different requests ? Equation 2 normalizes the candidate scores using only the top-k candidates rather than the full vocabulary. This can remove information about the draft model's actual confidence. For example, let's say there are 2 requests i.e, A with candidate probabilities (0.60, 0.30) and B with candidate probabilities (0.10, 0.05). After normalization they both become (0.667, 0.333), even though the original probabilities are very different. Since RF uses these scores to distribute a shared budget across requests this could affect candidate selection. Equation 11 shows the expected prefix length based on these normalized scores but it does not prove that the scores reflect actual token acceptance by the target model. This is particularly important for the alternate branches. The paper does not provide an analysis or ablation of how well these priorities predict actual acceptance. The authors should compare the priority scores (ρθ(v)\rho_\theta(v)) with empirical acceptance rates and investigate whether using full-vocabulary confidence improves candidate selection.

  2. I would request some missing ablation and baseline to solidify the claim, i.e., Table 2 compares equal-chain, global-chain and global-forest but it does not include an equal-forest baseline where each request receives a fixed budget but can select multiple branches. This is important because the current ablation shows the benefit of budget sharing for single paths and the benefit of branching with a shared budget. However, it does not show whether sharing the budget still improves throughput when multiple branches are already allowed.

    Additionally, the paper also discusses related methods such as DDTree, BASTION, CaDDTree, ECHO, DSpark, and TETRIS but does not provide direct experimental comparisons. Some of these methods already explore tree construction and shared budgets or adaptive verification. Comparing against the most relevant methods or atleast explaining why these comparisons are not feasible, would help establish the novelty of RF. For example ECHO schedules candidates under a shared budget and DSpark picks verification lengths from survival estimates and engine throughput while TETRIS allocates prefixes across requests. TETRIS applied to DFlash2 chains may be similar to the global chain variant used in this paper. It would be useful for the authors to clarify the differences and explain the additional benefits of RF.

    Finally, I see that RF uses a a budget calibrated for each model, while DFlash2 uses a fixed verification window of W=8. Table 2 matches budgets across RF's own variants, but the headline comparison with DFlash2 does not. A comparison with DFlash2 using a tuned verification window would help determine whether the throughput improvement comes from better candidate selection or simply from using fewer verification tokens. Overall, the paper reports a 13.9% throughput improvement over DFlash2, but the current experiments do not fully show how much of this improvement comes specifically from selecting candidates jointly across requests rather than from the smaller verification budget or other implementation choices.

Questions for authors

For additional experiment request please refer to weakness 1 and 2.

Some clarifications request:

  1. In Eq. 2 is CpC_p the top-k candidate list from DFlash2? What is kk and how much of the full-vocabulary probability mass does it cover ? If this varies across requests, are the priority scores (ρθ(v)\rho_\theta(v)) reliable for cross-request comparison?
  2. How well do the priority scores ρθ(v)\rho_\theta(v) predict actual token acceptance ? A comparison across tree depths including main paths and alternative branches would help support Eq. 11 better.
  3. Appendix F.3 suggests that the 50.4% memory reduction mainly comes from the smaller budget i.e, K=3B and memory reservation design. Would DFlash2 achieve similar savings with the same reservation scheme ?
  4. Eq. 7 states (ybRF=ybARy_b^{RF} = y_b^{AR}) but Table 20 reports different accuracy results. Can the authors explain these differences and confirm whether the generated outputs are identical?
  5. Reporting per-request latency (p50/p95/p99) would help show whether the shared-budget approach causes delays for lower-priority requests.
8 comments
AuthorsOpenReview ↗

Response to Reviewer xhbk

Q1(a): In Eq. (2), is CpC_p the Top-k candidate set from DFlash2? What is kk, and how much of the full-vocabulary probability mass does it cover?

Response:
We thank the reviewer for raising this concern. In Eq. (2), Cₚ denotes DFlash2’s Top-16 candidate set at parent node p (k = 16).

We collect 16 snapshots and 2,048 request-rounds from four prefix positions on each of GSM8K, MATH-500, HumanEval, and MT-Bench. At the root, Top-16 retains an average of 94.29%, 98.21%, 97.66%, and 91.38% of the full-vocabulary probability mass, respectively, supporting its coverage across the evaluated datasets.

To directly assess cross-request comparability, we compare Top-16 normalization with full-vocabulary normalization, holding the candidate sets, target-model greedy labels, Global-Forest allocator, and verification budget Kₜ = 384 fixed.

Table R1. Candidate acceptance under Top-16 and full-vocabulary normalization.

BenchmarkTop-16FullΔ (95% CI)
GSM8K2.55082.5371−0.0137 [−0.0438, 0.0154]
MATH-5002.85742.8691+0.0117 [−0.0172, 0.0407]
HumanEval2.91412.9043−0.0098 [−0.0535, 0.0316]
MT-Bench2.44532.4102−0.0352 [−0.0754, 0.0019]

Top-16 / Full: mean acceptable candidates per request-round under Top-16 / full-vocabulary normalization. Δ: Full − Top-16. CI: confidence interval.

All four confidence intervals include zero, indicating no statistically distinguishable improvement in candidate coverage from full-vocabulary normalization under the tested conditions. Thus, although Top-16 normalization omits some probability mass, we observe no corresponding degradation in cross-request candidate allocation in these experiments.


Q1(b): If this coverage varies across requests, are the priority scores ρθ(v)\rho_{\theta}(v) reliable for cross-request comparisons?

Response:

RF uses candidate priorities ρθ(v)\rho_{\theta}(v) to allocate the shared budget. Eq. (11) interprets these priorities as candidate coverage probabilities under a score-induced auxiliary path distribution; Proposition 1 guarantees only surrogate optimality under fixed scores and unit node costs. Practical effectiveness therefore depends on whether the scores distinguish candidate utility across requests.

We directly evaluate cross-request ranking and candidate acceptance coverage using fixed request prefixes, candidate pools, and verification budgets, with paired offline replay of Equal-Forest (EF) and RF (Table R2).

Table R2. Cross-request ranking accuracy and candidate acceptance gains.

WorkloadRank Acc. ↑EF ↑RF ↑Gain ↑
GSM8K97.52%2.40872.7886+15.77%
MATH-50098.19%2.49022.9248+17.45%
HumanEval99.18%2.59622.9771+14.67%
MT-Bench97.53%1.87262.5220+34.68%
Mixed98.39%2.36332.9165+23.41%

Rank Acc.: cross-request ranking accuracy. EF / RF: mean acceptable candidates per request-round under Equal-Forest / RF. Gain: RF’s relative improvement over EF. Mixed: requests from all four benchmarks.

Cross-request ranking accuracy reaches 97.52%–99.18% across the four benchmarks, while RF increases acceptable candidates per request-round by 15.77%–34.68% over EF. For mixed requests from all four benchmarks, ranking accuracy reaches 98.39%, and acceptable candidates increase from 2.3633 to 2.9165 (+23.41%).

These results support effective cross-request candidate selection and improved acceptance coverage under the evaluated candidate distributions and shared-budget settings.

AuthorsOpenReview ↗

Response to Reviewer xhbk

Q2: How well do the priority scores ρθ(v)\rho_{\theta}(v) predict actual token acceptance across tree depths, for both main paths and alternative branches?

Response:
We thank the reviewer for this question. Table R3 directly evaluates how candidate priorities predict actual target-model acceptance. We fix the candidate pool before RF selection and label a candidate as a hit if its complete path matches the target model’s greedy continuation.

We report hit rates and AUROC separately for main paths and alternative branches at depths 1–7.

Table R3. Acceptance prediction across depths and branch types.

DepthMain NMain HitMain AUCAlt. NAlt. HitAlt. AUC
18,19288.44%0.941724,5762.84%0.9378
28,19276.42%0.936632,7682.17%0.9394
38,19266.04%0.941640,9601.80%0.9349
48,19257.20%0.947449,1521.54%0.9407
58,19251.49%0.947857,3441.21%0.9428
68,19245.19%0.951565,5361.02%0.9488
78,19239.36%0.952273,7280.87%0.9519

Main / Alt.: main-path / alternative-branch candidates. N: candidate count. Hit: fraction whose complete paths match the target model’s greedy continuation. AUC: area under the ROC curve.

AUROC ranges from 0.9366–0.9522 for main paths and 0.9349–0.9519 for alternative branches. Although hit rates decrease with depth, AUROC remains approximately 0.94–0.95, demonstrating strong ranking performance across depths and branch types.

These findings support the practical use of the coverage surrogate in Eq. (11) for candidate ranking.


Q3: Can DFlash2 achieve similar memory savings with the same reservation scheme?

Response:
DFlash2 can achieve verification-state memory savings with the same budget and reservation scheme.

We therefore distinguish memory savings from the throughput benefits of joint candidate allocation. RF’s overall gains reflect both verification-resource configuration and candidate-allocation optimization.

To isolate these effects, we compare equal-chain (EC), global-chain (GC), equal-forest (EF), and global-forest (GF) under matched verification resources (Table R4). GC applies shared-budget allocation to DFlash2’s candidate chains, while GF additionally allows candidate branches to compete across requests.

Table R4. Component comparison of budget sharing and branch selection (throughput: tokens/s).

MethodQwen ↑Ornith ↑
EC2135.33860.8
GC2285.44130.7
EF2270.14108.9
GF2398.84335.7

EC / GC: equal-budget / shared-budget chains. EF / GF: equal-budget / shared-budget forests; GF is RF’s forest execution path. Qwen: Qwen3.8-27B. Ornith: Ornith-1.5-35B-A3B.

Budget sharing improves throughput by approximately 7.0% (EC → GC), and branch selection adds approximately 5.0% (GC → GF) on both models. GF also outperforms independently allocated forests (EF) by 5.67% on Qwen and 5.52% on Ornith.

These results demonstrate that the memory savings are attributable to resource provisioning, while joint allocation provides additional throughput gains under matched resources.


Q4: Why do Eq. (7) and Table 20 suggest different conclusions about output equivalence? Are the generated outputs identical?

Response:
Eq. (7) expresses equivalence under ideal arithmetic, assuming identical prefixes, state-update semantics, greedy decoding rules, and stopping criteria.

Different computation layouts and execution paths can introduce numerical differences. When competing token scores are close, these differences can change the greedy selection, alter subsequent generation, and affect task accuracy. We will revise Eq. (7) and the accompanying text to make this distinction explicit.

As an additional quality check, we measure perplexity under the evaluation settings (Table R5).

Table R5. Perplexity comparison under the evaluation settings.

MethodPPL ↓Change vs. AR
AR1.097617—
DFlash21.098079+0.0421%
RF1.097735+0.0108%

PPL: perplexity. Change vs. AR: relative PPL change compared with target-only autoregressive decoding.

RF’s PPL differs from target-only autoregressive decoding (AR) by only +0.0108%. This indicates similar aggregate predictive quality, but does not establish identical generated sequences.

AuthorsOpenReview ↗

Response to Reviewer xhbk

Q5: Does shared-budget allocation increase latency for lower-priority requests?

Response:
RF allocates verification resources by candidate priority rather than fixed per-request quotas. We therefore compare Equal-Forest (EF) and RF across Easy, Medium, and Hard requests under identical requests and load conditions, reporting request-level latency and budget allocation in Table R6.

Table R6. Budget allocation and request latency by difficulty group.

GroupMethodRZCRTPOT p50 ↓TPOT p95 ↓p95 End-to-End Latency (ms) ↓
EasyEF1.0010.00%164.374015.42435,791.90
EasyRF1.1966.59%149.874001.39430,512.87
MediumEF0.9990.00%174.901880.39436,706.55
MediumRF1.0267.31%168.821819.50434,090.11
HardEF1.0010.00%196.412919.77434,310.65
HardRF0.9049.69%195.322894.91435,413.14

R: normalized candidate budget relative to equal budgeting. ZCR: zero-candidate round rate (%). TPOT p50 / TPOT p95: p50 / p95 time per output token (ms/token).

Relative to EF, RF increases the candidate budget for Easy requests by 19.5% and reduces it for Hard requests by 9.7%. Hard requests achieve 0.55% and 0.85% lower TPOT p50 and p95, respectively, with only a 0.25% increase in p95 end-to-end latency. Easy and Medium requests achieve TPOT p50 reductions of 8.82% and 3.48%, and p95 end-to-end latency reductions of 1.21% and 0.60%, respectively.

These results show that RF improves efficiency for easier requests without materially worsening the measured latency of difficult requests under the evaluated load.


▪ We thank the reviewer for the constructive comments, which help us clarify our contributions and strengthen the evaluation. Weakness 1 is identical to Q1(a) and Q1(b) and is addressed in those responses. One point in Weakness 2 overlaps with Q3 and is addressed there. We organize the remaining, non-overlapping concerns into Weaknesses 2-A 2-B 2-C below.


Weakness 2-A: Does budget sharing still improve throughput when branching is already enabled?

Response:
We thank the reviewer for identifying this missing comparison. The original EC → GC and GC → GF ablations isolate budget sharing for chains and branching under a shared budget, but do not directly test budget sharing when branching is already enabled.

We therefore add Equal-Forest (EF). EF and Global-Forest (GF) use identical candidate trees, drafter, scoring rules, total verification budget, and execution backend. Only budget allocation differs: EF assigns fixed per-request quotas and independently selects branches, whereas GF lets candidate nodes compete across requests under a shared budget.

Table R7. Controlled comparison of budget sharing and branching (throughput: tokens/s).

MethodBudgetStructureQwen3.8-27B ↑Ornith-1.5-35B-A3B ↑
ECFixedChain2135.33860.8
GCSharedChain2285.44130.7
EFFixedTree2270.14108.9
GFSharedTree2398.84335.7

Fixed: fixed per-request quotas. Shared: a shared budget across requests. GF: RF’s forest execution path.

As shown in Table R7, GF outperforms EF by 5.67% on Qwen and 5.52% on Ornith. Together, the four configurations complete the comparison of budget sharing and branching: EC → GC yields approximately 7.0%, EC → EF yields 6.3%–6.4%, and GC → GF adds approximately 5.0%.

The EF → GF comparison directly demonstrates that cross-request allocation provides additional throughput gains even when multi-branch selection is already available, under matched verification resources.

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

The paper introduces Request Forest (RF) which is a decoding framework that jointly grows verification trees across multiple requests under a shared budget. RF uses a lightweight draft model to generate candidate token sequences and provides predecessor conditioned scores to prioritize nodes. It allocates a shared verification budget across requests, determines per request tree depth and branching, packs the forest into a compact branch isolated layout, verifies it in a single target model forward pass, and commits only the states of accepted paths. Theoretical analysis shows that under specific scoring assumptions, the growth strategy maximizes the sum of node priorities. Experiments on several models and benchmarks demonstrate substantial throughput gains at high concurrency and reduced intermediate verification memory.

Critical strengths
  • The shared budget mechanism enables more efficient use of limited verification resources, leading to significant throughput improvements.

  • The analysis connects scoring assumptions to expected coverage and establishes optimality, offering a principled foundation for the method.

  • Strong gains and memory reductions

  • Evaluated on multiple models and benchmarks

Critical weaknesses
  • The method relies on several hyperparameters whose impact is not fully discussed.

  • Optimality claims depend on uniform node costs and specific scoring rules that may not hold in practice, potentially limiting the generality of the results.

  • Experiments focus on a relatively small set of tasks; broader evaluation (e.g., longer contexts, different domains) would strengthen the claims.

Questions for authors
  • How does RF’s performance vary with different draft model qualities or draft model architectures?

  • What is the effect of the window size W on throughput and memory? Are there diminishing returns or trade offs?

  • How does the shared budget ensure fairness among requests, especially when requests differ in difficulty or token generation difficulty?

  • Does the method maintain its advantages at very high concurrency or does performance degrade?

  • How does the branch isolated verification layout affect the target model’s ability to handle long sequences or complex dependencies?

  • What are the trade offs between the added complexity of forest construction and the observed throughput gains?

5 comments
AuthorsOpenReview ↗

Response to Reviewer Q6sF

Q1: How does RF’s performance vary across draft models?

Response:
We thank the reviewer for asking about RF’s applicability across draft models. RF is designed for block-parallel diffusion drafters, using their parallel candidates and conditional scores to jointly select requests and candidate branches under a shared verification budget. We therefore evaluate RF across different diffusion drafting methods.

We integrate RF with DFlash, DFlash2, and DSpark and compare each against its native verification pipeline using the same target model, batch size, and evaluation datasets.

Table R1. Throughput across drafters (tokens/s). Each entry reports native / RF throughput; average gains are computed across the three datasets.

Batch size BDrafterGSM8K ↑MATH-500 ↑HumanEval ↑Average RF gain
96DFlash22076.68 / 2167.782473.57 / 2779.552254.65 / 2690.00+12.02%
96DFlash1374.10 / 1613.541739.63 / 1851.421744.75 / 1857.79+10.11%
96DSpark1765.02 / 1782.732102.55 / 2203.371899.52 / 2081.53+5.13%
128DFlash22190.10 / 2378.732541.65 / 2931.882307.50 / 2893.45+16.45%
128DFlash1532.00 / 1911.411569.45 / 2016.651614.30 / 1980.68+25.32%
128DSpark2031.00 / 2068.122160.42 / 2264.231961.71 / 2184.00+5.99%
144DFlash22319.50 / 2496.452641.42 / 2964.032392.15 / 2949.68+14.38%
144DFlash1610.95 / 1989.851937.63 / 2106.911906.43 / 2038.75+13.07%
144DSpark1971.91 / 2001.542245.02 / 2371.662033.30 / 2199.33+5.10%

Table R2. Reserved memory for SSM verification states across drafters. Memory is measured in GiB per TP rank; reductions are relative to the native verification pipeline.

Batch size BDrafterRF memory (GiB) ↓Memory saved (GiB)Memory reduction
96DFlash217.289.5635.62%
96DFlash13.640.141.02%
96DSpark13.360.282.05%
128DFlash218.0018.2850.39%
128DFlash18.140.140.77%
128DSpark18.100.281.52%
144DFlash220.2520.5350.34%
144DFlash20.391.838.24%
144DSpark20.381.707.70%

These results show that RF consistently improves throughput and reduces SSM verification-state memory across the evaluated diffusion drafters, demonstrating its broad applicability and transferability. Its benefits extend beyond a single draft model: more efficient verification-budget allocation improves inference efficiency across drafters, making RF an effective and promising optimization approach for block-parallel diffusion inference.


Q2: How does window length affect throughput and memory usage?

Response:
We evaluate different window lengths at a batch size of 128. W = 8 achieves the highest throughput on both models. Reducing the window to W = 4 decreases throughput by 6.49% on Qwen and 6.02% on Ornith, while reserved SSM memory remains nearly unchanged. The smaller window limits the number of candidates retained per request but provides no corresponding memory savings under the current budget and allocation settings.

Increasing the window to W = 16 decreases throughput by 1.62% and 1.54%, respectively, while increasing reserved intermediate SSM memory by approximately 96.9% and 97.2%. These results indicate diminishing returns from larger windows: broader candidate coverage does not offset the additional resource overhead.

Table R3. Effect of window length on throughput and reserved SSM verification-state memory at batch size B = 128.

ModelWindow WThroughput ↑ (tokens/s)Change vs. W = 8SSM verification memory ↓ (GiB/rank)
Qwen3.8-27B42471.8−6.49%18.00
Qwen3.8-27B8 (default)2643.40%18.00
Qwen3.8-27B162600.7−1.62%35.44
Ornith-1.5-35B-A3B44814.3−6.02%7.48
Ornith-1.5-35B-A3B8 (default)5122.50%7.49
Ornith-1.5-35B-A3B165043.8−1.54%14.77
AuthorsOpenReview ↗

Response to Reviewer Q6sF

Q3: How does the shared budget maintain fairness across requests of varying difficulty?

Response:
We thank the reviewer for raising this fairness concern. RF allocates verification resources by candidate priority rather than fixed per-request quotas. To assess its impact on difficult requests, we compare Equal-Forest (EF; equal budgets) and RF (shared budget) across Easy, Medium, and Hard groups under identical requests and load conditions (Table R4). We report the zero-candidate round rate, the fraction of rounds receiving no candidate budget, and the normalized candidate budget, R, the allocated candidate count relative to equal budgeting.

Compared with EF, RF increases the candidate budget for Easy requests by 19.5% and reduces it for Hard requests by 9.7%. Despite receiving no additional candidates in 9.69% of rounds, Hard requests achieve 0.55% and 0.85% lower TPOT p50 and p95, with only a 0.25% increase in p95 end-to-end latency. Easy and Medium requests achieve TPOT p50 reductions of 8.82% and 3.48%, and p95 end-to-end latency reductions of 1.21% and 0.60%, respectively.

Thus, under the evaluated load, RF improves efficiency for easier requests without materially degrading TPOT or tail latency for difficult requests.

Table R4. Budget allocation and latency by request difficulty.

GroupMethodRZCRT50 ↓T95 ↓L95 ↓
EasyEF1.0010.00%164.374015.42435,791.90
EasyRF1.1966.59%149.874001.39430,512.87
MediumEF0.9990.00%174.901880.39436,706.55
MediumRF1.0267.31%168.821819.50434,090.11
HardEF1.0010.00%196.412919.77434,310.65
HardRF0.9049.69%195.322894.91435,413.14

R: normalized candidate budget relative to equal budgeting.

ZCR: zero-candidate round rate (%).

T50 / T95: p50 / p95 time per output token (ms/token).

L95: p95 end-to-end latency (ms). ↓: lower is better.


Q4: How does RF perform under extremely high concurrency?

Response:
We thank the reviewer for this question. We further evaluate latency near the GPU memory capacity limit on Qwen3.8-27B, using a fixed maximum output length of 512 tokens.

As shown in Table R5, RF reduces p95 end-to-end latency relative to MTP by 7.88% at B = 224 and 5.50% at B = 256, retaining a performance advantage at extremely high concurrency. However, p95 TTFT increases by 1.22% and 3.98%, respectively, indicating a trade-off between first-token latency and overall completion time.

Table R6 highlights the capacity constraint. Increasing concurrency from 224 to 256 raises reserved intermediate SSM verification-state memory from 31.50 to 36.00 GiB/rank, reduces KV capacity from 530,791 to 240,048 tokens, and triggers 30 retractions, indicating that the system is approaching its memory limit.

Thus, RF continues to improve end-to-end completion time at extremely high concurrency, but its gains do not scale indefinitely. As verification-state reservations grow and available KV capacity shrinks, queueing, retractions, and tail latency may become bottlenecks. We will clarify this capacity–latency trade-off in the revised manuscript.

Table R5. Per-request tail latency at extremely high concurrency.

Concurrency limit BMethodTTFT p95 ↓ (s)End-to-end latency p95 ↓ (s)
224MTP3.59479.446
224RF3.63873.185
256MTP3.99683.512
256RF4.15578.923

Table R6. RF capacity and mean TTFT at extremely high concurrency (Table 14 in the original manuscript).

Concurrency BReserved SSM memory (GiB/rank)KV capacity (tokens)Mean TTFT on GSM8K (s)Retraction count
22431.50530,7912.1540
24033.75385,4204.1320
25636.00240,0484.28030
AuthorsOpenReview ↗

Response to Reviewer Q6sF

Q5: Branch visibility and state consistency with long contexts.

Response:
RF’s branch isolation restricts visibility between candidate branches without truncating the committed history. As described in Appendix B, each candidate node accesses the complete cached history and its own root-to-node path, with correct position IDs and parent-state indices preserving computational dependencies.

We compare forest verification against sequential target-model forward passes on Qwen3.8-27B with committed histories of 1,024, 8,192, and 32,768 tokens, checking node visibility, position IDs, recurrent-state dependencies, and numerical outputs.

Across all 45 evaluated nodes, we observe zero visibility, position-ID, or parent-state indexing errors, with 100% Top-1 prediction agreement between forest and sequential execution (Table R7). Maximum relative errors are 0.009595 for SSM states and 0.013424 for convolution states, with no consistent increase as history length grows.

These results confirm that, under the tested context lengths and branch configurations, RF preserves history visibility and recurrent-state dependencies while maintaining consistent target-model Top-1 predictions. We will add these structural checks and numerical comparisons to the revised manuscript, clarifying finite-precision state differences and the evaluation scope.

Table R7. Visibility, position, and state checks across history lengths on Qwen3.8-27B.

LengthNodesVis.Pos.ParentΔLogitTop-1 ↑SSM ↓Conv. ↓
1,024170000.640625100%0.0095950.012683
8,192150000.375000100%0.0032540.006929
32,768130000.432656100%0.0091910.013424

Length: committed history length (tokens). Vis. / Pos. / Parent: counts of visibility-set, position-ID, and parent-state indexing errors, respectively. ΔLogit: maximum absolute logit difference. Top-1: prediction agreement under identical prefixes. SSM / Conv.: relative errors in SSM and convolution states, respectively.


Q6: Forest construction overhead and net performance gains

Response:
We thank the reviewer for this question. RF extends the independently constructed trees in Equal-Forest (EF) with cross-request candidate competition and global budget allocation, introducing additional selection and bookkeeping overhead. Table R8 evaluates whether this overhead is offset by gains in effective output and end-to-end throughput.

On Ornith-1.5-35B-A3B and GSM8K, with B = 128, W = 8, and K = 384, RF increases per-round execution time by approximately 2.7%, but raises effective output tokens per round from 436.31 to 484.94 (+11.15%). Consequently, amortized time per output token decreases from 0.1984 to 0.1834 ms (−7.56%).

These gains translate into 5,452.0 tokens/s end-to-end throughput, outperforming EF by 8.20% and the shared-budget chain baseline (GC) by 6.19%. Thus, the additional effective output from broader candidate coverage offsets forest-allocation overhead, reducing per-token cost and improving end-to-end throughput.

Table R8. Per-token cost and end-to-end throughput.

MethodRound ↓Tokens ↑Cost ↓Throughput ↑Gain ↑
EC86.58412.510.20994763.8−5.46%
GC86.59444.580.19475134.2+1.90%
EF86.58436.310.19845038.70%
RF88.95484.940.18345452.0+8.20%

EC: equal-budget chains. GC: shared-budget chains. EF: Equal-Forest. RF: shared-budget forest. Round: total execution time per round (ms). Tokens: effective output tokens per round across the batch. Cost: amortized time per output token (ms/token). Throughput: end-to-end throughput (tokens/s). Gain: throughput improvement over EF.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.