CS Paper Radar

Constrained Decoding: Harmful or Beneficial? Revisiting Its Impact on LLM Performance

Ngoc Trinh Hung Nguyen, Alonso Silva, Armen Aghasaryan, Mehwish Alam

cs.CL cs.AI ·submitted 2026-10-26 12:26 UTC · v1
code/data

Abstract

Constrained decoding guarantees that Large Language Models (LLMs) produce outputs conforming to predefined formats, but is often assumed to inherently degrade reasoning. We examine this assumption through a taxonomy of three constraint types: \emph{format constraints}, which enforce output structure; \emph{validity constraints}, which mask invalid answer; and \emph{reasoning constraints}, which restrict reasoning trajectories. We theoretically show that appropriate constraints can preserve or improve performance by eliminating invalid paths. Across four model families and eleven open-source models, causal ablations on diverse benchmarks using state-of-the-art constrained decoding strategies reveal that apparent performance degradation largely stems from non-equivalent prompting and output formats rather than from decoder-level masking. Meanwhile, validity constraints improve reliability and extractability by eliminating invalid answers, while reasoning constraints can improve reasoning and, consequently, accuracy when they enforce beneficial trajectories. These findings show that the impact of constrained decoding depends on the type of constraint and the output space it removes. Our code is available.

Closest papers

Nearest neighbours by meaning across the whole index.

Large Language Models Can Follow Instructions, But Not Many at Once: Phase Transitions in Compositional Constraint Satisfaction

cs.AI cs.CL ·2026-08-12 ·Mariya I. Vasileva
benchmark similarity 0.74
Abstract · 35 pages, 7 figures, 13 tables. Reviewed in the ARR May 2026 cycle

Large language models are increasingly deployed in settings that require simultaneous adherence to multiple explicit constraints - reasoning structure, safety boundaries, output schemas. Individual constraints are handled proficiently, but the compositional regime, where many must hold jointly, remains poorly characterized: how rapidly does performance degrade, what governs the degradation, and can the collapse be mitigated? We introduce Constraint Saturation Evaluation (CSE), a procedurally generated benchmark that systematically varies the number of simultaneous constraints (k), with every constraint scored by a deterministic, rule-based verifier and zero LLM-judge involvement: 15 models, 36 constraint types, 369,753 checks at k=1-12. Three findings emerge. First, per-constraint pass rate decays gradually and predictably, while the chance of satisfying all k constraints collapses - a model passing individual constraints at ~41% at k=8 succeeds on all eight just 5.7% of the time. Second, constraints do not degrade equally: structural constraints lose 2x more baseline capability per added constraint than lexical ones, ordered by a comprehension-maintenance gap that separates constraints requiring sustained tracking from binary decisions immune to composition. Third, failures are nearly independent, which is what makes the accumulation multiplicative; the residual coupling that does exist tracks shared output features rather than pairwise interference - a wrong sentence count fails every constraint that reads it. Reliable instruction following breaks down beyond 5-6 simultaneous constraints: probe-level success falls below 50% at 7 constraints for the strongest model, and at 3 or fewer for 12 of 15.

0.47

Specification-Guided Generation for Large Language Models

cs.AI ·2026-10-30 ·Alessandro Previti, Konstantinos Vandikas, Mario Alviano, Mats Carlsson, Albin Larsson Forsberg +3 more
similarity 0.72
Abstract

Large language models (LLMs) can generate structured outputs, but existing constrained-decoding methods mainly enforce syntax and cannot directly enforce satisfaction of a formal specification. We introduce a neuro-symbolic, specification-guided decoding framework that combines LLM generation with symbolic reasoning. At each step, the framework refines the decoding grammar by filtering out values that cannot be extended to an output satisfying the specification. We present a forward-only variant that guarantees specification satisfaction by construction, and a backtracking variant that revises earlier feasible choices when their downstream consequences leave only values that the LLM itself judges unsuitable. The framework is model-agnostic, requires no retraining, and builds on existing grammar-constrained decoding mechanisms. Experiments on configuration and constraint-solving benchmarks show that the forward-only variant reliably produces specification-compliant outputs while reducing repeated LLM inference compared with rejection sampling and incurring modest symbolic-reasoning overhead. The backtracking variant further reduces cases in which the model is forced to select values that it has itself judged unsuitable, thereby substantially improving adherence to the LLM's stated interpretation of the prompt.

0.17

Decodable but Not Actionable: Auditing the Representation-Behavior Gap in Frozen LLMs for Geometric Constraints

cs.CL cs.AI ·2026-08-18 ·Man Liang, Xinzhao Cheng, Faizan Wajid
similarity 0.71
Abstract · Revised manuscript with expanded experiments, analyses, and discussion

Large language models (LLMs) perform well on structured reasoning tasks, but what they encode and whether encoded information guides their behavior remain unclear. We introduce a controlled auditing framework that uses parametric CAD to distinguish failures of encoding, expression, and activation-level control. Applied to eight pretrained models and matched randomly initialized controls, our framework reveals that pretraining contributes substantially more to linear decoding of local relations than to global constraint status, which is already highly decodable from random representations. Yet strong local decodability does not translate into the models' zero-shot predictions, which remain far below supervised probe performance. Restoring clean internal activations can repair probe predictions, whereas simple activation steering does not provide reliable targeted control. With only 400 labeled relation pairs, low-rank fine-tuning substantially improves generation on three representative models, showing that the representation--behavior gap can be reduced through adaptation. Together, these findings show why decodability alone is insufficient evidence that encoded information will be expressed or controllable in model behavior.

0.24

CIRCE Divines LLM Task Complexity from Constraint Structure

cs.AI ·2026-10-30 ·Chenhao Hong, Jiakai Xu, Kaushiki Singh, Yusen Zhang, Eugene Wu
similarity 0.69
Abstract

Estimating whether a problem is too complex for a large language model (LLM) before the model attempts it can guide model routing, how to allocate test-time compute, and suggest the need for new tools to aid the agent. While existing estimators rely on the problem text, LLM-annotated task difficulty labels, or signals obtained after a model attempts to solve the problem, such as its hidden states, none explicitly leverage the constraint structure inherent in the problem: the variables to assign and how the constraints over them interact. We introduce CIRCE, which extracts a problem's structure by using a cheap LLM to construct a Constraint Intermediate Representation that deterministically compiles into the constraint graph. Across seven reasoning benchmarks (including SAT, logic, and math) and four LLMs, even a randomly initialized GNN encoder improves predictions of LLM response correctness, reducing negative log-likelihood from 0.465 to 0.423 and increasing AUROC from 0.691 to 0.727 relative to the strongest baseline for each metric.

0.20

Constraint-Aware Training

cs.LG ·2026-10-02 ·Jinwoo Kim
similarity 0.69
Abstract · Accepted at Neurips 2026 workshop AI for Verifiable Coding

When generating programs with language models, constrained decoding can apply program analyses to exclude tokens that violate syntax, scope, or typing rules. However, there is a duplication: standard training already teaches the model to suppress the tokens rejected by these analyses. This duplication leads to the question: if we will perform some analysis to filter a set tokens out during inference anyways, can we avoid teaching the model the said analysis altogether during training, and does this externalization lead to more efficient models? This paper defines a general constraint-aware objective satisfying this externalization desideratum and formalizes the benefits of externalization into three concrete theorems about model size and data efficiency. We show, through a controlled synthetic experiment, that the theorems survive training dynamics: constraint-aware training yields lower prediction loss at a matched parameter count and data compared to ordinary cross-entropy training, motivating training objectives that incorporate the analyses used during generation.

0.28

Constrained Tagging for Span Labeling

cs.IR ·2026-10-20 ·Radek Štulc, Jan Drchal
similarity 0.69
Abstract · 22 pages, 7 Figures, 13 Tables

Generative LLMs can label spans without task-specific training, but their output is not tied to positions in the input: a returned span may be absent from the input or occur several times. We present constrained tagging, a training-free method in which the model reproduces the input and wraps each span in labeled inline markup. A logits processor using a byte-level token trie and a finite-state machine admits only tokens that continue the input verbatim or form a valid tag, so the output reproduces the input exactly with labels from the given set, and spans may begin or end at any character boundary, even inside a token. Two-phase decoding lets reasoning models reason before the constraint engages. On six datasets and six open-weight models, the guarantee holds in all but 0.022% of 255,312 constrained generations, each failure a reasoning model exhausting its token budget or never closing its reasoning, and the constraint adds no measurable cost. Unlike context-based prompting, which loses 8.5% of its spans, constrained tagging locates every span it proposes on every dataset; it is as accurate on two datasets, and on the other four its errors lie in which spans the model chooses, not where they are.

0.20

How Much Prompt Is Enough? A Blackbox Minimization of Few-Shots in LLMs

cs.SE cs.AIcs.HC ·2026-09-28 ·Ali Alfageeh, Rahul Gopinath, Amin Alipour
similarity 0.68
Abstract

Prompts are the primary mechanism for directing the behavior of large language models (LLMs). Yet the internal structure and causal hierarchy of prompts remain poorly understood: which parts are causally necessary and which are redundant is an open question. This opacity can have severe consequences. Subtle prompt variations can silently shift model outputs in critical software systems, and engineers lack techniques to reason about prompt reliability. We present \framework, a blackbox prompt-minimization framework that reduces few-shot prompts to their necessary minimal subset. We use a case study to apply \framework to a few-shot learning system and demonstrate the insights that this framework can provide. Our experiments show that few-shot exemplars can be reduced by a mean of 65.3\%~$\pm$~15.8\% in character count while fully preserving propositional output fidelity. The models preferentially retain logical identifiers and constraint declarations while discarding natural language prose and cross-prompt relational annotations. Our analysis also shows that some models are universal encoders, able to produce highly legible yet minimized prompts, while others are universal decoders, able to interpret minimized prompts from most other models. By identifying which components are indispensable, \framework provides a principled basis for prompt compression and structural analysis of few-shot exemplars.

0.21

StateGate: A Behavioral-Fidelity Prompt Optimization Method for Long-Chain LLM Agents

cs.CR ·2026-11-01 ·Shicheng Huang, Cai Fu, Jianqiang Lyu, Yifan Zhang, Xianmao Ji
similarity 0.68
Abstract · 13 pages, 3 figures, 7 tables. Preprint

Currently, long-chain LLM agents commonly suffer from behavioral degradation in complex tasks, where prompts are written in full but steps are not executed in full. To address this issue, existing approaches face three major challenges. First, constraints are strongly bound to their textual carriers; once natural-language constraint sentences are removed, their binding force vanishes. Second, the execution process lacks independent verification, as the evidence for judgment is often supplied by the executing party itself, leading to the failure of self-referential validation. Third, existing remediation schemes are difficult to generalize, and hard-coded mechanisms cannot be transferred across tasks. In this paper, we propose StateGate, a novel prompt-optimization scheme that transforms semantic constraints into symbolic gates enforced by an external deterministic runtime. By decoupling the content of a constraint from its carrier of efficacy, StateGate achieves behavioral fidelity in long-chain tasks without losing the binding force of the prompt. Specifically, we first propose four independent compression strategies (deduplication, generalization, externalization, and text-to-gating) together with their corresponding decision chains, enabling principled prompt symbolization. Second, we design a three-component architecture consisting of a state file, a validator, and an orchestrator, which thoroughly separates judgment authority from execution authority. Third, we formally prove that the compliance of symbolic constraints is independent of context size. Finally, we validate the framework on a vulnerability-discovery task in the security domain; the results show that StateGate achieves 100% execution closure and accurate vulnerability detection.

0.15