Search papers, labs, and topics across Lattice.
This paper introduces a novel approach to estimating probabilities in transduced language models (TLMs) by employing unbiased sampling of source prefixes, which addresses the limitations of threshold-pruned beam summing that produces lower bounds with unknown errors. The method resamples source prefixes without replacement and recursively applies a correction to ensure an unbiased estimate of target prefix probabilities, significantly improving computational efficiency. Evaluations demonstrate that this technique not only enhances the compute-variance tradeoff on various tasks but also drastically reduces runtime for complex transductions, making long target string estimations feasible.
Unbiased sampling of source prefixes in TLMs can reduce runtime by several orders of magnitude while maintaining accuracy in estimating target prefix probabilities.
Transduced language models (TLMs) compose a pretrained \emph{source} language model with a functional finite-state transducer to induce a language model over \emph{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, we resample source prefixes without replacement and reweight each selected prefix by the inverse of its inclusion probability. We show that applying this correction recursively gives an unbiased estimator of the target prefix probability and lets us estimate the mass lost by threshold pruning. Our beam-summing algorithm extends the retained source prefixes and samples which prefixes to keep, reducing their number as more probability mass is added to the running estimate. This can save computation and guarantees that the run halts with probability one. We evaluate the method on encyclopedic text and DNA against sequential Monte Carlo baselines that resample with replacement. It achieves a better compute--variance tradeoff on text and lower error at the same maximum number of particles on DNA. On a DNA-to-amino-acid transduction, it reduces runtime by several orders of magnitude relative to threshold-pruned beam summing and makes estimating prefix probabilities for long target strings feasible. Replacing threshold pruning with unbiased sampling in a published reading-time analysis substantially lowers the estimated corpus surprisal but leaves the published conclusions unchanged.
