Speculative decoding speeds up LLM serving by drafting tokens that the target model verifies in one pass, and its gain grows with the drafts the target accepts. Structured outputs should be an ideal case, because much of a record follows from relations among its fields: an itinerary's days follow from its cities' stays and flights. Serving engines, however, draft such text by proposing it from the prompt or a learned head, and their grammar masks enforce only syntax, so the model must satisfy the relations, which it violates: on NATURAL PLAN's trip problems, Qwen3-8B writes a valid itinerary for 10%, and retries that name the violated relation raise this to 14%. We present FactorSpec, which serves exact relational constraints as speculative drafts. FactorSpec compiles a JSON Schema and its relations into a factor graph with an exact feasibility check, drafts every token the constraint determines as certain, verifies each request at a width chosen for it, and computes the masks in worker processes outside the scheduler while the GPU runs. In SGLang, its drafts yield up to 10.5 tokens per verify step, up to 1.9x those of the fastest n-gram drafter, and it decodes up to 1.43x faster than speculators tuned per load, at a grammar mask's cost; it also leads in vLLM. Because every record is also valid, it serves up to 13.9x the valid records per GPU-second of syntax-only baselines.
Figures & tables
Figure 1: Decoding the tour of Figure 4 after its first stop, three ways. A grammar mask admits every city, and the model chooses token by token. An n-gram drafter proposes text it has seen, which the target keeps where it agrees. FactorSpec’s relations admit only Oslo on day 3, then Lima on day 6; it drafts the determined tokens, the target accepts them all, and the record completes in two steps.
Workload
Determined
Syntax
Copied
Computed
Ledger
0.768
0.262
0.445
0.061
τ -bench retail
0.858
0.154
0.704
0.000
BFCL multi-turn
0.702
0.294
0.409
0.000
Trip planning
0.9998
0.000
0.000
0.9998
Meeting planning
0.895
0.039
0.063
0.793
Calendar planning
0.961
0.071
0.838
0.053
Table 1: The share of output tokens of 200 gold records per workload that the spec determines, admitting one token given the prefix, by source: syntax the grammar alone fixes; copied text appears in the prompt; computed is the rest, an upper bound, since a run with any computed value counts whole. Trip: seven-city problems.
Figure 2: When the model must satisfy the relations, trip and meeting records violate them, and retries and reasoning repair few. The share of each full set at 64 in flight whose record is valid, Qwen3-8B, 95% Wilson intervals; Trip 10 is all 1,599 trip problems; enum schemas on every workload except the ledger; thinking on 64 problems of each planning workload at 8 in flight, range of three runs.
Figure 3: FactorSpec in a serving engine. 1 The scheduler sends each request’s accepted tokens to its worker. 2 The worker computes the open field’s exact support, walks its token trie, and writes the mask row of every draft node into shared memory. 3 It replies with the tree and its certain nodes cr , which the target accepts with probability one; the engine merges the tree with its drafters and picks each request’s width Wr⋆ . 4 The target verifies under the rows. 5 The accepted tokens start the next step. The worker panel shows an open position of another tour.
Figure 5: One decode step at 64 requests in flight, schematic. On the scheduler thread the GPU waits for the constraint’s work; with the service, workers compute ahead during verify t and build the trees while the scheduler processes the result.
Figure 6
Figure 8: Exactness costs what a grammar mask costs, and every record completes. (b) at 8 in flight, enum schemas on every workload except the ledger; (c) over 200 gold records and records served at 64 in flight; (d) at 64 in flight.
Workload
n-gram
EAGLE-3
FactorSpec
Ledger
5.1 / 4.5
3.6 / 2.7
5.8 / 4.5
τ -bench retail
5.2 / 4.9
2.5 / 2.5
6.4 / 5.1
BFCL multi-turn
4.0 / 3.2
2.8 / 2.4
4.3 / 4.1
Trip planning
5.9 / 5.3
3.9 / 2.6
10.5 / 9.9
Meeting planning
5.7 / 4.7
3.6 / 2.6
8.4 / 7.4
Calendar planning
6.8 / 3.6
4.1 / 3.1
6.9 / 6.5
Table 2: Tokens per verify step per request, the mean acceptance length, at 8 / 64 in flight: each engine speculator at its fastest shape per cell, and our combined drafter. Same runs as Figure 7 .
Figure 9: FactorSpec serves the most valid records per GPU-second (bars, log scale) on every workload; on meeting planning the solver serves more that match gold (marks). At 64 in flight, every invalid record and retry charged; four of the seven syntax-only baselines shown; enum and solver baselines on all workloads but the ledger; 95% intervals over prompts and runs.
Figure 10: The drafters lead or tie on every workload in every setting, and the masks run at 0.95 to 1.19 of XGrammar. At 64 in flight; TP2 is two-GPU tensor parallelism; (f) is Qwen3-8B at temperature one; (g) masks over XGrammar, combined over n-gram; (h) per-request versus fixed width.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
8 in flight
64 in flight
Workload
n-gram
EAGLE-3
n-gram
EAGLE-3
Ledger
16
5×4
8
chain 4
τ -retail
12
chain 4
8
chain 4
BFCL
12
default
4
chain 4
Trip
16
5×4
8
chain 4
Meeting
16
5×4
8
chain 4
Appendix
Table 3: The fastest shape of each speculator per cell, Qwen3-8B on one A6000: the n-gram drafter’s width, and EAGLE-3’s tree as steps by ways or a chain.
Figure 11: Valid records per GPU-second (bars, log scale) and records that also match gold (marks) at 8 in flight, with the baselines of Figure 9 ; 95% intervals over prompts and runs.
Position
Query
Workload
p50
p99
p50
p99
max
Memo
Ledger
4.7
0.79
2.1
0.19
0.53
1.6 ×
τ -retail
4.3
1.95
75.7
0.76
1.07
2.5 ×
BFCL
4.9
2.17
16.1
0.13
0.20
1.5 ×
Trip
4.5
0.48
130.5
0.55
1.03
2.1 ×
Meeting
4.3
10.22
25.0
0.06
3.22
1.1 ×
Appendix
Table 4: The exact check’s cost per position and per query: medians in μ s, 99th percentiles and the slowest query in ms, and how much cheaper the memos make the distinct queries. Below, trip planning over three to ten cities, by city count.
Figure 12: Over every full set FactorSpec matches gold far more often on planning, and as often as the best baseline on tool calls. At 64 in flight, FactorSpec at one width per step; Trip 10 is all 1,599 trip problems; enum schemas on every workload except the ledger; 95% Wilson intervals.
Figure 13: FactorSpec answers every request validly and, past the grammar engine’s capacity, completes the most valid planning records inside the limit at the lowest tail latency. (a, b) Share of requests valid by each time at 64 in flight, retries included. (c–f) Poisson arrivals for two minutes per rate.
Figure 14: (a–c) The share of requests valid by each time at 64 in flight, retries included. (d, e) 99th-percentile latency under Poisson arrivals, two minutes per rate.
Jump-forward
Factor
Workload
In flight
12
32
32
Ledger
8
0.95
0.92
0.89
Ledger
64
0.97
0.96
0.98
Trip
8
1.00
1.19
1.20
Trip
64
1.01
1.03
1.02
Meeting
8
0.94
0.87
1.00
Appendix
Table 5: Throughput over the factor drafter at up to 12 slots, by the verify’s slots; mean of three runs.