By François Pachet and Pierre Roy
François Pachet and Pierre Roy. “Hidden Biases in Conditioning Autoregressive Models.” arXiv:2604.07855, 2026.
About the paper
Suppose a model must write a line that ends with a particular word. A decoding procedure can enforce that ending and still change the relative probabilities of lines that meet the requirement. The paper explains how this distortion can arise even when the trained model stays fixed.
Abstract in brief
For general autoregressive models with efficiently computable next-token probabilities, the authors show that finding the most probable complete sequence is NP-hard. They also show that computing the exact probability of a conditioning event is #P-hard, even for some simple regular constraints. These results explain why the exact methods available for finite-state Markov models do not extend directly to general autoregressive models.
Related research
The NeurIPS 2026 paper on exact sampling shows what is possible for variable-order Markov models with regular constraints. The Markov Constraints project links to the implementation and playground.