AdaSpark: Adaptive DSpark with Online Learning for Tree Verification and N-gram Fill
Organizations: Zeraix
Abstract
Block drafters such as DSpark propose ranked candidates for several positions in one forward pass, and a tree verifier checks them in one pass of the target. The number of rows to verify trades the tokens a wider tree is expected to accept against the time a wider verify takes. Most schedulers that choose this number take the verify time from a table or model measured before serving, corrected online by at most one scale factor, and take acceptance from the drafter's confidence estimates or from a map fitted offline. AdaSpark learns both quantities while it serves, with no profile, calibration or sweep in advance. It learns which verify widths are worth offering and fits each one's verify time as a function of context. It fits each candidate's acceptance probability to the target's verify outcomes, with the drafter's confidence head as one input, and orders and sizes the tree by that fit instead of by the head. The same model prices n-gram continuations of the request's own text, so drafted and text-derived candidates compete for rows in one best-first order. The width is chosen by pricing time at the long-run decode rate. On single- and multi-turn conversations from six public datasets, on three dense targets and one mixture-of-experts target, AdaSpark decodes 1.5-3.1x faster than llama.cpp's DSpark with the same drafters. Our imparo engine with AdaSpark is 1.17-1.52x faster than imparo running with a three-token chain (the default llama.cpp setting); this gain comes from the scheduler alone. Without a width sweep, AdaSpark is never more than 0.3% slower than the best pinned tree width on any dense target or context band. On the mixture-of-experts target it ties the best pinned width, and the other pinned widths from 4 to 16 rows are 5-14% slower.
Figures & tables
| target | rows | (443) | (1,596) | (8,444) | (ms) | (ms per 1k tokens) | max residual |
| LFM2.5-2.6B | 8 | 24.0 | 24.1 | 25.0 | 23.9 | 0.13 | 0.1% |
| LFM2.5-2.6B | 16 | 26.0 | 25.9 | 27.5 | 25.8 | 0.20 | 0.7% |
| LFM2.5-2.6B | 32 | 43.9 | 44.4 | 47.3 | 43.7 | 0.43 | 0.0% |
| LFM2.5-8B-A1B | 8 | 24.2 | 23.0 | 23.7 | 23.6 | 0.01 | 2.7% |
| LFM2.5-8B-A1B | 16 | 32.3 | 30.3 | 32.4 | 31.3 | 0.11 | 3.9% |
| LFM2.5-8B-A1B | 32 | 54.8 | 54.4 | 57.3 | 54.3 | 0.35 | 0.8% |
| target | requests | nodes | head-based | fitted | change | requests won | priced | first request |
| LFM2.5-2.6B | 91 | 580,495 | 0.1410 | 0.1238 | 12.2% | 91/91 | 100% | 157/436 |
| LFM2.5-8B-A1B | 94 | 592,660 | 0.1520 | 0.1360 | 10.5% | 94/94 | 100% | 322/644 |
| Qwen3-4B | 87 | 567,698 | 0.1644 | 0.1400 | 14.8% | 87/87 | 100% | 779/838 |
| Qwen3-8B | 93 | 634,175 | 0.1572 | 0.1336 | 15.0% | 93/93 | 100% | 749/864 |
| target | replies | n | 4 | 5 | 6 | 8 | 12 | 16 | AdaSpark / best | again |
| LFM2.5-2.6B | all replies | 92 | – | – | – | 0.907 | 0.968 | 0.998 | 1.002 [0.996, 1.008] | 0.995 |
| under 2,048 | 75 | – | – | – | 0.909 | 0.970 | 1.000 | 1.000 [0.995, 1.007] | 0.995 | |
| 2,048 and over | 17 | – | – | – | 0.899 | 0.962 | 0.990 | 1.010 [0.991, 1.025] | 0.995 | |
| LFM2.5-8B-A1B | all replies | 91 | 0.857 | 0.920 | 0.953 | 0.997 | 0.926 | 0.900 | 1.003 [0.989, 1.019] | 0.995 |
| under 2,048 | 74 | 0.847 | 0.910 | 0.947 | 0.996 | 0.930 | 0.902 | 1.004 [0.990, 1.020] | 1.002 | |
| 2,048 and over | 17 | 0.899 | 0.969 | 0.980 | 0.998 | 0.911 | 0.891 | 1.002 [0.950, 1.042] | 0.964 |
| evaluation subset: tok/s and ratio | over own AR | ||||||
| target | llama.cpp DSpark | imparo DSpark | AdaSpark | AdaSpark / llama.cpp | looped | llama.cpp DSpark | AdaSpark |
| LFM2.5-2.6B | 66.9 | 83.8 | 126.3 | 1.87 [1.80, 1.95] | 3 | 1.55 | 2.74 |
| LFM2.5-8B-A1B | 79.1 | 105.5 | 122.1 | 1.54 [1.52, 1.57] | 2 | 0.80 | 1.16 |
| Qwen3-4B | 35.7 | 79.1 | 100.4 | 2.83 [2.73, 2.92] | 7 | 0.83 | 2.33 |
| Qwen3-8B | 21.7 | 50.9 | 68.2 | 3.11 [3.05, 3.18] | 1 | 0.85 | 2.64 |
| evaluation subset | held out | whole test set | |||||
| target | ratio | replies | ratio | replies | ratio | replies | looped, held out |
| LFM2.5-2.6B | 1.87 [1.80, 1.95] | 92 | 1.80 [1.73, 1.89] | 64 | 1.84 [1.79, 1.90] | 156 | 3 |
| LFM2.5-8B-A1B | 1.54 [1.52, 1.57] | 93 | 1.50 [1.46, 1.54] | 65 | 1.52 [1.50, 1.55] | 158 | 1 |
| Qwen3-4B | 2.83 [2.73, 2.92] | 88 | 2.88 [2.83, 2.94] | 65 | 2.85 [2.79, 2.91] | 153 | 2 |
| Qwen3-8B | 3.11 [3.05, 3.18] | 94 | 3.07 [3.00, 3.14] | 67 | 3.10 [3.05, 3.14] | 161 | 0 |
| arm | SB | SP | WC | CF | TA | LB | all replies |
| LFM2.5-2.6B | |||||||
| llama.cpp DSpark (tok/s) | 67.2 | 66.6 | 60.5 | 72.9 | 64.9 | 71.8 | 66.9 |
| imparo DSpark (3-token chain) | 1.24 | 1.23 | 1.27 | 1.21 | 1.20 | 1.26 | 1.23 [1.21, 1.25] |
| full-block chain | 1.62 | 1.59 | 1.60 | 1.76 | 1.61 | 1.71 | 1.64 [1.59, 1.68] |
| fixed 16-row tree | 1.85 | 1.78 | 1.79 | 1.91 | 1.78 | 1.91 | 1.82 [1.78, 1.87] |
| cost-model width | 1.83 | 1.77 | 1.79 | 1.91 | 1.72 | 1.92 | 1.81 [1.76, 1.86] |
| LFM2.5-2.6B | LFM2.5-8B-A1B | Qwen3-4B | Qwen3-8B | |
| verified rows held by n-gram-only nodes | 15.2% | 9.4% | 7.2% | 8.1% |
| accepted draft tokens from n-gram-only nodes | 15.8% | 7.8% | 5.1% | 7.8% |
| accepted draft tokens from nodes both sources proposed | 18.1% | 18.5% | 22.1% | 22.4% |
| acceptance rate, drafter-only nodes | 24% | 46% | 33% | 34% |
| acceptance rate, nodes both proposed | 70% | 72% | 64% | 70% |
| acceptance rate, n-gram-only nodes | 30% | 40% | 26% | 37% |
| source | LFM2.5- 2.6B | LFM2.5- 8B-A1B | Qwen3-4B | Qwen3-8B |
| Spec-Bench | 1.51 | 1.14 | 1.28 | 1.33 |
| SPEED-Bench | 1.51 | 1.19 | 1.24 | 1.31 |
| WildChat | 1.43 | 1.12 | 1.24 | 1.32 |
| ConvFinQA | 1.71 | 1.24 | 1.36 | 1.41 |
| ToolACE | 1.41 | 1.19 | 1.23 | 1.24 |
| LongBench | 1.73 | 1.13 | 1.26 | 1.28 |
| target | all replies | under 2,048 | 2,048 and over | learned widths | kernel-class widths |
| LFM2.5-2.6B | 0.997 [0.992, 1.001] | 0.995 [0.990, 1.001] | 1.005 [0.995, 1.012] | 2–4, 6, 8–10, 12–17, 20, 22, 24, 26, 28, 32, 34, 36, 40, 48, 64 | 8, 16, 24, 32, 40, 47, 48, 56, 64 |
| LFM2.5-8B-A1B | 0.996 [0.990, 1.003] | 0.994 [0.987, 1.002] | 1.005 [0.992, 1.019] | 2–17, 20, 24, 28, 32, 64 | 8, 16, 24, 32, 40, 48, 56, 64 |
| Qwen3-4B | 0.998 [0.986, 1.008] | 1.003 [0.997, 1.010] | 0.985 [0.947, 1.012] | 2–18, 20, 24, 28, 30, 32, 44, 57 | 8, 16, 24, 32, 40, 48, 56, 64 |
| Qwen3-8B | 1.002 [0.999, 1.006] | 1.003 [1.001, 1.006] | 0.999 [0.989, 1.010] | 2–17, 20, 22, 24, 26, 28, 30, 32, 57 | 8, 16, 24, 32, 40, 48, 56, 64 |
| target | all replies | first turns |
| LFM2.5-2.6B | 81/95 | 39/42 |
| LFM2.5-8B-A1B | 73/95 | 34/42 |
| Qwen3-4B | 78/95 | 37/42 |
| Qwen3-8B | 85/95 | 38/42 |
| method | size chosen per round | verify cost from | acceptance from |
| AdaSpark | yes: tree width, from widths it learns, 2–64 rows | fitted online from served rounds, per learned width, as a function of context | fitted online per node, with terms for n-gram candidates |
| CAST [ 31 ] | yes: per step, by a cost-benefit test with thresholds set by hand per model | latency table over batch size, context and tokens fed, profiled per device before serving | drafter probabilities |
| EVICT [ 18 ] | yes: tree prefix, 1–32 tokens | table profiled at startup per verify length, no context term | drafter probabilities |
| Bastion [ 20 ] | yes: grows the tree until the estimated speedup falls | roofline model in width and context, calibrated offline, optional online scale factor | drafter probabilities |
| TreeSpark [ 9 ] | yes: stops at a price per verified token | latency ladder measured once per deployment | two-parameter map fitted offline to target outcomes |
| DSpark [ 8 ] , vLLM [ 17 ] , SGLang [ 19 ] | yes: a chain length per request under a batch budget | table profiled at engine start [ 8 ] ; at startup at 8,192 tokens [ 17 ] ; offline, at contexts under about 600 tokens [ 19 ] | confidence head, calibrated offline [ 8 ] |
| vLLM adaptive verification | SGLang DSpark scheduler | AdaSpark | |
| objective | expected tokens / cost | expected tokens steps per second | expected tokens time (Eq. 7) |
| source of cost | profiled at startup | offline profiler, loaded from a file | fitted from served rounds (§ 3.2 ) |
| context | one length, 8,192 tokens by default | 16-token prompts decoded for about 570 steps (contexts up to about 600 tokens) | per-class law in context, refitted while serving |
| where the table is not monotone | running maximum over narrower widths: a cheaper wide width is priced up and never used | lookup at the nearest profiled size below | minimum over wider classes: a cheaper wide class is used for the narrower widths |
| source of acceptance | drafter confidence head | drafter confidence head, optional offline calibration | fitted multinomial (§ 3.3 ) |
| candidate sources per verify | one | one | two, priced separately (§ 3.3 ) |
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| source and content | licence | categories | conv. | turns | subset turns | change to the text |
| Spec-Bench [ 65 ] MT-Bench two-turn items, translation, summarisation, QA, math reasoning, RAG | Apache-2.0 | 13 | 18 | 26 | 21 | none |
| SPEED-Bench [ 66 ] qualitative split | source’s own | 11 | 19 | 23 | 15 | none |
| WildChat [ 67 ] real user conversations; user turns only | ODC-BY | 1 | 8 | 32 | 16 | cut to the first four user turns |
| ConvFinQA [ 68 , 69 ] several questions about one earnings report | not stated | 1 | 8 | 29 | 16 | later turns reduced to their own question |
| ToolACE [ 70 ] tool use with the source’s schemas and recorded tool results | Apache-2.0 | 1 | 8 | 26 | 13 | Python-style parameter types ( dict , float , int ) renamed to the JSON Schema types they name |
| LongBench [ 71 ] long documents with the benchmark’s own task prompt | MIT | 6 | 12 | 12 | 6 | a document over the cap cut from the middle |
| part | constant | value | set by |
| cost model (§ 3.2 ) | quantile level | 0.15 | hand (Proposition 3 ) |
| context basis unit | 8,192 tokens | hand | |
| L1 and L2 weights , (on time normalised by the class’s scale) | 0.002, 0.01 | hand | |
| FTRL rate and stabiliser | 0.05, 1 | hand | |
| squared-gradient cap (rate floor) | 400 | hand | |
| sample bank per context band; samples a refit is judged on | 16 samples; the newest quarter of a band, all of a band with fewer than four | hand |
| alternative | what went wrong | measured |
| Per-round ratio without the fixed cost | narrow rounds looked cheap | +2.2% against a fixed width of 16 (1,596-token context); 0.8% with |
| Argmax of the value with no margin | the choice flipped on noise near the boundary | +1.70% / 0.95% against the best fixed width at two contexts; 0.40% / 0.42% with the margin |
| One acceptance curve per width, learned from rounds at that width | a round at rows says nothing about wider trees, so the learner never left its start | stayed at its initial width in 56 of 56 rounds from 8 rows and 47 of 47 from 16 |
| Drafter candidates priced without the contradicted term | picks next to a strong n-gram proposal were over-priced; the drafter’s gain fell to 0.5 and trees stayed at 8 rows | contradicted picks: 0.598 predicted, 0.539 accepted; their siblings 0.041 and 0.012. With the term, picks contradicted by a copy of tokens: 0.129 predicted, 0.147 accepted |
| Agreed candidates starting from the drafter’s own estimate | agreement was not counted | agreed picks: 0.865 predicted, 0.970 accepted |
| Monotone cost table (running maximum over narrower widths) | a cheaper wide class can never be chosen | by construction; 48 rows are 4% cheaper than 40 (§ 3.2 ) |