Transducing Language Models

Vésteinn Snæbjarnarson; Samuel Kiegeland; Tianyu Liu; Reda Boumasmoud; Ryan Cotterell; Tim Vieira

cs.CLMar 5, 2026

Transducing Language Models

Authors: Vésteinn Snæbjarnarson, Samuel Kiegeland, Tianyu Liu, Reda Boumasmoud, Ryan Cotterell, Tim Vieira

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

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: GPT-2 probabilities for the BPE token strings that, when lowercased, match hello . The total probability of all such sequences is at the bottom.

Figure 6: Average Jensen–Shannon divergence (JSD) and throughput (bytes/sec) across thresholds

\tau

. Left:

p_{{\color[rgb]{0.5508,0.0391,0.3477}\mathcal{X}}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}

(reference:

\tau=

1e-5). Right:

p_{{\color[rgb]{0.5508,0.0391,0.3477}\mathcal{X}}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}

(reference:

\tau=

1e-4; 3e-4 for

p_{\mathsf{phi4}}

). Bars show 95% bootstrapped CIs. At the tightest thresholds, large decomposition sizes prevent some models from completing all paragraphs; see § G.2 .

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 8 — Figure 8: Truncated frontier example for the target ${\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{y}}={\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}}$ . Top: the transducer f . Middle: the frontier graph $\mbox{{{\color[rgb]{0,0,1}run}}}_{\smash{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}}}}$ , whose nodes are sets of $(s,{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{b}})$ pairs and whose edges are input symbols. Buffers are truncated to length $|{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{y}}|{+}1=2$ : advancing $(q_{3},{\color[rgb]{0.3828,0.4492,0.0742}\texttt{cd}})$ by any input produces cdd , truncated back to cd , yielding the self-loop. Truncation keeps the state space finite while preserving whether the buffer has reached the target and which next output symbol it commits to. Reading ${\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{x}}={\color[rgb]{0.5508,0.0391,0.3477}\texttt{a}}$ reaches two states via $\varepsilon$ -closure: $q_{1}$ (buffer $={\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{y}}$ ) and $q_{3}$ (buffer $\succ{\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{y}}$ ). Yellow nodes are universal—every input leads to a non-empty accepting successor—placing a in ${\color[rgb]{0.5508,0.0391,0.3477}\mathcal{Q}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}})$ . The teal node $q_{2}$ has no arc on b , so the BFS fails and b enters ${\color[rgb]{0.5508,0.0391,0.3477}\mathcal{R}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}})$ .

Panel of Figure 15 — Figure 15: An FST that maps $n$ occurrences of ’a’ to the same number of ’b’s, except when the input is exactly two ’a’s, which are mapped to ’c’.

Panel of Figure 16 — Figure 16: An FST where the $\varepsilon$ -output arc $q_{0}\xrightarrow{{\color[rgb]{0.5508,0.0391,0.3477}\texttt{a}}:\varepsilon}q_{1}$ creates a frontier element whose output has not yet reached the target. For target ${\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{y}}={\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}}$ and source prefix ${\color[rgb]{0.5508,0.0391,0.3477}\boldsymbol{x}}={\color[rgb]{0.5508,0.0391,0.3477}\texttt{a}}$ , the frontier is $\mathcal{F}=\{(q_{1},\varepsilon),(q_{2},{\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}})\}$ . The covering states $\{q_{2}\}$ are not input-projection universal ( $q_{2}$ has no arc on b ), so $\mbox{{{\color[rgb]{0,0,1}fast\_univ\_filter}}}({\color[rgb]{0.5508,0.0391,0.3477}\texttt{a}},{\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}})$ fails and a would be misclassified as non-quotient. However, $q_{1}$ handles input b and produces c , matching the target. The BFS in is_cylinder confirms universality over the full frontier, correctly placing a in ${\color[rgb]{0.5508,0.0391,0.3477}\mathcal{Q}}({\color[rgb]{0.3828,0.4492,0.0742}\texttt{c}})$ .

C0HLZ5	P01858	P0DPI4	P0DUS0	P84464
P84465	P0DOY5	P67857	P67858	P67859
P81826	P23210	P85003	P84071	P86168
C0HJF1	C0HJG0	P02729	P81010	P86909
P86922	B3EWE5	P0DMM6	P0DQM6	P0DQM7
P12481	P85002	B3EWR3	P01358	P02728
P0C005	P0DKX2	P0DMM7	P0DQM9	P0DX30

Appendix

Table 1: Accession numbers used in this study.

Model	States	IP-Univ. States	Transitions
Tokens to Bytes
$p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$	75,723	75,723	125,979
$p_{\mathsf{llama1B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$	176,990	176,990	305,244
$p_{\mathsf{llama8B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$	176,990	176,990	305,244
$p_{\mathsf{phi4}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$	115,244	115,244	215,593
Tokens to Words

Appendix

Table 4: Number of states, IP-universal states, and transitions.

Panel of Figure 17 — Figure 17: An FST for converting DNA sequences to amino acids. Each triplet of nucleobases maps to one of 20 different amino acids. We only show a proportion of the machine.

Pos	Byte	JSD	$\max\|\Delta p\|$
0	R	3.9e-15	7.9e-7
1	o	6.5e-16	1.2e-6
2	b	3.5e-15	1.2e-6
3	e	4.4e-14	1.7e-6
4	r	4.5e-15	3.4e-6
5	t	1.8e-15	2.4e-6

Appendix

Table 5: Exact comparison: our method (

\tau=0

) vs. genlm-bytes (exact) for

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

	$p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$		$p_{\mathsf{llama1B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$
$\tau$	average JSD / byte	bytes / sec	average JSD / byte	bytes / sec
1e-1	4.0e-2 (3.7e-2, 4.2e-2)	70.95 (64.14, 79.65)	2.8e-2 (2.5e-2, 3.0e-2)	84.21 (71.77, 99.54)
3e-2	1.9e-2 (1.8e-2, 2.1e-2)	44.68 (40.59, 48.66)	1.2e-2 (1.1e-2, 1.4e-2)	72.23 (65.87, 78.10)
1e-2	6.7e-3 (5.8e-3, 7.8e-3)	25.13 (23.83, 26.69)	4.2e-3 (3.5e-3, 4.9e-3)	40.45 (37.60, 43.43)
3e-3	2.5e-3 (1.9e-3, 3.3e-3)	10.48 (9.89, 11.12)	1.1e-3 (8.4e-4, 1.3e-3)	22.09 (20.94, 23.51)
1e-3	1.4e-3 (9.3e-4, 1.9e-3)	6.21 (5.89, 6.59)	4.0e-4 (2.9e-4, 5.6e-4)	11.86 (11.27, 12.49)

Appendix

Table 6: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds

\tau

using

p_{{\color[rgb]{0.5508,0.0391,0.3477}\mathcal{X}}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}

against a reference distribution from Vieira et al. (2025a) with a beam size of

K

=32. 95

\%

confidence intervals are given in parentheses.

	$p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$		$p_{\mathsf{llama1B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$
$K$	JSD vs $K\!=\!32$	bytes / sec	JSD vs $K\!=\!32$	bytes / sec
8	3.0e-5 (2.5e-5, 3.9e-5)	37.81 (37.59, 37.98)	7.1e-5 (6.7e-5, 7.6e-5)	46.94 (45.69, 47.97)
16	2.4e-5 (2.3e-5, 2.7e-5)	28.83 (28.53, 29.13)	7.1e-5 (6.7e-5, 7.5e-5)	28.76 (28.42, 29.08)
32	(not applicable)	18.12 (17.87, 18.36)	(not applicable)	5.34 (4.21, 7.19)

Appendix

Table 7: Throughput and Jensen–Shannon divergence (JSD) of Vieira et al. (2025a) at beam sizes

K\in\{8,16,32\}

. JSD is measured against

K\!=\!32

. 95

\%

confidence intervals are given in parentheses.

	$p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$		$p_{\mathsf{llama1B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$
$\tau$	average JSD / byte	bytes / sec	average JSD / byte	bytes / sec
1e-1	3.8e-2 (3.4e-2, 4.1e-2)	76.50 (66.94, 89.01)	2.8e-2 (2.6e-2, 3.0e-2)	84.21 (72.49, 99.24)
3e-2	1.7e-2 (1.5e-2, 1.9e-2)	45.61 (39.82, 51.46)	1.2e-2 (1.1e-2, 1.4e-2)	72.23 (66.25, 78.94)
1e-2	5.9e-3 (4.8e-3, 7.1e-3)	25.71 (24.08, 27.89)	4.2e-3 (3.5e-3, 5.0e-3)	40.45 (37.65, 43.43)
3e-3	2.1e-3 (1.4e-3, 2.9e-3)	11.22 (10.44, 12.07)	1.1e-3 (8.5e-4, 1.3e-3)	22.09 (20.90, 23.34)
1e-3	1.5e-3 (9.1e-4, 2.3e-3)	6.49 (6.02, 6.99)	4.0e-4 (2.8e-4, 5.4e-4)	11.86 (11.25, 12.54)

Appendix

Table 8: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds

\tau

using

p_{{\color[rgb]{0.5508,0.0391,0.3477}\mathcal{X}}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}

against a reference distribution (

\tau=

1e-5). 95

\%

confidence intervals are given in parentheses.

	$p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$		$p_{\mathsf{llama1B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$
$\tau$	average JSD / byte	bytes / sec	average JSD / byte	bytes / sec
1e-1	3.9e-3 (3.3e-3, 4.7e-3)	26.65 (25.79, 27.48)	3.0e-3 (2.6e-3, 3.5e-3)	30.44 (28.31, 32.19)
3e-2	1.4e-3 (1.2e-3, 1.5e-3)	17.03 (16.42, 17.66)	1.1e-3 (9.3e-4, 1.3e-3)	17.45 (16.67, 18.27)
1e-2	5.7e-4 (5.0e-4, 6.7e-4)	10.79 (10.23, 11.36)	3.7e-4 (3.4e-4, 4.0e-4)	10.54 (10.03, 11.09)
3e-3	1.7e-4 (1.5e-4, 1.9e-4)	4.52 (4.29, 4.79)	1.3e-4 (1.2e-4, 1.4e-4)	8.30 (7.98, 8.67)
1e-3	5.5e-5 (5.1e-5, 6.1e-5)	2.01 (1.88, 2.15)	6.1e-5 (5.8e-5, 6.5e-5)	4.13 (3.91, 4.36)

Appendix

Table 9: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds

\tau

using

p_{{\color[rgb]{0.5508,0.0391,0.3477}\mathcal{X}}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}

against a reference distribution (

\tau=

1e-4; 3e-4 for

p_{\mathsf{phi4}}

). 95

\%

confidence intervals are given in parentheses.

	$p_{\mathsf{dna}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{dna2aa}}$ ( $n_{\texttt{max}}$ = 5000)		$p_{\mathsf{dna}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{dna2aa}}$ ( $n_{\texttt{max}}$ = 10000)
$\tau$	average JSD / byte	bytes / sec	average JSD / byte	bytes / sec
1e-1	2.8e-2 (2.4e-2, 3.2e-2)	9.55 (8.44, 10.90)	2.8e-2 (2.5e-2, 3.3e-2)	9.54 (8.45, 10.82)
3e-2	3.2e-3 (2.8e-3, 3.6e-3)	2.90 (2.57, 3.26)	3.3e-3 (2.9e-3, 3.7e-3)	2.03 (1.74, 2.39)
1e-2	6.6e-4 (4.4e-4, 9.0e-4)	2.20 (1.99, 2.47)	7.4e-4 (5.0e-4, 1.0e-3)	1.42 (1.25, 1.63)
3e-3	1.6e-4 (7.8e-5, 2.7e-4)	1.89 (1.72, 2.11)	2.7e-4 (1.1e-4, 4.9e-4)	1.16 (1.03, 1.31)
1e-3	7.1e-5 (1.7e-5, 1.6e-4)	1.79 (1.62, 1.97)	6.6e-5 (1.7e-5, 1.5e-4)	1.08 (0.97, 1.22)

Appendix

Table 10: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds

\tau

and a reference (

\tau=

1e-6) using

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

. 95

\%

confidence intervals are given in parentheses. We limit the candidate-set size (

n_{\texttt{max}}

) to mitigate the combinatorial blow-up with increasing sequence length.

Panel of Table 11 — Table 11: Mean and maximum quotient size $|{\color[rgb]{0.5508,0.0391,0.3477}\texttt{Q}}|$ across sequence positions for three transducers at varying pruning thresholds $\tau$ . Results are computed on paragraph 1 of WikiText (833 bytes for $p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$ , 850 bytes for $p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$ ) and on the longest protein in the test set (P83127, 12 amino acids for $p_{\mathsf{dna}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{dna2aa}}$ ). The ${{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$ and ${{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{dna2aa}}$ transducers have all-universal states ( $|{\color[rgb]{0.5508,0.0391,0.3477}\texttt{R}}|=0$ everywhere). The ${{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$ transducer has non-universal states, so we additionally report the remainder size $|{\color[rgb]{0.5508,0.0391,0.3477}\texttt{R}}|$ .

$\tau$	bytes / sec		Bits / byte		Cross-entropy
	Mean	95% CI	Mean	95% CI	Mean	95% CI
$p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}$
1e-1	82.61	(73.33, 92.34)	1.2434	(1.1884, 1.2936)	0.8619	(0.8237, 0.8966)
3e-2	49.10	(44.48, 54.24)	1.1466	(1.0978, 1.1949)	0.7948	(0.7609, 0.8282)
1e-2	28.46	(26.73, 30.33)	1.0652	(1.0199, 1.1068)	0.7383	(0.7070, 0.7672)
3e-3	14.20	(13.47, 14.98)	1.0385	(0.9956, 1.0806)	0.7199	(0.6901, 0.7490)

Appendix

Table 12: Cross-entropy and throughput for various thresholds

\tau

using

p_{{\color[rgb]{0.5508,0.0391,0.3477}\mathcal{X}}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}

. 95

\%

confidence intervals are given in parentheses.

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

\tau=

1e-5 is computed over 6 paragraphs; all other configurations use 10.

Converted States ( $n$ )	$p_{\mathsf{llama1B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$	$p_{\mathsf{llama8B}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$	$p_{\mathsf{phi4}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\mathrm{ptb}}$
0	(not applicable)	(not applicable)	(not applicable)
2	3.9e-5 (3.5e-5, 4.3e-5)	1.3e-4 (7.4e-5, 2.1e-4)	6.6e-5 (3.1e-5, 1.1e-4)
5	9.5e-4 (7.5e-4, 1.2e-3)	9.0e-4 (7.5e-4, 1.1e-3)	7.8e-4 (6.4e-4, 9.4e-4)
8	9.8e-4 (8.0e-4, 1.2e-3)	9.2e-4 (7.7e-4, 1.1e-3)	8.1e-4 (6.6e-4, 9.6e-4)
11	3.0e-2 (2.6e-2, 3.3e-2)	2.8e-2 (2.5e-2, 3.1e-2)	2.6e-2 (2.3e-2, 2.9e-2)
14	2.9e-2 (2.6e-2, 3.3e-2)	2.8e-2 (2.5e-2, 3.1e-2)	2.6e-2 (2.3e-2, 2.9e-2)

Appendix

Table 13: Average Jensen–Shannon divergence (JSD) for the PTB transducer (

\tau=

1e-3) after randomly converting

n

of the IP-universal states to non-IP-universal. 95

\%

confidence intervals are given in parentheses. JSD is computed against the unmodified transducer (

n=0

Figure 19: Per-repeat Jensen–Shannon divergence (JSD) vs. number of states converted from IP-universal to non-IP-universal for the PTB transducer (

\tau=

1e-3). Each repeat uses a different random conversion order. The abrupt jumps are caused by individual high-connectivity states, whose conversion causes a jump in JSD.

Panel of Figure 21 — Figure 21: A simple FST that segments character streams into words without contextual information, inserting ␣ at the start of each word.

Efficient Language Model Inference

Efficient language model inference reduces the compute, memory, latency, and energy needed to generate useful outputs.

See all 317 papers

Stochastic Estimation of Transduced Language Models
Aug 27, 2026Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral +2Language Modeling Sequence Modeling
ETH Zürich · CHI-FRO
Byte Language Models: Scaling, Emergent Abstractions, and Information Allocation
Oct 5, 2026Jie Wang, Shiwei Luo, Qi Zhang +1Language Model Scaling Byte-Level Language Model
School of Computer Science, East China Normal University, Shanghai, China · School of Computer Science, Fudan University, Shanghai, China
Alpha Diffusion Language Models: Factorization Alone Is Not the Problem
Sep 29, 2026Nikita Gushchin, Dmitry Baranchuk, Alexander KorotinDiffusion Language Models Diffusion Language Model Training
Applied AI Institute, Moscow, Russia · AXXX, Russia · Yandex Research

Aug 27, 2026J/K move · Enter open · S save

Stochastic Estimation of Transduced Language Models

Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral, Ryan Cotterell+1

ETH Zürich · CHI-FRO

Language Modeling Sequence Modeling Inverse Probability Weighting

Open paper AskPDF arXiv

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.

Abstract

Efficient Language Model Inference

Explore similar work

Stochastic Estimation of Transduced Language Models

Byte Language Models: Scaling, Emergent Abstractions, and Information Allocation

Alpha Diffusion Language Models: Factorization Alone Is Not the Problem