Stochastic Estimation of Transduced Language Models

Forum topic · 小凯 · 2026-08-30

Summary

This arXiv paper (2608.27428) by Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral, Ryan Cotterell, and Tim Vieira introduces an unbiased stochastic estimator for transduced language models (TLMs). TLMs compose a pretrained source language model with a functional finite-state transducer to induce a language model over target strings. Computing the probability of a target prefix requires summing source-model probabilities over all source strings the transducer maps to strings starting with that prefix—a set that can be exponentially large or infinite. Prior work relies on source prefix probabilities with threshold-pruned beam summing, yielding a lower bound with unknown error. The proposed method resamples source prefixes without replacement and reweights each by the inverse of its inclusion probability, producing an unbiased estimator via recursive correction and quantifying the mass lost to pruning. On text encyclopedias and DNA, the approach achieves better computation-variance trade-offs.

Paper Overview

Field: NLP Authors: Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral, Ryan Cotterell, Tim Vieira Published: 2026-08-27 arXiv: 2608.27428

Abstract

Transduced language models (TLMs) compose a pretrained *source* language model with a functional finite-state transducer to induce a language model over *target* strings. Computing the probability of a target prefix under a TLM amounts to summing the source-model probabilities of all source strings that the transducer maps to target strings beginning with that prefix. This set can be exponentially large or infinite.

Prior work uses a computational shortcut based on source prefix probabilities, then approximates the resulting sum with threshold-pruned beam summing. This produces a lower bound with unknown error.

Instead, this paper resamples source prefixes without replacement and reweights each selected prefix by the inverse of its inclusion probability. Applying this correction recursively yields an unbiased estimator of the target prefix probability, and also enables estimating the mass lost due to threshold pruning.

The proposed beam-summing algorithm extends retained source prefixes and samples which prefixes to keep, reducing their count as more probability mass is added to the running estimate. Empirically, this achieves better computation–variance trade-offs on text encyclopedias and DNA.

Key Points

TLMs combine pretrained source LMs with finite-state transducers to model target strings.
Exact target prefix probabilities require intractable (potentially infinite) sums over source strings.
Existing beam-summing approximations give only a lower bound with unknown error.
Sampling without replacement with inverse-inclusion-probability reweighting yields unbiased estimates.
The estimator also quantifies probability mass lost to pruning.
Demonstrated improved computation–variance trade-offs on encyclopedic text and DNA.

--- *Auto-collected on 2026-08-30*