Tractable Hierarchical Control of Autoregressive Language Models

# Tractable Hierarchical Control of Autoregressive Language Models
Source: [https://arxiv.org/html/2607.20483](https://arxiv.org/html/2607.20483)
Antonio Vergari avergari@ed\.ac\.ukVaishak Belle vbelle@ed\.ac\.ukUniversity of Edinburgh

###### Abstract

Constraining the generation of autoregressive large language models \(LLMs\) is an important component of integrating language models into formal systems\. In the generation of code and data for tasks like program synthesis, ensuring that language models produce syntactically valid output is a prerequisite for processing such output\. These languages \(such as SQL or JSON\) are often designed asL​R​\(k\)LR\(k\)context\-free grammars\. By distilling the LLM to a tractable probabilistic model, its autoregressive generation can be steered and masked to incorporate the probability of satisfying logical constraints, ensuring high quality output that is guaranteed to be valid\. This paper demonstrates that the satisfaction of anyL​R​\(k\)LR\(k\)grammar of finite duration can be calculated in polynomial time, an improvement over the exponential time of applying previous methods to such grammars\. This result enables efficient constraint and steering of LLM generation towards output that better satisfies formal syntactic constraints\.

## 1Introduction

The output of large language models \(LLMs\) often needs to be parsed and converted into a structured form\. In code generation\(Jianget al\.,[2026](https://arxiv.org/html/2607.20483#bib.bib15)\), data generation\(Liet al\.,[2024](https://arxiv.org/html/2607.20483#bib.bib18)\), and structured natural language processing tasks\(Genget al\.,[2023](https://arxiv.org/html/2607.20483#bib.bib17)\), large language models must generate sequences which satisfy a predetermined formal language to be processed for downstream tasks\. Many of these languages are designed to beL​R​\(k\)LR\(k\)languages, i\.e\., languages which can be parsed using a shift\-reduce parser\(Ahoet al\.,[2006](https://arxiv.org/html/2607.20483#bib.bib23)\)\. The class of automata that classifyL​R​\(k\)LR\(k\)languages isdeterministic pushdown automata\(DPDAs\)\(Knuth,[1965](https://arxiv.org/html/2607.20483#bib.bib11)\)\. For this reason, improving the autoregressive generation of text that can be guaranteed to satisfy an arbitrary DPDA is important to the future of using the output of these models in formal systems\.

Even when prompted to satisfy simple hierarchical constraints, LLMs can fail, especially as the constraints stray out of their training distribution\. Across four open LLMs \(Figure 1\), we found the models consistently failed to generate text satisfying a simple context\-free grammar constraint, generating a short well\-nested sequence of square brackets and angle brackets, called a Dyck\-2 language \(discussed inEbrahimiet al\.\([2020](https://arxiv.org/html/2607.20483#bib.bib21)\)\)\. We found that as the set of parentheses changes from the more canonical\(\)​\[\]\(\)\[\]set to less attested parentheses in the literature on Dyck languages such as<\><\>and\{\}\\\{\\\}, all models perform worse at generating well\-typed and well\-nested sequences\. Despite the canonical Dyck\-2 language showing up in these models’ corpora, they fail to generate sequences satisfying the non\-canonical but conceptually equivalent constraint requested, as illustrated in Figure 1\. These models’ inability to reliably generate text satisfying such constraints indicates the necessity of constrained and steered generation more broadly in tasks that require LLMs to satisfy more complex languages with such nested structures\.

![Refer to caption](https://arxiv.org/html/2607.20483v1/LLMsFailing.png)Figure 1:LLMs fail to satisfy simple context\-free constraints\. Llama 3\.3 \(70 billion parameters\), Olmo 3\.1 \(32 billion parameters\), Mistral Medium 3\.5 \(128 billion parameters\) and DeepSeek V4 Pro \(1\.6 trillion parameters\) were instructed to generate a short example of Dyck\-2, the balanced parentheses language with two different types of parentheses\.When LLMs generate text, they produce a probability distribution over all potential next tokens, from which a new token is sampled\. Recent successes in constrained autoregressive generation mask the next token logits generated by the LLM to ensure that it is only possible for the model to generate valid tokens\(Deutschet al\.,[2019](https://arxiv.org/html/2607.20483#bib.bib25); Donget al\.,[2025](https://arxiv.org/html/2607.20483#bib.bib24); Kuchniket al\.,[2023](https://arxiv.org/html/2607.20483#bib.bib26)\)\. This approach ensures that the models never generate sequences that violate the specified generation constraints\. However, the probability of the remainder of the constrained sequence is not incorporated into the estimate of the immediate next token probability\. Failing to incorporate future consequences of the immediate next token decision leads to lower quality overall sequence generation\(Loulaet al\.,[2025](https://arxiv.org/html/2607.20483#bib.bib1)\)\.

We build onZhanget al\.\([2023a](https://arxiv.org/html/2607.20483#bib.bib20)\), incorporating the future consequences of the next token decision by distilling the LLM into a tractable probabilistic model \(TPM\),\(Vergariet al\.,[2019](https://arxiv.org/html/2607.20483#bib.bib4)\), in which the future constrained probability mass can be precisely and exactly accounted for\. This approach has previously been applied to enforce deterministic finite automata \(DFA\) constraints on language model generationZhanget al\.\([2023b](https://arxiv.org/html/2607.20483#bib.bib10),[2024](https://arxiv.org/html/2607.20483#bib.bib2)\)\. DFA constraints can ensure that the LLM generates text that conforms to any specifiedregular language\. Regular languages can describe constraints on the inclusion or exclusion of substrings as well as other simple constraints\. They cannot enforce the computationally more complex class ofdeterministic context\-free languages\(DCFLs\)\(Hopcroft and Ullman,[1979](https://arxiv.org/html/2607.20483#bib.bib19)\), which describe languages with recursive structure\. Examples of DCFLs range from simple languages such as nested parentheses to complex programming languages like HTML, C, SQL, etc\. In order to ensure the satisfaction of an arbitrary DCFL, the appropriate constraining class of automata is deterministic pushdown automata\.

This paper documents our method for tractably constraining and steering language models to satisfy DCFLs, which we callPASTA\-G\(Pushdown\-Automata Steering for Tractable Autoregressive Generation\)\. PASTA\-G modifies autoregressive language models to exactly incorporate the probability of the entire sequence into each token’s probability distribution, improving the generation of complex, recursively defined constraints\. In doing so, it enables guaranteed satisfaction of DCFL constraints\.

## 2Prior work

Zhanget al\.\([2023a](https://arxiv.org/html/2607.20483#bib.bib20)\)describes a method for using a distilled TPM over token sequence probabilities to guide the generation of an autoregressive LLM\. Unlike autoregressive LLMs, TPMs can tractably evaluate next token probabilities given complex long\-term constraints over future tokens, not just the immediate next token in generation\. Constraints \(represented asα\\alpha\) can be described as a boolean function over sequences\. The satisfaction of such a constraint can be described as a weighted model counting problem: the probability of satisfying the boolean constraintα\\alphais equal to the sum of the probabilities of all sequences \(x1:nx\_\{1:n\}\) which satisfy the constraint\.

p​\(α\)=∑x1:n​satisfies​αp​\(x1:n\)p\(\\alpha\)=\\sum\_\{\\mathclap\{x\_\{1:n\}\\text\{ satisfies \}\\alpha\}\}p\(x\_\{1:n\}\)
In autoregressive generation, wheret−1t\-1tokens have already been generated, the probability of prior tokens,x<tx\_\{<t\}, and the probability of a prospective next tokenxtx\_\{t\}are conditioned upon\.

p​\(α∣xt,x<t\)=∑x1:n​satisfies​αp​\(xt\+1:n∣xt,x<t\)p\(\\alpha\\mid x\_\{t\},x\_\{<t\}\)=\\sum\_\{\\mathclap\{x\_\{1:n\}\\text\{ satisfies \}\\alpha\}\}p\(x\_\{t\+1:n\}\\mid x\_\{t\},x\_\{<t\}\)
In the context of this task, a probabilistic model over token sequences is tractable if it is capable of exactly computing such a weighted\-model count in polynomial time\. If this distilled TPM can estimate the probability of a continuation of the sequence satisfying a logical constraintα\\alpha, thenZhanget al\.\([2023a](https://arxiv.org/html/2607.20483#bib.bib20)\)demonstrates that an autoregressive LM can be combined with the TPM to produce high quality token sequences guaranteed to satisfyα\\alpha\. The resulting distribution is:

p​\(xt\+1\|x1:t,α\)∝pTPM​\(α\|x1:t\+1\)⋅pLM​\(xt\+1\|x1:t\)p\(x\_\{t\+1\}\|x\_\{1:t\},\\alpha\)\\propto p\_\{\\text\{TPM\}\}\(\\alpha\|x\_\{1:t\+1\}\)\\cdot p\_\{\\text\{LM\}\}\(x\_\{t\+1\}\|x\_\{1:t\}\)
This was further developed inZhanget al\.\([2024](https://arxiv.org/html/2607.20483#bib.bib2)\), which showed that this approach can be applied in general to ensure that LM generation satisfies arbitrary deterministic finite automata \(DFAs\)\. To show this, they distill the LM to a hidden Markov model \(HMM\), and demonstrate that the HMM can be used to evaluate the probability of the overall sequence \(with a given maximum length\) satisfying any DFA\. One limitation of this paper is that DFAs can only model regular languages, a class of languages less expressive than most data languages and programming languages\(Hopcroft and Ullman,[1979](https://arxiv.org/html/2607.20483#bib.bib19)\)\.

## 3Deterministic pushdown automata

Pushdown automata can be defined in a variety of ways\. Here we only treat stack\-empty pushdown automata, a variety that accepts a string only when the automata’s stack is empty\. These are proven to be equivalent to every other formalization of pushdown automata inHopcroft and Ullman \([1979](https://arxiv.org/html/2607.20483#bib.bib19)\)\. In that same text, stack\-empty pushdown automata are defined as:

A=\(Q,Σ,Γ,q0,γ0,δ\)A=\(Q,\\Sigma,\\Gamma,q\_\{0\},\\gamma\_\{0\},\\delta\)where

- •QQis the finite set of states
- •Σ\\Sigmais a finite set called the input alphabet
- •Γ\\Gammais a finite set called the stack alphabet
- •q0∈Qq\_\{0\}\\in Qthe start state
- •γ0∈Γ\\gamma\_\{0\}\\in\\Gammathe initial stack symbol
- •δ\\deltais a finite subset ofQ×\(Σ∪\{ϵ\}\)×Γ×Q×Γ∗Q\\times\(\\Sigma\\cup\\\{\\epsilon\\\}\)\\times\\Gamma\\times Q\\times\\Gamma^\{\*\}, the transition relation

When executing, the pushdown automaton is described as having a configuration\.

C=\(q,γ\),q∈Q,γ∈Γ∗C=\(q,\\gamma\),\\,q\\in Q,\\,\\gamma\\in\\Gamma^\{\*\}
Sometimes the stack is described as having a topvvand a remainderWW\.

C=\(q,v​W\),v∈Γ,W∈Γ∗C=\(q,vW\),v\\in\\Gamma,W\\in\\Gamma^\{\*\}
If the stack is empty, it is written as

Each element of the transition relation associates a state, a stack element, and an input symbol \(σ∈Σ\\sigma\\in\\Sigma\) to an output state and a sequence of stack elements\.

\(q,σ,v,q^,V\)∈δ\(q,\\sigma,v,\\hat\{q\},V\)\\in\\delta
The above rule states that when the pushdown automaton’s configuration is \(qq,v​WvW\) and the next input symbol isσ\\sigma, then the automaton’s resulting configuration after consuming that symbol will be\(q^,V​W\)\(\\hat\{q\},VW\)\. Importantly, the valueVVcan be a sequence of elements inΓ\\Gammaof any length, including length0\.

The deterministic pushdown automaton \(DPDA\) requires that if there is anϵ\\epsilontransition \(a transition requiring noσ\\sigmatoken as input\) available from a configuration, then there can be noσ\\sigmatransition defined on that configuration\. It also requires that there be at most oneϵ\\epsilontransition from that configuration\. In other words, allϵ\\epsilontransitions are required to be processed when in their input configuration\.

## 4Approximation of DPDAs using DFAs

One approach to incorporating the probability of satisfying a DPDA could be to use the prior literature on finite automata satisfaction to approximate a DPDA of finite duration, obviating the need for a bespoke method handling DPDAs\. While pushdown automata of finite duration can be approximated by finite state automata, this approximation incurs exponential computational cost\. The cache used inZhanget al\.\([2024](https://arxiv.org/html/2607.20483#bib.bib2)\)is of sizeO​\(m⋅\|Z\|⋅\|Σ\|\)O\(m\\cdot\|Z\|\\cdot\|\\Sigma\|\), wheremmis the number of edges in the DFA,\|Z\|\|Z\|is the number of hidden states in the HMM, and\|Σ\|\|\\Sigma\|is the number of input symbols\. In the approximation of a duration\-bounded DPDA using a DFA, every state of the DFA represents a configuration of the pushdown automaton \(\|Q\|⋅\|Γ\|H\|Q\|\\cdot\|\\Gamma\|^\{H\}\), whereHHrepresents an upper bound on the stack height\. The worst case complexity for the number of edges in such a DFA is equal to the number of states squared, leading to a cache size ofO​\(\|Q\|2⋅\|Γ\|2​H⋅\|Z\|⋅\|Σ\|\)O\(\|Q\|^\{2\}\\cdot\|\\Gamma\|^\{2H\}\\cdot\|Z\|\\cdot\|\\Sigma\|\)\. This quickly becomes infeasible to compute as stack height increases, which we explore in our experiments\.

## 5Exact inference over deterministic pushdown automata

There are a variety of tractable probabilistic models that could be used to calculate the probability of satisfying a DPDA\. Although PASTA\-G follows the prior literature in using an HMM as its TPM, we first describe how exact inference over DPDAs is calculated in a fully factorized probabilistic model to provide intuition for the more complex HMM derivation\.

### 5\.1Fully factorized model

In the fully factorized model, the probability of each token is independent, which means the probability of an entire token sequence is the product of the probabilities of each token in the sequence \(p​\(x1:n\)=∏ip​\(xi\)p\(x\_\{1:n\}\)=\\prod\_\{i\}p\(x\_\{i\}\)\)\. Building onZhanget al\.\([2024](https://arxiv.org/html/2607.20483#bib.bib2)\), we need to evaluate the probability that the constraintα\\alphais true given all tokens up to and including the current token of generation\. For a stack\-empty DPDA, the constraint we plan to satisfy is that the stack is empty after generatingnntokens \(nnbeing a target for the final duration of the entire sequence\)\.

p​\(α∣xt,x<t\)=p​\(γn=ϵ∣xt,x<t\)p\(\\alpha\\mid x\_\{t\},x\_\{<t\}\)=p\(\\gamma\_\{n\}=\\epsilon\\mid x\_\{t\},x\_\{<t\}\)
Using the law of total probability, we can introduce the state of the DPDA here, describing the entire configuration of the DPDA\.

p​\(γn=ϵ∣xt,x<t\)=∑qn∈Qp​\(qn,γn=ϵ∣xt,x<t\)p\(\\gamma\_\{n\}=\\epsilon\\mid x\_\{t\},x\_\{<t\}\)=\\sum\_\{q\_\{n\}\\in Q\}p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid x\_\{t\},x\_\{<t\}\)
After consumingtttokens, all future configurations of a DPDA are entirely dependent on the configuration at timett\. The DPDA cannot "look back" at prior tokens to modify its configuration later on in processing\. This Markov property of DPDAs allows the DPDA configuration to substitute for the observed tokens due to the conditional independence\(qn,γn\)⟂⟂x1:t∣\(qt,γt\)\(q\_\{n\},\\gamma\_\{n\}\)\\perp\\\!\\\!\\\!\\\!\\perp x\_\{1:t\}\\mid\(q\_\{t\},\\gamma\_\{t\}\)\. Using this independence, we can substitute the configuration at timettfor the tokens in the prior equation\.

p​\(qn,γn=ϵ∣xt,x<t\)=p​\(qn,γn=ϵ∣qt,γt\)p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid x\_\{t\},x\_\{<t\}\)=p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}\)
Assume thatγt=v​W\\gamma\_\{t\}=vW, wherev∈Γv\\in\\Gammais the top of the stack andW∈Γ∗W\\in\\Gamma^\{\*\}is the remainder of the stack\. In order for the stack to be reduced toϵ\\epsiloninn−tn\-ttokens, the top value of the stack,vv, must be reduced toϵ\\epsilonin less than or equal ton−tn\-ttokens, and the remainder of the stackWWmust be reduced toϵ\\epsilonin the remaining number of tokens\. In enumerating every path of reduction, we must also sum over all potential configurations at each potential cut\.111We provide a derivation of equation 1 in appendix B\.1\.

p\(\\displaystyle p\(qn,γn=ϵ∣qt,γt=vW\)=\\displaystyle q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=∑u=0n−t∑qt\+u∈Qp​\(qt\+u,γt\+u=ϵ∣qt,γt=v\)⋅p​\(qn,γn=ϵ∣qt\+u,γt\+u=W\)\\displaystyle\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=v\)\\cdot p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\(1\)
This grounds the probability of reducing an entire stack in the probabilities of reducing individual elements of the stack\. The single stack element component of equation 1 is the probability that a configuration with a single stack elementvvreduces toϵ\\epsiloninuutokens\. The value of this depends on whether the configuration\(qt,γt\)\(q\_\{t\},\\gamma\_\{t\}\)has anϵ\\epsilontransition or not\. If the configuration has anϵ\\epsilontransition, then that transition must be applied immediately by the definition of the DPDA\.

\(qt,\\displaystyle\(q\_\{t\},ϵ,v,q^t,V\)∈δ⟹\\displaystyle\\epsilon,v,\\hat\{q\}\_\{t\},V\)\\in\\delta\\impliesp​\(qn,γn=ϵ∣qt,γt=v\)=p​\(qn,γn=ϵ∣q^t,γt=V\)\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=v\)=p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid\\hat\{q\}\_\{t\},\\gamma\_\{t\}=V\)\(2\)
If there is noϵ\\epsilontransition defined on the configuration at timett, the probability of a single stack element reducing toϵ\\epsiloninn−tn\-ttokens can be described as the probability that the next token is a valid transition token from the input configuration composed with the probability that the resulting configuration is satisfied inn−t−1n\-t\-1tokens\. For the purpose of concise notation, we define a functionΔ\\Delta, which takes a configuration and returns all token\-state\-stack triples into which that configuration can progress\.

\(σ,qt\+1,V\)∈Δ​\(qt,v\)⇔\(qt,σ,v,qt\+1,V\)∈δ\(\\sigma,q\_\{t\+1\},V\)\\in\\Delta\(q\_\{t\},v\)\\iff\(q\_\{t\},\\sigma,v,q\_\{t\+1\},V\)\\in\\delta
Using this function, we can define our single\-stack element reduction equation:

\(qt,\\displaystyle\(q\_\{t\},ϵ,v,q^t,V\)∉δ⟹\\displaystyle\\epsilon,v,\\hat\{q\}\_\{t\},V\)\\not\\in\\delta\\impliesp​\(qn,γn=ϵ∣qt,γt=v\)=∑\(xt\+1,qt\+1,γt\+1\)∈Δ​\(qt,v\)p​\(xt\+1\)⋅p​\(qn,γn=ϵ∣qt\+1,γt\+1\)\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=v\)=\\sum\_\{\\mathclap\{\(x\_\{t\+1\},q\_\{t\+1\},\\gamma\_\{t\+1\}\)\\in\\Delta\(q\_\{t\},v\)\}\}p\(x\_\{t\+1\}\)\\cdot p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\+1\},\\gamma\_\{t\+1\}\)\(3\)
While the last probability statement may condition on a stackγt\+1\\gamma\_\{t\+1\}with multiple elements in it, the duration of the remaining sequence is reduced by 1 token\. In combination with the multi\-element stack equation, this enables the calculation ofp​\(qn,γn=ϵ∣qt,γt\)p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}\)given prior knowledge ofp​\(qn,γn=ϵ∣qt\+u,γt\+u\)p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\+u\},\\gamma\_\{t\+u\}\)for allq∈Q,γt\+u∈Γ,1≤u≤n−tq\\in Q,\\gamma\_\{t\+u\}\\in\\Gamma,1\\leq u\\leq n\-t\. This composition is described in detail in the appendix A\.1, under Algorithm 1\.

The base case of this relation is whent=nt=n, at which point if there areϵ\\epsilontransitions defined on the configuration\(qn,γn\)\(q\_\{n\},\\gamma\_\{n\}\), the probability of reducing toϵ\\epsilonin0tokens is the probability that the resulting configuration after applying theϵ\\epsilontransition reduces toϵ\\epsilonin0tokens \(this merely restates equation 2\)\. If there are noϵ\\epsilontransitions defined on the configuration at tokennn, then the probability that the constraint is satisfied is 1 if and only if the stack is empty\.

\(qt,\\displaystyle\(q\_\{t\},ϵ,a,q^t,a^\)∉δ⟹\\displaystyle\\epsilon,a,\\hat\{q\}\_\{t\},\\hat\{a\}\)\\not\\in\\delta\\impliesp​\(qn,γn=ϵ∣qn,γn\)=𝟙​\[γ𝕟=ϵ\]\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{n\},\\gamma\_\{n\}\)=\\mathbbold 1\[\\gamma\_\{n\}=\\epsilon\]
Due to the expensive nature of recomputing equations 2 and 3 for every configuration and duration, a cache can be constructed beginning at the base case ofp​\(qn,γn=ϵ∣qn,γn=v\)p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{n\},\\gamma\_\{n\}=v\)and progressing top​\(qn,γn∣q0,γ0=v\)p\(q\_\{n\},\\gamma\_\{n\}\\mid q\_\{0\},\\gamma\_\{0\}=v\)\. Elements of this cache can be dynamically composed at runtime using equation 1, allowing for the estimation of satisfying a stack of arbitrary heighthhinO​\(\|Q\|2⋅n2⋅h\)O\(\|Q\|^\{2\}\\cdot n^\{2\}\\cdot h\)floating point multiplications \(see appendix A\.1\)\. The runtime to construct the cache isO​\(n3⋅\|Q\|2⋅\|δ\|⋅h\)O\(n^\{3\}\\cdot\|Q\|^\{2\}\\cdot\|\\delta\|\\cdot h\), wherehhis the maximum number of stack additions for any transition rule\. This can be understood as applying Algorithm 1 to each transition rule inδ\\deltafor successively larger values ofnn\.

### 5\.2Hidden Markov Model \(HMM\)

![Refer to caption](https://arxiv.org/html/2607.20483v1/hmm_smallerp.png)Figure 2:HMMIn the context of autoregressive language generation, a hidden Markov model \(HMM\) is a probability distribution over sequences of observed tokens\. Unlike the fully\-factorized example treated in section 5\.1, in an HMM tokens are not independent\. Rather, tokens are conditionally independent given a hidden state of the modelzt∈Zz\_\{t\}\\in Z, which may change in value every time a token is emitted\. This is the tractable probabilistic model used inZhanget al\.\([2024](https://arxiv.org/html/2607.20483#bib.bib2)\)to ensure language models satisfy DFA constraints\.

Using the same approach as section 5\.1, the constraint our TPM must calculate,α\\alpha, represents the stack being empty after generating our targetnntokens\. This constraint ensures that the final sequence will be of durationnnand will be accepted by the deterministic pushdown automaton\.

p​\(α\|xt,x<t\)=p​\(γn=ϵ\|xt,x<t\)=p​\(γn=ϵ,xt,x<t\)p​\(xt,x<t\)p\(\\alpha\|x\_\{t\},x\_\{<t\}\)=p\(\\gamma\_\{n\}=\\epsilon\|x\_\{t\},x\_\{<t\}\)=\\dfrac\{p\(\\gamma\_\{n\}=\\epsilon,x\_\{t\},x\_\{<t\}\)\}\{p\(x\_\{t\},x\_\{<t\}\)\}
The denominator is easy to compute, so we focus on the numerator\. We use the law of total probability to introduceztz\_\{t\}, the hidden state of our HMM\.

p​\(γn=ϵ,xt,x<t\)=∑zt∈Zp​\(γn=ϵ\|zt,xt,x<t\)⋅p​\(zt,xt,x<t\)p\(\\gamma\_\{n\}=\\epsilon,x\_\{t\},x\_\{<t\}\)=\\sum\_\{z\_\{t\}\\in Z\}p\(\\gamma\_\{n\}=\\epsilon\|z\_\{t\},x\_\{t\},x\_\{<t\}\)\\cdot p\(z\_\{t\},x\_\{t\},x\_\{<t\}\)
In generating and parsing sequentially using a DPDA, after parsing the firsttttokens, the future configurations of the DPDA depend solely on the configuration of the DPDA immediately after consuming tokentt\. As a reminder, the DPDA cannot look back at prior tokens or configurations to determine its state later during processing\. This is a Markov property of DPDAs and allows us to write:p​\(γn=ϵ∣zt,xt,x<t\)=p​\(γn=ϵ∣zt,qt,γt\)p\(\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},x\_\{t\},x\_\{<t\}\)=p\(\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}\)\. Applying that identity, we can write

p​\(γn=ϵ,xt,x<t\)=∑zt∈Zp​\(γn=ϵ\|zt,qt,γt\)⋅p​\(zt,xt,x<t\)p\(\\gamma\_\{n\}=\\epsilon,x\_\{t\},x\_\{<t\}\)=\\sum\_\{z\_\{t\}\\in Z\}\\boxed\{p\(\\gamma\_\{n\}=\\epsilon\|z\_\{t\},q\_\{t\},\\gamma\_\{t\}\)\}\\cdot p\(z\_\{t\},x\_\{t\},x\_\{<t\}\)
We can incorporate the potential final statesqnq\_\{n\}as well as potential final HMM hidden statesznz\_\{n\}into the equation using the law of total probability:

p​\(γn=ϵ\|zt,qt,γt\)=∑qn∈Q∑zn∈Zp​\(zn,qn,γn=ϵ\|zt,qt,γt\)\\boxed\{p\(\\gamma\_\{n\}=\\epsilon\|z\_\{t\},q\_\{t\},\\gamma\_\{t\}\)\}=\\sum\_\{q\_\{n\}\\in Q\}\\sum\_\{z\_\{n\}\\in Z\}p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\|z\_\{t\},q\_\{t\},\\gamma\_\{t\}\)
Assume thatγt=v​W\\gamma\_\{t\}=vW, wherev∈Γv\\in\\Gammais a single stack symbol, andW∈Γ∗W\\in\\Gamma^\{\*\}is the remainder of the stack\. Forγn\\gamma\_\{n\}to beϵ\\epsilongiven the stackγt=v​W\\gamma\_\{t\}=vW, first the top element ofγt\\gamma\_\{t\}\(vv\) must be reduced toϵ\\epsilonin fewer thann−tn\-ttokens, and then the remainder of the stack \(WW\) must be reduced toϵ\\epsilonin the remaining tokens\. Summing over all possible durationsuuof reducingvvtoϵ\\epsilon, all possible HMM stateszt\+uz\_\{t\+u\}after reducingvvtoϵ\\epsiloninuutokens, and all possible DPDA statesqt\+uq\_\{t\+u\}, we can isolate the probability of reducing the top element of the stackvvfrom the probability of reducing the remainder of the stackWW\.222We derive equation 4 in detail in appendix B\.2\.

p​\(zn,qn,γn=ϵ∣zt,qt,γt=v​W\)=\\displaystyle p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)=∑u=0n−t∑qt\+u∈Q∑zt\+u∈Zp​\(zt\+u,qt\+u,γt\+u=ϵ∣zt,qt,γt=v\)⋅p​\(zn,qn,γn=ϵ∣zt\+u,qt\+u,γt\+u=W\)\\displaystyle\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}\\sum\_\{z\_\{t\+u\}\\in Z\}p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=v\)\\cdot p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\(4\)
The first component of equation 4 is the joint probability that a configuration with a single stack elementvvreduces toϵ\\epsiloninuutokens, and that the HMM’s hidden state at timet\+ut\+uiszt\+uz\_\{t\+u\}given the HMM’s hidden state at timett\. The value of this depends on whether the configuration\(qt,γt\)\(q\_\{t\},\\gamma\_\{t\}\)has anϵ\\epsilontransition or not\. If the configuration has anϵ\\epsilontransition, then that transition must be applied immediately by the definition of the DPDA\.

\(qt,\\displaystyle\(q\_\{t\},ϵ,v,q^t,V\)∈δ⟹\\displaystyle\\epsilon,v,\\hat\{q\}\_\{t\},V\)\\in\\delta\\impliesp​\(zt\+u,qt\+u,γt\+u=ϵ∣zt,qt,γt=v\)=p​\(zt\+u,qt\+u,γt\+u=ϵ∣zt,q^t,γt=V\)\\displaystyle p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=v\)=p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid z\_\{t\},\\hat\{q\}\_\{t\},\\gamma\_\{t\}=V\)\(5\)
If there is noϵ\\epsilontransition defined on the configuration at timett, the probability of a single stack element reducing toϵ\\epsiloninuutokens can be described as the probability that the next token is a valid transition token from the input configuration composed with the probability that the resulting configuration is reduced inn−1n\-1tokens\. To describe this succinctly, we borrow the functionΔ\\Deltafrom section 5\.1\. The functionΔ\\Deltatakes a configuration and returns all token\-state\-stack triples into which that configuration can progress\.

Δ​\(qt,v\)=\(σ,qt\+1,V\)⇔\(qt,σ,v,qt\+1,V\)∈δ\\Delta\(q\_\{t\},v\)=\(\\sigma,q\_\{t\+1\},V\)\\iff\(q\_\{t\},\\sigma,v,q\_\{t\+1\},V\)\\in\\delta
Using this function, we can define our probability of reducing a single stack element when there is noϵ\\epsilontransition defined on it\.

\(qt,\\displaystyle\(q\_\{t\},ϵ,v,qt′,V\)∉δ⟹\\displaystyle\\epsilon,v,q\_\{t\}^\{\\prime\},V\)\\not\\in\\delta\\impliesp​\(zt\+u,qt\+u,γt\+u=ϵ∣zt,qt,γt=v\)=\\displaystyle p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=v\)=∑zt\+1p​\(zt\+1\|zt\)​∑\(xt\+1,qt\+1,γt\+1\)∈Δ​\(qt,v\)p​\(xt\+1\|zt\+1\)⋅p​\(zt\+u,qt\+u,γt\+u=ϵ∣zt\+1,qt\+1,γt\+1\)\\displaystyle\\sum\_\{z\_\{t\+1\}\}p\(z\_\{t\+1\}\|z\_\{t\}\)\\sum\_\{\\mathclap\{\(x\_\{t\+1\},q\_\{t\+1\},\\gamma\_\{t\+1\}\)\\in\\Delta\(q\_\{t\},v\)\}\}p\(x\_\{t\+1\}\|z\_\{t\+1\}\)\\cdot p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid z\_\{t\+1\},q\_\{t\+1\},\\gamma\_\{t\+1\}\)\(6\)
While equation 6 may increase the stack size \(as with equation 3\), it will always decrease the duration of the remaining sequence\. The exact value of equation 6’s recurrent component can be calculated using equation 4\. The base case for equation 6 is whenu=0u=0\. When this is the case, if there areϵ\\epsilontransitions defined on the configuration, then the probability of reducing the stack is calculated using equation 5\. If there are noϵ\\epsilontransitions defined on the configuration, then the probability of reducing the stack toϵ\\epsilonis 1 if and only if the stack is already empty\.

\(qt,\\displaystyle\(q\_\{t\},ϵ,v,q^t,V\)∉δ⟹\\displaystyle\\epsilon,v,\\hat\{q\}\_\{t\},V\)\\not\\in\\delta\\impliesp​\(zt,qt,γt=ϵ∣zt,qt,γt\)=𝟙​\[γ𝕥=ϵ\]\\displaystyle p\(z\_\{t\},q\_\{t\},\\gamma\_\{t\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}\)=\\mathbbold 1\[\\gamma\_\{t\}=\\epsilon\]
The relationships defined above monotonically reduce the sequence duration required to compute their probabilities\. This allows us to compute the value of equation 4 for sequences of durationn−tn\-tknowing only the values of equations 4, 5, and 6 for sequence durations less thann−tn\-t\. Using this fact, we can iteratively construct from base cases a cache of values representing equations 5 and 6 and compose those values to evaluate equation 4\. The cache for equations 5 and 6 occupiesO​\(\|Z\|2⋅\|Q\|2⋅\|Γ\|⋅n\)O\(\|Z\|^\{2\}\\cdot\|Q\|^\{2\}\\cdot\|\\Gamma\|\\cdot n\)space\. The composition of these values into equation 4 for a stack height ofhhruns inO​\(n2⋅\|Q\|2⋅\|Z\|2⋅h\)O\(n^\{2\}\\cdot\|Q\|^\{2\}\\cdot\|Z\|^\{2\}\\cdot h\)floating point multiplications using Algorithm 2 specified in appendix A\.2\. By applying Algorithm 2 for every transition rule inδ\\deltaand every duration from0tonn, the cache can be constructed inO​\(n3⋅\|Q\|2⋅\|Z\|2⋅h⋅\|δ\|\)O\(n^\{3\}\\cdot\|Q\|^\{2\}\\cdot\|Z\|^\{2\}\\cdot h\\cdot\|\\delta\|\)time\.

## 6Experiments

![Refer to caption](https://arxiv.org/html/2607.20483v1/dyck.png)Figure 3:Balanced parentheses \(Dyck\-1\)To empirically validate PASTA\-G, we implemented it in Python and compared its estimation ofp​\(α∣xt,x<t\)p\(\\alpha\\mid x\_\{t\},x\_\{<t\}\)with the brute\-force weighted\-model count estimation ofp​\(α∣xt,x<t\)p\(\\alpha\\mid x\_\{t\},x\_\{<t\}\)\. We applied these tests on the prototypical balanced\-parentheses languages, comparing runtime and memory usage with Ctrl\-G\.

Balanced parentheses languages \(also called Dyck languages\) are those languages that are only satisfied when their input is a properly nested sequence of parentheses\. An illustration of balanced parentheses \(Dyck\-1\) strings can be found in Figure 3\. Dyck\-1 is context\-free, requires hierarchical and recursive parsing, and cannot be represented by a finite\-state automaton\(Hopcroft and Ullman,[1979](https://arxiv.org/html/2607.20483#bib.bib19)\), making it a good candidate for comparing PASTA\-G to Ctrl\-G\.

One way to evaluate the empirical accuracy of PASTA\-G is by treating it as a weighted model counting problem\. We can evaluate the true probability of constraint satisfaction by looking at all potential strings and evaluating the sum of the probabilities of those strings that satisfy the constraint\. From an autoregressive context, we must condition on the already generated content and sum over potential string completions\.

p​\(α∣xt,x<t\)\\displaystyle p\(\\alpha\\mid x\_\{t\},x\_\{<t\}\)=∑x1:n​satisfies​αp​\(xt\+1:n∣xt,x<t\)\\displaystyle=\\sum\_\{\\mathclap\{x\_\{1:n\}\\text\{ satisfies \}\\alpha\}\}p\(x\_\{t\+1:n\}\\mid x\_\{t\},x\_\{<t\}\)
We test PASTA\-G’s expected probability distribution over possible next tokensxtx\_\{t\}using all potential prefixes for expected sequence lengths between 1 and 10 across a collection of randomly initialized two\-state HMMs\. For all next tokens \(xt∈\{‘​‘​\(”,‘​‘\)​”,‘​‘​<EOS\>​”\}x\_\{t\}\\in\\\{\`\`\(",\`\`\)",\`\`\\text\{<EOS\>\}"\\\}\), prefixes \(x1:t−1x\_\{1:t\-1\}\), sequence lengths \(nn\), and HMM initializations, we see identical probabilities between our evaluation and the weighted\-model counting evaluation ofp​\(α∣xt,x1:t−1\)p\(\\alpha\\mid x\_\{t\},x\_\{1:t\-1\}\)\.

To evaluate the runtime complexity, we benchmark both the cache size and inference time as they vary with the maximum sequence length in estimating the probability of Dyck\-1\. Because Dyck\-1 can pop at most one stack element per token, we can upper\-bound the stack\-height asH=⌈n/2⌉H=\\lceil n/2\\rceil, wherennrepresents the upper\-bound on how many tokens can be generated\. Using this upper\-bound, we can approximate a length\-bounded Dyck pushdown automaton by creating a finite set of states\(q,γ\),∀q∈Q,γ∈Γh,0≤h≤H\(q,\\gamma\),\\forall q\\in Q,\\gamma\\in\\Gamma^\{h\},0\\leq h\\leq H\. This set of states can be used as input to Ctrl\-G to simulate the behavior of our pushdown automaton probability estimation\. We find that, as expected, Ctrl\-G has exponential cache\-space and inference\-time complexity with respect to sequence length, whereas PASTA\-G has linear space\-complexity and quadratic inference\-time complexity with respect to sequence length, as shown in Figure 4\.

![Refer to caption](https://arxiv.org/html/2607.20483v1/runtimecomparisons.png)Figure 4:Runtime and cache size of Ctrl\-G and PASTA\-G for Dyck\-1\.As sequence length increases, Ctrl\-G’s cache size and inference time grow exponentially, while PASTA\-G’s cache size grows linearly and its inference time grows quadratically\.
## 7Related Work

InLoulaet al\.\([2025](https://arxiv.org/html/2607.20483#bib.bib1)\), the incorporation of total sequence probability into the autoregressive next token decision for context\-free grammar satisfaction is achieved using sequential Monte\-Carlo\. This approach demonstrates impressive results across a variety of languages\. It does not, however, use the tractable marginalization enabled by a TPM, which implies that the method would rely on a large number of particles to converge\. It does show that logit\-based steering can measurably improve generation quality for complex real\-world code and data constrained generation tasks\.

Baigetet al\.\([2026](https://arxiv.org/html/2607.20483#bib.bib27)\)take a similar approach to integrating TPMs and context\-free grammars, though without using LLMs\. They approach this task by compiling the grammar into a tractable probabilistic circuit \(PC\)\(Darwiche,[2003](https://arxiv.org/html/2607.20483#bib.bib9); Vergariet al\.,[2019](https://arxiv.org/html/2607.20483#bib.bib4); Choiet al\.,[2020](https://arxiv.org/html/2607.20483#bib.bib8)\)that can be trained on observed examples of the grammar\. PCs generalize HMMs and other TPMs and have been extensively used for tractable neuro\-symbolic computation\(Ahmedet al\.,[2022](https://arxiv.org/html/2607.20483#bib.bib7)\)\. PASTA\-G uses a preexisting TPM \(an HMM\) and composes its parameters dynamically to tractably estimate the probability of each element in a sequence autoregressively\. Ideally, we could use the same compilation strategy ofBaigetet al\.\([2026](https://arxiv.org/html/2607.20483#bib.bib27)\), which incurs cubic complexity, to obtain a PC that encodes a context\-free grammar and tractably multiply it with an HMM to retrieve our algorithm\(Vergariet al\.,[2021](https://arxiv.org/html/2607.20483#bib.bib6)\)\. This would, however, require additional memory and computational overhead for the multiplication\. Two further advantages of our method over that used inBaigetet al\.\([2026](https://arxiv.org/html/2607.20483#bib.bib27)\)are that PASTA\-G does not require re\-distillation of the tractable probabilistic model when the grammar changes, and PASTA\-G’s HMM has no upper\-bound on its parameter count for grammars generated to fixed sequence durations\.

## 8Future areas of research

### 8\.1Tokenization

One limitation in applying PASTA\-G to large language models is the problem of misalignment between the LLM tokenizer and the tokenization assumed in the DPDA\. The first issue with such misalignment is that the LLM tokenizer may split DPDA tokens, breaking the determinism required by this approach\. Another issue is that the DPDA tokens may split canonical sequence tokenizations for the LLM\. For example, most deterministic context\-free grammar representations of English word sequences assume spaces are separate tokens from words, whereas most byte\-pair\-encoding tokenizers used in LLMs merge words and spaces\. These tokenization misalignments will need to be addressed to properly apply PASTA\-G to more diverse languages\.

### 8\.2Other future areas of research

Any language that can be parsed deterministically using a definite number of look\-ahead symbols is a deterministic context\-free language and can be parsed using a DPDA\(Knuth,[1965](https://arxiv.org/html/2607.20483#bib.bib11)\)\. Automatically translating DCFLs more complex than those treated in this paper into DPDAs could be a fruitful area of future research\. Doing so would enable the effortless application of PASTA\-G to arbitrary DCFLs\.

The extension of this work to other formal automata is an open area of future research\. Applying PASTA\-G’s approach to nondeterministic pushdown automata would generate more powerful languages with exact satisfaction guarantees\. Similarly, creating a method similar to PASTA\-G for more powerful automata such as the nested stack automaton would enable its application to context\-sensitive languages\. Most natural languages are "mildly context\-sensitive,"\(Shieber,[1985](https://arxiv.org/html/2607.20483#bib.bib12); Michaelis,[1998](https://arxiv.org/html/2607.20483#bib.bib13)\), and some programming languages are as well \(e\.g\., Python,Laurent and Mens \([2016](https://arxiv.org/html/2607.20483#bib.bib14)\)\)\. Extending exact probabilistic inference to constrained generation of mildly context\-sensitive languages could improve autoregressive code and language generation\. Finally, our approach could be hybridized with that inBaigetet al\.\([2026](https://arxiv.org/html/2607.20483#bib.bib27)\)by embedding an HMM as a probabilistic circuit layer in an LLM\(Grivaset al\.,[2026](https://arxiv.org/html/2607.20483#bib.bib5)\)that compiles a context\-free grammar\.

## References

- K\. Ahmed, S\. Teso, K\. Chang, G\. Van den Broeck, and A\. Vergari \(2022\)Semantic probabilistic layers for neuro\-symbolic learning\.InProceedings of the 36th International Conference on Neural Information Processing Systems,NIPS ’22,Red Hook, NY, USA\.External Links:ISBN 9781713871088Cited by:[§7](https://arxiv.org/html/2607.20483#S7.p2.1)\.
- A\. V\. Aho, M\. S\. Lam, R\. Sethi, and J\. D\. Ullman \(2006\)Compilers: principles, techniques, and tools \(2nd edition\)\.Addison\-Wesley Longman Publishing Co\., Inc\.,USA\.External Links:ISBN 0321486811Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p1.2)\.
- A\. Baiget, J\. Maene, S\. Lee, B\. Wang, G\. V\. den Broeck, and M\. Kim \(2026\)ExplainFuzz: explainable and constraint\-conditioned test generation with probabilistic circuits\.External Links:2604\.06559,[Link](https://arxiv.org/abs/2604.06559)Cited by:[§7](https://arxiv.org/html/2607.20483#S7.p2.1),[§8\.2](https://arxiv.org/html/2607.20483#S8.SS2.p2.1)\.
- Y\. Choi, A\. Vergari, and G\. Van den Broeck \(2020\)Probabilistic circuits: a unifying framework for tractable probabilistic modeling\.Technical reportUniversity of California, Los Angeles \(UCLA\)\.External Links:[Link](http://starai.cs.ucla.edu/papers/ProbCirc20.pdf)Cited by:[§7](https://arxiv.org/html/2607.20483#S7.p2.1)\.
- A\. Darwiche \(2003\)A differential approach to inference in bayesian networks\.Journal of the ACM \(JACM\)50,pp\. 280–305\.Cited by:[§7](https://arxiv.org/html/2607.20483#S7.p2.1)\.
- D\. Deutsch, S\. Upadhyay, and D\. Roth \(2019\)A general\-purpose algorithm for constrained sequential inference\.InProceedings of the 23rd Conference on Computational Natural Language Learning \(CoNLL\),M\. Bansal and A\. Villavicencio \(Eds\.\),Hong Kong, China,pp\. 482–492\.External Links:[Link](https://aclanthology.org/K19-1045/),[Document](https://dx.doi.org/10.18653/v1/K19-1045)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p3.1)\.
- Y\. Dong, C\. F\. Ruan, Y\. Cai, Z\. Xu, Y\. Zhao, R\. Lai, and T\. Chen \(2025\)Xgrammar: flexible and efficient structured generation engine for large language models\.Proceedings of Machine Learning and Systems7\.Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p3.1)\.
- J\. Ebrahimi, D\. Gelda, and W\. Zhang \(2020\)How can self\-attention networks recognize Dyck\-n languages?\.InFindings of the Association for Computational Linguistics: EMNLP 2020,T\. Cohn, Y\. He, and Y\. Liu \(Eds\.\),Online,pp\. 4301–4306\.External Links:[Link](https://aclanthology.org/2020.findings-emnlp.384/),[Document](https://dx.doi.org/10.18653/v1/2020.findings-emnlp.384)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p2.3)\.
- S\. Geng, M\. Josifoski, M\. Peyrard, and R\. West \(2023\)Grammar\-constrained decoding for structured NLP tasks without finetuning\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Singapore,pp\. 10932–10952\.External Links:[Link](https://aclanthology.org/2023.emnlp-main.674/),[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.674)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p1.2)\.
- A\. Grivas, L\. Loconte, E\. van Krieken, P\. Nawrot, Y\. Zhao, E\. Wielewski, P\. Minervini, E\. Ponti, and A\. Vergari \(2026\)Fast and expressive multi\-token prediction with probabilistic circuits\.InInternational Conference on Machine Learning,Cited by:[§8\.2](https://arxiv.org/html/2607.20483#S8.SS2.p2.1)\.
- J\. E\. Hopcroft and J\. D\. Ullman \(1979\)Introduction to automata theory, languages and computation\.External Links:[Link](https://api.semanticscholar.org/CorpusID:31901407)Cited by:[§C\.3](https://arxiv.org/html/2607.20483#A3.SS3.p2.7),[§1](https://arxiv.org/html/2607.20483#S1.p4.1),[§2](https://arxiv.org/html/2607.20483#S2.p6.1),[§3](https://arxiv.org/html/2607.20483#S3.p1.1),[§6](https://arxiv.org/html/2607.20483#S6.p2.1)\.
- J\. Jiang, F\. Wang, J\. Shen, S\. Kim, and S\. Kim \(2026\)A survey on large language models for code generation\.ACM Trans\. Softw\. Eng\. Methodol\.35\(2\)\.External Links:ISSN 1049\-331X,[Link](https://doi.org/10.1145/3747588),[Document](https://dx.doi.org/10.1145/3747588)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p1.2)\.
- D\. E\. Knuth \(1965\)On the translation of languages from left to right\.Information and Control8\(6\),pp\. 607–639\.External Links:ISSN 0019\-9958,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/S0019-9958%2865%2990426-2),[Link](https://www.sciencedirect.com/science/article/pii/S0019995865904262)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p1.2),[§8\.2](https://arxiv.org/html/2607.20483#S8.SS2.p1.1)\.
- M\. Kuchnik, V\. Smith, and G\. Amvrosiadis \(2023\)Validating large language models with relm\.Proceedings of Machine Learning and Systems5,pp\. 457–476\.Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p3.1)\.
- N\. Laurent and K\. Mens \(2016\)Taming context\-sensitive languages with principled stateful parsing\.InProceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering,SLE 2016,New York, NY, USA,pp\. 15–27\.External Links:ISBN 9781450344470,[Link](https://doi.org/10.1145/2997364.2997370),[Document](https://dx.doi.org/10.1145/2997364.2997370)Cited by:[§8\.2](https://arxiv.org/html/2607.20483#S8.SS2.p2.1)\.
- D\. Li, Y\. Zhao, Z\. Wang, C\. Jung, and Z\. Zhang \(2024\)Large language model\-driven structured output: a comprehensive benchmark and spatial data generation framework\.ISPRS International Journal of Geo\-Information13\(11\),pp\. 405\.Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p1.2)\.
- J\. Loula, B\. LeBrun, L\. Du, B\. Lipkin, C\. Pasti, G\. Grand, T\. Liu, Y\. Emara, M\. Freedman, J\. Eisner, R\. Cotterell, V\. Mansinghka, A\. K\. Lew, T\. Vieira, and T\. J\. O’Donnell \(2025\)Syntactic and semantic control of large language models via sequential monte carlo\.External Links:2504\.13139,[Link](https://arxiv.org/abs/2504.13139)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p3.1),[§7](https://arxiv.org/html/2607.20483#S7.p1.1)\.
- J\. Michaelis \(1998\)Derivational minimalism is mildly context\-sensitive\.InSelected Papers from the Third International Conference, on Logical Aspects of Computational Linguistics,LACL ’98,Berlin, Heidelberg,pp\. 179–198\.External Links:ISBN 354042251XCited by:[§8\.2](https://arxiv.org/html/2607.20483#S8.SS2.p2.1)\.
- S\. M\. Shieber \(1985\)Evidence against the context\-freeness of natural language\.Linguistics and Philosophy8\(3\),pp\. 333–343\.External Links:ISSN 01650157, 15730549,[Link](http://www.jstor.org/stable/25001210)Cited by:[§8\.2](https://arxiv.org/html/2607.20483#S8.SS2.p2.1)\.
- A\. Vergari, Y\. Choi, A\. Liu, S\. Teso, and G\. Van den Broeck \(2021\)A compositional atlas of tractable circuit operations for probabilistic inference\.InAdvances in Neural Information Processing Systems 34 \(NeurIPS\),pp\. 13189–13201\.Cited by:[§7](https://arxiv.org/html/2607.20483#S7.p2.1)\.
- A\. Vergari, N\. Di Mauro, and G\. Van den Broeck \(2019\)Tractable probabilistic models: Representations, algorithms, learning, and applications\.Tutorial at the 35th Conference on Uncertainty in Artificial Intelligence \(UAI\)\.Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p4.1),[§7](https://arxiv.org/html/2607.20483#S7.p2.1)\.
- H\. Zhang, M\. Dang, N\. Peng, and G\. V\. den Broeck \(2023a\)Tractable control for autoregressive language generation\.External Links:2304\.07438,[Link](https://arxiv.org/abs/2304.07438)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p4.1),[§2](https://arxiv.org/html/2607.20483#S2.p1.3),[§2](https://arxiv.org/html/2607.20483#S2.p5.2)\.
- H\. Zhang, M\. Dang, N\. Peng, and G\. Van den Broeck \(2023b\)Tractable control for autoregressive language generation\.InInternational Conference on Machine Learning,pp\. 40932–40945\.Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p4.1)\.
- H\. Zhang, P\. Kung, M\. Yoshida, G\. V\. den Broeck, and N\. Peng \(2024\)Adaptable logical control for large language models\.External Links:2406\.13892,[Link](https://arxiv.org/abs/2406.13892)Cited by:[§1](https://arxiv.org/html/2607.20483#S1.p4.1),[§2](https://arxiv.org/html/2607.20483#S2.p6.1),[§4](https://arxiv.org/html/2607.20483#S4.p1.7),[§5\.1](https://arxiv.org/html/2607.20483#S5.SS1.p1.4),[§5\.2](https://arxiv.org/html/2607.20483#S5.SS2.p1.1)\.

## Appendix ADynamic Programming Algorithms

### A\.1Algorithm 1

Algorithm 1Evaluate equation 1 to computep​\(qn,γn=ϵ∣qt,γt\)p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}\)1:Cache of probabilities

C​\[u,qu,q1,γ1\]=p​\(qu,γu=ϵ∣q1,γ1\)C\[u,q\_\{u\},q\_\{1\},\\gamma\_\{1\}\]=p\(q\_\{u\},\\gamma\_\{u\}=\\epsilon\\mid q\_\{1\},\\gamma\_\{1\}\)
2:Configuration

\(qt,γt\)\(q\_\{t\},\\gamma\_\{t\}\)where

qt∈Qq\_\{t\}\\in Q,

γt∈Γh\\gamma\_\{t\}\\in\\Gamma^\{h\}
3:

acc←𝟎\\textit\{acc\}\\leftarrow\\mathbf\{0\}⊳\\triangleright\|Q\|×\(n−t\+1\)\|Q\|\\times\(n\-t\+1\)matrix

4:

5:for all

q∈Qq\\in Q,

q′∈Qq^\{\\prime\}\\in Qdo⊳\\trianglerightInitialize accumulator using bottom\-of\-stackγt​\[h−1\]\\gamma\_\{t\}\[h\-1\]

6:for

d←0d\\leftarrow 0to

n−tn\-tdo

7:

acc\[q′,d\]\+=C\[d,q′,q,γt\[h−1\]\]\\textit\{acc\}\[q^\{\\prime\},d\]\\mathrel\{\+\}=C\[d,q^\{\\prime\},q,\\gamma\_\{t\}\[h\-1\]\]
8:endfor

9:endfor

10:

11:for

s←h−2s\\leftarrow h\-2down to

0do

12:

acc′←𝟎\\textit\{acc\}^\{\\prime\}\\leftarrow\\mathbf\{0\}⊳\\triangleright\|Q\|×\(n−t\+1\)\|Q\|\\times\(n\-t\+1\)matrix

13:for

d←0d\\leftarrow 0to

n−tn\-tdo⊳\\trianglerightDurationdd

14:for

u←0u\\leftarrow 0to

dddo⊳\\trianglerightSplit indexuu

15:for all

q∈Qq\\in Q,

q′∈Qq^\{\\prime\}\\in Qdo⊳\\trianglerightRestatement of equation 1

16:

acc′\[q′,d\]\+=C\[u,q′,q,γt\[s\]\)⋅acc\[q,d−u\]\\textit\{acc\}^\{\\prime\}\[q^\{\\prime\},d\]\\mathrel\{\+\}=C\[u,q^\{\\prime\},q,\\gamma\_\{t\}\[s\]\)\\cdot\\textit\{acc\}\[q,d\-u\]
17:endfor

18:endfor

19:endfor

20:

acc←acc′\\textit\{acc\}\\leftarrow\\textit\{acc\}^\{\\prime\}
21:endfor

22:

23:return

acc​\[qt,n−t\]\\textit\{acc\}\[q\_\{t\},\\,n\-t\]

### A\.2Algorithm 2

Algorithm 2Evaluate equation 4 to computep​\(zn,qn,γn=ϵ∣zt,qt,γt\)p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}\)1:Cache of probabilities

C​\[u,zu,qu,z1,q1,γ1\]=p​\(zu,qu,γu=ϵ∣z1,q1,γ1\)C\[u,z\_\{u\},q\_\{u\},z\_\{1\},q\_\{1\},\\gamma\_\{1\}\]=p\(z\_\{u\},q\_\{u\},\\gamma\_\{u\}=\\epsilon\\mid z\_\{1\},q\_\{1\},\\gamma\_\{1\}\)
2:Configuration

\(qt,γt\)\(q\_\{t\},\\gamma\_\{t\}\)where

qt∈Qq\_\{t\}\\in Q,

γt∈Γh\\gamma\_\{t\}\\in\\Gamma^\{h\}
3:

acc←𝟎\\textit\{acc\}\\leftarrow\\mathbf\{0\}⊳\\triangleright\|Q\|×\(n−t\+1\)×\|Z\|\|Q\|\\times\(n\-t\+1\)\\times\|Z\|matrix

4:

5:for all

q∈Qq\\in Q,

q′∈Qq^\{\\prime\}\\in Qdo⊳\\trianglerightInitialize accumulator using bottom\-of\-stackγt​\[h−1\]\\gamma\_\{t\}\[h\-1\]

6:for all

z∈Z,z′∈Zz\\in Z,z^\{\\prime\}\\in Zdo

7:for

d←0d\\leftarrow 0to

n−tn\-tdo

8:

acc\[q′,d,z′\]\+=C\[d,z′,q′,z,q,γt\[h−1\]\]\\textit\{acc\}\[q^\{\\prime\},d,z^\{\\prime\}\]\\mathrel\{\+\}=C\[d,z^\{\\prime\},q^\{\\prime\},z,q,\\gamma\_\{t\}\[h\-1\]\]
9:endfor

10:endfor

11:endfor

12:

13:for

s←h−2s\\leftarrow h\-2down to

0do

14:

acc′←𝟎\\textit\{acc\}^\{\\prime\}\\leftarrow\\mathbf\{0\}⊳\\triangleright\|Q\|×\(n−t\+1\)×\|Z\|\|Q\|\\times\(n\-t\+1\)\\times\|Z\|matrix

15:for

d←0d\\leftarrow 0to

n−tn\-tdo⊳\\trianglerightDurationdd

16:for

u←0u\\leftarrow 0to

dddo⊳\\trianglerightSplit indexuu

17:for all

q∈Qq\\in Q,

q′∈Qq^\{\\prime\}\\in Qdo

18:for all

z∈Zz\\in Z,

z′∈Zz^\{\\prime\}\\in Zdo⊳\\trianglerightRestatement of equation 4

19:

acc′\[q′,d,z′\]\+=C\[u,z′,q′,z,q,γt\[s\]\)⋅acc\[q,d−u,z\]\\textit\{acc\}^\{\\prime\}\[q^\{\\prime\},d,z^\{\\prime\}\]\\mathrel\{\+\}=C\[u,z^\{\\prime\},q^\{\\prime\},z,q,\\gamma\_\{t\}\[s\]\)\\cdot\\textit\{acc\}\[q,d\-u,z\]
20:endfor

21:endfor

22:endfor

23:endfor

24:

acc←acc′\\textit\{acc\}\\leftarrow\\textit\{acc\}^\{\\prime\}
25:endfor

26:

27:return

acc​\[qt,n−t,zt\]\\textit\{acc\}\[q\_\{t\},\\,n\-t,z\_\{t\}\]

## Appendix BDerivations of stack decomposability equations

### B\.1Derivation of equation 1

To derive equation 1, we must ground the expression below in probability expressions conditioned upon single stack elements, rather than the entire stackγt\\gamma\_\{t\}\.

p​\(qn,γn=ϵ∣qt,γt\)p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}\)
For the entire stackv​WvWto reduce toϵ\\epsiloninn−tn\-ttokens, at some point in the reduction the stack must be equal toWW\. Applying any transition consumes the top element of the stack and pushes some number of stack elements back onto the stack\. The minimum number of elements that can be pushed onto the stack is0, in which case the stack after applying the transition is11element smaller than the stack prior\. No matter how many elements are pushed, each of those elements must be popped one transition at a time for the entire stack to reduce toϵ\\epsilon\. This iterative popping necessarily reduces the stackv​WvWtoWWat some point in the reduction toϵ\\epsilon, because the DPDA cannot pop the top element ofWWwithout the stack being equal toWW\.

By the law of total probability, we can introduce a cut in the derivation, supposing a number of tokensuuand stateqt\+uq\_\{t\+u\}which correspond to reducing the stack toWWinuutokens without having reduced the stack toWWprior to consuminguutokens\.

p​\(qn,γn=ϵ∣qt,γt=v​W\)=∑u=0n−t∑qt\+u∈Q\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}p\(qt\+u,γt\+u=W,W∉γt:t\+u−1,qn,γn=ϵ∣qt,γt=vW\)\\displaystyle p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW\)
By Bayes theorem we can decompose the above equation\.

p​\(qn,γn=ϵ∣qt,γt=v​W\)=∑u=0n−t∑qt\+u∈Q\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=\\vphantom\{\\sum\}\\smash\{\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}\}\\,\\,p\(qn,γn=ϵ∣qt,γt=vW,qt\+u,γt\+u=W,W∉γt:t\+u−1\)⋅\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW,q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\)\\cdotp\(qt\+u,γt\+u=W,W∉γt:t\+u−1∣qt,γt=vW\)\\displaystyle p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid q\_\{t\},\\gamma\_\{t\}=vW\)
By the Markovian conditional independence\(qt,γt\)⟂⟂\(qt\+k,γt\+k\)∣\(qt\+l,γq\+l\),∀k,l∈ℕ,l<k\(q\_\{t\},\\gamma\_\{t\}\)\\perp\\\!\\\!\\\!\\\!\\perp\(q\_\{t\+k\},\\gamma\_\{t\+k\}\)\\mid\(q\_\{t\+l\},\\gamma\_\{q\+l\}\),\\forall k,l\\in\\mathbb\{N\},l<k, future DPDA configurations are isolated from prior configurations given knowledge of an intermediate configuration\.

p​\(qn,γn=ϵ∣qt,γt=v​W\)=∑u=0n−t∑qt\+u∈Q\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=\\smash\{\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}\}\\,\\,p\(qn,γn=ϵ∣qt\+u,γt\+u=W\)⋅\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\\cdotp\(qt\+u,γt\+u=W,W∉γt:t\+u−1∣qt,γt=vW\)\\displaystyle\\boxed\{p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid q\_\{t\},\\gamma\_\{t\}=vW\)\}The boxed probability expression can be rewritten as a weighted model count over all token sequences that satisfy the automata constraints described in the expression\. We defineFFas the set of all token strings which reduce the configuration\(qt,v​W\)\(q\_\{t\},vW\)to\(qt\+u,W\)\(q\_\{t\+u\},W\)inuutokens without reducing the stack toWWin fewer thanuutokens:

F=\{xt\+1:t\+u:\(qt,γt=v​W\)​⟶xt\+1:t\+u​\(qt\+u,γt\+u=W\)∧W∉γt:t\+u−1\}F=\\\{x\_\{t\+1:t\+u\}:\(q\_\{t\},\\gamma\_\{t\}=vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}\\\}Using this expression of our constraint, we write the weighted model count as:

p\(qt\+u,γt\+u=W,W∉γt:t\+u−1∣qt,γt=vW\)=∑xt\+1:t\+up\(xt\+1:t\+u\)⋅𝟙\[𝕩𝕥\+𝟙:𝕥\+𝕦∈𝔽\]p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=\\sum\_\{\\mathclap\{x\_\{t\+1:t\+u\}\}\}p\(x\_\{t\+1:t\+u\}\)\\cdot\\mathbbold\{1\}\[x\_\{t\+1:t\+u\}\\in F\]
The DPDA can only follow transition rules which correspond to elements on the top of the stack during its derivation\. Our constraint requires that at no point in derivation prior tot\+1t\+1is the stack equal toWW, meaning the top element ofWWis never at the top of the stack prior to the final configuration\(qt\+u,γt\+u\)\(q\_\{t\+u\},\\gamma\_\{t\+u\}\)\. These two facts demonstrate the independence of\(qt,v​W\)​⟶xt\+1:t\+u​\(qt\+u,W\)\(q\_\{t\},vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},W\)fromWWwhenW∉γt:t\+u−1W\\not\\in\\gamma\_\{t:t\+u\-1\}\. If the top element ofWWnever affects the transitions taken, then the reduction of the stack toWWcan be calculated in the absence ofWW\. See appendix C for a proof of this equivalence\.

G=\{xt\+1:t\+u:\(qt,γt=v\)​⟶xt\+1:t\+u​\(qt\+u,γt\+u=ϵ\)\}G=\\\{x\_\{t\+1:t\+u\}:\(q\_\{t\},\\gamma\_\{t\}=v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\)\\\}
Using this logical equivalence, we can rewrite our weighted model count\.

p\(qt\+u,γt\+u=W,W∉γt:t\+u−1∣qt,γt=vW\)=∑xt\+1:t\+up\(xt\+1:t\+u\)⋅𝟙\[𝕩𝕥\+𝟙:𝕥\+𝕦∈𝔾\]p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=\\sum\_\{\\mathclap\{x\_\{t\+1:t\+u\}\}\}p\(x\_\{t\+1:t\+u\}\)\\cdot\\mathbbold\{1\}\[x\_\{t\+1:t\+u\}\\in G\]The weighted model count can be converted back into a probability statement about the contents of the DPDA configuration\.

p\(qt\+u,γt\+u=W,W∉γt:t\+u−1∣qt,γt=vW\)=p\(qt\+u,γt\+u=ϵ∣qt,γt=v\)p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=v\)This equivalence allows us to rewrite our reduction, leaving us with equation 1\.

p​\(qn,γn=ϵ∣qt,γt=v​W\)=∑u=0n−t∑qt\+u∈Q\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}p​\(qn,γn=ϵ∣qt\+u,γt\+u=W\)⋅p​\(qt\+u,γt\+u=ϵ∣qt,γt=v\)\\displaystyle p\(q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\\cdot p\(q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=v\)

### B\.2Derivation of equation 4

Similarly to appendix B\.1, to derive equation 4 we must ground the probability expression below in probability expressions conditioned on single stack elements, rather than the entire stackγt\\gamma\_\{t\}\.

p​\(zn,qn,γn=ϵ∣zt,qt,γt\)p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}\)
By the law of total probability, we can introduce a cut at tokenuuinto our derivation\. For any derivation that pops all elements of the stackv​WvW, at some pointuutokens in the future the stack must be equal to the remainder of the stackWWbecause the stack can pop at most one element per transition\. At that point where the stack is equal toWW, there will be an intermediate HMM hidden statezt\+uz\_\{t\+u\}and an intermediate DPDA stateqt\+uq\_\{t\+u\}\. We sum over all possible values of both of those variables at this intermediate state in the derivation\.

p\\displaystyle p\(zn,qn,γn=ϵ∣zt,qt,γt=v​W\)=\\displaystyle\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)=∑u=0n−t∑qt\+u∈Q∑zt\+up\(zn,qn,γn=ϵ,zt\+u,qt\+u,γt\+u=W,W∉γt:t\+u−1∣zt,qt,γt=vW\)\\displaystyle\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}\\sum\_\{z\_\{t\+u\}\}\\,p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon,z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)
By Bayes’ theorem, we can separate the parts of the above expression which don’t correspond to the state at tokennn\.

p\\displaystyle p\(zn,qn,γn=ϵ∣zt,qt,γt=v​W\)=\\displaystyle\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)=∑u=0n−t∑qt\+u∈Q∑zt\+up\(zn,qn,γn=ϵ∣zt\+u,qt\+u,γt\+u=W,W∉γt:t\+u−1,zt,qt,γt=vW\)⋅\\displaystyle\\vphantom\{\\sum^\{1\}\}\\smash\{\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}\\sum\_\{z\_\{t\+u\}\}\}\\,\\,p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\},z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)\\cdotp\(zt\+u,qt\+u,γt\+u=W,W∉γt:t\+u−1∣zt,qt,γt=vW\)\\displaystyle\\hskip 68\.28644pt\\mathrlap\{p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)\}By the Markov independencies\(qt,γt\)⟂⟂\(qt\+k,γt\+k\)∣\(qt\+l,γt\+l\)\(q\_\{t\},\\gamma\_\{t\}\)\\perp\\\!\\\!\\\!\\\!\\perp\(q\_\{t\+k\},\\gamma\_\{t\+k\}\)\\mid\(q\_\{t\+l\},\\gamma\_\{t\+l\}\)andzt⟂⟂zt\+k∣zt\+lz\_\{t\}\\perp\\\!\\\!\\\!\\\!\\perp z\_\{t\+k\}\\mid z\_\{t\+l\}for allk,l∈ℕ,l<kk,l\\in\\mathbb\{N\},l<k, the state of the HMM and configuration of the DPDA at tokennncan be isolated from the state and configuration at tokenttgiven knowledge of the intermediate state and configuration at tokent\+ut\+u\.

p\\displaystyle p\(zn,qn,γn=ϵ∣zt,qt,γt=v​W\)=\\displaystyle\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)=∑u=0n−t∑qt\+u∈Q∑zt\+up\(zn,qn,γn=ϵ∣zt\+u,qt\+u,γt\+u=W\)⋅\\displaystyle\\vphantom\{\\sum^\{1\}\}\\smash\{\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}\\sum\_\{z\_\{t\+u\}\}\}\\,p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\\cdotp\(zt\+u,qt\+u,γt\+u=W,W∉γt:t\+u−1∣zt,qt,γt=vW\)\\displaystyle\\hskip 64\.87224pt\\boxed\{p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)\}The boxed probability expression can be rewritten as a weighted model count over all sequences that satisfy the automata constraints described in the expression\. As in appendix B\.1, we define the set of all tokens sequences which satisfy the automata constraint as the setFF\.

F=\{xt\+1:t\+u:\(qt,γt=v​W\)​⟶xt\+1:t\+u​\(qt\+u,γt\+u=W\)∧W∉γt:t\+u−1\}F=\\\{x\_\{t\+1:t\+u\}:\(q\_\{t\},\\gamma\_\{t\}=vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}\\\}
p\\displaystyle p\(zt\+u,qt\+u,γt\+u=W,W∉γt:t\+u−1∣zt,qt,γt=vW\)=∑xt\+1:t\+up\(zt\+u,xt\+1:t\+u∣zt\)⋅𝟙\[𝕩𝕥\+𝟙:𝕥\+𝕦∈𝔽\]\\displaystyle\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)=\\sum\_\{\\mathclap\{x\_\{t\+1:t\+u\}\}\}\\,p\(z\_\{t\+u\},x\_\{t\+1:t\+u\}\\mid z\_\{t\}\)\\cdot\\mathbbold\{1\}\[x\_\{t\+1:t\+u\}\\in F\]
Using the proof specified in appendix C, this logical equivalence can be rewritten:

G=\{xt\+1:t\+u:\(qt,γt=v\)​⟶xt\+1:t\+u​\(qt\+u,γt\+u=ϵ\)\}G=\\\{x\_\{t\+1:t\+u\}:\(q\_\{t\},\\gamma\_\{t\}=v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\)\\\}This logical equivalence allows us to rewrite our weighted model count as

p\(zt\+u,qt\+u,γt\+u=W,W∉γt:t\+u−1∣zt,qt,γt=vW\)=∑xt\+1:t\+u\\displaystyle p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)=\\sum\_\{\\mathclap\{x\_\{t\+1:t\+u\}\}\}p​\(zt\+u,xt\+1:t\+u∣zt\)⋅𝟙​\[𝕩𝕥\+𝟙:𝕥\+𝕦∈𝔾\]\\displaystyle\\,p\(z\_\{t\+u\},x\_\{t\+1:t\+u\}\\mid z\_\{t\}\)\\cdot\\mathbbold\{1\}\[x\_\{t\+1:t\+u\}\\in G\]The weighted model count can be converted back into a probability statement about the contents of the DPDA configuration\.

p\(zt\+u,qt\+u,γt\+u=W,W∉γt:t\+u−1∣zt,qt,γt=vW\)=p\(zt\+u,qt\+u,γt\+u=ϵ∣zt,qt,γt=v\)p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W,W\\not\\in\\gamma\_\{t:t\+u\-1\}\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=vW\)=p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=v\)Rewriting our reduction using the above equivalence, we get equation 4\.

p​\(zn,qn,γn=ϵ∣qt,γt=v​W\)=∑u=0n−t∑qt\+u∈Q\\displaystyle p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid q\_\{t\},\\gamma\_\{t\}=vW\)=\\sum\_\{u=0\}^\{n\-t\}\\sum\_\{q\_\{t\+u\}\\in Q\}p\(zn,qn,γn=ϵ∣zt\+u,qt\+u,γt\+u=W\)⋅\\displaystyle p\(z\_\{n\},q\_\{n\},\\gamma\_\{n\}=\\epsilon\\mid z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=W\)\\cdotp​\(zt\+u,qt\+u,γt\+u=ϵ∣zt,qt,γt=v\)\\displaystyle p\(z\_\{t\+u\},q\_\{t\+u\},\\gamma\_\{t\+u\}=\\epsilon\\mid z\_\{t\},q\_\{t\},\\gamma\_\{t\}=v\)

## Appendix CProof that the stack remainder is irrelevant to reducing the top stack element in exactlyuutokens

Here we prove that the set of token sequences that reduce a DPDA configurationCt=\(qt,v​W\)C\_\{t\}=\(q\_\{t\},vW\)toCt\+u=\(qt\+u,W\)C\_\{t\+u\}=\(q\_\{t\+u\},W\)in exactlyuutokens without reducing the stack toWWin fewer thanuutokens are equivalent to the set of token sequences that reduce the configurationCt=\(qt,v\)C\_\{t\}=\(q\_\{t\},v\)toCt\+u=\(qt\+u,ϵ\)C\_\{t\+u\}=\(q\_\{t\+u\},\\epsilon\)in exactlyuutokens\.

We prove this by demonstrating that at every intermediate configuration betweenttandt\+ut\+u,Ci=\(qi,γi\)C\_\{i\}=\(q\_\{i\},\\gamma\_\{i\}\), the set of available transitions to the DPDA are identical under these two constraints\. This means that the set of tokens accepted at every intermediate configuration are identical, and consuming any of those tokens corresponds to an identical resultant configuration between both of the above conditions \(modulo the bottom of the stack,WWorϵ\\epsilon\)\. By that fact, the set of sequences that transition a DPDAAAbetween configurations\(qt,v​W\)→\(qt\+u,W\)∧W∉γt:t\+u−1\(q\_\{t\},vW\)\\rightarrow\(q\_\{t\+u\},W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}is the same as the set of sequences that transitionAAbetween configurations\(qt,v\)→\(qt\+u,ϵ\)\(q\_\{t\},v\)\\rightarrow\(q\_\{t\+u\},\\epsilon\)\.

We consider this over the intersection of two sets of two cases\. The first set of cases conditions on the structure of the stack\. Either there is one stack element,yy, aboveWW/ϵ\\epsilon, or there are multiple elements aboveWW/ϵ\\epsilon, which we represent as the listYY\. The second set of cases is whether the transition being made is the final transition moving into the configurationCt\+uC\_\{t\+u\}, or whether more than one transition will be made before entering the final configuration\. Across all combinations of these cases, the available sets of transitions to the DPDA are identical\.

There may be constraints on the available transitions in a particular configuration that are unique to the DPDAAAbeing analyzed, such as the fact that certain configurations may be impossible to reduce in the required token limit\. Under both of the cases,WWandϵ\\epsilon, studied here, those constraints apply as extra filters on the available transitions \(and equivalently, the available token sequences\)\. These extra filters all apply to both constraints evaluated, and so have no means of affecting their equivalence\.

### C\.1Case 1: The intermediate configuration is in the form\(qi,y​W\)\(q\_\{i\},yW\)or\(qi,y\)\(q\_\{i\},y\)and this is the final transition\.

Under the constraint\(qt,v​W\)​⟶xt\+1:t\+u​\(qt\+u,W\)∧W∉γt:t\+u−1\(q\_\{t\},vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}, if the configuration is in the form\(qi,y​W\)\(q\_\{i\},yW\)and this is the final transition, the DPDA must use the final transition to reduce toWWto ensure the stack isWWafter processing all transitions\. The set of transitions available to the DPDA are in the form\(qi,⋅,y,qt\+u,ϵ\)\(q\_\{i\},\\cdot,y,q\_\{t\+u\},\\epsilon\)\.

Under the constraint\(qt,v\)​⟶xt\+1:t\+u​\(qt\+u,ϵ\)\(q\_\{t\},v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\epsilon\), if the configuration is in the form\(qi,y\)\(q\_\{i\},y\)and this is the final transition, for the same reason as in the prior constraint, the DPDA must use the final transition to reduce toϵ\\epsilonto satisfy the constraint\. The set of transitions available to the DPDA are in the form\(qi,⋅,y,qt\+u,ϵ\)\(q\_\{i\},\\cdot,y,q\_\{t\+u\},\\epsilon\)\.

✓The set of transitions available under these two constraints are identical in Case 1\.

### C\.2Case 2: The intermediate configuration is in the form\(qi,Y​W\)\(q\_\{i\},YW\)or\(qi,Y\)\(q\_\{i\},Y\)and this is the final transition

Under the constraint\(qt,v​W\)​⟶xt\+1:t\+u​\(qt\+u,W\)∧W∉γt:t\+u−1\(q\_\{t\},vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}, the list of stack elementsYYcannot be reduced in a single transition, because at most one element can be popped from the stack in a single transition, andYYhas at least two elements that must be popped for the stack to becomeWW\. There are no valid transitions in this case\.

Under the\(qt,v\)​⟶xt\+1:t\+u​\(qt\+u,ϵ\)\(q\_\{t\},v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\epsilon\)constraint, the list of stack elementsYYcannot be reduced in a single transition for the same reason as above\. There are no valid transitions in this case either\.

✓The set of available transitions under these two constraints are identical in Case 2\.

### C\.3Case 3: The intermediate configuration is in the form\(qi,y​W\)\(q\_\{i\},yW\)or\(qi,y\)\(q\_\{i\},y\)and this is not the final transition

Under the constraint\(qt,v​W\)​⟶xt\+1:t\+u​\(qt\+u,W\)∧W∉γt:t\+u−1\(q\_\{t\},vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}, pop operations are not allowed in this case, because that would result in a stackWWbefore the final transition, violating the second condition of the constraint\. For that reason, the only transition rules allowed in this case are in the form\(qi,⋅,y,q^,Y^\),q^∈Q,Y^∈Γ≥1\(q\_\{i\},\\cdot,y,\\hat\{q\},\\hat\{Y\}\),\\hat\{q\}\\in Q,\\hat\{Y\}\\in\\Gamma^\{\\geq 1\}\.

Under the\(qt,v\)​⟶xt\+1:t\+u​\(qt\+u,ϵ\)\(q\_\{t\},v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\epsilon\)constraint, in this case pop operations are also not allowed, but for a slightly different reason\. The transition relation on DPDAs, as described inHopcroft and Ullman \[[1979](https://arxiv.org/html/2607.20483#bib.bib19)\], is a finite subset ofQ×\(Σ∪\{ϵ\}\)×Γ×Q×Γ∗Q\\times\(\\Sigma\\cup\\\{\\epsilon\\\}\)\\times\\Gamma\\times Q\\times\\Gamma^\{\*\}\. The third component of each transition relation is the stack element input required by the transition, specified as an element ofΓ\\Gamma, the set of all stack symbols\. Transitions therefore cannot take as their stack element input the empty stackϵ\\epsilon, asϵ\\epsilonis not a stack symbol\. This means that after performing a pop operation, no further transitions are possible\. However, that would mean that this was the final transition in the production of\(qt\+u,ϵ\)\(q\_\{t\+u\},\\epsilon\), violating this case’s constraint that this is not the final transition\. Performing a pop operation forces us to violate the constraint of this case, and so is not allowed\. Due to this, the set of available transitions in this case and under this constraint are those transition rules in the form\(qi,⋅,y,q^,Y^\),q^∈Q,Y^∈Γ≥1\(q\_\{i\},\\cdot,y,\\hat\{q\},\\hat\{Y\}\),\\hat\{q\}\\in Q,\\hat\{Y\}\\in\\Gamma^\{\\geq 1\}

✓The set of available transitions under these two constraints are identical in Case 3\.

### C\.4Case 4: The intermediate configuration is in the form\(qi,Y​W\)\(q\_\{i\},YW\)or\(qi,Y\)\(q\_\{i\},Y\)and this is not the final transition

Under the\(qt,v​W\)​⟶xt\+1:t\+u​\(qt\+u,W\)∧W∉γt:t\+u−1\(q\_\{t\},vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}constraint, there are no additional constraints on the set of available transitions in this case\. Pop, preserve, and push transitions are all valid in this state, because none of them necessarily preclude the possibility of transitioning to the specified final configuration in future transitions\.

Under the\(qt,v\)​⟶xt\+1:t\+u​\(qt\+u,ϵ\)\(q\_\{t\},v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\epsilon\)constraint, no additional constraints are put on the set of available transitions in this case for the same reason as above\.

✓The set of available transitions under these two constraints are identical in Case 4\.

### C\.5Summary

In all cases during their derivation, the set of available transitions is identical between both\(qt,v​W\)​⟶xt\+1:t\+u​\(qt\+u,W\)∧W∉γt:t\+u−1\(q\_\{t\},vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}and\(qt,v\)​⟶xt\+1:t\+u​\(qt\+u,ϵ\)\(q\_\{t\},v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\epsilon\)\. This means that the set of token sequences that reduce\(qt,v​W\)\(q\_\{t\},vW\)to\(qt\+u,W\)\(q\_\{t\+u\},W\)without reducing toWWbeforet\+ut\+utokens is identical to the set of token sequences which reduce\(qt,v\)\(q\_\{t\},v\)to\(qt\+u,ϵ\)\(q\_\{t\+u\},\\epsilon\)\. As sets of token sequences,

\{xt\+1:t\+u:\(qt,v​W\)​⟶xt\+1:t\+u​\(qt\+u,W\)∧W∉γt:t\+u−1\}=\{xt\+1:t\+u:\(qt,v\)​⟶xt\+1:t\+u​\(qt\+u,ϵ\)\}\\\{x\_\{t\+1:t\+u\}:\(q\_\{t\},vW\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},W\)\\land W\\not\\in\\gamma\_\{t:t\+u\-1\}\\\}=\\\{x\_\{t\+1:t\+u\}:\(q\_\{t\},v\)\\overset\{x\_\{t\+1:t\+u\}\}\{\\longrightarrow\}\(q\_\{t\+u\},\\epsilon\)\\\}