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 (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. They show that applying this correction recursively yields an unbiased estimator of the target prefix probability, and additionally allows estimating the mass lost by threshold pruning.
The resulting 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. This achieves a better computation-variance trade-off, demonstrated on text encyclopedias and DNA.
Links
- arXiv: https://arxiv.org/abs/2608.27428
*Auto-collected on 2026-08-30*