acceptodds
Under review as a conference paper at ICLR 2027

Improving Grammar Constraints Generation Alignment by Sampling Highly Probable Playouts

Abstract

Large Language Models (LLMs) can generate structured outputs such as program code, mathematical formulas, or well-formed markup language, but some of their outputs may end up non-grammatical, especially when considering very precise and obscure structures. Grammar Constrained Decoding (GCD) is used to force each subsequent token generated to follow a particular grammar. However, simple techniques use a distorted distribution of the LLMs. Grammar Aligned Decoding (GAD) is the problem of aligning sampling with a grammar constraint. Adaptive sampling with approximate expected futures (ASAp) has been proposed to solve GAD but requires storing the change in the probabilities of the LLM for each token in a datastructure. Furthermore, ASAp samples randomly from the aligned distribution as it is computed, which may not be optimal to maximize the alignment speed. We propose Greedy Best First Search with Greedy Sampling (GBFSGS) as a method to obtain high likelihood samples, which is more likely to maximize the alignment speed of the distribution. GBFSGS is able to solve GAD while storing the new probabilities in a datastructure with one element per sample drawn instead of per token changed. We show how the method finds the most probable samples of a distribution, including under a grammar constraint. We show how to implement the algorithm to avoid duplicate samples. We empirically evaluate our method on three sets of problems to evaluate the behavior of the methods. We show GBFSGS is able to select better samples than sampling to improve the alignment of the distribution while reducing the memory needed to store the aligned distribution.

Primary area:
generative models
Keywords:
Large Language Models, Grammar Constraints, Optimisation

Reviews

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

The paper presents GBFSGS, a grammar constrained decoding algorithm building off of the prior work of ASAp that aligns the conditioned distribution with the underlying distribution. The paper claims better convergence results than ASAp.

Critical strengths

None

Critical weaknesses

The paper is poorly written and appear unfinished. The main presented algorithm is cut off, which makes it difficult to assess this work. The text explanation is not precise nor detailed enough to explain the algorithm nor provide a convincing argument and proof for convergence. The key equations defining the prior work the algorithm is based on appear malformed, showing the not-entailed symbol. There is inconsistent notation leading to undefined values such as P~Skθ\tilde{P}_{S_k}^\theta. The paper breaks ICLR formatting requirements by using a tiny font for the figure captions. The work also claims a reduction in memory, but does not provide metrics measuring memory usage. Additionally, the improvement of the final expectation over the ASAp baseline is not a lot, putting into question the impact and significance of the findings.

Questions for authors
  • How is (faster) convergence guaranteed? Could the authors provide a proof?
Reviewer_B3X7OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper is about grammar-constrained decoding by global conditioning (i.e., Bayes rule). It builds closely on a prior method called ASAp (Park et al., 2024). The proposed method, GBFSGS, replaces ASAp’s random exploration with a best-first exploration to refine estimates of future grammaticality more eagerly.

Overall, I found the results encouraging; however, the current evaluation and exposition do not fully substantiate the claimed advantages; see below.

Critical strengths

S1. Preserving the language model’s distribution under grammatical constraints is a worthwhile goal that many papers have investigated. Local grammatical validity filtering alone does not ensure faithful sampling, and the paper addresses this (now well-known) distinction.

S2. The paper’s algorithmic idea is simple and reasonable. They aim to eagerly select paths to update the approximation, which appears to improve their convergence rates.

S3. Their experiments show faster reductions relative to ASAp.

Critical weaknesses

W1. The experimental comparisons are too narrow. Comparing only against GCD and ASAp does not establish competitiveness with other approaches targeting constrained distributions. The authors should compare against several highly relevant methods, including Gonzalez et al.’s MCMC method, which evaluates on the same benchmark families, and (grammar-only) SMC variants of Loula et al. and Lipkin et al.. Also, approximately aligned decoding (AprAD; Melcer et al., 2024) is acknowledged but not evaluated.

W2. The computational-efficiency claim is not sufficiently supported. Equal numbers of generations do not imply equal computation. The paper should report alignment error against elapsed time, FLOPS, or language-model forward passes.

W3. The experiments do not isolate the sources or robustness of the improvement. The evaluation uses one model and a small benchmark collection, without reported variability across independent runs. Ablations are needed for a more rigorous comparison.

Questions for authors

N/A

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

This paper presents a new method for grammar-aligned decoding, i.e. fixing the distribution distortion introduced by grammar-constrained decoding. The authors claim that the prior work (ASAp) that fixes distortion during repeated sampling is inefficient.

To improvement efficiency of distribution distortion fixing, the authors introduce Greedy Best First Search (GBFS) using the likehood of the sequences as the moves. To further incorporate information down the tree, they sample a full sentence from the node selected in GBFS, hence giving their method GBFS with Greedy Sampling (GBFSGS). They further optimize the memory use of GBFSGS by only storing changes of Expected Future Grammaticality in the root nodes of the greedy samples.

Experiments on Syntax-Guided Synthesis and constituency parsing show that their method can converge faster than prior work.

Critical strengths
  • New idea of using greedy samples instead of random samples to maximize the efficiency of grammar alignment.
  • Optimization of memory use by only storing the changes of expected future grammaticality in the root nodes of the greedy samples.
Critical weaknesses

The paper is half-baked. There are so many places this paper needs to polish. Overall, I don't think this paper is not currently qualified to be published; it needs more polishment.

Below are part of the suggestions to improve this paper:

  1. add a demonstration figure for GBFSGS to give the readers some impressions on why it is more efficient than ASAp,
  2. add a proof of convergence for GBFSGS,
  3. add theoretical analysis for probable faster convergence than ASAp,
  4. complete the paragraph at line 152,
  5. properly layout figures 1 to 12 (so that they don't just occupy so much spaces in the paper without providing enough new information),
  6. fix the titles of figures 5 to 8 and explain the geometric average in the main text,
  7. refer to figures 4 and 8 in the main text,
  8. add a required 'AI Use Statement' section to the paper,
  9. compare with more related work (e.g. AprAD mentioned in Section 7),
  10. rewrite Section 2 and 3 so that the background and symbols are not simply introduced in the 'Related Works' section,
  11. add more related work in (1) constrained decoding and (2) grammar-aligned decoding (I think this should be possible by finding the papers that cited ASAp on Google Scholar),
  12. explicitly state the ranges of variables, e.g. w′w' in ∑w′\sum_{w'},
  13. remove equation 7 (which is incompatible with equation 8 and 9),
  14. remove the unnecessary explanation of context-free grammar (notice that only L(G)L(\mathcal G) is necessary in the other sections).
Questions for authors

See the above weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.