注意力与可达性相遇：语法约束下 LLM 解码的结构等价性与效率

This study investigates grammar-constrained decoding (GCD) as a coupling between an autoregressive next-token distribution and a reachability oracle over a pushdown system derived from a context-free grammar (CFG). An oracle invariance theorem is proven, stating that language-equivalent grammars induce identical admissible next-token sets for every prefix, resulting in identical logit masks, yet can lead to provably different compiled state spaces and online ambiguity costs. Exact control-state blowup counts are provided for the canonical $a^n b^n$ language under redundant nonterminal delegation. Additionally, a left-to-right structural ambiguity cost (SAC) is introduced to measure the incremental packed-parse-forest growth per token. For two equivalent grammars over all finite strings, SAC is shown to be $O(1)$.