On Importance Sampling-Based Evaluation of Latent Language Models

Robert L. Logan Iv, Matt Gardner, Sameer SinghACL 2020 · DOI · OpenReview

Abstract

Evaluating language models with latent structures—such as syntax trees, coreference chains, or knowledge graphs—is notoriously difficult because calculating exact likelihoods is mathematically intractable. This paper provides a rigorous analysis of Importance Sampling (IS) for this task. We prove that IS estimates serve as stochastic upper bounds of true perplexity and offer a definitive set of best practices to ensure fair and reproducible model comparisons. Our findings reveal that choices in sample size, proposal distributions, and data aggregation significantly shift reported metrics, often leading to underestimates of model potential in existing literature.

Introduction: The Challenge of Latent Structure Evaluation

Traditional language models predict the next token based solely on observed history. In contrast, "latent" language models (LLMs) jointly model text and underlying structures, such as syntactic parses (RNNG), coreference chains (EntityNLM), or links to external knowledge bases (KGLM).

The primary hurdle for LLMs is evaluation. Calculating a model's perplexity—the standard metric for sequence prediction—requires "marginalizing out" the latent variables, which involves summing over an exponential number of possible structures. Since exact calculation is impossible for sequences of non-trivial length, researchers rely on Importance Sampling (IS) to estimate these values. However, the field has lacked a systematic understanding of how IS parameters affect the reliability of these estimates.

Methodology

We evaluate three prominent latent language models: RNNG, EntityNLM, and KGLM. Our analysis focuses on several key mechanics of Importance Sampling:

  1. Importance Sampling (IS): Estimating total probability by sampling structures from a "proposal distribution" and weighting them appropriately.
  2. Peeking vs. Non-Peeking: Comparing proposal distributions that "peek" at future words to ensure consistency versus those that do not.
  3. Aggregation Levels: Comparing instance-level aggregation (averaging probabilities per sentence/document) versus corpus-level aggregation (averaging across the entire dataset).
  4. Beam Marginalization: A deterministic alternative using beam search to sum over the top-$k$ most likely structures.

Key Insights and Theoretical Contributions

The "Stochastic Upper Bound" Proof

A central contribution of this work is the theoretical proof, derived via Jensen's Inequality, that importance-sampled perplexity estimates are always greater than or equal to the true perplexity. This establishes that IS estimates are conservative; a low estimated perplexity implies that the model's true performance is likely even better.

The Impact of Aggregation

Aggregation granularity significantly shifts results. For instance, in the KGLM model, switching from corpus-level to instance-level aggregation dropped the estimated perplexity from approximately 42 to 30. This massive improvement highlights how sensitive evaluation metrics are to the underlying mathematical treatment of the estimate.

No Convergence in Sight

Perhaps the most surprising finding is that perplexity estimates continue to decrease even at very high sample counts. Most reported results in the literature use around 100 samples, yet our experiments show that even 10,000 samples do not reach a plateau.

Perplexity estimates for ENTITYNLM continue to decrease significantly as the sample size increases up to 10,000, suggesting that typical sample sizes are insufficient for convergence.

Experimental Results

Our results demonstrate that increasing sample size and tuning the proposal distribution are critical for accurate evaluation.

Comparison of perplexity estimates across RNNG, ENTITYNLM, and KGLM models as a function of sample size and proposal temperature.
  • Sample Size: Increasing samples from 100 to 1,000 typically dropped perplexity by several points across all models.
  • Temperature Scaling: Increasing the entropy of the proposal distribution by scaling logits with a temperature parameter ($\tau > 1.0$) generally yielded tighter (lower) bounds.
  • Beam Search vs. Sampling: While beam marginalization provided tight bounds for RNNG (which has a smaller latent space), it performed poorly for models with complex, sparse latent structures like EntityNLM and KGLM.

Conclusion and Future Work

This study underscores that current evaluation practices for latent language models likely underestimate their true performance due to insufficient sampling and inconsistent aggregation. While more samples lead to better estimates, the computational cost remains a significant barrier. Future research should focus on developing more powerful proposal distributions that incorporate broader document context and exploring techniques like annealed importance sampling to find even tighter bounds on perplexity.

Summary updated

BibTeX
@inproceedings{iv2020importance,
  author = {Robert L. Logan IV and Matt Gardner and Sameer Singh},
  title = {{On Importance Sampling-Based Evaluation of Latent Language Models}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.18653/v1/2020.acl-main.196},
}
Figure