PCTree Turns DSpark Chains Into Parent-Conditioned Trees, Adding Up to 29.5% Extra Speedup

From Chains to Trees: Parent-Conditioned Drafting for Semi-Autoregressive Speculative Decoding

Zixian Li, Tong Li, Chi Xie, Xiaohui Song, Haonan Lu

cs.CL

2026-08-03

PCTree turns DSpark's chain into a parent-conditioned tree, no retraining. Extra AR speedup at B=7 is 3.1%-29.5%; Qwen3-4B GSM8K at B=16, acceptance 9.41 to 11.16.

What problem this solves

Speculative decoding only pays off when drafted tokens survive target verification. DSpark is a semi-autoregressive drafter: one parallel backbone forward emits logits for a whole block, then a cheap Markov head adds a previous-token bias so tokens inside the block are not independent.

The original decoder still materializes a single chain. One early mismatch throws away the suffix, and larger blocks make that cascade worse. Tree verification can hedge the same failure, but autoregressive drafters such as EAGLE pay extra draft forwards to grow the tree. DSpark already learned a parent-conditional child distribution. The chain decoder never used that signal to branch.

Method

PCTree is an inference policy. Same checkpoint, same one-pass backbone, same Markov head. The linear draft becomes a budgeted tree.

One backbone forward produces shared logits for B positions.
At depth d, frontier parents are batched through the Markov head, so each concrete parent gets its own child distribution over the shared logits.
Each parent keeps its local top-k children. Nodes are ranked by joint path log-probability. Only the k best nodes of the current layer become the next frontier, which caps width instead of letting it grow as k to the power of depth.
After B stages, the global top-N nodes (including the root) form a prefix-closed tree, packed with an ancestor-only attention mask and verified in one target forward.

The main setting is k=4, N=32. Setting k=1 recovers the greedy DSpark chain.

Broadcasting one depth-wise distribution to every parent is the failure mode to avoid: tokens that look fine in isolation get stitched into a path that is unlikely given the actual parent. The Shared-Markov tree control does exactly that. It walks the greedy DSpark chain first, then reuses each depth's distribution for every sibling.

Results

Targets are Qwen3-4B/8B/14B on nine tasks: GSM8K, MATH-500, AIME25, MBPP, HumanEval, LiveCodeBench, MT-Bench, Alpaca, Arena-Hard. Wall-clock numbers use one NVIDIA H20, bfloat16, SDPA, greedy verification, and DSpark confidence scheduling turned off. B=7 uses official DSpark checkpoints; B=16 drafts are trained with the official recipe. Qwen3-4B at B=16 and GSM8K at B=7 are three-run means. Most other main-table cells are single runs.

Task	B	DSpark τ	PCTree τ	AR speedup
GSM8K	7	6.31	7.24	4.24× → 4.50× (+6.1%)
GSM8K	16	9.41	11.16	6.14× → 6.60× (+7.5%)
HumanEval	7	5.60	6.78	3.74× → 4.27× (+14.3%)
MT-Bench	7	3.82	5.07	2.48× → 3.20× (+29.3%)

At B=7, the extra AR speedup over matched DSpark ranges from 3.1% (Qwen3-4B MATH-500, 4.21× to 4.34×) to 29.5% (Qwen3-14B Alpaca, 2.61× to 3.38×). Acceptance length rises in every model-task pair. Chat tasks reject early more often, so the relative gain is larger there.

On GSM8K at B=16 with the same DSpark weights, the chain scores 9.410, Shared-Markov 10.225, PCTree 11.156. Parent-specific reconditioning adds 9.1% acceptance over branching alone and cuts rounds per sample from 24.718 to 22.632. An external DFlash+DDTree run sits at 7.485, but the draft architecture and checkpoint both change, so that number is context, not a causal contrast.

The extra work is real. At B=7, Markov-plus-tree time per round rises from 0.65ms to 3.52ms while the backbone stays at 3.46ms. Rounds per sample fall from 39.9 to 35.1, which is enough to keep net speedup positive. Most of the gain appears already at k=2 (τ 9.41 to 10.85); k=4 saturates at 11.16 and k=8 does not help. Larger N still lengthens accepted prefixes, but end-to-end speedup peaks at N=32 for B=7 and N=64 for B=16.

Why it matters

For a stack that already ships DSpark, this is a training-free patch. A drafter that splits into a parallel block plus a cheap sequential head can feed tree verification without a new architecture. k=2 is close to saturated, so serving does not need a wide tree.

The improvement is incremental. Tree quality cannot exceed the pretrained Markov head. The speedups are tied to H20, bf16, SDPA, and a fixed N=32. EAGLE-3 and DFlash numbers are reproduced from the DSpark paper, not a same-harness race.

Limitations

The authors list four constraints. A training-free expander cannot repair a weak Markov head. Layer-wise top-k pruning can drop a globally better path. Very large k or N make draft construction and verify attention expensive on small targets or tight memory. Hardware, precision, attention kernels, and the tree budget all move the wall-clock number.

Most main-table cells are single runs, so extra decimal places are not statistical confidence. The three GSM8K repeats give +6.1±0.9% at B=7 and +7.5±1.7% at B=16: the sign is stable, the magnitude is noisy. Confidence scheduling from the original DSpark serving path is off. Only Qwen3 targets appear.

Terms

Speculative decoding: a small model drafts future tokens; the target verifies them in one forward and commits the longest matching prefix.
Markov head: a low-rank bias that depends only on the previous token, restoring intra-block dependence on shared block logits.
Acceptance length τ: tokens committed per verification round, including the target bonus token.
Parent-conditioned branching: each parent at a depth gets its own child distribution rather than sharing one position-wise distribution.
Verification budget N: maximum number of tree nodes, including the root, sent to the target in one round.