Stochastic Estimation of Transduced Language Models

Forum topic · 小凯 · 2026-08-29

Summary

This paper, posted on the zhichai.net forum (arXiv:2508.11365, NLP), introduces an unbiased stochastic estimator for transduced language models (TLMs). TLMs compose a pretrained source language model with a finite-state transducer to induce a language model over target strings; computing the probability of a target prefix requires summing over all source strings mapped to that prefix, a set that can be exponentially large or infinite. Prior threshold-pruned beam summing yields only a lower bound with unknown error. The authors instead resample source prefixes without replacement, reweighting each by the inverse of its inclusion probability, which recursively yields unbiased estimates of target prefix probabilities and quantifies the error of pruning. Their beam-summing variant reduces the number of retained prefixes as probability mass accumulates, saving computation and guaranteeing termination with probability one. Evaluated on encyclopedic text and DNA against sequential Monte Carlo baselines, it achieves better computation-variance trade-offs on text and lower error on DNA, and in a DNA-to-amino-acid transduction reduces runtime by orders of magnitude, making long target strings feasible. Replacing pruning with unbiased sampling in reading-time analyses lowered corpus surprise estimates, though published conclusions held.

This forum post shares the paper Stochastic Estimation of Transduced Language Models (arXiv: 2508.11365) by Vésteinn Snæbjarnarson, Samuel Kiegeland, and Manuel de Prada Corral. Posted 2026-08-28, NLP.

Background

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 — a set that can be exponentially large or infinite. Prior work approximates this sum with threshold-pruned beam summing, producing a lower bound with unknown error.

Method

Resample source prefixes without replacement and reweight each selected prefix by the inverse of its inclusion probability.
Applying this correction recursively yields an unbiased estimator of target prefix probabilities.
The estimator also quantifies the quality lost by threshold pruning.
The beam-summing variant shrinks the set of retained prefixes as probability mass is added to the running estimate, saving computation and guaranteeing termination with probability one.

Results

Evaluated on encyclopedic text and DNA, compared against sequential Monte Carlo baselines with resampling with replacement.
Better computation–variance trade-off on text; lower error on DNA at the same maximum particle count.
In a DNA-to-amino-acid transduction, runtime is reduced by orders of magnitude relative to threshold-pruned beam summing, making prefix probability estimation for long target strings feasible.
In a published reading-time analysis, replacing pruning with unbiased sampling significantly lowers the estimated corpus surprise, but the published conclusions remain unchanged.