# Transducing Language Models

arXiv: https://arxiv.org/abs/2603.05193 · HTML: https://mlsanity.com/paper/2603.05193/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 62 references that are in the map.
- First posted on arXiv 5 Mar 2026.

## Builds on (most cited first, 25 of 25)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [Efficient Guided Generation for Large Language Models](https://mlsanity.com/paper/2307.09702/) (2023)
- [HyenaDNA: Long-Range Genomic Sequence Modeling at Single Nucleotide Resolution](https://mlsanity.com/paper/2306.15794/) (2023)
- [Fast WordPiece Tokenization](https://mlsanity.com/paper/2012.15524/) (2020)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [How to Compute the Probability of a Word](https://mlsanity.com/paper/2406.14561/) (2024)
- [From Language Models over Tokens to Language Models over Characters](https://mlsanity.com/paper/2412.03719/) (2024)
- [Analyzing Cognitive Plausibility of Subword Tokenization](https://mlsanity.com/paper/2310.13348/) (2023)
- [Leading Whitespaces of Language Models' Subword Vocabulary Pose a Confound for Calculating Word Probabilities](https://mlsanity.com/paper/2406.10851/) (2024)
- [Where is the signal in tokenization space?](https://mlsanity.com/paper/2408.08541/) (2024)
- [Understanding and Mitigating Tokenization Bias in Language Models](https://mlsanity.com/paper/2406.16829/) (2024)
- [Words, Subwords, and Morphemes: What Really Matters in the Surprisal-Reading Time Relationship?](https://mlsanity.com/paper/2310.17774/) (2023)
- [On the Proper Treatment of Tokenization in Psycholinguistics](https://mlsanity.com/paper/2410.02691/) (2024)
- [Model Decides How to Tokenize: Adaptive DNA Sequence Tokenization with MxDNA](https://mlsanity.com/paper/2412.13716/) (2024)
- [Language Models over Canonical Byte-Pair Encodings](https://mlsanity.com/paper/2506.07956/) (2025)
- [Sampling from Your Language Model One Byte at a Time](https://mlsanity.com/paper/2506.14123/) (2025)
- [Neural Grammatical Error Correction with Finite State Transducers](https://mlsanity.com/paper/1903.10625/) (2019)
- [Constructing a BPE Tokenization DFA](https://mlsanity.com/paper/2405.07671/) (2024)
- [Syntactic Control of Language Models by Posterior Inference](https://mlsanity.com/paper/2506.07154/) (2025)

## Built on by (most cited first, 5 of 5)

- [On the Proper Treatment of Units in Surprisal Theory](https://mlsanity.com/paper/2604.28147/) (2026)
- [Surprisal Theory is Tautological (without Rational Grounding)](https://mlsanity.com/paper/2607.21574/) (2026)
- [Stochastic Estimation of Transduced Language Models](https://mlsanity.com/paper/2608.27428/) (2026)
- [Revisiting the Estimation of Unigram Surprisal in Computational Psycholinguistics](https://mlsanity.com/paper/2610.18414/) (2026)
- [Estimating Surprisal from the Speech Signal](https://mlsanity.com/paper/2610.18439/) (2026)

## Abstract (arXiv)

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.