- Rating
- 4
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper tries to calculate the intractable membership probability in constrained decoding.
It extends the idea of using hidden Markov models (HMM) as a tractable surrogate to use context-free grammars (CFG) as constraints. It approximates CFG constraints for linear-time inference by only looking ahead a fixed number of tokens past the current prefix, requiring the 'prefix-unambiguity' only available in LL(1) grammars.
It calculates the probability conditioned on the prefix by using the remaining stack as the start symbol. It precomputes relevant probabilities for each non-terminal and every length, so at runtime it can be calculated efficiently.
Critical strengths
- Novel and realistic idea of only considering a fixed number of look-ahead tokens for linear-time inference.
- Clear writing, thorough theorital analysis, and full respect for existing work.
Critical weaknesses
- The alignment between the terminals and tokenizers is not considered.
- The effectiveness of this work (and similar work) depends on how well the HMMs can approximate the base LMs.
Questions for authors
- How well do the HMMs approximate the base LM?
- Can we get some experimental comparison with the concurrent work of Scribner et al. (2026), both in performance and speed?
- The GPU memory consumption of this work is nearly double the memory of LCD. Why?
- How much empirical performance gain can we get if we can use the full constraint instead of limited look-aheads? Or asked in another way, how well do limited look-heads empirically approximate the full constraint?