Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding

Faruk Alpay Department of Computer Engineering, Bahçeşehir University, Istanbul, Turkey [email protected] Bilge Senturk Department of Industrial Engineering, Bahçeşehir University, Istanbul, Turkey [email protected] · 2026

Read Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding by Faruk Alpay Department of Computer Engineering, Bahçeşehir University, Istanbul, Turkey [email protected] Bilge Senturk Department of Industrial Engineering, Bahçeşehir University, Istanbul, Turkey [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05540.txt.

Description

Alpay and Senturk study grammar-constrained decoding, coupling a next-token distribution with a reachability oracle over a pushdown system from a context-free grammar. They prove oracle invariance: language-equivalent grammars share admissible next-token sets and logit masks for every prefix, yet yield different compiled state spaces. They introduce a cost for packed-parse-forest growth per token: O(1) under right-recursion, but Theta(t^2) per token and Theta(n^3) under concatenation. Any sound online masking engine incurs Omega(t^2) work per token on one grammar family.

Catalog record

CREATORFaruk Alpay Department of Computer Engineering, Bahçeşehir University, Istanbul, Turkey [email protected] Bilge Senturk Department of Industrial Engineering, Bahçeşehir University, Istanbul, Turkey [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51873
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05540

Browse the full library · About the Tower of Babel