Transducing
Language Models

Vésteinn Snæbjarnarson

PhD thesis, Department of Computer Science, University of Copenhagen, 2026

Read the thesis (PDF) Slides (PDF) Errata 212 pages, 11 MB. Last updated 31 August 2026.

Defence

17 November 2026, University of Copenhagen.

Advisors
Serge Belongie, Ryan Cotterell
Committee
David Chiang, Mirella Lapata, Anders Søgaard

Abstract

Language models assign probabilities to strings of symbols, but the distribution an application needs can be a different one. A model over byte-pair tokens does not directly expose word-level probabilities. A model over DNA sequences does not directly score sequences of amino acids. A model over cased text scores a lowercased string only as one casing among many. Post-processing the model's outputs can produce samples in the desired representation, but it does not by itself provide a probabilistic language-model interface over that representation. Such an interface would support scoring target strings, conditioning on target prefixes, and returning a next-symbol distribution over the target alphabet. We call this gap the string-mismatch problem.

This thesis addresses the string-mismatch problem by introducing transduced language models (TLMs). A string drawn from one distribution and pushed through a deterministic map is a draw from a new distribution. When that map is encoded by a finite-state transducer, we show how to compose the transducer with a pretrained language model. The resulting model has a full autoregressive interface over the transducer's target alphabet without retraining. We express a target-prefix probability as the source-model mass over the set of all source strings that map to that prefix or its extensions. We then show how this set can be decomposed so that its mass can be calculated more efficiently, and give sufficient conditions for a finite decomposition.

Exact enumeration computes the prefix probability by summing over the decomposition, but the number of terms may be prohibitively large. Dropping low-probability source prefixes from the enumeration reduces time and memory use but underestimates the TLM prefix probability. We remove this bias with a sequential Monte Carlo estimator based on reweighted sampling without replacement. The estimator terminates with probability one even when the decomposition has an infinite number of terms. In our experiments, it has lower variance and is more efficient than with-replacement SMC baselines.

The final research chapter applies TLMs to psycholinguistics, where surprisal theory predicts greater processing difficulty for linguistic units that are less predictable in context. The method lets us keep the pretrained model fixed and compute surprisal for units suited to the scientific question rather than only for the model's symbols. We demonstrate the approach on eye-tracking data with the model's own symbols, characters, and several notions of a word as units of analysis.

Papers in the thesis

Errata and clarifications

For the version of 31 August 2026. Items 1–8 and 10–12 come from the comments of the assessment committee, with my thanks.

  1. References to lines of algorithms print as the number of the enclosing section (pp. 36, 38, 39, 52, 55, 64, 73, 75).
  2. Section 3.1 (p. 18) assumes a total map. A partial map can be made total by adding a garbage state that emits a special symbol outside the target alphabet; the probability of that symbol is the source mass outside the domain.
  3. “Covers” is used without a definition. An output string covers y when it extends y. A source string x covers y when its image does, that is, when x is in the precover of y. A buffer (p. 42) is the partial output of one path and covers y when it extends y.
  4. Example 3.2 (p. 20) and later examples: arcs labelled with several symbols, such as ad:ungood, are shorthand for chains of single-symbol arcs.
  5. Proposition 3.2(3): the bound (|ΣX| + 1)|y| can be sharpened to |ΣX||y|.
  6. Example 3.4 (pp. 27–28): the loop at state 3 should copy its input, so that condition (i) of Lemma 3.1 holds; the quotient and remainder given are unchanged. Lemma 3.1 is meant to include partial functions, and the example is one.
  7. Section 5.1 (p. 63): the inclusion probability πi is the probability that particle i is in the selected set S. It is a design choice; ours is given in Eq. 5.11 (p. 68).
  8. Section 5.1.1 (p. 64): the twist is a parameter of the algorithm. All experiments use the live indicator (p. 78).
  9. “The bigram corpus” (pp. 84, 146, 147) means the ten WikiText-2 test paragraphs of Section 5.2.1, scored with the byte-level bigram model. That model is trained on the WikiText-2 training split.
  10. Section 6.4.2 (p. 100) and Table C.7 (p. 165): the zero-surprisal character observations are attributed to positions where the byte distribution is deterministic under BPE. They arise from the beam approximation of the byte-level model, at near-certain word completions.
  11. Section 6.5 (p. 103) and Chapter 7 (p. 106): the estimator gives unbiased prefix probabilities. Surprisals are logarithms of their ratios and are not unbiased (see Appendix C.6). The 106-nat difference is 1.4% of the corpus total of about 7,486 nats.
  12. Section 6.5 (p. 103): “leaves the PTB-word analysis unchanged” should read “the conclusions did not change”. No difference between the two estimators was detected; equivalence was not tested.