TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation
Gwen Yidou-Weng*, Benjie Wang*, Guy Van den Broeck · 2025
Read TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation by Gwen Yidou-Weng*, Benjie Wang*, Guy Van den Broeck (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18535.txt.
Introduction
Gwen Yidou Weng, Benjie Wang, and Guy Van den Broeck steer language model output with exact probability math in this 2025 paper. Users want text that fits set traits, like safe tone or a chosen topic. Models that write word by word struggle to honor such whole-text traits.
Older fixes retrain the model per trait or guess future trait odds by sampling, which is slow and shaky for rare traits. Their framework, TRACE, computes those odds exactly with tractable reasoning circuits. New traits can be added without retraining. Control becomes faster and more reliable. The work joins logic-based reasoning with fluent generation.
Catalog record
| CREATOR | Gwen Yidou-Weng*, Benjie Wang*, Guy Van den Broeck |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18535
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation Gwen Yidou-Weng*, Benjie Wang*, Guy Van den Broeck Abstract As large language models (LMs) advance, there is an increasing need to control their outputs to align with human values (e.g., detoxification) or desired attributes (e.g., personalization, topic). However, autoregressive models focus on next-token predictions and struggle with global properties that require looking ahead. Existing solutions either post-train LMs for each new attribute—expensive and inflexible—or approximate the Expected Attribute Probability (EAP) of future sequences by sampling or training, which is slow and unreliable for rare attributes. We introduce TRACE ( T ractable Probabilistic R easoning for A daptable C ontrollable g E neration) 1 1 1 Our code is available at: https://github.com/yidouweng/trace , a novel framework that efficiently computes EAP and adapts to new attributes through tractable probabilistic reasoning and lightweight control . TRACE distills a Hidden Markov Model (HMM) from an LM and pairs it with a small classifier to estimate attribute probabilities, enabling exact EAP computation over the HMM’s predicted futures. This EAP is then used to reweigh the LM’s next-token probabilities for globally compliant continuations. Empirically, TRACE achieves state-of-the-art detoxification results with only 20% decoding overhead, yields 76 low-resource personalized LMs within seconds, and seamlessly extends to composite attributes. † † affiliationnotice: Equal contribution 1 Introduction 0 (toxic) 1 (nontoxic) Attribute Probability It’s a pain in future text p_{\textit{hmm}}(x_{>t}\mid x_{\leq t}) the ass 0.3 the butt 0.15 the neck 0.05 … … … … \textit{EAP}=0.1 p_{lm}=\textbf{0.3} \times = p_{\textit{TRACE}}\propto 0.03 to future text p_{\textit{hmm}}(x_{>t}\mid x_{\leq t}) deal with 0.2 handle 0.1 … … … … \textit{EAP}=0.8 p_{lm}=0.1 \times = p_{\textit{TRACE}}\propto\textbf{0.08} Figure 1 : TRACE reweighs LM next token probabilities by “lookahead,” computing the Expected Attribute Probability (EAP), \sum_{x_{>t}}p(s\mid x_{\leq t},x_{>t})\cdot p_{\textit{hmm}}(x_{>t}\mid x_{\leq t}) , using an HMM to tractably compute the expectation of a probabilistic classifier s . As large language models (LMs) become more ubiquitous in commercial products and daily life, there is a growing need to control their outputs. There is a large body of research in LM alignment with objectives such as detoxification ( Gehman et al., 2020 ; Xu et al., 2021 ) , where abundant data and benchmarks exist. Meanwhile, there is growing interest involving specialized or personal attributes under low-data conditions ( Adiwardana et al., 2020 ; Xu et al., 2021 ) , as well as compositional attributes for creating complex or novel outputs that rarely appear during standard training ( Liu et al., 2022 ) . Controllable text generation is challenging because most language models are autoregressive, generating each token solely from its predecessors without looking ahead—yet many attributes depend on the entire text. One line of solutions modifies the base model’s distribution via fine-tuning or post-training (e.g., RL, RLHF) ( Gururangan et al., 2020 ; Rafailov et al., 2023 ; Schulman et al., 2017 ) , but these approaches can be highly expensive and risk degrading fluency or diversity ( Kumar et al., 2022 ) . Thus, there is a need for more lightweight solutions that can directly leverage pre-trained LMs by changing the decoding strategy. Fundamentally, we argue that decoding-based controllable generation is a probabilistic reasoning task: we wish to sample from the language model’s distribution conditional on some attribute . For example, some approaches utilize sampling to find attribute-consistent generations ( Yang & Klein, 2021 ; Tu et al., 2024 ; Chakraborty et al., 2024 ; Mudgal et al., 2024 ) , but this can be computationally expensive. Other methods train expensive LM-based discriminators to predict satisfaction of an attribute given a partial text sequence ( Krause et al., 2021 ; Meng et al., 2022 ; Liu et al., 2021 ) , but this requires large amounts of data and training time. Both struggle with rare attributes due to limited data and high variance. In this work, we propose a framework for controllable generation that utilizes tractable models to approximate the probability of satisfying an attribute given a partial sequence. This approach avoids costly sampling methods and retraining the base language model (LM) for each target attribute. First, we perform a one-time distillation of a tractable Hidden Markov Model (HMM) to approximate the base LM. Next, for each desired attribute, we train a log-linear classifier to estimate the probability of satisfying a target attribute given the entire text. During decoding, we use Bayesian conditioning to reweight next-token probabilities based on the likelihood that future sequences—predicted by the HMM—comply with these attributes, which we refer to as Expected Attribute Probability (EAP) (Figure 1 ). Crucially, the combination of the tractable HMM and log-linear classifier enables us to compute EAP over all of the exponentially many future sequences efficiently and exactly (over the HMM state space). Our method, T ractable probabilistic R easoning for A daptable C onstrained g E neration ( TRACE ), constitutes a uniquely lightweight solution that enforces control with almost zero decoding-time overhead over the base LM. It further decouples generative model training from control , eliminating the need to retrain the LM or HMM for new objectives. Adapting to novel or rare attributes merely requires training a small classifier in seconds. Handling compositions of attributes is also straightforward by multiplying the EAP of each attribute during decoding. We evaluate TRACE on three important tasks: (1) Detoxification : TRACE outperforms expensive RL, training- and sampling-based baselines on GPT2-large and Gemma 2B. (2) Personalized LLMs : TRACE adapts to 76 distinct characters in about three seconds each, outperforming prompting approaches with only a few hundred training samples, and taking only \sim 1.2\times time per-token to standard decoding. (3) Compositional Attributes : TRACE seamlessly generates texts satisfying multiple attributes–e.g. political and nontoxic –a combination too sparse for training or sampling methods. Overall, TRACE is a simple, lightweight controllable generation approach that achieves state-of-the-art detoxification performance, extends to low-resource and composite text generation, and scales well to modern LLMs. 2 Related Work Controllable text generation methods fall into two main categories: those that modify the language model (LM) via training, and those that steer a pre-trained model through decoding-time interventions. 2.1 Training Methods One line of approaches modifies the base LM parameters, typically through fine-tuning or reinforcement learning , to instill desired attributes directly into the model’s distribution. DAPT ( Gururangan et al., 2020 ) fine-tunes the base LM on domain-specific data. PPO ( Schulman et al., 2017 ) uses a reward model and policy gradients to fine-tune the LM towards desired behaviors like non-toxicity, while DPO ( Lee et al., 2024 ) aligns the model using pairwise preferences without an explicit reward model. Similarly, Quark ( Lu et al., 2022 ) uses an RL-like procedure conditioned on a learned reward token. A major drawback of these methods is the need for substantial data and costly retraining of the large LM for each new attribute or set of attributes. Furthermore, modifying the base LM risks degrading its general fluency and diversity ( Kumar et al., 2022 ) . 2.2 Decoding Methods An alternative direction focuses on modifying the decoding process of a fixed, pre-trained LM to steer generation towards desired attributes, often by incorporating an estimate of the Expected Attribute Probability (EAP) of future text. Training