WorksComputer Science
FactorSpec: Serving Exact Relational Constraints as Speculative Drafts
Abstract
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.
Introduction
Speculative decoding ([18, 7]) speeds up LLM serving by drafting tokens that the target verifies in one forward pass, and its gain grows with the drafts the target accepts. Structured outputs, such as tool calls and plans, should be an ideal case, because much of a record follows from relations among its fields: a refund’s item must belong to its order, and an itinerary’s days follow from its cities’ stays and the direct flights between them. Serving engines such as SGLang ([48]) and vLLM ([17]), however, check only syntax, and the model violates the relations: on 999 trip problems of three to seven cities from NATURAL PLAN ([47]), Qwen3-8B writes a valid itinerary for 10%, and retries that name the violated relation reach 14% (§ 2.4).
Existing approaches each cover part of this. Grammar engines ([11, 42]) answer in microseconds but enforce syntax, and an enum schema closes the gap where a record copies values from its prompt. Semantic constrained decoders ([37, 33, 26]) check relations locally, which on joint relations leads a decoder to infeasible prefixes: served in an engine, arc consistency leaves 12 to 64%
of planning records incomplete. Solver pipelines ([22, 30]) compute a valid answer outside the model, which then still decodes it token by token. The engines’ drafters ((Li et al., 2025b)) propose likely or repeated text, and jump-forward decoding ([48]) skips the tokens a grammar determines; the text the relations compute, such as the day a stay must end, lies outside all of them.
Drafting from the relations themselves would serve both speed and validity, but it poses two systems problems. The first is speed at serving load: a drafter’s gain shrinks as the batch grows ([23]), as one width per step spends slots on guesses. The second is cost: an exact check over joint relations, such as an all-different over cities or arithmetic over days, is far heavier than a grammar mask, and on the scheduler thread it would delay every request of the step.
Our insight is that an exact constraint is itself a drafter (Figure 1). It knows which positions it determines, so it can propose those tokens, and it knows for each request how many of its drafts the target will accept. It also knows its next state before the target samples a determined token, so it can compute ahead while the device runs. The constraint thus turns its cost into a source of speed.

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 then agrees with. 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.
FactorSpec builds this insight into speculative decoding for structured outputs. A client declares a record as a JSON Schema and a list of relations, which compile to a factor graph with an exact feasibility check and a token-level structure engine that admits a token only if it extends to a valid record. Against the speed problem, speculative drafters propose the constraint’s determined runs as certain drafts, alone or grafted with the engine’s n-gram corpus or EAGLE-3 head, and verify each request at a width chosen for it. Against the cost problem, a constraint service of worker processes holds each request’s session outside the scheduler process and writes mask rows into shared memory while the forward pass runs.
We evaluate FactorSpec in SGLang and vLLM on six tool-calling and planning workloads and find that exactness is both fast and cheap. On Qwen3-8B, each verify step accepts up to 10.5 tokens, up to 1.9 those of the fastest n-gram shape, because a determined run is accepted whole. That acceptance length lets the combined drafter match or outrun the engine’s speculator tuned per load at 8, 64 and 128 requests in flight (Figure 6), by up to 1.43 where the relations compute the record and 1.01 to 1.12 where the model chooses most of it. The masks alone run at 0.95 to 1.07 of XGrammar’s throughput up to 64 in flight, because the workers overlap the GPU, so the cost of exactness is host CPU. Because every record is also valid, the gain in usable output is far larger: FactorSpec serves up to 13.9 the valid planning records per GPU-second of syntax-only baselines. A solver makes every record valid too, so against it the margin is speed, 1.04 to 1.46; where gold follows a fixed objective the solver’s records match gold more often. These results hold, as leads or ties, across two engines, four models, tensor parallelism and sampling.

Figure 6. With every record valid, the combined drafter matches or outruns the speculator tuned per load. Throughput over XGrammar alone, each speculator at its best shape per cell.
This paper makes the following contributions.
The constraint as a lossless drafter that knows which drafts are certain, with per-request verify widths, where engines verify a step at one width (Sections 3.1 to 3.3).
Exact per-token enforcement of joint relations, where semantic decoders check local ones: a memoized feasibility check over factor graphs, a structure engine that keeps every admitted token completable, and a JSON Schema frontend (Sections 3.4 and 3.5).
A constraint service outside the scheduler process, where grammar engines run inside it: worker processes write shared-memory mask rows and compute ahead (Section 3.6).
An evaluation in two engines, on three model sizes, two families and six workloads, against speculators tuned per load, enum schemas, retries, reasoning, solvers and enumerated schemas (Section 5).
Background and Motivation
Speculative decoding in a serving engine
A serving engine runs a scheduler loop that admits requests, forms a batch, launches the target’s forward pass and processes the previous iteration’s results. Under speculative decoding, a drafter proposes several tokens per request, and the target verifies them in one forward pass (Leviathan et al., [18]; Chen et al., [7]), a tree per request in SGLang (Miao et al., [25]) and a chain in vLLM. Drafts come from a learned head such as EAGLE-3 (Li et al., 2025b) or from an n-gram corpus of earlier text. The tokens a verify step yields per request, the acceptance length, set the speedup when the batch is small. As the batch grows, each verify slot also costs time, and the engine verifies every request of a step at the same width, so the width suits the batch on average.
Structured generation
For a constrained request the engine keeps a grammar object with three calls: fill, which writes the request’s row of a vocabulary bitmask before sampling; accept, which advances the object by a sampled token; and rollback. A grammar engine such as XGrammar (Dong et al., [11]) compiles a schema into an automaton and answers these calls in C++ in a few microseconds. The engine makes the calls on its scheduler thread, one request after another, so their cost adds to every step: negligible at microseconds per call, and significant for a heavier check. Under speculation, the grammar supplies a mask row per draft node.
Relations as a factor graph
A record’s fields that take finitely many values are variables, and a relation among fields is a factor, a Boolean table over the variables in its scope. The support of a variable under evidence is the set of its values that extend to a full assignment satisfying every factor. A mask needs exactly this set: a value outside it reaches an infeasible prefix, and every value inside it can still complete the record. Bucket elimination computes the support exactly (Dechter, [9]) at a cost exponential in the induced width of its elimination order. Such relations are costly to state as a grammar: to admit references to just the of identifiers a record declared earlier, an automaton must remember which were declared, up to states, while a factor graph keeps the identifiers as variables and relates each reference directly.
Motivation
We measured Qwen3-8B on SGLang with workloads from tool calling and planning (§ 5.1). Three observations motivate the design: an opportunity (O1), a requirement (O2) and a challenge (O3), each met by one part of § 3.
O1: The relations determine most of the record, and the engine’s speculators propose little of it at load. Table 1 splits the determined tokens of gold records by source. On the tool calls the determined text is mostly copied from the prompt, which a corpus or a prompt matcher can also propose. On trip planning all of the itinerary and on meeting planning 79% of the schedule is computed from the problem, so those tokens lie outside the reach of both drafters. The engine’s speculators miss these tokens, because their gain falls with the batch: tuned per load, they run at 1.38 to 2.86× XGrammar at 8 requests in flight but only 0.94 to 1.17× at 128 (Figure 6), because a step verifies every request at one width. The constraint should draft what it determines and size each request’s verify by it (§ 3.1 to § 3.3).
| 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.
O2: When the model must satisfy joint relations, it violates them, and retries and reasoning repair few. The drafts must also be valid. On tool calls, whose relations are mostly memberships, XGrammar alone on the ledger and an enum schema on retail and BFCL make 0.98 to 1.00 of the records valid (Figure 2), because a membership is a per-field check. On trip and meeting planning, whose relations join fields, an enum schema leaves validity where XGrammar’s is (Figure 2 and Figure 8(b)), and the best baseline makes under a third of the records valid. Retries succeed on a minority of problems, whether the model samples three attempts, receives feedback or reasons for thousands of tokens. A weaker check misses the cycles too: arc consistency leads 12 to 64% of planning records to infeasible prefixes (§ 7), because local propagation sees each constraint in isolation. The relations must be enforced exactly while the model decodes (§ 3.4 and § 3.5).
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 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.
O3: Constraint work serialized over the batch limits throughput. The engine calls each request’s grammar object in turn on its scheduler thread, between two forward passes, which suits a C++ automaton that answers in microseconds. An exact check is heavier: opening a field costs up to 10 ms at the 99th percentile (§ 7). Run in a single worker process beside the GPU, the check holds the masks to 0.90 of XGrammar on meeting planning and our drafter to 0.92 to 0.93 of the engine’s n-gram drafter; with eight worker processes the masks reach 0.95 and the drafter 1.09 to 1.22 (Figure 10(g)). The work must leave the scheduler thread and spread over processes that run while the device computes (§ 3.6).

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.
Design
Figure 3 shows FactorSpec inside a serving engine. A request names a spec, a template with a factor graph, together with an instance of the problem. After the draft–verify loop (§ 3.1), the section follows § 2.4: the drafters and widths take O1’s opportunity (§ 3.2 and § 3.3), exact feasibility and tokenization meet O2 (§ 3.4 and § 3.5), and the service meets O3 (§ 3.6).

Figure 3. FactorSpec in a serving engine. ❶ The scheduler sends each request’s accepted tokens to its worker. ❷ 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. ❸ It replies with the tree and its certain nodes , which the target accepts with probability one; the engine merges the tree with its drafters and picks each request’s width . ❹ The target verifies under the rows. ❺ The accepted tokens start the next step. The worker panel shows an open position of another tour.
Lossless constraint drafts
FactorSpec decodes in the draft–verify loop of speculative decoding, with the constraint as drafter. At each step it drafts, for each request, the run of tokens the relations determine from the current position, then candidates at the first open position, and the target verifies the tree in one forward pass under a mask row for every node. A determined token is the one its mask admits, so the target accepts it with probability one, and the constraint knows before the verify how many of each request’s drafts are certain.
The drafts are lossless. Our reference decoder is token-bytoken decoding under the mask “grammar and relational feasibility”. Speculation changes only which tokens one forward pass verifies, so in exact arithmetic greedy output equals the reference decoder’s and exact rejection sampling preserves its token-level distribution. That distribution is the masked decoder’s, the guarantee grammar masks provide [31], which differs from the model’s distribution conditioned on a valid record. In floating point a verify of another shape can flip a near-tie (§ 9); validity holds for every record.
A step, end to end. Take the tour of Figure 4 with the road rows shown, after the model has written the first stop, Rome on day 1, and the key of the second stop’s city. The scheduler sends the request’s accepted tokens to its worker (❶). The worker adds Rome and day 1 as evidence and asks the factor graph for the support of the second city: the road table admits only Oslo, so that field and its day, , are determined, and so is the third stop, Lima on day 6. The rest of the record is a determined run of 24 Qwen3 tokens in the engine’s JSON rendering. The worker writes a mask row for each node of the run, up to the node budget, into the request’s shared-memory block (❷) and replies that every node is certain (❸). The scheduler gives the request the server’s full width of 12 slots, the target verifies them under the rows (❹), and all 12 are accepted (❺). Meanwhile the

Figure 4. A declared record: a three-city tour that takes a road between stops, visits each city once and reaches each stop on day one plus the stays before it. Abridged from our repository’s example: required keys, other declaration keys, labels, one road row and a first-day relation omitted.
worker has already computed the remaining 12 tokens, so the next step reads them and completes the record at once.
The drafters
O1 shows that the relations determine most of each record. FactorSpec therefore drafts from the constraint, as § 3.1 describes, and combines that draft with the engine’s drafters where the record holds text that the relations leave undetermined.
Factor drafter. The factor drafter proposes the constraint’s tree (Figure 3, left): the determined run from the current position, then the candidates of the token trie at the first open position (§ 3.5), up to the node budget. The target accepts every node of the determined run, because the mask at each of those positions allows one token.
Combined drafter. At an open position the model chooses among the candidates, and on copy workloads the engine’s n-gram corpus often predicts its choice. The combined drafter grafts the corpus’s continuation under each open leaf and asks the service for the grafted nodes’ rows. Rows go to the grafted tokens the spec allows, and the mask walk descends through allowed tokens alone, so a refused graft drops out of the verify.
Merged drafter. Where the open text is prose, a learned head may predict it better than a corpus. The merged drafter therefore gives a request the constraint’s tree whenever the constraint offers one and any other request EAGLE-3’s, in one verify at one width per step, and skips the drafter head when every request takes the constraint’s tree.
The engine’s drafters also run under our masks, which the evaluation uses to compare drafters on identical records; the service writes their rows while the target runs.
Per-request verify widths
The drafts also tell the engine how wide to verify. A verify step sends tokens through the target. Below the device’s knee, where reading the weights bounds the forward pass, extra slots are nearly free; above it, each slot costs time and returns a token when the target accepts it. An engine verifies every request of a step at one width, so a request inside free text takes the slots a request inside a determined run needs. The constraint knows, per request, how many of its draft positions are certain, so the factor and combined drafters give each request a separate width and choose the widths to maximize expected accepted tokens per unit of step time,
where counts request ’s certain nodes within its width, which the target accepts with probability one;
is the expected accepted tokens of guessed nodes, an exponential moving average over the drafter’s verifies, each of which measures every narrower width at once; and is the tokens the forward pass computes for the step’s slots, padded to a captured graph when one runs the step. Read through its least concave majorant, a request’s return per added slot is non-increasing, so for each total the best widths take the slots of highest return across requests, and one sorted pass scans every total (Algorithm 2 in Section A). Certain nodes return one token each and are taken first; a request inside free text keeps its root and the guesses whose return exceeds their cost.
The knee is 128 tokens, measured on the A6000; is fitted once per model and tensor-parallel size; and is learned from the drafter’s measured steps, pooled across ranks at intervals so that every rank chooses the same widths. Per-request widths are a server mode, on in every run we report except the full sets, the worker ablation and the jump-forward comparison, which use one width per step.
The forward pass computes each request’s real slots alone; Section A describes the verify layout, the captured graphs and how tensor-parallel ranks agree on widths.
Exact feasibility
O2 requires every draft, and every token the target samples, to hold the relations exactly.
Specs. A client declares a record as a JSON Schema and a list of relations over JSON Pointer paths (Figure 4), and the server compiles it to a spec: a template, whose choice fields are factor variables, and a factor graph over those variables. A spec is built from the request alone: the variables’ domains and the factors come from the problem statement or the tool context in the prompt. A spec can be built at three levels, which the evaluation compares: syntax, which a grammar engine can enforce; membership, where each reference is one of the identifiers the context declares; and relational, with every factor.
Exact feasibility. Every mask rests on one query: the support (Section 2.3) of the next field given the values the decoder has committed. To answer it, the factor engine stores each factor as a dense Boolean table within a per-graph budget and refuses an input table over the budget when the spec is built. A support query reduces those tables by the evidence and eliminates the other variables in a min-fill order in the Boolean semiring: the tables of a bucket are joined by AND and the eliminated variable is reduced by OR. The answer is exact: every value in the support has a valid completion.
A decoder’s queries form a walk, each clamping one more variable, so consecutive queries share almost all of their work. The engine exploits this by memoizing a reduced table by its factor and the restriction the evidence places on its scope, and a bucket’s message by its variable and the keys of the tables that feed it. A query then reduces only the tables the new value changes and joins only the buckets they reach; on a chain-shaped graph the cost is the work of one neighborhood.
Memoization bounds the work per query, but the size of each table depends on how a relation is encoded. Trip planning’s all-different over cities, encoded as one table over every city variable, joins up to 22.2 million entries at seven cities and exceeds the budget at eight. A chain encoding over visited-set states holds the same itineraries with a largest join of 8,575 entries at seven cities and 529,200 at ten, which covers every problem of the dataset.
Global factors. Some relations stay large under any table encoding, yet are cheap to decide directly. A meeting schedule visits parties in turn, each with a location, an availability window and a minimum stay; as tables it is a join over three clock variables per visit of several hundred values each. Because waiting is allowed, ending a visit earlier keeps every way to continue, so whether a plan can still meet more parties depends only on the parties met, the last one and the time, monotonically in the time. A dynamic program over states, the parties met and the last party, therefore gives the latest time from which each state can still complete the plan, and every field’s exact support is a lookup in it. Such a relation enters the graph as a global factor with a dedicated exact check, over a scope disjoint from every other factor’s, so a variable’s support is the support within its component while the rest remain satisfiable.
From values to tokens
The feasibility check answers questions about values, but the decoder emits tokens. The structure engine bridges the two and maintains the invariant that every admitted token extends to a complete, valid record. Outside free text, a state holds candidate continuations: each runs from the current position through the next field value or structural decision and on through the literal text that follows, up to the next field boundary. These candidates are tokenized in context, as the tokens they add to the tokenization of the preceding text, so a value’s first token is the one the tokenizer produces after the preceding text. The allowed set is then the next token of every candidate that matches the tokens emitted so far. A value followed by a decision, such as whether an array goes on, gives one candidate per pair, because the token that closes the value differs between the two.
A free field is a token class that ends at the first token of the following literal; where the tokenizer merges punctuation with a delimiter, as in !", the engine splits the merged token and carries the rest of the delimiter as a forced run. If a boundary would re-tokenize the text before it, the request ends with an explicit error. States are memoized per parent and token, so a draft tree and the later walk over it derive each state once. Positions where one token is allowed form the determined runs that the drafters of § 3.2 propose.
The session. A per-request session exposes fill, accept, rollback, fork and expand, which builds a draft tree under a node budget. It keeps the state after every accepted token, so a rollback is a list truncation and a fork shares the states it has; a disallowed token or an empty allowed set raises an error before it reaches the sampler. Every drafted and verified token passes through the session, which is why the guarantee of § 3.1 holds.
The constraint service
O3 requires the constraint’s work to leave the scheduler thread (Figure 5). The service runs it in a pool of worker processes, eight per rank by default, on the cores the scheduler process leaves free; a worker imports the constraint library alone, and every session of one spec opens on one worker and shares its compiled check.

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 and build the trees while the scheduler processes the result.
Each request holds two blocks of a shared-memory array of mask rows, sized to the verify width, one for the current step and one for the next. A worker writes each node’s row into a block and its reply names the block, so the scheduler’s fill is a row copy. Per step, each request posts its accepted tokens and its ask: the constraint’s tree, the rows of another drafter’s tree, or the root row. The messages leave in one batch per worker and kind of ask, so a step of 64 requests costs 8 to 16 messages each way; Algorithm 1 in Section A gives a worker’s step.
At a determined position the next token is known before the target samples it, so after replying the worker computes the next reply ahead while the device runs the verify, one field value at a time, so that the next step finds the worker ready even while it opens a field of several hundred values. A speculative drafter asks for the next trees as soon as the verify’s tokens reach the host, before the scheduler accepts them into the grammars. The workers therefore build the trees while the scheduler thread processes the result, and the scheduler copies rows before it launches the next verify (Figure 5).
Engine integration
SGLang. FactorSpec registers a grammar backend and five speculative algorithms through SGLang’s plugin registries: the three drafters, and the engine’s n-gram and EAGLE-3 drafters under FactorSpec’s masks. The backend hands every non-relational request to XGrammar, so the server serves everything an XGrammar server serves. Every configuration we evaluate, ours included, runs under SGLang’s overlap rule, which disables the overlap scheduler for a speculative batch with a grammar.
vLLM. vLLM drives the grammar one request at a time, and a blocking call per request would make the constraint’s work serial again. The vLLM grammar object therefore answers fill, accept and draft validation from the block of its last reply, and the proposer posts every request’s step before it waits for any reply.
Implementation
FactorSpec is 16,700 lines of Python, counted with wc. The constraint engine, 9,100 lines excluding its workload declarations, holds the factor engine, the structure engine, the session and the JSON Schema frontend, and runs independently of any serving engine; the serving layer, 7,600 lines, holds the service, the drafters, the width model and both engines’ adapters. A declaration’s schema holds objects, enums, integer ranges, optional properties, bounded arrays and capped free text, and its relations are drawn from twelve kinds, from allowed rows and all-different to running sums and visit schedules, whose encodings a compiler chooses; a declaration compiles in 0.05 to 0.55 ms at the median. In SGLang 0.5.16, FactorSpec registers its grammar backend and drafters through the plugin registries and replaces three functions that lie outside them: the batch mask fill and the draft-tree mask builders of the n-gram and EAGLE-3 workers; in vLLM 0.21.0, two patches register the backend and the proposer. The workers are plain subprocesses that share the mask rows through one shared-memory segment. A conformance test replays recorded traces through both engines’ grammar objects and compares every mask row against the constraint session’s output.
Evaluation
We ask four questions. RQ1: How much faster does the constraint make decoding as a drafter (§ 6)? RQ2: What does exactness cost against a grammar mask (§ 7)? RQ3: How many more valid records does an operator get (§ 8)? RQ4: Does the design generalize, and what accounts for it (§ 8.1)?
Setup
Platform. Two NVIDIA RTX A6000 GPUs and a 64-core two-socket host; Qwen3-8B with an EAGLE-3 head unless stated, and Llama 3.1 8B, Qwen3-1.7B and Qwen3-14B; SGLang 0.5.16 and vLLM 0.21.0 (Section B gives the details).
Workloads. Three tool-calling workloads, a synthetic ledger and -bench retail ([44]) and BFCL multi-turn ([32]) calls, whose arguments must name identifiers the context declares; and three NATURAL PLAN ([47]) planning workloads, trip, meeting and calendar, of 999 problems each, plus all 1,599 trip problems as a full set.
In meeting and calendar planning the model also chooses among valid plans. Trip planning with notes adds a free-text note of up to tokens to every stay, which lowers the determined share from 1.00 at to 0.50 at 128. RQ2 and RQ4 use the first five workloads, and RQ2 all six at 128 in flight. Section B states each workload’s relations and prompts.
Baselines. Constraints: XGrammar and llguidance on the syntax schema, and XGrammar with each field’s value set as an enum. Speculators: SGLang’s n-gram drafter at its default width of 12 and at 4, 8, 16, 24 and 32, and EAGLE-3 at its default tree, at five steps, four ways and as chains of two, four and eight tokens. We call each of these eleven drafter settings a shape, one workload at one load a cell, and a cell’s fastest shape its tuned speculator. Retries: retry samples up to three attempts, error feedback names the violated relation, and thinking lets Qwen3 reason for up to 8,192 tokens. Solvers: solve then emit computes a valid record on the CPU before decoding and constrains XGrammar to emit it; an enumerated schema lists each request’s feasible records as a JSON Schema, any of at most 1,024 records. We report FactorSpec’s combined drafter unless a figure names another; all configurations run under SGLang’s overlap rule.
Metrics and protocol. We report throughput, and valid records per GPU-second, which charges every invalid answer and retry; correct records per GPU-second counts only records that match gold. Closed loop runs at 1 to 128 requests in flight on a separate window of records per load. Open loop offers Poisson arrivals at six rates for two minutes each; the planning workloads replay a pool of 128 problems, which lets every n-gram corpus, ours included, see earlier answers (Section B). Each configuration runs on a fresh engine, greedy except under retry and sampling; each of 332 configurations ran three times, and figures show the mean and the range on one A6000 with Qwen3-8B unless they name another setting. Validators written independently of the constraint engine check every record.
RQ1: The constraint as a drafter
Following O1, we expect the constraint’s drafts to gain most where the relations compute the record, and to keep their gain at load. Figure 6 compares the combined drafter with the engine’s speculators, each tuned over the eleven shapes per cell (Table 3).
| Workload | 8 in flight: n-gram | 8 in flight: EAGLE-3 | 64 in flight: n-gram | 64 in flight: 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 |
| Calendar | 16 | 5×4 | 4 | chain 4 |
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.
Faster than tuned speculators at every load. With every record valid, the combined drafter leads the tuned speculator by up to 1.43 at 8 in flight, 1.26 at 64 and 1.39 at 128. The lead is largest where the relations compute the record, 1.26 to 1.43 on trip planning, because there a determined run fills most of the verify step. It is smallest where the model chooses most of the record and the n-gram corpus covers the rest, 1.01 to 1.12 on the tool calls (a tie on -bench retail at 64). At 128 in flight the speculators fall to 0.94 to 1.17 XGrammar, because a step verifies every request at one width; the combined drafter still runs at 1.05 to 1.45, because per-request widths keep slots on the requests that return them.
Longer accepted runs. Table 2 shows why the throughput leads hold. Each verify step accepts up to 10.5 tokens per request on trip planning and 8.4 on meeting planning, 1.0 to 1.9 as many as the fastest n-gram shape, because a determined run is accepted whole. Those determined runs carry most of the gain: verifying only them reaches 0.89 to 0.97 of the factor drafter (RQ4). The guesses and per-request widths add the rest, which decides the speed as free text grows: on the ledger at 64 in flight both drafters yield 4.5 tokens per step, yet ours runs 1.11 faster, because per-request widths spend fewer slots on guesses.
| 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 6.
The speed comes from the drafts. A faster drafter could write shorter or different records. Under our masks, where both drafters write identical records, the combined drafter still runs at 1.07 to 1.42 the n-gram drafter at 8 in flight and 1.07 to 1.79 over loads 1 to 64.
Free text. As the determined share falls, so does the lead (Figure 7). On trip planning with notes at 64 in flight, the combined drafter falls from 1.77 XGrammar to 1.13 as notes grow to 128 tokens, while the tuned n-gram drafter and EAGLE-3 fall below XGrammar from 32-token notes on, to 0.72 and 0.73. Per-request widths explain the gap: a request inside a note keeps only the guesses whose return exceeds their cost, which adds 8 to 37% at every nonzero note budget. Removing them drops our drafter to 0.88. The merged drafter, at one width per step, runs at 0.64 to 0.91 of the combined one.
Figure 7. As notes grow, only the combined drafter stays above XGrammar. Trip with notes at 64 in flight.
Takeaway. The relations determine the drafts that lie beyond a speculator. Drafting them at a width per request keeps speculation profitable at high load and in free text.
RQ2: The cost of exactness
With the speed established, we ask what exactness costs.
Masks at a grammar mask’s cost. The masks run at 0.95 to 1.07 of XGrammar’s throughput at every load up to 64 in flight (Figure 8(a)) and at 0.94 to 1.13 at 128, because the service computes each row while the device runs. Llguidance reads 0.94 to 1.05 on the same cells, so ratios above one come from the different records the masks produce, which confirms that the check itself hides behind the step. That parity has a host cost: the eight workers per rank hold 7.4 to 8.3 of the 32 cores of the socket the scheduler leaves free and 7.8 to 9.7 GiB (Figure 8(d)). On Qwen3-1.7B, whose step is under half as long, the masks still run at 0.95 to 1.01 of XGrammar.
What one query costs. The per-query breakdown explains where those cores go (Table 4). Most of each position’s mask is a 4.3 to 4.9 s support lookup, but opening a field rebuilds the elimination tables: that costs up to 2.2 ms at the 99th percentile on the tool calls and 10 ms on meeting planning, where the dynamic program is built. Serial on the scheduler thread, such openings would delay every request of a step. Once the field is open, a single feasibility query into it takes 2 to 131 at the median and at most 3.2 ms, and on trip planning the median grows from 101 at three cities to 198 at ten as the tables grow. The memos make distinct queries 1.5 to 2.5× cheaper where the relations are tables, and change little on meeting and calendar planning, whose global factors answer from dedicated checks.
| Workload | Position p50 | Position p99 | Query p50 | Query p99 | Query 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 | 0.22 | 25.0 | 0.06 | 3.22 | 1.1× |
| Calendar | 4.5 | 0.38 | 54.9 | 0.08 | 0.11 | 0.9× |
| 3 cities | 4.6 | 0.35 | 100.6 | 0.22 | 0.23 | 1.6× |
| 4 cities | 4.5 | 0.39 | 115.0 | 0.29 | 0.31 | 1.9× |
| 5 cities | 4.5 | 0.41 | 130.2 | 0.36 | 0.41 | 2.0× |
| 6 cities | 4.5 | 0.47 | 138.4 | 0.44 | 0.48 | 2.2× |
| 7 cities | 4.5 | 0.52 | 153.6 | 0.57 | 0.60 | 2.3× |
| 8 cities | 4.5 | 0.67 | 163.8 | 0.69 | 1.37 | 2.5× |
| 9 cities | 4.5 | 0.84 | 179.5 | 0.95 | 1.78 | 2.4× |
| 10 cities | 4.6 | 1.31 | 198.4 | 1.71 | 2.61 | 2.7× |
Table 4.
Weaker checks miss the cycles. Exactness could be traded for speed: a weaker constraint is cheaper to check, but it enforces only local consistency. An enum schema or our field membership makes the tool calls valid, 0.98 to 1.00, because their relations are mostly memberships. On trip and meeting planning, whose relations close cycles, the weaker checks leave 0.08 to 0.16 valid (Figure 8(b)). Our arc-consistency propagator, memoized like the exact engine, is exact on the acyclic relations of the tool calls ([12, 2]), at 0.59 to 0.97 of our masks’ throughput. On planning it runs at 0.29 to 0.95, and leads 12 to 16% of trip records and 53 to 64% of meeting records to infeasible prefixes (Figure 8(c)), because propagation sees each constraint in isolation; under the exact check, every record completes.
Takeaway. Off the scheduler thread, the exact check’s millisecond tail overlaps the GPU, so exactness costs a grammar mask’s time and about eight host cores per GPU. A weaker check leads planning records to infeasible prefixes.
RQ3: Valid records
An operator pays for valid records. Against a syntax-only baseline, we expect FactorSpec to lead by about the inverse of that baseline’s validity; against one that makes the records valid too, by throughput.
Against the model alone. The first expectation holds (Figure 9). Against the strongest of seven syntax-only baselines, FactorSpec serves 2.6 to 13.9× the valid planning records per GPU-second at 8 and 64 in flight. The gap is largest on trip planning, at least 9.3× over every prompt and run, because the baselines make fewer than one record in ten valid. On the tool calls, which an enum schema already makes valid, the lead is throughput alone, 1.07 to 1.20×. The lead carries over to records that match gold, 2.0 to 13.8× on planning, with a tie on retail and BFCL. Reasoning closes little of the gap: with thinking at 8 in flight on 64 problems, 19% of trip plans, 31% of meeting schedules and 95% of calendar slots become valid, so FactorSpec serves 79 to 631× their valid planning records per GPU-second.
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.
Against solvers and enumerated schemas. The second expectation holds too. Solve then emit needs only 0.3 to 1.7 ms to compute each answer, yet it still enters the grammar engine one token per step; FactorSpec’s determined runs write every known token at once, serving 1.28 to 1.46× the solver’s valid itineraries and meeting schedules. The enumerated schema fits every calendar and retail record and 381 of 384 BFCL calls, where FactorSpec leads it by 1.06 to 1.31×; our enumeration, one schema per appointment, refuses every trip and meeting request, which an anyOf over whole records could list where they are few. The solver chooses better, however, where gold follows a fixed objective: its earliest meeting plans match gold in 46 to 56% of problems against FactorSpec’s 14 to 16%, so it serves 2.6 to 2.8× FactorSpec’s correct meeting schedules, because its records always match its objective.
Full sets and load. Over each full set (Figure 12), FactorSpec’s records are all valid and match gold on 98 to 99% of itineraries, 15.0% of meeting schedules and 67.4% of calendar slots, against at most 13.6, 8.3 and 36.3% for the baselines. Seen from the request’s side, just 9 to 14% of the baselines’ trip and meeting requests ever receive a valid record; FactorSpec’s meeting schedules take 12.4 s at the median, since the baselines’ few valid ones are short.
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.
Under open-loop arrivals the gap widens further (Figure 13 and Figure 14): past the grammar engine’s capacity, FactorSpec completes 32 valid itineraries per second inside 10 s at 32 requests per second against 1.2 for the n-gram drafter, and 7.2 valid meeting schedules inside 20 s at 8 per second. against 0.66. Its 99th-percentile latency is the lowest at every rate, 3.8 s against 26 s on trip planning, because the determined runs keep the server ahead.

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.
Takeaway. Where relations join fields, validity, more than speed, sets how many usable records a server delivers. Against an equally valid solver the margin is speed; where gold follows a fixed objective, the solver chooses better.
RQ4: Generality and attribution
Other engines, models and sampling. The design carries over (Figure 10, 64 in flight). In vLLM, which drives the grammar one request at a time and verifies chains, the factor drafter leads the best of six baselines by 1.03 to 2.24×, because the determined runs help even in chains. The masks reach 1.19× XGrammar on trip planning, where the exact check’s different records account for the gap. Across four models (Llama 3.1 8B, Qwen3-1.7B, Qwen3-8B, and Qwen3-14B over two GPUs), the combined drafter leads by 1.02 to 1.50×, with ties on BFCL at 1.7B and at 8B over two GPUs. At temperature one validity stays 1.00 and the drafter leads by 1.02 to 1.35×, because sampling adds variety that the constraint still covers. Settings (b), (d), (e) and (f) ran at a later commit (Section B).
What each mechanism adds. The three mechanisms each contribute measurable speed when the others are in place (Figure 10(g, h)). Eight workers per rank raise the combined drafter by 19 to 31% over one, as O3 anticipates: the check’s millisecond tail needs parallelism to hide. Jump-forward, which verifies only the determined run, reaches 0.89 to 0.97 of the factor drafter, so the guessed nodes return 4 to 12% (0.94 to 1.01 in a separate campaign, Table 5). Per-request widths add 2 to 22% to the factor drafter and 1 to 10% to the combined drafter at 64 in flight, and cost up to 2.3% at one request in flight; one width per step, chosen by Equation (1), comes within 2% of the best fixed width.
| Workload | In flight | Jump-forward 12 | Jump-forward 32 | Factor 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 |
| Meeting | 64 | 0.94 | 0.91 | 0.95 |
Table 5. Throughput over the factor drafter at up to 12 slots, by the verify’s slots; mean of three runs.
Takeaway. The gains carry over to another engine, other models and sampling, and each mechanism adds measurable speed when the others are in place.
Discussion and limitations
A cell’s three runs repeat its prompts, so their range measures timing, and a speed lead of a few percent is a tie. Verify widths round differently: 1 to 4 of 64 greedy meeting records differ, all valid. The host work hides behind the device’s step, which we measure down to Qwen3-1.7B’s, on one GPU type and up to 128 requests in flight; a faster GPU shortens the step and may need more workers per rank. Declarations have finite domains and a table budget; a new relation kind needs a server-side extension, and writing correct relations is the application’s task.
Related work
Speculative decoding. Speculative sampling ([18, 7]) and tree verification ([25, 40, 8]) draft from learned heads ([5] (Li et al. 2025b)), Jacobi iteration (Fu et al., 2024), retrieval ([29] (He et al. 2024)) or the prompt, and their gain falls with the batch ([23, 45, 41]). Jump-forward decoding ([48]), Illguidance’s forced tokens and DOMINO ([4]) skip or speculate tokens a grammar determines, and adaptive speculation tunes one draft length per step ([15]). FactorSpec drafts what relations across fields determine and sizes each request’s verify by it, so Equation (1) divides a step’s slots among requests knowing part of each return.
Constrained decoding. Grammar engines ([11, 42] (Li et al. 2026)) and set automata (Su et al., 2026; Xu & Bouyarmane, 2026) overlap bitmask computation with the GPU. Semantic decoders check prefixes against completion engines ([37, 33]), static analysis ([1, 26]), composed parsers (Li et al., 2025a), a live environment ([46]), eager constraints ([3]) or programmable realizability ([27]); their checks are local. Solver pipelines answer or check outside the decoder ([22, 30, 16]). FactorSpec enforces exact joint relations ([6]) inside the decoder by moving the heavier check to worker processes, builds on consistency and elimination ([12, 2, 10, 9, 36]) as FactorDLM does for diffusion models (Su & Zhang, 2026), and composes with work masking’s distortion ([31, 28, 35]).
Conclusion
Serving engines’ drafters miss the text a structured record’s relations determine, and grammar masks enforce only syntax, so the model must satisfy the relations, which it violates. FactorSpec serves exact relational constraints as speculative drafts: an exact feasibility check decides which tokens the relations determine, the constraint drafts them as certain and sizes each request’s verify by them, and worker processes compute the masks while the GPU runs. Its drafts yield up to 10.5 tokens per verify step, and it matches or outruns speculators tuned per load by up to 1.43×, with every record valid at a grammar mask’s cost; the gain is largest where the relations compute the record. A constraint that knows which tokens it determines is itself a drafter, so serving engines can treat exactness as a source of speed.
AI Usage Disclosure
We used Claude (Anthropic) and ChatGPT (OpenAI), large language model assistants, to edit the writing of this paper: to proofread the text, correct grammar and spelling, and improve the wording, clarity and consistency of its sentences. The authors reviewed every edit and take full responsibility for the content of the paper.
Design Details
Algorithm 1 gives the step of one constraint worker (§ 3.6). A worker answers every request open on it in one reply per step. Where the accepted tokens are the determined run it computed ahead, the reply is already written; otherwise the worker advances the session from as far as the computed-ahead state matches. After replying, it computes ahead for every request whose sent tree is wholly determined, a chain of the full node budget under a speculator or a single-token root otherwise, and whose next position after it is determined too; it stops between two field values when the next step’s message arrives, so computing ahead always yields to the next step.
Algorithm 2 gives the per-request width allocation of § 3.3. Each request starts at its root. Its certain nodes return one token each and come first; its guessed nodes follow with the slopes of ’s least concave majorant, which are non-increasing, so one pass over all marginal returns in decreasing order visits the best allocation of every total
Algorithm 1 A worker’s step.
Require: one message per request open on the worker: its accepted tokens and its ask
for each request of the step do
if ’s accepted tokens are the run computed ahead then
reply with the reply computed ahead
else
advance ’s session, from the computed-ahead state where it matches
build the ask: the constraint’s tree under the node budget, the rows of another drafter’s tree, or the root row
write each node’s mask row into ’s free shared-memory block
end if
end for
send one reply for the step
for each request whose sent tree and next position are determined do
build ’s next reply into its other block, one field value at a time
stop between two values if the next step’s message has arrived
end for
poll for the next message for up to 1 s, then block
number of slots, and the allocation kept is the one with the most tokens per unit of step time. A request whose tree has more guessed nodes than any verify has yet measured takes its whole tree, and that verify measures every cut of it.
The engine’s verify bookkeeping keeps its uniform layout at the widest request’s width, with a request’s slots past its width unreachable, while the forward pass computes the real slots alone: each request gets a separate query length and packed tree mask. In this mode the verify graphs, captured per batch size at widths 2, 4, 8 and the server’s, run a step padded to the narrowest that holds it. Under tensor parallelism each rank’s service builds trees on a separate schedule, so the ranks compare a hash of each step’s trees and follow the first rank’s where they differ.
Evaluation Details
Platform. Two NVIDIA RTX A6000 GPUs with 48 GB each, and a two-socket Intel Xeon Gold 6338 host with 64 cores and 1 TB of memory. Qwen3-8B (Qwen Team, [34]) with the AngelSlim EAGLE-3 head, Llama 3.1 8B Instruct (Llama Team, [24]) with SGLang’s packaging of the EAGLE-3 authors’ head, Qwen3-1.7B and Qwen3-14B run in bfloat16 with a 12,288-token context and Qwen3’s thinking mode off unless stated. SGLang 0.5.16 and vLLM 0.21.0 are each capped at 30 GiB of device memory per
Algorithm 2 Per-request verify widths ((1)).
Require: each request’s tree, its first nodes certain; slopes of ’s least concave majorant; step cost
for each request ; the number of requests
for each : returns of 1, then for its guessed nodes
;
for each by decreasing do
; ;
if then
;
end if
end for
return ; request verifies its tree’s first nodes
GPU.
Workloads. The ledger is a synthetic tool-calling record whose transfers must refer to accounts the record declares, with distinct endpoints and a reversal that copies an earlier transfer. -bench retail and BFCL multi-turn calls must name the orders, items and files the conversation declares; the retail relations were mined from the training split, and we evaluate on the test split. The planning workloads come from NATURAL PLAN, excluding the problem each prompt uses as its worked example: 999 trip problems of three to seven cities, all 1,599 of three to ten as a full set, and 999 meeting and 999 calendar problems. An itinerary must visit every city for its stated days over direct flights within the event windows. A meeting schedule must respect travel times and availability windows and meet the most friends any plan meets; the model chooses whom and when. A calendar slot must fit every busy interval; on 600 problems several slots do, and the model chooses by the stated preferences. Every prompt shows one worked example and asks for a JSON record, and the meeting prompt states how many friends the best plan meets.
Tuned shapes. Table 3 lists the fastest shape of each speculator per cell at 8 and 64 in flight; the tuned speculator of every cell is the n-gram drafter’s. At 128 in flight the speculator is the best of ten shapes, since width 32’s verify exceeds the attention kernel’s workspace at that load.
Baselines per setting. In vLLM the baselines are XGrammer, the n-gram drafter at draft lengths 2, 4, 8 and 16, and EAGLE-3 at three draft tokens. In SGLang, the settings over two GPUs and on Qwen3-1.7B and Qwen3-14B compare against XGrammar and the n-gram drafter at widths 4, 8, 12 and 16; on Llama 3.1 8B also against EAGLE-3 at its default tree and as chains of two and four; and at temperature one against XGrammar and the n-gram drafter at width 12. The settings over two GPUs, on Qwen3-1.7B and
Qwen3-14B and at temperature one ran at a later commit than their baselines; their lead passes through XGrammar, measured in both sessions, so a change in the host’s speed cancels.
Requests per cell. Closed loop serves 64 requests per cell up to 16 in flight and 192 above, 192 also at 8 in flight in the tuned, solver and notes runs, and 256 at 128.
Enumerated schemas. Every calendar and retail record fits under the cap of 1,024 feasible assignments, in at most 16 and 31 anyOf branches once merged; 381 of the 384 BFCL calls fit, in at most 49 branches, and the client refuses the other 3. Compiling a schema on the client takes at most 0.9 s.
Thinking. Qwen3 reasons unmasked until </think> or a budget of 8,192 tokens, which with the longest prompt, 2,140 tokens on meeting planning, and the record stays inside the 12,288-token context; XGrammar then constrains the record. A trace that reaches the budget is closed by the engine and its record still decoded and scored. With this budget the -bench prompts exceed the context, so thinking serves the planning workloads.
Additional Results
Valid records at 8 in flight. Figure 11 repeats Figure 9 at 8 in flight, where the leads of RQ3 hold: 13.9× on trip, 13.2× on meeting and 2.6× on calendar planning over the syntax-only baselines.
What the exact check costs. Table 4 times the work a worker does, on one core, over 200 gold records per workload: each position’s mask, the allowed set and the advance by the gold token, and each feasibility query. Between records the heap is collected and frozen as a worker does when a request ends, so every timed query excludes a full garbage collection. The memo column answers each distinct query of the first 50 records again on a fresh engine, whose memos start empty, and gives the ratio of the two totals.
Matching gold over the full sets. Figure 12 gives the share of each full set whose record matches gold, beside the
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.
| Ledger | -retail | BFCL | Trip | Meeting | Calendar | |
| Records / GPU-s |
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.
validity of Figure 2.
Time to a valid record and open loop. Figure 13 gives the time to a valid record on trip and meeting planning and the service under Poisson arrivals on the ledger, trip and meeting planning, which RQ3 quotes.
On the tool calls, where most records are valid under every configuration, the time to a valid record follows each configuration’s speed (Figure 14(a–Figure 14c)). Under the open loop, FactorSpec’s 99th-percentile latency is the lowest at every rate on the ledger and on meeting planning (d, e).
A wider verify. The server’s widest verify is 12 slots. Table 5 compares jump-forward, which verifies only the determined run, at 12 and 32 tokens per step, and the factor drafter at up to 32 slots, each over the factor drafter at up to 12, in a separate campaign whose servers shared one history. On trip planning at 8 in flight, a record the relations fix whole, 32 slots run 1.20× faster; elsewhere they change the factor drafter’s throughput by −11 to +2%. Jump-forward runs at 0.94 to 1.01 of the factor drafter when both use 12 slots, and at 0.87 to 1.03 of it when both use 32; in this campaign the guessed nodes return less than the 4 to 12% of RQ4.
References
- [1]Agrawal, L. A., Kanade, A., Goyal, N., Lahiri, S. K., and Rajamani, S. K. Monitor-Guided Decoding of Code LMs with Static Analysis of Repository Context. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL http://papers.nips.cc/paper_files/paper/2023/hash/662b1774ba8845fc1fa3d1fc0177cee b-Abstract-Conference.html.DOI
- [2]Beeri, C., Fagin, R., Maier, D., and Yannakakis, M. On the Desirability of Acyclic Database Schemes. J. ACM, 30(3):479–513, 1983. doi: 10.1145/2402.322389. URL https://doi.org/10.1145/2402.322389.
- [3]Beurer-Kellner, L., Fischer, M., and Vechev, M. T. Prompting Is Programming: A Query Language for Large Language Models. Proc. ACM Program. Lang., 7(PLDI):1946–1969, 2023. doi: 10.1145/3591300. URL https://doi.org/10.1145/3591300.
- [4]Beurer-Kellner, L., Fischer, M., and Vechev, M. T. Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation. In Salakhutdinov, R., Kolter, Z., Heller, K. A., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, volume 235 of Proceedings of Machine Learning Research, pp. 3658–3673. PMLR / OpenReview.net, 2024. URL https://proceedings.mlr.press/v235/beurer-kellner24a.html.
- [5]Cai, T., Li, Y., Geng, Z., Peng, H., Lee, J. D., Chen, D., and Dao, T. Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. In Salakhutdinov, R., Kolter, Z., Heller, K. A., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, volume 235 of Proceedings of Machine Learning Research, pp. 5209–5235. PMLR / OpenReview.net, 2024. URL https://proceedings.mlr.press/v235/cai24b.html.arxiv.org/abs/2401.10774
- [6]Chavan, A. Constrained Decoding Eliminates Structural Failures in Small LLMs but Reveals a Scale-Dependent Semantic Gap. CoRR, abs/2609.23742, 2026. doi: 10.48550/ARXIV.2609.23742. URL https://doi.org/10.48550/ARXIV.2609.23742.
- [7]Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifre, L., and Jumper, J. Accelerating Large Language Models Decoding with Speculative Sampling. CoRR, abs/2302.01318, 2023. doi: 10.48550/ARXIV.2302.01318. URL https://doi.org/10.48550/ARXIV.2302.01318.
- [8]Chen, Z., May, A., Svirschevski, R., Huang, Y., Ryabinin, M., Jia, Z., and Chen, B. Sequoia: Scalable and Robust Speculative Decoding. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J. M., and Zhang, C. (eds.), Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. URL http://papers.nips.cc/paper_files/paper/2024/hash/ea1f5f0878d43ff4b8bf64ef4a2326c-Abstract-Conference.html.arxiv.org/abs/2402.12374
- [9]Dechter, R. Bucket Elimination: A Unifying Framework for Reasoning. Artif. Intell., 113(1-2):41–85, 1999. doi: 10.1016/S0004-3702(99)00059-4. URL https://doi.org/10.1016/S0004-3702(99)00059-4.
- [10]Dechter, R. and Pearl, J. Network-Based Heuristics for Constraint-Satisfaction Problems. Artif. Intell., 34(1):1–38, 1987. doi: 10.1016/0004-3702(87)90002-6. URL https://doi.org/10.1016/0004-3702(87)90002-6.
- [11]Dong, Y., Ruan, C. F., Cai, Y., Xu, Z., Zhao, Y., Lai, R., and Chen, T. XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models. In Zaharia, M., Joshi, G., and Lin, Y. C. (eds.), Proceedings of the Eighth Conference on Machine Learning and Systems, MLSys 2025, Santa Clara, CA, USA, May 12-15, 2025. OpenReview.net/mlsys.org, 2025. URL https://openreview.net/forum?id=rjQfX0YgdI.arxiv.org/abs/2411.15100
- [12]Freuder, E. C. A Sufficient Condition for Backtrack-Free Search. J. ACM, 29(1):24–32, 1982. doi: 10.1145/32290.322292. URL https://doi.org/10.1145/322290.322292.
- [15]Hou, Y., Zhang, F., Du, C., Zhang, X., Pan, J., Pang, T., Du, C., Tan, V. Y. F., and Yang, Z. BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., and Bekkerkamp, F., Mahajan, T., Wagstaff, K., and Zhu, J. (eds.), Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025, volume 267 of Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025. URL https://proceedings.mlr.press/v267/hou25h.html.arxiv.org/abs/2505.15141
- [16]Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Sadat, L., and Murthy, A. Position: LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks. In Salakhutdinov, R., Kolter, Z., Heller, K. A., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, volume 235 of Proceedings of Machine Learning Research, pp. 22895–22907. PMLR / OpenReview.net, 2024. URL https://proceedings.mlr.press/v235/kambhampati24a.html.arxiv.org/abs/2402.01817
- [17]Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J., Zhang, H., and Stoica, I. Efficient Memory Management for Large Language Model Serving with PagedAttention. In Flinn, J., Seltzer, M. I., Druschel, P., Kaufmann, A., and Mace, J. (eds.), Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023, pp. 611–626. ACM, 2023. doi: 10.1145/3600006.3613165. URL https://doi.org/10.1145/3600006.3613165.
- [18]Leviathan, Y., Kalman, M., and Matias, Y. Fast Inference from Transformers via Speculative Decoding. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 19274–19286. PMLR, 2023. URL https://proceedings.mlr.press/v202/leviathan23a.html.arxiv.org/abs/2211.17192
- [22]Liu, B., Jiang, Y., Zhang, X., Liu, Q., Zhang, S., Biswas, J., and Stone, P. LLM+P: Empowering Large Language Models with Optimal Planning Proficiency. CoRR, abs/2304.11477, 2023. doi: 10.48550/ARXIV.2304.11477. URL https://doi.org/10.48550/ARXIV.2304.1147.
- [23]Liu, X., Yu, J., Park, J., Stoica, I., and Cheung, A. Speculative Decoding: Performance or Illusion? CoRR, abs/2601.11580, 2026. doi: 10.48550/ARXIV.2601.11580. URL https://doi.org/10.48550/ARXIV.2601.11580.
- [24]Llama Team. The Llama 3 Herd of Models. CoRR, abs/2407.21783, 2024. doi: 10.48550/ARXIV.2407.21783. URL https://doi.org/10.48550/ARXIV.2407.21783.
- [25]Miao, X., Oliaro, G., Zhang, Z., Cheng, X., Wang, Z., Zhang, Z., Wong, R. Y. Y., Zhu, A., Yang, L., Shi, X., Shi, C., Chen, Z., Arfeen, D., Abhyankar, R., and Jia, Z. SpecInfer: Accelerating Large Language Model Serving with Tree-based Speculative Inference and Verification. In Gupta, R., Abu-Ghazaleh, N. B., Musuvathi, M., and Tsafrir, D. (eds.), Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, ASPLOS 2024, La Jolla, CA, USA, 27 April 2024- 1 May 2024, pp. 932–949. ACM, 2024. doi: 10.1145/3620666.3651335. URL https://doi.org/10.1145/3620666.3651335.
- [26]Mündler, N., He, J., Wang, H., Sen, K., Song, D., and Vechev, M. T. Type-Constrained Code Generation with Language Models. Proc. ACM Program. Lang., 9(PLDI): 601–626, 2025. doi: 10.1145/3729274. URL https://doi.org/10.1145/3729274.
- [27]Nagy, S., Zhou, T., Polikarpova, N., and D’Antoni, L. Chop-Chop: A Programmable Framework for Semantically Constraining the Output of Language Models. Proc. ACM Program. Lang., 10(POPL):1905–1932, 2026. doi: 10.1145/3776708. URL https://doi.org/10.1145/3776708.
- [28]Nie, W., Meng, Z., Zou, K., Lin, Z., Li, Z., Zheng, H., Jang, J.-S. R., and Zhang, H. Future Validity is the Missing Statistic: From Impossibility to Φ-Estimation for Grammar-Faithful Speculative Decoding. CoRR, abs/2605.07698, 2026. doi: 10.48550/ARXIV.2605.07698. URL https://doi.org/10.48550/ARXIV.2605.07698.
- [29]Oliaro, G., Jia, Z., Campos, D. F., and Qiao, A. SuffixDecoding: Extreme Speculative Decoding for Emerging AI Applications. In Belgrave, D., Zhang, C., Montoya, L. N., Lin, H.-T., Pascan u, R., Koniusz, P., Ghassemi, M., Chen, N., Ruíz, I. V. M., and Loaiza-Bonilla, A. (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2025, NeurIPS 2025, San Diego, CA, USA, December 2-7, 2025 / Mexico City, Mexico, November 30 - December 5, 2025, 2025. URL http://papers.nips.cc/paper_files/paper/2025/hash/b7aea253ab34a773967f1e4cdea9e4fb-Abstract-Conference.html.arxiv.org/abs/2411.04975
- [30]Pan, L., Albalak, A., Wang, X., and Wang, W. Y. Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning. In Bouamor, H., Pino, J., and Bali, K. (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, Singapore, December 6-10, 2023, volume EMNLP 2023 of Findings of ACL, pp. 3806–3824. Association for Computational Linguistics, 2023. doi: 10.18653/V1/2023.FINDINGS-EMNLP.248. URL https://doi.org/10.18653/V1/2023.FINDINGS-EMNLP.248.
- [31]Park, K., Wang, J., Berg-Kirkpatrick, T., Polikarpova, N., and D’Antoni, L. Grammar-Aligned Decoding. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J. M., and Zhang, C. (eds.), Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. URL http://papers.nips.cc/paper_files/paper/2024/hash/2bdc2267c3d7d01523ee217aca0754f3-Abstract-Conference.html.arxiv.org/abs/2405.21047
- [32]Patil, S. G., Mao, H., Yan, F., Ji, C. C.-J., Suresh, V., Stoica, I., and Gonzalez, J. E. The Berkeley Function Calling Leaderboard (BFCL): From Tool Use to Agentic Evaluation of Large Language Models. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., Berkenkamp, F., Maharaj, T., Wagstaff, K., and Zhu, J. (eds.), Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025, volume 267 of Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025. URL https://proceedings.mlr.press/v267/patil25a.html.
- [33]Poesia, G., Polozov, A., Le, V., Tiwari, A., Soares, G., Meek, C., and Gulwani, S. Synchromesh: Reliable Code Generation from Pre-trained Language Models. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openreview.net/forum?id=KmtVD97J43e.arxiv.org/abs/2201.11227
- [34]Qwen Team. Qwen3 Technical Report. CoRR, abs/2505.09388, 2025. doi: 10.48550/ARXIV.2505.09388. URL https://doi.org/10.48550/ARXIV.2505.09388.
- [35]Reddy, A., Walker, T. T., Ide, J. S., and Bedi, A. S. Draft-Conditioned Constrained Decoding for Structured Generation in LLMs. CoRR, abs/2603.03305, 2026. doi: 10.48550/ARXIV.2603.03305. URL https://doi.org/10.48550/ARXIV.2603.03305.
- [36]Régin, J.-C. A Filtering Algorithm for Constraints of Difference in CSPs. In Hayes-Roth, B. and Korf, R. E. (eds.), Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31 - August 4, 1994, Volume 1, pp. 362–367. AAAI Press / The MIT Press, 1994.
- [37]Scholak, T., Schucher, N., and Bahdanau, D. PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models. In Moens, M.-F., Huang, X., Specia, L., and tau Yih, S. W. (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pp. 9895–9901. Association for Computational Linguistics, 2021. doi: 10.18653/V1/2021.EMNLP-MAIN.779. URL https://doi.org/10.18653/V1/2021.EMNLP-MAIN.779.
- [40]Sun, Z., Suresh, A. T., Ro, J. H., Beirami, A., Jain, H., and Yu, F. X. SpecTr: Fast Speculative Decoding via Optimal Transport. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL https://papers.nips.cc/paper_files/paper/2023/hash/6034a661584af6c28fd97a6f23e56c0a-Abstract-Conference.html.arxiv.org/abs/2310.15141
- [41]Wang, X., Miao, Z., Zhu, Y., Shen, H., Wan, Z., Yang, F., and Zhang, M. AgentSpec: Speculative Decoding for Batch Inference of LLM Agents. CoRR, abs/2608.24004, 2026. doi: 10.48550/ARXIV.2608.24004. URL https://doi.org/10.48550/ARXIV.2608.24004.
- [42]Willard, B. T. and Louf, R. Efficient Guided Generation for Large Language Models. CoRR, abs/2307.09702, 2023. doi: 10.48550/ARXIV.2307.09702. URL https://doi.org/10.48550/ARXIV.2307.09702.
- [44]Yao, S., Shinn, N., Razavi, P., and Narasimhan, K. τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains. CoRR, abs/2406.12045, 2024. doi: 10.48550/ARXIV.2406.12045. URL https://doi.org/10.48550/ARXIV.2406.12045.
- [45]Zhang, R. H., Dey, S., Mishra, A., Wu, H., Li, B., and Zhang, R. Batch Speculative Decoding Done Right. CoRR, abs/2510.22876, 2025. doi: 10.48550/ARXIV.2510.22876. URL https://doi.org/10.48550/ARXIV.2510.22876.
- [46]Zhang, S., Xu, R., Li, H., Yu, Q., Zhang, Y., Xia, C., Feng, X., Wang, C., Cui, H., and Zhao, J. Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments. CoRR, abs/2607.18357, 2026. doi: 10.48550/ARXIV.2607.18357. URL https://doi.org/10.48550/ARXIV.2607.18357.
- [47]Zheng, H. S., Mishra, S., Zhang, H., Chen, X., Chen, M., Nova, A., Hou, L., Cheng, H.-T., Le, Q. V., Chi, E. H., and Zhou, D. NATURAL PLAN: Benchmarking LLMs on Natural Language Planning. CoRR, abs/2406.04520, 2024a. doi: 10.48550/ARXIV.2406.04520. URL https://doi.org/10.48550/ARXIV.2406.04520.
- [48]Zheng, L., Yin, L., Xie, Z., Sun, C., Huang, J., Yu, C. H., Cao, S., Kozyrakis, C., Stoica, I., Gonzalez, J. E., Barrett, C. W., and Sheng, Y. SGLang: Efficient Execution of Structured Language Model Programs. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J. M., and Grabner, D. C. (eds.), Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024b. URL http://papers.nips.cc/paper_files/paper/2024/hash/724be4472168f31ba1c9ac630f15dec8-Abstract-Conference.html.arxiv.org/abs/2312.07104




