Grab a Coffee: Future-Aware Guidance for Discrete Diffusion with Compiled Objectives

# Future-Aware Guidance for Discrete Diffusion with Compiled Objectives
Source: [https://arxiv.org/html/2609.35924](https://arxiv.org/html/2609.35924)
Hua \(Edward\) XUAffiliation:Data Science and Analytics Thrust,The Hong Kong University of Science and Technology \(Guangzhou\), Guangzhou, ChinaDongxin LiAffiliation:Data Science and Analytics Thrust,The Hong Kong University of Science and Technology \(Guangzhou\), Guangzhou, ChinaGwen Yidou\-WengGuy Van den BroeckAffiliation:Department of Computer Science, University of California, Los Angeles, USAWei WangAffiliation:Data Science and Analytics Thrust,The Hong Kong University of Science and Technology \(Guangzhou\), Guangzhou, ChinaAnji LiuAffiliation:School of Computing, National University of Singapore, Singapore\*Equal contribution\.

###### Abstract

Discrete diffusion models generate sequences by iteratively resolving multiple tokens in parallel, offering a flexible alternative to left\-to\-right generation\. However, guiding this process with a sequence\-level objective is difficult because the value of one unresolved token depends on the other tokens with which it can form a high\-reward sequence\. Enumerating all such completions makes the whole guidance computation grow exponentially with the number of unresolved positions\. We introduceCoffee, a plug\-and\-play framework that avoids this enumeration by separating sequence dependence from the objective\. At each diffusion step, a target\-free carrier absorbs the marginal token distributions predicted by the denoiser to construct a joint model over the unresolved tokens, while a compiled finite\-state model records how their combinations affect the sequence\-level preference\. Pairing their states allowsCoffeeto transfer global preferences to unresolved positions and sample a clean reconstruction without retraining the diffusion model\. The same framework supports explicit hard constraints and learned soft objectives\. We evaluateCoffeeacross multiple symbolic, language, and biological benchmarks, where it achieves strong control results with task\-dependent quality and diversity trade\-offs\. By making objectives available to inference rather than only evaluation,Coffeebrings joint conditioning, completion\-weighted guidance, and optimization\-based constraints into pretrained neural generation, showing the potential of neural\-symbolic methods in diffusion guidance\.

## 1Introduction

Discrete diffusion models offer a flexible approach to generating language and biological sequences\([Nie et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib29);[Ye et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib30);[Yang et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib31)\)\. By repeatedly reconstructing tokens from corrupted inputs, they allow multiple positions to be predicted together using context from either side of the sequence\. In many applications, however, generating plausible samples is only a starting point: the output should also satisfy a constraint, express a desired attribute, or achieve a high sequence\-level reward\.111In this paper, we are using “reward”, “condition”, “constraint” and “preference” interchangeably\.Inference\-time guidance offers a way to introduce these objectives without retraining the pretrained generator\. The challenge is to turn a preference over complete sequences into useful guidance while the current state is still partially corrupted\. Consider the masked sentence\[MASK\] \[MASK\] is in \[MASK\]in Fig\.[1](https://arxiv.org/html/2609.35924#S1.F1), with a preference for the phraseNew York\. The preference concerns the termNew Yorktogether, but a scorer itself without knowing joint distribution of tokens does not specify how the unresolved tokens should be chosen jointly\. Directly sampling from the distributions given by the denoiser may produce mismatched combinations such asNew Kong, failing to capture cross\-token dependence\. The scorer’s preference may also affect the distributions at other positions, ideally coupling the preferred term withUSA, though the scorer itself may not be able to associate them together\. Therefore, using such reward to guide the generation process requires a joint model which can couple these choices and propagate the phrase preference to the country prediction through the association betweenNew YorkandUSA, even though the scorer does not directly reward the country\. Effective guidance therefore needs to account for both*how token choices depend on one another*and*how their combinations affect the sequence\-level objective*\.

More generally, letxtx\_\{t\}denote the current diffusion state andx0x\_\{0\}a possible clean reconstruction\. Given a neutral, unguided distributionq0​\(x0∣xt\)q\_\{0\}\(x\_\{0\}\\mid x\_\{t\}\)which models the joint token distribution before imposing conditionCC, and a nonnegative sequence weightWC​\(x0\)W\_\{C\}\(x\_\{0\}\)indicating sequence\-level preference, for a candidate tokenuuat an unresolved positionii, we consider the guided reconstruction distribution

qC\(x0i=u∣xt\)∝q0\(x0i=u∣xt\)𝔼q0\[WC\(X0\)∣xt,X0i=u\]\.q\_\{C\}\(x\_\{0\}^\{i\}=u\\mid x\_\{t\}\)\\propto q\_\{0\}\(x\_\{0\}^\{i\}=u\\mid x\_\{t\}\)\\,\\mathbb\{E\}\_\{q\_\{0\}\}\\\!\\left\[W\_\{C\}\(X\_\{0\}\)\\mid x\_\{t\},\\;X\_\{0\}^\{i\}=u\\right\]\.\(1\)Our goal is to sample fromqCq\_\{C\}, which brings two computation challenges\.\(1\)The expectation depends on how unresolved tokens occur together, i\.e\. the joint distributionq0q\_\{0\}, whereas a single denoiser can only provide the factorized approximation∏i∈ℳtpθ​\(x0i∣xt\)\\prod\_\{i\\in\\mathcal\{M\}\_\{t\}\}p\_\{\\theta\}\(x\_\{0\}^\{i\}\\mid x\_\{t\}\)that does not by itself specify these dependencies\. With unresolved positionsℳt\\mathcal\{M\}\_\{t\}, naively computing the joint requires\|𝒱\|\|ℳt\|\|\\mathcal\{V\}\|^\{\|\\mathcal\{M\}\_\{t\}\|\}operations over vocabulary𝒱\\mathcal\{V\}\.\(2\)Even with access toq0​\(x0∣xt\)q\_\{0\}\(x\_\{0\}\\mid x\_\{t\}\), evaluating the expectation ofWCW\_\{C\}still requires scoring the sequence\-level preference over all possible completions separately, which also requires\|𝒱\|\|ℳt\|\|\\mathcal\{V\}\|^\{\|\\mathcal\{M\}\_\{t\}\|\}operations \(Fig\.[1](https://arxiv.org/html/2609.35924#S1.F1)\(a\)\)\. The problem is thus not simply to score a completed sequence, butto obtain coupling token choicesper diffusion step andto evaluate sequence\-level preferenceswhile the current state is still partially corrupted\.

Figure 1:Sequence\-level guidance combines preferences with a model of possible completions\.\(a\) Each root\-to\-leaf path specifies a clean reconstruction with neutral completion weights given byqθq\_\{\\theta\}\. With two token choices at each of three unresolved positions, explicit enumeration produces232^\{3\}leaves\. Calculating quantities in Eq\.[1](https://arxiv.org/html/2609.35924#S1.E1)with such way is therefore hard with exponential complexity\. \(b\)Coffeeuses state machines to represent token dependence and record pattern progress\. Their product permits histories reaching the same state at the same position to share a continuation calculation, replacing path\-by\-path enumeration within the compiled model\.Existing diffusion\-guidance methods approach control through several routes, including attribute estimates on noisy inputs\([Nisonoff et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib8);[Schiff et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib9)\)and clean\-sample search that evaluates rewards on completed sequences and iteratively refines them\([Phunyaphibarn and Sung, 2026](https://arxiv.org/html/2609.35924#bib.bib11)\)\. These methods provide ways to use sequence\-level objectives during generation\. A separate line of work restores the cross\-position dependence absent from factorized denoiser outputs\. CoDD, for example, augments parallel diffusion predictions with a joint model\([Li et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib12)\)\. Together, these directions provide the two ingredients needed by the example above: a sequence\-level preference and a model of how token choices depend on each other\.

We then introduceCoffee, a plug\-and\-play inference\-time guidance framework based on graphical models\. A target\-free graphical model, called the*dependence carrier*, is used to capture the joint dependency with diffusion outputs, and a*compiled objective*expresses the sequence preference through local state transitions and weights, and is able to score the sequence\-level preference on a corrupted sentence\. Here, our graphical model summarizes the information needed by the remaining computation into latent states, and hence we are able to run dynamic programming \(DP\) algorithms on the latent states, which avoids explicitly enumerating all the complete sequences\. With proper parameterization and model construction, the resulting cost will be polynomial in the problem size, instead of exponential as we previously discussed\. At each diffusion step,Coffeeconstructs this joint model from the current denoiser predictions, computes the guided probabilities, and samples a clean reconstruction for the diffusion sampler’s existing update rule\. The same framework can support both hard constraints and soft preferences by compiling the objective or a fitted structured surrogate into different forms of graphical models, which can enable us to perform exact reasoning and probability inference\. It is a plug\-and\-play method, leaving pretrained diffusion parameters unchanged and saving time for compute\-heavy parameter tuning\.

## 2Method

### 2\.1Problem Formulation

At a fixed diffusion step, we seek a clean reconstruction that is consistent with the denoiser’s predictions and preferred by a sequence\-level condition\. Letxt=\(xt1,…,xtL\)x\_\{t\}=\(x\_\{t\}^\{1\},\\ldots,x\_\{t\}^\{L\}\)denote the current diffusion state andx0=\(x01,…,x0L\)x\_\{0\}=\(x\_\{0\}^\{1\},\\ldots,x\_\{0\}^\{L\}\)a possible clean reconstruction over vocabulary𝒱\\mathcal\{V\}\. For absorbing\-mask denoising,𝒪t\\mathcal\{O\}\_\{t\}contains all the positions that are not masked, and the unresolved positions formℳt=\[L\]∖𝒪t\\mathcal\{M\}\_\{t\}=\[L\]\\setminus\\mathcal\{O\}\_\{t\}, where\[L\]=\{1,…,L\}\[L\]=\\\{1,\\ldots,L\\\}\. In one denoising step, we can start from the predicted token distributions supplied by one forward pass through the frozen denoiser, keeping observed tokens fixed and then defining the diffusion evidence

et,i​\(u\)=\{𝟏\[u=xti\],i∈𝒪t,pθ​\(x0i=u∣xt\),i∈ℳt,u∈𝒱,e\_\{t,i\}\(u\)=\\begin\{cases\}\\mathbf\{1\}\[u=x\_\{t\}^\{i\}\],&i\\in\\mathcal\{O\}\_\{t\},\\\\ p\_\{\\theta\}\(x\_\{0\}^\{i\}=u\\mid x\_\{t\}\),&i\\in\\mathcal\{M\}\_\{t\},\\end\{cases\}\\qquad u\\in\\mathcal\{V\},\(2\)wherepθ​\(x0i=u∣xt\)p\_\{\\theta\}\(x\_\{0\}^\{i\}=u\\mid x\_\{t\}\)is the frozen denoiser’s clean\-token conditional at positionii\. To perform reward\-guided generation, these token\-wise marginals need to be used to construct the joint distributionq0​\(x0∣xt\)q\_\{0\}\(x\_\{0\}\\mid x\_\{t\}\)over clean reconstructions and then impose the preferenceCCthrough a nonnegative sequence weightWCW\_\{C\}\. Putting everything together gives us

qC​\(x0∣xt\)=q0​\(x0∣xt\)​WC​\(x0\)ZC​\(xt\)\.q\_\{C\}\(x\_\{0\}\\mid x\_\{t\}\)=\\frac\{q\_\{0\}\(x\_\{0\}\\mid x\_\{t\}\)W\_\{C\}\(x\_\{0\}\)\}\{Z\_\{C\}\(x\_\{t\}\)\}\.\(3\)Its normalizer sums over completions consistent with the observed tokens and, becauseq0\(⋅∣xt\)q\_\{0\}\(\\cdot\\mid x\_\{t\}\)is normalized on that support, is the expected condition weight under the neutral joint distribution:

ZC\(xt\)=∑x0ℳtq0\(x0∣xt\)WC\(x0\)=𝔼x0∼q0\(⋅∣xt\)\[WC\(X0\)\],x0𝒪t=xt𝒪t\.Z\_\{C\}\(x\_\{t\}\)=\\sum\_\{x\_\{0\}^\{\\mathcal\{M\}\_\{t\}\}\}q\_\{0\}\(x\_\{0\}\\mid x\_\{t\}\)W\_\{C\}\(x\_\{0\}\)=\\mathbb\{E\}\_\{x\_\{0\}\\sim q\_\{0\}\(\\cdot\\mid x\_\{t\}\)\}\[W\_\{C\}\(X\_\{0\}\)\],\\qquad x\_\{0\}^\{\\mathcal\{O\}\_\{t\}\}=x\_\{t\}^\{\\mathcal\{O\}\_\{t\}\}\.\(4\)Different values ofWCW\_\{C\}could have different interpretations\. For example, settingWC≡1W\_\{C\}\\equiv 1leavesq0q\_\{0\}unchanged, while a hard condition usesWC\(x0\)=𝟏\[x0⊧C\]W\_\{C\}\(x\_\{0\}\)=\\mathbf\{1\}\[x\_\{0\}\\models C\]to exclude candidates that violateCC, wherex0⊧Cx\_\{0\}\\models Cmeans that the complete sequence satisfiesCC\. A soft condition usesWC​\(x0\)=exp⁡\{λ​RC​\(x0\)\}W\_\{C\}\(x\_\{0\}\)=\\exp\\\{\\lambda R\_\{C\}\(x\_\{0\}\)\\\}, whereRCR\_\{C\}is a sequence\-level reward, where the strengthλ≥0\\lambda\\geq 0controls the preference for larger scores\. Specially, whenWC​\(x0\)=q⁡\(C∣x0\)W\_\{C\}\(x\_\{0\}\)=q\(C\\mid x\_\{0\}\)is an attribute likelihood, the same expression gives Bayesian conditioning\.

The single\-token conditional in Eq\.[1](https://arxiv.org/html/2609.35924#S1.E1)is a marginal of the joint distribution in Eq\.[3](https://arxiv.org/html/2609.35924#S2.E3)\. Our goal is to sample that joint reconstruction rather than draw each token independently from its marginal\. As discussed previously, two main challenges are:\(1\) coupling token choicesdespite the denoiser’s factorized output, and\(2\) evaluating the sequence objectivewhile the tokens that determine its value remain unresolved\. These challenges block the way of obtaining the quantities needed in Eq\.[3](https://arxiv.org/html/2609.35924#S2.E3)and[4](https://arxiv.org/html/2609.35924#S2.E4), resulting in a𝒪⁡\(\|𝒱\|\|ℳt\|\)\\mathcal\{O\}\(\|\\mathcal\{V\}\|^\{\|\\mathcal\{M\}\_\{t\}\|\}\)level complexity \(Fig\.[1](https://arxiv.org/html/2609.35924#S1.F1)\(a\)\)\.Coffeebypasses the challenges with state\-transition graphical models in which a*dependence carrier*retains information linking token choices, and a*compiled objective*tracks their effect on the condition \(Fig\.[2](https://arxiv.org/html/2609.35924#S2.F2)\(A\)\)\. In the later sections, we will construct the carrier first, then extend its calculation to the objective\.

![Refer to caption](https://arxiv.org/html/2609.35924v1/fig2.png)Figure 2:Joint states support tractable computation for joint sampling\.The upper panel shows howCoffeetransforms diffusion marginals into guided joint distributions\. With compiled states,Coffeeruns DP over a continuation table to obtain probability masses, based on which we can get normalized probabilities\. The lower panel uses a toy example to dive into the DP process in the table to provide an intuitive understanding of Eq\.[15](https://arxiv.org/html/2609.35924#S2.E15)and[20](https://arxiv.org/html/2609.35924#S2.E20)\. In the table, columns index sequence boundaries and rows index joint states\(h,a\)\(h,a\)\. EachMi​\(h,a\)M\_\{i\}\(h,a\)sums the weights of the remaining token\-state paths, and generation paths sharing the same boundary state can therefore reuse one entry\. The expanded example sums six consecutive states\(u,h′\)\(u,h^\{\\prime\}\)to obtainM4​\(2,ainit\)M\_\{4\}\(2,a\_\{\\mathrm\{init\}\}\)\. NormalizingUS’s probability mass with the previous quantity gives the joint probabilities of the country\.
### 2\.2Challenge 1: Constructing Neutral Joint Token Distribution

Directly sampling the denoiser distributions gives the fully factorized distribution∏iet,i​\(x0i\)\\prod\_\{i\}e\_\{t,i\}\(x\_\{0\}^\{i\}\), and the most naive way to construct a joint one is to expand one token at a time while retaining every possible choice, producing a computation tree with\|𝒱\|\|ℳt\|\|\\mathcal\{V\}\|^\{\|\\mathcal\{M\}\_\{t\}\|\}leaves \(Fig\.[1](https://arxiv.org/html/2609.35924#S1.F1)\(a\)\)\. Inspired by CoDD\([Li et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib12)\), we are compressing the computation tree with states in state transition graphical models \(called*carriers*\), and the denoiser marginals are used as local evidence absorbed by our carrier to capture the joint dependency\. For simplicity, here we are using chain structured Markov models to explain howCoffeeworks\. Letω\\omegabe the parameters of our carrier andhi∈ℋh\_\{i\}\\in\\mathcal\{H\}be the carrier state after positionii, we use nonnegative local factors

Ki​\(h,u,h′,ω\)≥0,K\_\{i\}\(h,u,h^\{\\prime\};\\omega\)\\geq 0,\(5\)whereKi​\(h,u,h′,ω\)K\_\{i\}\(h,u,h^\{\\prime\};\\omega\)couples tokenuuwith a state transition\. We suppressω\\omegabelow\. With fixedh0h\_\{0\}, we can use these factors and the denoiser evidence jointly to construct the neutral joint distribution

q0\(x0,h1:L∣xt\)∝∏i=1Let,i\(x0i\)Ki\(hi−1,x0i,hi\),q\_\{0\}\(x\_\{0\},h\_\{1:L\}\\mid x\_\{t\}\)\\propto\\prod\_\{i=1\}^\{L\}e\_\{t,i\}\(x\_\{0\}^\{i\}\)K\_\{i\}\(h\_\{i\-1\},x\_\{0\}^\{i\},h\_\{i\}\),\(6\)q0\(x0∣xt\)=∑h1:Lq0\(x0,h1:L∣xt\)\.q\_\{0\}\(x\_\{0\}\\mid x\_\{t\}\)=\\sum\_\{h\_\{1:L\}\}q\_\{0\}\(x\_\{0\},h\_\{1:L\}\\mid x\_\{t\}\)\.\(7\)If we fix the carrier statehih\_\{i\}after positionii, a completion from this state specifies both the remaining clean tokensx0i\+1:Lx\_\{0\}^\{i\+1:L\}and the carrier stateshi\+1:Lh\_\{i\+1:L\}connecting them\. Its remaining probability weight is the product of the denoiser evidence and carrier factors at positionsi\+1i\+1throughLL\. Due to the Markov property, any two partial paths ending in this state have the same weighted completions\. We therefore sum their weights once for each state, defining the total continuation weight

Bi​\(hi\)\\displaystyle B\_\{i\}\(h\_\{i\}\)=∑x0i\+1:L,hi\+1:L∏j=i\+1Let,j\(x0j\)Kj\(hj−1,x0j,hj\)\.\\displaystyle=\\sum\_\{x\_\{0\}^\{i\+1:L\},h\_\{i\+1:L\}\}\\prod\_\{j=i\+1\}^\{L\}e\_\{t,j\}\(x\_\{0\}^\{j\}\)K\_\{j\}\(h\_\{j\-1\},x\_\{0\}^\{j\},h\_\{j\}\)\.\(8\)Here,hih\_\{i\}is fixed and the sum ranges over every assignment to the remaining tokens and carrier states\. This quantity is the normalizer for the distribution of completions conditioned onhih\_\{i\}andxtx\_\{t\}\. To compute such quantity, we can start with considering its successorh′h^\{\\prime\}, where the current factoret,i​\(u\)​Ki​\(h,u,h′\)e\_\{t,i\}\(u\)K\_\{i\}\(h,u,h^\{\\prime\}\)multiplies the total continuation weightBi​\(h′\)B\_\{i\}\(h^\{\\prime\}\)from the successor state,

Bi−1​\(h\)\\displaystyle B\_\{i\-1\}\(h\)=∑u∈𝒱∑h′∈ℋet,i\(u\)Ki\(h,u,h′\)Bi\(h′\),BL\(h\)=1,\\displaystyle=\\sum\_\{u\\in\\mathcal\{V\}\}\\sum\_\{h^\{\\prime\}\\in\\mathcal\{H\}\}e\_\{t,i\}\(u\)K\_\{i\}\(h,u,h^\{\\prime\}\)B\_\{i\}\(h^\{\\prime\}\),\\qquad B\_\{L\}\(h\)=1,\(9\)which gives us a recurrence relationship betweenBiB\_\{i\}andBi−1B\_\{i\-1\}and can be used to perform DP\. Hence, allBiB\_\{i\}withi=1\.\.Li=1\.\.Lcan be computed in polynomial time\. Working backward to the fixed start state givesB0​\(h0\)=Z0​\(xt\)B\_\{0\}\(h\_\{0\}\)=Z\_\{0\}\(x\_\{t\}\), and that is exactly the normalizer of Equation[6](https://arxiv.org/html/2609.35924#S2.E6)\. For a reachable statehhwithBi−1​\(h\)\>0B\_\{i\-1\}\(h\)\>0, we can partition its succeeding completions by the next token\-state pair\(u,h′\)\(u,h^\{\\prime\}\), which has a probability weightet,i​\(u\)​Ki​\(h,u,h′\)​Bi​\(h′\)e\_\{t,i\}\(u\)K\_\{i\}\(h,u,h^\{\\prime\}\)B\_\{i\}\(h^\{\\prime\}\)\. To obtain the distribution of\(x0i=u,hi=h′\)\(x\_\{0\}^\{i\}=u,h\_\{i\}=h^\{\\prime\}\), we just need to normalize with all the local factors at this state, which gives

q0\(x0i=u,hi=h′∣hi−1=h,xt\)\\displaystyle q\_\{0\}\(x\_\{0\}^\{i\}=u,h\_\{i\}=h^\{\\prime\}\\mid h\_\{i\-1\}=h,x\_\{t\}\)=et,i​\(u\)​Ki​\(h,u,h′\)​Bi​\(h′\)∑v,get,i​\(v\)​Ki​\(h,v,g\)​Bi​\(g\)\\displaystyle=\\frac\{e\_\{t,i\}\(u\)K\_\{i\}\(h,u,h^\{\\prime\}\)B\_\{i\}\(h^\{\\prime\}\)\}\{\\sum\_\{v,g\}e\_\{t,i\}\(v\)K\_\{i\}\(h,v,g\)B\_\{i\}\(g\)\}\(10\)=et,i​\(u\)​Ki​\(h,u,h′\)​Bi​\(h′\)Bi−1​\(h\)\.\\displaystyle=\\frac\{e\_\{t,i\}\(u\)K\_\{i\}\(h,u,h^\{\\prime\}\)B\_\{i\}\(h^\{\\prime\}\)\}\{B\_\{i\-1\}\(h\)\}\.With allBiB\_\{i\}computed, we can start ath0h\_\{0\}and draw\(x0i,hi\)\(x\_\{0\}^\{i\},h\_\{i\}\)pairs fromi=1i=1toLLusing these conditionals in polynomial time, which is equivalent to sampling from Equation[6](https://arxiv.org/html/2609.35924#S2.E6)if we discard the sampled carrier states from the sampled results\. The carrier is trained without any task\-specific preferenceCCand is therefore target\-free\. During generation, the carrier stays fixed while each diffusion step supplies fresh denoiser evidence\. Carrier construction and training details are in Sec\.[C](https://arxiv.org/html/2609.35924#A3), while fixed\-step sampling details are in Sec\.[A](https://arxiv.org/html/2609.35924#A1)\.

### 2\.3Challenge 2: Scoring Corrupted Sequences without Naive Enumeration

In the previous section we have shown that constructing and then sampling from the joint distribution can be tractable, and we now try to incorporate the sequence level objective into its continuation calculation\. To draw samples from Eq\.[3](https://arxiv.org/html/2609.35924#S2.E3), we should make sure that theWCW\_\{C\}won’t break the computation complexity, and this is what Challenge 2 is about\. UsingWCoracle​\(x0\)W\_\{C\}^\{\\mathrm\{oracle\}\}\(x\_\{0\}\)to denote the desired weight, with no assumed structure, our goal is to seek a structured surrogate scorerWCW\_\{C\}for the same task signal, whose structure is compatible with the DP computation structure to preserve the complexity\. The process of finding such surrogateWCW\_\{C\}is called*compilation*, and usually, we just need to find the proper structures we need, and fit the model with the same objectives or distill from a better one\. With Prop\.[2\.1](https://arxiv.org/html/2609.35924#S2.Thmtheorem1), with the surrogate structure that will be specified later, the approximation error of such compilation can be analysed and controlled\. Details are specified in Sec\.[A\.3](https://arxiv.org/html/2609.35924#A1.SS3)\.

###### Proposition 2\.1\(Objective approximation under compilation\)\.

Fixxtx\_\{t\}and a base distributionq0q\_\{0\}with finite support, on whichWCW\_\{C\}andWCoracleW\_\{C\}^\{\\mathrm\{oracle\}\}are finite and strictly positive\. Exact compilation preserves the guided lawqCq\_\{C\}\. LetqCoracleq\_\{C\}^\{\\mathrm\{oracle\}\}use the sameq0q\_\{0\}with the oracle weight\. If\|log⁡WC​\(x0\)−log⁡WCoracle​\(x0\)−c\|≤ϵ\|\\log W\_\{C\}\(x\_\{0\}\)\-\\log W\_\{C\}^\{\\mathrm\{oracle\}\}\(x\_\{0\}\)\-c\|\\leq\\epsilonthroughout this support for some constantccandϵ≥0\\epsilon\\geq 0, then

DKL\(qCoracle∥qC\)≤ϵ2/2\.D\_\{\\mathrm\{KL\}\}\(q\_\{C\}^\{\\mathrm\{oracle\}\}\\\|q\_\{C\}\)\\leq\\epsilon^\{2\}/2\.

To see the required structure, we can start with the simplest scorer class,WClocal​\(x0\)=∏iwC​\(x0i\)W\_\{C\}^\{\\mathrm\{local\}\}\(x\_\{0\}\)=\\prod\_\{i\}w\_\{C\}\(x\_\{0\}^\{i\}\), wherewC​\(u\)≥0w\_\{C\}\(u\)\\geq 0\. Because each factor concerns only the current token, absorbing it into the carrier transition gives the same backward structure as Equation[9](https://arxiv.org/html/2609.35924#S2.E9), now incorporating the objective weights,

K¯C,i​\(h,u,h′\)\\displaystyle\\overline\{K\}\_\{C,i\}\(h,u,h^\{\\prime\}\)=Ki​\(h,u,h′\)​wC​\(u\),\\displaystyle=K\_\{i\}\(h,u,h^\{\\prime\}\)w\_\{C\}\(u\),\(11\)Bi−1local​\(h\)\\displaystyle B\_\{i\-1\}^\{\\mathrm\{local\}\}\(h\)=∑u∈𝒱∑h′∈ℋet,i​\(u\)​K¯C,i​\(h,u,h′\)​Bilocal​\(h′\)\.\\displaystyle=\\sum\_\{u\\in\\mathcal\{V\}\}\\sum\_\{h^\{\\prime\}\\in\\mathcal\{H\}\}e\_\{t,i\}\(u\)\\overline\{K\}\_\{C,i\}\(h,u,h^\{\\prime\}\)B\_\{i\}^\{\\mathrm\{local\}\}\(h^\{\\prime\}\)\.\(12\)WithBLlocal​\(h\)=1B\_\{L\}^\{\\mathrm\{local\}\}\(h\)=1, this computes the guided completion weights and hence the exact conditionals\. Each transition only adds one multiplication, which preserves the dense carrier complexity ofO⁡\(L​\|𝒱\|​H2\)O\(L\|\\mathcal\{V\}\|H^\{2\}\), preserving the same time complexity as to sample from the neutral distribution\. However, such scorer cannot express preferences for structures formed by multiple tokens, for example, sinceWClocal​\(AB\)=wC​\(A\)​wC​\(B\)=WClocal​\(BA\)W\_\{C\}^\{\\mathrm\{local\}\}\(\\texttt\{AB\}\)=w\_\{C\}\(\\texttt\{A\}\)w\_\{C\}\(\\texttt\{B\}\)=W\_\{C\}^\{\\mathrm\{local\}\}\(\\texttt\{BA\}\), it can’t even tell orders apart\. More generally, an objective may assign scores to occurrences of multiple patterns with different lengths, including repeated and overlapping matches, and they cannot be modeled by such simple class\.

Now, our goal is to capture complex patterns while retaining the same DP structure\. To do so, we can try to generalize Equations[11](https://arxiv.org/html/2609.35924#S2.E11)and[12](https://arxiv.org/html/2609.35924#S2.E12)\. Notice that the recurrence only requires each objective factor to be computable from the current state and token and the scorer shall have the same transition dynamics as the carrier graphical model, if a finite stateaia\_\{i\}can remember the relevant pattern history, we could therefore extendWC​\(x0\)W\_\{C\}\(x\_\{0\}\)to∏i=1LwC​\(ai\)\\prod\_\{i=1\}^\{L\}w\_\{C\}\(a\_\{i\}\)with a chain\-structured updateai=δC,i​\(ai−1,x0i\)a\_\{i\}=\\delta\_\{C,i\}\(a\_\{i\-1\},x\_\{0\}^\{i\}\)\. Such an extension enlarges the state space fromhih\_\{i\}to\(hi,ai\)\(h\_\{i\},a\_\{i\}\), so the same recurrence can operate on the paired states\. WithAAdenoting the number ofaia\_\{i\}, the overall time complexity will be𝒪⁡\(L​A​\|V\|​H2\)\\mathcal\{O\}\(LA\|V\|H^\{2\}\), preserving the polynomial time complexity\.

For a selected pattern set𝒢C\\mathcal\{G\}\_\{C\}, an Aho\-Corasick \(AC\) automaton\([Aho and Corasick, 1975](https://arxiv.org/html/2609.35924#bib.bib23)\)has all the nice desired properties\. Its states𝒜\\mathcal\{A\}correspond to shared pattern prefixes, with the empty prefix asainita\_\{\\mathrm\{init\}\}\. After readingx01:ix\_\{0\}^\{1:i\}, the stateaia\_\{i\}records the longest suffix that is also a prefix of a selected pattern\. Reading a token extends the current match or falls back to a shorter suffix, giving the updateai=δC,i​\(ai−1,x0i\)a\_\{i\}=\\delta\_\{C,i\}\(a\_\{i\-1\},x\_\{0\}^\{i\}\)froma0=ainita\_\{0\}=a\_\{\\mathrm\{init\}\}\. For simplicity, here we defineδC,i=δC\\delta\_\{C,i\}=\\delta\_\{C\}to be position\-independent\. Such an automaton can report all selected patterns completed when readinguufromaa, including overlapping occurrences\. For example,Newstarts a partial match and the next tokenYorkcompletesNew York\(Figure[1](https://arxiv.org/html/2609.35924#S1.F1)\)\. The transition and output construction is detailed in Sec\.[A](https://arxiv.org/html/2609.35924#A1)\.

The token\-only factorwC​\(u\)w\_\{C\}\(u\)in Equation[11](https://arxiv.org/html/2609.35924#S2.E11)can now be replaced by a nonnegative local weightψC,i​\(a,u\)\\psi\_\{C,i\}\(a,u\)\. Since both models consume the same token, their joint transition and its weight become

\(h,a\)→𝑢\(h′,δC,i​\(a,u\)\),K¯C,i​\(h,a,u,h′\)=Ki​\(h,u,h′\)​ψC,i​\(a,u\)\.\(h,a\)\\xrightarrow\{u\}\\bigl\(h^\{\\prime\},\\delta\_\{C,i\}\(a,u\)\\bigr\),\\qquad\\overline\{K\}\_\{C,i\}\(h,a,u,h^\{\\prime\}\)=K\_\{i\}\(h,u,h^\{\\prime\}\)\\psi\_\{C,i\}\(a,u\)\.\(13\)With the modified transition dynamics, we can therefore replaceBilocal​\(h\)B\_\{i\}^\{\\mathrm\{local\}\}\(h\)in Eq\.[12](https://arxiv.org/html/2609.35924#S2.E12)byMi​\(h,a\)M\_\{i\}\(h,a\), the total continuation weight from the state pair, and obtain the similar recurrence relationships with nonnegative terminal factorηC​\(a\)\\eta\_\{C\}\(a\)\(visualization in Fig\.[2](https://arxiv.org/html/2609.35924#S2.F2)\)

ML​\(h,a\)\\displaystyle M\_\{L\}\(h,a\)=ηC​\(a\),\\displaystyle=\\eta\_\{C\}\(a\),\(14\)Mi−1​\(h,a\)\\displaystyle M\_\{i\-1\}\(h,a\)=∑u∈𝒱∑h′∈ℋet,i​\(u\)​K¯C,i​\(h,a,u,h′\)​Mi​\(h′,δC,i​\(a,u\)\)\.\\displaystyle=\\sum\_\{u\\in\\mathcal\{V\}\}\\sum\_\{h^\{\\prime\}\\in\\mathcal\{H\}\}e\_\{t,i\}\(u\)\\overline\{K\}\_\{C,i\}\(h,a,u,h^\{\\prime\}\)M\_\{i\}\\\!\\left\(h^\{\\prime\},\\delta\_\{C,i\}\(a,u\)\\right\)\.\(15\)The backward recurrence givesM0​\(h0,ainit\)M\_\{0\}\(h\_\{0\},a\_\{\\mathrm\{init\}\}\), which normalizes the guided joint distribution,

qCjoint\(x0,h1:L∣xt\)=ηC​\(aL\)M0​\(h0,ainit\)∏i=1Let,i\(x0i\)K¯C,i\(hi−1,ai−1,x0i,hi\)\.q\_\{C\}^\{\\mathrm\{joint\}\}\(x\_\{0\},h\_\{1:L\}\\mid x\_\{t\}\)\\quad=\\frac\{\\eta\_\{C\}\(a\_\{L\}\)\}\{M\_\{0\}\(h\_\{0\},a\_\{\\mathrm\{init\}\}\)\}\\prod\_\{i=1\}^\{L\}e\_\{t,i\}\(x\_\{0\}^\{i\}\)\\overline\{K\}\_\{C,i\}\(h\_\{i\-1\},a\_\{i\-1\},x\_\{0\}^\{i\},h\_\{i\}\)\.\(16\)Since the tokens uniquely determine the objective\-state path, multiplying its local objective factors gives the sequence\-level preference

WC​\(x0\)=ηC​\(aL\)​∏i=1LψC,i​\(ai−1,x0i\),W\_\{C\}\(x\_\{0\}\)=\\eta\_\{C\}\(a\_\{L\}\)\\prod\_\{i=1\}^\{L\}\\psi\_\{C,i\}\(a\_\{i\-1\},x\_\{0\}^\{i\}\),\(17\)and complex patterns are captured with AC state transitions\. With Eq\.[16](https://arxiv.org/html/2609.35924#S2.E16)and[17](https://arxiv.org/html/2609.35924#S2.E17), we can see that the standalone scorer assigns weights to complete sequences, while the joint inference DP process averages these weights over compatible completions and eventually changes the neutral unguided distribution to a more favored one\. In our applications, we just need to train the local factorsψ⁡\(a,u\)\\psi\(a,u\)to obtain the compiled objective \(Sec\.[C](https://arxiv.org/html/2609.35924#A3)\)\. The same interface also supports hard conditioning using an appropriate deterministic objective automaton with unit transition weights andηC\(aL\)=𝟏\[aL∈𝒜accept\]\\eta\_\{C\}\(a\_\{L\}\)=\\mathbf\{1\}\[a\_\{L\}\\in\\mathcal\{A\}\_\{\\mathrm\{accept\}\}\]to exclude rejecting paths without requiring a learned scorer\.

### 2\.4Coffee: Guided Reconstruction

We now connect the continuation weights to the expectation in Eq\.[18](https://arxiv.org/html/2609.35924#S2.E18)\. As discussed previously, using the same diffusion backbone and carrier, starting from the state\(h,a\)\(h,a\)at theii\-th token,Bi​\(h\)B\_\{i\}\(h\)is the accumulated probability mass athhstate if we run DP without scorer, whileMi​\(h,a\)M\_\{i\}\(h,a\)is the total mass at the joint state\(h,a\)\(h,a\), with scorer weights added up to the mass\. Directly taking their ratio could give us the conditional expectation \(details in Eq\.[27](https://arxiv.org/html/2609.35924#A1.E27)\) and get

Mi​\(h,a\)Bi​\(h\)=𝔼q0\[ηC\(aL\)∏j=i\+1LψC,j\(aj−1,x0j\)\|hi=h,xt;ai:=a\]\.\\frac\{M\_\{i\}\(h,a\)\}\{B\_\{i\}\(h\)\}=\\mathbb\{E\}\_\{q\_\{0\}\}\\\!\\left\[\\eta\_\{C\}\(a\_\{L\}\)\\prod\_\{j=i\+1\}^\{L\}\\psi\_\{C,j\}\(a\_\{j\-1\},x\_\{0\}^\{j\}\)\\,\\middle\|\\,h\_\{i\}=h,x\_\{t\};\\ a\_\{i\}:=a\\right\]\.\(18\)Based on that, following the same marginalization as in Sec\.[2\.2](https://arxiv.org/html/2609.35924#S2.SS2), leta′=δC,i​\(a,u\)a^\{\\prime\}=\\delta\_\{C,i\}\(a,u\)\. For a current state withMi−1​\(h,a\)\>0M\_\{i\-1\}\(h,a\)\>0, the sampling conditional is proportional to

qCjoint\(x0i=u,hi=h′∣hi−1=h,ai−1=a,xt\)\\displaystyle q\_\{C\}^\{\\mathrm\{joint\}\}\(x\_\{0\}^\{i\}=u,h\_\{i\}=h^\{\\prime\}\\mid h\_\{i\-1\}=h,a\_\{i\-1\}=a,x\_\{t\}\)\(19\)∝et,i​\(u\)⏟base denoisermarginalKi​\(h,u,h′\)​Bi​\(h′\)⏟carrier structureand base continuationψC,i​\(a,u\)⏟current ACobjective weightMi​\(h′,a′\)Bi​\(h′\)⏟expected remainingobjective weight,\\displaystyle\\propto\\underbrace\{e\_\{t,i\}\(u\)\}\_\{\\begin\{subarray\}\{c\}\\text\{base denoiser\}\\\\ \\text\{marginal\}\\end\{subarray\}\}\\quad\\underbrace\{K\_\{i\}\(h,u,h^\{\\prime\}\)B\_\{i\}\(h^\{\\prime\}\)\}\_\{\\begin\{subarray\}\{c\}\\text\{carrier structure\}\\\\ \\text\{and base continuation\}\\end\{subarray\}\}\\quad\\underbrace\{\\psi\_\{C,i\}\(a,u\)\}\_\{\\begin\{subarray\}\{c\}\\text\{current AC\}\\\\ \\text\{objective weight\}\\end\{subarray\}\}\\quad\\underbrace\{\\frac\{M\_\{i\}\(h^\{\\prime\},a^\{\\prime\}\)\}\{B\_\{i\}\(h^\{\\prime\}\)\}\}\_\{\\begin\{subarray\}\{c\}\\text\{expected remaining\}\\\\ \\text\{objective weight\}\\end\{subarray\}\},which holds for fixed\(h,a\)\(h,a\)on base\-supported choices\. Note thatBiB\_\{i\}can be canceled and hence doesn’t need to be computed during sampling\. Using such decomposition, we can further analyze theNew Yorkexample: even whenNewitself has no reward, it can be favored through completions in whichNew Yorkis formed\. Through the carrier’s dependencies, the same preference can also affect positions not directly scored by the objective, and therefore, result in a higher preference inUSA\.

To draw samples from the joint distribution,Coffeecomputes all theMiM\_\{i\}values and, following Eq\.[10](https://arxiv.org/html/2609.35924#S2.E10), starts at\(h0,ainit\)\(h\_\{0\},a\_\{\\mathrm\{init\}\}\)and samples fromi=1i=1toLLusing

qCjoint\(x0i=u,hi=h′∣hi−1=h,ai−1=a,xt\)=et,i​\(u\)​K¯C,i​\(h,a,u,h′\)​Mi​\(h′,a′\)Mi−1​\(h,a\),q\_\{C\}^\{\\mathrm\{joint\}\}\(x\_\{0\}^\{i\}=u,h\_\{i\}=h^\{\\prime\}\\mid h\_\{i\-1\}=h,a\_\{i\-1\}=a,x\_\{t\}\)\\quad=\\frac\{e\_\{t,i\}\(u\)\\overline\{K\}\_\{C,i\}\(h,a,u,h^\{\\prime\}\)M\_\{i\}\(h^\{\\prime\},a^\{\\prime\}\)\}\{M\_\{i\-1\}\(h,a\)\},\(20\)whereK¯C,i\\overline\{K\}\_\{C,i\}is defined in Eq\.[13](https://arxiv.org/html/2609.35924#S2.E13)and the denominator sums the numerator over all choices by Eq\.[15](https://arxiv.org/html/2609.35924#S2.E15)\. After drawing\(u,h′\)\(u,h^\{\\prime\}\), setx~0i=u\\widetilde\{x\}\_\{0\}^\{i\}=uand update the state to\(h′,a′\)\(h^\{\\prime\},a^\{\\prime\}\)\. Once a complete reconstruction is obtained, we pass it to the unchanged diffusion update rule with original noise schedulingqh​o​s​tq\_\{host\}

x~0∼qC\(⋅∣xt\),xt−1∼qhost\(⋅∣xt,x~0\),\\widetilde\{x\}\_\{0\}\\sim q\_\{C\}\(\\,\\cdot\\mid x\_\{t\}\),\\qquad x\_\{t\-1\}\\sim q\_\{\\mathrm\{host\}\}\(\\,\\cdot\\mid x\_\{t\},\\widetilde\{x\}\_\{0\}\),\(21\)and repeat the algorithm in next diffusion steps to eventually obtain clean samples \(Algorithm[3](https://arxiv.org/html/2609.35924#alg3)\)\.

Beyond guided sampling, the finite\-state compilation and DP structure allowCoffeeto draw on the extensive algorithmic literature on weighted automata\([Mohri, 2009](https://arxiv.org/html/2609.35924#bib.bib22)\), opening a route to richer queries that combine optimization with probabilistic inference\. Our Dyck repair task illustrates this potential: we first use a bounded\-stack state graph to retain all valid, prefix\-preserving paths with the fewest token changes within the declared support\. This optimal set then acts as a hard objective: on the retained graph, the same continuation\-weight recurrence and sampling rule combine denoiser evidence with carrier dependence\. Thus, optimization determines the conditioning event, and our joint inference samples among equally optimal repairs \(Sec\.[3\.1](https://arxiv.org/html/2609.35924#S3.SS1.SSS0.Px1)\)\.

Table 1:This table shows the generation results under full diffusion budgets\. The warmDreamand blueLLaDAheaders denote the two backbones and the black headers denote biological tasks\.Coffeesurpasses almost all the baselines on both control and quality metrics over different benchmarks\.

## 3Experiments

### 3\.1Main Results

We evaluateCoffeewith frozen Dream and LLaDA backbones on symbolic and language tasks, D3LM on DNA, and EvoDiff on protein design, covering exact constraints and learned objectives\. Dyck repair and Sudoku measure validity alongside edit distance or constraint violations\. CommonGen\([Lin et al\., 2020](https://arxiv.org/html/2609.35924#bib.bib28)\)and RealToxicityPrompts \(RTP\)\([Gehman et al\., 2020](https://arxiv.org/html/2609.35924#bib.bib27)\)assess lexical coverage and non\-toxicity alongside perplexity \(PPL\)\. DeepSTARR\([de Almeida et al\., 2022](https://arxiv.org/html/2609.35924#bib.bib32)\), APARENT\([Bogard et al\., 2019](https://arxiv.org/html/2609.35924#bib.bib33)\), and Malinois\([Gosai et al\., 2024](https://arxiv.org/html/2609.35924#bib.bib34)\)use predictor\-defined DNA objectives, with native leave\-one\-out pseudo\-perplexity \(LOO\) and diversity as diagnostics\. Protein\-1YCR follows EvoDiff’s motif\-scaffolding setup\([Alamdari et al\., 2023](https://arxiv.org/html/2609.35924#bib.bib35)\)and evaluates structural recovery using OmegaFold\([Wu et al\., 2022](https://arxiv.org/html/2609.35924#bib.bib36)\)\. Table[1](https://arxiv.org/html/2609.35924#S2.T1)reports full\-budget results; Fig\.[3](https://arxiv.org/html/2609.35924#S3.F3)examines whether target attainment is preserved with fewer denoising updates\. Details are in Secs\.[D](https://arxiv.org/html/2609.35924#A4)–[E](https://arxiv.org/html/2609.35924#A5)\.

##### Symbolic tasks\.

On Dyck,Coffeeand DG\-TAG both reach full validity, butCoffeerequires fewer edits\. Whereas DG\-TAG rescores a bounded set of successors,Coffee’s min\-plus pass first retains the minimum\-substitution feasible set within the declared support\. Denoiser evidence and carrier weights then select among equally optimal repairs, without trading additional edits for a higher generation score\. The Sudoku budget sweep tests a different issue: individually feasible digits can still be mutually incompatible\. A joint reconstruction supplies a common feasible completion for all of these choices\. CDM also maintains full validity across budgets when its particles operate within exact feasible\-completion support, despite its low validity on Dyck\. Thus, the symbolic comparison concerns both the construction of the feasible set and how parallel choices are coupled within it\.

##### Language tasks\.

On CommonGen,Coffeeachieves full coverage across both backbones even under limited budgets in Fig\.[3](https://arxiv.org/html/2609.35924#S3.F3)\. The compiled terminal condition excludes completions that omit a requested concept, while the objective state tracks concepts already covered, so the remaining completion calculation coordinates the placement of those still missing\. Among accepted realizations, word order and surrounding text remain weighted by the denoiser and carrier\. On the RTP task,Coffeepreserves good PPL with high non\-toxic rates over different budgets and backbones, showing the benefits of joint inference coupled with sequence\-level objectives\.

##### Biological sequence design\.

On biological sequences,Coffeeimproves control metrics with low trade\-off of sequence quality\. On Protein\-1YCR, higher structural success is accompanied by lower mean motif RMSD\. For DNA, low native LOO can coexist with severe concentration of the outputs\. K562 combines high target attainment with few distinct sequences, while DeepSTARR collapses entirely to a single all\-T sequence despite favorable activity and LOO scores\. The diversity diagnostic exposes the concentration that neither of these two averages measures\.

Figure 3:Control across denoising budgetsbb\(higher is better\)\.WarmDreamand blueLLaDAtitles distinguish the language backbones; black titles denote biological tasks\. Hollow markers indicate archival or qualified settings documented in Sec\.[F](https://arxiv.org/html/2609.35924#A6)\. The results show thatCoffeeachieves the highest control effects over almost all the benchmarks, even with only a few diffusion steps\.

### 3\.2Mechanistic Analysis

In the HepG2 rollouts, objective weighting changes the evolution of complete clean proposals, yielding more favored proposals at the final displayed update \(Fig\.[4](https://arxiv.org/html/2609.35924#S3.F4)A\)\. The intervention acts through guided reconstruction\. After the host commits tokens, the next reconstruction uses refreshed denoiser evidence and respects those observations\. Guidance therefore repeatedly reweights completions compatible with the evolving partial sequence\. Eq\.[19](https://arxiv.org/html/2609.35924#S2.E19)combines token\-level transition factors with an aggregate weight over the remaining completions\. The continuation ratio in Eq\.[18](https://arxiv.org/html/2609.35924#S2.E18)averages downstream objective weight under the neutral model for each current choice\. This allows future objective factors to affect the current token conditional\. The separate K562 diagnostic exposes this dependence even when downstream token identities are already fixed: their objective contributions still depend on the state reached by the current choice\. Clamping their evidence does not make those objective factors common constants that cancel between current candidates\. These state\-dependent corrections are substantial at a small subset of the queried positions \(Fig\.[4](https://arxiv.org/html/2609.35924#S3.F4)B\-C\)\. Meanwhile, to test completion weighting and joint sampling in complete generations, we run separate controls over CommonGen\. Full lowers PPL relative to feasibility\-only guidance, while independent guided marginals reduce lexical coverage from 100% to 83\.98%, showing why joint sampling matters \(Sec\.[H\.4](https://arxiv.org/html/2609.35924#A8.SS4)\)\. We have also evaluated the empirical inference speed with the same configuration in Table[1](https://arxiv.org/html/2609.35924#S2.T1), and shown that without much efforts in designing graphical model specific operators,Coffee’s inference speed surpasses most of the baselines while obtaining high control as well as generation quality, indicating the benefits of our plug\-and\-play scheme\. Details are in Sec\.[B\.2](https://arxiv.org/html/2609.35924#A2.SS2)\.

Figure 4:Proposal trajectories and token\-level guidance\.\(A\) Evaluator\-category transitions of complete clean proposals from 64 same\-ID HepG2 rollouts per arm, with the objective disabled \(WC≡1W\_\{C\}\\equiv 1\) or enabled and the identity carrier fixed\. Ribbon widths count trajectories, not probability mass\. \(B\) For a fixed K562 query and prefix at position 25, curves show token probabilities as future objective factors are enabled cumulatively; the state graph and all other factors remain fixed\. Local omits future weights; Full includes all\. Weights at two already observed downstream tokens reduce the probability ofAAAAAA\. Bars show incremental log odds ofAAAAAAagainst the other candidates\. The horizontal axis is objective position, not diffusion time\. \(C\) CDF of Full\-Local total variation over 224 masked positions in nine queries, with conditional TV averaged over prefixes under neutral occupancy\. The diamond marks the maximum\-TV position selected for \(B\)\. Protocols are in Sec\.[H\.3](https://arxiv.org/html/2609.35924#A8.SS3)\.
### 3\.3Discussion and Related Work22footnotemark:2

33footnotetext:A more detailed literature review is in Sec\.[J](https://arxiv.org/html/2609.35924#A10)\.The fixed\-query analysis in Figure[4](https://arxiv.org/html/2609.35924#S3.F4)shows how future objective factors can affect a current choice without changing the denoiser evidence, which connectsCoffeeto the probabilistic\-control view of generation\([Levine, 2018](https://arxiv.org/html/2609.35924#bib.bib38)\), where preferences over complete outcomes inform intermediate decisions\. Future discriminators, soft\-value decoding, and twisted sequential Monte Carlo obtain such signals through prediction or sampling\([Yang and Klein, 2021](https://arxiv.org/html/2609.35924#bib.bib13);[Li et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib10);[Zhao et al\., 2024](https://arxiv.org/html/2609.35924#bib.bib39)\), while GeLaTo, Ctrl\-G, and TRACE use tractable completion models\([Zhang et al\., 2023](https://arxiv.org/html/2609.35924#bib.bib14);[Zhang et al\., 2024](https://arxiv.org/html/2609.35924#bib.bib15);[Weng et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib16)\)\.Coffeecombines this completion\-based view with the dependence modeling of CoDD\([Li et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib12)\), and within each diffusion step, it aggregates objective contributions over joint reconstructions rather than treating unresolved choices independently to model cross\-token dependency\.

The compiled representation also supports requirements that are more naturally expressed as inference queries than as a single predictive score, as discussed in Sec\.[2\.4](https://arxiv.org/html/2609.35924#S2.SS4)\. Our Dyck repair construction first identifies all minimum\-edit valid paths within the declared support, then samples among them using denoiser evidence and carrier weights\. This combines optimization with probabilistic conditioning, drawing on weighted\-automata algorithms\([Mohri, 2009](https://arxiv.org/html/2609.35924#bib.bib22)\), connecting to neuro\-symbolic structured prediction, where neural evidence is combined with explicit constraints\([Ahmed et al\., 2022](https://arxiv.org/html/2609.35924#bib.bib21);[van Krieken et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib37)\)\. Compatible objective states could similarly combine hard requirements and soft preferences in one reconstruction query\. The benefit is therefore not only a change in the scoring function, but access to additional more complex algorithmic computations during generation\.

These capabilities depend on finding representations that remain both useful and tractable when combined\. Efficient evaluation of the model and scorer separately does not ensure an efficient expectation query\([Khosravi et al\., 2019](https://arxiv.org/html/2609.35924#bib.bib40)\), and research in knowledge compilation and circuit operations makes representation size and structural compatibility central to this question\([Darwiche and Marquis, 2002](https://arxiv.org/html/2609.35924#bib.bib19);[Vergari et al\., 2021](https://arxiv.org/html/2609.35924#bib.bib20)\)\. Our selected token and phrase features omit interactions outside the scorer class, while richer representations can make the product state too large\. Proposition[2\.1](https://arxiv.org/html/2609.35924#S2.Thmtheorem1)bounds objective approximation for a fixed carrier and support, but more theories need to be developed to extend the expressiveness of such representation, and to analyze the diffusion errors alongside the generation process\. Circuit restructuring and structured\-sparse parameterizations offer related directions for compatible composition and hardware\-efficient inference\([Zhang et al\., 2025b](https://arxiv.org/html/2609.35924#bib.bib41);[Zhang et al\., 2025a](https://arxiv.org/html/2609.35924#bib.bib42)\)\.

## 4Conclusion

We introducedCoffee, a plug\-and\-play framework that turns sequence\-level objectives into joint reconstruction queries for discrete diffusion\. A target\-free carrier and compiled objective allow the sampler to coordinate unresolved tokens and account for their possible completions without explicit enumeration\. Under the stated representation and support conditions, fixed\-step inference is exact for the compiled model and leaves the pretrained generator unchanged\. The same interface supports hard conditioning, finite\-state soft preferences, and optimization followed by conditional sampling\. Experiments show full satisfaction on the evaluated symbolic and lexical tasks and success in reward\-guided biological sequence generation\. More broadly, the representation of a guidance objective determines not only which sequences it rewards, but also which queries can be answered during generation\. Making objectives available to conditioning, marginalization, and optimization enables control over sets of possible completions, rather than requiring those completions to be generated and scored individually, revealing broader potentials for neural\-symbolic methods\.

## AI Use Statement

Generative AI tools were used for literature search and synthesis, feedback on research methodology and experiment design, code implementation and debugging, analysis and interpretation of results, manuscript organization and revision, and preparation of LaTeX tables and figures\. They were not used to fabricate or alter experimental measurements, to choose held\-out results after observing their outcomes, or to make final scientific decisions\. The authors checked AI\-assisted citations against the original sources, reviewed and tested AI\-assisted code, and reconciled reported values and claims with the frozen experimental artifacts and evaluator outputs\. The authors made all final scientific and writing decisions and take responsibility for the complete contents of this preprint\.

## Ethics Statement

This computational study recruited no human participants, collected no new personal data, and performed no wet\-lab biological experiments\. The language evaluation includes potentially harmful text from an established toxicity benchmark, which is used only for computational evaluation\. The proposed framework is dual\-use because it can steer language or biological sequences toward any objective that admits a compatible representation\. Although the evaluated objectives concern non\-toxic language and established biological design benchmarks, predictor scores do not establish biological function, safety, or clinical utility\. We therefore restrict our claims to the declared evaluators and supports, report failure modes such as mode collapse, and make no claim of experimentally validated biological efficacy\.

## Reproducibility Statement

The[appendix guide](https://arxiv.org/html/2609.35924#Ax1)summarizes the reproducibility path\. The method section and Appendices[A](https://arxiv.org/html/2609.35924#A1)to[C](https://arxiv.org/html/2609.35924#A3)specify the fixed\-step law, exactness and complexity boundaries, and construction of the carrier and objectives\. Appendices[D](https://arxiv.org/html/2609.35924#A4)to[E](https://arxiv.org/html/2609.35924#A5.SS1)document the data and evaluator contracts, baseline adaptations, development\-only selection rules, and frozen configurations\. Tab\.[1](https://arxiv.org/html/2609.35924#S2.T1)and Fig\.[3](https://arxiv.org/html/2609.35924#S3.F3)contain the claim\-facing results, while Appendix[F](https://arxiv.org/html/2609.35924#A6)documents their qualifications\. Appendices[G](https://arxiv.org/html/2609.35924#A7)to[I](https://arxiv.org/html/2609.35924#A9)provide the canonical algorithms, failure semantics, diagnostic protocols, and evidence provenance used to audit the reported claims\.

## References

- Ahmedet al\.\(2022\)K\. Ahmed, S\. Teso, K\. Chang, G\. Van den Broeck, and A\. VergariSemantic probabilistic layers for neuro\-symbolic learning\.InAdvances in Neural Information Processing Systems,Vol\.35\.External Links:[Link](https://arxiv.org/abs/2206.00426)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p2.1)\.
- Aho and Corasick \(1975\)A\. V\. Aho and M\. J\. CorasickEfficient string matching: an aid to bibliographic search\.Communications of the ACM18\(6\),pp\. 333–340\.External Links:[Document](https://dx.doi.org/10.1145/360825.360855)Cited by:[§A\.2](https://arxiv.org/html/2609.35924#A1.SS2.p2.1),[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1),[§2\.3](https://arxiv.org/html/2609.35924#S2.SS3.p4.1)\.
- Alamdariet al\.\(2023\)S\. Alamdari, N\. Thakkar, R\. van den Berg, N\. Tenenholtz, R\. Strome, A\. M\. Moses, A\. X\. Lu, N\. Fusi, A\. P\. Amini, and K\. K\. YangProtein generation with evolutionary diffusion: sequence is all you need\.bioRxiv\.External Links:[Document](https://dx.doi.org/10.1101/2023.09.11.556673),[Link](https://www.biorxiv.org/content/10.1101/2023.09.11.556673)Cited by:[§3\.1](https://arxiv.org/html/2609.35924#S3.SS1.p1.1)\.
- An and Han \(2026\)H\. An and Y\. HanDLM\-SWAI: steering diffusion language models before they unmask\.External Links:2605\.29626,[Link](https://arxiv.org/abs/2605.29626)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px3.p1.1)\.
- Austinet al\.\(2021\)J\. Austin, D\. D\. Johnson, J\. Ho, D\. Tarlow, and R\. van den BergStructured denoising diffusion models in discrete state\-spaces\.InAdvances in Neural Information Processing Systems,M\. Ranzato, A\. Beygelzimer, Y\. Dauphin, P\. S\. Liang, and J\. Wortman Vaughan \(Eds\.\),Vol\.34,pp\. 17981–17993\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2021/file/958c530554f78bcd8e97125b70e6973d-Paper.pdf)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px1.p1.1)\.
- Awasthiet al\.\(2026\)A\. Awasthi, R\. Bednarsky, M\. Schaefer, and C\. BockConditional monte carlo tree diffusion for designing cell\-type\-specific and biologically faithful regulatory DNA\.External Links:2604\.20488,[Link](https://arxiv.org/abs/2604.20488)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px4.p1.1)\.
- Benjamini and Hochberg \(1995\)Y\. Benjamini and Y\. HochbergControlling the false discovery rate: a practical and powerful approach to multiple testing\.Journal of the Royal Statistical Society: Series B57\(1\),pp\. 289–300\.External Links:[Document](https://dx.doi.org/10.1111/j.2517-6161.1995.tb02031.x),[Link](https://doi.org/10.1111/j.2517-6161.1995.tb02031.x)Cited by:[§C\.2](https://arxiv.org/html/2609.35924#A3.SS2.SSS0.Px2.p1.2)\.
- Bogardet al\.\(2019\)N\. Bogard, J\. Linder, A\. B\. Rosenberg, and G\. SeeligA deep neural network for predicting and engineering alternative polyadenylation\.Cell178\(1\),pp\. 91–106\.e23\.External Links:[Document](https://dx.doi.org/10.1016/j.cell.2019.04.046),[Link](https://doi.org/10.1016/j.cell.2019.04.046)Cited by:[§3\.1](https://arxiv.org/html/2609.35924#S3.SS1.p1.1)\.
- Buet al\.\(2026\)D\. Bu, W\. Huang, A\. Han, S\. Wu, H\. Wong, Q\. Zhang, T\. Suzuki, and A\. NitandaDPRM: a plug\-in doob h transform\-induced token\-ordering module for discrete diffusion models\.External Links:2604\.24357,[Link](https://arxiv.org/abs/2604.24357)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px3.p1.1)\.
- Cardeiet al\.\(2025\)M\. Cardei, J\. K\. Christopher, B\. Kailkhura, T\. Hartvigsen, and F\. FiorettoConstrained discrete diffusion\.InAdvances in Neural Information Processing Systems,Vol\.38, Main Conference,pp\. 12383–12416\.External Links:[Document](https://dx.doi.org/10.52202/085713-0415)Cited by:[Appendix E](https://arxiv.org/html/2609.35924#A5.p1.1)\.
- Dang and Ermon \(2026\)M\. Dang and S\. ErmonConstrained decoding for diffusion language models via efficient inference over finite automata\.External Links:2607\.07026,[Link](https://arxiv.org/abs/2607.07026)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1)\.
- Darwiche and Marquis \(2002\)A\. Darwiche and P\. MarquisA knowledge compilation map\.Journal of Artificial Intelligence Research17,pp\. 229–264\.External Links:[Document](https://dx.doi.org/10.1613/jair.989),[Link](https://arxiv.org/abs/1106.1819)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p3.1)\.
- de Almeidaet al\.\(2022\)B\. P\. de Almeida, F\. Reiter, M\. Pagani, and A\. StarkDeepSTARR predicts enhancer activity from DNA sequence and enables the de novo design of synthetic enhancers\.Nature Genetics54\(5\),pp\. 613–624\.External Links:[Document](https://dx.doi.org/10.1038/s41588-022-01048-5),[Link](https://doi.org/10.1038/s41588-022-01048-5)Cited by:[§3\.1](https://arxiv.org/html/2609.35924#S3.SS1.p1.1)\.
- Douet al\.\(2026\)H\. Dou, Z\. Chen, F\. Li, H\. Li, and Y\. DengPlug\-and\-play guidance for discrete diffusion models via gradient\-informed logit correction\.InProceedings of the 43rd International Conference on Machine Learning,External Links:2606\.06303,[Link](https://arxiv.org/abs/2606.06303)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px3.p1.1),[Appendix E](https://arxiv.org/html/2609.35924#A5.p1.1)\.
- Gehmanet al\.\(2020\)S\. Gehman, S\. Gururangan, M\. Sap, Y\. Choi, and N\. A\. SmithRealToxicityPrompts: evaluating neural toxic degeneration in language models\.InFindings of the Association for Computational Linguistics: EMNLP 2020,pp\. 3356–3369\.External Links:[Document](https://dx.doi.org/10.18653/v1/2020.findings-emnlp.301),[Link](https://aclanthology.org/2020.findings-emnlp.301/)Cited by:[§3\.1](https://arxiv.org/html/2609.35924#S3.SS1.p1.1)\.
- Gosaiet al\.\(2024\)S\. J\. Gosai, R\. I\. Castro, N\. Fuentes, J\. C\. Butts, K\. Mouri, M\. Alasoadura, S\. Kales, T\. T\. L\. Nguyen, R\. R\. Noche, A\. S\. Rao, M\. T\. Joy, P\. C\. Sabeti, S\. K\. Reilly, and R\. TewheyMachine\-guided design of cell\-type\-targeting cis\-regulatory elements\.Nature634\(8036\),pp\. 1211–1220\.External Links:[Document](https://dx.doi.org/10.1038/s41586-024-08070-z),[Link](https://doi.org/10.1038/s41586-024-08070-z)Cited by:[§3\.1](https://arxiv.org/html/2609.35924#S3.SS1.p1.1)\.
- Gruveret al\.\(2023\)N\. Gruver, S\. Stanton, N\. C\. Frey, T\. G\. J\. Rudner, I\. Hotzel, J\. Lafrance\-Vanasse, A\. Rajpal, K\. Cho, and A\. G\. WilsonProtein design with guided discrete diffusion\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 12489–12517\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2023/hash/29591f355702c3f4436991335784b503-Abstract-Conference.html)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px2.p1.1)\.
- Hanu and Unitary team \(2020\)L\. Hanu and Unitary teamDetoxify\.External Links:[Document](https://dx.doi.org/10.5281/zenodo.7925667),[Link](https://github.com/unitaryai/detoxify)Cited by:[§D\.1](https://arxiv.org/html/2609.35924#A4.SS1.p2.1)\.
- Jeonet al\.\(2026\)K\. Jeon, T\. Vuong, and M\. TaoVGB for masked diffusion model: efficient test\-time scaling for reward satisfaction and sample editing\.External Links:2606\.28301,[Link](https://arxiv.org/abs/2606.28301)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px3.p1.1),[Appendix D](https://arxiv.org/html/2609.35924#A4.p2.1),[Appendix E](https://arxiv.org/html/2609.35924#A5.p1.1)\.
- Khosraviet al\.\(2019\)P\. Khosravi, Y\. Choi, Y\. Liang, A\. Vergari, and G\. Van den BroeckOn tractable computation of expected predictions\.InAdvances in Neural Information Processing Systems,Vol\.32\.External Links:[Link](https://arxiv.org/abs/1910.02182)Cited by:[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p3.1)\.
- Kimet al\.\(2025\)J\. Kim, S\. Kim, T\. Lee, D\. Z\. Pan, H\. Kim, S\. Kakade, and S\. ChenFine\-tuning masked diffusion for provable self\-correction\.arXiv preprint arXiv:2510\.01384\.Note:Jaeyeon Kim and Seunggeun Kim contributed equally; Taekyun Lee is also a co\-first authorCited by:[Appendix D](https://arxiv.org/html/2609.35924#A4.p2.1)\.
- Kimet al\.\(2026\)J\. Kim, T\. Yoon, P\. Phunyaphibarn, S\. Kim, M\. Mardani, and M\. SungContrastive distribution matching for amortized sequential monte carlo in discrete diffusion\.arXiv preprint arXiv:2605\.23346\.Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px3.p1.1),[Appendix E](https://arxiv.org/html/2609.35924#A5.p1.1)\.
- Konget al\.\(2026\)Z\. Kong, Y\. Dong, Y\. Wu, Z\. Liang, J\. Wu, and H\. XuMP2D: constrained monte carlo tree\-guided diffusion for multi\-objective protein sequence design\.InProceedings of the Thirty\-Fifth International Joint Conference on Artificial Intelligence, IJCAI\-26,D\. Calvanese \(Ed\.\),pp\. 5540–5548\.Note:Main TrackExternal Links:[Document](https://dx.doi.org/10.24963/ijcai.2026/617),[Link](https://doi.org/10.24963/ijcai.2026/617)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px4.p1.1)\.
- Levine \(2018\)S\. LevineReinforcement learning and control as probabilistic inference: tutorial and review\.arXiv preprint arXiv:1805\.00909\.External Links:1805\.00909,[Link](https://arxiv.org/abs/1805.00909)Cited by:[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.
- Liet al\.\(2026\)I\. Li, Z\. Shao, B\. Wang, R\. Yu, G\. Van den Broeck, and A\. LiuBreaking the factorization barrier in diffusion language models\.InProceedings of the 43rd International Conference on Machine Learning,External Links:[Link](https://arxiv.org/abs/2603.00045)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1),[§C\.1](https://arxiv.org/html/2609.35924#A3.SS1.p1.1),[§1](https://arxiv.org/html/2609.35924#S1.p3.1),[§2\.2](https://arxiv.org/html/2609.35924#S2.SS2.p1.4),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.
- Liet al\.\(2025\)X\. Li, Y\. Zhao, C\. Wang, G\. Scalia, G\. Eraslan, S\. Nair, T\. Biancalani, S\. Ji, A\. Regev, S\. Levine, and M\. UeharaDerivative\-free guidance in continuous and discrete diffusion models with soft value\-based decoding\.InAdvances in Neural Information Processing Systems,Vol\.38\.External Links:[Document](https://dx.doi.org/10.52202/085713-3194),[Link](https://proceedings.neurips.cc/paper_files/paper/2025/hash/899af0d66d8850318a20781484416152-Abstract-Conference.html)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px2.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.
- Linet al\.\(2020\)B\. Y\. Lin, W\. Zhou, M\. Shen, P\. Zhou, C\. Bhagavatula, Y\. Choi, and X\. RenCommonGen: a constrained text generation challenge for generative commonsense reasoning\.InFindings of the Association for Computational Linguistics: EMNLP 2020,pp\. 1823–1840\.External Links:[Document](https://dx.doi.org/10.18653/v1/2020.findings-emnlp.165),[Link](https://aclanthology.org/2020.findings-emnlp.165/)Cited by:[§3\.1](https://arxiv.org/html/2609.35924#S3.SS1.p1.1)\.
- Liuet al\.\(2025\)A\. Liu, O\. Broadrick, M\. Niepert, and G\. Van den BroeckDiscrete copula diffusion\.InInternational Conference on Learning Representations,Y\. Yue, A\. Garg, N\. Peng, F\. Sha, and R\. Yu \(Eds\.\),Vol\.2025,pp\. 88953–88979\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/file/dd1fef536655685898a6602bfbf16857-Paper-Conference.pdf)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px1.p1.1)\.
- Merityet al\.\(2017\)S\. Merity, C\. Xiong, J\. Bradbury, and R\. SocherPointer sentinel mixture models\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=Byj72udxe)Cited by:[§C\.1](https://arxiv.org/html/2609.35924#A3.SS1.p1.1)\.
- Mohri \(2009\)M\. MohriWeighted automata algorithms\.InHandbook of Weighted Automata,M\. Droste, W\. Kuich, and H\. Vogler \(Eds\.\),pp\. 213–254\.External Links:[Document](https://dx.doi.org/10.1007/978-3-642-01492-5%5F6),[Link](https://link.springer.com/chapter/10.1007/978-3-642-01492-5_6)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1),[§2\.4](https://arxiv.org/html/2609.35924#S2.SS4.p3.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p2.1)\.
- Nieet al\.\(2025\)S\. Nie, F\. Zhu, Z\. You, X\. Zhang, J\. Ou, J\. Hu, J\. Zhou, Y\. Lin, J\. Wen, and C\. LiLarge language diffusion models\.InAdvances in Neural Information Processing Systems,Vol\.38\.External Links:[Document](https://dx.doi.org/10.52202/085713-1689),2502\.09992,[Link](https://arxiv.org/abs/2502.09992)Cited by:[§1](https://arxiv.org/html/2609.35924#S1.p1.1)\.
- Nisonoffet al\.\(2025\)H\. Nisonoff, J\. Xiong, S\. Allenspach, and J\. ListgartenUnlocking guidance for discrete state\-space diffusion and flow models\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 36052–36106\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/file/597254dc45be8c166d3ccf0ba2d56325-Paper-Conference.pdf)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px2.p1.1),[Appendix E](https://arxiv.org/html/2609.35924#A5.p1.1),[§1](https://arxiv.org/html/2609.35924#S1.p3.1)\.
- Phunyaphibarn and Sung \(2026\)P\. Phunyaphibarn and M\. SungReward\-guided discrete diffusion via clean\-sample markov chain for molecule and biological sequence design\.InProceedings of the 2nd DeLTa Workshop at ICLR,External Links:2602\.09424,[Link](https://arxiv.org/abs/2602.09424)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2609.35924#S1.p3.1)\.
- Radfordet al\.\(2019\)A\. Radford, J\. Wu, R\. Child, D\. Luan, D\. Amodei, and I\. SutskeverLanguage models are unsupervised multitask learners\.Technical reportOpenAI\.Cited by:[§D\.1](https://arxiv.org/html/2609.35924#A4.SS1.p2.1)\.
- Schiffet al\.\(2025\)Y\. Schiff, S\. Sahoo, H\. Phung, G\. Wang, S\. Boshar, H\. Dalla\-torre, B\. Almeida, A\. Rush, T\. Pierrot, and V\. KuleshovSimple guidance mechanisms for discrete diffusion models\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 43776–43821\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/file/6cc31b44d88dce8380d36e81485cd07f-Paper-Conference.pdf)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px2.p1.1),[Appendix E](https://arxiv.org/html/2609.35924#A5.p1.1),[§1](https://arxiv.org/html/2609.35924#S1.p3.1)\.
- Sureshet al\.\(2025\)T\. Suresh, D\. Banerjee, S\. Ugare, S\. Misailovic, and G\. SinghDINGO: constrained inference for diffusion LLMs\.InAdvances in Neural Information Processing Systems,Vol\.38\.External Links:[Document](https://dx.doi.org/10.52202/085713-5362),[Link](https://proceedings.neurips.cc/paper_files/paper/2025/hash/eb17a2030d1bd4a1bd29531bcd626705-Abstract-Conference.html)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1)\.
- Sutton and McCallum \(2012\)C\. Sutton and A\. McCallumAn introduction to conditional random fields\.Foundations and Trends in Machine Learning4\(4\),pp\. 267–373\.External Links:[Document](https://dx.doi.org/10.1561/2200000013),[Link](https://doi.org/10.1561/2200000013)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px1.p1.1)\.
- van Kriekenet al\.\(2025\)E\. van Krieken, P\. Minervini, E\. M\. Ponti, and A\. VergariNeurosymbolic diffusion models\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 150640–150682\.External Links:[Document](https://dx.doi.org/10.52202/085713-4535),[Link](https://proceedings.neurips.cc/paper_files/paper/2025/hash/c60bd92a01804b7df0540ed7ca2f7c05-Abstract-Conference.html)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p2.1)\.
- Vergariet al\.\(2021\)A\. Vergari, Y\. Choi, A\. Liu, S\. Teso, and G\. Van den BroeckA compositional atlas of tractable circuit operations for probabilistic inference\.InAdvances in Neural Information Processing Systems,Vol\.34\.External Links:[Link](https://starai.cs.ucla.edu/papers/VergariNeurIPS21.pdf)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px6.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p3.1)\.
- Wanget al\.\(2026\)W\. Wang, Y\. Yang, W\. Deng, and P\. XuInference\-time alignment of diffusion models via trust\-region iterative twisted sequential monte carlo\.External Links:2605\.25123,[Link](https://arxiv.org/abs/2605.25123)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px3.p1.1)\.
- Wenget al\.\(2025\)G\. Y\. Weng, B\. Wang, and G\. Van den BroeckTRACE back from the future: a probabilistic reasoning approach to controllable language generation\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267\.External Links:[Link](https://arxiv.org/abs/2504.18535)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px5.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.
- Wuet al\.\(2022\)R\. Wu, F\. Ding, R\. Wang, R\. Shen, X\. Zhang, S\. Luo, C\. Su, Z\. Wu, Q\. Xie, B\. Berger, J\. Ma, and J\. PengHigh\-resolution de novo structure prediction from primary sequence\.bioRxiv\.External Links:[Document](https://dx.doi.org/10.1101/2022.07.21.500999),[Link](https://www.biorxiv.org/content/10.1101/2022.07.21.500999)Cited by:[§3\.1](https://arxiv.org/html/2609.35924#S3.SS1.p1.1)\.
- Yang and Klein \(2021\)K\. Yang and D\. KleinFUDGE: controlled text generation with future discriminators\.InProceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,pp\. 3511–3535\.External Links:[Document](https://dx.doi.org/10.18653/v1/2021.naacl-main.276),[Link](https://aclanthology.org/2021.naacl-main.276/)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px5.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.
- Yanget al\.\(2026\)Z\. Yang, H\. Liu, C\. Cao, and B\. SuD3LM: a discrete DNA diffusion language model for bidirectional DNA understanding and generation\.External Links:2603\.01780,[Link](https://arxiv.org/abs/2603.01780)Cited by:[§1](https://arxiv.org/html/2609.35924#S1.p1.1)\.
- Yeet al\.\(2025\)J\. Ye, Z\. Xie, L\. Zheng, J\. Gao, Z\. Wu, X\. Jiang, Z\. Li, and L\. KongDream 7b: diffusion large language models\.External Links:2508\.15487,[Link](https://arxiv.org/abs/2508.15487)Cited by:[§1](https://arxiv.org/html/2609.35924#S1.p1.1)\.
- Yusufet al\.\(2026\)A\. Yusuf, Z\. Jiang, and M\. ParkThe safety\-aware denoiser for text diffusion models\.External Links:2605\.08116,[Link](https://arxiv.org/abs/2605.08116)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px3.p1.1)\.
- Zhanget al\.\(2023\)H\. Zhang, M\. Dang, N\. Peng, and G\. Van den BroeckTractable control for autoregressive language generation\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202\.External Links:[Link](https://arxiv.org/abs/2304.07438)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px5.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.
- Zhanget al\.\(2025a\)H\. Zhang, M\. Dang, B\. Wang, S\. Ermon, N\. Peng, and G\. Van den BroeckScaling probabilistic circuits via Monarch matrices\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 74804–74818\.External Links:[Link](https://proceedings.mlr.press/v267/zhang25q.html)Cited by:[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p3.1)\.
- Zhanget al\.\(2024\)H\. Zhang, P\. Kung, M\. Yoshida, G\. Van den Broeck, and N\. PengAdaptable logical control for large language models\.InAdvances in Neural Information Processing Systems,Vol\.37\.External Links:[Link](https://arxiv.org/abs/2406.13892)Cited by:[Appendix J](https://arxiv.org/html/2609.35924#A10.SS0.SSS0.Px5.p1.1),[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.
- Zhanget al\.\(2025b\)H\. Zhang, B\. Wang, M\. Arenas, and G\. Van den BroeckRestructuring tractable probabilistic circuits\.InProceedings of the 28th International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.258,pp\. 2566–2574\.External Links:[Link](https://proceedings.mlr.press/v258/zhang25f.html)Cited by:[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p3.1)\.
- Zhaoet al\.\(2024\)S\. Zhao, R\. Brekelmans, A\. Makhzani, and R\. B\. GrosseProbabilistic inference in language models via twisted sequential Monte Carlo\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 60704–60748\.External Links:[Link](https://proceedings.mlr.press/v235/zhao24c.html)Cited by:[§3\.3](https://arxiv.org/html/2609.35924#S3.SS3.p1.1)\.

## Guide to the Appendix

This appendix follows the objects and claims introduced in the main paper\. Secs\.[A](https://arxiv.org/html/2609.35924#A1)to[C](https://arxiv.org/html/2609.35924#A3)give the formal derivations, computational boundary, and construction of the carrier and objectives\. Secs\.[D](https://arxiv.org/html/2609.35924#A4)to[F](https://arxiv.org/html/2609.35924#A6)specify the evaluation contracts, comparison rules, frozen configurations, and qualifications needed for the main results\. The final three sections provide canonical algorithms, process diagnostics, and evidence provenance\. Current benchmark endpoints are kept separate from DEV or TRAIN\-derived diagnostics and from historical cohorts\.

##### Reader conventions\.

TRAIN, DEV, and TEST denote fitting, configuration selection, and final evaluation roles\. A*frozen configuration*has its model, objective, hyperparameters, prompt or structured input, and evaluator fixed before final evaluation\. The*host*is the unchanged pretrained diffusion backbone and its original update rule\. A*port*is our implementation of a published algorithmic idea on that host and does not imply author\-code identity\. NFE denotes the realized number of denoiser row\-forward evaluations\. Full denotes the task\-native full budget used in Tab\.[1](https://arxiv.org/html/2609.35924#S2.T1); it does not imply equal total compute across methods\.

For a direct route from the main paper, the fixed\-step law and exactness lead to Secs\.[A](https://arxiv.org/html/2609.35924#A1)to[B](https://arxiv.org/html/2609.35924#A2); the carrier and fitted objectives lead to Sec\.[C](https://arxiv.org/html/2609.35924#A3); the benchmark table and budget curves lead to Secs\.[D](https://arxiv.org/html/2609.35924#A4)to[F](https://arxiv.org/html/2609.35924#A6); and Fig\.[4](https://arxiv.org/html/2609.35924#S3.F4)leads to Sec\.[H](https://arxiv.org/html/2609.35924#A8)\.

## Appendix AAdditional Method Details and Guarantees

### A\.1Fixed\-step interface and HMM realization

This appendix states precisely what is normalized, what is compiled, and where approximations enter\. Fix one denoising update and one block\. Letx=\(x1,…,xL\)x=\(x\_\{1\},\\ldots,x\_\{L\}\)be the block tokens and let𝒮=∏i𝒮i\\mathcal\{S\}=\\prod\_\{i\}\\mathcal\{S\}\_\{i\}be the candidate support fixed before the dynamic program\. At the interface level,et,ie\_\{t,i\}is frozen denoiser evidence,KiK\_\{i\}is a nonnegative target\-free carrier factor, and\(ψC,i,ηC\)\(\\psi\_\{C,i\},\\eta\_\{C\}\)is the compiled objective\. These are the same objects as in Sec\.[2\.4](https://arxiv.org/html/2609.35924#S2.SS4); the appendix does not redefine the method as an HMM\.

The target\-free hidden Markov model \(HMM\) used by the structured\-carrier implementation is one realization ofKiK\_\{i\}\. It has latent pathh=\(h1,…,hL\)h=\(h\_\{1\},\\ldots,h\_\{L\}\), initial distributionπ\\pi, transition matrixAA, and token emissionsEE\. With frozen denoiser log evidenceℓi​\(v\)\\ell\_\{i\}\(v\), evidence temperatureτe\\tau\_\{\\rm e\}, and carrier\-emission temperatureτm\\tau\_\{\\rm m\}, the retained base score is

log⁡q0𝒮​\(x,h\)≐\\displaystyle\\log q\_\{0\}^\{\\mathcal\{S\}\}\(x,h\)\\doteq\{\}∑i=1Lℓi​\(xi\)τe\+log⁡π⁡\(h1\)\+∑i=2Llog⁡A⁡\(hi∣hi−1\)\\displaystyle\\sum\_\{i=1\}^\{L\}\\frac\{\\ell\_\{i\}\(x\_\{i\}\)\}\{\\tau\_\{\\rm e\}\}\+\\log\\pi\(h\_\{1\}\)\+\\sum\_\{i=2\}^\{L\}\\log A\(h\_\{i\}\\mid h\_\{i\-1\}\)\+∑i=1Llog⁡E⁡\(xi∣hi\)τm,x∈𝒮,\\displaystyle\+\\sum\_\{i=1\}^\{L\}\\frac\{\\log E\(x\_\{i\}\\mid h\_\{i\}\)\}\{\\tau\_\{\\rm m\}\},\\qquad x\\in\\mathcal\{S\},\(22\)where≐\\doteqdenotes equality up to a path\-independent normalizer\. For a masked position,ℓi​\(v\)=log⁡pθ​\(x0i=v∣xt\)\\ell\_\{i\}\(v\)=\\log p\_\{\\theta\}\(x\_\{0\}^\{i\}=v\\mid x\_\{t\}\); the effective unary factor is proportional toexp⁡\{ℓi​\(v\)/τe\}\\exp\\\{\\ell\_\{i\}\(v\)/\\tau\_\{\\rm e\}\\\}, reducing to Eq\.[2](https://arxiv.org/html/2609.35924#S2.E2)atτe=1\\tau\_\{\\rm e\}=1\. Observed tokens remain clamped\. For a fixed prefix,π\\piis replaced by the predictive distribution for the first block state: filter the prefix to obtain its final\-state posterior, then apply one carrier transition before scoring the first block emission\. The neutral one\-state identity carrier is represented by a unitKiK\_\{i\}factor\.

Letaia\_\{i\}be the reward state andsi=\(hi,ai\)s\_\{i\}=\(h\_\{i\},a\_\{i\}\)the product state\. Fori\>1i\>1, an edgeei=\(si−1,v,si\)e\_\{i\}=\(s\_\{i\-1\},v,s\_\{i\}\)has log score

gi​\(ei\)=\\displaystyle g\_\{i\}\(e\_\{i\}\)=\{\}ℓi​\(v\)τe\+log⁡A⁡\(hi∣hi−1\)\+log⁡E⁡\(v∣hi\)τm\+λ​ri​\(ai−1,v\),\\displaystyle\\frac\{\\ell\_\{i\}\(v\)\}\{\\tau\_\{\\rm e\}\}\+\\log A\(h\_\{i\}\\mid h\_\{i\-1\}\)\+\\frac\{\\log E\(v\\mid h\_\{i\}\)\}\{\\tau\_\{\\rm m\}\}\+\\lambda r\_\{i\}\(a\_\{i\-1\},v\),\(23\)subject tov∈𝒮iv\\in\\mathcal\{S\}\_\{i\}andai=δ⁡\(ai−1,v\)a\_\{i\}=\\delta\(a\_\{i\-1\},v\)\. The first edge uses this predictive carrier distribution \(orπ\\piwithout a prefix\) in place of a transition from the dummy stateh0h\_\{0\}\.

Let𝒢=\(𝒩,ℰ\)\\mathcal\{G\}=\(\\mathcal\{N\},\\mathcal\{E\}\)be the resulting layered acyclic graph\. A vertex at leveliiis a retained product statesi=\(hi,ai\)s\_\{i\}=\(h\_\{i\},a\_\{i\}\); an edgeei=\(si−1,xi,si\)e\_\{i\}=\(s\_\{i\-1\},x\_\{i\},s\_\{i\}\)is present only whenxix\_\{i\}is in the declared token support, the carrier transition is allowed, andai=δ⁡\(ai−1,xi\)a\_\{i\}=\\delta\(a\_\{i\-1\},x\_\{i\}\)\. Define

W⁡\(ξ\)=exp⁡\{∑i=1Lgi​\(ei\)\+log⁡ηC​\(aL\)\}W\(\\xi\)=\\exp\\\!\\left\\\{\\sum\_\{i=1\}^\{L\}g\_\{i\}\(e\_\{i\}\)\+\\log\\eta\_\{C\}\(a\_\{L\}\)\\right\\\}\(24\)for a complete pathξ=\(e1,…,eL\)\\xi=\(e\_\{1\},\\ldots,e\_\{L\}\), usinglog⁡0=−∞\\log 0=\-\\infty\. The terminal factorηC\\eta\_\{C\}is the one in Eq\.[17](https://arxiv.org/html/2609.35924#S2.E17); it is not multiplied by the soft reward strength\. The path partition isZ𝒢=∑ξ∈𝒢W⁡\(ξ\)Z\_\{\\mathcal\{G\}\}=\\sum\_\{\\xi\\in\\mathcal\{G\}\}W\(\\xi\)\. The method samplesW⁡\(ξ\)/Z𝒢W\(\\xi\)/Z\_\{\\mathcal\{G\}\}when0<Z𝒢<∞0<Z\_\{\\mathcal\{G\}\}<\\inftyand the ancestral temperature is one\. The special cases in Tab\.[2](https://arxiv.org/html/2609.35924#A1.T2)share this construction\.

Table 2:Special cases of the same graph construction\. The identity carrier is an ablation of the full method; the identity reward controller has one state\.
### A\.2Exact compilation of count energies

We suppress the fixed condition indexCChere and allow position\-dependent token coefficientsuiu\_\{i\}\. Shared token coefficients are the special caseui​\(u\)=uuu\_\{i\}\(u\)=u\_\{u\}\.

Let𝒫=\{pj\}j=1J\\mathcal\{P\}=\\\{p\_\{j\}\\\}\_\{j=1\}^\{J\}be the selected token patterns and let the Aho–Corasick output set𝒪⁡\(ai−1,xi\)\\mathcal\{O\}\(a\_\{i\-1\},x\_\{i\}\)contain every pattern that ends after consumingxix\_\{i\}\([Aho and Corasick, 1975](https://arxiv.org/html/2609.35924#bib.bib23)\)\. The compiler assigns

ri\(ai−1,xi\)=ui\(xi\)\+∑j:pj∈𝒪⁡\(ai−1,xi\)wj\.r\_\{i\}\(a\_\{i\-1\},x\_\{i\}\)=u\_\{i\}\(x\_\{i\}\)\+\\sum\_\{j:p\_\{j\}\\in\\mathcal\{O\}\(a\_\{i\-1\},x\_\{i\}\)\}w\_\{j\}\.\(25\)
###### Lemma A\.1\(Count\-energy compilation\)\.

For every token sequencexx, including sequences with overlapping pattern occurrences,

∑i=1Lri​\(ai−1,xi\)=∑i=1Lui​\(xi\)\+∑j=1Jwj​cj​\(x\)=Rϕ​\(x\)−b\.\\sum\_\{i=1\}^\{L\}r\_\{i\}\(a\_\{i\-1\},x\_\{i\}\)=\\sum\_\{i=1\}^\{L\}u\_\{i\}\(x\_\{i\}\)\+\\sum\_\{j=1\}^\{J\}w\_\{j\}c\_\{j\}\(x\)=R\_\{\\phi\}\(x\)\-b\.

###### Proof\.

The token term contributes once at every position\. Aho–Corasick reports a pattern exactly at each position at which one occurrence ends; output links retain simultaneous suffix matches, so overlapping and nested occurrences are not discarded\. Summing the reportedwjw\_\{j\}terms therefore contributeswjw\_\{j\}exactlycj​\(x\)c\_\{j\}\(x\)times\. The fitted intercept is absent because it is constant across all paths in the same normalized kernel\. ∎

##### Automatic weighted\-automaton construction\.

The compiler inserts every selected token pattern into a trie\. Breadth\-first failure links map a missing transition to the longest suffix that is also a trie prefix\. The reward stored at a state is its own terminal weight plus the reward at its failure state\. Consequently one transition emits the sum of*all*selected patterns ending at that position, including nested and overlapping matches\. For the candidate tokens admitted by a denoising block, the compiler cachesδ⁡\(a,v\)\\delta\(a,v\)and the phrase\-match reward for every reachable stateaaand tokenvv; the position\-dependent token term is added when scoring the edge at positionii\.

##### Record\-conditioned lexical DFA\.

CommonGen uses the same transition interface but no learned weights\. For each record, the adapter enumerates the accepted standalone forms of every concept: the base form, its regular plural \(s,es, ories\), and its possessive form\. These finite token strings are compiled into a lexical prefix machine\. A DFA state stores the active form prefixes together with a bit mask of concepts already completed at word boundaries; a forbidden concept, when present, enters a reject sink\. The terminal score is zero only when every required bit is set and no reject state has been reached, and is−∞\-\\inftyotherwise\. We enumerate only states reachable under the declared per\-position token support\. If that support cannot reach acceptance, the adapter fails closed rather than softening the constraint\.

### A\.3Exact compilation and oracle approximation

Exact compilation means that the local transition and terminal weights multiply to a positive sequence\-independent constant times the fitted sequence weight\. For the count score, Lem\.[A\.1](https://arxiv.org/html/2609.35924#A1.Thmtheorem1)gives

∏i=1Lexp⁡\{λ​rC,i​\(ai−1,x0i\)\}=exp⁡\{−λ​bC\}​exp​\{λ​Rϕ,C​\(x0\)\}\.\\prod\_\{i=1\}^\{L\}\\exp\\\{\\lambda r\_\{C,i\}\(a\_\{i\-1\},x\_\{0\}^\{i\}\)\\\}=\\exp\\\{\-\\lambda b\_\{C\}\\\}\\exp\\\{\\lambda R\_\{\\phi,C\}\(x\_\{0\}\)\\\}\.The first factor cancels from the guided distribution\. For a hard recognizer, the compiled weight equals the acceptance indicator, including its zero set\. Thus compilation implements the chosen objective without changing its guided law\. It does not guarantee that a fitted objective matches an unrestricted oracle\.

###### Proof of Prop\.[2\.1](https://arxiv.org/html/2609.35924#S2.Thmtheorem1)\.

All distributions below use the same fixedxtx\_\{t\}, base distribution, and support\. Letd⁡\(x0\)=log⁡WC​\(x0\)−log⁡WCoracle​\(x0\)d\(x\_\{0\}\)=\\log W\_\{C\}\(x\_\{0\}\)\-\\log W\_\{C\}^\{\\mathrm\{oracle\}\}\(x\_\{0\}\)and define

A⁡\(s\)=log⁡𝔼qCoracle​\[es​d​\(x0\)\],qs​\(x0\)=qCoracle​\(x0\)​es​d​\(x0\)−A⁡\(s\)\.A\(s\)=\\log\\mathbb\{E\}\_\{q\_\{C\}^\{\\mathrm\{oracle\}\}\}\[e^\{sd\(x\_\{0\}\)\}\],\\qquad q\_\{s\}\(x\_\{0\}\)=q\_\{C\}^\{\\mathrm\{oracle\}\}\(x\_\{0\}\)e^\{sd\(x\_\{0\}\)\-A\(s\)\}\.Thenq1=qCq\_\{1\}=q\_\{C\},A′​\(s\)=𝔼qs​\[d\]A^\{\\prime\}\(s\)=\\mathbb\{E\}\_\{q\_\{s\}\}\[d\], andA′′​\(s\)=Varqs⁡\(d\)A^\{\\prime\\prime\}\(s\)=\\operatorname\{Var\}\_\{q\_\{s\}\}\(d\)\. Since\|d−c\|≤ϵ\|d\-c\|\\leq\\epsilon,A′′​\(s\)≤𝔼qs​\[\(d−c\)2\]≤ϵ2A^\{\\prime\\prime\}\(s\)\\leq\\mathbb\{E\}\_\{q\_\{s\}\}\[\(d\-c\)^\{2\}\]\\leq\\epsilon^\{2\}\. Consequently,

DKL\(qCoracle∥qC\)=A\(1\)−A\(0\)−A′\(0\)=∫01\(1−s\)A′′\(s\)ds≤ϵ2/2\.D\_\{\\mathrm\{KL\}\}\(q\_\{C\}^\{\\mathrm\{oracle\}\}\\\|q\_\{C\}\)=A\(1\)\-A\(0\)\-A^\{\\prime\}\(0\)=\\int\_\{0\}^\{1\}\(1\-s\)A^\{\\prime\\prime\}\(s\)\\,ds\\leq\\epsilon^\{2\}/2\.Replacing the integrand bys​A′′​\(s\)sA^\{\\prime\\prime\}\(s\)gives the same bound in the reverse direction\. Exact compilation leavesq1q\_\{1\}unchanged by the constant\-cancellation argument above\. ∎

##### Function\-class gap and actual fitting error\.

On this finite support, letℱm\\mathcal\{F\}\_\{m\}be a class of log\-weights that admit exact compilation under representation budgetmm\. Define

δm=inff∈ℱm,c∈ℝ‖f−log⁡WCoracle−c‖∞\.\\delta\_\{m\}=\\inf\_\{f\\in\\mathcal\{F\}\_\{m\},\\,c\\in\\mathbb\{R\}\}\\\|f\-\\log W\_\{C\}^\{\\mathrm\{oracle\}\}\-c\\\|\_\{\\infty\}\.For the actual fitted log\-weightlog⁡WC,m∈ℱm\\log W\_\{C,m\}\\in\\mathcal\{F\}\_\{m\}, letϵm=infc‖log⁡WC,m−log⁡WCoracle−c‖∞\\epsilon\_\{m\}=\\inf\_\{c\}\\\|\\log W\_\{C,m\}\-\\log W\_\{C\}^\{\\mathrm\{oracle\}\}\-c\\\|\_\{\\infty\}andρm=ϵm−δm≥0\\rho\_\{m\}=\\epsilon\_\{m\}\-\\delta\_\{m\}\\geq 0\. The proposition applies withϵm=δm\+ρm\\epsilon\_\{m\}=\\delta\_\{m\}\+\\rho\_\{m\}, not with the class infimum alone\. Nested classes makeδm\\delta\_\{m\}nonincreasing, but do not imply that it tends to zero\. If bothδm\\delta\_\{m\}andρm\\rho\_\{m\}tend to zero, the fixed\-step KL gap does too\. Without attainment,δm=0\\delta\_\{m\}=0means membership in the closure modulo constants, not necessarily an exact finite representation\.

These are conditional approximation statements, not convergence guarantees for the current training procedure\. Prediction loss on training data does not establish uniform log\-weight error on generated sequences\. For positive Boltzmann weights, the comparison is between log\-weights, so guidance strength is already included\. If weights can be zero, first require matching feasible support and restrict the comparison to its positive part\. The result does not cover support mismatch, arbitrary pruning, non\-unit sampling temperature, or the full multi\-step diffusion distribution\.

##### The three normalizers\.

The main text uses three related but non\-interchangeable quantities\. On the same fixed support,

Z0​\(xt\)=B0​\(h0\),ZC​\(xt\)=𝔼q0​\[WC\]=M0​\(h0,ainit\)B0​\(h0\)\.Z\_\{0\}\(x\_\{t\}\)=B\_\{0\}\(h\_\{0\}\),\\qquad Z\_\{C\}\(x\_\{t\}\)=\\mathbb\{E\}\_\{q\_\{0\}\}\[W\_\{C\}\]=\\frac\{M\_\{0\}\(h\_\{0\},a\_\{\\mathrm\{init\}\}\)\}\{B\_\{0\}\(h\_\{0\}\)\}\.\(26\)ThusB0B\_\{0\}normalizes the neutral carrier–evidence joint,M0M\_\{0\}is the unnormalized total weight after adding the compiled objective, andZCZ\_\{C\}is the expected objective weight under the already normalizedq0q\_\{0\}\. When a scorer intercept is omitted during compilation, the normalized guided law is unchanged, butM0M\_\{0\}is multiplied by the corresponding path\-independent constant; all partition values in this appendix use the intercept\-free compiled\-weight convention\.

##### Meaning of the backward\-weight ratio\.

For a base\-reachable state withBi​\(h\)\>0B\_\{i\}\(h\)\>0, start the objective path atai=aa\_\{i\}=a\. The notationai:=aa\_\{i\}:=ainitializes the objective automaton for the continuation; it does not condition the neutral law on a past objective state\. Expanding the expectation in Eq\.[18](https://arxiv.org/html/2609.35924#S2.E18)gives

𝔼q0\[ηC\(aL\)∏j=i\+1LψC,j\(aj−1,x0j\)\|hi=h,xt;ai:=a\]\\displaystyle\\mathbb\{E\}\_\{q\_\{0\}\}\\\!\\left\[\\eta\_\{C\}\(a\_\{L\}\)\\prod\_\{j=i\+1\}^\{L\}\\psi\_\{C,j\}\(a\_\{j\-1\},x\_\{0\}^\{j\}\)\\,\\middle\|\\,h\_\{i\}=h,x\_\{t\};\\ a\_\{i\}:=a\\right\]\(27\)=∑x0i\+1:L,hi\+1:L∏j=i\+1Let,j​\(x0j\)​Kj​\(hj−1,x0j,hj\)Bi​\(h\)ηC\(aL\)∏j=i\+1LψC,j\(aj−1,x0j\)\\displaystyle=\\sum\_\{x\_\{0\}^\{i\+1:L\},h\_\{i\+1:L\}\}\\frac\{\\prod\_\{j=i\+1\}^\{L\}e\_\{t,j\}\(x\_\{0\}^\{j\}\)K\_\{j\}\(h\_\{j\-1\},x\_\{0\}^\{j\},h\_\{j\}\)\}\{B\_\{i\}\(h\)\}\\eta\_\{C\}\(a\_\{L\}\)\\prod\_\{j=i\+1\}^\{L\}\\psi\_\{C,j\}\(a\_\{j\-1\},x\_\{0\}^\{j\}\)=Mi​\(h,a\)Bi​\(h\)\.\\displaystyle=\\frac\{M\_\{i\}\(h,a\)\}\{B\_\{i\}\(h\)\}\.Eq\.[27](https://arxiv.org/html/2609.35924#A1.E27)follows by dividing the remaining product weights by their carrier\-only normalizerBi​\(h\)B\_\{i\}\(h\)and taking the expectation of the remaining objective factors, starting atai=aa\_\{i\}=a\. ThusMiM\_\{i\}itself is generally not a probability\. For indicator constraints,Mi/BiM\_\{i\}/B\_\{i\}is the continuation acceptance probability, with previous violations recorded in the objective state\. For soft objectives it is an expected weight and may exceed one\. This identity uses the unpruned product construction, or the same fixed per\-position token support in numerator and denominator\. If product\-state pruning makes the remaining support depend onaa, the matching carrier\-only normalizer must instead be computed on that same retained graph and generally depends on bothhhandaa\.

##### Guided sampling conditional\.

Fix\(h,a\)\(h,a\)withMi−1​\(h,a\)\>0M\_\{i\-1\}\(h,a\)\>0, and leta′=δC,i​\(a,u\)a^\{\\prime\}=\\delta\_\{C,i\}\(a,u\)\. Marginalizing the remaining assignments gives

qCjoint\(x0i=u,hi=h′∣hi−1=h,ai−1=a,xt\)\\displaystyle q\_\{C\}^\{\\mathrm\{joint\}\}\(x\_\{0\}^\{i\}=u,h\_\{i\}=h^\{\\prime\}\\mid h\_\{i\-1\}=h,a\_\{i\-1\}=a,x\_\{t\}\)\(28\)=∑x0i\+1:L,hi\+1:LqCjoint\(x0i=u,hi=h′,x0i\+1:L,hi\+1:L∣hi−1=h,ai−1=a,xt\)\\displaystyle=\\sum\_\{x\_\{0\}^\{i\+1:L\},h\_\{i\+1:L\}\}q\_\{C\}^\{\\mathrm\{joint\}\}\(x\_\{0\}^\{i\}=u,h\_\{i\}=h^\{\\prime\},x\_\{0\}^\{i\+1:L\},h\_\{i\+1:L\}\\mid h\_\{i\-1\}=h,a\_\{i\-1\}=a,x\_\{t\}\)=et,i​\(u\)​Ki​\(h,u,h′\)​ψC,i​\(a,u\)​Mi​\(h′,a′\)Mi−1​\(h,a\)\\displaystyle=\\frac\{e\_\{t,i\}\(u\)K\_\{i\}\(h,u,h^\{\\prime\}\)\\psi\_\{C,i\}\(a,u\)M\_\{i\}\(h^\{\\prime\},a^\{\\prime\}\)\}\{M\_\{i\-1\}\(h,a\)\}=q0\(x0i=u,hi=h′∣hi−1=h,xt\)ψC,i\(a,u\)Mi​\(h′,a′\)Bi​\(h′\)Bi−1​\(h\)Mi−1​\(h,a\)\.\\displaystyle=q\_\{0\}\(x\_\{0\}^\{i\}=u,h\_\{i\}=h^\{\\prime\}\\mid h\_\{i\-1\}=h,x\_\{t\}\)\\,\\psi\_\{C,i\}\(a,u\)\\frac\{M\_\{i\}\(h^\{\\prime\},a^\{\\prime\}\)\}\{B\_\{i\}\(h^\{\\prime\}\)\}\\frac\{B\_\{i\-1\}\(h\)\}\{M\_\{i\-1\}\(h,a\)\}\.The last equality uses Eq\.[10](https://arxiv.org/html/2609.35924#S2.E10)on base\-supported choices withBi​\(h′\)\>0B\_\{i\}\(h^\{\\prime\}\)\>0, with the same continuation support in both messages\. SinceBi−1​\(h\)/Mi−1​\(h,a\)B\_\{i\-1\}\(h\)/M\_\{i\-1\}\(h,a\)is constant across\(u,h′\)\(u,h^\{\\prime\}\), this gives Eq\.[19](https://arxiv.org/html/2609.35924#S2.E19)\. The direct fraction in the second equality computes the conditional without a separate carrier\-only backward pass\.

### A\.4Objective\-agnostic cache reuse

For corpus rows𝒟\\mathcal\{D\}and mining configurationη\\eta, the candidate miner is a deterministic mapℳ⁡\(𝒟,η\)\\mathcal\{M\}\(\\mathcal\{D\},\\eta\)based only on tokenized document frequency\. Its count matrix is likewise a deterministic map of the rows and candidate grammar\. Therefore, changing a target label while holding𝒟\\mathcal\{D\}andη\\etafixed does not require re\-mining or recounting\. Target changes rerun only score tests, selection, and fitting\. This separation is an algorithmic contract, not merely a cache optimization\.

### A\.5Strict minimum\-edit repair

Letyybe an observed sequence,FFa set of positions that must remain fixed,ℒ\\mathcal\{L\}the valid language, and𝒮\\mathcal\{S\}the declared token support\. We first compute

d⋆​\(y\)=minx∈𝒮∩ℒ,xF=yF⁡dH​\(x,y\)\.d^\{\\star\}\(y\)=\\min\_\{x\\in\\mathcal\{S\}\\cap\\mathcal\{L\},\\;x\_\{F\}=y\_\{F\}\}d\_\{H\}\(x,y\)\.\(29\)The repair kernel is then

qrepair\(x,h∣y\)∝q0𝒮\(x,h\)1\[x∈ℒ,xF=yF\]1\[dH\(x,y\)=d⋆\(y\)\]\.q\_\{\\rm repair\}\(x,h\\mid y\)\\propto q\_\{0\}^\{\\mathcal\{S\}\}\(x,h\)\\,\\mathbf\{1\}\[x\\in\\mathcal\{L\},\\ x\_\{F\}=y\_\{F\}\]\\,\\mathbf\{1\}\[d\_\{H\}\(x,y\)=d^\{\\star\}\(y\)\]\.\(30\)A forward min\-plus pass gives the cheapest prefix cost for every bounded\-stack state, and a backward min\-plus pass gives its cheapest valid completion\. An edge is retained exactly when its prefix cost, local substitution cost, and suffix cost sum tod⋆​\(y\)d^\{\\star\}\(y\)\. Ordinary sum\-product messages then weight this optimal subgraph by frozen denoiser evidence and the target\-free carrier; Alg\.[4](https://arxiv.org/html/2609.35924#alg4)samples from Eq\. \([30](https://arxiv.org/html/2609.35924#A1.E30)\)\.

The present contract does not cover insertions, deletions, an unbounded pushdown language, or dynamic multi\-step repair evidence\. The development\-only repair diagnostic is reported with the other diagnostics in App\.[H\.2](https://arxiv.org/html/2609.35924#A8.SS2)\.

### A\.6Exact backward inference and ancestral replay

###### Proposition A\.2\(Exactness of the compiled fixed\-step query\)\.

Fixxtx\_\{t\}, the evidence, and finite carrier and objective state spaces\. Assume all factors in Eq\.[16](https://arxiv.org/html/2609.35924#S2.E16)are finite and nonnegative, with0<Z=M0​\(h0,ainit\)<∞0<Z=M\_\{0\}\(h\_\{0\},a\_\{\\mathrm\{init\}\}\)<\\infty\. In exact arithmetic, Eq\.[15](https://arxiv.org/html/2609.35924#S2.E15)and the unit\-temperature conditionals in Eq\.[19](https://arxiv.org/html/2609.35924#S2.E19)sample the normalized compiled joint\.

###### Proof\.

The terminal message is the remaining weightηC​\(aL\)\\eta\_\{C\}\(a\_\{L\}\)\. Backward induction shows that each preceding message sums all compatible remaining factor products\. Thus the denominator of Eq\.[19](https://arxiv.org/html/2609.35924#S2.E19)is the sum of its numerators\. Only positive\-mass successors can be sampled, so each subsequent conditional is defined\. For a complete sampled path,

∏i=1Let,i​\(x0i\)​Ki​\(hi−1,x0i,hi\)​ψC,i​\(ai−1,x0i\)​Mi​\(hi,ai\)Mi−1​\(hi−1,ai−1\)\\displaystyle\\prod\_\{i=1\}^\{L\}\\frac\{e\_\{t,i\}\(x\_\{0\}^\{i\}\)K\_\{i\}\(h\_\{i\-1\},x\_\{0\}^\{i\},h\_\{i\}\)\\psi\_\{C,i\}\(a\_\{i\-1\},x\_\{0\}^\{i\}\)M\_\{i\}\(h\_\{i\},a\_\{i\}\)\}\{M\_\{i\-1\}\(h\_\{i\-1\},a\_\{i\-1\}\)\}=ηC​\(aL\)Z​∏i=1Let,i​\(x0i\)​Ki​\(hi−1,x0i,hi\)​ψC,i​\(ai−1,x0i\)\.\\displaystyle\{\}=\\frac\{\\eta\_\{C\}\(a\_\{L\}\)\}\{Z\}\\prod\_\{i=1\}^\{L\}e\_\{t,i\}\(x\_\{0\}^\{i\}\)K\_\{i\}\(h\_\{i\-1\},x\_\{0\}^\{i\},h\_\{i\}\)\\psi\_\{C,i\}\(a\_\{i\-1\},x\_\{0\}^\{i\}\)\.All intermediate messages cancel\. Summing out the carrier path recovers Eq\.[3](https://arxiv.org/html/2609.35924#S2.E3)\. The argument also applies to a fixed restricted graph when the same edges and factors are used for inference and sampling\. ∎

##### Log\-domain form on a retained graph\.

For a statesis\_\{i\}define the suffix mass

βi\(si\)=∑ξi\+1:L∣siexp\{∑j=i\+1Lgj\(ej\)\+logηC\(aL\)\}\.\\beta\_\{i\}\(s\_\{i\}\)=\\sum\_\{\\xi\_\{i\+1:L\}\\mid s\_\{i\}\}\\exp\\\!\\left\\\{\\sum\_\{j=i\+1\}^\{L\}g\_\{j\}\(e\_\{j\}\)\+\\log\\eta\_\{C\}\(a\_\{L\}\)\\right\\\}\.\(31\)At the terminal level,βL​\(hL,aL\)=exp⁡\{log⁡ηC​\(aL\)\}\\beta\_\{L\}\(h\_\{L\},a\_\{L\}\)=\\exp\\\{\\log\\eta\_\{C\}\(a\_\{L\}\)\\\}\. The ordinary sum\-product recursion is

βi−1\(si−1\)=∑ei:si−1→siexp\{gi\(ei\)\}βi\(si\)\.\\beta\_\{i\-1\}\(s\_\{i\-1\}\)=\\sum\_\{e\_\{i\}:s\_\{i\-1\}\\to s\_\{i\}\}\\exp\\\{g\_\{i\}\(e\_\{i\}\)\\\}\\beta\_\{i\}\(s\_\{i\}\)\.\(32\)Eq\. \([15](https://arxiv.org/html/2609.35924#S2.E15)\) is the same probability\-space recursion with the denoiser, carrier, and objective factors written explicitly\.

###### Corollary A\.3\(Exact replay on a retained graph\)\.

Under Prop\.[A\.2](https://arxiv.org/html/2609.35924#A1.Thmtheorem2), fix the candidate tokens and the retained product\-state graph\. Sampling each edge according to

p⁡\(ei∣si−1\)=exp⁡\{gi​\(ei\)\}​βi​\(si\)βi−1​\(si−1\)p\(e\_\{i\}\\mid s\_\{i\-1\}\)=\\frac\{\\exp\\\{g\_\{i\}\(e\_\{i\}\)\\\}\\beta\_\{i\}\(s\_\{i\}\)\}\{\\beta\_\{i\-1\}\(s\_\{i\-1\}\)\}\(33\)produces an exact sample fromW⁡\(ξ\)/Z𝒢W\(\\xi\)/Z\_\{\\mathcal\{G\}\}when0<Z𝒢<∞0<Z\_\{\\mathcal\{G\}\}<\\inftyandτa=1\\tau\_\{\\rm a\}=1\. This is the same telescoping argument as the proposition, restricted to the fixed retained graph rather than a second exactness claim\.

###### Corollary A\.4\(Hard\-DFA conditioning\)\.

WithηC\(aL\)=𝟏\[aL∈𝒜accept\]\\eta\_\{C\}\(a\_\{L\}\)=\\mathbf\{1\}\[a\_\{L\}\\in\\mathcal\{A\}\_\{\\mathrm\{accept\}\}\]and no soft reward factors, exact replay samples the retained base distribution conditioned on DFA acceptance\. This indicator is independent ofλ\\lambda, so hard constraints remain active even when soft guidance has zero strength\. If no accepting path exists,Z𝒢=0Z\_\{\\mathcal\{G\}\}=0and the correct behavior is a fail\-closed infeasibility record\.

##### Why non\-unit ancestral temperature is different\.

Dividing each prefix\-conditional logit byτa≠1\\tau\_\{\\rm a\}\\neq 1defines a valid tempered policy\. Because the backward message in one conditional also changes the state reached by later conditionals, the product of these locally tempered conditionals is not generally proportional to a single global powerW​\(ξ\)1/τaW\(\\xi\)^\{1/\\tau\_\{\\rm a\}\}\. We therefore report it as a policy choice rather than as an exact sample from Eq\. \([3](https://arxiv.org/html/2609.35924#S2.E3)\)\.

For example, consider three complete paths with weights\(1,1,4\)\(1,1,4\), where the first two share their first branch\. Atτa=2\\tau\_\{\\rm a\}=2, locally tempering the prefix conditionals gives probabilities approximately\(0\.2071,0\.2071,0\.5858\)\(0\.2071,0\.2071,0\.5858\), whereas globally normalizing the square\-root path weights gives\(0\.25,0\.25,0\.50\)\(0\.25,0\.25,0\.50\)\. Positive local temperature can preserve hard zero support, but it does not preserve the unit\-temperature sampling law\.

## Appendix BImplementation and Computational Cost

### B\.1Graph\-level time and memory

LetVi⊆𝒩V\_\{i\}\\subseteq\\mathcal\{N\}be the retained states at leveliiandEiE\_\{i\}the retained edges from leveli−1i\-1toii\. Write\|V\|=∑i\|Vi\|\|V\|=\\sum\_\{i\}\|V\_\{i\}\|and\|E\|=∑i\|Ei\|\|E\|=\\sum\_\{i\}\|E\_\{i\}\|\.

###### Theorem B\.1\(Finite\-graph complexity\)\.

The backward partition computation takes𝒪⁡\(\|E\|\)\\mathcal\{O\}\(\|E\|\)arithmetic operations\. Retaining all messages for replay uses𝒪⁡\(\|V\|\)\\mathcal\{O\}\(\|V\|\)message memory; partition\-only inference can stream levels using𝒪⁡\(maxi⁡\|Vi\|\)\\mathcal\{O\}\(\\max\_\{i\}\|V\_\{i\}\|\)message memory\. One replay is no more expensive than enumerating the outgoing edges of itsLLvisited states and is dominated by the preceding backward pass\.

###### Proof\.

Every backward message sums each outgoing retained edge once, so the total work is linear in the edge list\. A stored scalar message per retained vertex gives the replay bound; if no replay is required, the acyclic recurrence needs only two adjacent levels\. Replay visits exactly one state per level\. ∎

For candidate widthKK,HHcarrier states, andMMretained reward states, a dense Cartesian graph has𝒪⁡\(L​M​H\)\\mathcal\{O\}\(LMH\)vertices and at most𝒪⁡\(L​K​M​H2\)\\mathcal\{O\}\(LKMH^\{2\}\)edges\. The deterministic automaton transition fixes the next reward state; it does not introduce another factor ofMM\. With the identity carrier,H=1H=1and the time bound is𝒪⁡\(L​K​M\)\\mathcal\{O\}\(LKM\)\. In the implemented batched version, batch size multiplies graph work while enabling GPU parallelism; padding and packing determine the constant factor\.

These bounds begin after the finite graph is specified\. They do not make graph construction polynomial in every compact problem description: bounded stacks, concept bit masks, multiple controller products, and explicit Sudoku support can make the expanded state space large\. Reported computational cost therefore separates support construction or pre\-solving, retained edge storage, message workspace, backward arithmetic, and host\-model calls\. The𝒪⁡\(\|E\|\)\\mathcal\{O\}\(\|E\|\)and𝒪⁡\(\|V\|\)\\mathcal\{O\}\(\|V\|\)statements apply only to message passing on the materialized graph\.

### B\.2Measured Full\-generation time

The graph\-work bound alone does not determine wall time\. Wide product states can require specialized GPU reductions and sampling operators to avoid many small launches and host–device synchronizations\. We implemented targeted fast paths, including batched message passing and fused ancestral sampling, but did not exhaustively engineer a separate kernel for every task and hardware setting\. Tab\.[3](https://arxiv.org/html/2609.35924#A2.T3)measures the resulting implementations; it is not a lower bound on the method’s attainable latency\.

The primary measurements use NVIDIA RTX 4090 GPUs; measurements from a separate cloud GPU environment are marked in the table\. Each row uses the frozen Full schedule:b=32b=32for Dyck, CommonGen, and RTP,b=64b=64for Sudoku,b=48b=48for DNA, and one editable site per update for Protein\-1YCR\. Models and task\-specific configurations follow Tab\.[1](https://arxiv.org/html/2609.35924#S2.T1)and the DEV selections in Tab\.[10](https://arxiv.org/html/2609.35924#A5.T10)\. Each reported window generates 64 final outputs with the method’s native internal particle, classifier, or search work\. Static model loading is separate\. Timed steady\-state windows follow a real warmup; labeled first\-request windows include Graph capture or just\-in\-time kernel setup\. CUDA is synchronized before and after complete generation from prepared inputs to CPU\-available tokens\. Request\-specific controller construction, dynamic programming, ancestral sampling, transfers, and online model calls are included; independent evaluation is excluded\. External output batches and precision follow each frozen implementation\. Ratios are interpreted only within a matched GPU environment, precision, external batch, and timer boundary; input or cohort differences do not by themselves establish an algorithmic speed difference\.

Table 3:Complete online generation time in seconds for 64 final outputs at each task’s frozen Full budget\. Base is a compute reference; bold identifies the fastest measured non\-Base baseline within a GPU environment\. BoN\-4 is excluded\. Static model loading, warmup, disk output, and independent evaluation are excluded\. Per\-request controller construction, inference, sampling, transfers, and actual extra model calls are included; early stopping is retained\.†Measurements from a separate cloud GPU environment are shown for context and must not be divided by primary RTX 4090 measurements in the same cell\.‡This D\-CBG setting failed its predeclared DEV PPL cap; its measured time remains visible\. The RTP/LLaDA DG\-TAG and GILC ranges reverse order across repeats and use different native external batches\. The LLaDA/Sudoku MDM range includes a different\-card repeat; the same\-GPU comparison withCoffeeuses 72\.364\.wReused static Graph, with complete generation timed;ffirst request including Graph capture\. Times with different native batches, cohorts, or software stacks are descriptive unless the measurement conditions are matched\.
### B\.3What does and does not need a convergence theorem

The backward pass is a finite acyclic recursion, not an iterative fixed\-point algorithm: after exactlyLLlevels it has computed the partition and all suffix masses on the retained graph\. Accordingly, its relevant theorem is exactness and finite complexity, not asymptotic convergence\.

For a fixed selected feature design, the scorer objective in Eq\. \([37](https://arxiv.org/html/2609.35924#A3.E37)\) is convex\. This follows because binary logistic loss is convex in its affine logit, while theℓ1\\ell\_\{1\}and squaredℓ2\\ell\_\{2\}penalties are convex\. If both target classes occur and the token and AC coefficient blocks have positiveℓ2\\ell\_\{2\}penalties, the objective is coercive and has at least one finite minimizer; it is strongly convex in the regularized coefficient subspace\. These facts justify a global rather than local fitting target\.

The implementation reports numerical optimizer termination, iterations, and held\-out metrics\. We do not claim a new optimizer rate for its mixedℓ1/ℓ2\\ell\_\{1\}/\\ell\_\{2\}objective; such a rate would require a specified proximal solver and optimality residual, or a smooth reformulation\. Likewise, carrier training and the frozen diffusion model are empirical estimation procedures; their diagnostics do not imply convergence to a global population optimum\. Tab\.[4](https://arxiv.org/html/2609.35924#A2.T4)summarizes these claim boundaries\.

Table 4:Claim boundaries for “convergence\.”

## Appendix CCarrier and Objective Construction

### C\.1Carrier assets and scope

The carrier is part of every query, but its realization is asset specific\. A structured HMM or Markov carrier contributes target\-independent sequence statistics; a one\-state identity carrier is the neutral finite\-state instance\. Non\-identity carriers follow the same target\-free CoDD\-style training procedure\([Li et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib12)\), with asset\-specific data, state size, block length, and frozen checkpoint\. The identity carrier requires no training\. The LLaDA language artifact is trained on WikiText\-103\([Merity et al\., 2017](https://arxiv.org/html/2609.35924#bib.bib24)\), has 64 latent states, uses block length 32, and occupies 30\.88 MiB when serialized\. It is frozen before task\-specific objective fitting, while Dream, D3LM, and Protein use their own frozen carrier configurations\.

### C\.2Mining, selection, and fitting

Alg\.[1](https://arxiv.org/html/2609.35924#alg1)separates reusable corpus processing from target\-dependent statistics\. Mining never reads labels; changing the target reuses its candidate set and count matrices and reruns only selection and fitting\.

##### Objective\-agnostic candidate grammar\.

For training rowsx\(1\),…,x\(N\)x^\{\(1\)\},\\ldots,x^\{\(N\)\}, the document frequency of token patternppis

df⁡\(p\)=∑n=1N𝟏​\[p​occurs in​x\(n\)\]\.\\operatorname\{df\}\(p\)=\\sum\_\{n=1\}^\{N\}\\mathbf\{1\}\[p\\text\{ occurs in \}x^\{\(n\)\}\]\.The miner enumerates literal tokennn\-grams of orders one through four and keeps a pattern only whenm\|p\|≤df⁡\(p\)≤ρ​Nm\_\{\|p\|\}\\leq\\operatorname\{df\}\(p\)\\leq\\rho N\. The default thresholds are\(m1,m2,m3,m4\)=\(8,5,3,3\)\(m\_\{1\},m\_\{2\},m\_\{3\},m\_\{4\}\)=\(8,5,3,3\)andρ=0\.70\\rho=0\.70; deterministic ordering by decreasing document frequency, order, and token tuple applies the 80,000\-candidate resource cap\. Mining reads neither the target labels nor validation rows\. The stored sparse matrix uses occurrence counts

Xn​j=cj​\(x\(n\)\),X\_\{nj\}=c\_\{j\}\(x^\{\(n\)\}\),not binary presence, so training and inference agree when a pattern repeats or overlaps itself\.

Algorithm 1Build and compile a count\-logit reward1:tokenized training text; training labels; validation text and labels; document\-frequency limits; feature orders

1:41\{:\}4
2:signed token weights, weighted phrase automaton, validation report, and one decision record per candidate

3:

𝒞←MineNgrams\(training text,1:4,frequency limits\)\\mathcal\{C\}\\leftarrow\\textsc\{MineNgrams\}\(\\text\{training text\},1\{:\}4,\\text\{frequency limits\}\)
4:

Xtrain,Xval←CountOccurrences​\(𝒞,training text,validation text\)X\_\{\\mathrm\{train\}\},X\_\{\\mathrm\{val\}\}\\leftarrow\\textsc\{CountOccurrences\}\(\\mathcal\{C\},\\text\{training text\},\\text\{validation text\}\)⊳\\trianglerightno labels used above

5:

𝒮←∅\\mathcal\{S\}\\leftarrow\\emptyset
6:for

n=1,…,4n=1,\\ldots,4do

7:forcandidate

c∈𝒞c\\in\\mathcal\{C\}of order

nndo

8:

dc←ResidualizedLogisticTest\(Xtrain\[:,c\],training labels,𝒮\)d\_\{c\}\\leftarrow\\textsc\{ResidualizedLogisticTest\}\(X\_\{\\mathrm\{train\}\}\[:,c\],\\text\{training labels\},\\mathcal\{S\}\)
9:apply within\-order false discovery rate \(FDR\) correction to all

dcd\_\{c\}
10:

𝒜n←ApplyGatesAndCaps​\(\{dc:\|c\|=n\},𝒮\)\\mathcal\{A\}\_\{n\}\\leftarrow\\textsc\{ApplyGatesAndCaps\}\(\\\{d\_\{c\}:\|c\|=n\\\},\\mathcal\{S\}\)⊳\\trianglerightstability, artifact, heredity, and child\-over\-parent gates

11:

𝒮←𝒮∪𝒜n\\mathcal\{S\}\\leftarrow\\mathcal\{S\}\\cup\\mathcal\{A\}\_\{n\}
12:

\(b,u,w\)←FitRegularizedLogistic\(Xtrain\[:,𝒮\],training labels\)\(b,u,w\)\\leftarrow\\textsc\{FitRegularizedLogistic\}\(X\_\{\\mathrm\{train\}\}\[:,\\mathcal\{S\}\],\\text\{training labels\}\)
13:report

←EvaluateOnly​\(b,u,w,Xval,validation labels\)\\leftarrow\\textsc\{EvaluateOnly\}\(b,u,w,X\_\{\\mathrm\{val\}\},\\text\{validation labels\}\)
14:automaton

←CompileAhoCorasick​\(𝒮,w\)\\leftarrow\\textsc\{CompileAhoCorasick\}\(\\mathcal\{S\},w\)
15:return

\(b,u,automaton,report,\{dc:c∈𝒞\}\)\(b,u,\\text\{automaton\},\\text\{report\},\\\{d\_\{c\}:c\\in\\mathcal\{C\}\\\}\)

##### Residualized short\-to\-long score test\.

At feature orderkk, letHkH\_\{k\}contain an intercept, five label\-free text diagnostics \(log length, unique\-token fraction, repeated\-bigram fraction, maximum\-run fraction, and punctuation fraction\), and the features accepted at orders belowkk\. A class\-weighted ridge logistic null fit gives probabilitiespp, residualr=ω⊙\(y−p\)r=\\omega\\odot\(y\-p\), andD=diag⁡\(ω⊙p⊙\(1−p\)\)D=\\operatorname\{diag\}\(\\omega\\odot p\\odot\(1\-p\)\)\. For candidate count columncjc\_\{j\}, the residualized score and information are

Uj\\displaystyle U\_\{j\}=cj⊤​r,\\displaystyle=c\_\{j\}^\{\\top\}r,\(34\)Ij\\displaystyle I\_\{j\}=cj⊤​D​cj−cj⊤​D​Hk​\(Hk⊤​D​Hk\+γ​P\)−1​Hk⊤​D​cj,\\displaystyle=c\_\{j\}^\{\\top\}Dc\_\{j\}\-c\_\{j\}^\{\\top\}DH\_\{k\}\(H\_\{k\}^\{\\top\}DH\_\{k\}\+\\gamma P\)^\{\-1\}H\_\{k\}^\{\\top\}Dc\_\{j\},\(35\)Zj\\displaystyle Z\_\{j\}=Uj/Ij,\\displaystyle=U\_\{j\}/\\sqrt\{I\_\{j\}\},\(36\)wherePPleaves the intercept unpenalized\. We convert\|Zj\|\|Z\_\{j\}\|to a two\-sided normalpp\-value;γ\\gammais the null\-fit ridge strength\. We apply Benjamini–Hochberg correction within each order\([Benjamini and Hochberg, 1995](https://arxiv.org/html/2609.35924#bib.bib1)\)\.

A candidate then passes five transparent gates: correctedq≤0\.05q\\leq 0\.05and\|Zj\|≥2\|Z\_\{j\}\|\\geq 2; absolute correlation at most0\.980\.98with every text diagnostic; at least one selected prefix or suffix parent for orders above one; at least a2%2\\%gain over the strongest same\-sign parent; and matching sign plus significance in at least four of five stratified70%70\\%training subsamples\. Survivors are ordered by correctedqq,\|Z\|\|Z\|, document frequency, and token tuple before per\-order and global resource caps are applied\. The accepted columns are appended toHkH\_\{k\}before testing orderk\+1k\+1; the readable reference defaults cap each order at 64 and the complete selection at 256\. Every candidate has a decision record containing its statistic and first rejection reason\. Training and inference both count every occurrence, including overlaps\. Validation data report the area under the receiver operating characteristic curve \(AUC\), balanced accuracy, and log loss but never enter the fit or these gates\.

We use these gates as a reproducible screening procedure\. The paper does not claim that the final, adaptively constructed dictionary has a finite\-sample 5% false\-discovery\-rate guarantee: such a claim would additionally require the calibration and dependence assumptions of the individual score tests and the sequential selection procedure\.

With binary training targetsyny\_\{n\}, token coefficientsuu, selected\-pattern coefficientsww, and count\-semantic feature valuescjc\_\{j\}, the fitted scorer uses binary cross\-entropy \(BCE\),

Rϕ​\(x\)=b\+∑iuxi\+∑jwj​cj​\(x\)R\_\{\\phi\}\(x\)=b\+\\sum\_\{i\}u\_\{x\_\{i\}\}\+\\sum\_\{j\}w\_\{j\}c\_\{j\}\(x\)and minimizes

ℒ⁡\(ϕ\)=\\displaystyle\\mathcal\{L\}\(\\phi\)=\{\}1N​∑n=1NBCE⁡\(yn,σ⁡\(Rϕ​\(x\(n\)\)\)\)\\displaystyle\\frac\{1\}\{N\}\\sum\_\{n=1\}^\{N\}\\operatorname\{BCE\}\\\!\\left\(y\_\{n\},\\sigma\(R\_\{\\phi\}\(x^\{\(n\)\}\)\)\\right\)\+αu​∥u∥22\+α1​∥w∥1\+α2​∥w∥22\.\\displaystyle\+\\alpha\_\{u\}\\lVert u\\rVert\_\{2\}^\{2\}\+\\alpha\_\{1\}\\lVert w\\rVert\_\{1\}\+\\alpha\_\{2\}\\lVert w\\rVert\_\{2\}^\{2\}\.\(37\)The sigmoid belongs to the supervised fit and to diagnostic probabilities\. The generation\-time factor uses the signed energyRϕR\_\{\\phi\}itself, as stated in Eq\. \([3](https://arxiv.org/html/2609.35924#S2.E3)\)\.

Eq\.[37](https://arxiv.org/html/2609.35924#A3.E37)is the logistic special case, not a universal training law\. RTP uses a backbone\- and cohort\-bound binary or soft\-toxicity asset\. Malinois uses a target\-highest binary objective with reverse\-complement tied sixmer features\. DeepSTARR and APARENT use their frozen asset\-specific regression objectives\. The exact feature grammar, labels, loss, regularization, and coefficients are task specific rather than inferred from the task name\. CommonGen trains no scorer: its terminal0/−∞0/\-\\inftyDFA is fixed by each record\. Offline scorer accuracy is diagnostic; only frozen generation followed by the independent task evaluator supports a result claim\.

### C\.3Task\-specific controller construction

The inference engine sees only the finite\-state interface, but the compiler and scored text scope are task specific\. Tab\.[5](https://arxiv.org/html/2609.35924#A3.T5)states the complete mapping\. The learned controllers are weighted deterministic automata, not hard accept/reject DFAs; CommonGen is the terminal hard\-DFA instance\.

Table 5:How each task becomes a controller\. Literal feature mining is shared in form but labels and fitted weights are task specific\. CommonGen, Dyck, and Sudoku have no learned count\-logit reward\. Protein bigrams are chronological action\-order features, not adjacent residues in the final sequence\.Algorithm 2Compile a task\-specific controller1:task

tt; task record; tokenizer; declared candidate support; selected patterns and fitted weights when

ttis learned

2:token energies plus a finite\-state controller

3:if

t∈\{RTP,DeepSTARR,APARENT,Malinois\}t\\in\\\{\\mathrm\{RTP\},\\mathrm\{DeepSTARR\},\\mathrm\{APARENT\},\\mathrm\{Malinois\}\\\}then

4:place every fitted unigram weight in the token\-energy table

5:insert every selected phrase and its signed weight into a token trie

6:add failure links and propagate terminal weights along those links

7:returntoken energies and the resulting weighted AC controller

8:if

t=CommonGent=\\mathrm\{CommonGen\}then

9:forconcept

ccin the recorddo

10:

Vc←StandaloneForms​\(c,base, plural, possessive\)V\_\{c\}\\leftarrow\\textsc\{StandaloneForms\}\(c,\\text\{base, plural, possessive\}\)
11:

Tc←TokenizeWithBoundaries​\(Vc,tokenizer\)T\_\{c\}\\leftarrow\\textsc\{TokenizeWithBoundaries\}\(V\_\{c\},\\text\{tokenizer\}\)
12:build a prefix matcher over

⋃cTc\\bigcup\_\{c\}T\_\{c\}
13:initial DFA state

←\\leftarrow\(empty active prefixes, zero concept mask, not rejected\)

14:breadth\-first enumerate transitions on the declared support; update active prefixes, completed\-concept bits, and the reject flag

15:terminal score

←0\\leftarrow 0iff all required bits are set and not rejected;

−∞\-\\inftyotherwise

16:returnzero token energies and the reachable hard DFA

17:returnUnsupportedTask\(t\)

For learned tasks, fixed context is consumed before the scored scope to obtain the carrier and automaton boundary state, and rewards are accumulated only on the declared continuation or biological output sequence\. For CommonGen, word boundary handling belongs to the tokenizer adapter\. The same accepted token strings define both generation and exact evaluation\. This prevents evaluator\-only morphology rules from silently differing from the DFA used during generation\.

## Appendix DExperimental Setup and Evaluation

Tab\.[6](https://arxiv.org/html/2609.35924#A4.T6)summarizes the evaluation contracts\.

Table 6:Task and evaluator contracts\. The scorer used for guidance is not the sole evaluator\.The split law is uniform: fitted components use TRAIN only, hyperparameters use DEV only, and a frozen configuration is evaluated once on its declared final panel\. CommonGen uses 993 DEV records and 1,497 disjoint TEST records\. Dyck uses 1,024 DEV inputs and 9,798 evaluation inputs\. Sudoku uses 64 development puzzles from PRISM training solutions and its released 2,000\-puzzle hard validation file\([Kim et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib6)\), as redistributed by MDM\-VGB\([Jeon et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib5)\); we do not call it an independently certified test split\.

The final panels are fixed benchmark cohorts\. Some were evaluated earlier in this study and are therefore not new prospective holdouts\. For each reported system, fitting uses TRAIN data and configuration selection uses DEV data; no final\-panel metric selects its configuration\. The stated source disjointness concerns these experimental records and does not certify that the pretrained backbone never encountered similar data\.

RTP is a shared stress benchmark rather than a population estimate: its 1,024 prompts are selected by toxicity of a frozen diffusion\-only continuation, and the identical ordered prompt IDs are then used for every method\. No guided method defines its own panel\. DNA experiments use 1,000 unconditional draws per displayed system\. These are independent frozen\-system samples with a common backbone, output contract, predictor, and sample count; they are not paired molecules and do not imply unseen biological generalization\.

### D\.1Metric computation

ForNNoutputs, hard satisfaction isN−1​∑n𝟏​\[V⁡\(x\(n\)\)\]N^\{\-1\}\\sum\_\{n\}\\mathbf\{1\}\[V\(x^\{\(n\)\}\)\]\. Sudoku validityVVrequires correct output format, clue preservation, and all row, column, and box rules\. Its separate clue score is the fraction of outputs preserving every given clue\. CommonGen validity requires every requested concept under the accepted\-form and word\-boundary rules\. Dyck validity checks bracket balance and type matching, while mean edit distance is the symbol\-level Hamming distance to the input averaged over all outputs, including invalid ones\. Minimum\-edit optimality is verified separately against the exact repair cost\.

RTP non\-toxicity isN−1∑n𝟏\[tn<0\.5\]N^\{\-1\}\\sum\_\{n\}\\mathbf\{1\}\[t\_\{n\}<0\.5\], wheretnt\_\{n\}is the generated continuation’sunitary/toxic\-bert@4d6c22e74ba2score\([Hanu and Unitary team, 2020](https://arxiv.org/html/2609.35924#bib.bib25)\)\. Prompt\-conditionedopenai\-community/gpt2\-large@32b71b12589ccorpus perplexity\([Radford et al\., 2019](https://arxiv.org/html/2609.35924#bib.bib26)\)isexp⁡\(∑nNLLn/∑nTn\)\\exp\(\\sum\_\{n\}\\mathrm\{NLL\}\_\{n\}/\\sum\_\{n\}T\_\{n\}\), where NLL denotes negative log\-likelihood andTnT\_\{n\}counts scored output tokens\. The prompt supplies context but contributes neither loss nor tokens to that denominator\. Corpus PPL aggregates token losses before exponentiation\.

For DNA, the declared task crop is scored by the official predictor\. DeepSTARR and APARENT report the mean target output over successfully scored sequences, with scoring failures recorded separately\. DeepSTARR Pass@95 is the fraction of all generated sequences reaching the fixed activity threshold\. Malinois target\-highest rate is the fraction whose target\-cell score strictly exceeds both other cell scores\. Native D3LM masked LOO masks one token at a time, records the original token’s negative log probability with all other tokens visible, averages those losses over all scored tokens, and exponentiates\. It is a pseudo\-perplexity, not a normalized joint likelihood or a target\-activity metric\.

Protein motif RMSD compares the declared motif atoms in the OmegaFold structure with the reference under the evaluator’s alignment\. Mean RMSD averages these per\-output distances\. Success@1Å isN−1∑n𝟏\[RMSDn≤1Å\]N^\{\-1\}\\sum\_\{n\}\\mathbf\{1\}\[\\mathrm\{RMSD\}\_\{n\}\\leq 1\\,\\text\{\\AA\}\]\. Satisfaction, isoform usage, target\-highest, and success rates are displayed as percentages in the main tables\.

The remaining setup details are organized in App\.[D\.2](https://arxiv.org/html/2609.35924#A4.SS2)\(inputs and prompts\), App\.[E](https://arxiv.org/html/2609.35924#A5)\(baseline adaptations\), and App\.[E\.1](https://arxiv.org/html/2609.35924#A5.SS1)\(generation and selection\)\.

### D\.2Exact generation prompt contracts

We freeze prompts as part of the experimental condition\. Diffusion\-only, carrier\-only, learned guidance, and other algorithmic baselines receive the*formal task input*below\. The prompt\-only baseline receives the same record, start canvas, and generation budget, but applies the corresponding*explicit\-control wrapper*\. Prompt\-only is therefore a named baseline, not a point in the guided\-temperature sweep\. Braces below denote fields filled from the frozen dataset record\. Free continuations begin after the displayed suffix\.

#### D\.2\.1RealToxicityPrompts \(RTP\)

For diffusion\-only and all algorithmic guidance methods, the model receives the dataset prefix verbatim:

The matched prompt\-only baseline uses the frozenrtp\_prompt\_only\_v2template:

> Continue the text naturally and coherently using non\-toxic language\. Output only new text and do not repeat the given prefix\. Text: \{prefix\}

Only the newly generated continuation is passed to the toxicity evaluator; conditional perplexity is computed with the original prefix as context\.

#### D\.2\.2CommonGen

Every method receives the same concept\-conditioned task prompt:

> Write one short sentence using all these words: \{concept1\}, …, \{conceptm\}\. Sentence:

This prompt states the benchmark input rather than an additional soft\-control instruction\. We therefore do not report a separate prompt\-only CommonGen baseline\. Exact control is defined by the record\-conditioned terminal DFA, and acceptance requires every requested concept in the generated sentence\.

#### D\.2\.3Structured and biological inputs

Dyck, Sudoku, and the biological tasks use structured records rather than an additional natural\-language control prompt\. Dyck methods receive the same 32\-token repair record with the first 12 tokens locked; Sudoku methods receive the same puzzle and clue mask\. DNA methods share the D3LM backbone, 48\-token output contract, target identity, and evaluator but draw independent unconditional samples\. Thus language and symbolic inputs are row\-matched, whereas the biological comparison is distributional rather than molecule\-paired\. For the 48\-token DNA contract, Tab\.[1](https://arxiv.org/html/2609.35924#S2.T1)includes ab=48b=48full\-budget anchor with independently frozen method\-specific DEV selections\. This uses the same masked host and records 48 total token commits per trajectory; the native schedule can still contain zero\- or multi\-token steps\. BoN and particle methods retain their additional trajectory costs\. The confirmation scope, retained fixed\-panel evaluations, and mode collapse are summarized in App\.[F](https://arxiv.org/html/2609.35924#A6)\. The main table displays the K562b=48b=48target\-specific result\. HepG2 and SK\-N\-SH are not part of the main endpoint comparison and are therefore omitted from that table; HepG2 appears only in the mechanism diagnostic in Fig\.[4](https://arxiv.org/html/2609.35924#S3.F4)A\. Language Full uses a 32\-token chunk atb=32b=32, and Dyck may finish its 20 editable positions within that allocation\. Sudoku Full usesb=64b=64and permits at most one new cell per update, with 10–53 realized calls on the panel in Tab\.[13](https://arxiv.org/html/2609.35924#A8.T13)\.

## Appendix EBaselines and Hyperparameter Selection

Algorithmic sources are CDD\([Cardei et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib3)\), CDM\([Kim et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib2)\), D\-CBG\([Schiff et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib9)\), DG/TAG\([Nisonoff et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib8)\), GILC\([Dou et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib4)\), and MDM\-VGB\([Jeon et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib5)\)\. Tab\.[7](https://arxiv.org/html/2609.35924#A5.T7)summarizes each port\.

Table 7:Executable baseline recipes\. “Port” means our implementation of the published algorithmic idea on the frozen host backbone; it does not claim author\-code parity\.For the new multi\-solution Sudoku adaptation, CDM particles operate inside exact feasible\-completion guidance\. Its denoising\-step budget counts host updates, while particle work remains a separate compute coordinate\. Full\-trajectory particle methods, including DNA and Protein CDM, instead incurP​bPbbackbone row\-forwards\.

For conditional language and symbolic tasks, methods receive identical ordered row IDs, checkpoint, prompt or structured record, output length, evaluator, and reverse\-step budget\. Biological systems use independent unconditional draws under a common backbone, output contract, predictor, and sample count; we do not describe them as paired\. Particle count, MC samples, search width, best\-of\-NN, and realized NFE remain separate compute coordinates rather than being hidden insidebb\. The allocated denoising budget, realized committed\-token count, and realized backbone NFE are distinct quantities\. A global 1:1 point denotes token\-complete masked denoising under the same host; no experiment here changes the host into a block\-diffusion model\.

To contextualize the denoising\-budget comparison, Tab\.[8](https://arxiv.org/html/2609.35924#A5.T8)estimates backbone arithmetic for Base andCoffeeon the same 1,497 LLaDA/CommonGen prompts in separate efficiency runs\.

Table 8:Estimated backbone TFLOPs per output in the LLaDA/CommonGen efficiency runs\. We useF≈2​P​SF\\approx 2PSper forward, nominalP=8×109P=8\\times 10^\{9\},bbobserved forwards, and mean padded lengthsS=54\.50S=54\.50\(Base\) and53\.2053\.20\(Coffee\)\. The length difference reflects batching\. They excludeCoffee’s dynamic programming and are neither profiled nor total FLOPs; other tasks require their own sequence lengths and model\-call counts\.### E\.1Shared protocol

#### E\.1\.1Frozen model and inference settings

Tab\.[9](https://arxiv.org/html/2609.35924#A5.T9)gives the language defaults before task\-specific selection\.

Table 9:Default COFFEE language configuration before benchmark\-specific DEV selection\. Temperatures andλ\\lambdaare independent controls\.This is a language default, not a universal recipe\. Dream, D3LM, Protein, and task\-specific controller settings follow the development\-time search and selection rules in Tabs\.[10](https://arxiv.org/html/2609.35924#A5.T10)and[11](https://arxiv.org/html/2609.35924#A5.T11)\. The carrier construction is described in App\.[C](https://arxiv.org/html/2609.35924#A3)\.

#### E\.1\.2Selection and statistical reporting

Selection is performed independently inside each denoising budget\. Language tasks first maximize the declared control metric subject to the same\-budget quality rule, then use the deterministic tie\-break in Tab\.[10](https://arxiv.org/html/2609.35924#A5.T10)\. Dyck and Sudoku select by exact validity before secondary edit or clue metrics\. Biological ports select on the declared DEV predictor while retaining native LOO as a separately reported trade\-off; no TEST quantity selects a configuration\.

For CommonGen and RTP, the common soft\-language quality rule compares prompt\-conditioned corpus PPL on DEV with the unguided Base for the same backbone, task, and budget:

PPLcandidateDEV≤1\.5​PPLBaseDEV\.\\mathrm\{PPL\}^\{\\mathrm\{DEV\}\}\_\{\\mathrm\{candidate\}\}\\leq 1\.5\\,\\mathrm\{PPL\}^\{\\mathrm\{DEV\}\}\_\{\\mathrm\{Base\}\}\.Among candidates satisfying this common cap, selection maximizes the task’s control metric\. If none satisfies it, the lowest\-PPL point on the DEV frontier is frozen without relaxing the cap\. Its final\-panel control and quality measurements are still reported for matched systems, but the point cannot support a claim that requires satisfying the cap\. PPL is a quality proxy and does not by itself rule out repetitive or degenerate outputs\.

Every displayed cell is one frozen system evaluated on its declared panel\. Success rates use all planned outputs as their denominator\. A continuous quantity that is undefined for a failed output is summarized only over evaluable outputs\. The main table reports claim\-facing metrics, while App\.[F](https://arxiv.org/html/2609.35924#A6)records only the failure or coverage qualifications needed to interpret those claims\. A dash denotes an unavailable or inapplicable measurement rather than zero\. Paired intervals are used only when systems share the same input rows and a paired resampling unit; independent DNA draws are not assigned paired intervals\. Small numerical differences on unpaired panels are treated as descriptive rather than as significance claims\.

Table 10:Selection contracts for the results discussed in the main paper\. No final\-panel metric is used to choose a configuration\.Table 11:Development\-time search axes for the methods shown in the main comparison\. Batch size is an execution choice rather than a selected scientific parameter\. Particle, candidate, and verifier work remain separate from the denoising\-step budget\.

## Appendix FMain\-Claim Support and Result Qualifications

Tab\.[1](https://arxiv.org/html/2609.35924#S2.T1)and Fig\.[3](https://arxiv.org/html/2609.35924#S3.F3)contain the claim\-facing numerical results\. The appendix records only the additional qualifications needed to interpret those results rather than repeating every numerical cell already visible in the table and budget curves\.

All endpoints in Tab\.[1](https://arxiv.org/html/2609.35924#S2.T1)are frozen final\-panel outcomes and remain numerically ranked on the displayed metrics\. Mode collapse and quality\-gate failures remain disclosed through the reported quality and diversity diagnostics rather than turning those TEST outcomes into report\-only results\.

A hollow marker in Fig\.[3](https://arxiv.org/html/2609.35924#S3.F3)denotes a point outside the standard comparison set\. The map below lists every such point\. Report\-only points are lower\-budget archival diagnostics excluded from standard ranking, while K562 points are separately qualified\. No oracle, reference, or quality\-cap\-failed point is plotted\.

Report\-only points\.CommonGen / Dream, CDD \(4\), D\-CBG \(4, 16\); RTP / Dream, CDD \(16\), D\-CBG \(4\), COFFEE \(4, 16\); DeepSTARR, D\-CBG \(4\), GILC\-DB \(4, 16\); CommonGen / LLaDA, CDD \(4\), D\-CBG \(4, 16\); RTP / LLaDA, CDD \(4, 16\), D\-CBG \(4\)\.

Separately qualified points\.K562, D\-CBG \(16\), GILC\-DB \(16\)\.

Tab\.[12](https://arxiv.org/html/2609.35924#A6.T12)summarizes the main claim boundaries\.

Table 12:Additional evidence and claim boundaries for the results interpreted in the main text\.
## Appendix GCanonical Algorithms and Failure Semantics

### G\.1The fixed\-step compiled update

The following pseudocode gives the fixed\-step inference and sampling procedure used in Sec\.[2\.4](https://arxiv.org/html/2609.35924#S2.SS4)\. Its factors are fixed before the backward pass; support and numerical implementation details are discussed in the surrounding appendix\.

Algorithm 3OneCoffee\-guided diffusion update1:current sequence

xtx\_\{t\}; frozen denoiser; carrier factors

K1:LK\_\{1:L\}; compiled objective

\(δC,1:L,ψC,1:L,ηC\)\(\\delta\_\{C,1:L\},\\psi\_\{C,1:L\},\\eta\_\{C\}\); host reverse transition

qhostq\_\{\\mathrm\{host\}\}
2:next diffusion state

xt−1x\_\{t\-1\}
3:Build the clamped unary evidence

et,1:Le\_\{t,1:L\}using Eq\.[2](https://arxiv.org/html/2609.35924#S2.E2)\.

4:Set

ML​\(h,a\)←ηC​\(a\)M\_\{L\}\(h,a\)\\leftarrow\\eta\_\{C\}\(a\)for every terminal product state

\(h,a\)\(h,a\)\.

5:for

i=L,L−1,…,1i=L,L\-1,\\ldots,1do

6:Compute

Mi−1M\_\{i\-1\}from

MiM\_\{i\}using Eq\.[15](https://arxiv.org/html/2609.35924#S2.E15)\.

7:if

M0​\(h0,ainit\)=0M\_\{0\}\(h\_\{0\},a\_\{\\mathrm\{init\}\}\)=0then

8:returnNoPositiveMass\(retained support\)

9:

\(h,a\)←\(h0,ainit\)\(h,a\)\\leftarrow\(h\_\{0\},a\_\{\\mathrm\{init\}\}\)
10:for

i=1,2,…,Li=1,2,\\ldots,Ldo

11:Sample

\(u,h′\)\(u,h^\{\\prime\}\)with probability proportional to

12:

et,i​\(u\)​Ki​\(h,u,h′\)​ψC,i​\(a,u\)e\_\{t,i\}\(u\)K\_\{i\}\(h,u,h^\{\\prime\}\)\\psi\_\{C,i\}\(a,u\)
13:

⋅Mi​\(h′,δC,i​\(a,u\)\)\\cdot M\_\{i\}\\\!\\left\(h^\{\\prime\},\\delta\_\{C,i\}\(a,u\)\\right\)\.

14:

x~0i←u\\widetilde\{x\}\_\{0\}^\{i\}\\leftarrow u;

\(h,a\)←\(h′,δC,i​\(a,u\)\)\(h,a\)\\leftarrow\(h^\{\\prime\},\\delta\_\{C,i\}\(a,u\)\)\.

15:Sample

xt−1∼qhost​\(xt−1∣xt,x~0\)x\_\{t\-1\}\\sim q\_\{\\mathrm\{host\}\}\(x\_\{t\-1\}\\mid x\_\{t\},\\widetilde\{x\}\_\{0\}\)
16:using the host model’s original proposal\-to\-state rule\.

17:return

xt−1x\_\{t\-1\}

Algorithm 4Strict minimum\-edit repair with frozen evidence1:reference

yy; locked positions

FF; per\-position candidates

C1:LC\_\{1:L\}; bounded\-language transition

δ\\delta; frozen evidence; target\-free carrier; random seed

2:one globally minimum\-edit valid repair or a fail\-closed record

3:initialize forward min\-plus cost

D0​\(a0\)=0D\_\{0\}\(a\_\{0\}\)=0and

D0​\(a\)=∞D\_\{0\}\(a\)=\\inftyotherwise

4:for

i=1,…,Li=1,\\ldots,Ldo

5:

Di\(a′\)←mina,v:δ⁡\(a,v\)=a′\[Di−1\(a\)\+𝟏\[v≠yi\]\]D\_\{i\}\(a^\{\\prime\}\)\\leftarrow\\min\_\{a,v:\\delta\(a,v\)=a^\{\\prime\}\}\[D\_\{i\-1\}\(a\)\+\\mathbf\{1\}\[v\\neq y\_\{i\}\]\], respecting

FFand

CiC\_\{i\}
6:run the symmetric backward min\-plus recursion to obtain suffix costs

7:

d⋆←d^\{\\star\}\\leftarrowminimum terminal forward cost

8:forevery layered edge

\(i,a,v,a′\)\(i,a,v,a^\{\\prime\}\)do

9:retain the edge iff prefix cost

\+\+edit cost

\+\+suffix cost equals

d⋆d^\{\\star\}
10:ifthe retained graph has no accepting terminal paththen

11:returnNoFeasibleRepair\(declared support\)

12:attach frozen evidence and carrier scores to every retained edge

13:run sum\-product backward messages on the retained graph

14:ifthe root message

M0​\(h0,a0\)=0M\_\{0\}\(h\_\{0\},a\_\{0\}\)=0then

15:returnNoPositiveMass\(retained support\)

16:

x←AncestralReplay​\(messages,seed\)x\\leftarrow\\textsc\{AncestralReplay\}\(\\text\{messages\},\\text\{seed\}\)
17:return

\(x,\{i:xi≠yi\},d⋆\)\(x,\\\{i:x\_\{i\}\\neq y\_\{i\}\\\},d^\{\\star\}\)

The min\-plus stage is score free: it determines the exact feasible edit support\. The later sum\-product stage changes only the relative probability of tied minimum\-edit repairs\. A resource limit returns a separate resource\-failure record rather than dropping states as an unreported beam or being mislabeled as mathematical infeasibility\.

##### Log\-domain implementation\.

The production backend stores𝗆i​\(s\)=log⁡Mi​\(s\)\\mathsf\{m\}\_\{i\}\(s\)=\\log M\_\{i\}\(s\)and replaces every sum in the backward recurrence by log\-sum\-exp\. At unit ancestral temperature, the replay logit for edgee:s→s′e:s\\to s^\{\\prime\}isgi​\(e\)\+𝗆i​\(s′\)g\_\{i\}\(e\)\+\\mathsf\{m\}\_\{i\}\(s^\{\\prime\}\); this is Eq\.[33](https://arxiv.org/html/2609.35924#A1.E33)in log space and does not introduce a second message namedBB\. Compatible rows are batched without changing the sampling law\.

##### Failure records\.

The implementation distinguishes an unsatisfiable hard objective on the declared support, zero positive carrier–objective mass on an otherwise feasible retained graph, a resource\-limit abort during graph construction, and a numerical failure\. Only the first two are mathematical support outcomes; resource and numerical failures are reported separately and never relabeled as infeasibility\.

## Appendix HGuidance Dynamics and Diagnostic Experiments

### H\.1Multi\-solution Sudoku joint consistency

The TRAIN\-derived 120\-puzzle diagnostic uses one source\-disjoint seed and fixed settings\. Joint replay, independent exact marginals, and the joint reference share the same 64\-bit floating\-point \(FP64\) conditional scores, decoder, and confidence rule; D\-CBG uses a different feasibility\-derived confidence source\. Joint replay, uniform joint sampling, and the reference all reach 120/120, while independent marginals fail at smaller budgets\. This supports the need for coherent joint sampling under parallel commits; because uniform joint sampling also succeeds, it does not establish a validity gain from learned carrier weighting\.

Table 13:Multi\-solution Sudoku: joint consistency under parallel commitments\. Entries count valid, clue\-preserving outputs out of 120 puzzles; 40 puzzles have 2, 3–8, and 9–32 solutions, respectively\. This is a TRAIN\-derived, source\-disjoint exploratory panel with one seed and fixed diagnostic settings, not the 2,000\-puzzle evaluation or a complete\-baseline comparison\. Full \(b=64b=64\) permits at most one new cell per step, with 10–53 actual calls\. The FP64 joint reference and independent\-marginal row use identical conditional scores, support, temperature, decoder, and confidence rule; proposals may lead to different subsequent commit positions\. Uniform joint still uses model\-based commit ordering\.
### H\.2Minimum\-edit repair development diagnostic

The diagnostic fixes a 12\-token valid source prefix, repairs a 20\-token suffix, and uses four bracket tokens with a bounded Dyck stack\. On 9,877 invalid development leaves, every returned sequence is valid and globally minimum\-edit within the declared support; mean edit distance is 8\.283 and masked\-suffix pseudo\-perplexity is 12\.27\. A matched MDM\-VGB port repairs 28\.41% of rows; its valid subset has mean edit distance 10\.57 and pseudo\-perplexity 10\.21\. These are shared\-LLaDA DEV diagnostics, not held\-out evidence or a reproduction of the original MDM\-VGB experiment\.

### H\.3Guidance dynamics and frozen\-query diagnostics

Panel A of Fig\.[4](https://arxiv.org/html/2609.35924#S3.F4)uses 64 shared HepG2 IDs under the same identity carrier, host schedule, and retained\-support rule\. Its ribbons count transitions of each rollout’s complete clean proposal between displayed updates; they are not probability flow\. The scorer\-on andWC≡1W\_\{C\}\\equiv 1arms therefore describe proposal trajectories under two frozen systems rather than an intervention that isolates cross\-position lookahead\.

Panels B–C use nine distinct frozen K562b=4b=4queries\. For a fixed conditioning statez=\(h,a,x0<i\)z=\(h,a,x\_\{0\}^\{<i\}\), the Full and Local action distributions share denoiser evidence, carrier factors, current objective weight, and retained support\. The Full conditional uses the target\-weighted continuation messageMiM\_\{i\}, whereas Local replaces only that message with the neutral continuation massBiB\_\{i\}\. Panel B selects one query at position 25 and one prefix product state, then varies the future objective horizondd: the objective factors at positionsi\+1,…,i\+di\+1,\\ldots,i\+dare included, while those afteri\+di\+dare set to one\. The entire 48\-token lattice, including suffix denoiser evidence, carrier factors, candidate support, and automaton state transitions, remains intact\. Thusd=0d=0reproduces Local andd=23d=23reproduces Full for the same fixed prefix\. The intermediate points are controlled recalculations, not diffusion\-time updates\. In this query, the probability ofAAAAAAis 0\.771 atd=0d=0or 1, 0\.643 atd=2d=2, and 0\.500 fromd=3d=3through 23\. Positions 27 and 28 are observedAAAAAAtokens in the frozen state; enabling their objective factors changes the current action odds by factorsexp⁡\(−0\.623\)\\exp\(\-0\.623\)andexp⁡\(−0\.588\)\\exp\(\-0\.588\), respectively\. Their product is 0\.298\.

For panel C, letμi0​\(z\)\\mu\_\{i\}^\{0\}\(z\)be the normalized occupancy under exact neutral\-prefix replay\. The position\-level statistic is

TV¯i=∑zμi0​\(z\)​12​∑u\|pFull​\(u∣z\)−pLocal​\(u∣z\)\|\.\\overline\{\\operatorname\{TV\}\}\_\{i\}=\\sum\_\{z\}\\mu\_\{i\}^\{0\}\(z\)\\frac\{1\}\{2\}\\sum\_\{u\}\\left\|p\_\{\\mathrm\{Full\}\}\(u\\mid z\)\-p\_\{\\mathrm\{Local\}\}\(u\\mid z\)\\right\|\.\(38\)Panel C plots the empirical CDF of this prefix\-conditional TV averaged over neutral\-prefix occupancy; it does not first mix the two action distributions and then compute TV\. The highlighted position is the largest variation among these nine queries and was selected only for illustration\. Its occupancy\-weighted TV is 0\.250, whereas panel B uses one selected prefix with conditional TV 0\.270\. The displayed 19/224 count is descriptive\. Here future refers to positions not yet sampled in the same clean reconstruction, rather than later diffusion steps; this diagnostic establishes no external K562 benefit\.

Qualitative examples are included only when the matched diffusion\-only output, strongest eligible baseline output, guided output, independent evaluator score, and internal scorer trace are all available for the same record\. Examples do not substitute for aggregate results and are not selected by TEST score alone\.

### H\.4CommonGen completion weighting and joint sampling

This diagnostic reuses 256 official validation records selected before the component outcomes by concept count and tokenized concept length\. Each arm uses the same records and three seeds with LLaDA\-8B\-Base, 32 generated tokens, denoising budgetb=8b=8, and the same prompt and retained\-support rule\. Evidence, carrier\-emission, and ancestral temperatures are\(0\.9,0\.3,1\.0\)\(0\.9,0\.3,1\.0\)\. The target\-free carrier is either the fitted 64\-state WikiText HMM \(H\) or a one\-state identity carrier \(I\)\. We recompile each record’s lexical DFA after generation and compute prompt\-conditioned GPT\-2\-large PPL over the generated continuations\. All 5,376 outputs are nonempty and included in both metrics\.

The comparisons keep the carrier and the lexical controller fixed within each carrier setting\. At a fixed query, letg0​\(v∣s\)g\_\{0\}\(v\\mid s\)denote the neutral action conditional andh⁡\(v,s\)h\(v,s\)the neutral mass of accepting completions after actionvv\. Full assigns weight proportional tog0​\(v∣s\)​h​\(v,s\)g\_\{0\}\(v\\mid s\)h\(v,s\)\. Feasible keeps the neutral weightg0​\(v∣s\)g\_\{0\}\(v\\mid s\)only whenh⁡\(v,s\)\>0h\(v,s\)\>0\. It therefore removes dead ends without using the relative mass of the remaining completions\. Neutral removes the terminal acceptance weight while retaining the same candidate graph\. Full\-marginal computes the exact single\-token marginals of Full on the retained support at each fixed query, then draws the concurrently committed tokens independently\. Once different tokens are committed, later denoiser queries and their supports may diverge\.

Table 14:CommonGen component diagnostic on 256 reused validation inputs and three seeds per arm\. PPL is the prompt\-conditioned GPT\-2\-large corpus PPL over generated continuations\. No output is excluded from scoring\.H–Full and H–Full\-marginal differ in lexical coverage by16\.0216\.02percentage points, with a 95% input\-cluster bootstrap interval of\[13\.15,18\.75\]\[13\.15,18\.75\]\. Both Full and Feasible attain 100% coverage under H and I\. Relative to Feasible, Full reduces corpus token NLL by0\.06910\.0691\[0\.0221,0\.1148\]\[0\.0221,0\.1148\]under H and0\.07640\.0764\[0\.0319,0\.1235\]\[0\.0319,0\.1235\]under I; brackets again give 95% input\-cluster intervals\. Each of 5,000 bootstrap draws resamples the 256 inputs while keeping their three seed outputs together\. The joint\-versus\-marginal result concerns lexical coverage, not a PPL gain\. These are development diagnostics on reused validation records, not fresh held\-out results\. Unit ancestral temperature makes the joint and marginal laws directly comparable but differs from the main\-table selected configurations\. Their fixed\-query exactness is conditional on retained candidate support, up to floating\-point error; PPL measures an external language\-model score rather than sentence quality\.

## Appendix IReproducibility and Evidence Provenance

Each displayed value binds one task, backbone, cohort, method, budget, metric, and frozen configuration; values are not pooled across these contracts\. Reproduction constructs the data roles in Tab\.[10](https://arxiv.org/html/2609.35924#A5.T10), trains or loads the TRAIN\-only component, runs the DEV grids in Tab\.[11](https://arxiv.org/html/2609.35924#A5.T11), applies the deterministic selection rule, and evaluates the frozen configuration once\. Algs\.[1](https://arxiv.org/html/2609.35924#alg1)–[4](https://arxiv.org/html/2609.35924#alg4)specify the computations\. Failed outputs remain in the denominator, and comparisons require shared task, split, prompt, evaluator, support, and budget contracts\.

## Appendix JRelated Work

##### Discrete diffusion and dependence modeling\.

D3PMs generalize discrete diffusion beyond uniform corruption and include an absorbing\-state construction that connects diffusion with masked generation\([Austin et al\., 2021](https://arxiv.org/html/2609.35924#bib.bib43)\)\. Discrete Copula Diffusion supplements denoiser predictions with a separately trained copula model to restore dependencies between output variables and reduce the number of denoising steps\([Liu et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib45)\)\. Chain\-structured conditional random fields give a standard graphical\-model treatment of conditional sequence dependence and dynamic\-programming inference\([Sutton and McCallum, 2012](https://arxiv.org/html/2609.35924#bib.bib44)\)\. These works motivate the use of structured dependence models inside discrete generation, whileCoffeeseparately represents the target\-free dependence carrier and the sequence objective used for guidance\.

##### Guidance for discrete diffusion\.

Existing methods steer discrete diffusion through intermediate predictors, continuous relaxations, or repeated evaluation of candidate outputs\. Predictor\-based methods estimate properties at noisy states and use those estimates to modify the reverse transitions\([Nisonoff et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib8);[Schiff et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib9)\), while NOS optimizes continuous denoiser representations\([Gruver et al\., 2023](https://arxiv.org/html/2609.35924#bib.bib7)\)\. SVDD evaluates the future value of candidate clean predictions\([Li et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib10)\), and CSMC constructs a Metropolis–Hastings chain over complete clean samples\([Phunyaphibarn and Sung, 2026](https://arxiv.org/html/2609.35924#bib.bib11)\)\. These approaches support broad classes of objectives, but require either a reliable signal at intermediate noise levels or repeated reward evaluation during sampling\. Training such predictors also requires task\-specific examples across the corruption process, where the attribute may be difficult to identify at high noise\.Coffeeinstead starts from a clean\-sequence objective and compiles it into finite\-state factors\. This avoids a separate neural attribute predictor at every noise level when the objective admits a compact compiled representation\.

##### Concurrent inference\-time steering\.

Several concurrent methods steer frozen diffusion models through learned twists, local prediction corrections, or scheduling policies\. CDM amortizes a twisted sequential Monte Carlo proposal with a learned twist\([Kim et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib2)\), while TRI\-TSMC iteratively fits the twist through trust\-region updates\([Wang et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib46)\)\. GILC modifies clean\-prediction logits using reward information\([Dou et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib4)\); DLM\-SWAI applies precomputed token\-level attribute biases\([An and Han, 2026](https://arxiv.org/html/2609.35924#bib.bib47)\); and SAD steers the denoiser away from unsafe regions\([Yusuf et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib48)\)\. DPRM instead uses a Doob\-transform process reward to change token ordering\([Bu et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib49)\), while MDM\-VGB adds verifier\-guided remasking and backtracking\([Jeon et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib5)\)\. These approaches support broad objectives through learned twists, local corrections, ordering, or search\.Coffeetargets objectives that admit compact finite\-state factors and computes their continuation weights on the retained product graph\.

##### Search for biological sequence design\.

Tree\-guided diffusion has also been used for biological design\. MP2D combines conditional diffusion, constrained Monte Carlo tree search, and iterative refinement for multi\-objective protein design\([Kong et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib50)\)\. DNA\-CRAFT combines class\-conditioned diffusion with Monte Carlo tree guidance for cell\-type\-specific regulatory DNA design\([Awasthi et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib51)\)\. These methods explicitly search multiple denoising trajectories under external objectives, whereasCoffeeperforms exact backward inference for the compiled objective within each retained fixed\-step graph\.

##### Future\-aware control through tractable completion models\.

Autoregressive control has likewise used predictions or tractable models of future continuations\. FUDGE trains a discriminator to predict whether a prefix will eventually satisfy an attribute\([Yang and Klein, 2021](https://arxiv.org/html/2609.35924#bib.bib13)\)\. GeLaTo distills a hidden Markov model for tractable conditioning on lexical constraints\([Zhang et al\., 2023](https://arxiv.org/html/2609.35924#bib.bib14)\), while Ctrl\-G pairs such a model with a finite\-state logical constraint\([Zhang et al\., 2024](https://arxiv.org/html/2609.35924#bib.bib15)\)\. TRACE combines a distilled hidden Markov model with a lightweight attribute model to aggregate future attribute probabilities without sampling the continuations individually\([Weng et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib16)\)\.Coffeeextends this completion\-based view to a diffusion step in which unresolved variables may occur anywhere in the sequence and must be treated as one joint clean reconstruction\. It also compiles count\-additive soft preferences into weighted state transitions, so the same backward\-message algorithm supports both hard acceptance and soft reward\.

##### Compiled representations for structured inference\.

Knowledge compilation studies representations that make otherwise expensive queries tractable\([Darwiche and Marquis, 2002](https://arxiv.org/html/2609.35924#bib.bib19)\)\. A probabilistic circuit is a directed computation graph that represents a distribution through sums and products\. Under appropriate structural compatibility conditions, circuit operations such as products and marginalization remain tractable\([Vergari et al\., 2021](https://arxiv.org/html/2609.35924#bib.bib20)\)\. Semantic Probabilistic Layers use this structure to combine neural predictions with logical constraints\([Ahmed et al\., 2022](https://arxiv.org/html/2609.35924#bib.bib21)\), and Neurosymbolic Diffusion Models use discrete diffusion to capture dependencies among symbols inside a neuro\-symbolic predictor\([van Krieken et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib37)\)\. CoDD introduces a tractable probabilistic layer that restores cross\-position dependence to factorized diffusion\-language predictions\([Li et al\., 2026](https://arxiv.org/html/2609.35924#bib.bib12)\)\. For sequence objectives, weighted automata provide a finite\-state algebra\([Mohri, 2009](https://arxiv.org/html/2609.35924#bib.bib22)\), while Aho–Corasick automata retain the suffix information needed to count overlapping pattern occurrences\([Aho and Corasick, 1975](https://arxiv.org/html/2609.35924#bib.bib23)\)\. Recent constrained diffusion methods use dynamic programming or finite automata to enforce hard regular constraints\([Suresh et al\., 2025](https://arxiv.org/html/2609.35924#bib.bib17);[Dang and Ermon, 2026](https://arxiv.org/html/2609.35924#bib.bib18)\)\.Coffeecomposes a target\-free dependence carrier with a separately compiled objective and derives one product\-state message\-passing and sampling algorithm for hard and soft sequence guidance\.