Learning Tractable Distributions of Language Model Continuations

Gwen Yidou-Weng, Ian Li, Anji Liu, Oliver Broadrick, Guy Van den Broeck, Benjie Wang · 2025

Read Learning Tractable Distributions of Language Model Continuations by Gwen Yidou-Weng, Ian Li, Anji Liu, Oliver Broadrick, Guy Van den Broeck, Benjie Wang (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-2511-16054.txt.

Introduction

Gwen Yidou-Weng, Ian Li, and five co-authors present Learning to Look Ahead, a hybrid method for controlling language model generation with exact future reasoning. Controlled generation must enforce sequence-level rules about syntax, style, or safety that depend on tokens not yet produced, making exact conditioning of an autoregressive model intractable. Hidden Markov model surrogates can answer future questions exactly but usually ignore context weakly.

Their design conditions a shared tractable surrogate on base model embeddings through a small neural head that sets only a latent prior per prefix. All next-token candidates are scored in one batched forward update, avoiding costly rescoring. Experiments improve continuation likelihood over standard surrogates and extend lookahead control to vision-language models.

Catalog record

CREATORGwen Yidou-Weng, Ian Li, Anji Liu, Oliver Broadrick, Guy Van den Broeck, Benjie Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-16054

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Tractable Distributions of Language Model Continuations Gwen Yidou-Weng, Ian Li, Anji Liu, Oliver Broadrick, Guy Van den Broeck, Benjie Wang Abstract Controlled language generation conditions text on sequence-level constraints (for example, syntax, style, or safety). These constraints may depend on future tokens, which makes directly conditioning an autoregressive language model (LM) generally intractable. Prior work uses tractable surrogates such as hidden Markov models (HMMs) to approximate the distribution over continuations and adjust the model’s next-token logits at decoding time. However, we find that these surrogates are often weakly context aware, which reduces query quality. We propose Learning to Look Ahead ( LTLA ), a hybrid approach that pairs the same base language model for rich prefix encoding with a fixed tractable surrogate model that computes exact continuation probabilities. Two efficiency pitfalls arise when adding neural context: (i) naïvely rescoring the prefix with every candidate next token requires a sweep over the entire vocabulary at each step, and (ii) predicting fresh surrogate parameters for each prefix, although tractable at a single step, forces recomputation of future probabilities for every new prefix and eliminates reuse. LTLA avoids both by using a single batched HMM update to account for all next-token candidates at once, and by conditioning only the surrogate’s latent state prior on the LM’s hidden representations while keeping the surrogate decoder fixed, so computations can be reused across prefixes. Empirically, LTLA attains higher conditional likelihood than an unconditional HMM, approximates continuation distributions for vision–language models where a standalone HMM cannot encode visual context, and improves constraint satisfaction at comparable fluency on controlled-generation tasks, with minimal inference overhead. 1 Introduction Autoregressive models are the dominant way to represent high-dimensional discrete distributions over language and sequence data ( 13 ; 31 ) , factorizing the distribution into a sequence of next-token conditional distributions. Many useful queries, however, concern properties of the entire sequence: to generate autoregressively under a sequence-level constraint, we need the probability that the remaining suffix will satisfy that constraint given the current prefix ( 3 ; 37 ) . Computing this probability requires reasoning over exponentially many possible futures and is therefore intractable for standard autoregressive language models (LM). In practice, estimates come from sampling ( 28 ; 15 ; 21 ) , which introduces significant computational overhead, or from learned heuristics ( 17 ; 35 ; 27 ) that must be tailored to each query or constraint. Tractable probabilistic models (TPMs) are a broad class of generative models that admit efficient routines for exactly computing such conditional queries exactly and efficiently ( 8 ) . As such, a natural approach employed by prior works ( 37 ; 36 ) is to utilize TPMs as tractable surrogates to the LM, such that queries on the LM can be approximated by computing them on the surrogate. However, we identify that current TPMs used for language modeling, such as hidden Markov models (HMM), face two significant obstacles in this setting. Firstly, we find empirically that HMMs are comparatively insensitive to the prefix, which yields less accurate distributions over continuations, as illustrated in Fig. 1 . Secondly, as models operating only over discrete sequences, they cannot effectively encode some kinds of context, notably continuous multimodal features used by modern vision–language models. To encode the past well and answer future queries quickly, we separate the two jobs. Understanding the past (“lookback”) should preserve as much information as possible, whereas forecasting the future (“lookahead”) must remain tractable. The same base LM already builds a rich representation of the prefix, which we reuse to encode the prefix into the tractable model (for example, a HMM) that models and computes exact probabilities over continuations. In short, we propose a hybrid tractable model where a transformer-based LM is used for lookback and a HMM for lookahead. (a) Standard HMM (b) Neural-Encoded HMM (LTLA) Figure 1: The encoder given by standard HMMs is often insensitive to information contained within the context. In this example, we show an example with the context they fired the <x> after just one , where <x> can be coach or employee . The distribution is almost identical for the standard HMM, while the neural HMM shows a significant shift in distribution (in particular, with season and game being more likely when <x> = coach ). Making this hybrid model practical raises two concrete challenges. First, when autoregressively generating the next token, a naïve strategy would run the transformer on the prefix concatenated with every candidate token across the vocabulary to assess how each affects the downstream conditional query; this per-step sweep over the entire vocabulary is expensive (see “Exhaustive LM Rescoring” in Table 1 ) . Second, conditioning the surrogate itself on the prefix by predicting fresh parameters for every context remains tractable at a single step but prevents reuse: as the prefix grows, the surrogate must be rebuilt and its future probabilities recomputed at every step, which increases decode-time cost and memory (see “Prefix-Parameterized TPM” in Table 1 ; cf. Sec. 3.1 ) . Both issues undercut the efficiency that makes TPMs attractive. Thus, we propose a solution that encodes rich context with the transformer while maintaining TPM efficiency by encoding the prefix only into the HMM surrogate’s latent prior and keeping the rest of the HMM fixed. Specifically, the transformer’s hidden states are fed into to a lightweight head that is trained to produce a prior over the surrogate’s latent state, and the observed next token x_{t} is incorporated with a one-step HMM update as a single batched matrix–vector operation, avoiding separate computation for each token in the vocabulary. With fixed transition and emission parameters, future computations are reusable across steps, so conditional queries remain exact and fast even for long sequence lengths (see “LTLA (Ours)” in Table 1 ) . We call this approach Learning to Look Ahead (LTLA) : it learns to injects context through the LM representation, while preserving tractability of the lookahead model. Our contributions can be summarized as follows: 1. We introduce LTLA, a novel approach for learning tractable surrogates to language models. LTLA reuses the base language model to predict the prior of a HMM modeling continuations given the current context, enabling accurate estimates of conditional queries at each time step of generation while only using a small number of matrix-vector multiplications. We further show how LTLA can be used to condition on multimodal context by leveraging vision-language models (VLM). 2. We propose different architectural choices for both the neural encoder and tractable decoder, and investigate their effect on modeling performance, decoding overhead, and downstream performance. 3. Empirically, we show that LTLA achieves improved conditional log-likelihood compared with existing tractable models, especially for the next few tokens. We also demonstrate the application of LTLA to controlled-generation tasks for both language and vision–language models, where LTLA improves constraint satisfaction compared to existing approaches while adding only a small inference-time overhead. Table 1: Comparison of lookahead properties across models. Model Tractable Lookahead Context Awareness (incl. multimodal) No Extra LM Calls per Step? Reuse Surrogate Precompute per Prefix? Decoding Overhead LLM ✗ ✓ — — — Standard HMM ✓ ✗ ✓ ✓ Low Exhaustive LM Rescoring ✗ ✓ ✗ ✓ High Prefix-Parameterized TPM ✓ ✓ ✓ ✗ High

Read the complete text