# Hidden Biases in Conditioning Autoregressive Models

arXiv: https://arxiv.org/abs/2604.07855 · HTML: https://mlsanity.com/paper/2604.07855/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 11 references that are in the map.
- First posted on arXiv 9 Apr 2026.

## Builds on (most cited first, 8 of 8)

- [Language (Technology) is Power: A Critical Survey of "Bias" in NLP](https://mlsanity.com/paper/2005.14050/) (2020)
- [Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation](https://mlsanity.com/paper/2005.10283/) (2020)
- [Enabling Language Models to Fill in the Blanks](https://mlsanity.com/paper/2005.05339/) (2020)
- [If beam search is the answer, what was the question?](https://mlsanity.com/paper/2010.02650/) (2020)
- [On NMT Search Errors and Model Errors: Cat Got Your Tongue?](https://mlsanity.com/paper/1908.10090/) (2019)
- [DeepBach: a Steerable Model for Bach Chorales Generation](https://mlsanity.com/paper/1612.01010/) (2016)
- [Learning to Traverse Latent Spaces for Musical Score Inpainting](https://mlsanity.com/paper/1907.01164/) (2019)
- [The Piano Inpainting Application](https://mlsanity.com/paper/2107.05944/) (2021)

## Built on by (most cited first, 1 of 1)

- [Stay Within Your Bounds: Distance-Guided Decoding for Guaranteed Context-Free Grammar Compliance](https://mlsanity.com/paper/2608.28229/) (2026)

## Abstract (arXiv)

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.