Stochastic Estimation of Transduced Language Models: Unbiased Prefix Probability Estimation

Forum topic · 小凯 · 2026-08-29

Summary

This post summarizes arXiv paper 2508.11365 by Snæbjarnarson, Kiegeland, and de Prada Corral on stochastic estimation of 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, but computing target prefix probabilities requires summing over source string sets that can be exponentially large or infinite. Prior approaches use 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; applied recursively, this gives an unbiased estimator of target prefix probabilities. The beam summing algorithm progressively reduces the number of retained prefixes, saving computation and guaranteeing termination with probability one. Experiments on encyclopedic text and DNA show better computation-variance tradeoffs on text, lower error on DNA versus sequential Monte Carlo baselines, and orders-of-magnitude runtime reductions in DNA-to-amino-acid transduction. Applying unbiased sampling to published reading-time analyses lowers estimated corpus surprisal, though prior conclusions hold.

Paper Overview

Field: NLP
Authors: Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral
Published: 2026-08-28
arXiv: 2508.11365

Summary (Translated)

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, the authors 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 and allows estimating the quality of the loss from threshold pruning. Their beam summing algorithm extends retained source prefixes and samples which prefixes to keep, reducing their number as more probability mass is added to the running estimate — saving computation and guaranteeing termination with probability one.

Key Results

Evaluated on encyclopedic text and DNA, compared against a sequential Monte Carlo baseline with resampling.
Achieves a better computation-variance tradeoff on text; lower error on DNA at the same maximum particle count.
In one DNA-to-amino-acid transduction task, runtime is reduced by several orders of magnitude relative to threshold-pruned beam summing, making prefix probability estimation feasible for long target strings.
Replacing threshold pruning with unbiased sampling in published reading-time analyses significantly lowers estimated corpus surprisal, but the published conclusions remain unchanged.

---

*Auto-collected on 2026-08-29. Original post in Chinese via zhichai.net.*