acceptodds
Under review as a conference paper at ICLR 2027

Valid but Excluded: Token-Path Exclusions in Constrained Decoding for LLM Agents

Abstract

Constrained decoding can exclude the canonical token path of a valid JSON string even when its character parser accepts the complete text and the omitted token's characters at the reachable prefix. We distinguish these canonical-path exclusions from native-stack rejections caused by a narrower compiled language. On a constructed 192-case holdout, four stacks reject different path sets; two reject 48 paths each but disagree on 72. Within LM Format Enforcer, we identify and repair two token-enumeration rules without changing its character parser. The repair restores 16 excluded paths among 160 character-accepted strings while rejecting all 12 invalid controls. A separate BFCL-schema panel extends the result beyond the factorial fixtures: exclusions fall from 5/164 to 0/164 under each of two tokenizer files, on the same five cases. On 16 mask-selected generation cases, exact target copying rises from 0/16 to 16/16 for Qwen and 14/16 for Llama; 61 of 128 selected agent-state pairs also change their final-answer payloads. A larger mask audit finds that all 2,201,656 newly admitted token–prefix memberships pass the live character parser. Full-path CPU replay is substantially slower, even after a cache optimization. These results establish path restoration and selected output sensitivity, not deployment prevalence or end-to-end agent gains.

Primary area:
foundation or frontier models, including LLMs
Keywords:
constrained decoding, structured generation, tokenization, canonical-path exclusion, token masking, JSON Schema, LLM agents, function calling

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.20 over 5 reviews, above 2% of the others.
Reviewer_dTXLOpenReview ↗
Rating
2
Confidence
4(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates canonical token-path exclusions in constrained decoding, where valid JSON strings may have their canonical token sequences incorrectly rejected. The authors compare four existing constrained decoding backends and identify two implementation issues in the token-enumeration rules of LM Format Enforcer (LMFE) 0.11.3. The proposed repair restores excluded token paths and affects model outputs in selected cases.

Overall, the paper provides a relatively thorough technical investigation and experimental validation. However, I find that its main technical contribution is largely centered on repairing specific implementation issues in an existing decoding framework. Given that tokenizer alignment and valid-token masking have been investigated in prior work, I have concerns about the methodological novelty and generalizability of the contribution.

Critical strengths

S1. The paper clearly distinguishes character-parser acceptance, canonical token-path admissibility, and actual generation behavior. This distinction is useful for understanding different types of rejection in constrained decoding systems.

S2. The authors provide a careful diagnosis and validation of the LMFE implementation issues. The repair preserves the underlying character parser and is supported by holdout evaluations, component ablations, and additional validity checks.

S3. The paired generation experiments demonstrate that token-enumeration issues can affect actual model outputs rather than merely producing differences in static token masks.

Critical weaknesses

W1. Limited methodological novelty and generalizability.

The main technical contribution of this paper is the identification and repair of two specific token-enumeration issues in LMFE 0.11.3. However, tokenizer–grammar alignment and the incorrect masking of valid tokens have already been investigated in previous work, including DOMINO, SynCode, and GreatGramma. The proposed repair mainly relies on fallback trie traversal and modifications to cache usage, rather than introducing a new general-purpose constrained decoding algorithm.

Furthermore, although the paper compares four decoding backends, their observed path rejections do not necessarily share the same underlying cause. For example, XGrammar admits the three initial LMFE failure cases, while many of its other path rejections are attributed to its property-order compilation policy. The cross-backend experiments therefore do not establish that the specific LMFE enumeration defect is shared by other decoding frameworks.

Consequently, it remains unclear what generalizable methodological insight this work provides beyond identifying and correcting implementation issues in LMFE.

W2. Insufficient evidence of practical impact on realistic agent tasks.

Although the authors demonstrate that the repair restores canonical token paths and changes selected model outputs, the practical impact of these exclusions on realistic agent tasks remains unclear.

The 16 generation cases are selected based on identified path exclusions, making them appropriate for validating the repair but not for estimating the frequency of such failures during natural generation. The BFCL-schema evaluation identifies only five distinct affected strings, all of which have admissible alternative tokenizations under the original LMFE implementation.

Moreover, the output changes in the selected agent-state experiments are concentrated in final-answer payloads, and the repair is not evaluated through complete agent executions. Therefore, the paper does not yet establish whether the proposed repair leads to meaningful improvements in real-world agent reliability.

W3. Substantial runtime overhead of the repair.

Although the authors introduce additional caching to reduce the overhead, Appendix L.5 shows that the optimized v3 implementation still incurs approximately 5.85× and 15.05× the original CPU complete-path replay time for Qwen and Llama, respectively.

While these results do not directly represent GPU inference latency, the considerable overhead may limit the practical value of a repair targeting a relatively narrow set of implementation issues.

Questions for authors

Q1. Beyond the specific LMFE repair, what methodological or technical insights can be generalized to other constrained decoding systems? Could the authors further distinguish character-accepted token-path exclusions from compiled-language policy rejections in the other backends to clarify the generality of the investigated issue?

Q2. Could the authors provide further evidence of how frequently this issue affects naturally generated token paths, or clarify its potential impact on complete agent-task performance?

Q3. Could the substantial runtime overhead be reduced through a more selective token-checking mechanism?

5 comments
AuthorsOpenReview ↗

Generality beyond the LMFE patch, complete episodes, and v3 cost

Thank you for the feedback! "Original LMFE" = LM Format Enforcer 0.11.3 as released; "v2" = our repaired enumerator (Section 5.3); "v3" = v2 with a character-set cache whose masks equal v2's at all audited prefixes (App. L.4). New results: Appendix M of the revised PDF (pp. 37–42).

W1/Q1. Beyond an LMFE patch. Two LMFE rules interact (D.5, D.8): a free-text shortcut judges fragments without string context, and later traversal can miss those it rejects; a cache sizes backslash fragments by raw, not decoded, length. Of 160 character-accepted holdout paths, the original excludes 16, fallback-only 16, bypass-only 96 and both changes 0 (Table 11).

We do not claim a new decoding algorithm; DOMINO, SynCode and GreatGramma are prior work (Section 2, Table 21). What transfers is a two-way test, run with the backend's own parser: at a reachable prefix, an excluded token whose characters the parser accepts and that an enumeration-only change restores is an enumeration error; text the compiled language rejects is a policy. In other backends, XGrammar 0.1.27 rejects 48/192 paths with matched schema and text property orders and 192/192 with mismatched ones: a declared-order policy (Table 10). A post-submission CPU replay finds an order policy in llguidance 1.3.0: its 48 holdout rejections are two-field objects, admitted 48/48 when orders match and 0/48 when they differ (M.8, p. 40). Outlines Core's 72/192 remain unattributed; we have no evidence that another backend shares LMFE's defect.

W2/Q2. Complete episodes. 90 synthetic AgentGraph-v2 tasks, fixed before any repair outcome, ran under five Qwen3.5-0.8B checkpoints, which pick tool call or answer at each step. Success is an exact or numeric final-answer match (M.1–M.2, p. 37).

  • Validation (72 tasks, 360 task–checkpoint pairs): 282 → 316 correct; 34 gains on 23 tasks, 0 losses; design-weighted +9.4 pp, positive under each checkpoint.
  • Development (18 tasks, 90 pairs): 70 → 75; 5 gains on 3 tasks, 0 losses; +5.55 pp, two checkpoints unchanged.

No loss on this fixed panel is an observation, not a guarantee. As your W2 anticipated, the gain is in final answers, not tool execution: all 360 validation and 90 development pairs execute identical tool sequences; on 240 tool-required validation pairs, first tool and arguments match an enabled task-graph action in 200/240 and the complete plan in 156/240 under both (M.4, p. 38).

Natural generation (W2/Q2). At the "first divergence" (first token where the original and v2 generations differ), the original mask excludes v2's token although its parser accepts the added characters, in 270/360 validation and 70/90 development pairs. They come from 58 validation and 19 development prompt-prefix contexts, all at one original-mask state, so they show exposure on generated tokens, not a frequency. Every gain is in such a pair, yet most such pairs (236/270, 65/70) keep their label: co-occurrence, not mediation (M.3, p. 38).

BFCL V4: one Qwen3.5-2B checkpoint, used unchanged although its freeze record carries a failed training-gate marker (M.6, p. 39). Replaying its unmasked tokens through original LMFE finds such an exclusion in 186/345 supported tasks of a 384-task sample; all 545 captured generations took the final-answer route, so this one-checkpoint count is not a traffic estimate. Under free routing (the checkpoint picks call or answer), official scores rise 77/345 → 86/345 (10 gains, 1 loss; category-weighted +2.67 pp, 95% stratified bootstrap interval +0.90 to +4.48 pp). This is no-call format recovery: every gain turns an invalid output into a correct no-call answer. Both constrained arms score 0/250 in the other categories; unmasked generation scores 85/345. With the tool route imposed on 178 call-required tasks, both decoders score 126/178 with identical per-task labels (M.7). Although the five BFCL strings stay reachable by other token paths, the two masks' greedy next token differs at 6/10 teacher-forced prefixes (Table 28).

W3/Q3. Cost. On one A100, one episode at a time, in the 28 of 40 run groups accepted under sampled GPU isolation, mean seconds for original/v2/v3 are 13.42/27.51/20.99 (validation, 264 pairs) and 13.62/24.22/16.15 (development, 54 pairs); timed pairs cover checkpoints 0–2, plus part of 3 on validation (M.5, pp. 38–39). v3 reproduces v2's trace in every pair and takes 1.56× (validation) and 1.19× (development) the original mean time; the median within-pair v3/original ratio is 1.09× on both splits. Times include output-length differences; this is not serving latency. Table 30's 5.85× and 15.05× time only CPU mask queries, not model calls. Selectivity: we have not yet found a narrower check that provably keeps every admitted path.

Revision. The revised PDF states these results and limits in the Abstract, Contributions 1 and 3, new Section 6.3 (p. 9), Sections 7–9 and Ethics, with v3's episode cost (Section 7) and open items (Section 8).

Thank you for the additional experiments and clarifications.

My primary concern regarding methodological novelty remains unresolved. The proposed approach still mainly identifies and repairs two implementation-specific issues in LMFE, rather than introducing a substantially new or generalizable decoding methodology. Moreover, the additional experiments do not clearly establish the incremental benefits of the proposed repair itself, as several improvements appear to result from schema enforcement in general rather than the specific repair.

Overall, I appreciate the authors' efforts to strengthen the evaluation, but my assessment of the paper's contribution remains unchanged.

AuthorsOpenReview ↗

What the repair changes under the same schema

Thank you for identifying the remaining attribution issue. The Gemma result shows a benefit from schema enforcement: original LM Format Enforcer and v3 both solve 41/43 requests and emit identical tokens. We attribute that gain to enforcing the schema. The complete-episode comparison in Appendix M.2 tests the repair separately, because both arms already enforce the same schema with the same character parser.

We rechecked all 900 original and repaired episode records against their saved hashes. Each task uses the same checkpoint and prompt in both arms; only token enumeration changes.

Synthetic AgentGraph panelOriginal LMFERepair v2Gains / losses
Validation: 72 tasks × 5 checkpoints282/360316/36034 / 0
Validation pairs where both trajectories are schema-valid282/358314/35832 / 0
Development: 18 tasks × 5 checkpoints70/9075/905 / 0
Development pairs where both trajectories are schema-valid70/8375/835 / 0

The 32 validation gains with both outputs schema-valid are important here: they cannot be explained simply by turning schema-invalid outputs into schema-valid outputs. Appendix M.2 already reports this breakdown; our earlier reply should have made it explicit. The task panel was fixed before repair outcomes. The table shows raw counts; under the frozen design weights, the validation gain is +9.40 percentage points and is positive at all five checkpoints. A new, post-hoc sensitivity check resamples whole domains and graph motifs while retaining all five checkpoints, giving a central 95% bootstrap range of [+2.50, +17.99] points. This describes the fixed synthetic panel and checkpoints, not deployment-wide benefit. The schema-valid subset is descriptive, since validity itself is an outcome of decoding.

The gains are in the final answer. Executed tool sequences are identical in every pair, and v3 reproduces v2’s traces. On the separate released Llama-3.1-8B BFCL panel, original LMFE and v3 solve 142/178 and 143/178 requests; all outputs are schema-valid, but the one-answer difference is too small to establish a general accuracy advantage (Appendix M.8). We therefore distinguish the observed repair effect on the synthetic panel from the broader benefit of enforcing a schema.

We also ran a new intervention on all five token-divergent pairs in that 178-request Llama panel, selected by token differences without consulting correctness labels. At the first divergence, we either admitted the omitted token once under original LMFE or removed it once under v3, then resumed that arm’s usual masks. Prompts, model, schema, greedy decoding and the 192-token cap stayed fixed. All ten unchanged baselines exactly reproduced the archived tokens.

On these five requestsOriginalOriginal + one restored tokenFull v3v3 − one token
Officially correct1/51/52/51/5
Schema-valid5/55/55/55/5

For the gained request—the accented city-name argument in Appendix M.8—restoring that token recovered the complete repaired output and its correct score; removing it recovered the complete original output and its wrong score. However, restoration alone also lost another originally correct request. The one-token intervention isolates an answer-content effect while validity stays unchanged; its mixed results do not establish a shortcut to the full repair or a population accuracy gain.

On novelty, the general technical lesson is the need to test token enumeration against the backend’s own live character parser. A rejected canonical token path alone is insufficient: it can reflect a deliberately narrower compiled language, or a token omitted despite the live parser accepting its characters. The cross-backend controls distinguish property-order restrictions in XGrammar and llguidance from LMFE’s parser-accepted enumeration exclusions; Outlines Core’s exclusions remain unattributed. Building on tokenizer–grammar alignment work in DOMINO, SynCode and GreatGramma, our contribution is this parser-relative diagnosis, followed by a parser-preserving intervention and a matched answer-level evaluation. The diagnosis can be applied across stacks, while the specific repair and measured answer gains concern LMFE.

We appreciate your pressing us to separate these claims. The comparison we ask you to consider is the repair against an already constrained decoder, especially the gains where both outputs meet the schema, alongside the explicit limits on tool performance and generalization.

Reviewer_8N37OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper investigates a problem in constrained decoding where valid JSON outputs can be incorrectly blocked because certain tokens are excluded during generation. The authors compare four constrained decoding frameworks and identify inconsistencies in how they allow tokens. They propose modifications to LM Format Enforcer (LMFE) to fix two token-filtering issues without changing the underlying JSON parser. Experiments show that these fixes allow previously blocked tokens and change the generated outputs for selected Qwen, Llama, and agent examples. However, the paper does not demonstrate improvements in overall agent task performance, and the proposed solution significantly increases computational cost.

Critical strengths

Found two implementation issues in the latest grammar constrained decoding backbones like xgrammar and others.

Critical weaknesses

Limited practical impact: The paper demonstrates that valid token sequences can be incorrectly blocked, but it does not show whether fixing these issues improves the correctness or overall task performance of LLM agents. Since alternative token sequences can often generate the same valid output, the practical significance of these exclusions remains unclear.

High computational overhead: The proposed solution significantly increases decoding overhead, even after optimization. This raises concerns about its practicality for real-time LLM applications, especially since the paper does not demonstrate corresponding improvements in end-to-end task performance.

Questions for authors
  1. Practical impact (Clarification): Since alternative token sequences can often generate the same valid JSON output, how frequently do the identified token-path exclusions lead to incorrect outputs or actual failures in realistic LLM agent tasks?

  2. Computational overhead (Clarification): The proposed repair significantly increases decoding overhead, even after optimization. How do the authors justify this additional cost, and is there evidence that the improvement in output quality outweighs the computational expense?

  3. End-to-end performance (Additional evaluation): Can the authors provide evidence that restoring excluded token paths improves end-to-end agent task success or function-calling accuracy, rather than only exact target copying?

1 comment
AuthorsOpenReview ↗

Complete-episode answers, tied tool calls, and measured cost

Thanks for the valuable feedback! "Original LMFE" is LM Format Enforcer 0.11.3 as released; "v2" is our repaired enumerator (Section 5.3); "v3" is v2 with a character-set cache whose masks equal v2's at all audited prefixes (App. L.4). New results: Appendix M of the revised PDF (pp. 37–42).

W1 and Q3: end-to-end effect

Complete episodes (M.1–M.4, pp. 37–38): 90 synthetic AgentGraph tasks (72 validation, 18 development), fixed before any repair outcome, each under five fixed Qwen3.5-0.8B checkpoints. Success: exact or numeric final-answer match after the full episode.

  • Validation: 282/360 to 316/360 task–checkpoint pairs (34 gains on 23 tasks, 0 losses); design-weighted (fixed, near-uniform task weights) +9.4 percentage points (pp), positive under each checkpoint.
  • Development: 70/90 to 75/90 (5 gains on 3 tasks, 0 losses); two checkpoints unchanged. Zero observed losses do not prove the repair cannot hurt.
  • Tool decisions are tied: all 360 validation and 90 development pairs execute identical tool sequences. On 240 tool-required validation pairs, the first tool and its arguments match an enabled task-graph action in 200/240 and the complete plan in 156/240 under both decoders. The gain is in final answers.

W1's alternative paths: a reachable string need not be taken; greedy decoding takes the best admitted token, so removing one can change the continuation. The removed token is the unconstrained rank-1 next token in all 32 model-case scores of the selected 16-case panel (Section 6.1, p. 8); on five BFCL strings with a post-hoc alternative path, the masked greedy choice at a fixed prefix changes in 6/10 records under the BFCL prompt (Table 28, p. 35).

Function calling (BFCL V4, M.6–M.7, pp. 39–40): one Qwen3.5-2B checkpoint, used unchanged although its freeze record carries a failed training-gate marker; 345 supported tasks of a frozen 384-task sample; official checker; invalid outputs count as failures.

  • Free routing (the checkpoint picks call or answer): 77/345 original, 86/345 v2 (10 gains, 1 loss; category-weighted +2.67 pp, 95% stratified bootstrap interval +0.90 to +4.48 pp). All 10 gains turn an invalid output into a correct no-call response; the loss is the reverse. The checkpoint never took the tool route: outside the no-call categories both constrained arms score 0/250 (unmasked 29/250; 85/345 overall).
  • Imposed tool route (the checkpoint still picks tool and arguments), all 178 supported single-turn call-required tasks: 126/178 for both decoders, identical per-task labels. Released Llama-3.1-8B-Instruct (BF16, native prompt; M.8): 142/178 original, 143/178 v3 (1 gain, 0 losses; +0.56 pp, interval 0.00 to +1.69, including 0). Neither model loses a task; no tool-call gain is shown.

Revision

The revised PDF states these results and limits in the Abstract, Contribution 3, a new Section 6.3 (p. 9), Sections 7–9 and Ethics.

Q1: how often exclusions lead to failures

The "first divergence" is the first token where the original and v2 generations differ. There the original mask excludes v2's token although LMFE's own character parser accepts its characters, in 270/360 validation and 70/90 development pairs (M.3). They come from 58 and 19 prompt-prefix contexts at one original-mask state, not independent sites. Validation: 34 such pairs turn wrong to right, 0 right to wrong, 236 keep their label; development: 5, 0, 65. Pairs without one (90 validation, 20 development) never change. This is co-occurrence on one synthetic panel. On BFCL, unmasked generation's emitted tokens contain such an exclusion in 186/345 tasks (one checkpoint, final-answer payloads); 11/345 change correctness between original and v2. We have no rate for deployed traffic.

Q2 and W2: cost

Mean time per complete episode on one A100, one episode at a time, after warmup (M.5, pp. 38–39), in the 28 of 40 run groups accepted under sampled GPU isolation:

  • Validation, 264 pairs (checkpoints 0–2, 48 of 72 pairs of checkpoint 3; checkpoint 4, with the largest gain, untimed): 13.42 s original, 27.51 s v2, 20.99 s v3; v3 is 1.56× original. Correct: 214, 232, 232 of 264.
  • Development, 54 pairs (checkpoints 0–2): 13.62, 24.22, 16.15 s; v3 1.19× original.

v3 reproduces v2's trace in every pair; on timed validation pairs it adds 7.6 s per episode over original for 18 more correct answers of 264. The median within-pair v3/original ratio is 1.09× on both splits; means also include output-length differences. Batched serving is untested. Table 30's CPU ratios (p. 36; v3/original 5.85× on Qwen) replay fixed paths without forward passes: mask cost, not episode time.

Strengths

A correction: both repaired defects are in LMFE's enumerator. XGrammar's 75.0-point order effect is a declared property-order policy, which the paper's test separates from an enumeration error (Section 5.2; Table 10, p. 21); we have no evidence that another backend shares LMFE's defect (M.8).

Reviewer_FZBTOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper examines canonical-path exclusions in grammar-constrained decoding: schema-valid JSON strings that pass character-level parsing are incorrectly rejected at the token-masking stage. It compares four public constrained decoding backends, identifies two enumeration bugs in LM Format Enforcer, proposes a parser-preserving repair, and confirms the fix changes model outputs on selected test cases.

Critical strengths

The work draws a clear conceptual distinction between token-enumeration errors and character-language compilation policies, and delivers a precise root-cause diagnosis for the LMFE defects.

Critical weaknesses
  1. Practical relevance is unsubstantiated. All core findings are derived from artificially constructed factorial test suites and hand-picked BFCL cases. The paper provides no measurement of how frequently canonical-path exclusions occur in natural LLM agent traffic, standard function-calling benchmarks, or real-world deployment. Furthermore, the repair is only validated via exact string copying metrics, with no demonstration of end-to-end task performance gains (e.g., tool-call accuracy, task success rate).
  2. Contribution is narrow and lacks generalizable methodology. The work only identifies and patches two specific enumeration rules in a single backend (LM Format Enforcer). It offers no general framework for detecting token-enumeration errors across other constrained decoding stacks, nor does it perform root-cause analysis on rejections from llguidance, XGrammar or Outlines to show whether the same class of bug exists elsewhere.
  3. The repair is incomplete in correctness and prohibitive in cost. On the correctness side, the repair only addresses two observed failure patterns (cross-boundary fragments and escape-length caching) without any systematic proof that all enumeration defects have been eliminated. On the engineering side, the repair introduces 6–52× CPU overhead, which remains 4–15× even after cache optimization. The paper does not evaluate whether this overhead becomes a latency bottleneck in real GPU serving pipelines.
Questions for authors
  1. Have you run a full scan on standard function-calling benchmarks (e.g., the full BFCL dataset, natural AgentGraph trajectories) to measure the baseline rate of canonical-path exclusions in naturally generated outputs? Is there any evidence that these exclusions cause measurable degradation in end-to-end task accuracy or tool execution correctness?
  2. Completeness of the repair: The current fix targets only the two failure modes you observed. What systematic testing (e.g., fuzzing, exhaustive trie verification) have you performed to confirm that no other unobserved token-enumeration errors remain? How do you rule out that this is a piecewise patch rather than a fundamental solution to the enumeration problem?
  3. Deployment feasibility: The reported CPU overhead is substantial in replay benchmarks. In a realistic end-to-end GPU generation pipeline where mask computation interleaves with model forward passes, does the repaired enumerator introduce measurable latency degradation? Do you have a path to optimize the overhead to production-acceptable levels while retaining correctness?
1 comment
AuthorsOpenReview ↗

Emitted tokens, complete episodes, repair checks, episode cost

Thank you for the valuable feedback! Original LMFE: LM Format Enforcer 0.11.3 as released. v2: our repaired enumerator (Section 5.3). v3: v2 with a character-set cache whose masks equal v2's at all audited prefixes (App. L.4). Exclusion: the original mask omits a token whose characters LMFE's own parser accepts at a reachable prefix; the text may stay reachable by another tokenization.

W1/Q1. Natural occurrence. BFCL (M.6, p. 39): we did not scan all 4,441 BFCL V4 tasks. A 384-task sample (category quotas, SHA-256 task-ID order, frozen before paired runs) has 345 tasks fitting our single-call protocol. We replayed one fixed Qwen3.5-2B checkpoint's unmasked tokens in original LMFE. Of 545 payloads, 372 contain an exclusion, 27 follow an admitted path, 112 fail the schema and 34 fail JSON parsing. By task: 186/345, or 186/200 tasks with a fully accepted payload. Limits: one checkpoint, used unchanged although its freeze record carries a failed training-gate marker; all 545 generations took the final-answer route; dependent turns; no prevalence estimate.

AgentGraph (M.1, M.3, pp. 37–38): 90 synthetic tasks (72 validation, 18 development), fixed before any repair outcome, under five fixed Qwen3.5-0.8B checkpoints. At the first divergence (first token where the original and v2 generations differ), the original mask excludes v2's token in 270/360 validation and 70/90 development pairs, from 58 and 19 prompt-prefix contexts at one original-mask state: not independent sites.

End-to-end. AgentGraph, original → v2 (M.2, M.4):

  • Final answer (exact/numeric match): validation 282/360 → 316/360 (34 gains, 0 losses on this panel; design-weighted +9.4 pp, positive under each checkpoint); development 70/90 → 75/90 (5/0; two checkpoints unchanged).
  • 240 tool-required validation pairs: first tool and arguments 200/240, complete plan 156/240, both. Every pair in both splits executes identical tool sequences.

Gains are in final answers only; each co-occurs with an exclusion, but 236/270 validation and 65/70 development event pairs keep their label (no mediation shown).

BFCL, free routing (the checkpoint picks call or answer; official scorer; invalid = failure): original 77/345 → v2 86/345 (10 gains, 1 loss; category-weighted +2.67 pp, 95% stratified bootstrap interval +0.90 to +4.48 pp). All 10 gains turn an invalid output into a correct no-call response. Both constrained arms score 0/250 outside the no-call categories (unmasked: 29/250); unmasked scores 85/345 overall, about level with v2. With the tool route imposed (the checkpoint still picks tool and arguments) on 178 single-turn call-required tasks (M.7), both arms score 126/178 with identical per-task labels. Released Llama-3.1-8B-Instruct (BF16; not trained by us, so no gate marker): 142/178 original, 143/178 v3 (1 gain, 0 losses; interval 0.00 to +1.69 pp, including 0; M.8).

Hand-picked cases. The submitted BFCL-schema tasks were hash-selected (App. L.1); the 16 generation cases were selected by the mask before any model ran (Section 6.1).

W2. The Section 3 test needs only a backend's mask, character parser and a schema validator. XGrammar 0.1.27 rejects 48/192 paths with matched schema/text property order, 192/192 with mismatched order; the rise reflects a declared-order policy (Table 10). In llguidance 1.3.0 all 48 holdout rejections are two-field objects: 48/48 admitted when orders match, 0/48 otherwise (M.8, p. 40). Outlines Core: unattributed; we have no evidence another backend shares LMFE's defect.

W3a/Q2. v2 changes two general rules (Table 11): fragments the cache rejects are re-checked from the live parser state, and backslash fragments bypass the raw-length cache; both were designed post hoc from an earlier bank. Tests: a 192-case holdout fixed before either version ran (16 exclusions removed, 0/12 invalid controls admitted; Table 2); exhaustive trie traversal over a 57-token synthetic vocabulary, matched by v2 on all 1,570 reachable parser-accepted prefix rows (0/35 invalid controls admitted; D.7); 2,201,656 recorded v2-only memberships, all parser-accepted (L.4). Not claimed: fuzzing, a proof, or completeness at untested states; an escaped-quote enum value stays parser-rejected (D.7).

W3b/Q3. Yes, measurably. The 6–52× and 4–15× are CPU replay medians on fixed paths (Table 30), not generation. On one A100, in the 28 of 40 run groups accepted under sampled GPU isolation (no checkpoint-4 pairs on either split; M.5, pp. 38–39), mean complete-episode times were 13.42/27.51/20.99 s (original/v2/v3) on 264 validation pairs and 13.62/24.22/16.15 s on 54 development pairs. v3 reproduces v2's traces in every pair at 1.56× the original mean on validation (development 1.19×); the median within-pair v3/original ratio is 1.09× on both splits; times include output length. Serving latency under load is not measured.

Reviewer_z1SdOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper is mainly about token-path exclusion in constrained decoding for LLMs. The author compares four constrained decoding methods and finds token-enumeration problems in LMFE. Based on this observation, the author proposes a repair method to fix the bad cases that cannot be handled well by previous methods.

The author uses two LLMs to show the effectiveness of their method. Using more decoding time, the method can recover the previously excluded token paths.

Critical strengths
  1. The author provides an observation that existing mainstream constrained decoding methods may deny valid token paths.
  2. The author proposes a method to fix the wrongly denied valid token paths, with experiments showing the effectiveness of the method.
Critical weaknesses

W1: Limited value in real situations. Most of the time, users of LLMs cannot control the decoding strategy, so they cannot benefit from this method. Meanwhile, simply using prompt engineering is an easy and useful way to get valid JSON.

W2: Insufficient baselines and high computational cost. The paper uses too few models to prove the effectiveness of the proposed method. There are many open-source LLMs that can be examined with simple GPUs with less than 24GB of memory, but the author still omits these models. Another problem is that the method decreases the speed of decoding, which is a non-negligible cost.

Questions for authors

Q1: Can the method be used in more LLM models such as Qwen3.8-27B, Qwen3.6-35B-A3B or Gemma4 26B-A4B, which are populer open-source "small" LLMs? The experiment can be done with common quantization settings such as INT4 and INT8.

Q2: Is the method better than other constrained decoding methods XGrammar and llguidance? More baseline comparison is needed.

Q3: Could the author provide some end-to-end inference measurements, such as generation speed and latency, to show the method won't largely decrease the decoding speed.

3 comments
AuthorsOpenReview ↗

Practical relevance, baselines, model coverage and episode cost

Thank you for the constructive feedback! Original LMFE: LM Format Enforcer 0.11.3 as released; v2: our repaired enumerator (Section 5.3); v3: v2 plus a character-set cache whose masks equal v2's at all audited prefixes (App. L.4). New results: Appendix M of the revised PDF (pp. 37–42).

W1/Q1. Practical relevance. AgentGraph (90 synthetic tasks, five fixed Qwen3.5-0.8B checkpoints): at the first divergence (first token where the original and v2 generations differ), the original mask excludes v2's token although LMFE's own parser accepts its characters, in 270/360 validation and 70/90 development pairs, from only 58 and 19 prompt-prefix contexts at one mask state (M.3). BFCL V4: replaying a Qwen3.5-2B checkpoint's unmasked tokens finds such an exclusion in 186/345 single-call tasks, all in final-answer payloads (all 545 generations took that route); its freeze record carries a failed training-gate marker, and we used it unchanged (M.6). Neither count is deployment prevalence.

Complete episodes: exact or numeric final-answer matches rise from 282/360 to 316/360 on validation (34 gains, 0 observed losses) and from 70/90 to 75/90 on development (5/0; M.2, p. 37). Tool decisions tie (identical tool sequences in every pair; M.4).

Models: path tests under Qwen, Llama and Phi tokenizers (Section 5, App. L); generation with Qwen3.5-0.8B and Llama-3.1-8B (Table 3, p. 8); episodes with one family. New: released Llama-3.1-8B-Instruct (BF16, native prompt) on the 178 imposed-route BFCL tasks below: 142 correct with original LMFE, 143 with v3 (1 gain, 0 losses; +0.56 percentage points (pp), interval 0.00 to +1.69, including 0); token paths differ in 5 tasks, each at an original-LMFE exclusion in a tool argument (M.8). Not run: Qwen3.8-27B, Qwen3.6-35B-A3B, Gemma 4 26B-A4B, INT4/INT8 (INT8/NF4: CPU preflight only); no Gemma tokenizer. Weights and precision do not enter the mask but change which prefixes are visited, so effects may differ by model.

W2/Q2. Other decoders. On one constructed 192-path holdout, LMFE, llguidance, Outlines Core and XGrammar reject 48, 48, 72 and 84 (Figure 1, p. 2; Table 9, p. 21). XGrammar 0.1.27's order effect follows declared property order (Table 10, p. 21). A new fixed-path test finds an order policy in llguidance 1.3.0: two-field paths pass 48/48 when orders match, 0/48 otherwise (M.8).

Task level, imposed tool route (the checkpoint still picks tool and arguments), 178 single-turn call-required BFCL tasks, official checker, invalid = failure (M.7, p. 40). Correct and strict-schema-valid: original LMFE 126 and 174; v2 126 and 174; llguidance 1.8.0 118 and 158; XGrammar 0.2.7 120 and 176 (M.8). Original and v2 agree on every task's label; the two differing payloads fail in both. Against them, llguidance has 13 gains, 21 losses (12 invalid): −4.57 pp (category-weighted; 95% stratified bootstrap interval −10.79 to +1.64); XGrammar 14 and 20 (none invalid): −3.62 pp (−9.90 to +2.63). Both intervals cross zero: this panel does not order the decoders.

Free routing (the checkpoint picks call or answer), 345 tasks (M.6): correct 77 original, 86 v2, 85 unmasked; invalid 101, 36, 81. All 10 v2 gains turn an invalid output into a correct no-call answer; the loss is the reverse. Other 250 tasks: 0 for both constrained arms, 29 unmasked. So v2 is about level with unmasked, with fewer invalid outputs.

Post-processing: a fixed syntax cleanup (code fences, trailing commas, literal dictionaries; no labels) of unmasked outputs on 273 single-turn tasks: 196/273 parse, 85/273 correct, before and after (M.7). Prompt engineering (fixed format instruction, no mask, same checkpoint and tasks): 96 correct vs 86 v2, 77 original, 85 unmasked (vs v2: 18 gains, 8 losses; +3.57 pp weighted, interval +0.23 to +7.11; M.8). On this checkpoint the prompt-only control matches or exceeds the repair; we present the repair as a validity constraint (240 scorable v2 outputs vs 192), not as better than prompting. Its edge is on call-required tasks (16 vs 0); on no-call tasks v2 leads, 86 vs 80.

W2/Q3. Cost. Submitted v3/original medians (4.255–15.046×; Table 30, p. 36) time CPU replay of complete paths, not generation. New: one A100, one episode at a time after warmup, in the 28 of 40 run groups accepted under sampled GPU isolation (M.5, pp. 38–39), mean s per episode (original/v2/v3): validation, 264 pairs, 13.42/27.51/20.99; development, 54 pairs, 13.62/24.22/16.15. v3 takes 1.56× (validation) and 1.19× (development) the original mean; the median within-pair v3/original ratio is 1.09× on both splits. v3 reproduces v2's trace in every pair; times include output length; timed pairs cover checkpoints 0–2 and 48/72 validation pairs of checkpoint 3, not checkpoint 4 (largest validation gain). Not measured: batched serving, latency under load, other backends.

Revision. The Abstract, Contribution 3, a new Section 6.3 (p. 9), Sections 7–9 and Ethics report these results and limits.

Reviewer_z1SdOpenReview ↗

Response to the Author Rebuttal

Thank you for the additional experiments and revisions. I appreciate the effort, but the response doesn't fully resolve my concerns. On the contrary, some results further reinforce my doubts.

The simple prompt-engineering baseline achieves 96 correct tasks, compared with 86 for repaired LMFE and 77 for original LMFE. This shows that a simpler and cheaper method can do better than the proposed method.

The author didn't add experiments on Qwen3.8-27B, Qwen3.6-35B-A3B and Gemma4 26B-A4B. It's surprising that the author honestly lists these experiments as "not run", indicating that the author's response may have been generated by an agent that directly reports the results.

Compared with other methods, the proposed method didn't show enough of an advantage, and the problem of high decoding time cost still exists.

Unless the authors provide convincing evidence addressing these issues, I will have to maintain my current rating.

AuthorsOpenReview ↗

When does enforcing a tool-call schema help on Gemma 4?

Thank you for pressing us on the larger models and the cost of constrained decoding. Since our first reply we have tested Gemma-4-26B-A4B-it in BF16. We chose 43 requests from five categories of our 178-task BFCL panel before generation. All 43 required a tool call. We fixed the route, gave all three methods the same prompt, and used the official BFCL checker to score the tool name and arguments in the saved outputs.

Gemma 4 on the same 43 requestsPrompt onlyOriginal LM Format EnforcerCached repair (v3)
Correct tool call30/4341/4341/43
Valid under the required schema32/4343/4343/43
Median seconds per request, one A10010.2214.3714.33

All 11 gains came on requests where prompting produced invalid JSON. Allowing one enclosing Markdown code fence recovered six prompt-only successes, narrowing the gap to five. Original LM Format Enforcer and v3 produced identical tokens on every request. Enforcing the schema helped on this panel, and the original implementation captured the entire gain.

We agree with your reading of the free-routing result (Appendix M.8, p. 42). On those 273 tasks, prompting the Qwen3.5-2B checkpoint gave 96 correct, versus 86 with v2 and 77 with original LM Format Enforcer. Every method chose the final-answer route. Prompting still emitted 27 tool-call objects, 16 of which were correct. An application that already knows it needs a tool call can enforce that contract, as in the Gemma test. An application that has to choose the route can lose correct calls by enforcing the wrong contract.

The Gemma timings include mask computation and cover one request at a time. In the separate 264 paired validation episodes, v3 took 20.99 seconds on average versus 13.42 for original LM Format Enforcer (Appendix M.5, p. 39). Serving throughput under load and the two larger Qwen models you named remain open. We appreciate your asking us to report what enforcing the schema buys alongside the time it costs.

Reviewer_UrjuOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors suggest that existing constrained decoding stacks can incorrectly exclude valid token sequences because of a mismatch between character-level grammar constraints and token-level decoding, and a potential repair can reduce unintended distortions in LLM generation. The authors evaluate four native constrained-decoding stacks with 192 constructed json cases and found that these four tasks rejects different canonical paths and disagree with each other. The authors then propose fallback traversal, which rechecks rejected tokens based on their context, and cache bypass, which ignore raw length when decoding backslash related tokens, as joint repair to LMFE, with experiments showing that both repairs are needed. Then the authors investigate how these repairs affect the output of LLMs using 16 of 192 json cases, which was rejected in their first experiment and accepted after repair, and and found output changes in all LLMs being tested. These findings supports the authors' claim that constrained decoding stacks affect the outputs of LLMs, although the authors do not establish whether the proposed repair improves the performance of LLMs.

Critical strengths

The authors pinpoint two interacting mechanisms in LMFE that leads to inadvertent rejection of correct word-level generation. The ablation experiment demonstrates the need to both repairs implemented by the authors.

Critical weaknesses
  1. The LMFEs are tested on one crafted test suit throughout all experiments, and as the authors proceed they discard most of the testcases. The way this test suit is generated and the BCFL testcases chosen are arbitrary, making it hard to rule out effect of chance. The model choice and decoding stack choice are also limited, leaving questions of generalization on both ends.
  2. The advantage of generating outputs closer to LLMs' intention is rarely explored, which weakens the influence of this paper. The authors only test for changes in LLM outputs but never measures whether the change is positive or negative.
Questions for authors
  1. To what extent does the proposed approach generalize to other constrained-decoding frameworks?
  2. Could the authors clarify the construction procedure for the factorial JSON test suite, including the factors considered and how the test cases are generated?
1 comment
AuthorsOpenReview ↗

Measured task effect, panel sampling, and scope of the repair

Thank you for the review! "Original LMFE" is LM Format Enforcer 0.11.3 as released; "v2" is our repaired enumerator (Section 5.3). An exclusion is the mask removing, at a reachable prefix, a token whose characters LMFE's own parser accepts. New results: Appendix M of the revised PDF (pp. 37–42).

W2. Is the change positive or negative? We now measure it in complete episodes on 90 synthetic AgentGraph-v2 tasks, fixed before any repair outcome, each under five fixed Qwen3.5-0.8B checkpoints. Success is an exact or numeric final-answer match.

  • Validation (72 tasks): 282/360 → 316/360 task–checkpoint pairs correct; 34 gains on 23 tasks, 0 losses; design-weighted (near-uniform) +9.4 percentage points (pp), positive under each checkpoint.
  • Development (18 tasks): 70/90 → 75/90; 5 gains on 3 tasks, 0 losses; +5.55 pp, two checkpoints unchanged.

Zero losses is a panel observation, not a guarantee. In 32/34 validation and 5/5 development gains both trajectories are schema-valid, so the gain is not only repaired formatting. Every pair in both splits executes identical tool sequences, so the gain is in answers, not tool use (M.1–M.4, pp. 37–38).

On "closer to LLMs' intention": in the 16 generation cases the excluded token is the unconstrained model's local rank-1 token (32/32 model-case scores), and whenever unconstrained decoding copies the target, v2 does too (Qwen 14/14, Llama 13/13); Llama still misses 2/16 under v2 (Section 6.1, pp. 7–8).

On BFCL V4 (345 single-call tasks of a frozen 384-task sample; one Qwen3.5-2B checkpoint; official scorer, invalid = fail; free routing: the checkpoint picks call or answer), original LMFE scores 77/345 and v2 86/345: 10 gains, 1 loss, category-weighted +2.67 pp (95% stratified interval +0.90 to +4.48 pp), all 11 changes between an invalid output and a correct no-call answer. Scope: the checkpoint, used unchanged although its freeze record carries a failed training-gate marker, never took the tool route here, so the gain concerns no-call answers only. Unmasked generation scores 85/345: 56 on no-call tasks (v2: 86), 29 elsewhere (constrained arms: 0). With the tool route imposed (the checkpoint still picks tool and arguments) on 178 call-required tasks, both score 126/178, identical per task (M.6–M.7, pp. 39–40).

W1. One suite, discarded cases, chance. No holdout case is discarded: Table 2 (p. 6) reports all 192 (LMFE's character parser accepts 160, rejects 32); original LMFE excludes 16 of the 160, v2 none, and neither admits any of 12 invalid controls. Two panels are chosen by mask outcome, to test restored paths, not frequency: the 16 generation cases (fixed before any model ran) and five BFCL strings for prefix tests. A separate BFCL-schema panel takes per-category quotas (20 or 16 tasks) in SHA-256 order of seed, category and task ID; exclusions fall from 5/164 to 0/164 character-accepted paths under Qwen and Llama tokenizers (L.1, p. 32).

On chance: path outcomes are deterministic (forward and reverse runs agree), and the two earlier factorial banks (d0, e9; Q2) give identical counts (30/192 exclusions each; Table 5, p. 19). The BFCL interval excludes zero. AgentGraph validation gains appear under every checkpoint and come from 23 of 72 tasks, none of which loses; we report no interval for it.

Q2. Factorial construction. Each bank covers the 4 × 4 × 4 × 3 = 192 cells once: boundary (object or array close or comma), escape (none, quote, backslash, newline), fragment (alphanumeric, period, right brace, right bracket), string schema (free text, exact length, finite enum). A case is a JSON Schema, a valid JSON text and its factor labels; its canonical path is the tokenizer's encoding. Banks d0 (discovery), e9 (evaluation) and h7 (holdout) use different texts; h7 adds 12 invalid and 16 cache-order controls and was frozen without importing LMFE or querying any backend (Appendix A, B.2; pp. 16–18). The repair was designed post hoc from d0 and fixed before any evaluation on h7.

Q1 and W1 coverage. The Section 3 test needs only a backend's mask, character parser and a schema validator. Four stacks reject different path sets (Figure 1, p. 2). XGrammar's rejections rise by 75.0 pp when schema and text property orders differ (Table 10, p. 21); a new fixed-path check finds an order policy behind all 48 llguidance 1.3.0 rejections (M.8, p. 40); Outlines Core's are unattributed. What transfers is the test, not the patch: we found no evidence that another tested backend shares LMFE's enumeration defect, so the repair itself is LMFE-specific. Model choice: on BFCL tool calls, Llama-3.1-8B-Instruct scores 142/178 (original), 143/178 (v3, cached v2) (1 gain, 0 losses, interval including 0; M.8).

Revision. Changed: Abstract, Contribution 3, new Section 6.3 (p. 9), Sections 7–9 and Ethics; Section 8 lists what is untested (episodes with other model families, a BFCL checkpoint that calls tools itself, quantized models).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.