1 Introduction↩︎

Autoregressive language models generate text token by token, requiring a full forward pass at every step. Speculative decoding [1], [2] addresses this bottleneck by pairing a lightweight drafter with the target language model: the drafter proposes candidate tokens, and the target model verifies them in a single parallel forward pass, preserving the output distribution.

Tree-based verification [3] extends this by organizing multiple candidate continuations as a tree: common prefixes are shared and all branches are verified in a single parallel forward pass. Each additional node raises coverage but also increases verification cost.

This tension between coverage and cost is the central optimization problem in draft tree construction: how many nodes should the tree have, and where should they be placed? Existing methods [4]–[7] optimize the draft tree to maximize expected token acceptance. While intuitive, this objective is misaligned with throughput: acceptance length is non-decreasing in budget and provides no principled basis for budget selection. Methods that adapt tree shape per step [6], [8] still fix the total node budget offline, leaving no mechanism to respond to per-round variability in the optimal budget.

We propose throughput as the primary design criterion for draft tree construction. By modeling drafting and verification costs as functions of tree size, we derive a per-round objective that decomposes into a one-dimensional budget search. The central finding is that under a mild convexity condition on the verification cost, the throughput objective is unimodal in tree size. This unimodality yields an efficient greedy algorithm that finds the throughput-optimal tree and adapts the budget per round, without any offline budget search or additional training.

We instantiate the framework on block diffusion drafting [9], [10], which produces per-position marginal distributions in a single forward pass. Experiments on Qwen3-4B and Qwen3-8B across eight benchmarks spanning reasoning, coding, and instruction-following tasks show that CaDDTree matches or surpasses DDTree with oracle budget selection on nearly all tasks. Code is available at https://github.com/ZhangShuai1230/CaDDTree.

2 Related Work↩︎

2.0.0.1 Speculative decoding and drafter design.

Speculative decoding [1], [2] uses a cheap drafter to propose tokens verified in one parallel forward pass by the target model, preserving its distribution. Autoregressive drafters conditioned on target hidden states, most notably the EAGLE family [6], [11], [12], achieve high acceptance rates. Block diffusion models [9] offer a complementary paradigm: a single forward pass predicts an entire token block, enabling longer drafts at near-constant latency. DFlash [10] instantiates this by conditioning the drafter on target-model features, achieving state-of-the-art performance. PARD [13] adapts autoregressive models to mimic block-parallel prediction.

2.0.0.2 Tree-based parallel verification.

SpecInfer [3] introduced tree attention, enabling verification of an entire candidate tree in one forward pass. Medusa [14] exploits this with lightweight prediction heads covering successive future positions. EAGLE-2 [6] constructs draft trees dynamically guided by per-step acceptance-rate estimates; EAGLE-3 [12] further improves draft quality by fusing multi-layer features. DySpec [15], Staged Speculative Decoding [16], and Recursive Speculative Decoding [17] explore further structural extensions. DART [7] builds draft trees from one-pass parallel logits with \(n\)-gram continuity constraints. TALON [8] adapts tree shape per step using token confidence; GOOSE [18] builds anisotropic trees routing reliable tokens into chains and uncertain ones into wide branches. Both fix the total node budget offline.

2.0.0.3 Optimal tree construction.

OPT-Tree [4] first formulated adaptive tree construction for autoregressive drafters, maximizing expected acceptance length under a fixed node budget. DDTree [5] extends this to block diffusion drafters: one pass yields per-position marginals for greedy optimal tree assembly. Zhang et al. [19] optimize throughput directly via reinforcement learning but require training additional draft policies. CaDDTree departs from all of the above: it replaces acceptance-length maximization with direct throughput optimization, adapts the total node budget per round, and provably identifies the optimum via a greedy algorithm with unimodality guarantees, requiring no additional training beyond a one-time cost profiling step.

3 Background↩︎

3.1 Speculative Decoding↩︎

Let \(p(\cdot \mid \mathbf{c})\) denote the target model’s distribution over the next token given context \(\mathbf{c}\), and let \(q(\cdot \mid \mathbf{c})\) denote the drafter’s distribution. Speculative decoding [1], [2] accelerates generation by having the drafter propose a sequence of \(n\) candidate tokens \((x_1, \ldots, x_n)\), then letting the target model verify all of them in a single parallel forward pass. For each position \(i\), the target evaluates \(p(x_i \mid \mathbf{c}, x_{<i})\) and accepts or rejects via rejection sampling [1]: accepted tokens extend the output, while the first rejection triggers a resample from a corrected distribution, preserving the target’s distribution exactly. Under greedy decoding, acceptance is equivalent to requiring \(x_i = \arg\max p(\cdot \mid \mathbf{c}, x_{<i})\).

Each round begins with one committed token \(b\), the bonus token: it comes from the prefill pass in the first round and from the last accepted token in subsequent rounds. Let \(\alpha \ge 0\) denote the number of tokens accepted in a round; the round commits \(1 + \alpha\) tokens in total. Throughput scales with \(\mathbb{E}[\alpha]\), making draft quality the central design objective.

3.2 Block Diffusion Drafting↩︎

Autoregressive drafters require one forward pass per drafted token. Block diffusion models [9] eliminate this cost: a single forward pass given context \(\mathbf{c}\) and bonus token \(b\) produces logits for \(L\) positions simultaneously, yielding a per-position marginal distribution \[q_i(v \mid \mathbf{c}, b) = \operatorname{softmax}(\ell_i)_v, \label{eq:marginals}\tag{1}\] for \(v \in \mathcal{V}\) and \(i = 1, \ldots, L\). Each \(q_i\) is a marginal: it conditions only on \((\mathbf{c}, b)\), not on tokens chosen at earlier positions within the same block, so the drafter’s joint distribution factorizes as \[Q(y_{1:L} \mid \mathbf{c}, b) := \prod_{i=1}^{L} q_i(y_i \mid \mathbf{c}, b). \label{eq:factorized}\tag{2}\] This one-pass, fixed-cost structure makes long draft sequences feasible regardless of depth; the trade-off is that positions are predicted independently, which can accelerate error accumulation. DFlash [10] instantiates block diffusion conditioned on target-model features, achieving state-of-the-art acceptance rates.

3.3 Tree Drafting and Tree Attention↩︎

Rather than proposing a single continuation, the drafter can propose a tree of candidates verified simultaneously in one target-model forward pass via tree attention [3]. Covering multiple branches increases the probability that the target’s preferred continuation appears somewhere in the draft.

Formally, a draft tree \(\mathcal{T}\) is a set of nodes, where each node \(\mathbf{s} = (s_1, \ldots, s_d)\) represents the depth-\(d\) token sequence \((b, s_1, \ldots, s_d)\); \(\mathcal{T}\) is valid if it is prefix-closed: whenever \(\mathbf{s} \in \mathcal{T}\), every prefix of \(\mathbf{s}\) also belongs to \(\mathcal{T}\). In tree attention, each node attends only to the shared context KV cache and to its own ancestors. The target model selects the path with the longest accepted prefix; that prefix is appended to the output, and the first unaccepted token along the chosen path becomes the next bonus token.

3.4 Draft Tree Construction↩︎

Given a draft tree \(\mathcal{T}\), the ideal objective is to maximize the expected acceptance length under the target distribution \(p\): \[\max_{\mathcal{T}} \; \mathbb{E}_p\bigl[\alpha(\mathcal{T}, \mathbf{c})\bigr], \label{eq:true-obj}\tag{3}\] where \(\alpha(\mathcal{T}, \mathbf{c})\) denotes the number of tokens accepted. This is intractable: \(p\) is the expensive target model itself, and evaluating \(\mathbb{E}_p[\alpha]\) requires marginalizing over all paths in \(\mathcal{T}\) under \(p\).

[5] propose to replace \(p\) by the drafter’s factorized distribution \(Q\) from Equation 2 , yielding a tractable surrogate. Under \(Q\), the expected number of accepted tokens decomposes over nodes as \[\Phi(\mathcal{T}) := \sum_{\mathbf{s} \in \mathcal{T}} \pi_{\mathbf{s}}, \label{eq:surrogate}\tag{4}\] where the prefix probability \[\pi_{\mathbf{s}} := \prod_{i=1}^{d} q_i(s_i \mid \mathbf{c}, b) \label{eq:prefix-prob}\tag{5}\] is the probability that a sample from \(Q\) begins with \(\mathbf{s}\). The factorization of \(Q\) is what makes \(\Phi(\mathcal{T})\) computable from a single drafter forward pass.

Optimizing \(\Phi(\mathcal{T})\) under a fixed budget \(n = |\mathcal{T}|\) reduces to selecting the \(n\) nodes with the largest prefix probabilities. Labeling all prefix probabilities in non-increasing order as \(\delta_1 \ge \delta_2 \ge \cdots\), \[\Phi^*(n) := \max_{|\mathcal{T}|=n} \Phi(\mathcal{T}) = \sum_{k=1}^{n} \delta_k, \label{eq:phistar}\tag{6}\] with the optimal tree \(\mathcal{T}^*_n\) consisting of the top-\(n\) nodes by \(\pi_\mathbf{s}\). DDTree constructs \(\mathcal{T}^*_n\) greedily: a max-heap over log-prefix-scores pops nodes in order of decreasing \(\delta_k\), pushing the first child and next sibling at each step, and halts after \(B\) pops. The tree size \(B\) is a hyperparameter with no principled criterion for setting it.

4pt

4 Throughput-Optimal Draft Tree Construction↩︎

4.1 The Fixed-Budget Trap↩︎

The DDTree framework frames tree construction as: given a budget \(B\), build \(\mathcal{T}^*_B\). This leaves the budget as a free hyperparameter, and there is no principled criterion for setting it. Three empirical observations motivate replacing the acceptance-length objective with direct throughput maximization over an adaptive, context-aware budget.

4.1.0.1 Observation 1: per-token time is unimodal, not monotone.

Figure 2 plots acceptance length and per-token generation time as functions of the node budget for Qwen3-4B on MATH-500. Acceptance length increases monotonically: more nodes give the target model a larger set of candidates to accept. Per-token time, however, is unimodal: it decreases initially because larger trees yield more accepted tokens per round, making the fixed drafting cost cheaper per output token, then increases once the marginal verification overhead outweighs the additional acceptance gain. The throughput-optimal budget is strictly smaller than the acceptance-length-maximizing budget: the latter always selects a larger tree than throughput can justify.

4.1.0.2 Observation 2: the optimal budget varies from round to round.

The optimal budget is not a property of the dataset alone; it varies at each decoding round depending on the drafter’s confidence. Figure 1 quantifies this using Qwen3-4B on MATH-500, grouping rounds into ten confidence deciles by their maximum position-1 probability.

The left panel shows acceptance length as a function of budget per decile. High-confidence rounds saturate quickly (further nodes add negligible acceptance gain), while low-confidence rounds continue to benefit from larger trees throughout the budget range. The right panel shows that the budget needed for full acceptance recovery varies substantially with drafter confidence across all three datasets; reasoning tasks saturate earlier and more sharply than MT-Bench. No single fixed budget is efficient across all confidence levels and tasks.

4.1.0.3 Observation 3: verification cost grows with tree size and context.

Figure 3 shows that verification latency increases with node count, and becomes more expensive at longer context lengths. This matters because context length grows throughout generation, so verification cost keeps changing even within a single response.

4.2 Throughput as the Optimization Objective↩︎

The observations above suggest that per-token latency, rather than acceptance length, should be the design criterion.

4.2.0.1 Cost model.

Let \(\ell\) denote the current context length. Define the round cost \(C(\mathcal{T};\,\ell) := C_d + C_v(|\mathcal{T}|;\,\ell)\), where \(C_d > 0\) is the drafting cost and \(C_v(n;\,\ell)\) is the verification cost for a tree with \(n\) nodes at context length \(\ell\). We model \(C_v\) as a function of \(n\) and \(\ell\); Section 5.3 validates the resulting cost estimates.

4.2.0.2 Per-round objective.

Let \(\mathcal{T}_t\) denote the draft tree built at round \(t\) and \(\alpha_t\) the number of tokens accepted. The response throughput over \(R\) rounds is \(\Theta_R = \sum_t (1+\alpha_t) / \sum_t C(\mathcal{T}_t;\,\ell_t)\). Under the surrogate approximation (derivation in Appendix 7.1), maximizing long-run throughput reduces round-by-round to maximizing \[\hat{\theta}(\mathcal{T};\,\ell) := \frac{1 + \Phi(\mathcal{T})}{C_d + C_v(|\mathcal{T}|;\,\ell)}. \label{eq:per-round}\tag{7}\]

4.3 Decomposition into Budget Selection↩︎

The objective \(\hat{\theta}(\mathcal{T};\,\ell)\) ranges over all valid trees. We first reduce this combinatorial problem to a search over a single integer.

Proposition 1 reduces the problem (proof: Appendix 7.2) to the one-dimensional search \(\max_{n \ge 0} \hat{\theta}^*(n;\,\ell)\), evaluated incrementally via the same best-first heap used to build the DDTree, with \(\delta_n = \Phi^*(n) - \Phi^*(n-1)\) being the \(n\)-th largest prefix probability.

4.4 Unimodality of Surrogate Throughput↩︎

All proofs in this section are in Appendix 7. We identify a general condition under which \(\max_n \hat{\theta}^*(n;\,\ell)\) is efficiently solvable. Define the marginal verification cost \(c_n := C_v(n;\,\ell) - C_v(n-1;\,\ell)\) (for fixed \(\ell\)) and the marginal acceptance-cost ratio \[\rho_n := \frac{\delta_n}{c_n}. \label{eq:marginal-ratio}\tag{8}\]

4.5 The CaDDTree Algorithm↩︎

Algorithm 4 implements Corollary 1 for any verification cost \(C_v(\cdot;\,\ell)\) satisfying Assumption 1 at the current context length \(\ell\). It runs a max-heap over log-prefix-probabilities and halts at the first node that fails the stopping condition 10 . The tree size \(n^*\) adapts jointly to the drafter’s confidence distribution and the context-dependent cost, without any hyperparameter.

4.6 Offline Cost Profiling↩︎

4.6.0.1 Profiling procedure.

\(C_v(n;\,\ell)\) is estimated once offline per (model, hardware) pair. We profile at a grid of context lengths \(\mathcal{L} = \{0,\,1\text{k},\,2\text{k},\,\ldots,\,8\text{k}\}\) tokens and node counts \(\mathcal{N} = \{1, 2, \ldots, N\}\) with \(N = 1024\). At each \((\ell, n)\), we run the target model with a dummy tree of \(n\) nodes and record the median verification latency over 20 trials (after 5 warm-up iterations). The drafting cost \(C_d\) is measured as the mean latency of a single drafter forward pass over 500 rounds after 5 warm-up iterations.

4.6.0.2 Convex regression.

For each \(L_j \in \mathcal{L}\), we fit \(\hat{C}_v(\cdot;\,L_j)\) by solving \[\min_{f \;\text{convex, non-decreasing}} \;\sum_{n\in\mathcal{N}} \bigl(y_{j,n} - f(n)\bigr)^2, \label{eq:convex-reg}\tag{11}\] a convex quadratic program with \(O(N)\) variables and \(O(N)\) constraints, solved in under one second per context length via CLARABEL [20]. The result is a piecewise-linear function that is convex and non-decreasing by construction, with breakpoints automatically determined by the data.

4.6.0.3 Context interpolation at inference.

At run time, the current context length \(\ell\) is known exactly. For \(L_j \le \ell < L_{j+1}\), let \(\alpha = (\ell - L_j)/(L_{j+1} - L_j)\); we set \[\begin{align} \hat{C}_v(n;\,\ell) &= (1-\alpha)\,\hat{C}_v(n;\,L_j) \\ &\quad+ \alpha\,\hat{C}_v(n;\,L_{j+1}). \end{align} \label{eq:cv-interp}\tag{12}\] Since linear interpolation of convex functions is convex, \(\hat{C}_v(\cdot;\,\ell)\) inherits convexity and monotonicity in \(n\), so Assumption 1 holds for every \(\ell\).

5 Experiments↩︎

5.1 Experimental Setup↩︎

5.1.0.1 Models.

We evaluate on two target models: Qwen3-4B and Qwen3-8B [21], each paired with its DFlash checkpoint.

5.1.0.2 Benchmarks.

Eight benchmarks spanning reasoning, code, and instruction following: MATH-500 [22], GSM8K [23], AIME 2025, HumanEval [24], MBPP [25], LiveCodeBench [26], MT-Bench [27], and Alpaca [28].

5.1.0.3 Baselines.

• AR: standard greedy/sampling without speculative decoding.

• DFlash [10]: block diffusion speculative decoding with a single sequence draft.

• DDTree-oracle [5]: DDTree with the best budget per (dataset, model, temperature), selected by grid search over \(\{16, 32, 64, 128, 256, 512, 1024\}\).

5.1.0.4 Hardware and hyperparameters.

All experiments run on 8 A800 GPUs with block size \(L = 16\), bfloat16 precision, maximum 2048 new tokens, and temperatures \(\{0.0, 1.0\}\). For CaDDTree, cost parameters are estimated once per (model, hardware) pair via the profiling procedure in Section 4.6. For DDTree and CaDDTree, the target model uses standard PyTorch scaled dot product attention, as the standard FlashAttention-2 [29] kernel does not support the custom tree attention mask; the DFlash drafter uses FlashAttention-2. For the AR and DFlash baselines, we report the faster of the two attention implementations.

5.2 Main Results↩︎

Table 1 reports per-token generation time (ms/tok; lower corresponds to higher throughput) and mean acceptance length \(\tau\) at temperature 0.0. Temperature 1.0 results are in Appendix 9.

CaDDTree matches or surpasses DDTree-oracle on nearly all tasks. For Qwen3-8B, the grid oracle is constrained to \(B{=}128\); CaDDTree selects budgets between grid values and outperforms the oracle on most tasks. For Qwen3-4B, the oracle uses \(B{=}256\); CaDDTree closely matches the oracle across tasks without any grid search. The pattern is consistent at both temperatures (temperature-1.0 results in Appendix 9).

5.3 Cost Model Validation↩︎

Figure 3 shows measured verification latency against node count for nine context lengths (0–8k tokens). The measured latency is consistent with being monotone and convex in node count across all contexts; the convex regression fits closely track the measurements (\(R^2 \geq 0.979\) across all nine context lengths, RMSE \(\leq\) 4.9 ms), supporting Assumption 1. Moreover, both the base verification cost \(C_v(0;\,\ell)\) and the marginal cost per node increase with context length; by design, this causes CaDDTree to select smaller budgets at longer contexts without any manual adjustment. Table 2 compares two cost model variants.

5pt

The constant model sets \(C_v(n;\,\ell) = C_v(0;\,\ell)\) for all \(n\), so the surrogate throughput is strictly increasing and the algorithm always grows the tree to the maximum budget (capped at 1024 nodes), yielding a clear per-token latency increase and confirming that per-node verification overhead is non-negligible.

5.4 Adaptive Budget Analysis↩︎

The throughput-optimal \(n^*\) varies substantially across rounds, even within the same dataset. Figure 5 makes this concrete: on MATH-500, budgets spread widely, with a substantial fraction of rounds selecting fewer nodes than the grid oracle and a larger fraction selecting more. No single fixed budget serves both regimes well. On Alpaca, the distribution is tightly concentrated and the mean falls between grid points, at a value no fixed grid budget matches exactly. CaDDTree finds the per-round optimum automatically in both cases.

Figure 6 reveals why the optimal budget differs: the drafter’s per-token uncertainty varies across steps. When the drafter is confident, every accepted token sits at rank 1 with no competing siblings; a narrow chain suffices, saving most of the oracle budget at no loss in accepted tokens. When the drafter is uncertain, accepted tokens span multiple ranks and large rejected subtrees appear at every step; the tree must fan out widely to find the accepted path. Together, the two panels confirm that per-round budget adaptation captures both regimes, and that no single fixed budget can eliminate this variation.

5.5 Ablation: Sensitivity to Cost Parameters↩︎

5pt

Table 3 shows that all four perturbations produce \(|\Delta| \leq 0.07\) ms/tok, suggesting that approximate cost estimates suffice and highly precise offline calibration is not strictly necessary.

6 Conclusion↩︎

We introduced CaDDTree, a cost-aware diffusion draft tree method that optimizes per-token latency directly rather than acceptance length under a fixed budget. By explicitly modeling both drafting and verification latencies, we showed that the throughput objective decomposes into a one-dimensional budget search that is efficiently solvable via a greedy stopping rule with provable unimodality guarantees under convex verification cost. CaDDTree eliminates offline budget selection and adapts the tree size per decoding round, consistently matching or exceeding DDTree with oracle budget selection across diverse benchmarks and target models.

Appendix↩︎

7 Proofs↩︎

7.1 Derivation of Per-Round Objective↩︎

Over \(R\) rounds, the response throughput is \(\Theta_R = \sum_{t=1}^R (1+\alpha_t) / \sum_{t=1}^R C(\mathcal{T}_t;\,\ell_t)\). At each round, \(\mathcal{T}_t\) is a deterministic function of the drafter’s marginals \(\{q_i^{(t)}\}\), while acceptance \(\alpha_t\) is random under the target \(p\). By the law of large numbers, as \(R \to \infty\): \[\begin{align} \Theta_R \to \Theta = \frac{\mathbb{E}_t[\mathbb{E}_p[1+\alpha_t \mid \mathcal{T}_t]]}{\mathbb{E}_t[C(\mathcal{T}_t;\,\ell_t)]} \approx \frac{\mathbb{E}_t[1 + \Phi(\mathcal{T}_t)]}{\mathbb{E}_t[C(\mathcal{T}_t;\,\ell_t)]}, \end{align}\] where the inner expectation over target acceptance is replaced by the surrogate \(\Phi\). We therefore maximize \(\hat{\theta}(\mathcal{T}_t;\,\ell_t)\) at each round as a tractable per-round surrogate for the long-run ratio \(\Theta\). \(\square\)

7.2 Proof of Proposition 1↩︎

Fixed-budget optimality. For any node \(\mathbf{s} = (s_1, \ldots, s_d)\), its parent satisfies \(\pi_{\mathbf{s}_{-}} = \pi_{\mathbf{s}} / q_d(s_d) \ge \pi_{\mathbf{s}}\), so every ancestor has weakly higher prefix probability. Hence if \(\mathbf{s}\) is among the top-\(n\) nodes by \(\pi\), every ancestor is too: \(\mathcal{T}^*_n\) is prefix-closed and forms a valid tree. Since \(\Phi(\mathcal{T}) = \sum_{\mathbf{s}\in\mathcal{T}}\pi_{\mathbf{s}}\) and \(\mathcal{T}^*_n\) selects the \(n\) nodes with the largest \(\pi_{\mathbf{s}}\), no valid \(n\)-node tree achieves a higher \(\Phi\).

Budget selection. For fixed \(n\), the denominator \(C_d + C_v(n;\,\ell)\) is constant, so maximizing \(\hat{\theta}(\mathcal{T};\,\ell)\) over valid \(n\)-node trees reduces to maximizing \(\Phi(\mathcal{T})\), achieved by \(\mathcal{T}^*_n\). Taking the maximum over \(n \ge 0\) yields ?? . \(\square\)

7.3 Proof of Lemma 1↩︎

We verify the weighted average representation by direct expansion. Let \(c_{n+1} = C_v(n+1;\,\ell) - C_v(n;\,\ell) > 0\) and \(w_n = (C_d + C_v(n;\,\ell)) / (C_d + C_v(n+1;\,\ell))\), so \(1 - w_n = c_{n+1} / (C_d + C_v(n+1;\,\ell))\). Then: \[\begin{align} &w_n \hat{\theta}^*(n) + (1-w_n)\,\rho_{n+1} \nonumber\\ &= \frac{1 + \Phi^*(n)}{C_d + C_v(n+1;\,\ell)} + \frac{c_{n+1}}{C_d + C_v(n+1;\,\ell)} \cdot \frac{\delta_{n+1}}{c_{n+1}} \nonumber\\ &= \frac{1 + \Phi^*(n) + \delta_{n+1}}{C_d + C_v(n+1;\,\ell)} = \hat{\theta}^*(n+1). \nonumber \end{align}\]

The equivalence \(\hat{\theta}^*(n+1) > \hat{\theta}^*(n)\) iff \(\rho_{n+1} > \hat{\theta}^*(n)\) follows immediately: \(\hat{\theta}^*(n+1)\) is a strict convex combination of \(\hat{\theta}^*(n)\) and \(\rho_{n+1}\), so it lies between them, and exceeds \(\hat{\theta}^*(n)\) iff \(\rho_{n+1} > \hat{\theta}^*(n)\). \(\square\)

7.4 Proof of Theorem 2 (Unimodality)↩︎

By Assumption 1, \(\{\rho_n\}\) is non-increasing. If \(\hat{\theta}^*\) is non-decreasing for all \(n\), the conclusion holds trivially. Otherwise, let \(n_0 \ge 0\) be the smallest index with \(\hat{\theta}^*(n_0+1) \le \hat{\theta}^*(n_0)\), equivalently \(\rho_{n_0+1} \le \hat{\theta}^*(n_0)\). From the weighted average representation: \[\begin{align} \hat{\theta}^*(n_0+1) &= w_{n_0}\hat{\theta}^*(n_0) + (1-w_{n_0})\rho_{n_0+1} \nonumber\\ &\ge \rho_{n_0+1}. \label{eq:lb-app} \end{align}\tag{13}\]

Inductive step. Assume \(\rho_{n+1} \le \hat{\theta}^*(n)\) for some \(n \ge n_0\), so \(\hat{\theta}^*(n+1) \le \hat{\theta}^*(n)\) and the bound above gives \(\hat{\theta}^*(n+1) \ge \rho_{n+1}\). Since \(\{\rho_n\}\) is non-increasing: \[\rho_{n+2} \le \rho_{n+1} \le \hat{\theta}^*(n+1),\] so \(\hat{\theta}^*(n+2) \le \hat{\theta}^*(n+1)\) by Eq. 10 . The induction is complete: \(\hat{\theta}^*\) is non-increasing for all \(n \ge n_0\). \(\square\)

7.5 Proof of Corollary 1 (Greedy Optimality)↩︎

Algorithm 4 terminates at the first \(n\) for which \(\hat{\theta}^*(n+1) \le \hat{\theta}^*(n)\). By Theorem 2, this is the global maximizer \(n^*\). At termination, the heap has popped exactly the top-\(n^*\) prefixes by probability (by Proposition 1), and Proposition 1 guarantees that \(\mathcal{T}^*_{n^*}\) is the throughput-optimal tree. \(\square\)

7.6 Proof of Corollary 2 (Convex Cost)↩︎

\(\{\delta_n\}\) is non-increasing by construction; \(\{c_n\}\) non-decreasing by the convexity hypothesis; hence \(\rho_n = \delta_n / c_n\) is non-increasing. \(\square\)

8 Benchmark Details↩︎

All runs use block size 16, bfloat16 precision, and a maximum of 2048 new tokens. Each dataset uses 128 evaluated examples, except AIME 2025 (30), HumanEval (164), and MT-Bench (160). The evaluation set is sharded across 8 A800 GPUs. Before timing, one warmup prompt is run through each method (autoregressive, DFlash, DDTree, CaDDTree) to exclude one-time setup costs.

9 Temperature 1.0 Results↩︎

4pt

References↩︎