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.
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.
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