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∼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
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 2
Figure 6: Average Jensen–Shannon divergence (JSD) and throughput (bytes/sec) across thresholds τ . 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: τ= 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: τ= 1e-4; 3e-4 for pphi4 ). 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
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 ε -closure: q1 (buffer ={\color[rgb]{0.3828,0.4492,0.0742}\boldsymbol{y}} ) and q3 (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 q2 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}}) .
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’.
Figure 16: An FST where the ε -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 {q2} are not input-projection universal ( q2 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, q1 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}}) .
Table 4: Number of states, IP-universal states, and transitions.
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∣Δ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 ( τ=0 ) vs. genlm-bytes (exact) for p_{\mathsf{gpt2}}\circ{{\color[rgb]{0.3828,0.4492,0.0742}\texttt{f}}}_{\alpha} .
Table 6: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds τ 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.
Table 7: Throughput and Jensen–Shannon divergence (JSD) of Vieira et al. (2025a) at beam sizes K∈{8,16,32} . JSD is measured against K=32 . 95 % confidence intervals are given in parentheses.
Table 8: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds τ 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 ( τ= 1e-5). 95 % confidence intervals are given in parentheses.
Table 9: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds τ 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 ( τ= 1e-4; 3e-4 for pphi4 ). 95 % confidence intervals are given in parentheses.
Table 10: Average Jensen–Shannon divergence (JSD) and bytes/sec for various thresholds τ and a reference ( τ= 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 ( nmax ) to mitigate the combinatorial blow-up with increasing sequence length.
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 τ . 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}}| .
Table 12: Cross-entropy and throughput for various thresholds τ 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} at τ= 1e-5 is computed over 6 paragraphs; all other configurations use 10.
Table 13: Average Jensen–Shannon divergence (JSD) for the PTB transducer ( τ= 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 ( τ= 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.
Figure 21: A simple FST that segments character streams into words without contextual information, inserting ␣ at the start of each word.
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.
Vésteinn Snæbjarnarson, Samuel Kiegeland, Manuel de Prada Corral +2
Tokenizer-free language models remove the inductive bias of fixed tokenizers by modeling text directly as bytes, but the resulting longer sequences substantially increase computation and eliminate explicit text abstractions. We ask whether this additional computation can be useful, and whether standard Transformers can learn the abstractions that tokenization provides. We study these questions on Transformers without specialized tokenization-related architectures. With token-superposition training and hash embeddings, byte Transformers consistently outperform subword Transformers as model size scales. We further find that byte Transformers build local text abstractions as external tokenizers: a set of segmentation-like positions are used to collect local context representations, and restricting up to 25% of intermediate layers to these local representations preserves downstream performance. Finally, these learned structures induce highly non-uniform generation difficulty, with uncertainty concentrated near local structure boundaries; exploiting them for speculative decoding yields 3.4× more accepted tokens than in subword Transformers.
Jie Wang, Shiwei Luo, Qi Zhang +1
School of Computer Science, East China Normal University, Shanghai, China · School of Computer Science, Fudan University, Shanghai, China
Discrete diffusion language models can generate multiple tokens in parallel, but reducing the number of denoising steps can lead to inconsistent predictions. Standard cross-entropy training fits conditional token marginals, whereas parallel generation requires consistent joint predictions. We introduce Alpha Diffusion Language Models (AlphaDLM), trained with a sequence-level alpha loss that recovers cross-entropy in the limit of vanishing alpha and has a joint-mode optimum at alpha one. Our analysis characterizes how the objective and factorization jointly determine the fitted distribution. We identify conditions under which intermediate alpha preserves multiple valid completions while excluding invalid token combinations. Trained on TinyGSM, our method achieves 34.6% accuracy on GSM8K with only four model evaluations. We further scale the method to SDAR-1.7B and evaluate it on code and mathematics benchmarks. These results show that changing the training objective can improve the accuracy-computation trade-off of factorized diffusion language models.
Nikita Gushchin, Dmitry Baranchuk, Alexander Korotin
Applied AI Institute, Moscow, Russia · AXXX, Russia · Yandex Research