Transducing Language Models

This paper introduces a general framework for deriving new language models by composing pretrained models with deterministic finite-state transducers, enabling efficient probability marginalization and conditioning to adapt outputs to diverse formats like bytes, words, or amino acids without retraining.

The Gist

Imagine you have a brilliant, highly trained chef (a Language Model) who is an expert at cooking a specific type of cuisine. Let's say this chef only knows how to speak in "sub-word ingredients" (like "flour," "sugar," and "baking-powder").

However, the restaurant owner (the downstream application) wants to serve the dish in a different format. Maybe the owner wants the recipe written in "whole words" (like "cake"), or perhaps they want it translated into a completely different language, like "DNA sequences" or "bytes" (the raw code of the computer).

Usually, if you ask the chef to just "write it down differently," they get confused. They might try to force the ingredients into words, but the math gets messy. You end up with a recipe that says "half a cake" or "a quarter of a byte," which makes no sense.

This paper introduces a "Universal Translator" (a Transducer) that sits between the chef and the owner.

Here is how it works, broken down into simple concepts:

1. The Problem: The "Mismatch"

Modern AI models are trained to predict the next "token" (a chunk of text). But these tokens are often weird.

• Example: The word "hello" might be broken into "he" and "llo."
• The Issue: If you want the AI to predict the next letter (h, e, l, l, o) instead of the next chunk, the AI doesn't know how to do that directly. It's like asking a chef who only speaks French to write a menu in English without a dictionary.

2. The Solution: The "Translator Machine" (FST)

The authors built a machine called a Finite-State Transducer (FST). Think of this as a very smart, rule-based conveyor belt.

• Input: The AI's raw output (the sub-word chunks).
• The Machine: A set of rules that says, "If you see 'he' followed by 'llo', glue them together to make 'hello'." Or, "If you see the DNA code 'ATG', turn it into the amino acid 'Methionine'."
• Output: The clean, desired format (words, bytes, or proteins).

3. The Magic Trick: "Probability Math"

Here is the tricky part. If the AI says there is a 50% chance of "he" and a 50% chance of "llo," how do we know the probability of the combined word "hello"?

• The Old Way: You'd have to guess, or retrain the whole AI from scratch to learn this new format. That's expensive and slow.
• The New Way (This Paper): The authors figured out a mathematical way to sum up all the possibilities.
  • Imagine the AI is rolling dice to make a word. There are thousands of different ways the dice could roll to spell "hello" (e.g., "h" + "ello", "he" + "llo", "hel" + "lo").
  • The "Translator Machine" acts like a super-scientist. It looks at every single way the AI could have produced "hello," adds up the probabilities of all those paths, and tells you the true probability of "hello" appearing.

4. The "Quotient and Remainder" (The Shortcut)

Calculating every single path is impossible because there are too many (like trying to count every grain of sand on a beach).

• The Analogy: Imagine you are counting money in a jar. Instead of counting every single penny, you group them.
  • The Quotient: These are the "safe bets." If the AI says "he," we know for a fact that any ending will result in a valid word starting with "he." We don't need to check the rest; we just count the whole group.
  • The Remainder: These are the "edge cases." Maybe the AI said "he," but if the next letter is "x," it's not a word. We have to check these specific, tricky paths individually.
• The Result: The authors created an algorithm that quickly separates the "safe bets" from the "tricky cases." This lets them calculate the answer almost instantly without checking every single grain of sand.

5. Why This Matters (Real World Examples)

The paper tested this on three different "chefs":

1. Text to Bytes: Turning a model that speaks in "chunks" into one that speaks in raw computer code (bytes). This is great for fixing typos or understanding how computers actually see text.
2. Text to Words: Turning a model that speaks in "chunks" into one that speaks in proper "words" (like a dictionary). This is crucial for psychology research to understand how humans read.
3. DNA to Proteins: Turning a model that reads DNA letters (A, C, G, T) into a model that predicts the resulting proteins (the building blocks of life). This helps biologists design new medicines without retraining the AI.

The Bottom Line

This paper is like giving a universal adapter to any AI.

• Before: If you wanted an AI to speak a different "language" (format), you had to build a new AI from scratch.
• Now: You can take any existing AI, plug in this "translator machine," and instantly get a new AI that speaks exactly the format you need, with perfect math behind it, all without retraining a single neuron.

It's a way to make powerful AI models flexible and adaptable to any job, whether that job is writing code, translating DNA, or just writing better English.

Technical Summary

Here is a detailed technical summary of the paper "Transducing Language Models" by Snæbjarnarson et al.

1. Problem Statement: The String Mismatch Problem

Modern Large Language Models (LLMs) define probability distributions over sequences of tokens (often subword units like Byte-Pair Encoded tokens). However, downstream applications often require outputs in different formats, such as:

• Characters/Bytes: For psycholinguistics, spelling correction, or low-level control.
• Words: For linguistic analysis requiring orthographic boundaries (e.g., Penn Treebank guidelines).
• Amino Acids: For computational biology (converting DNA sequences to protein sequences).

The Core Challenge:
While sampling from a transformed distribution is trivial (sample a token sequence, apply the transformation), other operations become intractable. Specifically:

1. Scoring: Calculating the probability of a specific transformed string $P(y)$ requires summing the probabilities of all source strings $x$ that map to $y$ (the preimage $f^{-1}(y)$). This set can be exponentially large or infinite.
2. Conditioning: Computing the next-symbol distribution $P(y_{t+1} | y_{1:t})$ requires marginalizing over all source prefixes that map to the current target prefix.
3. Adaptation: Existing solutions often rely on ad-hoc post-processing or retraining models, which is computationally expensive and loses the original model's learned distribution.

2. Methodology: Transduced Language Models

The authors propose a framework where a Transduced Language Model ($p_Y$) is defined as the composition of a source Language Model ($p_X$) and a deterministic string-to-string transformation ($f$), encoded as a Finite-State Transducer (FST).

$$p_Y(y) = \sum_{x \in f^{-1}(y)} p_X(x)$$

To make this computationally feasible, the paper introduces a Prefix Decomposition strategy.

A. Theoretical Framework

Instead of summing over the infinite set of source strings, the authors decompose the precover $P(y)$ (the set of source strings $x$ such that $y$ is a prefix of $f(x)$) into two disjoint sets:

1. Quotient ($Q(y)$): A prefix-free set of source strings where every extension maps to a string starting with $y$. For these strings, the probability contribution is the prefix probability of the source model ($\vec{p}_X(x)$).
2. Remainder ($R(y)$): A set of source strings that map exactly to $y$ (or a prefix of $y$) but do not cover all extensions. For these, the contribution is the string probability ($p_X(x)$).

The prefix probability of the target is then:
$$\vec{p}_Y(y) = \sum_{x \in Q(y)} \vec{p}_X(x) + \sum_{x \in R(y)} p_X(x)$$

B. Algorithms

The paper develops algorithms to compute $Q(y)$ and $R(y)$ efficiently using the structure of the FST:

1. Exact Decomposition (BFS):

   • The algorithm performs a Breadth-First Search (BFS) on the source strings.
   • It maintains a "frontier" of transducer states and output buffers.
   • For each candidate string $x$, it performs three checks:
     • Is Cylinder? Does every extension of $x$ map to a string starting with $y$? If yes, $x \in Q(y)$.
     • Is Member? Does $x$ itself map to a string starting with $y$? If yes (and not a cylinder), $x \in R(y)$.
     • Is Live? Can $x$ be extended to eventually cover $y$? If no, prune.
   • Optimization: The algorithm uses Lazy Determinization and Frontier-based checks to avoid explicitly constructing the massive determinized automaton. It also employs IP-Universality shortcuts (Input-Projection Universal states) to instantly classify strings as cylinders without full BFS.

2. Approximation via Pruning:

   • When the decomposition is too large, the algorithm sorts candidates by their source prefix probability and discards those with low cumulative mass (controlled by a threshold $\tau$).
   • This provides a lower bound on the probability, with the error vanishing as $\tau \to 0$.

3. Finiteness Conditions:

   • The paper proves that if the transducer is strict-prefix monotone (e.g., token-to-byte), the remainder is empty and the quotient is bounded.
   • For non-monotone transformations (e.g., Penn Treebank tokenization), the paper provides sufficient conditions (Safety) involving IP-universal states and finite closure to guarantee finite decomposition.

3. Key Contributions

1. Formal Framework: A rigorous definition of language models derived from deterministic string-to-string transformations, treating the transformation as a first-class component rather than a post-processing step.
2. Efficient Algorithms:
   • An exact algorithm for computing prefix probabilities and next-token distributions via quotient-remainder decomposition.
   • A practical approximation algorithm using probability-mass pruning.
   • Optimizations like lazy determinization, frontier tracking, and IP-universal shortcuts that significantly speed up inference.
3. Theoretical Analysis: Characterization of when exact decomposition is possible (finiteness conditions) and the relationship between prefix monotonicity and decomposition size.
4. Interoperability: The resulting transduced models maintain the standard autoregressive interface (next-symbol distributions), allowing them to be used with any system designed for standard LLMs.

4. Experimental Results

The authors evaluated the framework on three distinct domains using models like GPT-2, LLaMA 3, and Phi-4:

1. Tokens to Bytes:

   • Result: Achieved near-identical distributions to exact baselines (Jensen-Shannon Divergence < $10^{-4}$) with moderate pruning ($\tau \le 10^{-3}$).
   • Performance: Throughput ranged from ~1 to 80 bytes/sec depending on the pruning threshold.
   • Observation: This transformation is strict-prefix monotone, resulting in empty remainders and high efficiency.

2. Tokens to Orthographic Words (Penn Treebank):

   • Result: Successfully modeled context-sensitive word boundaries (e.g., handling "Dr." vs. "3.50").
   • Challenge: This transformation is not prefix monotone, leading to non-empty remainders and larger decomposition sizes.
   • Performance: Lower throughput compared to token-to-byte due to the complexity of the remainder set, but still feasible.

3. DNA to Amino Acids:

   • Result: Converted a DNA language model to an amino acid model.
   • Challenge: The mapping is combinatorial (3 nucleotides $\to$ 1 amino acid), causing the candidate set to grow exponentially.
   • Mitigation: Used candidate-set capping ($n_{max}$) alongside pruning.
   • Performance: Demonstrated that practical approximations are sufficient for biological sequence modeling.

Key Finding: The proposed approximation (pruning) yields high-quality estimates (low JSD) at a fraction of the computational cost of exact enumeration.

5. Significance and Impact

• Retraining-Free Adaptation: Allows practitioners to adapt powerful pretrained models to specific output units (bytes, words, proteins) without the cost of fine-tuning or retraining.
• Theoretical Unification: Bridges the gap between probabilistic language modeling and formal language theory (finite-state transducers), providing a principled way to handle "string mismatch."
• Applications:
  • Psycholinguistics: Enables accurate calculation of word-level surprisal from subword models.
  • Bioinformatics: Facilitates the use of LLMs for protein design and analysis without retraining on amino acid sequences.
  • Controlled Generation: Allows for strict adherence to output constraints (e.g., valid chemical formulas, specific grammatical structures) by composing with appropriate FSTs.
• Future Directions: Opens the door to leveraging advances in finite-state methods for LLM adaptation, including potential applications in self-consistency reasoning and marginalizing over multiple valid interpretations of a prompt.

In summary, this paper provides a mathematically sound and computationally efficient toolkit to "transduce" existing language models, enabling them to speak the "language" required by specific downstream applications while preserving their original probabilistic knowledge.