Predictive Querying for Autoregressive Neural Sequence Models

Alex James Boyd, Sam Showalter, Stephan Mandt, Padhraic Smyth

Abstract

Autoregressive neural sequence models are highly effective at next-token prediction but struggle with "predictive querying"—estimating the probability of complex future events. This difficulty arises from the need to marginalize over an exponentially large space of possible future sequences. We present a general framework for answering these queries by combining beam search with importance sampling. Our hybrid estimator leverages beam search to identify high-probability "heavy hitters" and importance sampling to estimate the remaining probability mass, providing a tractable and low-variance solution across diverse domains.

Introduction

Modern sequence models, such as Transformers and RNNs, are typically trained to predict the immediate next token in a sequence. While they excel at this task, many real-world applications require reasoning about events multiple steps into the future. For instance, in clinical settings, one might query the probability of a specific symptom appearing within a certain timeframe. In natural language processing, a relevant query might be the probability of a sentence concluding within the next few tokens.

Predictive querying overview: The top diagram illustrates a query for the probability of a sentence ending (<EOS>) at step K. The bottom histograms show the resulting probability distributions for different natural language prompts.

The fundamental challenge in predictive querying is marginalization. Calculating the probability of a future event requires summing the probabilities of every valid sequence of intermediate tokens. Given a vocabulary $V$ and a query horizon $K$, the number of possible paths grows as $O(V^K)$, making exact computation impossible for even modest horizons in models like GPT-2.

Methodology

To address the intractability of marginalization, we propose a three-part framework:

1. Query Formalization

We define a typology of queries based on "elementary building blocks." This allows for the formalization of complex conditions, such as "Event A occurs before Event B" or "Event C occurs exactly $n$ times," as sets of restricted path spaces.

2. Constrained Proposal Distributions

To efficiently estimate query probabilities, we develop constrained proposal distributions. By renormalizing the model's output at each step to exclude tokens that would violate the query constraints, we "force" the model to only sample sequences that satisfy the query.

A tree diagram illustrating the constrained path space for a query where event 'a' must occur at exactly step 3. Solid lines represent valid paths, while dotted lines represent paths excluded by the constraint.

3. The Hybrid Estimator

The core of our approach is a hybrid estimator that combines the strengths of search and sampling:

  • Beam Search (BS): Greedily identifies the most likely paths to provide a deterministic lower bound on the query probability.
  • Importance Sampling (IS): Uses the constrained proposal to provide an unbiased estimate of the total probability.
  • Hybrid Approach: Uses beam search to capture the "head" of the distribution (high-probability sequences) and importance sampling to estimate the "long tail."

Experiments and Results

We evaluated the framework across five domains: Amazon product reviews, Android app usage, MOOC student interactions, character-level Shakespeare modeling, and word-level WikiText modeling using GPT-2.

The hybrid method consistently outperformed pure beam search and pure importance sampling. In high-entropy settings like natural language, beam search often fails to capture significant probability mass as the query horizon increases. Conversely, while importance sampling is unbiased, it can suffer from high variance. The hybrid approach mitigates these issues, providing a significant reduction in variance—up to 6x in GPT-2 experiments—compared to naive sampling.

Discussion and Insights

The effectiveness of different estimation strategies is closely linked to the model's entropy. In low-entropy scenarios where the model is highly certain, beam search is often sufficient. However, in the "heavy-tailed" distributions typical of natural language, the hybrid approach is essential for capturing the full range of probable outcomes.

While our framework provides a robust solution for predictive querying, it relies on the underlying model being well-calibrated. Future work includes scaling these methods to even larger state spaces and exploring amortized models trained specifically to answer queries.

Summary updated

Abstract

In reasoning about sequential events it is natural to pose probabilistic queries such as “when will event A occur next” or “what is the probability of A occurring before B”, with applications in areas such as user modeling, language models, medicine, and finance. These types of queries are complex to answer compared to next-event prediction, particularly for neural autoregressive models such as recurrent neural networks and transformers. This is in part due to the fact that future querying involves marginalization over large path spaces, which is not straightforward to do efficiently in such models. In this paper we introduce a general typology for predictive queries in neural autoregressive sequence models and show that such queries can be systematically represented by sets of elementary building blocks. We leverage this typology to develop new query estimation methods based on beam search, importance sampling, and hybrids. Across four large-scale sequence datasets from different application domains, as well as for the GPT-2 language model, we demonstrate the ability to make query answering tractable for arbitrary queries in exponentially-large predictive path-spaces, and find clear differences in cost-accuracy tradeoffs between search and sampling methods.
BibTeX
@inproceedings{boyd2022predictive,
  author = {Alex James Boyd and Sam Showalter and Stephan Mandt and Padhraic Smyth},
  title = {{Predictive Querying for Autoregressive Neural Sequence Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=mhe2C2VWwCW},
}
Figure