acceptodds
Withdrawn from ICLR 2027

Grammar Reachability for Lossless LM-Head Compression and Deterministic Token Injection in Structured Generation

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Schema-constrained generation offers two complementary deployment optimisations. GRVP (Grammar-Reachable Vocabulary Pruning) identifies the unique minimum LM-head row set preserving the grammar-masked output distribution (Theorem 4.1). It removes 98% of rows on automotive Thrift IDL and 99.9% on public VehicleWorld, with ΔEM=0.0000 across nine configurations and three model families; tied and mixed-type models use masks without storage savings. GGSD (Grammar-Guided Structured Decoding) injects grammar-forced tokens without a forward pass and reproduces per-state constrained greedy decoding for every block budget (Theorem 5.4). Reported speedups are 1.8× on VehicleWorld, 5.86× on xLAM and 64× on automotive (GPU-synchronised median; up to 86× on a favourable subset), with deterministic fractions of 46%, 84% and 96.5% respectively. Both methods are post-training and require no training data. Frequency pruning needs Ω(|L(GS)|) samples in the worst case: 26% of reachable automotive tokens are absent from training, whereas xLAM deterministic-position coverage reaches 96%. Grammar analysis thus separates structural reachability from corpus frequency.

Primary area:
foundation or frontier models, including LLMs
Keywords:
structured generation, vocabulary pruning, grammar-constrained decoding, speculative decoding, inference efficiency

Reviews

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

The paper introduces two techniques for making LM inference more efficient under syntactic constraints: dropping unusable tokens from the LM-head (GRVP) and picking tokens deterministically when the constraints only give you one option, rather than via inference (GGCD). The paper claims that GGCD already exists but that GRVP is novel. The evaluation suggests that GRVP and GGCD reduce inference cost and increase accuracy when compared against baselines.

Critical strengths

Not sure

Critical weaknesses
  1. The paper is difficult to read. Terms are frequently used without/before definition/explanation (e.g., the Contributions section, Section 2.1, L97, p_M, R_freq). The statement of Theorem 4.3 is also a bit vague, and the two key algorithms seem underspecified. I also felt that intuition was replaced by propositions, which further obscured things. Finally, it was difficult to locate the key claims being made in the Evaluation section, and it was unclear what was being measured in the experiments.

  2. Neither the intro nor the related work section adequately distinguishes this paper's contributions against the prior work. As a result, it is difficult to assess the paper's contributions. The "Constrained Generation" section in the related work suggests that GGCD already exists. As for GRVP, if is novel then the introduction should explain what challenges prevented it from being developed in prior work.

Questions for authors

Besides proofs, what does your work contribute that is not provided by prior work?

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

GRVP removes unreachable output rows. GGSD inserts grammar-forced tokens. Tests report unchanged GRVP outputs and faster GGSD decoding.

Critical strengths

Automotive model storage falls by about 1 GB. This can help devices with limited memory.

Critical weaknesses

Appendix F overstates equivalence. Local masking and global conditioning can produce different greedy outputs. The tests use a different mask from the proof. Software changes also affect the speed comparison. The paper needs a major editorial revision, it is hard to follow.

Questions for authors

Some sections of the main body start with formal results without any intro to why they are necessary. Can you fix the flow of the paper so it becomes more readable? Same comment goes for the appendix.

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

This paper proposes GRVP (grammar-reachable vocabulary pruning) and GGSD (grammar-guided forced-token injection) as two acceleration methods for structured generation, claiming 98% LM-head row removal and 64× decoding speedup on automotive Thrift IDL. The theoretical losslessness proofs are clean, but the headline speedup numbers come from non-reproducible proprietary data and uncontrolled timing setups, and the practical system-level benefit is questionable.

Critical strengths

The minimality certificate for GRVP and the token-by-token equivalence proof for GGSD are cleanly derived and formally self-consistent.

Bit-identical Δ_EM = 0.0000 across all nine configurations validates the losslessness claim.

Critical weaknesses

The headline 64× speedup is essentially cherry-picked: it comes from a 1,000-record high-EM subset, uncapped blocks, and GPU-synchronized timing, and is not run under the same harness as the 7.49× SchemaAutomaton result; the paper itself acknowledges the two differ by over 7σ and "do not isolate the O(n)→O(1) automaton effect," yet still promotes 64× as the main result in the abstract and conclusion.

The most impactful claims—98% pruning and 64× speedup—rest entirely on the proprietary automotive Thrift IDL; on public VehicleWorld the deterministic fraction is only 46.4% with a 1.8× speedup, and on xLAM only 5.86×. A reader cannot tell whether this is a genuine method advantage or whether the authors happened to pick an extreme schema with dense enum values and almost entirely deterministic positions.

End-to-end tok/s at batch=1 remains 26.9 both before and after GRVP+GGSD, because the LM head accounts for only ~2% of a decode step; the paper never addresses the fundamental question—if the end-to-end gain is zero in the most common batch=1 deployment scenario, what is the practical value of this work? The 1,700–2,291 tok/s figures come from a different configuration than the 26.9 tok/s baseline and cannot be compared directly.

Questions for authors

Run a fully controlled ablation on a single harness, fixed record set, and fixed GPU, varying only automaton type and block budget K, and report one credible median speedup rather than putting the best-subset number in the abstract.

Reproduce the ~60× speedup magnitude on at least one public schema with enum density comparable to automotive; otherwise readers must treat 64× as a proprietary-environment anecdote.

Address the zero end-to-end gain at batch=1: clarify the target deployment scenario (high batch? long context? edge?) and report end-to-end tok/s under that scenario, rather than only isolated LM-head latency numbers.

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

Related papers

Discussion (0)

Sign in to comment.