acceptodds
Under review as a conference paper at ICLR 2027

Co-Evolving Trees and Control Policies: Bridging Posterior Optimality and Online Efficiency in Speculative Decoding

Abstract

Tree-based speculative decoding accelerates LLM inference through parallel verification of candidate continuations. Posterior verification records and a calibrated latency model enable statistically optimized tree portfolios with near-optimal surrogate throughput in a finite candidate space. Pre-drafting routing, however, commits an entire cycle with limited information, making mistaken template choices costly and hindering realization of posterior gains. Our preliminary experiments identify two advantages of decisions during drafting: richer observations and reuse of shared computation across alternative actions. We therefore formulate an ideal joint objective for draft structures and online policies: expected committed tokens per expected complete-cycle time. We propose Oracle-Guided Structure–Policy Optimization (OGSPO), using a common net-gain objective for coupled conditional updates. It first solves for posterior-optimal decision depths using verification records and modeled costs in a mixed-integer fractional program, then alternates policy and structure updates. With the draft structure fixed, posterior records and a latency model estimate every legal terminal action’s net gain for policy learning. Sampled same-trace executions correct policy-improvement estimates. With the policy response fixed, state-conditioned reach and stop probabilities weight mixed-integer optimization of the shared nested draft structure. We establish conditional unbiasedness of policy-improvement estimates under the sampling protocol and finite-domain optimality bounds for the structural proxy under a fixed response. Across twelve configurations spanning three models, four devices, and two temperatures, OGSPO improves four-workload mean complete-request throughput over EAGLE-3 by 9.2% on average and up to 19.3%. Comparisons and ablations further support the benefits of joint structure–policy design.

Primary area:
optimization
Keywords:
speculative decoding, large language model inference, adaptive inference, draft tree optimization, online decision making, efficient LLM inference

Reviews

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

The paper jointly optimizes speculative draft trees and the policy that decides when to stop drafting and how many candidates to verify. It alternates offline tree search with policy updates and uses sampled execution feedback to correct its performance estimates. Overall, the paper is a valid, incremental contribution to the community, but I still have several concerns on the novelty and other aspects.

Critical strengths
  1. Optimizing actual decoding time rather than acceptance length alone is a good direction.
  2. I appreciate the effort to separate the gains from changing the tree and adapting the controller. The ablations make the contribution easier to assess.
  3. Testing several model families and hardware platforms is useful, especially for a method that depends on runtime costs.
Critical weaknesses
  1. I am not fully convinced by the novelty of the paper. For example, adaptive tree construction and draft stopping are already well-studied in the prior works. Jointly optimizing them is reasonable and expected, but the paper needs to make clearer what this adds beyond combining these existing ideas (A+B). The gains over Learning to Draft are sometimes only a few percent, which makes the added complexity harder to justify.

  2. The serving relevance remains unclear in the manuscript. Dynamic trees are difficult to support efficiently at high concurrency, and the evaluation is mainly batch size 1. How would the controller's variable stopping points and verification budgets work with continuous batching and CUDA graphs in SGLang or vLLM? Without an implementation or measurements in such a setting, I find it hard to judge whether the gains would survive production deployment.

  3. The offline optimization pipeline also needs a clearer cost breakdown. Each deployment configuration requires traces, latency fitting, policy updates, and integer optimization. How much wall-clock time and GPU compute does this take, and what needs to be repeated when the workload or hardware changes? Reporting normalized feedback budgets alone does not tell me whether the relatively modest serving gains repay the setup cost.

Questions for authors

Please see weaknesses section above.

Though the authors have provided a rebuttal, these issues seem to persist and I recommend the authors to reposition especially the novelty of this paper.

6 comments
AuthorsOpenReview ↗

oCuF · Response 1

Visual Walkthrough (Click: https://iclr27-paper47457.pages.dev): We recommend visiting for animations contrasting runtime tree adaptation with our offline static template and explain U0–U1–U2. The responses below are self-contained.

We thank Reviewer oCuF for recognizing our focus on decoding time over acceptance length, our tree/controller ablations, and our cross-platform evaluations.

Response 1: What Does OGSPO Fundamentally Add Beyond "Adaptive Tree Construction" and Draft Stopping? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 1: What Does OGSPO Fundamentally Add Beyond "Adaptive Tree Construction" and Draft Stopping? (}W1 — Part 1)

W1 “Adaptive tree construction and draft stopping are already well-studied directions. … what this adds beyond combining existing ideas.”

R1-Key Point: OGSPO is not runtime heuristic "adaptive tree construction": it solves a static, statistically throughput-optimal\small\colorbox{#244F78}{\color{white}\textbf{static, statistically throughput-optimal}} shared nested template offline and uses delayed-decision nested optimization (U0/U2) plus counterfactual residual-corrected policy learning (U1) to unlock the posterior theoretical ceiling that isolated pre-drafting portfolios fail to release.

Details follow:

Honestly, we disagree with categorizing OGSPO as "adaptive tree construction" or viewing it as a combination of existing heuristics (W1).

  • Division of Labor: Offline Static Optimal Template vs. Lightweight Online Control: In this context, "adaptive" strategies adjust hyperparameters—such as draft depth, width, or node budgets—dynamically at runtime via proxy signals. We understand why one might view such surface-level tuning skeptically. However, although OGSPO includes a lightweight online continue/stop controller, the tree structure in OGSPO is fundamentally static, not dynamically constructed at runtime. Specifically, the controller's purpose is to unlock the ceiling of a single, statistically throughput-optimal shared nested template Γ=(U1,…,UJ)\Gamma=(U_1,\dots,U_J) solved offline over a reference state distribution and reused statically across diverse datasets and states: the static template fixes candidate paths offline, while the controller only decides when to stop along pre-planned stages and which top-KK budget to verify.
  • From Heuristic Adjustment to Approaching Theoretical Optimality (What Is Truly New):
    • R1-1: Foundational Mathematical Asset:\rule{0pt}{2.52em}\color{#315B75}\textsf{R1-1: Foundational Mathematical Asset:}
      Using a calibrated latency predictor and integer programming to solve for statistically optimal static trees or portfolios is our starting point (§3.2, App. C.4), explicitly calibrating the posterior theoretical throughput ceiling and statistically optimal tree portfolios in a finite candidate domain.
    • R1-2: The Pre-Drafting Information Bottleneck:\rule{0pt}{2.52em}\color{#315B75}\textsf{R1-2: The Pre-Drafting Information Bottleneck:}
      However, our preliminary study (§3.2, Fig. 1 & App. D) reveals a severe capability bottleneck when static portfolios are used in isolation: the best held-out selector recovered only 2.0% of the posterior portfolio gain (vs. 50%–76% with verification-informed selection).
    • \rule{0pt}{2.52em}\color{#315B75}\textsf{R1-3: Unlocking the Ceiling via Co-Evolving Nested Structures \\& Residual-Corrected Control:}
      Anchoring our formulation on an explicit posterior optimality ceiling fundamentally separates OGSPO from methods that tweak local expansion heuristics or restricted template families. OGSPO bridges the gap to this ceiling via two coupled mechanisms:
      • Delayed-Decision Nested Topology Optimization (U0 & U2): Instead of pre-drafting choices among disjoint trees, U0 solves a mixed-integer fractional program for posterior-optimal decision depths under complete costs (Eq. 7), and U2 compiles a shared nested structure weighted by the controller's state-conditioned reach and stop probabilities (Rj0,qjh0R_j^0, q_{jh}^0) under a fitted proxy with finite-domain optimality bounds (Eq. 20).
      • Counterfactual Full-Action Policy Learning with Same-Trace Residuals (U1): Rather than learning from sparse executed actions alone, U1 uses posterior target records to value every legal terminal action counterfactually, while sparse same-trace execution residuals\small\colorbox{#E4F2EF}{\textsf{same-trace execution residuals}} correct surrogate bias (provably conditionally unbiased, Eq. 9 & App. A.2 Eq. 15). Across 16 seeds (Fig. 4, §5.3), residual correction reaches the 1.08$\times$ target in 16/16 runs at budget 15, vs. 9/16 for sampled feedback and 1/16 for model-only.
      • Direct Link to Global Throughput: Via Jρ(Γ,π)=Aμ(Γ,π)−ρBμ(Γ,π)J_\rho(\Gamma,\pi)=A_\mu(\Gamma,\pi)-\rho B_\mu(\Gamma,\pi), every local update remains strictly tethered to the ideal global throughput objective\small\colorbox{#EAF0F7}{ideal global throughput objective} (η∗=sup⁡Γ,πE[G]/E[T]\eta^* = \sup_{\Gamma,\pi} \mathbb{E}[G]/\mathbb{E}[T])—a paradigm shift from ad-hoc runtime tuning to systematically learning and approaching theoretical posterior optimality.
AuthorsOpenReview ↗

oCuF · Response 2

Response 2: Do the Throughput Gains Over LTD Justify OGSPO’s Optimization Complexity? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 2: Do the Throughput Gains Over LTD Justify OGSPO's Optimization Complexity? (}W1 — Part 2)\color{#4472C4}\small\textsf{— Part 2)}

W1 “The gains over Learning to Draft are sometimes only a few percent … the added complexity harder to justify.”

R2-Key Point: Yes—Main Table 1 disables CUDA Graphs for algorithmic parity; same-method runtime optimizations add \small\colorbox{#244F78}{\color{white}\textbf{+2.54\\% to +9.07\\%}} in Table H1, our solved static template embeds over 20% posterior decision headroom in a controlled fixed-template analysis (Table N2), and all solver complexity stays strictly offline.

Our detailed evidence on hardware potential, decision headroom, and online simplicity follows below:

  • \rule{0pt}{2.52em}\color{#315B75}\textsf{R2-1: Algorithmic Gains \\& Same-Method Engineering Potential (Table H1):}
    With CUDA Graphs disabled in Main Table 1 (B=1B=1), OGSPO improves 4-task mean throughput over LTD by +5.13% (T=0T=0: 138.3→145.4 TPS138.3 \rightarrow \mathbf{145.4\text{ TPS}}) and +8.84% (T=1T=1: 101.8→110.8 TPS101.8 \rightarrow \mathbf{110.8\text{ TPS}}) on H800 (and up to +19.3% over native EAGLE-3 across 12 settings), while controlled ablations across 6 paired groups (Fig. 3a) show policy adaptation on the new structure nearly doubles the median structural gain (1.022×→1.043×1.022\times \rightarrow \mathbf{1.043\times}, vs. 1.016×1.016\times for equal extra training on the old tree). Because OGSPO's shared nested template fixes candidate layouts offline, it supports pre-compiled indexing, cache reuse, and CUDA Graphs. Table H1 isolates these same-method engineering gains (holding token outputs and decisions identical before vs. after optimization): capturing the B=1B=1 MLP actor in CUDA Graphs cuts per-call latency from 0.430 ms0.430\text{ ms} to 0.144 ms0.144\text{ ms} (+2.54%), combined runtime optimization on the 4-stage nested policy adds +9.07% across 400 requests, and verification packing\small\colorbox{#E4F2EF}{\textsf{verification packing}} on the 48-node B=4B=4 system adds +3.40%.
  • \rule{0pt}{2.52em}\color{#315B75}\textsf{R2-2: Over 20\\% Latent Decision Headroom Within Solved Static Templates:}
    In a controlled decision-accuracy analysis on 419 sampled HumanEval states (B=1,T=1B=1, T=1, 4-exit nested template after the third structural update), 100% posterior action selection within the finite menu exceeds the best fixed exit/pruning combination in that tree by \small\colorbox{#EAF0F7}{+24.08\\% in statewise local rate} (118.96→147.60 TPS118.96 \rightarrow \mathbf{147.60\text{ TPS}}) and +26.87% in global progress-to-time ratio (120.25→152.57 TPS120.25 \rightarrow \mathbf{152.57\text{ TPS}}). As stop/continue decision accuracy scales to 80%, 90%, and 95%, the same static template yields +13.66%, +18.70%, and +21.34% local rate gains (Table N2).
  • R2-3: Offline Complexity vs. Lightweight Online Execution:\rule{0pt}{2.52em}\color{#315B75}\textsf{R2-3: Offline Complexity vs. Lightweight Online Execution:}
    While offline optimization is rigorous, its preparation costs include data collection as well as fitting (R4, Table S1), whereas online inference requires only a lightweight controller—either the 512K-parameter MLP (0.144 ms0.144\text{ ms}/call with CUDA Graph capture) in our B=1B=1 route or a compact regression tree in our B=4B=4 route—acting on a pre-solved static nested structure.

Table H1: Same-Method Runtime Improvements on H800 (Holding Decisions & Outputs Identical)

\bbox[#E9E5EF]{\small\textbf{Optimization}}\bbox[#E9E5EF]{\small\textbf{Evaluation Scope}}\bbox[#E9E5EF]{\small\textbf{Before (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{After (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{Gain}}
Controller CUDA Graph capture (B=1B=1)Single-request controller (0.430→0.144 ms0.430 \rightarrow 0.144\text{ ms})142.44146.06+2.54%
Combined runtime optimization (B=1B=1)Five held-out tasks (400 requests)100.03109.10+9.07%
Verification packing (B=4B=4)ShareGPT development requests (cap 512)232.98240.90+3.40%


Table N2: Local Decision Headroom Within Solved Static Nested Templates (B=1B=1, H800, T=1T=1)

\bbox[#E9E5EF]{\small\textbf{Template \\& Diagnostic Scope}}\bbox[#E9E5EF]{\small\textbf{Baseline Reference TPS}}\bbox[#E9E5EF]{\small\textbf{@ 80\\% Acc.}}\bbox[#E9E5EF]{\small\textbf{@ 90\\% Acc.}}\bbox[#E9E5EF]{\small\textbf{@ 95\\% Acc.}}\bbox[#E9E5EF]{\small\textbf{@ 100\\% Posterior Ceiling}}
4-Exit Template (419 States, Stop Acc.)118.96 (Best fixed exit)135.20 (+13.66%)141.21 (+18.70%)144.35 (+21.34%)147.60 (+24.08% local / +26.87% ratio)
4-Exit Template (419 States, Stop+Prune Acc.)118.96 (Best fixed exit)129.94 (+9.23%)138.21 (+16.18%)142.76 (+20.01%)147.60 (+24.08%)

AuthorsOpenReview ↗

oCuF · Response 3&4

Response 3: How Does OGSPO Work with Batched Serving, Continuous Batching, and CUDA Graphs? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 3: How Does OGSPO Work with Batched Serving, Continuous Batching, and CUDA Graphs? (}W2)

W2 “the controller's variable stopping points and verification budgets work with continuous batching and CUDA graphs in SGLang or vLLM?”

R3-Key Point: Because OGSPO fixes its nested stage topology offline, it naturally supports CUDA Graph capture and verification packing (+3.40% at B=4B=4), while improving held-out B=4B=4 ShareGPT throughput by \small\colorbox{#244F78}{\color{white}\textbf{+46.11\\%}} and +25.52% even under a basic shared-stop batch executor (Table B1).

Serving details and results follow:

Adapting to a batched executor recalibrates T^\hat{T}, solves a batch-specific tree, and trains the controller; existing acceptance records remain directly reusable\small\colorbox{#EAF0F7}{directly reusable}.

  • Empirical Confirmation Under Simple Shared Stopping:\rule{0pt}{2.52em}\color{#315B75}\textsf{Empirical Confirmation Under Simple Shared Stopping:}
    In our measured B=4B=4 implementation, the batch continues drafting or enters verification together, while each request maintains separate candidate tokens, accepted lengths, masks, KV caches, and retained budgets. The batch-adapted controller stops at the first decision point in 74.60% of cycles. Independent stopping can instead group stopped requests in a verification queue while accounting for waiting and packing costs in T^\hat{T}.
  • \rule{0pt}{2.52em}\color{#315B75}\textsf{CUDA Graphs \\& Serving-Engine Integration:}
    Fixing the tree topology offline makes its stage layouts amenable to pre-compilation, cache reuse\small\colorbox{#E4F2EF}{\textsf{cache reuse}}, and CUDA Graph capture (0.430→0.144 ms0.430 \rightarrow 0.144\text{ ms} actor capture at B=1B=1). Integrating with continuous-batching engines (SGLang/vLLM) additionally requires the corresponding queue/KV-cache adapter and measurement of its scheduling costs.

Table B1: Batched Complete-Call Throughput on H800 at B=4B=4 (Llama-3.1-8B-Instruct/EAGLE-3, T=1T=1)

\bbox[#E9E5EF]{\small\textbf{Evaluation / EAGLE-3 baseline}}\bbox[#E9E5EF]{\small\textbf{EAGLE-3 → OGSPO (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{Gain}}
ShareGPT, 768-token generation limit; Training-selected depth-3 tree152.52 → 222.83+46.11%
ShareGPT, 1,024-token generation limit; Training-selected depth-8 tree103.95 → 130.48+25.52%


Response 4: What Is the Offline Optimization Cost, and What Must Be Repeated When Workloads or Hardware Change? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 4: What Is the Offline Optimization Cost, and What Must Be Repeated When Workloads or Hardware Change? (}W3)

W3 “How much wall-clock time and GPU compute does this take … what needs to be repeated when the workload or hardware changes?”

R4-Key Point: Data collection is a shared investment; policy fitting on existing records takes seconds\small\colorbox{#BED1E5}{\textbf{takes seconds}} (23.53 s at B=4B=4; 0.56–3.42 s at B=1B=1). The frozen pair transfers across evaluated datasets without per-dataset fitting; hardware or batching shifts require timing calibration and tree–policy updates while reusing acceptance records (Table S1).

Costs and reuse rules follow:

Preparation vs. reuse (\rule{0pt}{2.52em}\color{#315B75}\textsf{Preparation vs. reuse (}W3):

  • Workload Shifts (0 s Retuning): A frozen pair transfers directly across the evaluated datasets without per-dataset fitting, serving the four main tasks and summarization extensions at B=1B=1. At B=4B=4, the ShareGPT-trained pair gains +22.25% on summarization and +9.70% on MBPP against the ShareGPT-selected EAGLE-3 depth-8 baseline. Performance depends on workload and baseline.
  • Batch / Hardware Shifts (Table S1): Hardware or batch-execution changes require new timing calibration and tree–policy updates; acceptance records remain reusable for the same model pair and decoding setting.

Table S1: Logged Preparation and Update Costs (B=4B=4 and B=1B=1 Routes, H800 + CPU)

\bbox[#E9E5EF]{\small\textbf{Stage}}\bbox[#E9E5EF]{\small\textbf{Time}}\bbox[#E9E5EF]{\small\textbf{When needed}}
Initial batched timing-data collection (B=4B=4)2.65 h cumulative worker timeBatch executor timing coverage
Shared acceptance/teacher-data collection (B=4B=4)18.34 minReusable acceptance records
Latency-model fitting (B=4B=4)18.55 sFit to measured execution costs
Batched tree search (B=4B=4)11.06 minUpdate the structure for changed costs or policy
Decision-position evaluation (B=4B=4)5.38 minUpdate decision positions
Controller fitting & cross-validation (B=4B=4)23.53 sFit policy on existing batch records
B=1B=1 route: shared init / feedback / policy refit1.90 h / 135.1–262.9 s / 0.56–3.42 sMLP init / 405-run residual job / panel refit

The timing-collection figure is cumulative worker time, including GPU execution.


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

This paper proposes Oracle-Guided Structure–Policy Optimization (OGSPO), a framework for jointly optimizing draft tree structures and online control policies in tree-based speculative decoding. The key insight is that the value of a draft tree depends on how the controller uses it, while the controller's decisions are constrained by the candidates exposed by the tree. OGSPO addresses this coupling through posterior-guided decision-depth selection, residual-corrected policy optimization, and policy-guided mixed-integer optimization. Experiments across multiple models, hardware platforms, decoding temperatures, and workloads demonstrate consistent throughput improvements over EAGLE-3 and LTD.

Critical strengths
  1. The paper addresses an important inference-efficiency problem and identifies a meaningful limitation of existing approaches that optimize draft tree construction and online drafting control largely separately. The proposed joint structure–policy objective provides a coherent framework for reasoning about committed-token progress and complete-cycle latency.
  2. OGSPO combines posterior-guided decision-depth selection, residual-corrected policy optimization, and MILP-based tree optimization. Theoretical analyses of conditional unbiasedness and structural optimization bounds support key components of the framework.
  3. Experiments show that OGSPO outperforms EAGLE-3 and LTD across multiple models, hardware platforms, decoding temperatures, and workloads. The analytical experiments also provide useful evidence for the benefits of policy adaptation, residual-corrected feedback, and dynamic drafting decisions.
Critical weaknesses
  1. The evaluation lacks direct comparisons with Yggdrasil and SMART. Implementing these methods for tree construction within the same EAGLE-3 framework and comparing them under the same settings would help establish whether OGSPO outperforms these alternatives.
  2. The evaluation focuses on batch-size-one execution, leaving unclear whether OGSPO generalizes to concurrent serving. Moreover, the controller and tree structure are tuned for each setting, it remains unclear whether a learned controller or tree configuration can transfer to other settings without retuning.
Questions for authors
  1. Could the authors compare OGSPO with Yggdrasil and SMART under the same settings using the same EAGLE-3 framework?
  2. Could the authors evaluate OGSPO under concurrent serving and investigate whether a controller–tree configuration tuned for one setting can transfer to other settings without retuning?
6 comments
AuthorsOpenReview ↗

GDLD · Response 1

Visual Walkthrough (Click: https://iclr27-paper47457.pages.dev): We recommend visiting our visual walkthrough for animations of the preliminaries and OGSPO's U0–U1–U2 co-evolution, plus an interactive layout of our rebuttal analyses and tables. All responses below are self-contained.

We thank Reviewer GDLD for recognizing our motivation to resolve the coupling between draft tree construction and online control, our unified progress–time objective, our theoretical guarantees, and our cross-platform evaluations. Below, we address (1) comparisons with Yggdrasil and SMART in the same EAGLE-3 framework (W1, Q1) [R1]; (2) concurrent batched serving (W2, Q2) [R2]; and (3) zero-retuning transferability vs. adaptation across settings (W2, Q2) [R3].

Response 1: Why Were SMART and Yggdrasil Not in the Main Tables, and How Does OGSPO Differ Conceptually? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 1: Why Were SMART and Yggdrasil Not in the Main Tables, and How Does OGSPO Differ Conceptually? (}W1, Q1)

W1 “The evaluation lacks direct comparisons with Yggdrasil and SMART.” Q1 “compare OGSPO with Yggdrasil and SMART under the same settings using the same EAGLE-3 framework?”

R1-Key Point: The main tables use reproducible EAGLE-3 backend comparisons; OGSPO systematically calibrates and approaches a posterior theoretical throughput ceiling\small\colorbox{#244F78}{\color{white}\textbf{posterior theoretical throughput ceiling}} through jointly optimized nested structures and online control (Table C1).

Our detailed explanation and common-backend comparisons follow below:

  • \rule{0pt}{2.52em}\color{#315B75}\textsf{Why Direct Numerical Comparisons Were Omitted (Reproducibility \\& Fairness to Prior Work):}

    • R1-1: Matched Implementation:\rule{0pt}{2.52em}\color{#315B75}\textsf{R1-1: Matched Implementation:}
      A same-backend comparison requires faithfully implementing SMART’s expansion rule and Yggdrasil’s selector and runtime under a common timing protocol.
    • R1-2: Common-Backend Comparisons:\rule{0pt}{2.52em}\color{#315B75}\textsf{R1-2: Common-Backend Comparisons:}
      Our numerical comparisons use GS and LTD in the same EAGLE-3 backend under the complete-cycle timing protocol (Table C1).
  • Beyond Implementation: From Heuristic Adjustment to Approaching Theoretical Optimality: Even setting implementation aside, SMART and Yggdrasil differ fundamentally from OGSPO in how the optimization problem is conceived:

    • Anchoring on Posterior Theoretical Optimality: Before introducing online control, our preliminary formulation (§3.2, App. C.4) establishes a mathematical framework that explicitly calibrates the posterior theoretical throughput ceiling and solves for statistically throughput-optimal tree topologies and portfolios within a finite candidate domain and calibrated cost model. Although online information bottlenecks and selector accuracy prevent an isolated pre-drafting router from fully releasing this multi-tree potential (§3.2, Fig. 1), having an explicit statistically optimal throughput target fundamentally separates our approach from methods that refine local expansion rules or restricted template families.
    • Maintaining the Link to the Ideal Throughput Objective: SMART uses a training-free runtime marginal gain-to-latency rule, while Yggdrasil selects within an equal-growth topology family with a compiler-oriented runtime. In contrast, every local step in OGSPO—position selection (U0), counterfactual full-action policy learning\small\colorbox{#E4F2EF}{\textsf{counterfactual full-action policy learning}} with same-trace residuals (U1), and policy-weighted MILP structure solving (U2)—remains strictly tethered to the ideal global throughput objective (η∗=sup⁡Γ,πE[G]/E[T]\eta^* = \sup_{\Gamma,\pi} \mathbb{E}[G]/\mathbb{E}[T] via our net-gain transformation JρJ_\rho and finite-domain optimality bounds, §3.3–§4.4). This represents a paradigm shift from ad-hoc adaptive adjustment to systematically learning and approaching theoretical optimality.

Table C1: Common EAGLE-3 Backend Comparisons on H800 (Llama-3.1-8B-Instruct/EAGLE-3, B=1B=1)

\bbox[#E9E5EF]{\small\textbf{Evaluation Setting \\& Benchmark Scope}}\bbox[#E9E5EF]{\small\textbf{E3}}\bbox[#E9E5EF]{\small\textbf{GS}}\bbox[#E9E5EF]{\small\textbf{LTD}}\bbox[#E9E5EF]{\small\textbf{Global Single Tree}}\bbox[#E9E5EF]{\small\textbf{OGSPO}}\bbox[#E9E5EF]{\small\textbf{Relative Gain}}
4-Task Mean (T=0T=0, Main Table 1)131.40141.10138.30—145.40+5.13% vs. LTD (+10.65% vs. E3)
4-Task Mean (T=1T=1, Main Table 1)102.00101.90101.80—110.80+8.84% vs. LTD (+8.63% vs. E3)
5-Task 400-Req Paired (T=1T=1, Seed 0 Run 1)———79.1186.53\small\colorbox{#EAF0F7}{+9.37\\% vs. Global Single Tree}
5-Task 400-Req Paired (T=1T=1, Seed 0 Run 2)———77.6084.15+8.45% vs. Global Single Tree
5-Task 400-Req Paired (T=1T=1, Seed 1)———78.3687.12+11.17% vs. Global Single Tree

AuthorsOpenReview ↗

GDLD · Response 2

Response 2: Does OGSPO Generalize to Concurrent / Batched Serving Beyond Batch Size 1? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 2: Does OGSPO Generalize to Concurrent / Batched Serving Beyond Batch Size 1? (}W2, Q2 — Part 1)\color{#4472C4}\small\textsf{— Part 1)}

W2 “whether OGSPO generalizes to concurrent serving.” Q2 “evaluate OGSPO under concurrent serving”

R2-Key Point: Yes—batching is nearly orthogonal to our optimization pipeline (allowing direct reuse of offline acceptance records), and our re-solved B=4B=4 OGSPO system improves held-out ShareGPT throughput by \small\colorbox{#244F78}{\color{white}\textbf{+46.11\\%}} and +25.52% over training-selected EAGLE-3 baselines even under a simple shared-stop rule (Table B1).

Our detailed batched execution analysis and results follow below:

We fully share your view that evaluating performance beyond batch size 1 is essential to assessing practical serving value (W2, Q2). Batching alters GPU utilization, packing, and synchronization, shifting the relative costs of drafting and verification; however, this shift is far from disruptive to our framework—it is nearly orthogonal. Because our objective is parameterized by execution costs, adapting to a batch executor requires only recalibrating the cost model T^\hat{T}, solving a batch-adapted nested tree, and training the controller on that tree—while existing token-acceptance records remain directly reusable\small\colorbox{#E4F2EF}{\textsf{remain directly reusable}} without re-collecting target verification data.

  • Empirical Confirmation at\rule{0pt}{2.52em}\color{#315B75}\textsf{Empirical Confirmation at} B=4B=4 (Table B1):\color{#315B75}\textsf{(Table B1):}
    Even under the simplest shared-stop batch execution rule without a specialized asynchronous scheduler, our re-solved B=4B=4 OGSPO system (a 48-non-root-node nested tree across 9 growth events with a ShareGPT-trained regression-tree controller) improves complete-call throughput on held-out ShareGPT subsets by +46.11% (152.52→222.83 tokens/s152.52 \rightarrow \mathbf{222.83\text{ tokens/s}}, 768-token limit) and +25.52% (103.95→130.48 tokens/s103.95 \rightarrow \mathbf{130.48\text{ tokens/s}}, 1,024-token limit) over training-selected native EAGLE-3 baselines. In our batched verification audit, reused acceptance records incur a mean relative error of only 0.101% (while timing collection and predictor fitting for T^\hat{T} are explicitly charged to preparation in R3, Table S1).
  • \rule{0pt}{2.52em}\color{#315B75}\textsf{How Requests Execute Together \\& Why Both Components Matter:}
    Our framework accommodates shared stopping, grouped independent stopping, or continuous batching once the executor's costs and legal actions enter the optimization. In our measured shared-stop implementation (Table B1), the batch continues drafting or enters verification together at shared decision points (growth events 4, 6, and terminal event 9), while each request independently maintains its own candidate tokens, accepted length, attention mask, KV-cache state, and retained candidate budget (packed or padded for batched verification; completed generations exit at cycle boundaries for newly admitted requests). Under this simple executor, both optimization components remain active: solving under batched costs produces a batch-specific tree, and the trained controller stops at the first decision point in \small\colorbox{#EAF0F7}{74.60\\% of cycles} in the main confirmation run while continuing deeper when warranted.
  • \rule{0pt}{2.52em}\color{#315B75}\textsf{Same-Method Packing \\& Complementary Scheduling Headroom:}
    Applying same-method verification packing to this B=4B=4 system yields an additional +3.40% speedup (232.98→240.90 tokens/s232.98 \rightarrow \mathbf{240.90\text{ tokens/s}} on ShareGPT dev requests, holding decisions and output tokens identical). Designing more adaptive cross-request batching and SLO admission schedulers forms a distinct, complementary system-level research direction—and given that 66.63% of token-acceptance variance occurs across positions within the same request (28.7×28.7\times top vs. bottom quartile step-4-to-9 gain across 1,894 states), coupling OGSPO with heterogeneity-aware schedulers promises substantial further headroom in future serving systems.

Table B1: Batched Complete-Call Throughput on H800 at B=4B=4 (Llama-3.1-8B-Instruct/EAGLE-3, T=1T=1)

\bbox[#E9E5EF]{\small\textbf{Evaluation / EAGLE-3 baseline}}\bbox[#E9E5EF]{\small\textbf{EAGLE-3 → OGSPO (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{Gain}}
ShareGPT, 768-token generation limit; Training-selected depth-3 tree152.52 → 222.83+46.11%
ShareGPT, 1,024-token generation limit; Training-selected depth-8 tree103.95 → 130.48+25.52%

AuthorsOpenReview ↗

GDLD · Response 3

Response 3: Can a Learned Tree–Controller Pair Transfer Without Retuning, and What Costs Repeat Under Shifts? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 3: Can a Learned Tree–Controller Pair Transfer Without Retuning, and What Costs Repeat Under Shifts? (}W2, Q2 — Part 2)\color{#4472C4}\small\textsf{— Part 2)}

Q2 “whether a controller–tree configuration tuned for one setting can transfer to other settings without retuning?”

R3-Key Point: Frozen tree–controller pairs transfer across the evaluated datasets at B=1B=1 and B=4B=4 without per-dataset fitting\small\colorbox{#244F78}{\color{white}\textbf{without per-dataset fitting}} (Table T1). Hardware or batching shifts require timing calibration and tree–policy updates, while existing acceptance records can be reused (Table S1).

Our cross-dataset transfer results and stage-wise cost breakdown follow below:

The answer depends on which execution conditions change: the evaluated workload shifts reuse a frozen structure–policy pair without retraining, whereas hardware or batch-execution shifts require new timing calibration and tree–policy updates (while reusing acceptance records for the same model pair and decoding setting).

$ \rule{0pt}{2.52em}\color{#315B75}\small\textsf{R3-1: Zero-Shot Transfer Across Workloads / Datasets (100\% Frozen Configuration)} $

  • Single-Request Main & Extension Benchmarks (Main Table 1 & App. Table 5):
    Within each model–device–temperature setting, all reported evaluation benchmarks are already strict zero-shot transfers without per-dataset retuning. A single frozen pair—fit solely on 96 ShareGPT and HumanEval dev requests—is deployed unchanged across QA, GSM8K, Alpaca, and MT-Bench (Table 1, +4.8% to +19.3% over EAGLE-3) and held-out summarization extensions (CNN/DailyMail, SUM in App. Table 5: 116.8→125.2 TPS116.8 \rightarrow \mathbf{125.2\text{ TPS}} at T=0T=0; 88.6→103.3 TPS88.6 \rightarrow \mathbf{103.3\text{ TPS}} at T=1T=1 on H800).
  • Batched Cross-Dataset Zero-Shot Transfer (Table T1):
    At B=4B=4 (H800, T=1T=1, 4 requests per dataset and 2 repeats), we deploy our frozen tree and controller trained on ShareGPT directly on other datasets. Table T1 shows two examples against the ShareGPT-selected EAGLE-3 depth-8 baseline; gains depend on target workload and baseline.

Table T1: Two Cross-Dataset Examples with the ShareGPT-Trained Frozen Pair (B=4B=4, H800, T=1T=1)

\bbox[#E9E5EF]{\small\textbf{Target dataset}}\bbox[#E9E5EF]{\small\textbf{EAGLE-3 depth-8 (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{Frozen OGSPO (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{Gain}}
Summarization219.23268.00+22.25%
MBPP258.32283.38+9.70%

R3-2: Preparation vs. Reuse Costs (Table S1)\rule{0pt}{2.52em}\color{#315B75}\small\textsf{R3-2: Preparation vs. Reuse Costs (Table S1)}

Policy fitting is inexpensive once data exist; collecting execution data is the substantial first-time investment. In our B=4B=4 route, initial batched timing collection takes 2.65 h cumulative worker time\small\colorbox{#EAF0F7}{2.65 h cumulative worker time} and shared acceptance collection takes 18.34 min, whereas fitting the controller on existing records takes just 23.53 s (and 0.56–3.42 s on existing B=1B=1 panels). Because initial databases are shared across datasets, adaptation costs depend strictly on which execution conditions change (Table S1).


Table S1: Logged Preparation and Update Costs (B=4B=4 and B=1B=1 Routes, H800 + CPU)

\bbox[#E9E5EF]{\small\textbf{Stage}}\bbox[#E9E5EF]{\small\textbf{Logged Time}}\bbox[#E9E5EF]{\small\textbf{When It Is Needed}}
Initial batched timing-data collection (B=4B=4)2.65 h cumulative worker timeEstablish timing coverage for the batch executor
Shared acceptance/teacher-data collection (B=4B=4)18.34 minEstablish reusable model-pair acceptance records
Latency-model fitting\small\colorbox{#E4F2EF}{\textsf{Latency-model fitting}} (B=4B=4)18.55 sFit predictor to the measured execution costs
Batched tree search (B=4B=4)11.06 minRe-solve structure for changed execution costs or policy use
Decision-position evaluation (B=4B=4)5.38 minAdapt available stopping positions (growth events 4/6/9)
Controller fitting & cross-validation (B=4B=4)23.53 sFit regression-tree policy on existing batch training records
B=1B=1 route: shared init / feedback / policy refit1.90 h / 135.1–262.9 s / 0.56–3.42 sOne-time MLP init / 405-run residual job / CPU panel refit

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

This paper proposes OGSPO, a method that jointly optimizes two components of tree-based speculative decoding (SD): (1) the draft tree structure and (2) a controller that decides when to stop drafting and which candidates to verify. The controller’s decisions depend on the tree, while the tree’s utility depends on how the controller uses it. The paper therefore optimizes both components under a shared throughput-maximization objective. The controller is a small model trained on execution history. At batch size 1, the paper reports an average throughput improvement of 9.2% over EAGLE-3 across four workloads, with a maximum improvement of 19.3%.

Critical strengths

S1. Well-formulated joint optimization of the tree structure and controller. The paper clearly formulates the interdependence between these two components as an optimization problem. It appropriately distinguishes increasing the number of accepted tokens from improving throughput and uses a shared objective that accounts for the controller’s own execution overhead. The experiments motivating this formulation are also well designed.

S2. Systematic formulation of policy learning. Rather than relying solely on feedback from executed actions, the method uses recorded posterior information to evaluate all possible terminal actions and corrects these estimates by executing a subset of the actions.

Critical weaknesses

W1. Limited evaluation configurations [+0.5 if resolved].

The paper demonstrates efficiency gains at batch size 1, but it remains unclear whether these gains persist at larger batch sizes. This is important for assessing the paper’s practical contribution to serving. Changing the batch size can affect GPU utilization, the relative costs of drafting and verification, and packing and synchronization overhead. The paper should therefore evaluate whether the latency model calibrated at batch size 1, along with the selected structure and policy, remains effective at other batch sizes.

Furthermore, even with shared decision points, individual requests may terminate drafting at different depths and select verification subtrees of different sizes. The paper should explain how such requests are batched and how scheduling works when only some requests continue drafting. It should evaluate the benefits of each component and the accuracy of the cost model across multiple batch sizes, and discuss the conditions under which the method remains useful in serving settings with high concurrency or latency SLOs.

W2. Insufficient implementation details.

W2-1. Unclear policy parameterization. To enable reproduction, the paper should specify the policy network architecture, feature encoding, optimizer, and training settings used in the experiments.

W2-2. Unclear construction of the candidate domain. The paper should explain how the initial PP and candidate supertree UU were constructed in the experiments. At a minimum, it should specify the initial depth, width, node budget, and generation rules. It should also report how sensitive the results are to the initial structure or provide sufficiently detailed instructions for exact reproduction.

W3. Unclear data usage and execution configurations in the main evaluation.

The paper should clearly specify the types and amounts of data used at each stage: offline profiling, policy training, structure optimization, configuration selection, and final evaluation. Appendix D provides some information, but a more detailed breakdown is needed.

The main results should also be accompanied by details of the serving framework and implementation, whether CUDA Graphs were enabled, generation lengths and key decoding settings, warm-up procedures, the number of measurement repetitions, and measurement variability. Although some supplementary experiments include these details, the paper should document them consistently across all experiments to support reproduction.

Questions for authors

Q1. The paper presents a multi-round procedure, but the main experiments use only one feedback round. How do throughput, tree structure, and policy change with additional rounds, and why was a single round chosen?

Q2. As the drafting termination depth and verification subtree size vary, how much do latency-model errors affect the ranking of actions?

Q3. With larger batch sizes or continuous batching, how are requests with different drafting termination depths and verification subtree sizes executed, and how much of each component’s benefit is retained?

9 comments
AuthorsOpenReview ↗

zfGm · Response 1

Visual Walkthrough (Click: https://iclr27-paper47457.pages.dev): We recommend visiting for animations explaining the preliminaries and U0–U1–U2 co-evolution; the responses below are self-contained.

We thank Reviewer zfGm for recognizing our joint structure–policy optimization (S1), motivating experiments (S1), and residual-corrected full-action policy learning (S2).

Response 1: Does OGSPO Still Work in Batched Serving, and How Are Divergent Requests Coordinated? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 1: Does OGSPO Still Work in Batched Serving, and How Are Divergent Requests Coordinated? (}W1, Q3)

W1 “whether these gains persist at larger batch sizes … packing and synchronization overhead.” Q3 “how are requests with different drafting termination depths and verification subtree sizes executed … how much of each component’s benefit is retained?”

R1-Key Point: Batching shifts relative execution costs without disrupting our optimization framework—recalibrating costs and re-solving the tree and policy (while directly reusing offline acceptance records) yields up to \small\colorbox{#244F78}{\color{white}\textbf{+46.11\\%}} throughput gains at B=4B=4 even under the simplest shared-stop coordination rule (Table B1).

Detailed analysis and batched evidence follow:

\rule{0pt}{2.52em}\color{#315B75}\textsf{R1-1: Architectural Orthogonality \\& Batched Effectiveness (}W1):
We strongly agree with your practically grounded perspective examining whether OGSPO remains effective beyond single-request (B=1B=1) execution (W1, Q3). Changing batch size alters GPU utilization, packing, and synchronization, shifting draft and verification costs (W1). Crucially, however, this shift is far from disruptive to our framework, tree solver, or policy training—it is nearly orthogonal: because the optimization objective is parameterized by execution costs, adapting to a new batch size only requires recalibrating the latency predictor T^\hat{T}, re-solving the nested tree, and fitting the controller on that tree. Moreover, since token acceptance probabilities depend on the target–draft model pair and temperature rather than batch size, existing acceptance records remain directly reusable\small\colorbox{#E4F2EF}{\textsf{directly reusable}} without re-collecting target verification data (while real timing collection and predictor fitting for T^\hat{T} are accounted for in R3).

Reused acceptance statistics incur a mean relative error of 0.101% in our batched verification audit.


Table B1: Batched Complete-Call Throughput on H800 at B=4B=4 (Llama-3.1-8B-Instruct/EAGLE-3, T=1T=1)

\bbox[#E9E5EF]{\small\textbf{Evaluation / EAGLE-3 baseline}}\bbox[#E9E5EF]{\small\textbf{EAGLE-3 → OGSPO (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{Gain}}
ShareGPT, 768-token generation limit; Training-selected depth-3 tree152.52 → 222.83+46.11%
ShareGPT, 1,024-token generation limit; Training-selected depth-8 tree103.95 → 130.48+25.52%

R1-2: Coordinating Requests with Different Decisions (\rule{0pt}{2.52em}\color{#315B75}\textsf{R1-2: Coordinating Requests with Different Decisions (}W1, Q3):
Our framework accommodates diverse batch execution schemes: the executor determines grouping, costs, and legal actions for tree and policy optimization. Requests can share a cycle-level stopping decision or stop independently and enter a verification queue while continuing requests keep drafting; iteration-level continuous batching admits new requests when full generations finish.

Our B=4B=4 evaluation uses the simplest shared-stop scheme:

  • Shared Cycle Exit with Independent Per-Request State: The batch continues drafting together or proceeds to verification together, while each request independently maintains its own candidates, accepted length, attention mask, KV-cache state, and retained candidate budget (packed or padded for batched verification). A request exits the service batch only after its full generation completes.
  • Both Structure & Policy Remain Active: Solving under batched costs yields a tree tailored to B=4B=4 execution, and training the controller on that tree learns effective early exits—stopping at the first decision point in \small\colorbox{#EAF0F7}{74.60\\% of cycles} in the main confirmation run while allowing the remaining cycles to continue farther.

R1-3: Algorithmic Focus vs. System Scheduling:\rule{0pt}{2.52em}\color{#315B75}\textsf{R1-3: Algorithmic Focus vs. System Scheduling:}
While Table B1 confirms batched effectiveness, designing dynamic cross-request batching and SLO-aware admission schedulers forms a distinct, complementary system-level direction (just as Yggdrasil leaves joint batch scheduling to future work and HeteroSpec positions itself as complementary to existing schedulers). Our paper focuses on a core algorithmic question: given the theoretical ceiling of posterior Oracle trees and an idealized Portfolio, how can joint structure–policy optimization realize that ceiling online?

AuthorsOpenReview ↗

zfGm · Response 2

Response 2: What Are the Exact Policy Parameterization and Construction of Structures\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 2: What Are the Exact Policy Parameterization and Construction of Structures} PP and U\mathcal{U}? (W2-1, W2-2)

W2-1 “policy network architecture, feature encoding, optimizer, and training settings” W2-2 “how the initial (P) and candidate supertree (U) were constructed … how sensitive the results are to the initial structure”

R2-Key Point: We provide complete model, 496-dimensional feature, and structural specifications in Tables D1 & D2, and show that our gains do not rely on a single hand-picked initialization because U2 actively adapts branch allocations\small\colorbox{#244F78}{\color{white}\textbf{actively adapts branch allocations}} across rounds, execution settings, and independently solved topologies (+9.37% in Table D2).

Details and structural sensitivity results follow:

  • Policy Interface Across Routes (\rule{0pt}{2.52em}\color{#315B75}\textsf{Policy Interface Across Routes (}W2-1):
    At each enabled decision point, the controller observes only information already materialized during drafting (confirmed prefix, generated candidates and cumulative draft log-scores, context length, remaining output allowance, and decoding settings, App. B.1) and outputs continuation vs. stopping probabilities along with a verification retention budget (terminal positions force a stop). In our main-paper B=1B=1 route, this is realized by the Structured496 MLP (D4/6/8/10, discrete retention ratios 0.25,0.50,0.75,1.00\\{0.25,0.50,0.75,1.00\\} via hard top-KK pruning). In our B=4B=4 route, a compact regression tree controls stopping and outputs a retention ratio in [0.5,1.0][0.5,1.0].
  • Distinct Roles of\rule{0pt}{2.52em}\color{#315B75}\textsf{Distinct Roles of} PP and U\mathcal{U} (W2-2):
    Source Structure PP is a fixed coverage structure used during offline trace collection to generate full candidate trajectories and record target acceptance probabilities across depths (powering position selection in U0, §4.2). Candidate Supertree U\mathcal{U} is the finite rank-address domain formed by the supported union of sibling-rank paths across reference states, from which U2 (§4.4) solves for a shared nested structure Γ=(U1,…,UJ)⊆U\Gamma=(U_1,\dots,U_J)\subseteq\mathcal{U}.
  • How the Tree Adapts Across Rounds and Settings (\rule{0pt}{2.52em}\color{#315B75}\textsf{How the Tree Adapts Across Rounds and Settings (}W2-2, Q1):
    Because U2 weights candidate branches by the learned policy's reach and stop probabilities (Rj0,qjh0R_j^0, q_{jh}^0), structural updates progressively align\small\colorbox{#E4F2EF}{\textsf{structural updates progressively align}} the tree with actual policy usage. In our multi-round log, successive re-solved 255-node trees replace 14 node addresses and then 3\small\colorbox{#EAF0F7}{14 node addresses and then 3}, while shifting one intermediate decision depth from 10 to 9. Similarly, changing execution costs at B=4B=4 produces a distinct 48-node tree tailored to batched execution, and an independently solved two-exit tree at B=1B=1 outperforms a globally optimized single tree (Table D2).

Table D1: Main-Paper B=1B=1 Controller Architecture & 496-Dim Feature Encoding at Depth dd (W2-1)

\bbox[#E9E5EF]{\small\textbf{Component / Indices}}\bbox[#E9E5EF]{\small\textbf{Specification \\& Normalization Constants (}}Structured496 \bbox[#E9E5EF]{\small\textbf{Checkpoint)}}
MLP ArchitectureOd∈R496O_d\in\mathbb{R}^{496} (fp32) →\rightarrow Linear(496→1024496\rightarrow 1024)+Tanh →\rightarrow Stop/Cont: Linear(1024→21024\rightarrow 2)+Softmax; Ratio: Linear(1024→11024\rightarrow 1)+Sigmoid.
Init & U1 Update512,003 params; warm-started from Structured496 (1,001,4721,001,472 steps, 1.90 h1.90\text{ h}); ratio init 0.50.5. U1: first-order gradient ascent with KL backtracking; 30 steps, η=0.001\eta=0.001, KL δπ=0.01\delta_\pi=0.01.
0–159 (Scores)10×1610\times 16 panel of top-10 parent candidates (by draft score) ×\times up to 16 children; missing filled with −100-100.
160–479 (Masks)Two 10×1610\times 16 binary masks: 160–319 (11 if retained at stage dd, 00 else); 320–479 (11 if expanded, 00 else).
480–485 (Layer)nctx/4096n_{ctx}/4096 (context), d/12d/12 (depth), n/256n/256 (candidates), kstop/256k_{stop}/256 (budget), ∣Kd∣/256\lvert K_d\rvert/256 (retained), ∣Ed∣/128\lvert E_d\rvert/128 (expanded).
486–491 (Next)nparent/128n_{parent}/128, min⁡(nparent,10)/10\min(n_{parent},10)/10, min⁡(nchild,16)/16\min(n_{child},16)/16, ∣Kd+1∣/256,∣Ed+1∣/128\lvert K_{d+1}\rvert/256, \lvert E_{d+1}\rvert/128 (next layer), max⁡(n−kstop,0)/256\max(n-k_{stop},0)/256.
492–495 (State)nsuffix/256n_{suffix}/256 (suffix len), gprev/13g_{prev}/13 (prev. accepted len), 1d∈Ddec\mathbf{1}\\{d\in\mathcal{D}_{dec}\\} (decision mask), (12−d)/12(12-d)/12 (remaining depth).

Table D2 appears at the start of Response 2&3.


AuthorsOpenReview ↗

zfGm · Response 2&3

Response 2:\rule{0pt}{2.52em}\color{#315B75}\textsf{Response 2:}


Table D2: Candidate Domain & Comparison (B=1,T=1B=1, T=1, H800)

\bbox[#E9E5EF]{\small\textbf{Object}}\bbox[#E9E5EF]{\small\textbf{Details}}
Source PP and supertree U\mathcal{U} (chain_manifest.json)255 non-root nodes; Dmax⁡=12D_{\max}=12; ≤10×16\le 10\times16/layer; at d∈4,6,8,10d\in\\{4,6,8,10\\}, retains (134,199,235,255)(134,199,235,255) and expands (51,94,121,136)(51,94,121,136).
Globally optimized single vs. two-exit tree (400 held-out requests, 5 tasks)79.11 → 86.53 TPS (+9.37%); +8.45%, +11.17% in two runs (255 nodes).

Response 3: How Are Datasets Split Across Stages, and How Is End-to-End Runtime Measured? (\rule{0pt}{3.15em}\color{#4472C4}\small\textsf{Response 3: How Are Datasets Split Across Stages, and How Is End-to-End Runtime Measured? (}W3)

W3 “the types and amounts of data used at each stage … whether CUDA Graphs were enabled … the number of measurement repetitions, and measurement variability.”

R3-Key Point: All offline calibration, policy training, and tree solving are strictly isolated within our development pool with zero test-set overlap\small\colorbox{#244F78}{\color{white}\textbf{zero test-set overlap}} (Table D3), while final evaluations measure complete end-to-end call wall-clock time under matched algorithmic parity (with same-method hardware optimizations isolated in Table H1).

The stage-wise data breakdown and runtime measurement protocol follow below:


Table D3: Stage-Wise Data Usage Across Offline Optimization & Final Evaluation (W3)

\bbox[#E9E5EF]{\small\textbf{Pipeline Stage}}\bbox[#E9E5EF]{\small\textbf{Dataset \\& Source}}\bbox[#E9E5EF]{\small\textbf{Request \\& State Volume}}\bbox[#E9E5EF]{\small\textbf{Split Role \\& Strict Isolation Rule}}
1. B=1B=1 Dev PoolShareGPT (60) + HumanEval (60)120 reqs (2,704 states)96 train / 24 internal selection reqs (metadata.json); zero overlap with test sets.
2. B=1B=1 U1 ResidualSampled from 96 Train Reqs405 executions/job (si=0.2s_i=0.2)Same-trace execution of 1 sampled action per selected state (2 clean timing repeats).
3. B=4B=4 AdaptationShareGPT batched pool44 train (88 states) / 8 val (24 states)Reuses shared teacher pool (96 train / 24 val); complexity chosen via request-isolated CV.
4. Final Test EvalQA, GSM8K, Alpaca, MT-Bench80 held-out reqs/task (160 turns MT)Untouched held-out evaluation benchmarks (+CNN/DM & SUM in App. Table 5).

  • \rule{0pt}{2.52em}\color{#315B75}\textsf{Main-Evaluation Protocol \\& Variability (}W3):
    All B=1B=1 main-table evaluations run in our custom staged EAGLE runtime (FP16, max 1,024 new tokens, 3 warmup + 1 formal timed run per task, shared target RNG seeds), with CUDA Graphs disabled\small\colorbox{#E4F2EF}{\textsf{CUDA Graphs disabled}} across all methods in Main Table 1 for algorithmic parity. Complete timing spans H2D, prefill, drafting, controller calls, pruning, verification, KV commit, and final cudaDeviceSynchronize() (excluding tokenization). Across 3 repeated measurements (B∈1,2,4,T∈0,1B\in\\{1,2,4\\}, T\in\\{0,1\\}, repeated measurements), min–max throughput variation stays within ±0.1\pm 0.1\\% to ±2.3\pm 2.3\\%.
  • \rule{0pt}{2.52em}\color{#315B75}\textsf{Same-Method Engineering Gains \\& Batch Recalibration Cost (Table H1,} W3):
    Because OGSPO fixes stage structures offline, its execution layouts support targeted runtime optimizations. Table H1 isolates these same-method engineering gains (holding output tokens and decisions identical before vs. after optimization). For batch recalibration (W3), building the initial shared timing database in our B=4B=4 route takes ~2.65 h of cumulative worker time\small\colorbox{#EAF0F7}{cumulative worker time} and predictor fitting takes 18.55 s; this shared database is then reused across workload evaluations under the same execution layout.

Serving conditions (W1): At high concurrency or under latency SLOs, usefulness depends on whether the progress gained offsets packing, synchronization and waiting costs while meeting latency targets. A separate B=4B=4 audit of the frozen B=1B=1 tree–controller pair observed early exits. Table B1 evaluates the re-solved pair and reports their joint throughput gain.


Table H1: Same-Method Runtime Improvements on H800 (Identical Outputs & Decisions)

\bbox[#E9E5EF]{\small\textbf{Optimization}}\bbox[#E9E5EF]{\small\textbf{Evaluation Scope}}\bbox[#E9E5EF]{\small\textbf{Before (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{After (tokens/s)}}\bbox[#E9E5EF]{\small\textbf{Gain}}
Controller CUDA Graph capture (B=1B=1)Single-request controller (0.430→0.144 ms0.430 \rightarrow 0.144\text{ ms})142.44146.06+2.54%
Combined runtime optimization (B=1B=1)Five held-out tasks (400 requests)100.03109.10+9.07%
Verification packing (B=4B=4)ShareGPT development requests (cap 512)232.98240.90+3.40%

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.