Decoupling Task-Solving and Output Formatting in LLM Generation

# Decoupling Task-Solving and Output Formatting in LLM Generation
Source: [https://arxiv.org/html/2510.03595](https://arxiv.org/html/2510.03595)
Haikang Deng, Po\-Nien Kung, Nanyun Peng University of California, Los Angeles \{haikang, ponienkung, violetpeng\}@cs\.ucla\.edu

###### Abstract

Large language models \(LLMs\) are increasingly adept at solving complex problems, such as mathematical reasoning and automatic evaluation\. However, performance often degrades when prompts intertwine task instructions with rigid formatting requirements\. This entanglement creates competing goals for the model, hindering its reasoning capabilities\. To address this, we introduceDeco\-G, a decoding framework that explicitly decouples format adherence from problem solving\.Deco\-Gdelegates format adherence to a separate Format Estimation Module \(FEM\), which performs probabilistic lookahead to estimate future format compliance rate and reweighs token probabilities, allowing the LLM to focus solely on task resolution\. To make this approach both practical and efficient, we introduce three key innovations: instruction\-aware distillation, a flexible trie\-building algorithm, and HMM state pruning\. Experiments across mathematical reasoning, event argument extraction, and LLM\-as\-a\-judge demonstrate thatDeco\-Gconstantly gains over prompting or structured generation baselines, with guaranteed format compliance\. We release our code at[haikangdeng/deco\-g](https://github.com/haikangdeng/deco-g)\.

Decoupling Task\-Solving and Output Formatting in LLM Generation

Haikang Deng, Po\-Nien Kung, Nanyun PengUniversity of California, Los Angeles\{haikang, ponienkung, violetpeng\}@cs\.ucla\.edu

## 1Introduction

![Refer to caption](https://arxiv.org/html/2510.03595v2/x1.png)Figure 1:GSM8k examples\. Unconstrained prompting yields correct answers but fails formatting, while adding constraints degrades reasoning accuracy\.Deco\-Gdecouples formatting via a Format Estimation Module \(FEM\), achieving both strict compliance and correct answer\.Instruction fine\-tuning\(Wei et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib34); Chung et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib4)\)empowers LLMs to solve complex tasks, often enhanced by reasoning strategies like Chain\-of\-Thought\(Wei et al\.,[2022](https://arxiv.org/html/2510.03595#bib.bib35)\)and Tree\-of\-Thought\(Yao et al\.,[2023](https://arxiv.org/html/2510.03595#bib.bib41)\)\. However, emerging evidence suggests that combining problem\-solving instructions with strict output\-format requirements in a single prompt negatively impacts performance\(Tam et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib33); Long et al\.,[2025](https://arxiv.org/html/2510.03595#bib.bib24); He et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib13)\)\. For instance,Long et al\. \([2025](https://arxiv.org/html/2510.03595#bib.bib24)\)demonstrate that output structure significantly affects accuracy on benchmarks like MMLU\(Hendrycks et al\.,[2020](https://arxiv.org/html/2510.03595#bib.bib14)\), whileTam et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib33)\)observe that stricter constraints correlate with greater reasoning degradation\. This suggests that the current paradigm of intertwining task and format instructions \(as shown in[Figure˜1](https://arxiv.org/html/2510.03595#S1.F1)\) may hurt LLMs’ reasoning capabilities\.

To mitigate this, recent works have explored relaxing format strictness\(Tam et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib33)\)or adopting more intuitive schema\(Long et al\.,[2025](https://arxiv.org/html/2510.03595#bib.bib24); He et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib13)\)\. Yet, these adjustments still impose constraints that distract LLMs from reasoning\. Alternatively, constrained decoding frameworks\(Beurer\-Kellner et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib3); guidance\-ai,[2024](https://arxiv.org/html/2510.03595#bib.bib12); Willard and Louf,[2023](https://arxiv.org/html/2510.03595#bib.bib37)\)ensure compliance by strictly enforcing token transitions\. However, this rigid intervention does not consider the model’s internal reasoning flow, resulting in abrupt cut\-offs or incoherent outputs\. This trade\-off highlights the critical need for a framework that seamlessly decouples format constraints from task solving to unlock the full potential of LLMs\.

In this paper, we introduceDeco\-G, a framework that explicitly decouples format adherence from task reasoning, allowing LLMs to focus solely on problem\-solving while introducing an auxiliary module to guarantee format adherence\. Specifically, it leverages the modularity of existing controllable text generation methods \(e\.g\. GeLaTo\(Zhang et al\.,[2023](https://arxiv.org/html/2510.03595#bib.bib44)\), Ctrl\-G\(Zhang et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib45)\)\) and delegates format adherence to a dedicated Format Estimation Module \(FEM\) that continuously estimates the final format compliance and reweighs each next\-token distribution to guide generation\.

While this work builds upon GeLaTo\(Zhang et al\.,[2023](https://arxiv.org/html/2510.03595#bib.bib44)\)and Ctrl\-G\(Zhang et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib45)\), it is, to our knowledge, the first framework that introduces explicit separation of task solving and format adherence to preserve LLMs’ full potential\. Moreover, naively applying existing methods leads to degraded performance, due to their limited compatibility with instruction\-tuned LLMs and computational bottlenecks when handling complex templates\. To this end, we introduce three innovations: \(1\) instruction\-aware distillation to capture task\-oriented behaviors; \(2\) a flexible trie algorithm for efficient automata construction; and \(3\) HMM state pruning to accelerate inference\.

To assessDeco\-G’s effectiveness across diverse constraint types, we evaluate it on three distinct tasks: mathematical reasoning, event argument extraction, and LLM\-as\-a\-judge\. Experiments demonstrate thatDeco\-Gconsistently improves overall task performance, driven by: \(1\) guaranteeing 100% format compliance; \(2\) enabling more natural, context\-aware format integration; and \(3\) freeing the LLM to concentrate on reasoning without the cognitive burden of formatting\.

Our contributions are as follows:

- •We propose a novel decoding framework that uses a Format Estimation Module to explicitly decouple format adherence from task solving, preserving the LLM’s reasoning capabilities while enforcing strict constraints\.
- •We introduce three technical innovations—instruction\-aware distillation, flexible trie construction, and HMM state pruning—that induce minimal computational overhead and render theDeco\-Gframework practical for real\-world deployment\.
- •We demonstrate consistent performance gains across diverse benchmarks, supported by a detailed analysis of the steering mechanism and entropy\-based control dynamics\.

## 2Preliminaries

This section reviews prior work on controllable generation that our approach builds upon, and highlights how these methods, while instrumental, struggle to achieve our goal of efficient task–format disentanglement\. Our formulation and technical contributions are introduced in the next section\.

### 2\.1Generation with Attribute Control

We follow prior work to formulate controllable text generation given a desired attributeα\\alphaas

P​\(x1:n\|α\)=∏tP​\(xt\|x<t,α\),P\(x\_\{1:n\}\|\\alpha\)=\\prod\_\{t\}\{P\(x\_\{t\}\|x\_\{<t\},\\alpha\)\},where the objective is to optimize the probability of sequences that exhibits the attributeα\\alpha\(e\.g\., contain certain keywords, sentiment, etc\.\)\. At each generation steptt, the target distribution for producing text with the desired attribute isP​\(xt\|x<t,α\)P\(x\_\{t\}\|x\_\{<t\},\\alpha\)\. Using Bayes’ rule, we can rewrite this as:

P​\(xt\|x<t,α\)=PLM​\(xt\|x<t\)​PLM​\(α\|xt,x<t\)PLM​\(α\|x<t\)P\(x\_\{t\}\|x\_\{<t\},\\alpha\)=P\_\{\\mathrm\{LM\}\}\(x\_\{t\}\|x\_\{<t\}\)\\frac\{P\_\{\\mathrm\{LM\}\}\(\\alpha\|x\_\{t\},x\_\{<t\}\)\}\{P\_\{\\mathrm\{LM\}\}\(\\alpha\|x\_\{<t\}\)\}\(1\)The first termPLM​\(xt\|x<t\)P\_\{\\mathrm\{LM\}\}\(x\_\{t\}\|x\_\{<t\}\)is the language model’s next\-token probability\. The second termPLM​\(α\|xt,x<t\)PLM​\(α\|x<t\)\\frac\{P\_\{\\mathrm\{LM\}\}\(\\alpha\|x\_\{t\},x\_\{<t\}\)\}\{P\_\{\\mathrm\{LM\}\}\(\\alpha\|x\_\{<t\}\)\}acts as a control signal\. It quantifies how the choice of the current tokenxtx\_\{t\}influences the probability that the complete sequence will satisfy attributeα\\alpha\. However, directly calculating this ratio is intractable, as it requires marginalizing over all possible future sequences\. A key challenge in controllable generation is to find a tractable approximation for this term\.

### 2\.2Estimating Attribute Likelihood

Recent controllable generation frameworks such as GeLaTo\(Zhang et al\.,[2023](https://arxiv.org/html/2510.03595#bib.bib44)\)and Ctrl\-G\(Zhang et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib45)\)leverage a tractable probabilistic model \(TPM\) to efficiently estimate the marginal probabilityP​\(α\|xt,x<t\)P\(\\alpha\|x\_\{t\},x\_\{<t\}\), serving as a signal to steer an LLM’s generation, following

P​\(xt\|x<t,α\)∝PLM​\(xt\|x<t\)​PTPM​\(α\|xt,x<t\)P\(x\_\{t\}\|x\_\{<t\},\\alpha\)\\propto P\_\{\\mathrm\{LM\}\}\(x\_\{t\}\|x\_\{<t\}\)P\_\{\\mathrm\{TPM\}\}\(\\alpha\|x\_\{t\},x\_\{<t\}\)\(2\)These approaches first distill a Hidden Markov Model \(HMM\) as a probabilistic approximation of the LLM and then encode logical constraints to formal structure\.

#### Sequence Modeling\.

HMM is the specific type of TPM used in these frameworks, chosen for its ability to model sequential data tractably\. The joint probability distribution over a sequence of observed variables \(tokens,x1:nx\_\{1:n\}\) and a corresponding sequence of hidden state variablesz1:nz\_\{1:n\}, is modeled as

PHMM​\(x≤t,z≤t\)=P​\(z1\)​P​\(x1\|z1\)​∏t=2TP​\(zt\|zt−1\)​P​\(xt\|zt\)\\begin\{split\}&P\_\{\\mathrm\{HMM\}\}\(x\_\{\\leq t\},z\_\{\\leq t\}\)=\\\\ &\\quad P\(z\_\{1\}\)P\(x\_\{1\}\|z\_\{1\}\)\\prod\_\{t=2\}^\{T\}P\(z\_\{t\}\|z\_\{t\-1\}\)P\(x\_\{t\}\|z\_\{t\}\)\\end\{split\}HMM’s Markov property enables efficient probabilistic inference over future sequences, a task that is intractable for language models\. In GeLaTo and Ctrl\-G, the HMM is distilled from the LLM using samples drawn unconditionally from the LLM\.

#### Formalizing Constraints\.

To enforce a constraint using the HMM, the constraints must be expressed in a formal language\.Zhang et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib45)\)propose representing logical constraints as Deterministic Finite Automata \(DFA\)\. A DFA is an abstract state machine that recognizes patterns in sequences\. Formally, a DFA is a 5\-tuple𝒟=\(Q,Σ,δ,q0,F\)\\mathcal\{D\}=\(Q,\\Sigma,\\delta,q\_\{0\},F\), whereQQis a finite set of states,Σ\\Sigmais the alphabet \(the LLM’s token vocabulary\),δ:Q×Σ→Q\\delta:Q\\times\\Sigma\\to Qis the transition function,q0∈Qq\_\{0\}\\in Qis the initial state, andF⊆QF\\subseteq Qis the set of accept states\. A sequence is “accepted” if it drives the machine from its initial state to an accept state\. This formalism is capable of representing logical constraints including the presence of keyphrases and word counts\.

#### Probabilistic reasoning over logical constraints\.

The core idea of these prior frameworks is to use the TPM to perform aprobabilistic lookahead— i\.e\., to efficiently computePTPM​\(α\|xt,x<t\)P\_\{\\mathrm\{TPM\}\}\(\\alpha\|x\_\{t\},x\_\{<t\}\), the probability that the full generated sequence will satisfy the constraintα\\alpha\. This is accomplished by marginalizing the joint HMM\-DFA state space over all possible future sequences that reach an accepting state in the DFA\. According toZhang et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib45)\), this marginalization can be calculated efficiently using a backward recurrence relation\. Refer to[Appendix˜A](https://arxiv.org/html/2510.03595#A1)for detailed derivation\.

### 2\.3From Prior Work toDeco\-G

While GeLaTo\(Zhang et al\.,[2023](https://arxiv.org/html/2510.03595#bib.bib44)\)and Ctrl\-G\(Zhang et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib45)\)demonstrate the effectiveness of generic TPMs for logical constraints \(e\.g\., keyphrases\), they face significant limitations when adapted for task\-format decoupling in instruction\-tuned LLMs:

- •Domain Shift:Prior methods distill HMMs from unconditional random generations\. This fails to capture theinstruction\-conditionaldistribution required for tasks\.
- •Template Complexity:Real\-world formats often interweave fixed text with variable\-length fields\. Representing these structures via standard DFA construction leads to state\-space explosion, creating a computational bottleneck\.
- •Inference Latency:The computational cost of probabilistic lookahead scales poorly with the massive vocabulary size\. Without optimization, this brings significant latency for real\-time generation\.

## 3Deco\-G

![Refer to caption](https://arxiv.org/html/2510.03595v2/x2.png)Figure 2:Deco\-Gdecouples task and format by prompting LLM with task\-only information and sending format constraints to FEM\.Deco\-Gdecodes from the posterior constructed by reweighing LLM token probabilities with the FEM estimated satisfaction rate\.In this section, we presentDeco\-G, a framework that realizes the decoupling of task reasoning from output formatting\. As shown in[Figure˜2](https://arxiv.org/html/2510.03595#S3.F2), our method separates the input prompt: the LLM receives only the task\-specific information, while a dedicated Format Estimation Module \(FEM\) receives the format constraints\. At each decoding step, the FEM estimates the likelihood of future compliance with the given format constraintsα\\alpha\. This likelihood is then used to reweigh the LLM’s original token probabilities, steering the generation towards a format\-compliant output\. Below, we describe the key components that enable this framework\.

### 3\.1Instruction\-Aware HMM Distillation

An HMM can approximate a large language model’s \(LLM\) output distribution to guide controllable generation\. The fidelity of this approximation is critical—ideally, an HMM that perfectly replicates the LLM’s probabilities would yield an exact posterior for format\-decoupled generation, per Equation \([1](https://arxiv.org/html/2510.03595#S2.E1)\)\. Our key insight is that for instruction\-tuned LLMs, the output distribution is fundamentally different when conditioned on a prompt versus when generating text unconditionally\. Prior methods\(Zhang et al\.,[2023](https://arxiv.org/html/2510.03595#bib.bib44),[2024](https://arxiv.org/html/2510.03595#bib.bib45)\), however, distill their HMMs using text sampled unconditionally from a model, an approach that fails to capture the task\-oriented behavior that emerges after instruction fine\-tuning\. This design renders methods like Ctrl\-G ineffective, leading to the suboptimal control patterns we demonstrate in[Appendix˜B](https://arxiv.org/html/2510.03595#A2)\.

To bridge this gap, we carry out instruction\-aware distillation: conditioning an HMM on task\-oriented behavior by training it exclusively on the LLM’s instruction\-response pairs\. Specifically, we distill knowledge from overone millioncompletions generated by an LLM prompted withone thousandunique instructions from the Natural\-Instructions\-v2\(Mishra et al\.,[2022](https://arxiv.org/html/2510.03595#bib.bib26)\)dataset\. FollowingZhang et al\. \([2023](https://arxiv.org/html/2510.03595#bib.bib44)\), we train the HMM using the Baum\-Welch algorithm\(Baum,[1972](https://arxiv.org/html/2510.03595#bib.bib2)\)\. This process yields a robust HMM that models the LLM’s conditional, instruction\-following behavior, enabling more precise control over generation across a wide spectrum of tasks\.

### 3\.2Flexible Trie Building for Complex Constraints

To efficiently enforce complex formatting requirements, we formalize the constraint space as aTemplate Languageℒ𝒯\\mathcal\{L\}\_\{\\mathcal\{T\}\}\. Unlike standard trie constructions which branch on individual characters, our flexible trie algorithm constructs a Deterministic Finite Automaton \(DFA\) by branching onsegments, comprised of fixed Pivots and variable Wildcards\.

#### Template Segments\.

Let𝒱\\mathcal\{V\}be the vocabulary of the LLM\. A templateT∈𝒯T\\in\\mathcal\{T\}is defined as an ordered sequence of segmentsS=\(s1,s2,…,sn\)S=\(s\_\{1\},s\_\{2\},\\dots,s\_\{n\}\), where each segmentsis\_\{i\}is either:

- •Pivot \(PP\):A deterministic sequence of tokensx1:m∈𝒱mx\_\{1:m\}\\in\\mathcal\{V\}^\{m\}representing static text \(e\.g\., formatting cues like “The answer is:”\)\. The language accepted by a pivot is the singleton set: L​\(P\)=\{x1:m\}L\(P\)=\\\{x\_\{1:m\}\\\}
- •Wildcard \(WW\):A variable slot constrained only by length\[ℓm​i​n,ℓm​a​x\]\[\\ell\_\{min\},\\ell\_\{max\}\]\. It accepts any token sequencexxwhere the length satisfies the bounds\. Its language is the union of all vocabulary permutations within the length range: L​\(W\)=⋃k=ℓm​i​nℓm​a​x𝒱kL\(W\)=\\bigcup\_\{k=\\ell\_\{min\}\}^\{\\ell\_\{max\}\}\\mathcal\{V\}^\{k\}

The language recognized by a full templateTTis the concatenation of its segment languages:L​\(T\)=L​\(s1\)⋅L​\(s2\)​⋯​L​\(sn\)L\(T\)=L\(s\_\{1\}\)\\cdot L\(s\_\{2\}\)\\cdots L\(s\_\{n\}\)\.

#### Trie Algorithm\.

We construct a minimal DFA𝒜=\(Q,Σ,δ,qi​n​i​t,F\)\\mathcal\{A\}=\(Q,\\Sigma,\\delta,q\_\{init\},F\)that recognizes the union of all allowed templates\. The core innovation is our State Convergence strategy, which prevents state\-space explosion for multi\-part templates\. Letqi​n​i​t\(i\)q\_\{init\}^\{\(i\)\}be the unique entry state for segmentsis\_\{i\}\. We construct the transition function such that for any valid string realizationwwof the current segmentsis\_\{i\}, the automaton transitions to the unique entry state of the next segmentsi\+1s\_\{i\+1\}:

∀w∈L​\(si\),δ∗​\(qi​n​i​t\(i\),w\)=qi​n​i​t\(i\+1\)\\forall w\\in L\(s\_\{i\}\),\\quad\\delta^\{\*\}\(q\_\{init\}^\{\(i\)\},w\)=q\_\{init\}^\{\(i\+1\)\}\(3\)whereδ∗:Q×𝒱∗→Q\\delta^\{\*\}:Q\\times\\mathcal\{V\}^\{\*\}\\to Qis the extended transition function processing a string of tokens\. Equation[3](https://arxiv.org/html/2510.03595#S3.E3)mathematically guarantees that the state configuration for segmentsi\+1s\_\{i\+1\}is strictly independent of the path taken throughsis\_\{i\}\.

#### Complexity\.

Standard DFA construction treats every valid length permutation of a wildcard as a distinct path\. For a template withNNsequential wildcards of length varianceKK, this dependency chains forward, resulting in exponential complexityO​\(KN\)O\(K^\{N\}\)\. Consider the event argument extraction template alternating between fixed pivotsPPand variable wildcardsWW:

T=P1​\(“Role A:”\)⋅W1⋅P2​\(“Role B:”\)⋅W2​…T=P\_\{1\}\(\\text\{\`\`\{Role A:\}''\}\)\\cdot W\_\{1\}\\cdot P\_\{2\}\(\\text\{\`\`\{Role B:\}''\}\)\\cdot W\_\{2\}\\dotsIn standard construction, the state history ofW2W\_\{2\}depends on the specific length chosen forW1W\_\{1\}\. In contrast, our algorithm enforces the convergence property \(Equation[3](https://arxiv.org/html/2510.03595#S3.E3)\): all valid paths forW1W\_\{1\}merge back to the single canonical nodeqi​n​i​t\(P2\)q\_\{init\}^\{\(P\_\{2\}\)\}\. This decouples the wildcard histories, ensuring the total state space grows linearly asO​\(N×K\)O\(N\\times K\)\.

### 3\.3Estimating Format Compliance

With a distilled HMM that simulates LLM distribution and a DFA that encodes format constraintsα\\alpha, we calculate the marginal probability over all sequences accepted by𝒟​\(α\)\\mathcal\{D\(\\alpha\)\}as

PFEM​\(α\|xt,x<t\)=P​\(𝒟​\(α\)=1,xt,x<t\)P​\(xt,x<t\)P\_\{\\mathrm\{FEM\}\}\(\\alpha\|x\_\{t\},x\_\{<t\}\)=\\frac\{P\(\\mathcal\{D\}\(\\alpha\)=1,x\_\{t\},x\_\{<t\}\)\}\{P\(x\_\{t\},x\_\{<t\}\)\}While the joint probability of format compliance and context sequenceP​\(𝒟​\(α\)=1,xt,x<t\)P\(\\mathcal\{D\}\(\\alpha\)=1,x\_\{t\},x\_\{<t\}\)is not readily available in the FEM, we followZhang et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib45)\)’s marginalization of HMM over DFA \([Appendix˜A](https://arxiv.org/html/2510.03595#A1)\) to calculate this value\. Finally, we use the FEM estimated compliance rate as likelihood to construct theDeco\-Gposterior:

P​\(xt\|x<t,α\)∝PLM​\(xt\|x<t\)​\[PFEM​\(α\|x<t,xt\)\]γP\(x\_\{t\}\|x\_\{<t\},\\alpha\)\\propto P\_\{\\mathrm\{LM\}\}\(x\_\{t\}\|x\_\{<t\}\)\[P\_\{\\mathrm\{FEM\}\}\(\\alpha\|x\_\{<t\},x\_\{t\}\)\]^\{\\gamma\}The resulting scores are re\-normalized over the vocabulary𝒱\\mathcal\{V\}\(via softmax\) to ensure a valid probability distribution\.γ\\gammais a hyperparameter that controls the steering strength with a default value of11\.

### 3\.4HMM Hidden State Pruning

The Format Estimation Module \(FEM\) provides effective guidance but introduces a computational bottleneck during inference\. The primary cost lies in the HMM’s emission stage, which calculates the probability distribution over the entire vocabulary𝒱\\mathcal\{V\}fromhhhidden states\. Withh=4096h=4096and\|𝒱\|\>100​k\|\\mathcal\{V\}\|\>100kforLlamaandQwen, this matrix\-vector multiplication \(O​\(h​\|𝒱\|\)O\(h\|\\mathcal\{V\}\|\)\) significantly impedes latency\.

To mitigate this, we introduceHMM hidden state pruning\. This technique exploits the observation that the probability mass of the hidden state distribution is highly concentrated within a small subset of states \(see[Figure˜3](https://arxiv.org/html/2510.03595#S5.F3)\)\. Instead of using the full state space, we approximate the emission probabilities by considering only thetop−k\\operatorname\{top\-k\}most probable states\. Empirically, selecting just the top5%5\\%\(k=200k=200\) is sufficient to retain over98%98\\%of the full model’s performance\. This strategy drastically improves efficiency by reducing the emission complexity fromO​\(h​\|𝒱\|\)O\(h\|\\mathcal\{V\}\|\)toO​\(k​\|𝒱\|\+h​log⁡h\)O\(k\|\\mathcal\{V\}\|\+h\\log h\), where theO​\(h​log⁡h\)O\(h\\log h\)term accounts for selecting the top states\. Withk≪hk\\ll h, this optimization achieves a∼13×\\sim 13\\timesreduction in FLOPs per decoding step, ensuring that the guidance overhead remains negligible while maintaining robust format compliance\.

## 4Experiment

#### Experimental Setup\.

We assessDeco\-G’s overall performance over three tasks: \(1\) math problem solving with reasoning, \(2\) event argument extraction as a generative task, and \(3\) LLM\-as\-a\-judge for summary evaluation \(see[Section˜4\.3](https://arxiv.org/html/2510.03595#S4.SS3)\)\. We applyDeco\-Gon performant instruction modelsLlama\-3\.1\-8B\-Instruct\(Grattafiori et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib11)\),Qwen2\.5\-7B\-Instruct\(Yang et al\.,[2025b](https://arxiv.org/html/2510.03595#bib.bib40)\), andQwen3\-8B\(Yang et al\.,[2025a](https://arxiv.org/html/2510.03595#bib.bib38)\)to verify its effectiveness\. The baselines we include for comparison are as follows:

- •Prompt\-Only \(NL/JSON\):Standard greedy decoding conditioned on task instructions and output constraints \(natural language or JSON\), without external interference\.
- •Structured Generation \(NL/JSON\):Constrained decoding usingOutlines\(Willard and Louf,[2023](https://arxiv.org/html/2510.03595#bib.bib37)\)to strictly enforce the target output format, either via a natural language template or a JSON schema\.
- •Ctrl\-G:A controllable generation baseline that uses an HMM distilled from unconditional sampling to guide generation, as detailed inZhang et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib45)\)\.

For the following experiments, we adopt greedy decoding to ensure fair comparison with baseline methods and evaluate zero\-shot performance\.

Table 1:GSM8k Results\.Deco\-Gguarantees format satisfaction and consistently outperforms Prompt\-Only and Outlines baselines across all models\.
### 4\.1Mathematical Reasoning

In this task, we evaluate our framework on GSM8k\(Cobbe et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib5)\), a collection of grade school math problems that take two to eight steps to solve\. Models are expected to carry out step\-by\-step reasoning and arrive at the answer\. FollowingTam et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib33)\), a group of task instructions is adopted to prompt the model to first reason about the math problem and then yield an integer as its answer\. For JSON format output, we prompt the model to output valid JSON blob with keys“reason”and“answer\.”For natural language output, format instructions are used to encourage the model to generate the template phrase“The final answer is …”Meanwhile, this phrase is specified as a key phrase to appear inDeco\-G’s generation\.

#### Evaluation Metrics\.

We measureFormat Complianceas the rate to which the generated answer follows format requirement\. In addition, we measureAccuracyas exact match of ground truth\.

#### Results\.

As shown in[Table˜1](https://arxiv.org/html/2510.03595#S4.T1),Prompt\-Only \(NL\)offers decent performance, withLlamascoring82\.3%82\.3\\%,Qwen2\.583\.6%83\.6\\%, andQwen390\.5%90\.5\\%on accuracy\. However, unstructured generation methods completely rely on the LLM for following format constraints and thus suffer from low compliance rate\. Structured generation \(Outlines\), on the contrary, guarantees format compliance, but its invasive intervention compromises task performance\. While both Ctrl\-G andDeco\-Gguarantee format compliance,Deco\-Gbenefits from more accurate control signal provided by the instruction\-aware HMM and achieves the best performance across all three models\. In practice, we observe thatQwenmodels have more skewed token distribution\. We thus raise the control factorγ\\gammato exert stronger control on the output\.

### 4\.2Event Argument Extraction

The generative event argument extraction \(EAE\) task assesses a model’s ability in identifying role\-related arguments from source text\. We evaluate on the ACE05\-EN dataset\(Doddington et al\.,[2004](https://arxiv.org/html/2510.03595#bib.bib9)\), in which a model is presented with an article, a trigger word, and a set of roles to determine whether arguments associated with the roles are present in the article\. This is naturally a templated task as generative models have to specify which word is extracted for which role\. Regarding JSON output, we ask model to generate a JSON blob with roles as keys and extracted arguments as values\. For natural language output, we specify the template“The <rolei\> is …”for every relevant role\. ForDeco\-G, we construct a flexible DFA that fuses the template phrases together with empty slots allowing LLM predict arguments spanning from 1 to 5 tokens\.

#### Evaluation Metrics\.

We measure performance by calculating thef1\-scorecomparing the extracted tuples and the ground truth tuples for the following categories: Argument Id \(AI\), Argument Class \(AC\), Argument\-attached Id \(AI\+\), Argument\-attached Class \(AC\+\)\.

#### Results\.

Thef1\-scoresreported in[Table˜2](https://arxiv.org/html/2510.03595#S4.T2)suggest that EAE remains a challenging task for generative models\. LLMs suffer from identifying correct relations in the article and presenting valid predictions that exist in the original text\. Baseline methods show inconsistent trends across models, indicating LLMs’ lack of robustness in event argument extraction\. EmployingDeco\-Genhances overall extraction quality forLlamaandQwen3, while mainly improving over AI and AI\+ forQwen2\.5\.Deco\-G’s gain on AI and AI\+ is more evident than its improvement on AC and AC\+, suggesting thatDeco\-Gcan further benefit from a tighter association between roles and extracted arguments\.

Table 2:Generative EAE results on ACE05\.Table 3:SummEval results, measured over Coherence, Consistency, Fluency, and Relevance\.

### 4\.3LLM\-as\-a\-judge Evaluation

We then use LLMs as judges to evaluate the quality of summaries and assess how well it aligns with human annotation\. This evaluation is performed on the SummEval\(Fabbri et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib10)\)which consists 1600 machine\-generated summaries for 100 news articles and human annotated scores over four dimensions: Coherence, Consistency, Fluency, and Relevance\. The models are asked to analyze the summary and assign a score from 1 to 5 based on the given criteria suggested by ChatGPT\(OpenAI,[2025](https://arxiv.org/html/2510.03595#bib.bib27)\)\. We use the format “The rating is …” for natural language output and “rating” as the key for harnessing JSON output\.

#### Evaluation Metrics\.

FollowingLiu et al\. \([2023](https://arxiv.org/html/2510.03595#bib.bib23)\), we adopt the summary\-level Spearman and Kendall\-Tau correlation to gauge the performance of each method\. Higher number indicates better alignment with human annotated scores\.

#### Results\.

For this task,Qwenmodels perform well in following the output format in unstructured settings, securing over99\.7%99\.7\\%compliance rate\. This may attribute to a less intensive reasoning phase compared to mathematical reasoning\. As indicated in[Table˜3](https://arxiv.org/html/2510.03595#S4.T3),Deco\-Gdemonstrates strongest average correlation with human annotator, enhancing over Consistency, Fluency, and Relevance when applied toQwenmodels\. A qualitative inspection reveals thatDeco\-Genables the flexible integration of scoring phrases at arbitrary positions, whereas unstructured and structured baselines consistently append ratings only after the analysis concludes\.

## 5Analysis

### 5\.1Complexity and Efficiency

![Refer to caption](https://arxiv.org/html/2510.03595v2/x3.png)\(a\)Llama\-3\.1\-8B\-Instruct
![Refer to caption](https://arxiv.org/html/2510.03595v2/x4.png)\(b\)Qwen2\.5\-7B\-Instruct
![Refer to caption](https://arxiv.org/html/2510.03595v2/x5.png)\(c\)Qwen3\-8B

Figure 3:Average retention rate \(of total mass\) overtop−k\\operatorname\{top\-k\}HMM hidden states on GSM8k dataset\.We analyze the efficiency ofDeco\-Gfrom both theoretical complexity and empirical latency perspectives, highlighting improvements brought by our HMM pruning \(Section[3\.4](https://arxiv.org/html/2510.03595#S3.SS4)\) and flexible trie construction \(Section[3\.2](https://arxiv.org/html/2510.03595#S3.SS2)\)\.

Table 4:Deco\-Gperformance on GSM8k with and without pruning\.#### Hidden State Sparsity\.

Our pruning strategy is empirically justified by the highly concentrated nature of the hidden state distributions \([Figure˜3](https://arxiv.org/html/2510.03595#S5.F3)\)\. ForLlama\- andQwen\-distilled HMMs, the top 5% of hidden states \(k=200k=200\) capture over 97\.8% of the total probability mass on average\. Crucially, this approximation preserves task performance\. As shown in[Table˜4](https://arxiv.org/html/2510.03595#S5.T4), the accuracy degradation on GSM8k is minimal when pruning is applied \(e\.g\., \-0\.2% forLlama, \+0\.9% forQwen3\)\. This confirms that the pruned HMM retains sufficient guidance information to steer generation effectively\.

#### Computational Complexity\.

The primary bottleneck in HMM\-guided generation is the emission probability calculation, which typically scales withO​\(h​\|𝒱\|\)O\(h\|\\mathcal\{V\}\|\)\. By exploiting the sparsity established above, we reduce this complexity toO​\(k​\|𝒱\|\)O\(k\|\\mathcal\{V\}\|\)wherek≪hk\\ll h\. Withk=200k=200, this yields a∼13×\\sim 13\\timesreduction in guidance FLOPs \(from 1\.08 down to 0\.08 GFLOPs for an 8B model\)\. Consequently, the total computational cost of the FEM constitutes only∼0\.53%\\sim 0\.53\\%of the LLM’s main forward pass\(Kaplan et al\.,[2020](https://arxiv.org/html/2510.03595#bib.bib15)\), rendering the overhead negligible\.

#### Empirical Latency\.

We measure the wall\-clock latency ofDeco\-Gagainst standard unconstrained generation, structured generation baselines \(Outlines\), and prior HMM\-based control \(Ctrl\-G\)\. As shown in Table[5](https://arxiv.org/html/2510.03595#S5.T5),Deco\-Gincurs minimal latency overhead while guaranteeing format compliance\.

Table 5:Inference latency comparison on GSM8k with single NVIDIA A100\.
#### Scalability with Constraint Complexity\.

Beyond raw speed,Deco\-Gdemonstrates superior scalability when handling complex constraints compared to baselines:

- •vs\. Structured Generation:Frameworks like Outlines\(Willard and Louf,[2023](https://arxiv.org/html/2510.03595#bib.bib37)\)and Guidance\(guidance\-ai,[2024](https://arxiv.org/html/2510.03595#bib.bib12)\)rely on intersecting FSMs with the LLM vocabulary\. This becomes computationally prohibitive for “floating” constraints atarbitrary positions\(e\.g\., after free\-form reasoning\), as modeling such unconstrained spans over long sequences triggers state\-space explosion in the automaton\. In contrast,Deco\-Gnaturally handles these “floating” constraints, allowing the LLM to generate free\-form text until the probabilistic guidance steers it into the target format, without requiring expensive pre\-computation of all possible prefix permutations\.
- •vs\. Ctrl\-G:Ctrl\-G\(Zhang et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib45)\)fails on templates with chained variable\-length segments, such as EAE extraction slots \(e\.g\., “Role A: \[span\] Role B: \[span\]”\)\. Standard DFA construction creates unique paths for every length permutation, causing exponential state explosion \(O​\(KN\)O\(K^\{N\}\)forNNslots\)\. OurFlexible Trie\(Section[3\.2](https://arxiv.org/html/2510.03595#S3.SS2)\) avoids this by merging wildcard paths at each fixed pivot, achieving linear complexity \(O​\(N×K\)O\(N\\times K\)\)\.

### 5\.2The Steering Process

Deco\-Gtakes advantage of HMM to estimate the future format satisfaction rate and adjust token probabilities based on the estimation\. To better understand this steering process, we examine the control signals produced by the FEM and visualize the control for a span of decoding step\. We track the original LLM distribution, FEM distribution, and their composed distribution, whichDeco\-Gdecodes from\.[Figure˜5](https://arxiv.org/html/2510.03595#A3.F5)provides an illustration ofDeco\-Gencouraging the generation of key phrase after step by step reasoning\. While the LLM tends to conclude its response with “The total number of … is …”Deco\-Gassigns high probabilities to the token “final,” steering the LLM generation to conform with format constraints\.

As LLMs are trained to provide clear and concise response, they tend to avoid repeating themselves when presenting the final answer\.Deco\-Gcaptures this intricacy and replaces LLM’s intended conclusive phrase with the format phrase “The final answer is” to reduce repetition\. We consider this format integration to be more natural than forcing LLM to generate certain phrases as in regex\-structured generation\.

## 6Related work

In the paper, we explore a controllable text generation \(CTG\) method to decouple task solving from format adherence\. There are two branches in CTG that provide avenues for achieving this format\-task decoupling—content\-wise hard control and attribute\-wise soft control\.Content\-wise methods\(Willard and Louf,[2023](https://arxiv.org/html/2510.03595#bib.bib37); guidance\-ai,[2024](https://arxiv.org/html/2510.03595#bib.bib12)\)enforce strict adherence to predefined templates, ensuring reliability but often exerting invasive control that leads to abrupt, incoherent cut\-offs\.Attribute\-wise soft controloffers greater flexibility, either by updating model weights—via retraining\(Keskar et al\.,[2019](https://arxiv.org/html/2510.03595#bib.bib16); Arora et al\.,[2022](https://arxiv.org/html/2510.03595#bib.bib1)\), fine\-tuning\(Wei et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib34); Zeldes et al\.,[2020](https://arxiv.org/html/2510.03595#bib.bib42); Li and Liang,[2021](https://arxiv.org/html/2510.03595#bib.bib20); Lester et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib19)\), or reinforcement learning\(Ouyang et al\.,[2022](https://arxiv.org/html/2510.03595#bib.bib28); Stiennon et al\.,[2020](https://arxiv.org/html/2510.03595#bib.bib32); Zeng et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib43); Dai et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib6)\)—or throughweighted decoding\(Dathathri et al\.,[2019](https://arxiv.org/html/2510.03595#bib.bib7); Yang and Klein,[2021](https://arxiv.org/html/2510.03595#bib.bib39); Krause et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib18); Schick et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib30); Liu et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib22); Khandelwal et al\.,[2021](https://arxiv.org/html/2510.03595#bib.bib17); Sitdikov et al\.,[2022](https://arxiv.org/html/2510.03595#bib.bib31); Wen et al\.,[2023](https://arxiv.org/html/2510.03595#bib.bib36); Deng and Raffel,[2023](https://arxiv.org/html/2510.03595#bib.bib8); Loula et al\.,[2025](https://arxiv.org/html/2510.03595#bib.bib25); Lipkin et al\.,[2025](https://arxiv.org/html/2510.03595#bib.bib21)\)\. The latter steers generation at inference time using lightweight auxiliary models \(Bayes’ rule\) without the high cost of retraining\.Deco\-Gadopts this weighted decoding paradigm to compute the posterior probability of format constraints as a decoupled attribute\.

## 7Conclusion

We presentDeco\-G, a novel decoding framework designed to decouple the responsibilities of task reasoning and format adherence\. It achieves this responsibility separation by employing an auxiliary Format Estimation Module to estimate future format satisfaction and modify token probabilities, thus allowing the LLM to concentrate solely on problem\-solving\. Experiments on mathematical reasoning, event argument extraction, and LLM\-as\-a\-judge evaluation demonstrate this decoupling approach leads to overall performance gain, attributed to improved format compliance and more natural format integration in the response\.

## Limitations

While we showDeco\-Genhances LLM task performance in various tasks, a few limitations should be taken into consideration when usingDeco\-G\. Firstly, the HMM used to estimate format satisfaction rate is specific to an LLM, meaning that one has to distill a new HMM when switching to a different LLM\. Although, in practice, we find that an HMM can be applied to larger LLMs in the same family, it is not an accurate representation of their token distributions\. Secondly, similar to other CTG methods that includes additional module for attribute modeling,Deco\-Gintroduces additional computation overhead during decoding\. As suggested by\(Zhang et al\.,[2024](https://arxiv.org/html/2510.03595#bib.bib45)\), the probabilistic traversal of future generation courses using HMM has a complexity that is linear to the number of edges in DFA and quadratic to the number of hidden states in HMM\. Complex format constraints, converted to larger DFA, are thus likely to increase generation runtime\. Finally, finding the optimal hyperparameterγ\\gammafor LLMs with highly peaked token distributions may require empirical explorations\. Such distributions require increasedγ\\gammato ensure robust format compliance, yet an excessive value may adversely affect the output quality\.

## Ethical considerations

We conduct experiments on mathematical reasoning, event argument extraction, and LLM\-as\-a\-judge evaluation\. The score assigned by an LLM should not be considered an accurate reflection of quality of the summary\. In addition, the LLM responses to the GSM8k questions should not be referenced for math instruction as they may include hallucination\.

We acknowledge the use of AI assistants for improving the manuscript’s prose, generating tables in LaTeX format, figure design, and assisting with code implementation for the analysis of HMM hidden state pruning\. All generated content, particularly the data in tables, was manually verified for accuracy against our experimental results\.

## References

- Arora et al\. \(2022\)Kushal Arora, Kurt Shuster, Sainbayar Sukhbaatar, and Jason Weston\. 2022\.Director: Generator\-classifiers for supervised language modeling\.In*Proceedings of the 2nd Conference of the Asia\-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference on Natural Language Processing \(Volume 1: Long Papers\)*, pages 512–526\.
- Baum \(1972\)Leonard E Baum\. 1972\.An inequality and associated maximization technique in statistical estimation for probabilistic functions of markov processes\.*Inequalities*, 3\(1\):1–8\.
- Beurer\-Kellner et al\. \(2024\)Luca Beurer\-Kellner, Marc Fischer, and Martin Vechev\. 2024\.[Guiding LLMs the right way: Fast, non\-invasive constrained generation](https://proceedings.mlr.press/v235/beurer-kellner24a.html)\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235 of*Proceedings of Machine Learning Research*, pages 3658–3673\. PMLR\.
- Chung et al\. \(2024\)Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro\-Ros, Marie Pellat, Kevin Robinson, and 16 others\. 2024\.[Scaling instruction\-finetuned language models](http://jmlr.org/papers/v25/23-0870.html)\.*Journal of Machine Learning Research*, 25\(70\):1–53\.
- Cobbe et al\. \(2021\)Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman\. 2021\.[Training verifiers to solve math word problems](https://arxiv.org/abs/2110.14168)\.*Preprint*, arXiv:2110\.14168\.
- Dai et al\. \(2024\)Josef Dai, Xuehai Pan, Ruiyang Sun, Jiaming Ji, Xinbo Xu, Mickel Liu, Yizhou Wang, and Yaodong Yang\. 2024\.Safe rlhf: Safe reinforcement learning from human feedback\.In*The Twelfth International Conference on Learning Representations*\.
- Dathathri et al\. \(2019\)Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu\. 2019\.Plug and play language models: A simple approach to controlled text generation\.*arXiv preprint arXiv:1912\.02164*\.
- Deng and Raffel \(2023\)Haikang Deng and Colin Raffel\. 2023\.Reward\-augmented decoding: Efficient controlled text generation with a unidirectional reward model\.In*Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing*, pages 11781–11791\.
- Doddington et al\. \(2004\)George R Doddington, Alexis Mitchell, Mark A Przybocki, Lance A Ramshaw, Stephanie M Strassel, and Ralph M Weischedel\. 2004\.The automatic content extraction \(ace\) program\-tasks, data, and evaluation\.In*Lrec*, volume 2, pages 837–840\. Lisbon\.
- Fabbri et al\. \(2021\)Alexander R Fabbri, Wojciech Kryściński, Bryan McCann, Caiming Xiong, Richard Socher, and Dragomir Radev\. 2021\.Summeval: Re\-evaluating summarization evaluation\.*Transactions of the Association for Computational Linguistics*, 9:391–409\.
- Grattafiori et al\. \(2024\)Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al\-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, and 542 others\. 2024\.[The llama 3 herd of models](https://arxiv.org/abs/2407.21783)\.*Preprint*, arXiv:2407\.21783\.
- guidance\-ai \(2024\)guidance\-ai\. 2024\.Guidance: A guidance language for controlling large language models\.[https://github\.com/guidance\-ai/guidance](https://github.com/guidance-ai/guidance)\.
- He et al\. \(2024\)Jia He, Mukund Rungta, David Koleczek, Arshdeep Sekhon, Franklin X Wang, and Sadid Hasan\. 2024\.[Does prompt formatting have any impact on llm performance?](https://arxiv.org/abs/2411.10541)*Preprint*, arXiv:2411\.10541\.
- Hendrycks et al\. \(2020\)Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt\. 2020\.Measuring massive multitask language understanding\.*arXiv preprint arXiv:2009\.03300*\.
- Kaplan et al\. \(2020\)Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei\. 2020\.Scaling laws for neural language models\.*arXiv preprint arXiv:2001\.08361*\.
- Keskar et al\. \(2019\)Nitish Shirish Keskar, Bryan McCann, Lav R Varshney, Caiming Xiong, and Richard Socher\. 2019\.Ctrl: A conditional transformer language model for controllable generation\.*arXiv preprint arXiv:1909\.05858*\.
- Khandelwal et al\. \(2021\)Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis\. 2021\.Generalization through memorization: Nearest neighbor language models\.In*International Conference on Learning Representations*\.
- Krause et al\. \(2021\)Ben Krause, Akhilesh Deepak Gotmare, Bryan McCann, Nitish Shirish Keskar, Shafiq Joty, Richard Socher, and Nazneen Fatema Rajani\. 2021\.Gedi: Generative discriminator guided sequence generation\.In*Findings of the Association for Computational Linguistics: EMNLP 2021*, pages 4929–4952\.
- Lester et al\. \(2021\)Brian Lester, Rami Al\-Rfou, and Noah Constant\. 2021\.The power of scale for parameter\-efficient prompt tuning\.In*Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing*, pages 3045–3059\.
- Li and Liang \(2021\)Xiang Lisa Li and Percy Liang\. 2021\.Prefix\-tuning: Optimizing continuous prompts for generation\.In*Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing \(Volume 1: Long Papers\)*, pages 4582–4597\.
- Lipkin et al\. \(2025\)Benjamin Lipkin, Benjamin LeBrun, Jacob Hoover Vigly, João Loula, David R\. MacIver, Li Du, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Timothy J\. O’Donnell, Alexander K\. Lew, and Tim Vieira\. 2025\.[Fast controlled generation from language models with adaptive weighted rejection sampling](https://arxiv.org/abs/2504.05410)\.*Preprint*, arXiv:2504\.05410\.
- Liu et al\. \(2021\)Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula, Noah A Smith, and Yejin Choi\. 2021\.Dexperts: Decoding\-time controlled text generation with experts and anti\-experts\.In*Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing \(Volume 1: Long Papers\)*, pages 6691–6706\.
- Liu et al\. \(2023\)Yang Liu, Dan Iter, Yichong Xu, Shuohang Wang, Ruochen Xu, and Chenguang Zhu\. 2023\.G\-eval: Nlg evaluation using gpt\-4 with better human alignment\.*arXiv preprint arXiv:2303\.16634*\.
- Long et al\. \(2025\)Do Xuan Long, Ngoc\-Hai Nguyen, Tiviatis Sim, Hieu Dao, Shafiq Joty, Kenji Kawaguchi, Nancy F\. Chen, and Min\-Yen Kan\. 2025\.[LLMs are biased towards output formats\! systematically evaluating and mitigating output format bias of LLMs](https://aclanthology.org/2025.naacl-long.15/)\.In*Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\)*, pages 299–330, Albuquerque, New Mexico\. Association for Computational Linguistics\.
- Loula et al\. \(2025\)João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K\. Lew, Tim Vieira, and Timothy J\. O’Donnell\. 2025\.[Syntactic and semantic control of large language models via sequential monte carlo](https://openreview.net/forum?id=xoXn62FzD0)\.In*The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24\-28, 2025*\. OpenReview\.net\.
- Mishra et al\. \(2022\)Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi\. 2022\.Cross\-task generalization via natural language crowdsourcing instructions\.In*ACL*\.
- OpenAI \(2025\)OpenAI\. 2025\.[ChatGPT](https://chat.openai.com/)\.Large language model\. Accessed May 19, 2025\.
- Ouyang et al\. \(2022\)Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe\. 2022\.[Training language models to follow instructions with human feedback](https://proceedings.neurips.cc/paper_files/paper/2022/file/b1efde53be364a73914f58805a001731-Paper-Conference.pdf)\.In*Advances in Neural Information Processing Systems*, volume 35, pages 27730–27744\. Curran Associates, Inc\.
- Ren and Sutherland \(2025\)Yi Ren and Danica J\. Sutherland\. 2025\.[Learning dynamics of llm finetuning](https://arxiv.org/abs/2407.10490)\.*Preprint*, arXiv:2407\.10490\.
- Schick et al\. \(2021\)Timo Schick, Sahana Udupa, and Hinrich Schütze\. 2021\.Self\-diagnosis and self\-debiasing: A proposal for reducing corpus\-based bias in nlp\.*Transactions of the Association for Computational Linguistics*, 9:1408–1424\.
- Sitdikov et al\. \(2022\)Askhat Sitdikov, Nikita Balagansky, Daniil Gavrilov, and Alexander Markov\. 2022\.Classifiers are better experts for controllable text generation\.*arXiv preprint arXiv:2205\.07276*\.
- Stiennon et al\. \(2020\)Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano\. 2020\.Learning to summarize with human feedback\.*Advances in Neural Information Processing Systems*, 33:3008–3021\.
- Tam et al\. \(2024\)Zhi Rui Tam, Cheng\-Kuang Wu, Yi\-Lin Tsai, Chieh\-Yen Lin, Hung yi Lee, and Yun\-Nung Chen\. 2024\.[Let me speak freely? a study on the impact of format restrictions on performance of large language models](https://arxiv.org/abs/2408.02442)\.*Preprint*, arXiv:2408\.02442\.
- Wei et al\. \(2021\)Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le\. 2021\.Finetuned language models are zero\-shot learners\.*arXiv preprint arXiv:2109\.01652*\.
- Wei et al\. \(2022\)Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou\. 2022\.[Chain\-of\-thought prompting elicits reasoning in large language models](https://proceedings.neurips.cc/paper_files/paper/2022/file/9d5609613524ecf4f15af0f7b31abca4-Paper-Conference.pdf)\.In*Advances in Neural Information Processing Systems*, volume 35, pages 24824–24837\. Curran Associates, Inc\.
- Wen et al\. \(2023\)Zhihua Wen, Zhiliang Tian, Zhen Huang, Yuxin Yang, Zexin Jian, Changjian Wang, and Dongsheng Li\. 2023\.Grace: gradient\-guided controllable retrieval for augmenting attribute\-based text generation\.In*Findings of the Association for Computational Linguistics: ACL 2023*, pages 8377–8398\.
- Willard and Louf \(2023\)Brandon T Willard and Rémi Louf\. 2023\.Efficient guided generation for llms\.*arXiv preprint arXiv:2307\.09702*\.
- Yang et al\. \(2025a\)An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, and 41 others\. 2025a\.[Qwen3 technical report](https://arxiv.org/abs/2505.09388)\.*Preprint*, arXiv:2505\.09388\.
- Yang and Klein \(2021\)Kevin Yang and Dan Klein\. 2021\.Fudge: Controlled text generation with future discriminators\.In*Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies*, pages 3511–3535\.
- Yang et al\. \(2025b\)Qwen: An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, and 23 others\. 2025b\.[Qwen2\.5 technical report](https://arxiv.org/abs/2412.15115)\.*Preprint*, arXiv:2412\.15115\.
- Yao et al\. \(2023\)Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan\. 2023\.Tree of thoughts: Deliberate problem solving with large language models\.*Advances in neural information processing systems*, 36:11809–11822\.
- Zeldes et al\. \(2020\)Yoel Zeldes, Dan Padnos, Or Sharir, and Barak Peleg\. 2020\.Technical report: Auxiliary tuning and its application to conditional text generation\.*arXiv preprint arXiv:2006\.16823*\.
- Zeng et al\. \(2024\)Yongcheng Zeng, Guoqing Liu, Weiyu Ma, Ning Yang, Haifeng Zhang, and Jun Wang\. 2024\.Token\-level direct preference optimization\.In*Proceedings of the 41st International Conference on Machine Learning*, pages 58348–58365\.
- Zhang et al\. \(2023\)Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck\. 2023\.[Tractable control for autoregressive language generation](https://arxiv.org/abs/2304.07438)\.*Preprint*, arXiv:2304\.07438\.
- Zhang et al\. \(2024\)Honghua Zhang, Po\-Nien Kung, Masahiro Yoshida, Guy Van den Broeck, and Nanyun Peng\. 2024\.[Adaptable logical control for large language models](https://arxiv.org/abs/2406.13892)\.*Preprint*, arXiv:2406\.13892\.

## Appendix AProbabilistic Reasoning over Logical Constraints

Zhang et al\. \([2023](https://arxiv.org/html/2510.03595#bib.bib44)\)andZhang et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib45)\)use a TPM to perform a probabilistic lookahead—that is, to efficiently computePTPM​\(α\|x≤t\)P\_\{\\mathrm\{TPM\}\}\(\\alpha\|x\_\{\\leq t\}\), the probability that the full generated sequence will satisfy the constraintα\\alpha\. The constraint is encoded as a DFA, and compliance is denoted by the event𝒟​\(α\)=1\\mathcal\{D\}\(\\alpha\)=1\. Then, the marginal probability over all sequences accepted by𝒟​\(α\)\\mathcal\{D\(\\alpha\)\}is expressed as

PTPM​\(α\|x≤t\)=PTPM​\(𝒟​\(α\)=1,x≤t\)PHMM​\(x≤t\)P\_\{\\mathrm\{TPM\}\}\(\\alpha\|x\_\{\\leq t\}\)=\\frac\{P\_\{\\mathrm\{TPM\}\}\(\\mathcal\{D\}\(\\alpha\)=1,x\_\{\\leq t\}\)\}\{P\_\{\\mathrm\{HMM\}\}\(x\_\{\\leq t\}\)\}where the numerator—likelihood of satisfying the constraint given a prefixx≤tx\_\{\\leq t\}—is found by marginalizing over the HMM hidden statesztz\_\{t\}and the DFA statessts\_\{t\}

PTPM​\(𝒟​\(α\)=1,x≤t\)=∑ztPTPM​\(𝒟​\(α\)=1∣zt,st\)​PHMM​\(zt,x≤t\)\\begin\{split\}&P\_\{\\mathrm\{TPM\}\}\(\\mathcal\{D\}\(\\alpha\)=1,x\_\{\\leq t\}\)=\\\\ &\\quad\\sum\_\{z\_\{t\}\}P\_\{\\mathrm\{TPM\}\}\(\\mathcal\{D\}\(\\alpha\)=1\\mid z\_\{t\},s\_\{t\}\)P\_\{\\mathrm\{HMM\}\}\(z\_\{t\},x\_\{\\leq t\}\)\\end\{split\}The conditional compliance probabilityPTPM​\(𝒟​\(α\)=1\|zt,st\)P\_\{\\mathrm\{TPM\}\}\(\\mathcal\{D\}\(\\alpha\)=1\|z\_\{t\},s\_\{t\}\), as shown inZhang et al\. \([2024](https://arxiv.org/html/2510.03595#bib.bib45)\), is calculated using a backward recurrence relation\. This sums the probabilities of all valid transitions from steptttot\+1t\+1, weighted by the HMM’s transition and emission probabilities

P​\(𝒟​\(α\)=1∣zt,st\)=∑zt\+1P​\(zt\+1∣zt\)​∑st\+1P​\(𝒟​\(α\)=1∣zt\+1,st\+1\)∑δ​\(st,xt\+1\)=st\+1P​\(xt\+1∣zt\+1\)\\begin\{split\}&P\(\\mathcal\{D\}\(\\alpha\)=1\\mid z\_\{t\},s\_\{t\}\)=\\\\ &\\quad\\sum\_\{z\_\{t\+1\}\}P\(z\_\{t\+1\}\\mid z\_\{t\}\)\\sum\_\{s\_\{t\+1\}\}P\(\\mathcal\{D\}\(\\alpha\)=1\\mid z\_\{t\+1\},s\_\{t\+1\}\)\\\\ &\\quad\\sum\_\{\\delta\(s\_\{t\},x\_\{t\+1\}\)=s\_\{t\+1\}\}P\(x\_\{t\+1\}\\mid z\_\{t\+1\}\)\\end\{split\}The computed probability then serves as the tractable approximation of the format compliance likelihood, which is used to guide the LLM’s next\-token generation as shown in Equation[2](https://arxiv.org/html/2510.03595#S2.E2)\.

## Appendix BSuboptimal Control from Unconditioned HMM Distillation

When an instruction\-tuned model is prompted with no specific user input for unconditional sampling, it often defaults to generic conversational phrases like, “Is there something I can help you with?” This behavior is a byproduct of its safety and helpfulness training\. An HMM distilled from corpora containing such non\-substantive responses learns a token distribution that is unrepresentative of the model’s capabilities in actual problem\-solving scenarios\.

Consequently, when this HMM is applied to a complex reasoning task, it produce suboptimal control signal that can disrupt the reasoning process of the LLM\. For example, withLlama, when we apply Ctrl\-G to the GSM8k dataset, its control mechanism prematurely forces the model to generate the required format phrase \(“The final answer is …”\), suppressing the step\-by\-step reasoning necessary to solve the problem\. This results in an accuracy of 61\.6%, even worse than the Prompt\-Only \(NL\) baseline\.

Table[6](https://arxiv.org/html/2510.03595#A2.T6)provides an example of this failure mode on a GSM8k problem, contrasting Ctrl\-G’s flawed output with the coherent response fromDeco\-G, which uses an instruction\-aware HMM\.

Table 6:Example of Ctrl\-G’s failure mode on GSM8k reasoning task\.
## Appendix CToken Entropy and Steering Strength

In the experiments, we reportDeco\-G’s results with hyperparameterγ=2\\gamma=2for controllingQwenmodels, asγ=1\\gamma=1doesn’t provide enough power to steer the model away from its own generation course\. We hypothesize thatQwenmodels’ token distributions are more skewed thanLlama’s, making it difficult for the control signal to actually make an impact on the distribution\. To verify this, we draw 100 examples from GSM8k responses and measure the average step\-wise entropy of LLM token distribution\. As shown in[Figure˜4](https://arxiv.org/html/2510.03595#A3.F4),Llama’s entropy is significantly higher than those ofQwen2\.5andQwen3, suggesting thatLlama’s token probabilities are more spread out and diverse, whereasQwenmodels’ token distributions are more peaky\. This increased peakiness could be a consequence of the distribution squeezing induced by more intensive fine\-tuning and preference optimization of the LLM\(Ren and Sutherland,[2025](https://arxiv.org/html/2510.03595#bib.bib29)\)\. It is thus intuitive to amplifyDeco\-G’s control strength for LLM with more skewed distribution to guarantee format compliance\.

Within the same model, structured generation methods have slightly higher entropy than their unstructured counterparts\. This may attribute to imposed template tokens provoking more uncertainty in future token prediction\. Meanwhile,Deco\-Gproduces lowest LLM entropy, indicating that an absence of format constraint in task solving may lead to LLM providing the most confident response\.

![Refer to caption](https://arxiv.org/html/2510.03595v2/x6.png)Figure 4:LLM’s token\-level entropy for different models and methods\.Llamahas a more flexible token distribution as compared toQwen\.![Refer to caption](https://arxiv.org/html/2510.03595v2/x7.png)Figure 5:Deco\-GsteersLlamato generate predefined template “The final answer is …” by boosting probabilities of template tokens\.
## Appendix DHMM Pruning and Efficiency

The primary benefit of HMM hidden state pruning is a substantial improvement in computational efficiency\. By reducing the computation of the HMM emission stage, pruning achieves a 13x reduction in the FLOPs required by the HMM forward function at each decoding step \(from approx\. 1\.08 GFLOPs to 0\.08 GFLOPs forLlama, calculation see below\)\. When compared to the LLM’s own forward pass, which requires approximately 16 GFLOPs per token\(Kaplan et al\.,[2020](https://arxiv.org/html/2510.03595#bib.bib15)\), the pruned FEM’s computational cost constitutes only about 0\.53% of the main inference workload\. This optimization renders the guidance overhead practically insignificant, thereby enhancing the viability of the DECO\-G framework\.

#### HMM Forward Computation Cost\.

Below, we specify the computational cost \(in FLOPs\) of the HMM’s forward pass\. The calculation uses the HMM parameters for theLlamamodel: hidden stateshh=4096, vocabulary size\|𝒱\|\|\\mathcal\{V\}\|=128k, andtop−k\\operatorname\{top\-k\}states for pruningkk=200\.

#### Before Pruning\.

The total cost is the sum of the state transition cost \(2​h22h^\{2\}\) and the emission cost \(2​h​\|𝒱\|2h\|\\mathcal\{V\}\|\)\.

Total FLOPs=\(2×40962\)\+\(2×4096×128,000\)=\(3\.36×107\)\+\(1\.05×109\)≈1\.08 GFLOPs\\begin\{split\}\\text\{Total FLOPs\}&=\(2\\times 4096^\{2\}\)\\\\ &\\quad\+\(2\\times 4096\\times 128\{,\}000\)\\\\ &=\(3\.36\\times 10^\{7\}\)\+\(1\.05\\times 10^\{9\}\)\\\\ &\\approx\\textbf\{1\.08 GFLOPs\}\\end\{split\}

#### After Pruning\.

The cost is the sum of the state transition cost and the pruned emission cost \(2​k​\|𝒱\|2k\|\\mathcal\{V\}\|\)\.

Total FLOPs=\(2×40962\)\+\(2×200×128,000\)=\(3\.36×107\)\+\(5\.12×107\)≈0\.08 GFLOPs\\begin\{split\}\\text\{Total FLOPs\}&=\(2\\times 4096^\{2\}\)\\\\ &\\quad\+\(2\\times 200\\times 128\{,\}000\)\\\\ &=\(3\.36\\times 10^\{7\}\)\+\(5\.12\\times 10^\{7\}\)\\\\ &\\approx\\textbf\{0\.08 GFLOPs\}\\end\{split\}This optimization reduces the HMM’s computational overhead from 1\.08 GFLOPs to 0\.08 GFLOPs, a∼\\sim13x reductionper decoding step\.

## Appendix EReproducibility Statement

A detailed description of our experimental setup, including the specific models used, HMM training parameters, and decoding strategy, is provided in the introductory paragraph of[Section˜4](https://arxiv.org/html/2510.03595#S4)\. To allow for replication of our experiments, the full prompts used for the mathematical reasoning \(GSM8k\), event argument extraction \(ACE05\), and LLM\-as\-a\-judge \(SummEval\) tasks are detailed in[Appendix˜F](https://arxiv.org/html/2510.03595#A6)\. Regarding computational overhead, a breakdown of the FLOPs required for the HMM forward pass, both with and without pruning, is presented in[Appendix˜D](https://arxiv.org/html/2510.03595#A4.SS0.SSS0.Px1)\.

## Appendix FPrompt Construction

We present the set of prompts used in the experiments\. For GSM8k \([Table˜8](https://arxiv.org/html/2510.03595#A8.T8)\), we sample from a set of task instructions and a set of format instructions to construct prompts for baseline methods\. For ACE05 \([Table˜9](https://arxiv.org/html/2510.03595#A8.T9)\), an event description is appended to the task instructions which further explains the event of interest\. For SummEval \([Table˜10](https://arxiv.org/html/2510.03595#A8.T10)\), we include domain specific scoring criteria in the task instructions to help LLM align better with human annotations for all methods\.

Table 7:Full ACE05 Results\.
## Appendix GMore EAE Results

In[Table˜2](https://arxiv.org/html/2510.03595#S4.T2), we report thef1\-scoresfor each method\. In[Table˜7](https://arxiv.org/html/2510.03595#A6.T7), we present the full results for our event argument extraction experiment\.

## Appendix HHMM Distillation and Usage

ForLlamaandQwen, we distill their HMMs on the LLM continuation only, since the instructions fromNatural\-Instructionsare human authored and should not be considered reflecting LLM distribution\. We remove the special chat tokens \(e\.g\. <\|system\|\>, <\|user\|\>, etc\.\) from the responses for HMM to capture the natural language distribution\.

We tried different inputs to the HMM, including 1\) regular prompt \(with chat template\), 2\) cleaned text prompt \(without chat template\), and 3\) no prompt \(empty string\)\. In practice, their results are almost identical\. Nonetheless, in accordance with the distillation objective, we report scores yielded from using empty input to the HMM\.

Table 8:GSM8k prompt construction and an example question\.Table 9:ACE05 prompt construction and an example question\.Table 10:SummEval prompts\.