mlsanityData to 14 Oct 2026

The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding

arXiv 2608.10137 ↗First posted 10 Aug 2026cs.CL cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Grammar Constrained Decoding (GCD) forces Language Models (LMs) to produce syntactically valid outputs by masking out non-conforming tokens at each step. However, because masking only checks whether each token is valid so far, the resulting distribution over complete outputs diverges from the LM's own distribution conditioned on the grammar, biasing generation toward valid but suboptimal outputs. Online sampling can restore this distribution, but only through costly iterative resampling. Our key insight is that the parser and lexer states that GCD tools already maintain carry a strong signal about future grammatical validity. We introduce SHIM, a lightweight, offline-trained correction of the LM's next-token probabilities, conditioned on this syntactic and lexical state together with candidate next tokens. Since GCD tools already compute these states, SHIM leaves the LM itself untouched. Across bit-vector and text-to-SQL grammars, this correction substantially narrows the gap to the LM's grammar-conditioned distribution compared to masking and online sampling, while running at nearly masking's speed. Even a variant that sees only the next token can improve on both baselines, making SHIM usable with GCD tools that do not expose their parser state.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 26 of its 32 references that are in the map. First posted on arXiv 10 Aug 2026.

Builds on

26 of 32 references.

References · 26

  1. 2021Evaluating Large Language Models Trained on Codecited by 8,320
  2. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  3. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  4. 2021Program Synthesis with Large Language Modelscited by 3,637
  5. 2022Competition-Level Code Generation with AlphaCodecited by 1,462
  6. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,141
  7. 2018Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Taskcited by 1,139
  8. 2023Teaching Large Language Models to Self-Debugcited by 988
  9. 2021FUDGE: Controlled Text Generation With Future Discriminatorscited by 376
  10. 2023Efficient Guided Generation for Large Language Modelscited by 200
  11. 2024Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generationcited by 101
  12. 2023Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programscited by 80
14 more
  1. 2024XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Modelscited by 75
  2. 2024SynCode: LLM Generation with Grammar Augmentationcited by 69
  3. 2023Tractable Control for Autoregressive Language Generationcited by 65
  4. 2024Grammar-Aligned Decodingcited by 54
  5. 2025Flexible and Efficient Grammar-Constrained Decodingcited by 43
  6. 2022Controllable Text Generation with Neurally-Decomposed Oraclecited by 41
  7. 2023Bounding the Capabilities of Large Language Models in Open Text Generation with Prompt Constraintscited by 31
  8. 2025Learning to Generate Structured Output with Schema Reinforcement Learningcited by 29
  9. 2025Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Samplingcited by 21
  10. 2025Constrained Sampling for Language Models Should Be Easy: An MCMC Perspectivecited by 14
  11. 2026Mitigating Bias in Locally Constrained Decoding via Tractable Proposalscited by 8
  12. 2025Correctness-Guaranteed Code Generation via Constrained Decodingcited by 7
  13. 2026LLMStructBench: Benchmarking Large Language Model Structured Data Extractioncited by 5
  14. 2025Constrained Adaptive Rejection Samplingcited by 3

Built on by

Not cited yet.