Stochastic Estimation of Transduced Language Models

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

cs.CLAug 27, 2026

Stochastic Estimation of Transduced Language Models

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

Organizations: ETH Zürich · CHI-FRO

Abstract

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, 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.

Figures & tables

Algorithm	Prune	(i) Unbiased	(ii) Variance (qual.)	(iii) Particle count
beam_summing ( Fig. 1 )	none	✓	$0$	unbounded
$\hookrightarrow$ $+$ $\mbox{{{\color[rgb]{0,0,1}prune}}}_{M}$	keep $M$ heaviest	✗	$0$	fixed $M$
$\hookrightarrow$ $+$ $\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}$	keep $\geq 1-\tau$ mass	✗	$0$	mass-set
smc_simple ( App. B )	multinomial	✓	high	fixed $M$
smc_rb ( App. B )	multinomial	✓	lower	fixed $M$
beam_swor	SWOR	✓	lowest	fixed $M$

Table 1: The TLM algorithm family . beam_summing ( Fig. 1 ) extends live particles to every live child before applying pruning. beam_swor and beam_swor_adaptive ( Fig. 2 ) extend beam_summing with pruning functions that sample distinct survivors without replacement. In contrast, smc_simple and smc_rb sample one child for each particle. smc_simple also samples the stop decision. smc_rb instead adds quotient and remainder contributions directly. The prune-free row is exact whenever the run halts. With

\mbox{{{\color[rgb]{0,0,1}prune}}}_{M}

, keeping at most the

M

heaviest particles, beam_summing is standard beam search ( Fig. 1 ), and with

\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}

it is the beam summing of Snæbjarnarson et al. (2026) . The qualitative variance labels summarize the full-scale measurements of Tab. 2 .

Panel of Figure 3 — Figure 3: One swor_adaptive prune, left to right (top), and successive prunes at one target position (bottom). Each bar is one child particle of the pool with height its weight. The dashed line is the per-particle threshold $1/c=\rho\,(A+W)/M$ (drawn at $\rho{=}1$ ). Panel (b) shows how each child particle fills $\min(c\,w^{(i)},\,1)$ of one of the $M$ slots, so a child particle above the threshold counts for at most $1/c$ of the mass however heavy, the counts sum to $\mu$ , and the particle count $m=\lfloor\mu+\tfrac{1}{2}\rfloor$ , the nearest integer, is fixed before any randomness. In panel (c), pps then keeps exactly $m$ particles, re-solving the constant to $c^{\prime}$ , pinning the child particles above the new threshold, and drawing each remaining survivor with probability $c^{\prime}\,w^{(i)}$ at the shared weight $1/c^{\prime}$ , so the draw passes the twisted total through unchanged ( Proposition 3.4 ). Bottom row: as $A$ grows, the pool’s bars shrink against the threshold and the particle count falls. When the pool counts for less than half a particle, a coin flip determines whether the call continues with a one-particle draw or halts.

Panel of Figure 4 — Figure 4: The one-state transducer of the halting example. Both arcs loop on the single initial, final state, a emitting nothing and b emitting c , so a source string maps to one c for each b it contains.

Panel of Figure 5 — Figure 5: Two ways to maintain a bounded particle pool. Dashed rings in ( 5(a) ) mark children removed by pruning. In ( 5(b) ), the cross marks a dropped particle and orange marks a duplicate. Grey edges show unexplored branches. Dot size shows weight.

Figure 6: Unbiased methods versus beam summing with

\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}

on the

p_{\mathsf{bigram}}{\circ}{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}

TLM, compared with exact probabilities. Panels (a) and (b) plot relative root-mean-square error

\mathrm{RMSE}[\hat{Z}/Z]

: (a) a single example paragraph and (b) the ten-paragraph corpus total, both against the mean live particle count. Labels give the maximum particle count

M

. Bars give

95\%

bootstrap intervals. Panel (c) counts the paragraphs each method resolves, capturing at least

5\%

of a paragraph’s mass.

Figure 7: GPT-2-large transduced with

{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}

. Panels (a) and (b) plot the estimates

\log\hat{Z}

in nats against the mean live particle count. Labels give the maximum particle count

M

. Each point is

\log\bigl(8^{-1}\sum_{s=1}^{8}\hat{Z}_{s}\bigr)

, with a failed run contributing

\hat{Z}_{s}=0

. Thick bars give

95\%

bootstrap intervals, thin whiskers span the finite per-run log estimates, and clipped minima are printed at the lower edge. The dashed line is the threshold-pruned lower bound at

\tau{=}10^{-3}

. The two algorithms appear to converge to a common value. The lower bound is

2.0

nats below this value on the paragraph and approximately

33

nats below it on the corpus. Panel (c) counts the paragraphs on which each method recovers at least the lower bound’s mass.

Panel of Figure 8 — Figure 8: Accuracy–walltime comparisons. (a) For $p_{\mathsf{bigram}}{}$ , where exact target prefix probabilities are available, the between-seed standard deviation of the corpus log-estimate against per-seed corpus walltime. Annotations in both panels give the mean live particle count, with the maximum particle count $M$ in parentheses. The beam_summing lines using $\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}$ report bias relative to the exact values, and bars give the 95% confidence interval of each standard deviation. (b) For $p_{\mathsf{gpt2}}$ , where exact target prefix probabilities are unavailable, the finite per-seed corpus log-estimates over $32$ seeds. Boxes span the interquartile range with whiskers at $1.5$ IQR and seeds beyond them drawn as dots, and the black bar marks the median seed. The star marks the pooled estimate $\log\overline{\hat{Z}}$ , the log of the seed-averaged $\hat{Z}$ , computed from all $32$ seeds with a failed run contributing $\hat{Z}=0$ . Because the pooled estimate averages $\hat{Z}$ before taking the logarithm, occasional high estimates can make it larger than the median per-seed estimate. The beam_summing line shows its corpus total at $\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}$ .

Panel of Figure 9 — Figure 9: DNA-to-amino-acid results. ( 9(a) ) Relative RMSE against exact values over $64$ seeds and three targets, with $95\%$ bootstrap intervals. The error of beam_swor_adaptive decreases faster with $M$ than that of smc_rb , while beam_summing with $\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}$ has fixed error. ( 9(b) ) Cumulative walltime for the bigram model. beam_summing with $\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}$ exceeds five minutes at position $13$ , while beam_swor_adaptive ( $\rho{=}0.1$ , $M{=}256$ ) reaches position $200$ in about five seconds.

Algorithm	$p_{\mathsf{bigram}}{\circ}{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$	$p_{\mathsf{gpt2}}{\circ}{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$	$p_{\mathsf{bigram}}{\circ}{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{dna2aa}}$
smc_simple	9.78	—	0.111
smc_rb	7.86	3.23	0.107
beam_swor	0.170	0.395	0.062
beam_swor_adaptive ( $\rho{=}0.1$ )	0.200	0.199	0.062

Table 2: Between-seed standard deviation, in nats, of each estimator’s log probability estimate

\log\hat{Z}

. The columns report the ten-paragraph WikiText-2 total for the bigram model, the first WikiText-2 paragraph for GPT-2, and the amino-acid target for DNA. Reported values use eight seeds and maximum particle counts of

2000

200

, and

256

, respectively, except beam_swor_adaptive on the bigram (

M{=}8000

, mean live count

251

). The smc_simple GPT-2 run covered only

120/850

bytes.

Pruning function	First fixation	Gaze duration	Total reading time
swor_adaptive	$0.76^{**}$	$2.05^{***}$	$3.26^{***}$
$\mbox{{{\color[rgb]{0,0,1}prune}}}_{\tau}$	$0.81^{**}$	$2.13^{***}$	$3.24^{***}$

Table 3: Predictive contribution of PTB-word contextual surprisal on MECO. Values are

\Delta\mathrm{LL}

10^{-3}

nats. For swor_adaptive , we use

\rho{=}0.1

, nominal

M{=}8000

, and

10

seeds. ∗

p<0.05

; ∗∗

p<0.01

; ∗∗∗

p<0.001

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 11 — Figure 11: (a) An example source string aligned to a target prefix under a function ${\color[rgb]{0.3828,0.4492,0.0742}f}$ , the dashed lines marking the boundaries between target positions. A symbol may emit none or several target symbols, so the source spans between boundaries vary in length while the alignment stays monotone. At each step a source symbol is scanned, and at each boundary a target symbol is emitted. (b) When $\psi=\mbox{{{\color[rgb]{0,0,1}is\_live}}}$ we sample by source mass (edge width) and never enter a dead branch ( $\times$ ), so no draw is wasted. Since we only look at the current live symbols, we cannot tell a heavy branch with little mass ahead (top) from a light branch that carries it (bottom). Importance weighting corrects for the proposal, while resampling with replacement mitigates particle-weight degeneracy ( §§ B.3 and B.5 ).

Figure 14: Sensitivity to the pruning parameters on the ten-paragraph bigram corpus (eight seeds). (a) Between-seed standard deviation of the corpus

\log\hat{Z}

against CPU time per seed as

\rho

varies for beam_swor_adaptive at nominal

M{\in}\{2000,8000\}

. Labels give

\rho

, and plain beam_swor at

M{=}2000

is the fixed-

M

reference. (b) Survivor-conditioned standard deviation as the ESS threshold

\eta

varies for smc_rb at

M{=}2000

. A corpus seed survives when all ten paragraph estimates are nonzero. Annotations mark settings with fewer surviving seeds and note that none survives at

M{=}200

Panel of Figure 15 — Figure 15: Per-position ratio $\hat{Z}_{t}/Z_{t}$ for all ten $p_{\mathsf{bigram}}{\circ}{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$ paragraphs at $M{=}200$ , averaged over $256$ runs. Paragraphs 0–5 are shown here and 6–9 in Fig. 16 . The beam_swor and beam_swor_adaptive averages remain close to one with sampling variation. Threshold-pruned beam summing at $\tau{=}10^{-2}$ and $\tau{=}10^{-3}$ falls below one where pruning discards positive covering mass.

Panel of Figure 16 — Figure 16: Per-position validation, paragraphs 6–9 (continued from Fig. 15 ), with the same methods and axes.

para	beam_summing	beam_swor_adaptive	$\Delta$	$t_{\mathrm{beam}}$	$t_{\mathrm{adaptive}}$
0	$-556.96$	$-554.96$ $(0.25)$	$-2.00$	$52$	$57$
1	$-564.10$	$-556.41$ $(1.38)$	$-7.70$	$106$	$210$
2	$-443.86$	$-443.21$ $(0.12)$	$-0.65$	$54$	$102$
3	$-747.96$	$-743.12$ $(0.19)$	$-4.84$	$170$	$216$
4	$-635.85$	$-631.16$ $(0.20)$	$-4.69$	$191$	$269$
5	$-772.31$	$-768.42$ $(0.27)$	$-3.88$	$353$	$647$

Appendix

Table 4: Per-paragraph log-prefix probabilities in nats and wall time in seconds under

p_{\mathsf{gpt2}}{\circ}{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}

. beam_summing uses

\tau{=}10^{-3}

. beam_swor_adaptive uses

\rho{=}0.1

, nominal

M{=}800

, and thirty-two runs. Parentheses give the between-run standard deviation, and wall times are per run. The

\Delta

column is beam_summing minus beam_swor_adaptive . The total row sums the per-paragraph log estimates. The corpus panel of Fig. 7 instead averages the per-run corpus estimates before taking the logarithm, hence its

-5376.7

Language Modeling

Language modeling develops systems that learn patterns in text and other sequences to understand, predict, and generate language.

See all 519 papers

Mar 5, 2026

Transducing Language Models

Modern language models define distributions over strings, but downstream tasks often require different output formats. For instance, a model that generates byte-pair strings does not directly produce word-level predictions, and a DNA model does not directly produce amino-acid sequences. In such cases, a deterministic string-to-string transformation can convert the model's output to the desired form. This is a familiar pattern in probability theory: applying a function

f

to a random variable

X\sim p

yields a transformed random variable

f(X)

with an induced distribution. While such transformations are occasionally used in language modeling, prior work does not treat them as yielding new, fully functional language models. We formalize this perspective and introduce a general framework for language models derived from deterministic string-to-string transformations. We focus on transformations representable as finite-state transducers -- a commonly used state-machine abstraction for efficient string-to-string mappings. We develop algorithms that compose a language model with an FST to marginalize over source strings mapping to a given target, propagating probabilities through the transducer without altering model parameters and enabling conditioning on transformed outputs. We present an exact algorithm, an efficient approximation, and a theoretical analysis. We conduct experiments in three domains: converting language models from tokens to bytes, from tokens to words, and from DNA to amino acids. These experiments demonstrate inference-time adaptation of pretrained language models to match application-specific output requirements.

Vésteinn Snæbjarnarson, Samuel Kiegeland, Tianyu Liu +3

ETH Zürich · University of Copenhagen · CHI-FRO

Efficient Language Model Inference

Ask PDF

Sep 28, 2026

Telescopic Language Models

One deployed language model must often serve many compute budgets, yet serving each budget still means a separate training or compression run per point. We train a Telescopic Language Model (TLM) to be that continuum: a nested-capacity Transformer supervised by stochastic prefix supervision with a full anchor. At every step, one randomly truncated prefix of the capacity axis is trained against the full next-token target, alongside one full-capacity pass, so the trained artifact is a valid language model at every depth. Two forward-backward passes per step, no architectural change, nothing extra at inference. Fixed-exit suites such as Matryoshka Language Model Suites (MLMS) occupy one point in this design space, and the point has a cost: supervising only a few fixed exits leaves the nested model at chance level everywhere else (perplexity 10^2-10^5 in our baselines). On a 200M proxy suite (20B FineWeb-Edu tokens, identical data stream for all methods), a single TLM run is a valid language model at every one of its twenty layer prefixes, in perplexity and on perplexity-sensitive downstream tasks, reducing the area under the quality-budget curve by 43-44% relative to the fixed-exit suites while matching them at full capacity, at ~12% lower GPU cost per run. The prefix sampling density is a dial: concentrating it on a few depths recovers fixed-exit quality there at the price of the continuum, so the operating points become a training-time choice rather than an architectural one. These results indicate that the training objective, not the nesting itself, is what makes a model elastic.

Zhilin Guo, Boqiao Zhang, Hakan Aktas +14

University of Cambridge · University of British Columbia · Google

Language Modeling Efficient Language Model Inference LLM Training

Ask PDF

Mar 9, 2026

Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference

Inference-time methods that aggregate and prune multiple samples have emerged as a powerful paradigm for steering large language models, yet we lack any principled understanding of their accuracy-cost tradeoffs. In this paper, we introduce a route to rigorously study such approaches using the lens of particle filtering algorithms such as Sequential Monte Carlo (SMC). Given a base language model and a process reward model estimating expected terminal rewards, we ask: how accurately can we sample from a target distribution given some number of process reward evaluations? Theoretically, we identify (1) simple criteria enabling non-asymptotic guarantees for SMC; (2) algorithmic improvements to SMC; and (3) a fundamental limit faced by all particle filtering methods. Empirically, we demonstrate that our theoretical criteria effectively govern the sampling error of SMC, though not necessarily its final accuracy, suggesting that theoretical perspectives beyond sampling may be necessary.

Noah Golowich, Fan Chen, Dhruv Rohatgi +4

Microsoft Research · MIT · NYU

Parallel Reasoning in Language Models LLM Inference Parallel LLM Inference Inference-Time Guidance Efficient Language Model Reasoning

Ask PDF

Abstract

Language Modeling

Explore similar work

Transducing Language Models

Telescopic Language Models

Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference