Metraipolis › archive › dc_d69cfeb06167

Efficient Grammar-Constrained Decoding via Parser Stack Classification — arXiv:2608.03065

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.03065
License (as archived)
CC0-1.0
Archived
2026-10-31T12:43:25.525Z
SHA-256 of the archived text
3ef5f3229d9f75ebfad55f503323b601e577bca351ef50a8ca22d590925a1a47
Stable URL of this page
https://metraipolis.com/documento/dc_d69cfeb06167

How to cite

Efficient Grammar-Constrained Decoding via Parser Stack Classification — arXiv:2608.03065 — arXiv (en), https://arxiv.org/abs/2608.03065 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d69cfeb06167 (Metraipolis archive dc_d69cfeb06167, sha256 3ef5f3229d9f75ebfad55f503323b601e577bca351ef50a8ca22d590925a1a47)
BibTeX
@misc{dcd69cfeb06167,
  title = {Efficient Grammar-Constrained Decoding via Parser Stack Classification — arXiv:2608.03065},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.03065},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d69cfeb06167; sha256 3ef5f3229d9f75ebfad55f503323b601e577bca351ef50a8ca22d590925a1a47},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03065. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

LLMs are widely used to generate structured output like source code or JSON. Grammar-constrained decoding (GCD) can guarantee the syntactic validity of the generated output, by masking out tokens that violate rules specified by a context-free grammar. However, the online computational overhead of existing GCD methods, with latency typically scaling linearly with vocabulary size, limits the throughput of LLMs, especially for models with large vocabularies. To address this issue, we propose PSC, a novel grammar-constrained decoding method. By combining acceptance conditions of all vocabulary tokens into a single classifier of the parser stack during preprocessing, PSC can compute the complete vocabulary mask by checking the parser stack exactly once per decoding step, with time complexity independent of the vocabulary size. Experiments show that PSC computes masks up to 700$\times$ faster than baselines on complex programming language grammars, and up to 30$\times$ faster for schema-conformant JSON; end-to-end LLM throughput with PSC approaches that of unconstrained decoding. We analyze the preprocessing overhead for preprocessing providers and decoding users, and provide a break-even point analysis to help users decide whether to do preprocessing by themselves.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-05 in cs.SE).
Categorie arXiv: Software Engineering (cs.SE).
Pagina del lavoro: https://arxiv.org/abs/2608.03065 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T12:33:04.212Z dalla pagina https://arxiv.org/catchup/cs.SE/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).