Hidden Biases in Conditioning Autoregressive Models

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.