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
| CREATOR | 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] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51873 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.05540