PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Estimation of Transduced Language Models

Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral, Ryan Cotterell, Tim Vieira

arXiv:2608.27428v1cs.CL

TL;DR

Target-prefix probabilities in transduced language models can require summing over exponentially large or infinite source-string sets, while threshold-pruned beam summing gives a lower bound with unknown error. The paper uses recursively reweighted sampling without replacement to obtain unbiased estimates and quantify pruning loss. Experiments show better efficiency or accuracy than with-replacement baselines and make long DNA-to-amino-acid prefix estimation feasible, although infinite decompositions require the almost-sure-halting mechanism.

  • Problem

    Threshold-pruned beam summing can be too expensive when mass is spread across many prefixes, and its pruning error is unknown.

  • Method

    The method samples distinct source prefixes without replacement, reweights them by inverse inclusion probability, and adaptively reduces retained particles as estimated mass accumulates.

  • Results

    The method improves the compute–variance tradeoff on encyclopedic text, lowers DNA error at equal maximum particle count, and reaches target position 200 in about five seconds versus over five minutes at position 13 for threshold-pruned beam summing.

  • Takeaways & Limitations

    Unbiased sampling provides a reference for estimating threshold-pruning error and makes long-target prefix probability estimation feasible in the DNA-to-amino-acid setting.

  • Takeaways & Limitations

    Without adaptive sampling, an infinite quotient–remainder decomposition can make beam enumeration fail to halt, even as path weights decay toward zero.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Transduced language models compute target-prefix probabilities by summing source-model mass over potentially enormous or infinite source-string sets. This work replaces threshold pruning with unbiased sampling, enabling error estimation and improved feasibility on challenging transductions.

  • Motivation: Target-prefix probability sums source-model probabilities over all source strings whose transduced outputs begin with the target prefix.This potentially exponential or infinite set is the target prefix’s precover.
  • Prior approach: Prior beam summing uses source-prefix probabilities and threshold pruning, producing a lower bound whose discarded mass is not quantified.It can work when relevant mass is concentrated in relatively few prefixes.
  • Method: Resampling distinct prefixes without replacement and inverse-inclusion reweighting replaces deterministic threshold pruning while preserving prefix weight in expectation.The method also reduces retained prefixes as accumulated mass grows.
  • Guarantees: Recursive reweighting yields an unbiased target-prefix estimator when runs halt with probability one, while repeated runs estimate sampling variation and pruning mass loss.The difference between unbiased estimates and threshold-pruned values estimates discarded mass.
  • Evaluation: On text, sampling without replacement improves the compute–variance tradeoff over SMC baselines; on DNA, it achieves lower error at the same maximum particle count.DNA-to-amino-acid estimation reaches target position 200 in about five seconds, while threshold-pruned beam summing exceeds five minutes at position 13.

2 BACKGROUND

The paper formalizes language models as distributions over finite strings and transduced language models as source models composed with deterministic transducers. It defines the precover and its quotient–remainder decomposition used for computation.

  • 2.1 LANGUAGE MODELS: An alphabet is a symbol set, and X* denotes the set of all finite strings over alphabet X.
  • 2.1 LANGUAGE MODELS: A language model pX is a distribution over X*, with prefix probabilities and conditional prefix probabilities defined through sequence probabilities.The model includes a special end-of-sequence symbol EOS.
  • 2.2 TRANSDUCED LANGUAGE MODELS: A transduced language model pY is characterized by a source language model pX and a transducer encoding a function from source strings X* to target strings Y*.
  • 2.2 TRANSDUCED LANGUAGE MODELS: The precover P(y) contains source strings whose transducer outputs cover target string y, and its predicates classify prefixes as live, members, or cylinders.Live prefixes have some extension covering y; members already cover y; cylinders have every extension covering y.
  • 2.2 TRANSDUCED LANGUAGE MODELS: The quotient–remainder decomposition partitions the precover into cylinder contributions and remainder elements, allowing each source string to be counted exactly once.Finite-state transducers make the semantic predicates computable through lazy determinization.

3 UNBIASED ESTIMATION OF TRANSDUCED LANGUAGE MODELS

The method replaces lossy threshold pruning in TLM beam summing with without-replacement sampling and inverse-inclusion-probability reweighting. Recursive correction preserves unbiasedness, while adaptive particle budgets reduce computation and guarantee almost-sure halting under the live twist.

  • Motivation: Threshold-pruned beam summing can discard positive covering mass, yielding a biased estimate whose pruning error is unknown.The problem becomes acute when relevant mass is distributed across many similarly weighted prefixes.
  • Stochastic pruning: SWOR samples distinct source-prefix survivors using weight-based inclusion probabilities and Horvitz–Thompson reweighting.The existing beam-summing decomposition and quotient–remainder contributions remain unchanged.
  • Adaptive budget: Adaptive-budget SWOR decreases the live-particle count as the running estimate grows, saving computation while preserving unbiasedness.The count is fixed before each random draw, and Proposition 3.4 gives almost-sure halting under the live twist.
  • Unbiasedness: Theorem 3.3 establishes an unbiased target-prefix estimator when the recursive run halts, because pruning preserves pool weights in expectation.The stochastic pruning functions satisfy the theorem’s expected-weight condition through Horvitz–Thompson reweighting.
  • Halting: Fixed-particle methods may run forever on infinite decompositions, whereas adaptive-budget SWOR halts the illustrated infinite-path example on its own.The example retains a live continuation indefinitely under fixed M even though its weight decays to zero.

4 EXPERIMENTS

The experiments evaluate unbiased sampling estimators against threshold-pruned beam summing and with-replacement SMC across text, GPT-2, and DNA transductions. Results show lower error or better compute–variance tradeoffs for sampling, with especially large gains on DNA and unchanged reading-time conclusions.

  • 4.3 TRANSDUCING DNA LANGUAGE MODELS: Position 200 in about five seconds: beam_swor_adaptive reached this DNA target position, whereas threshold-pruned beam summing exceeded five minutes at position 13.Beam_swor_adaptive scaled approximately linearly while beam_summing runtime grew rapidly within a dozen amino acids.
  • Experimental setup: The experiments compare four unbiased estimators with threshold-pruned beam summing and distinguish SMC resampling from without-replacement beam methods.The comparison separates EOS marginalization from extending every live child and pruning without replacement.
  • 4.1 BYTE-TO-WORD TRANSDUCTION ON REAL TEXT: 0.17 and 0.21 corpus relative RMSE were achieved by beam_swor and beam_swor_adaptive at their largest tested particle counts.Their between-seed standard deviations were 57× and 49× below smc_simple’s, respectively.
  • 4.2 COMPARING COMPUTE–VARIANCE FRONTIERS: 772 seconds versus 1224 seconds: beam_swor_adaptive was faster than threshold-pruned beam summing on GPT-2 transduced with fptb.At matched walltime on the bigram setting, its standard deviation was nearly three times lower than beam_swor’s.
  • 4.2 COMPARING COMPUTE–VARIANCE FRONTIERS: The unbiased GPT-2 estimators converged to a common value, while the threshold-pruned lower bound was 2.0 nats lower on a paragraph and approximately 33 nats lower on the corpus.At the largest tested particle count, smc_rb and beam_swor_adaptive agreed within 0.5 nats on the paragraph.
  • 4.5 PSYCHOLINGUISTICS: SURPRISAL FOR READING-TIME PREDICTION: 106 nats lower: replacing threshold pruning reduced estimated corpus surprisal, but produced no predictive difference in any reading-time measure.The one-sided p-values for predictive differences were at least 0.068 in both directions, and contextual surprisal improved held-out prediction under either estimator.

5 CONCLUSION

The paper replaces threshold pruning with unbiased sampling without replacement, preserving computability while estimating pruning error and guaranteeing almost-sure termination. In DNA-to-amino-acid transduction, this makes much longer target-prefix estimation feasible.

  • 5 CONCLUSION: The method replaces threshold pruning with weight-proportional sampling without replacement and Horvitz–Thompson reweighting.The adaptive version uses the current running estimate to set its particle count and retains the beam-summing enumeration and per-position estimate.
  • 5 CONCLUSION: The resulting estimator is unbiased, replaces unknown pruning error with sampling variance, and halts almost surely under the live twist.These properties follow from the recursive reweighting and adaptive-budget roulette rule.
  • 5 CONCLUSION: The work applies to target-prefix probability estimation for pretrained source models composed with deterministic transformations.The same estimator provides an unbiased reference for estimating threshold-pruning error.
  • 5 CONCLUSION: Figure 10’s sequential Monte Carlo baseline extends M particles under a proposal, applies incremental weights and an EOS potential, then uses ESS-gated multinomial resampling with replacement.The resampling step resets particle weights to their mean.

B.1 PROOFS FOR THE SWOR ESTIMATOR

The proof establishes that recursive pruning preserves source-prefix contributions in expectation, so beam_summing with a valid prune yields an unbiased target-prefix probability estimator when the run halts almost surely.

  • B.1 PROOFS FOR THE SWOR ESTIMATOR: The optimal twist recursively assigns each prefix the source mass of completions that cover the target string.For a cylinder prefix the twist is one; otherwise it combines immediate membership with live-child continuation probabilities.
  • B.1 PROOFS FOR THE SWOR ESTIMATOR: Lemma 3.2 states that any prune satisfying Eq. (13) preserves the unpruned pool weight at every iteration and source prefix.This is the induction invariant used by the unbiasedness proof.
  • B.1 PROOFS FOR THE SWOR ESTIMATOR: The induction proceeds over target-prefix length and within-call source-extension iterations.The base case starts from the empty prefix, and each next-pool prefix is formed by appending one source symbol.
  • B.1 PROOFS FOR THE SWOR ESTIMATOR: Theorem 3.3 concludes unbiasedness when every prune preserves expected pool weight and the run halts almost surely.The target-prefix estimate follows by summing the preserved contributions through the final target position.
  • B.1 PROOFS FOR THE SWOR ESTIMATOR: The proof tracks quotient extensions and remainder entries separately, showing that both retain their reference contributions in expectation.Quotient entries are extended through the beam, while remainder entries pass the target re-check unchanged.

B.2 PROOF FOR ADAPTIVE-BUDGET SWOR

The adaptive-budget proof shows that roulette handling of small expected budgets preserves weight in expectation and, under the live twist, guarantees almost-sure termination and unbiased estimates at every target position.

  • B.2 PROOF FOR ADAPTIVE-BUDGET SWOR: Proposition 3.4 shows that every adaptive-budget prune satisfies Eq. (13), and that the full live-twist run halts almost surely.Consequently, the estimator equals the target-prefix probability in expectation at every position.
  • B.2 PROOF FOR ADAPTIVE-BUDGET SWOR: When the budget is at least one, the prune either keeps all positive-weight particles or samples the required number without replacement using inclusion probabilities and Horvitz–Thompson reweighting.Zero-weight particles can be removed without changing source-prefix weights.
  • B.2 PROOF FOR ADAPTIVE-BUDGET SWOR: When the rounded particle budget is zero but retained weight is positive, roulette survives with probability equal to the fractional budget and rescales weights by its inverse.This avoids deterministically discarding positive weight and preserves Eq. (13).
  • B.2 PROOF FOR ADAPTIVE-BUDGET SWOR: The halting proof bounds survival through successive prunes and shows that the probability of surviving indefinitely is zero.It conditions on each finite starting pool and applies induction over target-prefix length.
  • B.2 PROOF FOR ADAPTIVE-BUDGET SWOR: In the SMC comparison, effective sample size detects unequal weights, while multinomial resampling duplicates higher-weight particles and discards lower-weight ones.The with-replacement construction preserves weighted sums conditionally in expectation under its support and halting assumptions.

B.4 INTERMEDIATE TARGETS AND THE smc_rb ALGORITHM

The smc_rb algorithm performs sequential importance sampling over target and source steps, using intermediate live-target distributions and a proposal restricted to source symbols that can still cover the target.

  • B.4 INTERMEDIATE TARGETS AND THE smc_rb ALGORITHM: The live-set proposal is computable at every step, unlike the optimal twist, which requires the full covering mass ahead.Its limitation is that it does not reveal how much covering mass remains, so particles may look promising early but later carry little weight.
  • B.4 INTERMEDIATE TARGETS AND THE smc_rb ALGORITHM: smc_rb combines one target-step factor with one source-step factor for every sampled source symbol within a target-recursion call.A particle can traverse multiple source symbols while advancing one target position.
  • B.4 INTERMEDIATE TARGETS AND THE smc_rb ALGORITHM: The live twist sets ψ_t(x) to one for surviving particles and restricts proposals to source symbols that remain live.The resulting conditional proposal keeps every particle live for the current target prefix by construction.
  • B.4 INTERMEDIATE TARGETS AND THE smc_rb ALGORITHM: The sampled particle’s weight equals the sum of its parent’s live-child weights.This simplification follows from conditioning the proposal on drawing a live next source symbol.
  • B.4 INTERMEDIATE TARGETS AND THE smc_rb ALGORITHM: Quotient particles are retained when they remain live and dropped when the target-step factor becomes zero, while completed remainder entries are rechecked for membership.Together these operations implement the recursive target update.

B.5 UNBIASEDNESS OF smc_rb

The smc_rb proof establishes unbiasedness by matching sampled-extension conditional expectations to the prune-free beam-summing recursion, assuming expected-weight-preserving pruning and almost-sure termination.

  • smc_rb is unbiased when every prune preserves the pool’s expected weight and the run halts almost surely.Under these conditions, E[ˆZ|y|] = p⃗Y(y).
  • Sampled symbol extensions preserve the corresponding source-prefix contribution in conditional expectation.For a live prefix x and child x′, the expected contribution is w p⃗X(x′ | x).
  • Zero-twist children and zero-twist prefixes contribute no weight under either the sampled or exhaustive extension.
  • The proof assembles the sampled-extension identity, stop-decision marginalization, re-queuing, and the beam-summing theorem to obtain unbiasedness.
  • The ESS-gated multinomial resample satisfies the expected-weight condition for every fixed input pool.

B.6 A COMMON TAIL-ROULETTE PRUNE

The tail-roulette decorator preserves particle weights in expectation while forcing fixed-cap pruning runs to halt almost surely, including recursive algorithms.

  • Tail roulette independently removes sufficiently light particles with probability 1/2 and doubles their weight otherwise.
  • The decorator preserves each particle’s weight in conditional expectation and therefore preserves total expected weight when the original prune does.
  • A fixed cap of M particles gives the coin flips conditional probability at least 2^-M of emptying the pool once weights are sufficiently small.
  • The probability that the pool remains nonempty at every iteration converges to zero, so decorated calls halt almost surely.
  • The decorator uses κ to delay roulette until particle weights are small relative to their reference weights; beam_swor_adaptive does not require it.The experiments use κ = e^-15 for WikiText and κ = e^-30 for DNA and MECO.

C SENSITIVITY TO PRUNING PARAMETERS

Pruning parameters trade computation against sampling variability, while exact finite-state ground-truth calculations are tractable for n-gram sources but not neural language models.

  • Sensitivity to ρ: At nominal M=8000, reducing ρ from 1 to 0.02 lowers standard deviation from 0.711 to 0.073 nats and raises time per seed from 349 to 1551 seconds.The default ρ=0.1 gives 0.200 nats at 623 seconds; plain beam_swor at M=2000 gives 0.170 nats at 3432 seconds.
  • Sensitivity to η: At M=2000, increasing η raises survivor-conditioned standard deviation from 5.1 nats at η=0.25 to 9.8 at η=0.75, while CPU time changes little.Seven of eight corpus seeds survive at η=0.25; η=0 gives every seed at least one zero paragraph estimate.
  • Exact ground truth: The bigram model composes with fptb into a weighted automaton whose accepting paths do not double-count source strings.
  • Exact ground truth: Backward weights satisfy β = f + Tβ and can be computed as β = (I − T)^−1f when the series converges.
  • Exact ground truth: Backward weights are computed once and forward weights are updated per target symbol, but the composed state space is not finite for neural language models.

E THE GENETIC-CODE WORST CASE

A uniform genetic-code construction is an extreme worst case for standard beam search: its retained mass vanishes exponentially, whereas importance-weighted and fixed-M without-replacement estimators remain exact.

  • Standard beam search: Standard beam search captures an exponentially vanishing share of target mass in the uniform codon construction.
  • Standard beam search: For T = 100 and d = 3, recovering all mass requires M = 3^100 ≈ 5 × 10^47 source strings.
  • Importance-weighted estimators: Importance weighting gives each valid codon a factor d/4^3, allowing M particles to represent d^T covering source strings.
  • Importance-weighted estimators: smc_simple and smc_rb have zero variance, while fixed-M beam_swor is also exact in this uniform setting.
  • Scope: The construction does not distinguish stochastic estimators because it assumes a uniform source and constant alias count d.Non-uniform DNA models introduce variance differences measured in the experiments.

F DETAILS OF THE MECO RERUN

The MECO rerun applies jackknife correction to surprisal estimates and finds that correcting corpus surprisal does not alter the reported predictive conclusions.

  • Jackknife check: Jackknife correction estimates logarithmic bias by repeatedly omitting one of ten runs and subtracts the estimate from the all-run surprisal.Averaging prefix-probability estimates remains unbiased, but taking their logarithm introduces bias.
  • Correction effects: The correction raises corpus log probability by 1.55 nats, lowering corpus surprisal by the same amount.
  • Correction effects: 107 nats replaces the 106-nat uncorrected difference after correction.
  • Correction effects: Held-out ΔLL changes by at most 0.015 × 10−3 nats, with neither Table 3 results nor the matched comparison changing.
  • Matched fit comparison: Paired sign-flip tests find no predictive difference between matched PTB-word fits, with p ≥ 0.068 in both directions for every measure.

G ADDITIONAL BYTE-TO-WORD RESULTS

Additional byte-to-word results validate per-position estimates across all ten paragraphs and report per-paragraph GPT-2 probabilities and runtimes.

  • Validation: Figures 15 and 16 extend exact-bigram validation to every byte position in all ten paragraphs.
  • Validation: beam_swor and beam_swor_adaptive averages remain close to one, while threshold-pruned beam summing falls below one where pruning discards positive covering mass.
  • Validation: Figure 15 shows paragraphs 0–5, and Figure 16 continues the same methods and axes for paragraphs 6–9.
  • Per-paragraph results: Table 4 reports per-paragraph log-prefix probabilities in nats and wall time in seconds under the GPT-2-to-byte transduction.It also gives between-run standard deviations, per-run wall times, and the difference between beam_summing and beam_swor_adaptive.
  • Per-paragraph results: Table 4 uses τ=10−3 for beam_summing and ρ=0.1, nominal M=800, and thirty-two runs for beam_swor_adaptive.
Loading 2608.27428v1…