{"id":"186e5317-1cde-4997-83ae-2cb9b9214ba7","arxiv_id":"2507.16768","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A structured decoding engine that precompiles static grammar templates and uses context-free operators with mask caching to cut time-to-first-token overhead by up to 250x versus XGrammar.","lead":"WGrammar is a new engine for structured decoding that precompiles fixed grammar templates offline and instantiates variable parts at runtime, using finite-state operators instead of pushdown automata to track generation state. It reports large latency reductions over XGrammar, but the headline 250x figure measures overhead rather than total time and depends on task-specific prior knowledge.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The headline 250x TTFT claim may stem from counting WGrammar's offline template work as free while charging XGrammar and Outlines for per-request grammar compilation; a warm-cache or precompiled baseline is needed before the central advantage is accepted.","rationale":"The reader's weakest-assumption analysis focuses on manual template design as a usability limitation. I agree that this is relevant, but the more load-bearing issue is benchmark fairness: the central quantitative claim is an overhead ratio computed inside an asymmetric cost window. WGrammar is allowed to move grammar construction offline into the structure factory, while the baselines appear to pay per-request compilation in the measured TTFT. Both systems can amortize compilation when structures recur, so the comparison must either give XGrammar the same precompilation opportunity or report the realistic amortized cost. This concern is concrete and testable because the released code includes templates and benchmarks. The paper has independent supporting evidence, including a public repository, a well-defined decomposition into static and dynamic constraints, and a clear FSM-based mask-caching design, so I do not see grounds for rejection. However, the headline 250x claim should not be accepted as a general engine-level speedup until the precompilation asymmetry is controlled. The secondary Reference-Lookup inconsistency additionally cautions against over-generalizing the TPOT advantage. These are addressable experimental conditions rather than fundamental flaws, so CONDITIONAL remains the appropriate verdict.","tokens_in":9460,"tokens_out":6624,"duration_ms":75350,"concrete_test":"Re-run the Outline-Generation TTFT measurement from Section 4.2 under three conditions: (1) XGrammar with a grammar object compiled once and reused for every request, with its compiled-grammar cache warmed before timing; (2) WGrammar with its structure factory; (3) WGrammar(online). Report per-request TTFT overhead and the XGrammar/WGrammar ratio. If the ratio falls to roughly 1x or to the 5.55x WGrammar(online) level, the 250x claim is dominated by the allowed precompilation asymmetry rather than WGrammar's runtime design; if it stays near 251x, the engine-level claim is supported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 4.2 defines TTFT overhead as TTFT minus unstructured TTFT (Table 1), and the 250x/251x claim is computed on that overhead. The comparison is asymmetric: WGrammar's structure factory is compiled once offline from structure.txt (Section 3.1) and therefore appears only in backend setup, while XGrammar and Outlines are measured with per-request grammar construction (Section 4.1). If the Outline-Generation grammar is reused across requests, XGrammar's persistent compiled-grammar cache should remove most of the 2,747.83ms per-request compilation cost, shrinking the 251x overhead ratio toward the 5.55x gap that WGrammar(online) already achieves without any offline template. The paper does not report cache warm-up, grammar reuse frequency, or whether an XGrammar precompiled grammar was used. Without that control, the headline speedup conflates engine efficiency with the task-specific precompilation granted only to WGrammar. A secondary consistency issue: on Reference-Lookup, WGrammar(online) beats WGrammar on both TTFT overhead (4.17 vs 4.70ms) and TPOT overhead (0.42 vs 0.50ms), so the claimed benefit of offline structural priors is not uniform even in the paper's own data.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper presents WGrammar, a structured decoding engine that leverages domain-specific prior knowledge to reduce the overhead of grammar compilation, state tracking, and mask creation during LLM generation. The core idea is to decompose output constraints into static templates precompiled offline and dynamic arguments instantiated at runtime, using compositional operators (Wait, Write, IfElse, Sequence, DoWhile) that are context-free and support global mask caching. The authors evaluate WGrammar, WGrammar(online), XGrammar, and Outlines on three datasets: Outline-Generation, Reference-Lookup, and JSON-mode-eval. They report up to 251x reduction in TTFT overhead compared to XGrammar (Table 1) and end-to-end TTFT speedups of 2.02-7.80x (Figure 5), along with a per-stage overhead breakdown (Figure 6). The code, templates, and datasets are publicly released.","tokens_in":9762,"tokens_out":5866,"duration_ms":54494,"significance":"If the reported results hold, the paper makes a useful contribution by showing that domain-aware offline precompilation can substantially reduce structured decoding overhead for production workloads with stable output structures. The decomposition into static and dynamic components and the use of context-free operators for regular formats are sensible design choices, and the global mask caching is a clean optimization. The release of code, templates, and datasets is a strength, as it enables reproducible comparisons. However, the significance is tempered by the fact that optimal performance requires users to manually design offline templates (acknowledged in Section 6), and the method is restricted to regular (non-context-free) formats, so it does not replace general CFG-based engines. The headline 250x speedup is an overhead ratio, not an end-to-end speedup, and the comparison with XGrammar may be unfair because WGrammar's offline compilation is amortized whereas XGrammar's per-request compilation is not. The findings are nonetheless potentially valuable for practitioners with recurring output formats.","major_comments":[{"comment":"The headline '250× speedup' is an overhead ratio, not an end-to-end speedup. The TTFT overhead is defined as the additional latency over unstructured decoding; the actual end-to-end TTFT speedup of WGrammar over XGrammar on Outline-Generation is 6.10× (Figure 5a), not 250×. The abstract and the contribution list (Section 1) state 'speedup' without this qualification. Please report both overhead reduction and end-to-end speedup, and rephrase the abstract to avoid misleading readers.","section":"Section 4.2, Table 1, Figure 5"},{"comment":"The comparison against XGrammar is asymmetric with respect to grammar compilation. WGrammar's structure factory is compiled once offline from structure.txt during backend setup, so its compilation cost is amortized across all requests. In contrast, the XGrammar measurements appear to include per-request grammar compilation: Figure 6a attributes 2,715.49 ms of XGrammar's time to grammar compilation. XGrammar supports persistent compiled-grammar reuse; the paper should include a warm-cache or precompiled XGrammar baseline. Without that control, the claimed TTFT advantage conflates offline precompilation with engine efficiency.","section":"Section 3.1 and 4.1, Figure 6"},{"comment":"On Reference-Lookup, WGrammar(online) outperforms WGrammar in both TTFT overhead (4.17 ms vs. 4.70 ms) and TPOT overhead (0.42 ms vs. 0.50 ms). This contradicts the general claim that domain-aware offline precompilation improves performance. The paper should either explain this anomaly or scope the claim to tasks where the offline structure is sufficiently complex to benefit from precompilation.","section":"Table 1, Reference-Lookup rows"}],"minor_comments":[{"comment":"The statement 'structured decoding introduces over 120,000 ms of TTFT latency with Outlines' should say 'overhead' or 'additional latency', since 120,234.58 ms is the overhead shown in Table 1, not the total TTFT.","section":"Section 1"},{"comment":"The phrase 'WGrammar employ different parsing methods' should be 'employs'; also 'the regular expressions syntax-based priors' is awkward and should be rephrased.","section":"Section 3.1"},{"comment":"The dataset names are inconsistent: 'Outlines-Generation' in Table 1 versus 'Outline-Generation' in the text and figures; unify the naming.","section":"Table 1"},{"comment":"No error bars, confidence intervals, or statistical tests are reported for the latency measurements. Given that the headline claim is a large speedup, repeating the experiments multiple times and reporting variance would strengthen the results.","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important practical problem and releases code, which is commendable. However, the headline claim is overstated and the baseline comparison needs to be made fair. I believe the paper can be made suitable for publication after these revisions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is a genuine engineering contribution with a headline number that oversells it. The static/dynamic decomposition of structured-decoding constraints, plus global mask caching via context-free operators, is a real idea that can speed up generation when output formats are stable. The released code is a plus. But the 250x claim is computed on TTFT overhead, not total latency, and the benchmark gives WGrammar's offline template work for free while charging XGrammar and Outlines for per-request grammar compilation. A warm-cache or precompiled XGrammar baseline would likely shrink that number to something closer to the 5-6x end-to-end gap on the hardest dataset. That is still a useful gain, but it is not an order-of-magnitude revolution.\n\nWhat the paper does well: it breaks down the overhead into grammar compilation, state tracking, and mask creation, and shows where the wins come from. The WGrammar(online) variant, relying only on regex priors, is a good control: it beats XGrammar on TTFT overhead even without offline templates, which suggests the operator design and mask caching carry real weight. The section on the Wait/Write/IfElse/DoWhile composition is clear and the regex-to-operator example is concrete.\n\nSoft spots: the missing warm-cache control is the main one. The paper also does not report error bars or statistical tests, and it skips LMFE, which is the most direct competitor for JSON-mode workloads. There is also an internal inconsistency: on Reference-Lookup, WGrammar(online) beats WGrammar on both TTFT and TPOT overhead, so the claimed benefit of offline structural priors is not uniform even in the paper's own data. That should be explained. The limitations section honestly admits the manual template design cost and the non-greedy regex semantics, which is good to see.\n\nVerdict: worth a serious referee. The idea is sound, the implementation is real, and the evaluation flaws are addressable. The authors should be pushed to rerun baselines with precompiled grammars, add variance estimates, and either reconcile the Reference-Lookup anomaly or soften the claim. I'd take this as a conditional accept with major revisions.\n\nFor you: if you work on inference engines or structured generation, cite the static/dynamic decomposition and mask caching. Take the 250x with a grain of salt.","headline":"Useful engineering contribution with a real static/dynamic decomposition and mask caching, but the 250x headline is inflated by asymmetric benchmarking; the honest gain is a solid constant-factor improvement.","tokens_in":10247,"tokens_out":1981,"would_cite":true,"duration_ms":20224,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Splitting output structure from runtime arguments makes LLM format control over 250x faster.","keywords":["structured decoding","grammar-guided generation","finite state machine","mask caching","context-free grammar","LLM inference","prior knowledge","EBNF template"],"falsifier":"Take a workload whose output schema is a long, flat, fixed JSON object with many keys but no shared template. If WGrammar's TTFT overhead versus XGrammar collapses to the 5.5x online-only range once the structure factory cannot describe the schema, that would show the speedup is a property of precompilation, not of the operator algebra itself. Concretely, benchmark a fresh random JSON schema per request with no structure.txt entry and compare WGrammar's TTFT overhead to the advertised 250x figure.","tokens_in":9275,"feed_emoji":"⚡","tokens_out":4384,"duration_ms":41331,"temperature":0.7,"pith_summary":"Structured decoding forces an LLM to emit valid JSON, HTML, or other formats, but each request normally pays for grammar compilation, pushdown-automaton state tracking, and token-mask construction. WGrammar argues that most production formats are largely stable: the skeleton is known in advance and only a few arguments change per request. The paper proposes decomposing constraints into static templates compiled offline and dynamic arguments instantiated at runtime, then executing them with small context-free operators (Wait, Write, IfElse, DoWhile) instead of a PDA. On three workloads, this cuts time-to-first-token overhead by over 250x versus XGrammar and up to 2.33x per output token. The payoff would be that format-constrained generation becomes cheap enough for latency-sensitive serving.","feed_headline":"Stable output templates make LLM format control up to 250x faster","feed_subtitle":"WGrammar precompiles fixed structure offline and caches masks, slashing per-request decoding cost.","key_machinery":"The load-bearing object is the structure factory plus the Wait/Write operator algebra. Wait is a conditional checkpoint that optionally runs a nested body when a token arrives; Write emits a fixed token sequence. Sequence, IfElse (built on a specialized Wait with true/false token sets), and DoWhile compose these into regular-format recognizers, replacing the pushdown automaton of CFG-based engines. The context-free nature of these operators is what enables global mask caching, and the offline template defers all expensive parsing to startup.","core_discovery":"The central claim is that exploiting domain prior knowledge, the fixed skeleton of an output format, can remove almost all per-request decoding overhead. WGrammar precompiles a 'structure factory' from an EBNF template containing named blocks like SECTION_START; at runtime a frontend parser combines that factory with the request's arguments to build a parse tree of operators, each a tiny finite state machine. Because these operators only depend on the current token set, they are context-free, so masks can be cached globally across requests and decoding steps. The paper reports grammar-compilation overhead reduced 175x versus XGrammar, state tracking 7-8x faster despite being Python versus C++, and end-to-end TTFT overhead improved 225x on Outline-Generation and up to 250x overall.","pith_inferences":["Template authoring could itself be automated by mining successful request/response pairs; the manual-DSL requirement is an engineering constraint, not a limit of the decomposition idea.","Global mask caching might extend to other context-free fragments beyond the listed operators, potentially shrinking the gap between the online and offline variants.","The non-greedy regex semantics noted in Section 6 may change the effective grammar for user-written patterns; a checklist of constructs where greedy and non-greedy behavior differ would help adopters predict correctness.","Serving systems with request batching could be redesigned around the structure factory, sharing one mask-factory across many concurrent requests of the same format."],"forward_implications":["For workloads with stable output shapes, structured decoding's time-to-first-token overhead becomes a few milliseconds, comparable to unconstrained decoding.","Per-token overhead stops scaling with grammar complexity, since transitions are constant-time and masks are cached globally.","Format-constrained generation becomes viable for interactive and agentic pipelines where current overheads are prohibitive.","Even with no task-specific template, the regular-expression-only online variant still beats XGrammar by roughly 5.5x on TTFT overhead, showing the operator design itself contributes beyond the offline cache."],"supporting_citations":[{"why":"XGrammar is the primary baseline whose PDA-based per-request compilation sets the TTFT and TPOT overhead numbers WGrammar must beat.","marker":"[3]"},{"why":"Outlines introduced state-machine guided generation and supplies the other baseline's overhead measurements.","marker":"[11]"},{"why":"The Earley algorithm is used for offline template parsing, whose O(n^3) cost is amortized at setup.","marker":"[4]"},{"why":"The LALR(1) algorithm is used for online request parsing, giving O(n) runtime parsing.","marker":"[2]"},{"why":"EBNF is the notation in which offline format templates are written.","marker":"[12]"},{"why":"The JSON-mode-eval dataset provides one of the three benchmark workloads.","marker":"[8]"},{"why":"vLLM is the inference engine into which WGrammar is integrated for end-to-end measurements.","marker":"[7]"},{"why":"Qwen2.5 models are used across the three evaluation datasets.","marker":"[14]"}],"fun_headline_variants":["250x faster structured decoding via precompiled templates","Precompiled structure slashes LLM decoding cost 250x","Prior structure knowledge drives 250x LLM decoding speedup","WGrammar: precompiled templates give LLM formats 250x speedup","Skipping grammar compilation yields 250x faster LLM output"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result rests on the user supplying an offline template that captures the request's output structure; requests that fall outside the precompiled structure factory drop back to slower online parsing, and the headline 250x speedup does not apply to them.","fun_headline_variants_meta":{"raw":{"variants":["250x faster structured decoding via precompiled templates","Precompiled structure slashes LLM decoding cost 250x","Prior structure knowledge drives 250x LLM decoding speedup","WGrammar: precompiled templates give LLM formats 250x speedup","Skipping grammar compilation yields 250x faster LLM output"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000939,"raw_usage":{"total_tokens":3969,"prompt_tokens":853,"completion_tokens":3116,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":3026}},"tokens_in":469,"tokens_out":3116,"duration_ms":24878,"temperature":1.0,"reasoning_tokens":3026,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:01:21.748517+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a workload whose output schema is a long, flat, fixed JSON object with many keys but no shared template. If WGrammar's TTFT overhead versus XGrammar collapses to the 5.5x online-only range once the structure factory cannot describe the schema, that would show the speedup is a property of precompilation, not of the operator algebra itself. Concretely, benchmark a fresh random JSON schema per request with no structure.txt entry and compare WGrammar's TTFT overhead to the advertised 250x figure.","supporting_citations":[{"cited_title":"Willard and Rémi Louf","cited_arxiv_id":null,"evidence_quote":"Outlines introduced state-machine guided generation and supplies the other baseline's overhead measurements."},{"cited_title":"An efficient context-free parsing algorithm","cited_arxiv_id":null,"evidence_quote":"The Earley algorithm is used for offline template parsing, whose O(n^3) cost is amortized at setup."},{"cited_title":"Efficient computation of lalr(1) look-ahead sets","cited_arxiv_id":null,"evidence_quote":"The LALR(1) algorithm is used for online request parsing, giving O(n) runtime parsing."},{"cited_title":"What can we do about the unnecessary diversity of notation for syntactic definitions? Commun","cited_arxiv_id":null,"evidence_quote":"EBNF is the notation in which offline format templates are written."},{"cited_title":"json-mode-eval dataset, 2023","cited_arxiv_id":null,"evidence_quote":"The JSON-mode-eval dataset provides one of the three benchmark workloads."},{"cited_title":"Efficient memory management for large language model serving with pagedattention","cited_arxiv_id":null,"evidence_quote":"vLLM is the inference engine into which WGrammar is integrated for end-to-end measurements."}],"review_version":1}