Hidden Biases in Conditioning Autoregressive Models François Pachet, Pierre Roy Abstract Large language and music models are increasingly used for constrained generation: rhyming lines, fixed meter, inpainting or infilling, positional endings, and other global form requirements. These systems often perform strikingly well, but the induced procedures are usually not exact conditioning of the underlying autoregressive model. This creates a hidden inferential bias, distinct from the better-known notion of bias inherited from the training set: samples are distorted relative to the true constrained distribution, with no generic guarantee of complete coverage of the admissible solution space or of correct conditional probabilities over valid completions. We formalize several exact inference tasks for autoregressive models and prove corresponding hardness results. For succinctly represented autoregressive models whose next-token probabilities are computable in polynomial time, exact sentence-level maximum a posteriori (MAP) decoding is NP-hard. This hardness persists under unary and metrical constraints. On the sampling side, exact conditioned normalization is #P-hard even for regular constraints such as fixed-length terminal events. Unlike finite-state Markov models, general autoregressive models do not admit a bounded-state dynamic program for these tasks. These results formalize a standard claim in the neural decoding literature: local autoregressive sampling is easy, whereas exact decoding and exact conditioning under global form constraints are computationally intractable in general. 1 Introduction Large language models are now routinely used for constrained generation. Users ask them to write rhyming lines, continue a poem in a prescribed meter, fill in missing text, complete a partially specified sentence, enforce a suffix or a letter pattern at a given position, or satisfy combinations of such requirements. Similar uses appear in symbolic music, where sequence models are asked to inpaint missing passages or complete a score subject to formal constraints. Empirically, these systems often perform strikingly well. They produce many valid-looking constrained outputs, and they often give the impression that formal control is largely solved. That impression is misleading. When an autoregressive model is used in this way, the resulting procedure is usually not exact conditioning of the original model on the requested constraint. Instead, practical systems rely on heuristic search, reranking, local reweighting, rejection sampling, or separately trained infilling architectures. The resulting samples are therefore biased relative to the exact conditional law of the fixed underlying autoregressive model. More importantly, one generally does not know which part of the admissible solution space is actually explored, whether all valid completions remain reachable, or whether feasible completions are produced with the correct conditional probabilities. This is a different notion of bias from the one usually discussed for large language models. There the term typically refers to skew inherited from the training distribution or reflected in the generated content [ 2 ] . Here the bias is computational: with the pretrained model held fixed, approximate constrained-generation procedures distort the exact conditional distribution induced by the requested constraint. The results of this paper explain why. The issue is not that such constraints are linguistically or musically exotic. On the contrary, many of them are simple to state and even regular or additive in structure. The difficulty comes from the mismatch between local left-to-right generation and global exact satisfaction of a property of the whole completed sequence. An autoregressive model with parameters \theta defines, for each finite sequence x=x_{1:n} , P_{\theta}(x_{1:n})=\prod_{i=1}^{n}P_{\theta}(x_{i}\mid x_{1:i-1}). This factorization suggests computational simplicity. For unconstrained generation, that is correct: one samples sequentially from the next-token conditionals. But sequence-level optimization or conditioning is a different problem. Given access to the local conditionals, one may ask for the globally most probable complete sequence, x^{*}\in\argmax_{x\in\mathcal{C}}P_{\theta}(x), or for exact sampling from the model conditioned on some global event. For finite-state Markov models, such tasks are solved by dynamic programming because the relevant dependence on the past is summarized by a bounded state. General autoregressive models do not enjoy this property. Their next-token distribution may depend on the entire prefix through an unbounded contextual representation. As a result, the factorization of the probability does not imply a Viterbi-style algorithm for recovering the most probable sequence, nor an efficient forward-backward style algorithm for exact conditioning. This distinction is reflected in practice. In the neural sequence generation literature, exact MAP decoding is treated as computationally difficult, and approximate methods such as greedy search, beam search, and reranking are used instead [ 4 , 3 , 1 ] . Yet this point is usually made algorithmically rather than complexity-theoretically. The purpose of this note is to make a family of precise hardness statements explicit. Our contribution is elementary and conceptually clarifying. We prove that exact sentence-level MAP decoding is NP-hard for a natural class of succinctly represented autoregressive models. The hardness persists under unary constraints and under metrical constraints. On the sampling side, we prove that exact conditioned normalization is already #P-hard for regular constraints as simple as “having fixed length L and ending in eos .” This perspective explains why current constrained-generation systems can be useful and impressive while still failing to deliver exact conditional sampling: they do not provide a generic guarantee of complete coverage of the valid solution space, nor of correct conditional probabilities over that space. 2 Setup Let \Sigma be a finite vocabulary containing a distinguished end-of-sequence symbol \mathtt{eos} . An autoregressive model assigns probabilities to finite complete sequences through conditionals of the form P_{\theta}(x_{1:n})=\prod_{i=1}^{n}P_{\theta}(x_{i}\mid x_{1:i-1}), with the convention that generation terminates as soon as \mathtt{eos} is produced. We therefore write \mathcal{C} for the set of complete sequences \mathcal{C}=\bigcup_{n>1}\left\{x_{1:n}\in\Sigma^{n}:x_{n}=\mathtt{eos}\text{ and }x_{i}\neq\mathtt{eos}\text{ for }i