{"id":"e0b96eaf-ea1c-4d7a-92c9-0be79cb51228","arxiv_id":"2601.04426","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"XGrammar-2 makes dynamic, tag-triggered structured generation fast by dispatching to cached substructure grammars with an Earley-based adaptive token-mask cache.","lead":"XGrammar-2 is a new engine that lets LLMs switch output structure mid-response based on tag tokens, reusing cached substructure masks so per-request grammar compilation nearly disappears. It reports over 6x faster grammar compilation than prior engines and under 6% end-to-end latency overhead in LLM serving.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3's min<t branch over-accepts repetitions (up to 2·max−t), directly threatening the §4.5 100% schema-validity claim.","rationale":"The paper's central contribution is efficiency for dynamic structured generation, but that contribution is only meaningful if outputs remain schema-valid. Section 4.5 stakes correctness on the optimizations preserving semantics. Algorithm 3, as written, does not preserve semantics for the common case min < t: its union of expansions over-accepts beyond max. This is a concrete, load-bearing flaw in the correctness argument, not a stylistic or reproducibility complaint. The reader's weakest assumption correctly identified repetition compression as a key unproven assumption, but stopped short of noticing the algorithm's explicit bounds error. I therefore partially agree with the reader. If the bug is real (and no code artifact is provided to check), the paper's central claim of 100% validity is false; if it is a typographical error in the pseudo-code, the claim may survive pending a corrected algorithm and a proof. Because either resolution is possible and the efficiency experiments may still hold, a CONDITIONAL verdict is appropriate: the authors must correct or justify Algorithm 3, provide a formal or brute-force equivalence check for repetition compression, and ideally release the code. This does not change the reader's overall CONDITIONAL recommendation but sharpens the reason for it and adds a decisive test.","tokens_in":18354,"tokens_out":6627,"duration_ms":70253,"concrete_test":"Instantiate Algorithm 3 with min=2, max=5, t=3 and build the resulting FSM/grammar. Enumerate all accepted strings for repetition counts k=0..7. If a string with k=6 or k=7 is accepted, the compression is semantically wrong and the §4.5 claim is false. If the implementation instead rejects k>5, identify how the pseudo-code should be corrected (e.g., Repeat(t,t) rather than Repeat(t,max)) and re-run the same check. For extra confidence, run the identical test against the actual XGrammar-2 codebase once released.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 4.5 asserts without proof that XGrammar-2 preserves XGrammar's constraint semantics, yielding '100% schema-valid tool-call arguments.' This rests on the repetition state compression of §3.6/Algorithm 3. As printed, Algorithm 3's branch for min < t is incorrect: it forms choice = Concat(Repeat(t, max), Expand(0, max−t)), whose repetition count ranges over [t, max] + [0, max−t] = [t, 2max−t]. Union with Expand(min, t) then accepts counts in [min, 2max−t] instead of [min, max]. Concretely, for R{2,5} with threshold t=3, the compressed expression accepts 6 and 7 repetitions, violating the schema bound. The runtime k-check described in §3.6 cannot repair this because the cache constructed from the over-approximating compressed grammar will treat a token that starts a 7th repetition as accepted; even if a separate runtime bound check were added, the paper neither describes nor proves one. The §4.5 'by construction' correctness argument therefore fails as written: this is not merely an unproven equivalence but a concrete counterexample to the stated algorithm. Appendix C's hash-consistency caveat is secondary—it mainly affects cache reuse (efficiency), not soundness. The central claim of a correct, near-zero-overhead dynamic structured generation engine depends on this compression step, and the paper provides no formal proof, no machine-checked verification, and no released artifact to confirm the shipped implementation avoids the bug.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents XGrammar-2, a structured generation engine targeting dynamic agentic LLM workloads. It introduces TagDispatch for intra-request tag-triggered structure switching, a cross-grammar cache for inter-request substructure reuse, an Earley-based adaptive token mask cache, JIT compilation, and repetition state compression. The experiments claim over 6x faster compilation than prior engines and near-zero end-to-end overhead in LLM serving systems.","tokens_in":18715,"tokens_out":6927,"duration_ms":65599,"significance":"The problem is timely and practically important: dynamic tool calling and response protocols are central to modern agentic LLM serving. The proposed design—especially the TagDispatch abstraction and cross-grammar cache—is plausible and would be a meaningful contribution if the efficiency and correctness claims hold. The paper also reports integration with SGLang and vLLM, which increases the potential impact. However, the correctness of the core repetition compression algorithm is not established, and as printed the algorithm is incorrect, which undermines the central 100% schema-validity claim. The end-to-end evaluation also contains baseline-comparison issues that need to be addressed.","major_comments":[{"comment":"Algorithm 3's min<t branch is incorrect. For R{min,max} with min<t<max, the expression Concat(Repeat(t,max), Expand(0,max-t)) accepts repetition counts in [t, 2max-t]; the union with Expand(min,t) covers [min, 2max-t] rather than [min,max]. Concretely, for R{2,5} with t=3, the printed algorithm accepts 6 and 7 repetitions, violating the schema bound. This directly contradicts the §4.5 claim of 100% schema-valid tool-call arguments. The runtime k-check mentioned in §3.6 is not specified or proven to restore exactness; the cache built from the over-approximating expression can accept the token that starts a 7th repetition. Please correct the algorithm or provide a formal correctness proof, including a precise description and proof of any runtime bound check.","section":"3.6, Algorithm 3 (Appendix B)"},{"comment":"The comparison against llguidance is uninterpretable for two of the four models. The text reports that llguidance produces empty outputs for Qwen3-0.6B and induces language drift from English to other languages for Llama3.1-8B. For these models, the reported latency and throughput numbers are not measuring the same task as the other engines. The claim that 'XGrammar-2 shows a small latency and better compatibility' is not supported unless these cases are handled separately or excluded, or a valid llguidance fallback configuration is provided and evaluated.","section":"4.3, Figure 9"},{"comment":"The ablation shows that the full optimization stack yields a per-token mask generation time of 126.49 us, which is about 2.8x slower than the Earley baseline of 45.50 us. The abstract and text emphasize 'near-zero overhead,' but this is only demonstrated in end-to-end measurements where mask generation may be hidden by other latencies. Please provide an end-to-end overhead breakdown (e.g., time-to-first-token and per-token latency relative to unconstrained decoding) and discuss the discrepancy between the per-token mask time and the near-zero-overhead claim.","section":"4.4, Table 4"},{"comment":"The cross-grammar cache relies on the claim that if two FSMs have equal hash values, they must have the same structure. No collision analysis or formal proof is given, and Appendix C concedes inconsistent hashes for non-DFA or duplicated FSMs. If a hash collision ever occurs, the reused token mask cache could accept invalid tokens or reject valid ones, which would again violate the §4.5 correctness guarantee. Please state the precise invariant ('equal hash implies isomorphic automaton') and prove it for the supported grammar subset, or provide strong empirical validation on the evaluated grammar classes.","section":"3.3, Appendix C"}],"minor_comments":[{"comment":"Typo: 'SgLang' should be 'SGLang'. Also, the model name 'Qwen-0.6B' is inconsistent with 'Qwen3-0.6B' used in the text.","section":"4.3"},{"comment":"The bar chart would be easier to read with numerical labels on each bar or a separate table, since the y-axis values in the text are dense and hard to map.","section":"Figure 9"},{"comment":"In the static setting, all requests use the same 5/20/50 tools, so the full-structure reuse rate should be 100%. The reported 99.0% needs an explanation (e.g., measurement noise or a small fraction of mismatched metadata).","section":"4.1, Table 1"},{"comment":"The correctness claim is stated as 'by construction' but no proof or machine-checked verification is provided. A formal theorem would be valuable, especially given the complexity of the compression and caching logic.","section":"4.5"},{"comment":"The paper says the engine is 'open-source' but does not provide a repository URL. Please include an artifact link; this is important for reproducibility, especially since no error bars or repeated runs are reported for the efficiency numbers.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The repetition compression bug is concrete and load-bearing; if the authors correct it and supply a rigorous correctness proof, the paper could become acceptable. The llguidance baseline issue in §4.3 must also be fixed. The absence of an artifact link and the lack of error bars make independent verification harder, but they are not, by themselves, grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the dynamic-dispatch and cross-grammar reuse story is genuinely useful, and the measured speedups on compilation are impressive. But Algorithm 3 has a concrete bug that breaks the paper's headline correctness guarantee, and there is no artifact to check whether the implementation avoids it.\n\nWhat's new: TagDispatch is a clean way to express tag-triggered structure switching, and the cross-grammar cache addresses a real pain point. JIT cache compilation is a reasonable engineering choice. The evaluation on BFCL and CONFETTI is a step up from microbenchmarks alone; the end-to-end latency and throughput tables tell a consistent story.\n\nWhere it falls down: Section 4.5 asserts 'by construction' that XGrammar-2 preserves XGrammar's semantics, so both achieve 100% schema-valid arguments. That construction is wrong as written. Algorithm 3's min < t branch produces a choice expression that accepts up to 2*max - t repetitions instead of max. Example: R{2,5} with threshold t=3 over-accepts 6 and 7. The runtime k-check mentioned in §3.6 is not specified or proven to catch this, and the cache built from the over-approximation will treat tokens that start the 7th repetition as valid. So the strongest claim in the paper — zero overhead with perfect validity — is unsupported. That is not a minor caveat; it's the central safety property of constrained decoding.\n\nOther issues are less severe. The llguidance baseline fails on two of four end-to-end models, making those comparisons hard to interpret. No error bars are reported. The ablation shows JIT alone raises per-token mask time 15.9x; the full system is 2.8x slower than the Earley baseline per token, though preprocessing drops 900x, so the tradeoff is defensible but should be stated. No code artifact or commit hash is provided despite the 'open-source' claim, so I can't check whether the shipped implementation has the bug.\n\nThe citation pattern and related work are fine; building on XGrammar is natural. The paper is a serious systems contribution with a fixable soundness problem. I would not cite it as a correctness guarantee until the algorithm is corrected and validated. If a revised version ships a corrected compression proof (or a direct property test on repetition-heavy schemas) and an artifact, this could be an important engine.\n\nRecommendation: worth an editor's time — send to peer review, but the reviewers should be asked to check the repetition-compression semantics carefully. It should not be accepted in its current form.","headline":"Good systems idea with a real efficiency win, but the repetition-compression algorithm as printed over-accepts, so the 100% schema-validity claim doesn't hold up.","tokens_in":19216,"tokens_out":3148,"would_cite":false,"duration_ms":30324,"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":"XGrammar-2 claims that dynamic structured generation for LLM agents—where the required output format changes across requests and within a request—can be served with over 6× faster grammar compilation than prior engines and near-zero end-to-","keywords":["structured generation","constrained decoding","tool calling","agentic LLMs","Earley parser","grammar caching","tag dispatch","just-in-time compilation"],"falsifier":"Build a grammar containing a repetition R{20,1024} and decode a large corpus through the compressed engine, checking whether any emitted string has fewer than 20 or more than 1024 repetitions; or construct two non-deterministic FSMs that hash to the same value but accept different languages, then observe whether a cache hit ever yields a token mask that the original grammar would reject. Either outcome would refute the 100% schema-validity claim and the semantic-preservation assumption.","tokens_in":18227,"feed_emoji":"⚙️","tokens_out":7117,"duration_ms":62180,"temperature":0.7,"pith_summary":"The paper argues that agentic LLM workloads—tool calling, response protocols—demand structure that changes per request and per token, and that existing constrained-decoding engines, which precompile a fixed grammar, pay prohibitive costs when the grammar is dynamic. To fix this, XGrammar-2 introduces TagDispatch, a grammar construct that switches the active constraint when a tag like a tool name appears, and a Cross-Grammar Cache that reuses token-mask computation across grammars that share substructures. The engine further uses an Earley-parser-based adaptive cache, just-in-time compilation, and repetition state compression. The central claim, backed by experiments, is that dynamic grammars compile over 6× faster and add near-zero end-to-end latency, making per-request and per-call structure enforcement practical at scale. A sympathetic reader would care because this is what makes tool calling with dozens or hundreds of tools feasible in production serving.","feed_headline":"6x faster dynamic grammar compilation for agent tool calling","feed_subtitle":"Tag-triggered switching and cross-grammar cache reuse cut compile time and per-token latency.","key_machinery":"The load-bearing pieces are the Earley-parser-based adaptive token mask cache, the Cross-Grammar Cache with its hierarchical FSM hashing, and TagDispatch. The adaptive cache stores token validity only for scannable Earley states—states whose next symbol is a terminal—avoiding the exponential state blow-up of pushdown-automaton caches. The Cross-Grammar Cache assigns consistent hash values to FSMs, so when two grammars share a substructure (a JSON schema, a tool argument pattern), the cached accepted/rejected/uncertain token sets are reused across requests, with lookahead mismatches repaired by rechecking only the uncertain tokens. TagDispatch is an EBNF intrinsic that uses an Aho–Corasick au","core_discovery":"The central discovery is that dynamic structured generation can be made nearly free by changing what gets cached. Instead of compiling the whole grammar ahead of time and caching token masks for every parser state, the engine caches at the substructure level, identifying reusable FSM sub-automata through a hierarchical hashing algorithm, and compiles only the masks encountered at runtime via just-in-time compilation. TagDispatch expresses intra-request switching as a first-class EBNF construct, so a tag such as '<function=get_weather>' routes decoding into the corresponding JSON-schema grammar and then back to free text. The engine replaces the pushdown-automaton state representation with an","pith_inferences":["If the semantic-preservation assumptions hold, the same architecture could extend to other dynamic structures—multi-step code generation, changing SQL schemas, or chained tool protocols—where the active grammar is not known until generation time.","The hierarchical hash-based substructure reuse suggests a fingerprinting approach that serving systems could use to version grammars incrementally, avoiding recompilation when only a subset of tools or fields change.","The configurable just-in-time tradeoff between prefill-time and decode-time compilation could be tuned automatically per hardware backend or per workload, a knob the paper leaves as a fixed constant.","A natural testable extension is applying repetition-state compression to streaming or incremental validation of long structured outputs, where the compressed state could serve as a compact representation of the current constraint frontier."],"forward_implications":["Dynamic tool calling with dozens or hundreds of tools becomes practical: grammar construction drops from seconds to roughly 10 ms, reducing time-to-first-token in agentic serving.","End-to-end latency with constraint enforcement stays within about 6% of unconstrained decoding, so output reliability gains no longer cost throughput.","Cross-grammar cache reuse means even when entire grammars differ across requests (near zero full-structure reuse), roughly half the substructure computation can be reused, making per-request compilation affordable.","TagDispatch makes intra-request structure switching expressible and compact, avoiding the rapid growth of hand-translated EBNF dispatchers as the number of tags increases.","The combination of just-in-time compilation and repetition compression cuts preprocessing time by over three orders of magnitude on JSON schema benchmarks while keeping per-token mask generation under about 130 microseconds."],"fun_headline_variants":["TagDispatch: switch grammar mid-request, zero recompile","Cross-grammar cache reuse: near-zero overhead for agent calls","Dynamic grammar with near-zero overhead: 6x faster compile","Switch grammar on the fly with TagDispatch","6x faster dynamic grammar for agent tool calling"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The engine's correctness rests on the assumption that its compressed repetition states and hash-based cache reuse accept exactly the same set of token sequences as the original grammar—so that no schema-invalid token can ever be produced.","fun_headline_variants_meta":{"raw":{"variants":["TagDispatch: switch grammar mid-request, zero recompile","Cross-grammar cache reuse: near-zero overhead for agent calls","Dynamic grammar with near-zero overhead: 6x faster compile","Switch grammar on the fly with TagDispatch","6x faster dynamic grammar for agent tool calling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001127,"raw_usage":{"total_tokens":4488,"prompt_tokens":677,"completion_tokens":3811,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":421,"completion_tokens_details":{"reasoning_tokens":3731}},"tokens_in":421,"tokens_out":3811,"duration_ms":23559,"temperature":1.0,"reasoning_tokens":3731,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T12:02:32.546581+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a grammar containing a repetition R{20,1024} and decode a large corpus through the compressed engine, checking whether any emitted string has fewer than 20 or more than 1024 repetitions; or construct two non-deterministic FSMs that hash to the same value but accept different languages, then observe whether a cache hit ever yields a token mask that the original grammar would reject. Either outcome would refute the 100% schema-validity claim and the semantic-preservation assumption.","supporting_citations":[],"review_version":1}