Paper deep dive

Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding

Tao Jin, Phuong Minh Nguyen, Naoya Inoue

Year: 2026Venue: arXiv preprintArea: cs.CLType: PreprintEmbeddings: 64

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%

Last extracted: 4/3/2026, 12:17:37 AM

Summary

Goose is a training-free speculative decoding framework that optimizes inference speed by constructing anisotropic speculation trees. It exploits the acceptance rate heterogeneity between context-matched tokens (high acceptance) and statistical transition tokens (low acceptance) by organizing them into a deep spine with wide branches. This structure achieves 1.9-4.3x lossless speedup, outperforming balanced-tree baselines by 12-33%.

Entities (5)

Goose · framework · 100%Speculative Decoding · technique · 100%Prompt Lookup Decoding · technique · 95%Sequoia · technique · 95%Token Recycling · technique · 95%

Relation Signals (3)

Goose → combines → Prompt Lookup Decoding

confidence 95% · Goose... builds an adaptive spine tree—a deep chain of high-acceptance context-matched tokens with wide branches of low-acceptance alternatives

Goose → combines → Token Recycling

confidence 95% · Goose... builds an adaptive spine tree... with wide branches of transition alternatives forking from every spine node.

Goose → improves → Speculative Decoding

confidence 95% · Goose achieves 1.9-4.3x lossless speedup, outperforming balanced-tree baselines

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Speculative decoding accelerates large language model inference by drafting multiple candidate tokens and verifying them in a single forward pass. Candidates are organized as a tree: deeper trees accept more tokens per step, but adding depth requires sacrificing breadth (fallback options) under a fixed verification budget. Existing training-free methods draft from a single token source and shape their trees without distinguishing candidate quality across origins. We observe that two common training-free token sources - n-gram matches copied from the input context, and statistical predictions from prior forward passes - differ dramatically in acceptance rate (~6x median gap, range 2-18x across five models and five benchmarks). We prove that when such a quality gap exists, the optimal tree is anisotropic (asymmetric): reliable tokens should form a deep chain while unreliable tokens spread as wide branches, breaking through the depth limit of balanced trees. We realize this structure in GOOSE, a training-free framework that builds an adaptive spine tree - a deep chain of high-acceptance context-matched tokens with wide branches of low-acceptance alternatives at each node. We prove that the number of tokens accepted per step is at least as large as that of either source used alone. On five LLMs (7B-33B) and five benchmarks, GOOSE achieves 1.9-4.3x lossless speedup, outperforming balanced-tree baselines by 12-33% under the same budget.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

63,513 characters extracted from source content.

Expand or collapse full text

Goose: Anisotropic Speculation Trees for Training-Free Speculative Decoding Tao Jin1 Phuong Minh Nguyen1 Naoya Inoue1 1Japan Advanced Institute of Science and Technology (JAIST) morgan, phuongnm, naoya-i@jaist.ac.jp Corresponding author. Abstract Speculative decoding accelerates large language model inference by drafting multiple candidate tokens and verifying them in a single forward pass. Candidates are organized as a tree: deeper trees accept more tokens per step, but adding depth requires sacrificing breadth (fallback options) under a fixed verification budget. Existing training-free methods draft from a single token source and shape their trees without distinguishing candidate quality across origins. We observe that two common training-free token sources—n-gram matches copied from the input context, and statistical predictions from prior forward passes—differ dramatically in acceptance rate (∼6× 6× median gap, range 22–18×18× across five models and five benchmarks). We prove that when such a quality gap exists, the optimal tree is anisotropic (asymmetric): reliable tokens should form a deep chain while unreliable tokens spread as wide branches, breaking through the depth limit of balanced trees. We realize this structure in Goose, a training-free framework that builds an adaptive spine tree—a deep chain of high-acceptance context-matched tokens with wide branches of low-acceptance alternatives at each node. We prove that the number of tokens accepted per step is at least as large as that of either source used alone. On five LLMs (7B–33B) and five benchmarks, Goose achieves 1.91.9–4.3×4.3× lossless speedup, outperforming balanced-tree baselines by 1212–33%33\% under the same budget. 1 Introduction Speculative decoding (Leviathan et al., 2023; Chen et al., 2023) accelerates autoregressive LLM inference by letting a drafter propose several candidate tokens at once; the target model then verifies all of them in a single forward pass, accepting correct guesses at no extra cost while keeping the output provably identical to standard decoding (lossless; Leviathan et al., 2023). The simplest draft is a single chain: efficient when the drafter is accurate, but a single rejection loses the entire continuation. Tree-structured speculation (Miao et al., 2024; Cai et al., 2024) hedges this risk by proposing multiple candidates organized as a tree; a tree attention mask restricts each candidate’s attention to its ancestors, letting the target model score every root-to-leaf path in one forward pass. We call the resulting structure—candidates plus mask—the draft tree; designing a good one amounts to allocating a fixed node budget B between depth (longer paths) and breadth (more fallback alternatives). Among training-free methods, three representative approaches illustrate the design space—and its limits. Token Recycling (TR; Luo et al., 2025) retrieves statistically likely next tokens from the target model’s own logits, producing breadth-heavy imbalanced trees that hedge broadly at each depth. Prompt Lookup Decoding (PLD; Saxena, 2023) copies n-gram-matched continuations from the input context, producing a deep chain accepted at high rates—but with no fallback when the match breaks or is absent. Sequoia (Chen et al., 2024) optimizes the depth–breadth trade-off via dynamic programming under a source-blind acceptance model that assigns acceptance probabilities by position alone—unable to distinguish high- from low-acceptance sources when both are available. This source-blind assumption forfeits a key structural advantage once both sources coexist. We measure that context-matched (PLD) tokens are accepted 22–18×18× more often than transition (TR) tokens (median ∼6× 6× across five models and five benchmarks; Section˜3). This acceptance heterogeneity suggests placing high-acceptance tokens along a deep spine and attaching low-acceptance tokens as wide branches at every spine node, so the spine pushes depth while branches provide fallback when the spine breaks early. We instantiate this insight in Goose, a training-free framework that builds an adaptive spine tree (Figure˜1): a deep chain of context-matched tokens with wide branches of transition alternatives forking from every spine node. A unified greedy walk verifies the entire tree in one forward pass. We prove that the spine tree’s expected yield—the number of accepted tokens per cycle—is at least as large as that of either source used alone (Proposition˜4), and design runtime adaptations that maintain this property in the boundary cases where one source is absent or dominant (Section˜4.3). Our contributions: 1. We formalize acceptance heterogeneity between two training-free token sources and prove that the optimal tree is anisotropic—allocating depth to reliable tokens and breadth to unreliable ones—breaking through the depth ceiling of single-source trees (Section˜3). 2. We design a confidence-adaptive, training-free tree construction that combines PLD and TR into a single spine tree with a non-degradation guarantee on expected yield (Section˜4). 3. Experiments on five models (7B–33B) across five benchmarks show 1.91.9–4.3×4.3× lossless speedup, outperforming isotropic-tree baselines by 1212–33%33\% under equal node budgets (Table˜2). 2 Related Work Speculative decoding (Leviathan et al., 2023; Chen et al., 2023; Stern et al., 2018) accelerates autoregressive LLM inference by guessing multiple future tokens and verifying them in a single forward pass; Xia et al. (2024) provide a comprehensive survey. A key extension is tree-structured verification (Miao et al., 2024; Cai et al., 2024): candidates are organized into a tree and checked simultaneously, after which the longest accepted path is selected and one bonus token is appended. Draft-model methods. Representative approaches include EAGLE (Li et al., 2024b; a), which trains feature-level draft heads, and Medusa (Cai et al., 2024), which attaches parallel prediction heads; EAGLE-3 (Li et al., 2025) replaces feature prediction with direct token prediction and multi-layer feature fusion, achieving up to ∼6.5× 6.5× speedup. All such methods (Miao et al., 2024; Kim et al., 2023; Zhou et al., 2023, inter alia) require per-model training or auxiliary models, limiting deployment flexibility. Training-free methods. Training-free drafters avoid auxiliary models entirely by mining candidate tokens from data already available at inference time. The simplest strategy copies tokens from the input context (Yang et al., 2023) or from the model’s own prior output via n-gram matching (Saxena, 2023); such copies are cheap but limited to recurring patterns. A broader class retrieves candidates from external datastores—REST (He et al., 2024) uses a suffix array, while Lookahead Decoding (Fu et al., 2024) constructs n-grams on the fly through parallel Jacobi iterations. Other methods refine token selection (Somasundaram et al., 2025; Le et al., 2025) or reuse the model’s own early layers (Zhang et al., 2024; Elhoushi et al., 2024). All the above improve which tokens to draft—better candidates or wider coverage. Goose asks a different question: given candidates from sources with very different acceptance rates, how should the verification tree be shaped? These two directions are orthogonal; better token selection would further widen the acceptance gap that the spine tree exploits. Tree topology optimization. Sequoia (Chen et al., 2024) formalizes the depth–breadth trade-off introduced above. Under Sequoia’s positional acceptance assumption, the probability of accepting a token depends only on its rank among siblings—all sources share a single acceptance vector regardless of origin. When the model is further simplified to a single uniform acceptance rate, the DP reduces to a balanced k-ary tree; we call such uniform-rate trees isotropic and use them as baselines in Section˜5.3. In Section˜3 we extend Sequoia’s framework to two sources with different acceptance rates, yielding a qualitatively different optimal shape. EAGLE-2 (Li et al., 2024a) prunes low-confidence branches via the draft head’s per-token scores, growing deeper along well-predicted paths; this adapts the shape to within-drafter quality variation but requires a trained head and lacks optimality guarantees. TR (Luo et al., 2025) applies a similar principle within its transition lookup table: higher-ranked candidates receive more children than lower-ranked ones, producing non-uniform trees without training. Despite producing non-uniform trees, these methods optimize within a single draft source, so the quality differences they exploit remain within-source. Goose exploits a qualitatively different axis: the cross-source gap between context-matched and transition tokens (22–18×18×; Section˜3). Extending Sequoia’s DP to this heterogeneous setting yields an anisotropic optimum—reliable tokens form a deep chain, unreliable ones spread as wide branches—confirmed by 12–33% gains (Table˜2). 3 Optimal Topology under Heterogeneous Acceptance The optimal tree shape follows directly from the acceptance asymmetry between the two draft sources. We build on Sequoia’s framework (Chen et al., 2024), which models each draft token as independently accepted with a source-independent probability and optimizes the tree via dynamic programming; we extend the model to two sources with different acceptance rates. This section formalizes that asymmetry, derives the expected yield of the spine tree (Proposition˜1), proves that branches should be concentrated near the root (Proposition˜2), and shows that the resulting tree strictly dominates any single-source alternative (Proposition˜3). Heterogeneous acceptance model. Following this model, we associate each draft source with a per-token acceptance probability: psp_s for context-matched (spine) tokens and ptp_t for transition tokens, with ps>ptp_s>p_t. Each spine token is modeled as independently accepted with probability psp_s; consecutive tokens are positively correlated in practice, but this only makes the bound in Equation˜1 tighter (correlation concentrates mismatches at earlier positions). To ground the model, we measure acceptance rates from greedy verification logs across all five models and five benchmarks (Figure˜5). The empirical spine acceptance p^s p_s (fraction of context-matched draft tokens accepted by the target model) ranges from 0.070.07 to 0.600.60 (median 0.210.21), while the empirical transition acceptance p^t p_t lies in 0.03–0.050.03--0.05 (median 0.0330.033), yielding a heterogeneity ratio p^s/p^t p_s/ p_t of 2×2× to 18×18× (median ≈6×≈ 6×); see Figure˜5 for per-benchmark and per-model details. Key quantities. Before stating the main results, we fix notation. The spine consists of m context-matched tokens forming a linear chain; at each spine node i (0≤i≤m−10≤ i≤ m-1), wiw_i transition candidates fork off as branches. The total number of candidates—spine plus all branches—is bounded by the node budget B (i.e., m+∑iwi≤Bm+ _iw_i≤ B). Let τ denote the number of tokens accepted in one verification cycle—the compression ratio in standard terminology (Chen et al., 2024; Leviathan et al., 2023)—so the expected yield is [τ]E[τ]. We also define two recurring terms. Given wiw_i branch candidates at spine node i, each accepted independently with probability ptp_t, the probability that at least one is correct is ϕi= 1−(1−pt)wi _i\;=\;1-(1-p_t)^w_i. Intuitively, ϕi _i grows quickly with wiw_i even when ptp_t is small: a handful of low-quality candidates collectively provide a reasonable chance of continuing the path. Each accepted branch token can itself be extended into a chain of further transition tokens, forming a subtree of maximum depth D (measured from the branching point; D=6D=6 in all experiments). Because every successive token in the subtree is independently accepted with probability ptp_t, the probability that the chain reaches at least depth k is ptkp_t^k. Summing over all possible depths gives the expected extension length: ℓ¯=∑k=1D−1ptk=pt(1−ptD−1)/(1−pt) \;=\; _k=1^D-1p_t^k\;=\;p_t(1-p_t^D-1)/(1-p_t), which ranges from 0 (when pt→0p_t→ 0) to D−1D-1 (when pt→1p_t→ 1). We now bound [τ]E[τ] via the indicator random variable (IRV) decomposition (Leviathan et al., 2023; Chen et al., 2024): the expected accepted token count equals the sum over all tree depths of the probability that the accepted path reaches and accepts that depth. Proposition 1 (Spine Tree Expected Yield). Under the heterogeneous model with spine length m≥1m≥ 1 and branch widths wii=0m−1\w_i\_i=0^m-1 (total budget m+∑iwi≤Bm+ _iw_i≤ B), the expected accepted path length satisfies: [τ]≥∑i=1mpsi⏟spine+∑i=0m−1psi(1−ps)ϕi(1+ℓ¯)⏟continuation synergy+ 1E[τ]\;≥\; _i=1^mp_s^i_ spine\;+\; _i=0^m-1p_s^i(1-p_s)\, _i\,(1+ )_ continuation synergy\;+\;1 (1) with ϕi _i and ℓ¯ as defined above. The bound is tight when the branches are independent chains. Proof sketch. We use the indicator random variable (IRV) technique of Leviathan et al. (2023); Chen et al. (2024): write [τ]E[τ] as a sum over tree depths, each term being the probability that the accepted path reaches and accepts that depth. For each spine depth i∈1,…,mi∈\1,…,m\, define Ii=[all i spine tokens accepted]I_i=1[all $i$ spine tokens accepted]; by independence, [Ii]=psiE[I_i]=p_s^i, yielding the first term—the expected yield of the pure PLD spine (wi=0w_i=0). For the synergy term, each factor has a concrete meaning: psi(1−ps)p_s^i(1-p_s) is the probability the spine breaks exactly at depth i+1i+1 (first i tokens accepted, next rejected); ϕi _i is the probability at least one branch at node i succeeds; and (1+ℓ¯)(1+ ) is the expected token contribution of a successful branch—11 for the branch token itself, and ℓ¯ for the expected subsequent chain extension. Summing over i=0,…,m−1i=0,…,m-1 covers every spine-failure event at which a branch provides a continuation. The final +1+1 is the bonus token: the target model’s greedy output at the last accepted position, guaranteed by the speculative-decoding protocol (Leviathan et al., 2023); deeper sub-branching within branches would only add further contributions, so Eq. 1 is a lower bound. Full derivation in Section˜E.1. □ Since the spine tree includes both the pure PLD chain (m=Bm=B, all wi=0w_i=0) and a near-pure TR tree (m=1m=1) as special cases, its yield never falls below either standalone strategy; ps→1p_s→1 recovers pure spine, ps→ptp_s→p_t recovers isotropic. In practice, the spine ratio adapts via an exponential moving average of the acceptance rate (Section˜4.3). Proposition 2 (Optimal Branch Allocation). The allocation wi∗\w_i^*\ maximizing the synergy term under total branch budget Bt=B−mB_t=B-m satisfies: wi∗=w0∗−|ln⁡ps||ln⁡(1−pt)|⋅iw_i^*\;=\;w_0^*\;-\; | p_s|| (1-p_t)|· i (2) where w0∗w_0^* is set by the budget constraint ∑wi=BtΣ w_i=B_t. The allocation decreases linearly with depth—deeper nodes are reached less often (psip_s^i decays exponentially)—and the slope |ln⁡ps|/|ln⁡(1−pt)|| p_s|/| (1-p_t)| equalizes the marginal value of one extra branch across positions. The proof follows from Lagrange multipliers; see Section˜E.2. In practice, we approximate the linear schedule with a 1/i1/i harmonic rule (Algorithm˜1) that preserves the monotone-decreasing shape without estimating acceptance rates. Empirically, τ is robust to allocation choices (Figure˜4b). Remark (independence approximation). Propositions 1–2 assume independence; positive intra-chain correlation concentrates mismatches earlier, making the allocation conservative—empirical gains in Table˜2 confirm the model captures most available synergy (Section˜D.4). Proposition 3 (Spine Tree Dominance). For acceptance rates ps>pt>0p_s>p_t>0 and any budget B large enough that the spine contains at least two nodes (B≥m+2B≥ m+2, practically B≥10B≥ 10 for ps/pt≥8p_s/p_t≥ 8), the spine tree with optimally allocated branches (Eq. 2) achieves strictly higher expected yield than the best single-source isotropic tree of the same budget: [τspine∗]>[τiso∗]whenever ps>pt.E[ _ spine^*]\;>\;E[ _ iso^*] p_s>p_t. (3) The gap increases monotonically with ps/ptp_s/p_t and vanishes as ps→ptp_s→ p_t. Proof sketch. Start from the optimal single-rate tree of budget B (the best uniform-rate tree under Sequoia’s framework (Chen et al., 2024)), where every token has rate ptp_t. Upgrade one token per depth from ptp_t to ps>ptp_s>p_t, creating a spine. At each modified depth d, the probability of at least one accepted candidate increases by (ps−pt)(1−pt)wd−1>0(p_s-p_t)(1-p_t)^w_d-1>0—a strictly positive improvement propagating through the yield; optimizing allocation (Proposition˜2) adds further gains. When ps→ptp_s→ p_t, the upgrade vanishes, recovering the isotropic baseline. Full proof in Section˜E.3. □ 4 Method: Goose Figure 1: Speculation-tree topologies (B fixed). (a) PLD spine (linear). (b) EAGLE-2 pruned tree. (c) Isotropic (uniform-rate) tree. (d) Goose anisotropic spine tree (spine ratio adapts per cycle; Section˜4.3). Figure 2: Goose pipeline overview. From anchor ., Stage 1 draws from a unified candidate pool: context matching produces the spine (blue), the adjacency table supplies branches (orange). Stage 2 verifies all candidates via one LLM forward pass. Stage 3 selects the longest accepted path via a greedy walk, discovering spine continuation: “2”→\,→\,“)” extends beyond the spine mismatch, yielding 8 tokens per call. Goose follows the standard speculative-decoding loop (Cai et al., 2024)—generate candidates, verify them in one forward pass, accept the longest correct path—but reshapes the candidate tree into a single asymmetric structure that combines two complementary token sources (Figure˜1d). Each decoding cycle begins from an anchor token, the last token accepted in the previous cycle, and proceeds in three stages (Figure˜2). Stage 1—Build spine tree. Goose assembles a candidate pool from two sources. Context matching (PLD) retrieves a continuation from previously generated text, forming a deep chain called the spine; the adjacency table—our bigram extension of TR’s adjacency matrix (Section˜4.1)—supplies statistically likely alternatives that fork from spine nodes as branches. BuildSpineTree allocates the node budget B between spine and branches (Section˜4.1), then packs all candidates into a single sequence with a tree attention mask—a modified causal mask that lets each node attend only to its root-to-node ancestors, so all paths can be verified in one forward pass. Stage 2—Verify and harvest. One LLM forward pass scores every candidate. All logits—including those at rejected branches—are harvested into the adjacency table, and the accepted prefix updates the PLD context index, enriching both sources for future cycles. Stage 3—Select longest correct path. A greedy walk identifies the longest path verified as correct by the target model (Section˜4.2); the last accepted token becomes the anchor of the next cycle. The tree shape is not fixed: when context-match confidence is high, Goose skips tree construction and verifies the PLD chain linearly (bypass mode; Section˜4.3); when no context match exists, the spine vanishes and the full budget forms a TR-only tree. The asymmetric topology enables a unique synergy called spine continuation: when a mismatch occurs on the spine, a branch at that point can extend the accepted path—recovering tokens that neither source alone could have found. To illustrate, consider generating self.calc.eval(data, flag, 2) when earlier output contains ...eval(data, flag, 1) (Figure˜2). Context matching yields a spine eval ( data , flag , 1 ); the model accepts the first six tokens but rejects 1 (correct: 2). A TR branch proposes 2; the greedy walk continues to ), recovering 8 accepted tokens versus 6 from a pure spine. Across benchmarks, spine continuation recovers additional tokens at mismatch points. Two refinements improve candidate quality (ablated in Table˜2): when multiple n-gram lengths return the same first token, Goose treats the prediction as high-confidence and extends the spine aggressively; and the adjacency table is upgraded from unigram to bigram conditioning, sharpening branch predictions. The complete decode loop is in Algorithm˜2 (Appendix). 4.1 Spine Tree Construction Tree construction. Given the anchor token and node budget B, one parameter controls the budget split: the spine ratio r, which sets what fraction of B goes to spine nodes (adapted online; Section˜4.3). Construction proceeds in four steps (Algorithm˜1, Appendix): (1) lay the spine—allocate up to B⋅rB·r nodes as a linear chain of context-matched tokens; (2) add root branches—attach the top adjacency-table alternatives at the root, using a share (1−ρ)(1-ρ) of the remaining budget (spine-branch ratio ρ=0.5ρ=0.5 by default); (3) add spine branches—distribute the remaining share ρ across spine nodes, with wider branches near the root and narrower ones deeper, approximating the optimal allocation derived in Proposition˜2; (4) extend all branches recursively via the adjacency table up to a maximum depth of 6. As introduced above, the adjacency table conditions on the two most recent tokens rather than TR’s original single-token lookup (Luo et al., 2025), improving prediction accuracy. 4.2 Unified Verification and Non-Degradation The spine tree implicitly contains all candidate paths; verification requires only a single greedy walk. Greedy walk with source priority. Starting at the root, the walk advances to a child whose draft token matches the model’s most likely output; when multiple children match, source priority (PLD >> TR) selects the deeper-reaching child. The walk terminates when no child matches, and the accepted path falls into one of three categories: (a) Pure PLD (all spine nodes, equivalent to standalone context-match), (b) Spine continuation (spine followed by a TR branch at the mismatch point—the synergy unique to the spine tree), or (c) Pure TR (root branch only, equivalent to standalone transition). No multi-path bookkeeping is needed; the greedy walk automatically discovers the longest accepted path. At termination, the target model samples one additional bonus token from its distribution at the last accepted position, following the standard speculative-decoding guarantee (Leviathan et al., 2023). Proposition 4 (Non-Degradation Guarantee). For any node budget B, the spine tree’s expected yield—the expected number of tokens accepted per cycle—is at least as large as that of standalone context matching or standalone transition-tree decoding, each given the full budget B. Proof sketch. (i) Context matching is input-determined: standalone PLD with budget B produces a chain of at most |||d| tokens (bounded by the match length, not B), leaving the remaining budget unused. In Goose, these tokens are preserved in full—short matches (||<8|d|<8) fit within ⌊Br⌋ Br even at the minimum spine ratio, while long matches trigger the bypass mode (Section˜4.3). The spine tree fills the unused slots with branches, so its accepted path is at least as long. (i) Compared with a standalone transition tree, the spine replaces some breadth nodes with a depth chain of context-matched tokens. Because context-matched tokens have higher acceptance probability, this swap can only maintain or increase the expected path length; the formal proof is in Proposition˜3. When no context match is available, the spine vanishes and the full budget forms a transition tree, recovering the baseline exactly. □ Remark. The guarantee above holds for expected yield (tokens accepted per verification call), not directly for wall-clock time. Moreover, parts (i) and (i) rely on runtime adaptations—the minimum spine ratio, bypass mode, and graceful fallback described in Section˜4.3—rather than on the tree topology alone. These mechanisms handle the boundary cases (very long matches, absent matches) that a fixed tree shape cannot cover; the ablation in Table˜2 quantifies their individual contributions. The greedy walk is formalized in Algorithm˜3; the full decoding loop, including tree construction and logit harvesting, is in Algorithm˜2 (Appendix). 4.3 Confidence-Adaptive Topology Not every cycle benefits equally from tree construction. Goose uses a continuous PLD confidence signal to modulate tree shape, ranging from a full spine tree down to a simple linear chain. Confidence signal. Goose queries context matching with multiple n-gram lengths 3,4,5\3,4,5\. Confidence is a function of two indicators: (i) consensus—at least two n-gram lengths return continuations that agree on the first token, and (i) chain length—long matches (8 or more tokens) indicate high PLD acceptance. When confidence is high, the tree reduces to a deep linear chain: tree construction is skipped entirely and the spine is verified as a single linear sequence, saving branch-building overhead—we call this the bypass mode. This largely eliminates hard-coded routing heuristics while preserving the expected-yield guarantee of Proposition˜4. Concretely, the spine ratio r is adjusted each cycle based on an exponential moving average (EMA) of the PLD acceptance rate p^s p_s. When the running average is high—indicating that context matches are frequently accepted—r increases toward 0.50, deepening the spine; when the average is low, r decreases toward 0.15, shifting budget to TR branches. This adaptation converges within 3–5 cycles; full details (smoothing coefficient, tier boundaries) are in Section˜C.3. 5 Experiments 5.1 Setup Models, hardware, and datasets. We evaluate five instruction-tuned models spanning 7B–33B parameters: Vicuna-7B/13B/33B (Zheng et al., 2023), Llama-3-8B-Instruct (Meta AI, 2024), and Qwen3-8B (Yang et al., 2025), all in FP16. The 7B–13B models run on a single NVIDIA A40 (48 GB); Vicuna-33B runs on 2×A100-40GB. We evaluate on five benchmarks spanning code, math, and dialogue: HumanEval (Chen et al., 2021), MBPP (Austin et al., 2021), ClassEval (Du et al., 2023), GSM8K (Cobbe et al., 2021), and MT-Bench (Zheng et al., 2023)—ranging from high repetition (code templates) to low repetition (open dialogue). Dataset sizes and generation lengths are listed in Table˜4. Batch size 1; seed 0. Baselines and metrics. AR (standard autoregressive), standalone PLD (Saxena, 2023), standalone TR (Luo et al., 2025) (using its default imbalanced BFS tree with unigram adjacency), Lookahead Decoding (Fu et al., 2024), REST (He et al., 2024), and EAGLE-2 (Li et al., 2024a) (draft-head method; Vicuna-7B, Llama-3-8B, Vicuna-13B using official heads). For the topology comparison (Section˜5.3), we evaluate Isotropic(k): a uniform-rate k-ary tree with k∈3,5k∈\3,5\ and the same node budget, derived from Sequoia’s framework but using Goose’s draft source. All methods use greedy decoding and produce identical output (lossless). We do not compare with EAGLE-3 (Li et al., 2025), whose substantially larger draft model makes iso-budget comparison nontrivial. We report τ (compression ratio: mean tokens accepted per verification call; cf. Section˜3), tok/s (wall-clock throughput), and Speedup (tok/s vs. AR); all hyperparameters are fixed across datasets and models (node budget B=60B=60, max branch depth D=6D=6, top-K=10K=10 adjacency candidates, spine-branch ratio ρ=0.5ρ=0.5; full list in Section˜C.3). During the first few cycles, the adjacency table is empty; Goose gracefully degrades to pure PLD (or AR if no context match exists) and populates the table from the resulting logits. 5.2 Main Results Figure 3: Wall-clock speedup over autoregressive (AR) decoding across five models and five benchmarks. All methods are lossless (greedy decoding, identical output). Speedup values for Goose are annotated above each bar. Full per-benchmark results including compression ratio (τ) are reported in Table˜3. †Vicuna-33B runs on 2×A100-40GB; all others on a single A40. Figure˜3 summarizes the main results. Goose achieves 1.9–4.3× lossless speedup across all five models, consistently outperforming every training-free baseline. Speedup varies predictably with acceptance heterogeneity: ClassEval (repetitive templates) yields up to 4.3×; MT-Bench (open dialogue) still reaches 1.9–2.9×, confirming that TR branches alone contribute meaningful acceleration. One outlier: on Llama-3-8B GSM8K, near-verbatim repetition inflates speedup to 7.5× (τ=9.25τ=9.25); all other 24 settings fall within the 1.9–4.3× speedup range. Among training-free baselines, standalone PLD averages 1.4–2.3× speedup and standalone TR reaches 2.0–2.9×; Goose exceeds both by combining them in a single verification tree. Lookahead Decoding and REST achieve lower τ than Goose due to a narrower candidate pool and suffix-array overhead, respectively. Comparison with EAGLE-2. EAGLE-2’s trained draft head yields higher τ (Table˜3), but its per-step latency offsets the advantage: Goose outperforms EAGLE-2 on Llama-3-8B (4.1× vs. 2.4×), matches on Vicuna-7B (2.9× vs. 2.9×), while EAGLE-2 leads on Vicuna-13B (2.8× vs. 3.3×). As a training-free method, Goose also covers models lacking draft heads (Qwen3-8B, Vicuna-33B). 5.3 Anisotropic vs. Isotropic Topology and Ablation Table 1: Compression ratio τ for spine vs. isotropic trees (budget B=60B=60). Δ3 _3: relative gain over Iso(3). Table 2: Ablation on Qwen3-8B (τ). Each row removes one design choice; Δ¯ : macro-averaged relative change. Model Dataset Spine (Ours) Iso(3) Iso(5) _3 L3-8B ClassEval 4.89 3.67 3.60 +33% HumanEval 4.11 3.32 3.27 +24% MT-Bench 3.50 2.76 2.76 +27% Q3-8B ClassEval 5.19 3.97 3.92 +31% GSM8K 3.87 3.00 3.01 +29% HumanEval 2.78 2.49 2.51 +12% MBPP 3.20 2.73 2.77 +17% MT-Bench 3.51 2.81 2.81 +25% Average 3.88 3.09 3.08 +25.4% Config. HE GS MB CE MT ¯ Goose (Ours) 2.78 3.87 3.20 5.19 3.51 — Idea 1: Anisotropic topology (§4.1) w/o spine branches 2.71 3.70 3.10 5.03 3.46 −-2.9% w/o bigram adjacency 2.69 3.66 3.11 5.01 3.38 −-3.7% Idea 2: Confidence-adaptive budget (§4.3) w/o consensus bypass 2.77 3.83 3.05 4.60 3.22 −-5.1% w/o context-match spine 2.68 3.76 3.11 5.00 3.37 −-3.4% Control w/o PLD tokens (shape kept) 2.77 3.88 3.21 5.19 3.54 ++0.2% Table˜2 confirms the prediction of Section˜3: the spine tree wins all 8 settings by 12–33%, with gains tracking ps/ptp_s/p_t (we report Llama-3-8B and Qwen3-8B as architecturally distinct representatives; Vicuna variants show similar trends). Iso(k=5k=5) performs similarly to Iso(k=3k=3), showing that the isotropic regime itself—not k—is the bottleneck. Ablation analysis. Table˜2 isolates each design idea by removing one component at a time on Qwen3-8B. The Control row replaces all PLD spine tokens with TR-sourced tokens while keeping the anisotropic shape intact; τ changes by only +0.2%+0.2\%, showing that tree shape matters more than token source identity for the topology gains in Table˜2. Idea 1 (Anisotropic topology). Removing spine branches (−2.9%-2.9\%) or bigram adjacency (−3.7%-3.7\%) each degrades τ, confirming that the advantage requires both branch placement and transition quality. Idea 2 (Confidence-adaptive budget). Consensus bypass is the largest contributor (−5.1%-5.1\%, up to −11.4%-11.4\% on ClassEval): when all n-gram lengths agree on a long continuation, Goose extends the spine directly without tree construction. Removing the spine (−3.4%-3.4\%) shows the PLD signal itself is essential; topology and adaptation are complementary. To complement the ablation, we trace the additive path from TR-only isotropic to full Goose on Qwen3-8B (MT-Bench τ): 2.81 → 3.20 (++14%, spine) → 3.37 (++5%, bigram) → 3.51 (++4%, bypass), cumulative ++25%. 5.4 Analysis Figure 4: (a) Goose’s mean τ decomposed into the best standalone baseline max⁡(τPLD,τTR) ( _ PLD, _ TR) (gray) and the synergy gain from the spine-tree topology (green); the gain ranges from +16%+16\% (Vicuna-13B) to +45%+45\% (Llama-3-8B). (b) Hyperparameter sensitivity (Qwen3-8B): each panel sweeps one parameter; τ plateaus at B≥60B≥60 and D≥6D≥6, and varies by fewer than 0.6 τ units across r and ρ. Source decomposition and synergy. Figure˜4a decomposes each model’s mean τ into the best standalone baseline max⁡(τPLD,τTR) ( _ PLD, _ TR) and the synergy gain from the spine-tree topology. The synergy ratio (τGoose/max⁡(τPLD,τTR) _ Goose/ ( _ PLD, _ TR)) exceeds 1.0 on all 25 settings (average 1.24×), with spine continuation contributing 12–44% of accepted tokens on Llama-3-8B. The source split varies by task, consistent with per-task adaptation; even on the weakest datasets, per-model average τ exceeds 2.9×2.9× (Section˜D.3). Tree construction adds negligible CPU overhead (<<1% of wall-clock time) with <<7 MB memory footprint. 6 Discussion and Conclusion We introduced the spine tree, an anisotropic draft-tree topology that exploits acceptance heterogeneity among training-free draft sources. Goose achieves 1.9–4.3× lossless speedup across five models and five benchmarks, outperforming isotropic baselines by 12–33% (Table˜2) and matching or exceeding EAGLE-2 wall-clock speed on two of three models—entirely training-free. The advantage scales with ps/ptp_s/p_t, consistent with Proposition˜3. Limitations. All experiments use batch size 1; in batched settings, amortized verification cost may reduce the relative benefit of tree-based speculation. The adjacency table grows with vocabulary size (<<7 MB in our experiments); for very large vocabularies (>>200K tokens), pruning or hashing may be needed. Our analysis assumes greedy decoding; extending to sampling-based verification (Leviathan et al., 2023) is left for future work. Future directions. The anisotropic framework generalizes to any pair of draft strategies with heterogeneous acceptance rates; substituting a draft head (EAGLE-3 (Li et al., 2025)) for transitions or adding a third source could widen the gap further. Extending the spine tree to batched serving and integrating KV-cache compression are promising next steps. References J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, and C. Sutton (2021) Program synthesis with large language models. arXiv preprint arXiv:2108.07732. Cited by: §5.1. T. Cai, Y. Li, Z. Geng, H. Peng, J. D. Lee, D. Chen, and T. Dao (2024) Medusa: simple LLM inference acceleration framework with multiple decoding heads. In Proceedings of the 41st International Conference on Machine Learning (ICML), Cited by: §1, §2, §2, §4. C. Chen, S. Borgeaud, G. Irving, J. Lespiau, L. Sifre, and J. Jumper (2023) Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318. Cited by: §1, §2. M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. d. O. Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, et al. (2021) Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374. Cited by: §5.1. Z. Chen, A. May, R. Svirschevski, Y. Huang, M. Ryabinin, Z. Jia, and B. Chen (2024) Sequoia: scalable and robust speculative decoding. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §E.3, §1, §2, §3, §3, §3, §3, §3. K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al. (2021) Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: §5.1. X. Du, M. Liu, K. Wang, H. Wang, J. Liu, Y. Chen, J. Feng, C. Sha, X. Peng, and Y. Lou (2023) ClassEval: a manually-crafted benchmark for evaluating LLMs on class-level code generation. arXiv preprint arXiv:2308.01861. Cited by: §5.1. M. Elhoushi, A. Shrivastava, D. Liskovich, B. Hosmer, B. Wasti, L. Lai, A. Mahmoud, B. Acber, S. Agrawal, A. Roman, et al. (2024) LayerSkip: enabling early-exit inference and self-speculative decoding. arXiv preprint arXiv:2404.16710. Cited by: §2. Y. Fu, P. Bailis, I. Stoica, and H. Zhang (2024) Break the sequential dependency of LLM inference using lookahead decoding. arXiv preprint arXiv:2402.02057. Cited by: §2, §5.1. Z. He, Z. Zhong, T. Cai, J. D. Lee, and D. He (2024) REST: retrieval-based speculative decoding. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), Cited by: §2, §5.1. S. Kim, K. Mangalam, S. Moon, J. Malik, M. W. Mahoney, A. Gholami, and K. Keutzer (2023) Speculative decoding with big little decoder. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. N. Le, T. D. Do, and L. Nguyen (2025) SPECTRA: faster large language model inference with optimized internal and external speculation. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 14015–14034. External Links: Link, Document Cited by: §2. Y. Leviathan, M. Kalman, and Y. Matias (2023) Fast inference from transformers via speculative decoding. In Proceedings of the 40th International Conference on Machine Learning (ICML), p. 19274–19286. Cited by: §E.1, §1, §2, §3, §3, §3, §4.2, §6. Y. Li, F. Wei, C. Zhang, and H. Zhang (2024a) EAGLE-2: faster inference of language models with dynamic draft trees. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing (EMNLP), Cited by: §2, §2, §5.1. Y. Li, F. Wei, C. Zhang, and H. Zhang (2024b) EAGLE: speculative sampling requires rethinking feature uncertainty. In Proceedings of the 41st International Conference on Machine Learning (ICML), Cited by: §2. Y. Li, F. Wei, C. Zhang, and H. Zhang (2025) EAGLE-3: scaling up inference acceleration of large language models via training-time test. arXiv preprint arXiv:2503.01840. Cited by: §2, §5.1, §6. X. Luo, Y. Wang, Q. Zhu, Z. Zhang, X. Zhang, Q. Yang, and D. Xu (2025) Turning trash into treasure: accelerating inference of large language models with token recycling. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 6816–6831. Cited by: §1, §2, §4.1, §5.1. Meta AI (2024) The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §5.1. X. Miao, G. Oliaro, Z. Zhang, X. Cheng, Z. Wang, Z. Zhang, R. Y. Y. Wong, A. Zhu, L. Yang, X. Shi, C. Shi, Z. Chen, D. Arfeen, R. Abhyankar, and Z. Jia (2024) SpecInfer: accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Cited by: §1, §2, §2. A. Saxena (2023) Prompt lookup decoding. Note: https://github.com/apoorvumang/prompt-lookup-decoding Cited by: §1, §2, §5.1. S. Somasundaram, A. Phukan, and A. Saxena (2025) PLD+: accelerating LLM inference by leveraging language model artifacts. In Findings of the Association for Computational Linguistics: NAACL 2025, p. 6075–6089. Cited by: §2. M. Stern, N. Shazeer, and J. Uszkoreit (2018) Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems (NeurIPS). Cited by: §2. H. Xia, Z. Yang, Q. Dong, P. Wang, Y. Li, T. Ge, T. Liu, W. Li, and Z. Sui (2024) Unlocking efficiency in large language model inference: a comprehensive survey of speculative decoding. In Findings of ACL, Cited by: §2. A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. (2025) Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §5.1. N. Yang, T. Ge, L. Wang, B. Jiao, D. Jiang, L. Yang, R. Majumder, and F. Wei (2023) Inference with reference: lossless acceleration of large language models. arXiv preprint arXiv:2304.04487. Cited by: §2. J. Zhang, J. Wang, H. Li, L. Shou, K. Chen, G. Chen, and S. Mehrotra (2024) Draft & verify: lossless large language model acceleration via self-speculative decoding. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 11263–11282. Cited by: §2. L. Zheng, W. Chiang, Y. Sheng, S. Zhuang, Z. Wu, Y. Zhuang, Z. Lin, Z. Li, D. Li, E. P. Xing, H. Zhang, J. E. Gonzalez, and I. Stoica (2023) Judging LLM-as-a-judge with MT-Bench and chatbot arena. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 36, p. 46595–46623. Cited by: §5.1. Y. Zhou, K. Lyu, A. S. Rawat, A. K. Menon, A. Rostamizadeh, S. Kumar, J. Kagy, and R. Agarwal (2023) DistillSpec: improving speculative decoding via knowledge distillation. arXiv preprint arXiv:2310.08461. Cited by: §2. Appendix A Full Main Results Table 3: Full main results. Speedup (Spd): wall-clock tok/s ratio vs. AR. τ: compression ratio (tokens per forward call). Bold: best per column. All methods produce identical output (lossless). Shaded rows denote methods requiring per-model training. †Vicuna-33B evaluated on NVIDIA A100 (2×40GB); all other models on A40. ClassEval GSM8K HumanEval MBPP MT-Bench Avg. Model Method Spd τ Spd τ Spd τ Spd τ Spd τ Spd Vicuna-7B AR 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 PLD 2.34 2.50 1.43 1.46 1.74 1.78 1.59 1.62 1.47 1.48 1.71 TR 2.58 3.29 2.46 2.96 2.53 3.06 2.41 2.86 2.19 2.60 2.43 Lookahead 2.27 2.41 1.63 1.67 1.72 1.77 1.75 1.78 1.58 1.60 1.79 REST 1.68 1.73 1.17 1.19 1.16 1.17 1.05 1.05 1.08 1.08 1.23 EAGLE-2 3.14 5.50 2.73 4.51 2.99 5.02 2.92 4.83 2.53 4.21 2.86 Goose (Ours) 3.58 4.64 2.67 3.23 2.97 3.63 2.84 3.40 2.42 2.88 2.90 Llama-3-8B AR 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 PLD 2.30 2.49 4.04 4.18 1.92 2.01 1.67 1.72 1.67 1.72 2.32 TR 2.87 3.64 3.68 4.52 2.79 3.40 2.60 3.11 2.29 2.82 2.85 Lookahead 2.35 2.57 2.59 2.80 1.98 2.08 1.79 1.86 1.73 1.80 2.09 REST 1.33 1.35 1.06 1.07 1.13 1.14 1.01 1.01 1.05 1.05 1.12 EAGLE-2 2.58 5.29 2.75 5.52 2.46 4.95 2.41 4.83 1.92 3.85 2.42 Goose (Ours) 3.82 4.89 7.46 9.25 3.36 4.11 3.00 3.61 2.84 3.50 4.10 Qwen3-8B AR 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 PLD 2.50 2.61 1.65 1.71 1.31 1.36 1.45 1.50 1.67 1.73 1.72 TR 3.77 4.50 2.60 3.03 2.18 2.55 2.43 2.81 2.44 2.86 2.68 Lookahead 2.42 2.42 1.93 1.88 1.52 1.47 1.75 1.68 1.78 1.74 1.88 REST 1.22 1.14 1.21 1.16 1.19 1.12 1.11 1.04 1.11 1.03 1.17 Goose (Ours) 4.28 5.19 3.23 3.87 2.34 2.78 2.70 3.20 2.92 3.51 3.09 Vicuna-13B AR 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 PLD 2.34 2.47 1.33 1.36 1.62 1.66 1.49 1.51 1.35 1.36 1.63 TR 2.71 3.34 2.56 3.02 2.49 2.94 2.40 2.78 2.12 2.46 2.46 Lookahead 2.14 2.26 1.58 1.62 1.73 1.78 1.64 1.67 1.47 1.49 1.71 REST 1.61 1.66 1.18 1.21 1.19 1.20 1.04 1.04 1.11 1.11 1.23 EAGLE-2 3.62 6.03 3.18 4.98 3.34 5.24 3.41 5.30 2.78 4.33 3.27 Goose (Ours) 3.68 4.59 2.66 3.14 2.84 3.37 2.66 3.11 2.30 2.67 2.83 Vicuna-33B† AR 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 PLD 1.85 1.99 1.29 1.33 1.36 1.40 1.27 1.30 1.14 1.15 1.38 TR 1.97 2.62 2.14 2.63 1.97 2.37 1.95 2.29 1.72 2.01 1.95 Lookahead 1.86 2.02 1.49 1.55 1.56 1.56 1.51 1.49 1.26 1.23 1.54 REST 1.48 1.54 1.14 1.18 1.18 1.16 1.08 1.05 1.09 1.05 1.19 Goose (Ours) 2.80 3.69 2.53 3.10 2.37 2.83 2.35 2.74 1.87 2.15 2.38 Table˜3 reports compression ratio (τ) and wall-clock speedup (Spd) for all five models across five benchmarks. Goose achieves the highest average speedup on four of five models; EAGLE-2 leads on Vicuna-13B thanks to its trained draft head but is unavailable for Qwen3-8B and Vicuna-33B. The per-benchmark τ values are the ground truth for the synergy analysis in Section˜D.2. Appendix B Algorithm Details B.1 Spine Tree Construction Algorithm 1 BuildSpineTree 1:Anchor token tat_a; PLD draft chain =(d1,…,dm)d=(d_1,…,d_m) 2:Adjacency table A; node budget B; max depth D 3:Spine ratio r∈(0,1)r∈(0,1); spine-branch ratio ρ∈(0,1)ρ∈(0,1) 4:Spine tree T with ≤B≤ B nodes and tree attention mask 5: 6:bs←min⁡(m,⌊Br⌋)b_s← (m,\, Br ) ⊳ PLD spine node count 7:br←⌊(B−1−bs)(1−ρ)⌋b_r← (B-1-b_s)(1-ρ) ⊳ Root-level branch count 8:bρ←B−1−bs−brb_ρ← B-1-b_s-b_r ⊳ Spine-level branch count 9: 10:d0←tad_0← t_a ⊳ Anchor as spine root 11:for i=1i=1 to bsb_s do ⊳ Step 1: lay PLD spine 12: Add did_i as child of di−1d_i-1 13:end for 14: 15:Attach top-brb_r successors from (ta)A(t_a) to root ⊳ Step 2: root branches 16: 17:for i=1i=1 to bsb_s do ⊳ Step 3: spine branches (harmonic decay) 18: ai←⌊bρ⋅1/i∑j=1bs1/j⌋a_i← b_ρ· 1/i _j=1^b_s1/j ⊳ Allocation for spine node did_i 19: Attach top-aia_i successors from (di)A(d_i) to did_i 20:end for 21: 22:BFS-extend all branch leaves through A up to depth D ⊳ Step 4 23:return T Duplicate entries (e.g., spine continuation di+1d_i+1 already present in (di)A(d_i)) are excluded during attachment to avoid redundant nodes. The BFS extension in Step 4 is a standard breadth-first expansion: starting from each branch leaf, it greedily appends top-scoring successors from A up to depth D within the remaining budget. B.2 Decoding Loop Algorithm 2 Goose Decoding Loop 1:Target model ℳM; prompt x; max tokens N 2:Budget B; spine-branch ratio ρ; max depth D; bypass threshold ℓbyp _byp; adjacency width K 3:Generated tokens y, identical to autoregressive output 4: 5:Build context index from x; init adjacency table A with top-K width 6:ℓ←ℳ() (x); update A with top-K entries per position from ℓ 7:tanc←argmax⁡ℓ[−1]t_anc← *arg\,max [-1]; p^s←0.3 p_s← 0.3 ⊳ Running estimate of spine acceptance psp_s 8:while ||<N|y|<N and not EOS do 9: (,c)←ContextMatch()(d,c)← ContextMatch(y) ⊳ Draft chain d; consensus flag c 10: if ≠∅d≠ and (||≥ℓbyp|d|≥ _byp or c) then 11: (acc,b)←(y_acc,\,b)← linear-verify d with ℳM ⊳ Bypass: high-confidence PLD 12: else if ≠∅d≠ or A has successors for tanct_anc then 13: r←SpineRatioTier(p^s)r← SpineRatioTier( p_s) ⊳ Adaptive spine ratio (Section˜4.3) 14: ←T← BuildSpineTree(tanc,,,r,B,ρ,Dt_anc,d,A,r,B,ρ,D) 15: (acc,b)←(y_acc,\,b)← UnifiedGreedyWalk(ℳ,M,T) 16: else 17: b←argmax⁡ℳ(tanc)b← *arg\,max\,M(t_anc); acc←∅y_acc← ⊳ AR fallback 18: end if 19: Update A from all logits of this cycle ⊳ Including rejected branches 20: Update p^s p_s via EMA; tanc←bt_anc← b; append acc∥by_acc\|b to y 21:end while Goose routes each cycle by source availability and confidence (Section˜4.3): (1) high-confidence or long context match triggers linear bypass; (2) any draft source available triggers the spine tree with unified greedy walk verification; (3) no source available triggers AR fallback. When only transitions (no context match) are available, =∅d= and the tree degenerates to a TR-only tree; when only a context match is available, the tree reduces to a linear chain—both are special cases that preserve the expected-yield guarantee of Proposition˜4. ContextMatch (called at line 5 of Algorithm˜2) is a standard n-gram lookup: given the generated sequence and a set of query lengths 3,4,5\3,4,5\, it finds the longest matching prefix in the context, copies the continuation as the draft chain d, and returns a consensus flag c (true iff ≥2≥ 2 matches agree on the first continuation token). B.3 Unified Greedy Walk Verification Algorithm 3 UnifiedGreedyWalk: Verification with Source Priority 1:Model ℳM; spine tree T (nodes tagged PLD or TR) 2:Accepted token list; bonus token b 3:ℓ←ℳ() (T) with tree attention mask ⊳ Single forward pass 4:x^i←argmax⁡ℓi x_i← *arg\,max _i for each node i ⊳ Greedy prediction per node 5: 6:v←rootv ; accepted ←[]←[] 7:while v has children in T do 8: if ∃ PLD-child v′v of v: [v′]=x^vT[v ]= x_v then ⊳ Priority 1: spine 9: accepted.append(v′v ); v←v′v← v ; continue 10: end if 11: if ∃ TR-child v′v of v: [v′]=x^vT[v ]= x_v then ⊳ Priority 2: branch 12: accepted.append(v′v ); v←v′v← v ; continue 13: end if 14: break ⊳ No child matches 15:end while 16: 17:b←x^vb← x_v ⊳ Bonus token from last accepted position 18:return accepted, b At each tree node, the walk checks PLD (spine) children before TR (branch) children—giving priority to the high-acceptance source. Once the walk transitions from spine to branch, it cannot return, producing the “spine continuation” path described in Section˜4.2. The walk naturally yields the longest accepted path and covers all three outcome categories: pure PLD (spine only), spine continuation (PLD prefix then TR suffix), or pure TR (root branch only). Appendix C Implementation and Setup C.1 Implementation Details This section provides the full engineering details summarized in Section˜4.3. Dense GPU bigram adjacency table. The adjacency table A (Section˜4.1) is implemented as a two-tier GPU-native structure. Tier 1 (Unigram): Two dense tensors of shape |V|×K|V|×K on GPU store, respectively, the token IDs and logit-derived scores of the top-K successors for each vocabulary token; lookup is O(1)O(1) with no CPU transfer. Tier 2 (Bigram): A hash table mapping (ti−1,ti)↦top-K(t_i-1,t_i) -K successors, exploiting the fact that two-token context substantially sharpens predictions (e.g., successors of f after def are much more predictable than f alone). Confidence-aware branch width. Branch width scales with the transition score in A: each successor’s allocated children (from the 1/i1/i harmonic schedule in Step 3 of Algorithm˜1) are further modulated by its score relative to its siblings, and successors whose score falls below 0.01 are pruned entirely. This focuses the node budget on high-confidence successors while keeping the total tree size within B. Aggressive logit harvesting. Every forward pass’s logits—including rejected branches and prefill—are harvested into the adjacency table via a batched topk (<<200,µs overhead), populating A substantially faster than the verified-positions-only strategy used in prior work. C.2 Datasets and Model Details Table 4: Benchmark details. Benchmark Domain Samples Max tokens HumanEval Code 164 512 MBPP Code 500 512 ClassEval Code 100 512 GSM8K Math 1,319 1,024 MT-Bench Dialogue 80 1,024 C.3 Hyperparameters and Experimental Setup Table 5: All hyperparameters (fixed across datasets and models). Parameter Value Context match n-gram lengths 3,4,53,4,5 Max spine continuation 20 Transition top-K 10 Tree node budget B 60 Max tree depth 6 Min score threshold 0.01 Spine-branch ratio ρ 0.5 EMA smoothing coefficient 0.3 Spine ratio tiers (r)(r) p^s<0.2→0.15 p_s<0.2→0.15, <0.4→0.30<0.4→0.30, ≥0.4→0.50≥0.4→0.50 Linear bypass threshold 8 tokens Table 6: Hardware and software configuration. Item Specification GPU (7B–13B) NVIDIA A40 (48 GB GDDR6) GPU (33B) 2×A100-PCIE-40GB (80 GB total) CUDA Toolkit 12.8 PyTorch 2.9.1+cu128 Transformers 4.57 (Hugging Face) Precision FP16 (float16) Appendix D Extended Experimental Analysis D.1 Acceptance Heterogeneity Figure 5: Acceptance heterogeneity across five benchmarks. (a) Mean p^s p_s and p^t p_t per benchmark (averaged over 5 models); the ratio N×N× above each bar pair quantifies the gap. (b) Heterogeneity ratio p^s/p^t p_s/ p_t per model×benchmark (25 settings). D.2 Synergy and Acceptance Rate Analysis The synergy ratio τGoose/max⁡(τPLD,τTR) _ Goose/ ( _ PLD, _ TR) exceeds 1.0 on every model (range 1.16–1.45×, mean 1.24×), confirming that the gain is a consistent structural phenomenon across all 25 settings. GSM8K achieves the highest per-benchmark synergy (2.05) due to repetition-induced τ inflation (see Section˜D.3); excluding this outlier, synergy ranges from 1.16 to 1.34. D.3 Cross-Task Robustness Figure 6: (a) τ across four A40 models and five datasets grouped by Goose’s affinity. CV below each column shows cross-model coefficient of variation. (b) Per-model mean τeq5/τiso _eq5/ _iso across 25 settings; all bars exceed 1.0, confirming spine dominance (Pearson r=0.91r=0.91). Strong-affinity datasets (ClassEval, GSM8K) share repetitive structure—class templates or chain-of-thought boilerplate—yielding high PLD-path acceptance. Weak-affinity datasets (MBPP, MT-Bench) contain shorter, less repetitive outputs that favor the TR-path, yet still achieve τ>2.6×τ>2.6×. The cross-model CV is below 14% for four of five datasets: GSM8K is the exception (CV==58.5%) because Llama-3-8B exhibits degenerate repetition loops on arithmetic tasks, inflating its τ to 9.25—an anomaly that disappears when that single model is excluded (CV drops to 11.7%). Overall, the strong/weak gap is moderate (mean 4.82 vs. 3.24, ratio 1.49×; the strong-affinity mean is lifted by the Llama-3-8B GSM8K outlier noted above), showing that Goose degrades gracefully rather than collapsing on unfavorable inputs. D.4 Prompt-Level Variance Across all 25 model×dataset settings, median τ tracks the mean closely (Pearson r>0.98r>0.98) and the IQR stays within 0.50.5–2.3×2.3× for 23 of 25 cases. The two exceptions—Llama-3-8B/GSM8K and Qwen3-8B/ClassEval—are traced to degenerate repetition loops that inflate τ; excluding the top 5% of prompts reduces their IQR to levels consistent with other settings. Overall, the tight IQR confirms that Goose’s gains are broadly distributed across prompts rather than driven by outliers. Appendix E Theoretical Proofs and Verification E.1 Proof of Proposition 1 (Spine Tree Expected Yield) Proof. We use the indicator random variable (IRV) decomposition introduced for speculative decoding by Leviathan et al. [2023]. For each position in the speculation tree, let I=[the accepted path reaches and accepts this position]I=1[the accepted path reaches and accepts this position]. Since τ=∑positionsIτ= _positionsI (plus the bonus token), linearity of expectation gives [τ]=∑Pr⁡[I=1]+1E[τ]=Σ [I=1]+1. Spine positions (d=1,…,md=1,…,m). Spine position d is reached and accepted iff all d spine tokens along the chain are accepted. Under the i.i.d. acceptance model, Pr⁡[I=1]=psd [I=1]=p_s^d. Summing: [spine]=∑d=1mpsdE[spine]= _d=1^mp_s^d. Branch positions at node i (i=0,…,m−1i=0,…,m-1). A branch subtree at node i is entered iff (a) all i preceding spine tokens are accepted (probability psip_s^i) and (b) the (i+1)(i+1)-th spine token is rejected (probability 1−ps1-p_s). Given entry, the branch token (depth offset j=0j=0) is accepted with probability ϕi=1−(1−pt)wi _i=1-(1-p_t)^w_i. For j=1,…,D−1j=1,…,D-1, each subsequent chain token is accepted independently with probability ptp_t, so depth offset j is reached and accepted with probability ϕi⋅ptj _i· p_t^j. Summing over all offsets within the branch subtree: [branch at node i∣entry]=∑j=0D−1ϕiptj=ϕi(1+∑j=1D−1ptj)=ϕi(1+ℓ¯),E[branch at node i ]= _j=0^D-1 _i\,p_t^j= _i\! (1+ _j=1^D-1p_t^j )= _i(1+ ), where ℓ¯=∑j=1D−1ptj = _j=1^D-1p_t^j as defined in the main text. Here the “11” accounts for the branch token itself, and ℓ¯ for the expected subsequent chain extension. Multiplying by the entry probability and summing over all spine nodes: [synergy]=∑i=0m−1psi(1−ps)ϕi(1+ℓ¯).E[synergy]= _i=0^m-1p_s^i(1-p_s)\, _i\,(1+ ). Combining. Adding the spine contribution, the synergy contribution, and the +1+1 bonus token: [τ]≥∑i=1mpsi+∑i=0m−1psi(1−ps)ϕi(1+ℓ¯)+ 1.E[τ]\;≥\; _i=1^mp_s^i\;+\; _i=0^m-1p_s^i(1-p_s)\, _i\,(1+ )\;+\;1. The inequality holds because branches are modeled as independent linear chains; any deeper sub-branching within a branch—absent in this setup—would only add further contributions, confirming the lower-bound direction. The bound is tight when each branch subtree is an independent linear chain with no further sub-branching. ∎ E.2 Proof of Optimal Branch Allocation Proof. Let Δ=∑i=0m−1psi(1−ps)ϕi(1+ℓ¯) = _i=0^m-1p_s^i(1-p_s)\, _i\,(1+ ) denote the synergy term in Equation˜1, with ϕi=1−(1−pt)wi _i=1-(1-p_t)^w_i. The marginal synergy of adding one branch at position i is: ∂Δ∂wi=psi(1−ps)(1−pt)wiln⁡11−pt(1+ℓ¯). ∂ ∂ w_i=p_s^i(1-p_s)(1-p_t)^w_i\, \! 11-p_t\,(1+ ). At optimality under the constraint ∑wi=BtΣ w_i=B_t, all marginals must be equal: psi(1−pt)wi=μp_s^i(1-p_t)^w_i=μ for a Lagrange constant μ. Taking logarithms: iln⁡ps+wiln⁡(1−pt)=ln⁡μi p_s+w_i (1-p_t)= μ, which gives wi=w0−|ln⁡ps||ln⁡(1−pt)|⋅iw_i=w_0- | p_s|| (1-p_t)|· i, i.e., linearly decreasing with depth. The intercept w0w_0 is set by ∑i=0m−1wi=Bt _i=0^m-1w_i=B_t. ∎ E.3 Proof of Anisotropic Dominance Proof. Let the total node budget be B and define ps>pt>0p_s>p_t>0. Step 1 (Replacement lemma). Consider any tree T of budget B where every candidate token has acceptance probability ptp_t. At depth d, let wdw_d denote the number of candidates; the probability of advancing past depth d is qd=1−(1−pt)wdq_d=1-(1-p_t)^w_d. Replace one of the wdw_d candidates with a spine token of acceptance psp_s: qd′= 1−(1−ps)(1−pt)wd−1=qd+(ps−pt)(1−pt)wd−1.q_d \;=\;1-(1-p_s)(1-p_t)^w_d-1\;=\;q_d\;+\;(p_s-p_t)\,(1-p_t)^w_d-1. Since ps>ptp_s>p_t and (1−pt)wd−1>0(1-p_t)^w_d-1>0, we have qd′>qdq_d >q_d. The expected yield of any tree is Y=∑d=1D∏j=1dqj+1Y= _d=1^D _j=1^dq_j+1, which is strictly increasing in each qjq_j. Hence Y′>Y >Y: replacing one branch token with a spine token at any single depth strictly improves yield. Step 2 (Constructing a dominating spine tree). Start from the optimal isotropic tree iso∗T_iso^* of budget B—the best uniform-rate tree under Sequoia’s framework [Chen et al., 2024]—which maximizes Y over all trees using a single source at rate ptp_t. Let D be its maximum depth. For d=1,…,min⁡(m,D)d=1,…, (m,D), apply Step 1 along a single root-to-leaf path, replacing one ptp_t-token per depth with a psp_s-spine token. The budget is unchanged (B), but each replaced depth has qd′>qdq_d >q_d, so: Yspine>Yiso∗.Y_spine\;>\;Y_iso^*. This spine tree is a feasible (not necessarily optimal) instantiation of Proposition˜1. Step 3 (Optimization improves further). Reallocating branch budget according to Proposition˜2 can only increase the yield: Yspine∗≥Yspine>Yiso∗Y_spine^*≥ Y_spine>Y_iso^*. Step 4 (Gap monotonicity). The per-depth gain (ps−pt)(1−pt)wd−1(p_s-p_t)(1-p_t)^w_d-1 increases linearly in (ps−pt)(p_s-p_t), so Yspine∗−Yiso∗Y_spine^*-Y_iso^* is monotonically increasing in ps/ptp_s/p_t (with ptp_t fixed) and vanishes as ps→ptp_s→ p_t. This is confirmed empirically: the spine advantage in Table˜2 correlates with the per-benchmark ps/ptp_s/p_t ratio. ∎ E.4 Numerical Verification of the Yield Bound We verify the yield lower bound of Proposition˜1 against measured compression ratios across all five target models and five benchmarks (25 settings). For each setting we extract p^s p_s and p^t p_t from the logged spine and branch statistics, estimate the average tree shape (m,B)(m,B) from tree_diag, and compute three quantities: (i) τeq5 _eq5, the lower bound from Eq. 1 with the optimal linear allocation of Proposition˜2; (i) τiso _iso, the yield of an isotropic tree with fan-out 3 and the same budget using only ptp_t; (i) τmeas _meas, the measured average accepted tokens per cycle. The bound is valid (τeq5≤τmeas _eq5≤ _meas) in all 25 model×dataset settings, confirming that Proposition˜1 provides a correct lower bound. The bound is conservative (median τeq5/τmeas≈38% _eq5/ _meas≈ 38\%), which is expected: the theory does not account for the consensus bypass mechanism (Section˜4.3) or multi-cycle warm-start effects, both of which raise the effective acceptance rate in practice. More importantly, τeq5>τiso _eq5> _iso in all 25 settings (median ratio ≈1.52×≈ 1.52×), empirically confirming the dominance result of Proposition˜3. The gain correlates strongly with the heterogeneity ratio p^s/p^t p_s/ p_t (Pearson r=0.91r=0.91), consistent with the monotonicity predicted by Step 4 of the proof (Section˜E.3). Figure˜6 visualizes the per-model dominance ratio.

Instant research discovery