Hidden Biases in Conditioning Autoregressive Models
Francois 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.
AI Impact Assessments
(3 models)Scientific Impact Assessment: "Hidden Biases in Conditioning Autoregressive Models"
1. Core Contribution
This paper formalizes the computational intractability of exact inference tasks for general autoregressive models under global constraints. The main results are:
The paper frames these results as explaining a "hidden inferential bias"—distinct from training data bias—arising when practitioners use heuristic methods (beam search, reranking, rejection sampling) to enforce global constraints on autoregressive models.
2. Methodological Rigor
The proofs are clean, correct, and follow standard complexity-theoretic reduction patterns. The SAT and #SAT reductions are straightforward: a CNF formula is encoded into an autoregressive model that generates bit assignments uniformly, then branches based on satisfiability. The constructions are polynomial-time and the conditional probabilities are efficiently computable, satisfying the succinct representation requirements.
However, the reductions are deliberately simple—perhaps too simple. The constructed autoregressive models are quite artificial: they are essentially lookup tables that evaluate a CNF formula at position m+1. The gap between these constructions and actual neural language models (transformers, RNNs) is significant. The paper acknowledges this implicitly by working with the broad class of "succinctly represented autoregressive models," but this generality is both a strength and a weakness—it captures the worst case but says little about typical cases encountered with real neural models.
The paper's formal framework is sound. The distinction between prefix-conditioned generation (easy) and suffix/global-conditioned generation (hard) is well articulated. The taxonomy of tractable vs. intractable constraints in Section 8 is useful.
3. Potential Impact
The paper addresses a genuine gap in the literature: the informal understanding that "exact constrained decoding is hard" has been widespread in the NLP community, but formal complexity-theoretic statements have been relatively scarce. By providing clean, citable hardness results, the paper serves a useful reference function.
Practical implications are modest but real. The results justify the use of approximate methods for constrained generation and frame the fundamental limitations of post-hoc constraint enforcement on pretrained autoregressive models. The inpainting corollary (Corollary 6) is particularly relevant given the proliferation of infilling systems in both text and music.
Influence on adjacent fields: The connection to music generation (inpainting, metrical constraints) broadens the audience. The distinction between inferential bias and training-data bias could sharpen discussions in the AI fairness and reliability communities.
However, the practical impact is limited because: (a) practitioners already know these tasks are hard and use approximations; (b) the results don't provide new algorithms or tighter characterizations for specific model architectures; (c) worst-case complexity results don't rule out efficient solutions for practically relevant instances.
4. Timeliness & Relevance
The paper is timely. Constrained generation from LLMs is a rapidly growing area, with applications in controlled text generation, code synthesis with specifications, and creative AI. The proliferation of systems that claim or appear to enforce global constraints makes the formalization of their limitations valuable.
The paper's framing around "hidden biases" is rhetorically effective and connects to current concerns about reliability and trustworthiness of AI systems. The observation that approximate conditioning creates systematic distortions in the output distribution—not just occasional failures—is an important conceptual point.
5. Strengths & Limitations
Strengths:
Limitations:
6. Additional Observations
The paper reads more as a "note" or position paper with formal backing than a full research contribution. The results, while correct and clearly stated, are essentially textbook-level reductions. The main value is in the framing and the explicit formalization rather than in technical novelty.
The paper would benefit from: (1) discussing whether specific neural architectures (e.g., bounded-context transformers) might yield tractability; (2) connecting to the extensive literature on inference in graphical models and weighted automata; (3) providing quantitative experiments measuring the magnitude of inferential bias in practical systems.
Generated Apr 10, 2026
Comparison History (99)
Paper 2 has higher likely impact: it formalizes a broadly relevant, under-theorized issue in constrained generation and provides general complexity-theoretic hardness results (NP-hard/#P-hard) that apply across language, music, and other autoregressive domains. The methodological rigor (formal definitions, proofs) and breadth/timeliness for decoding/conditioning practices make it foundational and widely citable. Paper 1 is timely and potentially important for alignment, but its contribution is more empirical and narrower (specific reward shaping and evaluations), with less immediate cross-field generality and more uncertainty about real-world deployment impact.
Paper 2 offers a foundational theoretical contribution: it formalizes “hidden inferential bias” in constrained generation and proves general NP-hard/#P-hard results for exact decoding and conditioning in autoregressive models, clarifying fundamental computational limits with broad relevance across NLP, music generation, and probabilistic inference. This kind of hardness characterization is highly reusable, shapes future method design (approximation/guarantees), and remains timely as constrained decoding is widely deployed. Paper 1 is novel and potentially useful for improving LLM reasoning, but its impact is more contingent on empirical robustness and adoption of a specific training framework.
Paper 1 establishes fundamental computational complexity results (NP-hardness, #P-hardness) for exact conditioning in autoregressive models, providing theoretical foundations that will remain relevant as long as these models are used. These hardness results formalize widely-held intuitions and have broad implications across NLP, music generation, and any constrained generation task. Paper 2 offers a useful practical framework for self-correction but is more incremental—recasting an empirical phenomenon via a simple Markov model with limited novelty. Paper 1's theoretical contributions have broader, more lasting impact across multiple fields.
Paper 1 presents a highly practical, large-scale unified biomedical knowledge graph with immediate, high-value real-world applications in drug discovery, RAG, and hypothesis generation. While Paper 2 offers important theoretical hardness proofs for AI, Paper 1's provision of a standardized, validated resource addresses a major bottleneck in bioinformatics, likely leading to broader immediate adoption and empirical impact across the life sciences.
Paper 1 addresses fundamental theoretical limitations of autoregressive models, which underpin modern AI across language, vision, and audio. By formally proving the computational intractability of exact conditioning, it establishes foundational constraints that will universally influence algorithm design. Paper 2 offers a highly valuable agent for reproducibility in computational biology, but focuses on a narrower domain. The broader applicability and foundational theoretical contributions of Paper 1 give it a significantly higher potential for widespread scientific impact across multiple disciplines.
Paper 1 offers a broadly relevant theoretical contribution: formalizing exact conditioning/decoding for autoregressive models and proving NP-hard/#P-hard results under common global constraints. This is highly novel in its rigor, provides durable “no free lunch” guidance for decoding/constraint methods, and impacts multiple fields (NLP, music generation, probabilistic inference, complexity theory). Paper 2 is timely and potentially useful system engineering for agent organizations, but its claims appear more empirical/architectural, likely less generalizable, and with weaker methodological permanence than complexity-theoretic barriers.
Paper 2 addresses a fundamental theoretical problem affecting the rapidly growing field of large language and music models. By formalizing and proving hardness results (NP-hard, #P-hard) for exact conditioning in autoregressive models, it provides rigorous theoretical foundations that impact a broad range of applications—constrained text generation, music composition, inpainting, and more. Its breadth of impact across AI/ML, theoretical CS, and NLP is substantial. Paper 1, while methodologically sound, addresses a narrower domain (road user interactions) with a computational model demonstration rather than broadly applicable theoretical results.
Paper 2 establishes fundamental theoretical limits (NP-hardness, #P-hardness) for exact constrained generation in autoregressive models, which underpin modern generative AI. While Paper 1 offers a valuable empirical architecture for agent systems, it is more likely to be quickly superseded in the fast-moving AI engineering space. Paper 2's foundational mathematical proofs provide lasting, rigorous insights that will fundamentally inform algorithm design and theoretical understanding across the broader field of machine learning.
Paper 2 addresses a fundamental theoretical question about autoregressive models—proving that exact conditioning and MAP decoding under global constraints are computationally intractable (NP-hard, #P-hard). This has broad implications across NLP, music generation, and any field using constrained autoregressive generation. The formal hardness results provide lasting theoretical foundations that explain widely observed empirical phenomena. Paper 1, while useful, addresses a narrower engineering problem (ablation automation for virtual cell repositories) with impact limited to a specific computational biology niche. Paper 2's breadth of applicability and theoretical depth give it greater potential impact.
Paper 2 is likely higher impact: it provides formal complexity-theoretic results (NP-hardness, #P-hardness) that clarify fundamental limits of exact conditioning/decoding for autoregressive models, directly relevant to widely used LLM/music generation practices. The contributions are broadly applicable across ML, NLP, computational creativity, and inference, and are timely given pervasive constrained generation. Paper 1 is innovative and applicable to traffic/autonomy, but is more domain-specific and appears to rely on a simplified scenario with less clear generalizable theoretical guarantees.
Paper 1 has higher likely impact because it targets a broadly used core paradigm (autoregressive decoding/conditioning in LLMs and generative audio/music) and formalizes widely encountered practical issues (approximate constrained generation) with clean hardness results that generalize across many constraints. Its conclusions directly affect how researchers interpret constrained decoding/sampling and motivate principled approximations, with immediate relevance given current LLM deployment. Paper 2 is rigorous and offers algorithms/experiments, but its scope is narrower to neurosymbolic constraint settings and specific shortcut notions.
Paper 1 addresses a fundamental theoretical question about the computational hardness of exact conditioning in autoregressive models (LLMs, music models), proving NP-hardness and #P-hardness results that formalize widely-held intuitions in the neural decoding literature. These results have broad implications across NLP, music generation, and constrained AI generation. Paper 2, while methodologically sound, is narrowly focused on a specific error pattern in GPT-5.4 for OWL 2 DL compliance queries—a niche intersection of prompt engineering and ontology reasoning with limited generalizability and audience.
Paper 1 addresses fundamental theoretical limitations of autoregressive models, proving computational hardness (NP-hard, #P-hard) for exact decoding and conditioning. Its insights into hidden inferential biases have broad implications for the foundation of modern generative AI, impacting NLP, machine learning, and AI theory at large. In contrast, Paper 2 presents a valuable but narrower applied system for STEM education. The foundational nature and broad applicability of Paper 1 across multiple AI domains give it a significantly higher potential scientific impact.
Paper 1 has higher potential impact because it formalizes a pervasive but under-theorized issue in modern constrained generation with autoregressive foundation models, proving broad hardness results (NP-hard MAP decoding; #P-hard exact conditioned normalization) that apply across LLMs, music models, and structured decoding under global constraints. The novelty is in rigorously characterizing “hidden inferential bias” as computational intractability, a timely and widely relevant insight for AI safety, evaluation, and decoding research. Paper 2 is methodologically strong and practically useful for POMDP deployment, but its impact is narrower to robust planning under observation-model misspecification.
Paper 1 provides fundamental theoretical results (NP-hardness, #P-hardness) about exact conditioning in autoregressive models, which are ubiquitous in modern AI. These complexity-theoretic proofs formalize widely-held intuitions and have broad implications across language modeling, music generation, and constrained decoding—affecting a huge research community. Paper 2 addresses an important applied problem in legal AI adjudication with a practical framework, but its contributions are more domain-specific. Paper 1's theoretical foundations will likely be cited more broadly and influence algorithmic design across multiple fields.
Paper 2 establishes fundamental theoretical limits (NP-hardness and #P-hardness) for exact decoding and conditioning in autoregressive models, which applies broadly across all generative AI domains (language, music, etc.). While Paper 1 offers a valuable applied framework for a specific legal use case, Paper 2 provides foundational mathematical guarantees that will durably impact the broader machine learning community's understanding of model inference.
Paper 1 (OLLM) introduces a novel, practical architectural method that addresses key challenges in LLM controllability and alignment through learned latent options. It demonstrates significant empirical improvements (51% to ~70%) with minimal parameter overhead, and offers a new paradigm for RL-based policy learning in latent space. Paper 2 provides valuable theoretical hardness results formalizing known intuitions about constrained decoding, but its impact is more confirmatory than transformative—it formalizes what practitioners already suspected. OLLM's combination of novelty, practical applicability, and opening a new research direction (latent-space policy learning) gives it broader potential impact.
Paper 2 has higher potential impact because it provides formal, broadly applicable complexity-theoretic results (NP-hardness and #P-hardness) about exact conditioning/decoding in autoregressive models under global constraints. This clarifies fundamental limits relevant across NLP, music generation, constrained decoding, and probabilistic inference, and is timely given widespread constrained generation methods. Paper 1 is an interesting, practical modeling tweak with promising math/alignability gains, but its impact is likely narrower and more benchmark/backbone-dependent, with less definitive methodological generality than Paper 2’s theoretical framing.
Paper 1 addresses a critical bottleneck in LLMs (long-context prefilling costs) with a practical, hardware-efficient, and training-free method. Such efficiency improvements typically see rapid adoption and drive significant follow-up research across NLP and multimodal fields. While Paper 2 offers valuable theoretical hardness proofs for constrained decoding, its impact is likely more confined to theoretical ML, whereas Paper 1 has immediate, broad, and scalable real-world applications.
Paper 2 has higher likely scientific impact: it formalizes a broad, under-theorized problem (hidden inferential bias in constrained generation) and provides general complexity-theoretic hardness results (NP-hard/#P-hard) that apply across domains (text, music, any autoregressive model). This yields durable, widely citable foundations that can shape decoding/conditioning research and clarify limits of current practice. Paper 1 is timely and important for AI safety/markets, but is more application-specific and dependent on particular experimental setups and prompting/optimization choices, which may narrow breadth and longevity.