Transducing Language Models
Authors: Vésteinn Snæbjarnarson
Samuel Kiegeland
Tianyu Liu
Reda Boumasmoud
Ryan Cotterell
Tim Vieira
Venue: ICLR 2026 Poster (2026)
Keywords: language models
tokenization
automata
transducers
Primary area: foundation or frontier models, including LLMs
TL;DR: We present a method for converting a language model over one set of tokens into a language model over another set of tokens

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.

TRANSDUCING LANGUAGE MODELS
Vésteinn Snæebjarnarson' 2.R. Samuel Kiegeland 2 2,
Tianyu Liu
Reda @ Ryan Cotterell
Tim Vieira @ X CHI-FRO
2ETH Zürich R University of Copenhagen
{vest. snae, tim. f. vieira)@gmail com (samuel. kiegeland, Banyu.liu, ryan. cotterelt @@inf. www.f..eth......m ch
reda. bowmasmoudemathh ethz. ch
ABSTRACT
Modern language models define distributions over strings, but downstream tasks often require different output formats. For instance, 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-iniing transformation desired form. This is a familiar pattern in probability theory: applying function f to random variable X p yields transformed random variable f(X) with induced distribution. While such transformations are occasionally used language modeling, prior work does not treat them 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 used machine abstraction for efficient string-to- toonggtt-stteee to-string mappings. We develop algorithms that compose language model with 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 theoretical analysis. We conduct experiments in three domains: converting language models from tokens to bytes, from tokens to words, and from DNA amino acids. These experiments demonstrate inference-ting time adaptation of pretrained language models to match application-specific output requirements.
convert the model's 's output to the
commonly
INTRODUCTION
Language models (LMs) define distributions over strings. Yet, the strings they produce often do not match the requirements of downstream applications, so practitioners resort to ad hoc post-processing. We call this the string mismatch problem. For example, natural language processing. modern lan- guage models typically generate byte-pair encoded strings (Sennrich et al., 2016), while downstream tasks may require words or characters instead (see Ex. (2), below). Similarly, DNA language models generate nucleobase sequences, whereas many applications require amino acid sequences (Ex. (5)).
Adding a string-to-string transformation to generation pipeline is a common engineering solution, such as normalizing output mapping subword tokens to bytes. Formally, this defines new language model over transformed strings. However, while sampling remains straightforward. other operations-suce transformed outputs- intractable. Consider, for instance, the mapping from a string in any casing to its lowercase version, in the use-case depicted in Fig. While lowercasing given input is trivial, converting the original distribution to distribution over lowercased words is not.
computing the probability of transformed string or conditioning
This work treats Ltringtto-string transformations first-class component of the language modeling pipeline. We show how to equip these transformed models with the familiar autoregressive interface- incremental next-symbol distributions and prefix probabilities-makine them interoperable with
Equual contribution.

---

any system built for standard autoregressive language models. This approach to the string mismatch problem is principled. modular, and can substantially cheaper than retraining. Moreover, the transformations often guarantee adherence to the requirements of the downstream applications.
Consider language models over English text-the same utterance can be encoded in many ways. For example,
Hello
4.1e
hello
3.
(1) Dr. Lemaître was flabbergasted.
HE LL
1.94-08 0
The byte-pair encoding used by GPT-4o (OpenAI, 2024) encodes Ex. (1) the following string of subword tokens:
hell
3.4e-10
Hell
1.8e-00
H ello
IJle10
Dr
_L
ema
\C3NAEtre
Lws
_fl ab
(2)
5822
451
4683
29135
673
1548
hell |0
7.4e122
berg asted LAFON9FVA4
XAF
Hell 0
7:2c-12
9667
23838
93643
187
he 1lo
4.7e-12
The byte-pair segmentation of Ex. (1) into subwords is based on character substring frequency. However, many applications seek different units. For instance, computa-
Hel lo
40e-12
tional psycholinguistics (e.g.. Giulianelli et al., 2024) and controlled generation (e.g.. Lew et al., 2023; Xefteri al., 2025) both require custom units. This also holds if one wishes derive distributions over words, such as those defined by the Penn Treebank (PTB) annotation guidelines (Marcus et al., 1993), a variation of which is shown below:
hello
4.6
Figure GPT-2 probabilities for the BPE token strings that, when lower- cased, match hello. The total probabil- ity of all such sequences is at the bottom.
(3) DR. LEMAÎTRE WAS FLABBERGASTED
For other applications, e.g., spelling correction, we might also wish represent Ex. (2) using string of characters or UTF-8 byte representation as follows:
r pr. m a AC3YAE r 68 189 195
a
NF0N9FNA4
(4)
144
118
188
114
181
948 175
In genetics, we have another example of varying representations. Consider the DNA sequence given in Ex. (5). The sequence is one of many that translate into the hormone oxytocin, typically written as the amino acid sequence Ex. (6), as represented below:
(5) TGTTACAT A CAAACAAATTTT AAAAAAATTCCTCTCTTTCCCCCCCC GGT
(6) CYIQNCPLG
Transforming a language model is generally non-trivial. Even transformations with simple colloquial descriptions can be hard to apply. The conversion to bytes (ex. (4)) can be performed using a lookup table that specifies the sequence bytes a subword token maps to. Similarly, the conversion from DNA to protein sequences (ex. (5)) relies on mappings from three-letter sequences of DNA bases to single amino acid. The grammatical word segmentation (ex. (3)) cannot be described as easily; it requires lookahead to determine whether, c.g., punctuation should stand alone, if it is part of the 'DR.' title, or a decimal number '3.50'. Simple rules alone do not ensure exact conversions. Despite their simplicity, the byte and amino-acid transformations are not straightforward: the number of token sequences that map to each output sequence grows exponentially over the length of the output, and a proper language model transformation must account for all source-sequence probabilities. ? The decimal and title examples highlight another level of complexity, where the transformation rules require careful analysis of the surrounding context. Recent papers have thus focused on practical methods for specific subsets of these transformations, in particular for estimating byte-level probabilities from subword models (Phan al., 2024; Vieira et al., 2025a: Hayase al., 2025).² We generalize these approaches to handle all of the examples given above.
This work introduces framework for string-to to-string conversion using Unite-state transducers (FSTs). FSTs encode powerful yet tractable family of relations, including those mentioned above. We com-
Note that UTF-8 allows multiple encodings of some strings. For example, the character can be encoded composed (AE) or decomposed (i (CC)82). See https://unt code. htgg/rpprrt//rr1:
"This can also be seen in Fig. where exponentially increasing number of input prefixes map to given output prefix: with each additional symhol on the output, the numher source sequences doubles.
Our approach is most similar to that of Vieira et al. (2025a), which considers the case of strict-prefix monotone transformations ($6), which includes the subword-to-byte transformation.
2

---

pose pretrained language models with transducers that encode such transformations, and refer to the compositions as transduced language models. FSTs provide explicit structure for tracing how proba- bilities from the original model should map to output sequences. This allows us to develop exact and approximate algorithms for efficient sampling, scoring, and conditioning on transformed strings, all without modifying the underlying language model. We give sufficient conditions for when the transfor- mations can be made exactly ($6) and approximations when exact transformations are infeasible ($5).
To validate our approach, we construct FSTs for the three use cases above: (i) converting tokens to bytes, (ii) inserting orthographic boundaries following the Penn Treebank tokenizer, and (iii) converting DNA sequences to sequences over amino acids. We then employ commonly used pretrained language models over the input units of the FSTs, and compose them with the FSTs to obtain language models over the output tokens. Finally, we use these settings to benchmark the theoretical and algorithmic contributions. In particular, we find that using practical approximation sufficient to obtain a good estimate a fraction of the computational cost.
2 BACKGROUND*
Strings. Let X' be an alphabet (i.e., a finite, non-empty set). Let X denote the set of all finite strings over X, including the empty string Ex.. When there is risk of ambiguity with other alphabets, we simply write E. We use a, x' E X to denote strings and Z' C X to denote sets of strings. Let war denote concatenation. Similarly, we define the concatenation of sets of strings as Zz' _े' {axx I E Z. x' E Z"), and in the singleton case as z _ {a Z', and Zx' de ZZ We write x 3 x' when x is prefix of x', and x < x' when it is strict-prefix. Conversely, if x I x', we say x' is an extension of x (a strict extension when 2 < x')
Language models. A language model px is probability distribution over set of strings X Let EOS & X be a special end-of-string symbol. We define the prefix probability of px as the probability that string X ~ px starts with given prefix æ, and the conditional prefix probability:
px(a' 1x) del PA (xx')
der (x
p2(()) de Px(xx')
PXOS
x))
(x)
px(x)
--E
when px(x) > 0; otherwise we set (x' ()) and px (FOS) x)) 1. Therefore, p. m)
is probability distribution over X Ll [FOS} for all æ E X Using this structure, any language model px may be factorized as (x(())
(1 .<t). This factorization defines a left-to-right generative process: starting from a = E, we repeatedly sample x' ~ p-(( m);
(EOS x) x)
if x' = FOS, we stop, otherwise we update x to aa. Conditional generation simply starts from the conditioning prefix instead of the empty string. We refer to the quantities in Eq. (1) as the autoregressive interface to the language model px.
Cylindrical sets. A cylindrical set is the set of all strings with given prefix. Let Z,Z' C X*: define the cylinder over 7 (Z) & Zx" We say that Z is cylindrical if Z = (Z). The union of cylinder sets is again a cylinder set, since cylinders are upward-closed. We define the basic cylinder for æ as (xr) del ((z)). The prefix-base operation pf( is defined by (2) del fxr Z: d E Z: x < æ): this operation uniquely partitions (Z) into basic cylinders over pZ) We say that Z is prefix-free if pf(Z) = Z. Since pf( is frefix-free, the basic cylinders ((x) x E pZ)) are pairwise disjoint, and (Z) Leeep((2) (z))
transducer a state-machine that encodes string-to-string relations X" x ) When we express a relationship defined by f as transducer, we expose the computational structure needed to develop efficient algorithms. Formally, finite-state transducer (FST) f is tuple (S, F, T) where S is finite set of states and X' and ) are alphabets of input and output symbols, respectively. The sets I, C S are the initial and accepting states. TC x (X U {=}) (Q'U (E)) x S is set of transitions. We render transitions (s, 2. y. s') E T as 8 any s': we say the transition scans x and emits y. We write T(s) for the set of outgoing transitions from state s, and T(s, .r) for those that scan z. The transducer f defines a set of paths II. Each
Transducers.
A provides notation glossary.
We refer Pin (2021, Ch. & 3) for a detailed treatment of transducers.
L.e.. T(s") del {(s "i 8') T: 8 s"}, and T(s", x") ((s s", T: =
3

---

path π II is sequence of transitions of the form So We call π an accepting path if &n E and SN E The relation defined by is given by [[]] S {(r,g)
51 22:02
S2 SN-1
SN:UN
SN-
E II: So E 1, E F), i.e., each accepting path contributes (not necessarily uniquely) pair of scanned and emitted strings. When every transition of transducer scans and emits the same symbol (x y), the machine acts finite-state automaton (acceptor) that recognizes a language L C X - the set of strings admitted by at least one accepting path. Such machine is a nondeterministie finite automaton (NEA) in general; it is deterministic finite automaton (DFA) if it has single initial state, no e-transitions, and at most one transition per state and input symbol. Every NEA can be converted an equivalent DFA by determinization (Rabin & Scott, 1959). For completeness, B provides additional background.
-3:1, SN-1 SNWN,
3 TRANSDUCED LANGUAGE MODELS
transduced language model py arises from applying a string-to striigg transformation f: X - ) encoded by transducer f. to a string drawn from source language model px. Formally, if
X ~ px, then f(X) has the following probability mass function:
py(y)
def
Pr ly f(X)) E>xExxee px(x) X-px
(2)
where (y) is the preimage of y. (y) (x X" y= f())). Put differently, in Eq. (2),
we sum over the strings z such that f(x) y. Unfortunately, evaluating py()) exactly using Eq. (2) is generally infeasible (since the preimage (yyy can be very large), even though exact sampling from Py is efficient (by sampling
px and applying f). Like all language models. transduced language model py has prefix and conditional prefix probability functions; its prefix probability
T = Pr ly 3 S(X) Xmpx
Σpx(2)
xEP(())
where Pιy) is the precover of y. with respect to defined as P(y) dnd (EE x y f(x)).
Prefix probabilities yield a conditional factorization of string probability (see $2), enabling efficient left-to-right autoregressive generation. We develop method $4 that allows us to compute the sum in Eq. (3) in finite time for a general class of mappings, such as those mentioned in the introduction (i.e., normalizing text, inserting orthographic word boundaries, or converting DNA amino-acid sequences). In $5, we present algorithms to compute these quantities.
4 DECOMPOSING THE PRECOVER
In $3, we saw that if we can sum over the precover of we can calculate (3)) (Eq. (3)), unlocking an autoregressive interface the transduced language model. The following two examples illustrate how we can often compute this infinite sum by exploiting structural properties of the transducer.
Example 1. The transducer below lowercases a string. For the target string ab, the precover is the infi- nite set Paab) ([AB, Ab, aB, ab)). Given model Pxx over the input language, the derivation on the right (4a-4c) applies Eg. (3) to express p (ab) as sum of four source- lanrege prefix probabilities:
p3(ab)=
Σ px(x))
(4a)
A:a ::b
a:a
b:b
#aP(ab)
:
Σ
Σ px(x))
(4b)
Z: z
Z:Z
''E (AB,Ab, abb) m=(''')
= (AB) + Pxx (Ab) + px + 7
(4c)
In Example 1, each input symbol maps exactly one output symbol, so the precover decomposes neatly into cylinders. The next example shows what happens when some source strings cover the target string, while their extensions do not.
NNote that the precover depends on fi we suppress this dependency when it is clear from context.
4

---

Example 2. The transducer below implements newspeak* rewrite rule: the word bad is replaced by ungood. For the target string ba, the precover does not decompose neatly into cylinders: since bad does not map to a string prefixed by ba, the cylinder (bad) does not contribute to py (ba). The derivation on the right (5-5c) shows how this cylinder is excluded."
ad: ungood
(b((ba) =
E
(x(
(5a)
b
#r (ba)) ((ood)
big
{b,
a
Σ
px
(5b)
b
3
=EU.EXi10) (ban)
{b, d)
b:E
=px(ba)) +
Σ px((bar)
(5c)
X (b)
b:
Because bad (ba) but bad & P(ba), the precover cannot be decomposed entirely into cylinders. In- stead, we decompose into two disjoint parts: a maximal cylindrical subset and its complement the precover. The quotiení collects the shortest element of each cylinder; the complement is the remainder. The final step (5c) illustrates a computational shortcut; for any y we can decompose (y)):
p)(1)= =
Σ px(+) +
Σ
(x(x)
(6)
=EQ(U)
ZER(S)
Quotient
Remainder
The precover can also be represented as an FSA, as shown below for P(bba.. The single string accepted at R (teal node) marks the remainder element ba while the state Q (yellow node) accepts (ba - (X' \ {d})) and marks the cylinder over the quotient.
b
a
R
X
{d)
Q
X
We now formalize the remainder, quotient, and decomposition for any string-to to-string function f. ) be map. For each y E y²* define
X' + The prefix decomposition of the precover. Let f C(y) del (a E X"; (x) S P(y)); this set is a cylinder-if æ E Cly) then every extension of æ also belongs to C(y) making it the largest cylinder contained in P(y)- We define the quotient and remainder of y with respect to f as
(7) We call the pair (Q(y): R(y)) the optimal prefix decomposition of P(y), characterized by three conditions: (i) Quy) is prefix-free, (ii) P(y) = (Q(y)) I R(y) (validity), and (ii) (Q(z)) = C(y)
( del pf(()
and R(y) P(y) \ C(y)
(maximality) identifies the largest cylinder in Ply). This decomposition (indeed, any valid one) lets compute prefix probabilities using the shorteut:
(v) = Σ (x((2)= = Σ px(x) = Epe(ax)) + Epr(#)= = Epr(#)+ Epr(a) Epr(a)) (8a)
=EP(N) REC())
xEQ())
*ER(y)
zEQ(3)
#ER(v)
x'EXx
$5 provides an algorithm for computing the prefix decomposition; $6 identifies when it is finite.
5 ALGORIHTM
We now present an algorithm for computing prefix decompositions by exploiting the explicit structure of transducer that encodes the function. Combined with the computational shortcut (Eq, (6)), this gives an autoregressive interface to transduced language models. We first describe the algorithm abstractly, then instantiate its checks using transducer, and finally discuss optimizations.
Newspeak the controlled language from Orwell's 1984 (Orwell, 1949); the example bad + ungood canonical. complete Newspeak transducer is left as an exercise for the Party. Ares labeled by a single symbol are copy transitions, e.g., is shorthand for b b; set label such as X' x (b} denotes copy-transition are per symbol in the
5

---

Fig. 2 gives the decomposition algorithm (decompose), which maintains a queue of candidate source strings and explores them by breadth-first search (BFS), optionally pruning www-robbbbiityy candidates at each step (described below). 10 Each dequeued string a: undergoes three checks, defined in terms of the precover Pyy):
def decomposely): memoize N < y) if . 0: q QUEUE((E))
else:
(Q', decompose(U<xN)
q +- QUEUE(Q' UR)
1. Cylinder:
is_cyl snylindr((a, y) < (x)) S P(y), i.e. every extension of æ covers y. æ is added to the quotient set Q and not explored further (line 12).
(Q, (0,0)
while [q] 0:
q' +
2. Member: is_men (z_mmmerr(,, y) = a E Ply). i..., a itself false but is_ s__member
for x e q:
covers y. When is_ ss_ccllndde true, æ is added to the remainder set R; its extensions are still explored (line 15).
if is is_cylinder(at y):
Q. (a)
3. Live: s_,,ive y/ === E X²: xx" E P(y). i.e., some extension of æ: belongs to the precover. Only live extensions enqueued (line 18).
continue
if is js_member(( (2, y):
R. add(())
for x' E X::
Because strings are processed chortest-first. if any prefix of the current string had already entered the quotient, the cur- rent string would never have been enqueued. Once the queue is exhausted, the algorithm returns the prefix decomposition. We instantiate these checks concretely in $5.1.
18
if is_live(æx' y):
q' (adar"))
q + prune(q')
20
21
return (Q.R)
Figure 2: Decomposition algorithm.
Theorem 5.1 (Correctness of decompose). Py)) admits a finite decomposition and the three checks exactly implement the conditions above with no pruning. then decompose yy terminates and its output (Q,R) is the optimal prefix decomposition (Eq. (7)).
Proof. We verify the three conditions of the optimal prefix decomposition (Eq. (7)).
1. Prefix-freeness (Q is prefix-free)) When is_ cylinderr succeeds for (line 12), the continue (line 14) skips the extension loop, so no ær' is enqueued. Since strings enter the queue only as single-symbol extensions of dequeued strings, no extension of is ever enqueued dequeued, and thus no two elements of Q share a prefix.
2. Validity (P(y) = (Q) L R): Let E Ply); we first show that æ E (Q) U. We show by induction on prefix length that either a prefix of æ enters Q or itself is dequeued and added to Q or The base case holds: is enqueued. If æeck is dequeued and not placed in Q then Øc is enqueued by the extension loop: since F<k++1 I x and Ply), we have is__ive(x=<t+1, (line 18). By induction, either some prefix Øzj enters Q-giving E (æ<x) C (Q)-or æ: itself dequeued, the cylinder check fails, and a E Py)) gives x via is_member (line 15). The reverse direction is clear since elements of Q pass the exact is cylinder check, (Q) C P(y). Similarly, elements of pass is js_member, so C Ply). What remains to show that (Q) and R are disjoint. If æ E R, then was dequeued and is cyllndeee failed, x in Q either
o Q. No proper prefix of æ would never have been enqueued pmefix-freeness) Hence x & (Q).
3. Maximality ((0) = C(y)): shortest-firg first processing ensures no proper prefix of quotient element satisfies _s_cylindes (line 12), so Q the minimal prefix-free set of cylinders. Together with the exact cylinder check, the earliest qualifying prefix is always found, as required by Eq, (7). It remains to show C(y) S (Q). By validity, Ply) = (Q) LIR. Every element of fails is_cylinder, so ( 0. Hence C(v)= C (0).
Termination: is_live (line 18) ensures only viable extensions are enqueued; finiteness of the decomposition guarantees the queue empties.
Conservative checks and suboptimality. If the checks used by decompose are conservative approximations, the algorithm may produce suboptimal decompositions- quotient than the optimal one. A conservative liveness check (false positives) enqueues unnecessary extensions but does not affect classification: every dequeued string is still correctly classified by is_cy cc. inder and is_ __memer,, so the result remains optimal. A conservative cylinder check (false negatives) may fail to recognize some quotient elements, placing them in R instead. The decomposition
but with smaller
Foro efficiency, decompase should be memoized. For |ı| > 0. the recursive call decompose(y seeds the queue with the previous decomposition q' U R' rather than enumerating from

---

remains valid, but because successful cylinder check terminates exploration of that subtree (line 14), missing a cylinder means the BFS continues exploring extensions that would otherwise have been cut off, potentially inflating the remainder and increasing the computation. By contrast, the membership check must be exact to preserve validity.
Approximation via pruning. When the prefix decomposition becomes large, exhaustively enu- merating and scoring can become infeasible. In these cases, we use a pruning strategy (prune) that sorts candidates by prefix probability and removes those whose cumulative probability mass falls below a specified threshold т. This discards low-probability candidates to keep decomposition tractable. Since pruning only removes candidates from the queue, every element found is correct (0) U S -ut) the decomposition is no longer valid in general (coverage may be incomplete), so the computed prefix probability a lower bound on the true value. Our strategy is detailed in SC.3.
5.1 GETTING STARTED: INSTANTIATING THE CHECKS WITH THE PRECOVER MACHINE
We now show how instantiate the three checks (Fig. 2) using finite-state transducer. This serves as a pedagogical introduction; &C describes a more detailed, but faster algorithm.
We represent the transformation f with transducer f (see $2 and B). Given target prefix y. projx (f y)* is an NFA that accepts exactly (vy) To enable the efficient state-based checks below, we determinize and trim this NEA to obtain DFA: P. del trim crim(determinizeeprg (proj, (f (foo y)* )))
Let Sy. ly, Fy. and Ty denote the components of p.. Since Py is deterministic, scanning a source string 21 rM ZN yields unique state, which denote by runy(æ)). We now describe how to implement the three checks using Py (pseudocode in Fig. 3).
Cylinder: We need to check whether (a) C P(y) to decide if Q(v). Let S = (z) be the unique state reached after scanning æ. Since Py is deterministic, (ar) C P(y) if and only S is universal: [Py ||]] X", meaning every continuation of x: is accepted. The is_cylinder
check (Fig. 3) tests universality via breadth-first search (BFS) from S.
Member: When the is_cy ss_cylinder check fails for æ with S = runy (æ), we need to determine whether the scanned string æ is in R(y). Here it suffices to check if S E y. i.e. if accepts æ.
Live: We construct Py as a trimmed automaton accepting x where y N f(x). Trimming ensures that every reachable state lies on some accepting path, so liveness reduces to run,(z) * 0.
Although decompose is written in terms of source strings, each check internally computes the state S (3) reached by scanning æ in the deterministic Pa,, and reduces to state property.
5.2 OPTIMIZATIONS
The algorithm above is correct but impractical for large transducers. In $ C, describe several optimizations; we summarize the key ideas here.
Lazy determinization. Eagerly determinizing Py is often computationally expensive. Instead, track frontiers: sets of transducer states reachable after scanning a source prefix, paired with the output emitted so far. Frontiers lazily perform the subset construction (the standard NFA-to-DFA conversion; Rabin & Scott, 1959) and the composition with y>' simultaneously, avoiding both eager determinization and eager composition. The three checks-cylinder member, and liveness are now defined in terms of the frontier rather than a single DFA state ($C.2)
Incremental next-symhol decomposition. To efficiently compute py (y' | y for all y' E E) introduce decompose_nexe next(< ($ C.4). which derives the decomposition of each extension yy' from the decomposition of y. operates in a single BFS pass that handles each y' y simultaneously.
Decomposition shortcuts. Many structural properties of the decomposition allow the BFS to skip work: non-cylinder monotonicity (Prop. C.3), cylinder uniqueness (Prop. C.4), input- projection universality (S (SC.6), combined universality (Prop. C.5), and an all-universal fast path (Fig. 14).
Lazier enumeration. Rather than explicitly composing the transducer with the copy transducer y)a" the frontier- based algorithms track output buffers directly, performing the composition lazily and avoiding the materialization cost. Additionally, we precompute states whose input projection
Thiss also he expressed P(y) = f( (y)"") [proj y)"
7

---

def (t,
x2 def iy_cylinder(x.g):
return (s, # deterministic def (
33
# Run BFS to find a counterexample:
34
# nonaccepting or incomplete state
S < rany(
V t {S}; q QUEUE((S))
2s if N return by unique return (re,)(run(((<w))22)))
36
while q:
S < q. pop()
27 def is (s__mmbbe((x,)))
38
if Fy: return False
return runy (x) E Fyy
for x' E
S' + step,,(S,z))
40
def is is_live(x, y):
20 not in failure state
41
S' = return False
if S' & V: q.add(S"); V add(
return (un +
43
return True
No counterexamples
Figure State-based instantiation of the checks from Fig. on the precover DFA Py. Helper functions step and run advance through the DFA; is s__mebeer and is live are single-state lookups; is_cylinge performs a BFS to verify universality.
accepts all of X' (6.. When a frontier reaches such state with buffer that already covers y, the cylinder check succeeds immediately, bypassing the expensive check.
Label pushing. As standard preprocessing step (see, e.g., Oncina al., 1993; Mohri, 2003; 2009), we push output labels toward the initial state of f: when every path through state emits output beginning with y, that is shifted to the incoming are so it is produced one step earlier. This ensures that output is committed early as possible, speeding up the frontier-based cylinder check.
SUFFICIENT CONDITIONS FOR FINITE DECOMPOSITIONS
The decomposition algorithms in $5 enumerate strings by breadth-fire search. For the enumeration to terminate, the quotient Q(y) and remainder Ryy) need to be finite for given target string y E ) Previous work (Vicira et al., 2025a, Props 1 and 3; also in (D.2) showed that strict-prefix monotonicity guarantees an empty remainder and a bounded quotient. This ensures that (y) is computable.
For functions that section, we give additional conditions for finite decomposition. We first give function-leves properties that guarantee an empty remainder and bounded quotient, and then transducer- conditions for when the quotient and remainder are finite.
strict-prefix monotone, however, the decomposition may be infinite. In this
We say that map f: X -> )" is strict-prefix monotone if and only if a < < = [(x) f(x'). Similarly f is prefix monotone if and only if x I x' = f(x) 3 (x'). We say that map f is prefix-continuous if, for every y E y", the set P(y) is cylindrical, i.e., R(y)
The following
proposition shows that prefix monotonicity implies wveix-continuity:
Proposition 6.1. The following are equivalent: (i) J is prefix monotone (ūi f((x)) S (f(x)) for all X (iii) ((f()) = C(f(x)) for all X (iv) f is prefix-continuuus
[Proof: $D.I]
Proposition 6.1 shows how we generalize Vieira et al. (2025a). First, by relaxing strict-prefix mono- tonicity to prefix monotonicity, we support multi-symbol lookahead in the quotient. Ex. (6) is an exam- ple of this: it is prefix monotone and requires two-symbol lookahead before committing to output. Second, by introducing the remainder, we can handle functions that are not prefix monotone, meaning that there can be source strings that cover the target, but not all of their extensions do (e.g., Example 2).
Lemma 6.1 gives sufficient conditions on a transducer that guarantee a finite decomposition for every target string, even when the underlying function is not prefix monotone. The key notion is safety: a state is safe if it is IP-universal, has finite closure (i.e., [[ < oo), or all its successors are safe.
Lemma 6.1. Let f: X - y" be a function realized by a transducer The decomposition (Q(v), R(y)) is finite for every E y if:
(i) No e-output cycles: f contains no cycle in which every are outputs E.
(ii) Safety: Every state of f is safe, defined inductively as the smallest set such that is safe if: (a) is IP-universal; (b) [f]]]]] co (finite closure); (c) for all transitions any s', s' is safe.
Proof: See $D.3.
8

---

The conditions in Lemma 6.1 guarantee exact computation. In particular, these are satisfied by the transducers introduced in the experiments section ($7): the token-to- to-tttt transducer fa and the INA-to-amino-ace transducer f dnaamaa whose quotients are finite and remainders empty, but not by the PTB transducer fpb. whose quotients are infinite.
The finiteness of decomposition is a property of the function f, not of any particular transducer encoding it. The lemma's conditions are sufficient but not necessary: safety tests each state individually, whereas the decomposition algorithm tests universality of frontiers (sets of state/string pairs), which can succeed even when individual states are not safe. There are many cases where the prefix decomposition is infinite, or otherwise prohibitively large; in these cases, we let the source language model determine which prefix decomposition members carry the most significant mass and prune others ($5). This lets us greedily approximate the probabilities of the transduced language model by enumerating a high-mass subset of the decomposition.
7 EXPERIMENTS
We now consider three examples of transduced language models. For each use case, we follow the approach in Vieira et al. (2025a) and measure the Jensen-Shannon divergence (JSD) between the distributions obtained using the approximation via probability mass pruning mentioned in $C.3 and reference distribution we get by choosing pruning threshold We also report cross-entropy loss ($G.4), reflecting the cost of scoring specific sequences rather than full distributions. Experiments use GPT-2 Large (Pgpt2) (Radford al., 2019), LLaMA 3.2-1B (Pilama1B) and LLaMA 3. 3-IB (pilamaBB) (Team, 2024), Phi-4 (pphia) (14B; Abdin et al., 2024), and a DNA model trained on the human genome (Dana). 12 For the experiments in $7, we use genlm-bytes! to convert token-level models to byte-level models. See F for details on the training and evaluation setup, and FF5 for transducer details.
Recall that a transduced language model Py is characterized by a source model px and a transducer f encoding some function / ($3). To make this dependency explicit, we write px o def py and refer to the operation as composing. All experiments compute next-symbol distributions using the more efficient algorithm ($ C.8), which reuses cached decompositions across target positions and exploits structural shortcuts ($C.5) Probability mass pruning ($ C.3) retains the most likely decomposition elements such that the discarded probability mass does not exceed the pruning threshold.
Our experiments span the menooooiont spectrum (Proposition 6. I): token-to-byte (T2B) is strict-prefix monotone, ONA-to-amino-ae is prefix monotone with multi-symbol lookahead, and PTB tokenization is not prefix monotone.
From tokens to bytes. We revisit the algorithm for converting models from tokens to bytes, as in Vieira et al. (2025a). This transformation can be realized by simple transducer fa. with ([ states. Specifically, the transducer contains chain for each token present in the input vocabulary X. This structure allows us to use a shortcut (see Fig. 14) that resolves each quotient element with a single LM call. An example of such machine given in Fig. 4. We benchmark the algorithms in $5 using the transducers Pgpt2 fa, Pllama18 fa. PilamaBB O fa. and Pphi4 o fa on the first ten paragraphs of the wiki textt---aaa- shown in Fig. 6 (left) and Tab. 8 in $G, lower pruning thresholds (T) give lower JSD values against a reference distribution (T = 1e-5) at the cost of throughput, measured in bytes per second. We confirm that the JSD values are similar to those achieved by Vieira et al. (2025a) in & G. Tab. 6. Their method is limited to strict-prefix monotone fransformations, which enables a specialized trie-based algorithm that achieves higher throughput while maintaining comparable accuracy.
dataset (Merity al., 2017) (corresponding to the first 7684 bytes). As
From tokens to orthographic word boundaries. The next transformation we consider is converting language models over tokens to language models over orthographic words. The precise definition of what constitutes such a word varies depending on the application. In some settings, contractions such "wouldn' t" should be treated natural segmentation would be "would" and "n" t". We can accommodate any FST-based definition. Linguistic tokenizers, such the PTB tokenizer (Marcus al., 1993), use contextual information to
single unit. In other settings, however, more
1 Lnnisss models: https: http:///iiiii.teee.oooa.mmmmmmaa http:://gghhhtttt/s/s/st/us http:///...rrr...ttsts///g/gnnne 1o/metaallaam/llamm 3.2-18, https://hugginggaace http:/ee.eoe//mteaaammmmaaaaaeee 1-88, http://ff......a/ioo////oo
https:
/ //huggingfacce co/mi co/microsoft/phte -4 and https: httpg//////gggaaaceeee.. http://ccc...oeeeeeee///////-/ea
ggenem-bytesis implementation of Vicira al. (2025a); see https:://githb.. http://ggtttuub.ccoomeeeee// hwt.mm/ggnllmmmggee metpl//m//emmmmmmmmmmmmmm bytess.

---

yoy y.y. Vy E (8-9,)
E 2 G)
@o
f1
Dog:D
.cati.
E:0
qo
Q2
d:d, Ad E (0-9} :SEP
.SSEP
E:8
e:t
f3
a:a
Figure 4: An FST for converting token model into a character model. Paths for cat and Dog.
Figure 5: An FST that inserts a separator (SEP)
before commas followed by non- non-digit characters.
T-36-5
r-lo- 3-30
7-10-3
33-3
7= o T=30-2
r=le-1
Pomt o fo
Plar Fo
Pphia o fo
Pano o f, fut PLas o f, fins Pphia o fo o pubs
e.
3e-2-
3e-3
JSD
1.5e-2
1.5e-3
0.0
0.0
0
25
50
75
0
25
50
75
0
15
30
8
16
24
10
15
20
2
8
Speed (bytes per second)
Figure 6: Average Jensen-Shannon divergence (JSD) and throughput (bytes/sec) across thresholds
T. Left: Px o fa (reference: le-5). Right: px o fa fpb (reference: T Te-4; 3e-4 for Pphia). Bars show 95% bootstrapped CIs. At the tightest thresholds, large decomposition sizes prevent some models from completing all paragraphs; see G.2.
segment raw English text into linguistically meaningful units suitable for downstream NL.P tasks. We construct an FST that encodes the PTB tokenizer, f pubs details are in $F.5. An example of rule in the transducer is given in Fig. 5, which inserts SEP before a comma a digit does not follow. Composing Px o fa f fpt yields transduced language model, mapping subword tokens to PTB tokens. To reduce the state count the composed FST and improve efficiency, we represent Px o fa using the byte-trand trte-transformed models from bytem. In Fig. 6 (right), we plot the average JSD against the throughput for different thresholds т. using the same dataset as in $7. The reference distribution uses le-4 (3e-4 for Pphia). As with the experiments in $7, we observe lower JSD lower thresholds, albeit at the cost of throughput. For experiments using higher thresholds, see $ SG, Tab. 9.
Converting DNA models to models over amino acids. We a transducer that converts sequences of the four DNA nucleotides to sequences over the twenty-two amino acids. 15 Let Pdna fdna2aa denote the transduced model that converts DNA nucleotides into amino acids. To evaluate our approach, we sample 65 human proteins." 16 In Tab. 10, we show the average JSD and throughput different thresholds т. Note that this transducer is particularly challenging since the set of candidates in the decomposed precover grows exponentially with the sequence length. To mitigate the combinatorial blow-up, we cap the candidate- set and report throughput and JSD while varying the cap.
CONCLUSION
We have introduced general framework for transforming language models using transducers. Empirically, we have shown that our beam-summing approximation efficiently transduces token- based LLMs into models over bytes, words, and even amino acids, without requiring retraining. Our theoretical analysis characterizes the conditions under which such mappings can be performed exactly. The proposed approach an effective way repurpose existing language models and to accurately compute probabilities for any unit and transformation defined by a transducer. By reducing the problem to transducer decomposition, the framework opens the door to leveraging future advances in finite-state methods for language model adaptation. (Future work and limitations are discussed in ŠJ.)
"https:: http:://gggtguuuboom////g///g/// geneebbbbeeellebeeeee that implements Vieira et al.'s (2025a) method. LL... X' = (A, (, and ) = {A. R, D.M.C.C.OOEE......L...MMM.... T, V,W, Y,B, x)
"Sampled from ht /ww.. wwwpuot.cnm.mo hwwp://ppw...o.o..ooooooooto//ee see Tah. for the accession numbers.
10

---

ACKNOWLEDGMENTS
Edo Dotan, Gal Jaschek, Tal Pupko, and Yonatan Belinkov. Effect of tokenization on transformers for biological sequences. Bioinformatics, 40(4), 2024. ISSN 1367-4811. URL /ttps:///oii.. org/ 10. 1003//boiiformmatcc//ttte"" The authors thank Ben LeBrun, Brian DuSell, Clemente Pasti, Juan Luis Gastaldi, Mario Giulianelli, and Yahya Emara for useful feedback and discussions that greatly improved this work. Vésteinn Snæbbarmarson supported by the Pioneer Centre for AI, DNRF grant number Pl.
REFERENCES
Marah Abdin, Jyoti Aneja, Harkirat Behl, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, Michael Harrison, Russell J. Hewett, Mojan Javaheripi, Piero Kauffmann, James R. Lee, Yin Tat Lee, Yuanzhi Li, Weishung Liu, Caio C. T. Mendes, Anh Nguyen, Eric Price, Gustavo de Rosa, Olli Saarikivi, Adil Salim, Shital Shah, Xin Wang. Rachel Ward, Yue Wu, Dingli Yu, Cyril Zhang. and Yi Zhang. Phi-4 technical report, 2024. URL https: //arxiv...iv wrg..oggg//.........o....... abs/2412 08905.
Cyril Allauzen, Bill Byrne, Adrià de Gispert, Gonzalo Iglesias, and Michael Riley. Pushdown Automata in Statistical Machine Translation. Computational Linguistics, 2014. URL https:
// //aclanthology. JrggJ14--3000
Lisa Beinborn and Yuval Pinter. Analyzing Cognitive Plausibility of Subword Tokenization. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2023. URL https://aclanthol..g org.//20../2 emnlp-main main. 272/.
Martin Berglund and Brink van der Merwe. Formalizing BPE tokenization. In Proceedings of the International Workshop Non-Clan non-Classical Models of Automata and Applications, volume 388, 2023. URL hww.h:tpp//eeee //ggi////iii// ces.cse..uu. unsw. wdw. httpreppcsppppppee
?NCMA2023 .4.
Martin Berglund, Willeke Martens, and Brink van der Merwe. Constructing BPE Tokenization DFA. Implementation and Application of Automata, 2024. ISBN 978-3-031-71112-11 URL
https://link, http:///iinnsssrinngneeeeee spwinger.....ee com/ cttpter/10.1001/111111 10011/997----03--7111------
Jean Berstel. Transductions and Context-Free Languages, volume 38. Teubner, Stuttgart, Germany, 1979. URL httpp:://wwwt httttt/////w....oobba...oooo/// htrpr//caaaa.rr//ccc////63661
Harry Blanchard, Alexander Pollatsek, and Keith Rayner. The acquisition of parafoveal word information in reading. Perception & Psychophysics, 46(1), 1989. ISSN 0031-5117. URL https://link, wwr.sspriiiieee wwt.coocccccoceoeo comm/contet//pdf//1 3758/BFF32288078. pdf.
Filippo Bonchi and Damien Pous. Hacking nondeterminism with induction and coinduction. Com-
munications of the ACM, 2015. URL http:::t:///ooi.og//// 11 1141027111111/111
Christian Choffrut. Une caracterisation des fonctions sequentielles et des fonctions sous-eqquenieells en tant que relations rationnelles. Theoretical Computer Science, 5(3), 1977. ISSN 0304-3975. URL https:://ol1 org/10. (77))4444777777)844444
Marco Cognetta, David Pohl, Junyoung Lee, and Naoaki Okazaki. Pitfalls, subtleties, and techniques in automata-based subword-level constrained generation. In Tokenization Workshop, 2025. URL
https://openrevii net met/forrum1d=DFFyb0GGG0)
M. De Wulf, L. Doyen, T. A. Henzinger, and F. Raskin. Antichains: A New Algorithm for Checking Universality of Finite Automata. In Proceedings of the International Conference on Computer Aided Verification, 2006. URL /tttps:///oi..oo wrw.orgg//////
01177/1817963...
Philip Gage. A new algorithm for data compression. The C Users Journal Archive, 12, 1994. URL kttps://api.. www.stiismccoooo...ee wowpoolarrrrg/ooousii::sss 59804000.
Renato Geh, Honghua Zhang, Kareem Ahmed, Benjie Wang, and Guy Van Den Broeck. Where is the
signal in tokenization space? In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2024. URL https: pettps://aclanteee h/aclanthalallg////a//// .rw. 2224/222..22m emnlp-main 230/
11

---

Marjan Ghazvininejad, Xing Shi, Yejin Choi, and Kevin Knight. Generating Topical Poetry. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2016. URL https://aclanthologg ottp://nnooooooo.o//11--/--1--1 1126/.
Mario Giulianelli, Luca Malagutti, Juan Luis Gastaldi, Brian DuSell, Tim Vieira, and Ryan Cotterell. On the Proper Treatment of Tokenization in Psycholinguistics. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2024. URL https: /ttp:://aaaaaaaa /ccnoooooo.. org/2024, emnlp- main. 1032.
Kyle Gorman. Pynini: A Python library for weighted finite-state grammar compilation. In Proceedings of the SIGFSM Workshop on Statistical NLP and Weighted Automata, 2016. URL https://
aclanthology. org/W1 2409//
Jonathan Hayase, Alisa Liu, Noah A. Smith, and Sewoong Oh. Sampling from Your Language Model One Byte at Time. In Tokenization Workshop, 2025. URL https://openrrevien net/forum?
id=DM8D9NqSuO.
John E. Hoperoft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison- Addison-Wesley, 2nd edition, 2001. ISBN 0201441241. URL
https://openlibee hwtpbbarrr..ogbb//ooeeoooeeeeeee httg//ookk/LLLS 006/00996..
Yanrong Ji, Zhihan Zhou, Han Liu, and Ramana V Davuluri. DNABERT: Pre-trained bidirectional encoder representations from transformers model for DNA-language genome. Bioinformatics, 37(15), 2021. ISSN 1367-4803. URL petpps//doff org/10 1093 httt://oooooooaaaccs/taaaa/o///a
Arthur B. Kahn. Topological sorting of large networks. Communications of the ACM, 5(11), 1962.
URL httph: acm.
a org/doi/10, /145/669996.0 369025.
Terry Koo, Frederick Liu, and Luheng He. Automata-based constraints for language model decod- ing. In Conference on Language Modeling, 2024. URL https: wwt.riiwwweeeeoummiiiiiiee
BDBdblmyzY.
Taku Kudo. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2018. URL https://aclanthology org/P18-1000
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng. Lianmin Zheng, Cody Hao Yu, Joseph Gon- zalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with PagedAttention.
SOSP, 2023. URL https://dol/ / org/10. 1 145/3600006.... 3613165.
Alexander K. Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash Mansinghka. Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs. In ICML Workshop: Sampling and Optimization in Discrete Space, 2023. URL id=U12KeqXxXy.
net/forum?
Chu-Cheng Lin, Hao Zhu, Matthew R. Gormley, and Jason Eisner. Neural Finite-State Transducers: Beyond Rational Relations. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019. URL
http:://aclanthology..oo http:///aaanttoooooroo/rr//// -wwp:oog...og/N1--112110
Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 1993. URL https://
aclanthology .oregg..orrr//o org/J93-220000 -004/
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer Sentinel Mix- ture Models. In International Conference on Learning Representations, 2017. URL https:
2udxxe.
A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the Annual Symposium Switching and Automata Theory, 1972. URL https: htt:://doii.ooo org/10 1109/SWATT 1972. 29.
Mehryar Mohri Finite-State Transducers in Language and Speech Processing. Computational Linguistics, 1997. URL https:://aclaatthology wttph/hooooooooogI99999. org/J97-2003/
12

---

Mehryar Mohri. Edit-Distance of Weighted Automata: General Definitions and Algorithms. International Journal of Foundations of Computer Science, 14(06), 2003. doi: 10.1142/
$01290541030021144 URL https:h//oi..rrgaa 012/1///12299441000002
Mehryar Mohri. Weighted Automata Algorithms, chapter 5.
Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-642-01492-5. URL https://doi.ors org/ 1007/
Sathvik Nair and Philip Resnik. Words, subwords, and morphemes: What really matters in the surprisal-reading time relationship? In Findings of the Association for Computational Linguisties:
EMNLP, 2023. URL https://aclantholles ooggggggggg/g///o/ooooooooo wwwgg2222..0 ww2....inniin.... findings-emnlp. 752/.
Eric Nguyen, Michael Poli, Marjan Faizi, Armin W Thomas, Michael Wornow, Callum Birch-Sykes, Stefano Massaroli, Aman Patel, Clayton M. Rabideau, Yoshua Bengio, Stefano Ermon, Christopher Re, and Stephen Baccus. HyenaDNA: Long-range genomic sequence modeling at single nucleotide resolution. In Proceedings of the Conference on Neural Information Processing Systems, 2023.
URL https: http:///pppeeeeieeee wwt..e//oouum//ddduoooooooo.
Byung-Dob Oh and William Schuler. Leading whitespaces of language models' subword vocabulary pose a confound for calculating word probabilities. In Proceedings of the Conference on Empiri- cal Methods in Natural Language Processing, 2024. URL https://aclantholoogy oat.a/annooooog.oor//22222/ o82/2024. smnlp-mainn 202/.
J. Oncina, P. Garcia, and E. Vidal. Learning subsequential transducers for pattern recogmition interpretation tasks. IEEE Transactions on Puttern Analysis and Machine Intelligence, 15(5), 1993. URL https::/iieexpppee
ieee. dog//ennmmet/2111 1465.
OpenAl. Tiktoken: A fast BPE tokeniser for OpenAl's models, 2024. URL https::/://ithhtu com/ openai/tiktoken.
George Orwell. Nineteen Eighty-Four. Secker & Warburg, 1949. URL https:://e..wikiippppet hree//ikii//ineeee_Eiityyyy
Buu Phan, Marton Havasi, Matthew Muckley, and Karen Ullrich. Understanding and Mitigating Tokenization Bias in Language Models, 2024. URL
16829.
Tiago Pimentel and Clara Meister. How to compute the probability of a word. In Proceedings of the Conference Empirical Methods in Natural Language Processing, 2024. URL https: pacclantoloogy.rggg... o2g/2224. emnlp-main. 1020/.
éric Pin. Mathematical Foundations of Automata Theory. Lecture notes LIAFA, Université .ddf.
Paris, 2025. URL htttps://www.rrrtt
Jean-Eric Pin. Handbook of Automata Theory. European Mathematical Society Publishing House, 2021. ISBN 118-3-98547-006-2 URL httphtttts//o.orgg//// 4171 4171/Automata.
Lifeng Qiao, Peng Ye, Yuchen Ren, Weiqiang Bai, chaoqi liang. Xinzhu Ma, Nanqing Dong, and Wanli Ouyang. Model decides how to tokenize: Adaptive DNA sequence tokenization with MxDNA. In The Annual Conference on Neural Information Processing Systems, 2024. URL
wtt.e//www.tttoooumm/////Auuuuue uZZZZ.
Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2), 1959. URL https://ieeexplors ieee. or org/document/ 5392601.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language Models are Unsupervised Multitask Learners. OpenAl Blog, 2019.
URL https://cdn. opwnai..ennaoccooooo wtwm/better--agguaae huapllrttrr.aauuussemmiiii/gggg unsupprriiseedmmllttttts_LLeeer
Pushpendre Rastogi, Ryan Cotterell, and Jason Eisner. Weighting Finite-State Transductions With Neural Context. In Proceedings of the Conference of the North American Chapter the Association for Computational Linguistics: Human Language Technologies, 2016. doi: 10.18653/v 1/N16- 1076.
URL https::/acllanttooogy..o wwwpo/ooyy.org/111-1111101 1076/.
13

---

Keith Rayner, Arold D. Well, Alexander Pollatsek, and James H. Bertera. The availability of useful information to the right of fixation in reading. Perception Psychophysics, 31(6), 1982. URL https://doi. org/ 10.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural Machine Translation of Rare Words with Subword Units. In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2016. URL https://aalaattoology orgg/16-116:5
Xinying Song, Alex Salcianu, Yang Song, Dave Dopson, and Denny Zhou. Fast WordPiece tokeniza- tion. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2021. URL https: hatps///aaaaaanoloooooe org/ /etg//211...2 w0221emmllp..... emnnp-mmaing 160/.
Felix Stahlberg, Christopher Bryant, and Bill Byrne Neural grammatical error correction with finite state transducers. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, 2019. URL
http:://aclanthhlloe www.ggg......ggooooooooooo.oo..o hrggg/9-1//1/1000660 9-166/
Llama Team. The Llama 3 herd of models, 2024. URL https::/arxxv..rrr /rg/ howg/bb/////////o /a//aab//////
Tim Vieira, Benjamin LeBrun, Mario Giulianelli, Juan Luis Gastaldi, Brian DuSell, John Terilla, Timothy J. O'Donnell, and Ryan Cotterell. From Language Models over Tokens to Language Models over Characters. In Forty-second International Conference on Machine Learning, 2025a. URL https: /openrevie. wwwparreeweeeeeooouuiiiiiieee nett/forum?id=ss$Srooooe
Tim Vieira, Tianyu Liu, Clemente Pasti, Yahya Emara, Brian DuSell, Benjamin LeBrun, Mario Giulianelli, Juan Luis Gastaldi, John Terilla, Timothy J. O' O'Donnell, and Ryan Cotterell. Language Models over Canonical Byte-Pair Encodings. International Conference on Machine Learning, 2025b. URL
net/forum's (n d=CCVrFVDNSY..
Ning Wang, Jiang Bian, Yuchen Li, Xuhong Li, Shahid Mumtaz, Linghe Kong, and Haoyi Xiong. Multi-purpose RNA language modelling with motif-aware pretraining and type-guided fine-tuning. Nature Machine Intelligence, 6(5), 2024. URL https://doi.org/// 1038/ 542256-824-00835
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-Consistency Improves Chain of Thought Reasoning in Lan- guage Models. In The International Conference on Learning Representations, 2023. URL https://openrrevew..t http//ppnrreiie..eeeeooorrmm/a/m www.nnttfformmmidd11nomm 11PMMM..
Brandon T. Willard and Rémi Louf. Efficient guided generation for large language models, 2023.
URL https:h/tt/aat //t::v...////////////////
wwwpxiiivvrrraaooo org/ abs/ 09702.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-art natural language pro- cessing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing: System Demonstrations, 2020. URL https: /aacttss://caannnne / org/ 2020. emnlp-demos. 6.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe Le, Mohammad Norouzi. Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang. Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation, 2016. URL https: //tp::://///vv..//.///ae org. wwt.oogg/////o.oo abs///bs/11999 081 44.
Vicky Xefteri, Tim Vieira, Ryan Cotterell, and Afra Amini. Syntactic Control of Language Models by Posterior Inference. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.). Findings of the Association for Computational Linguistics: ACL 2025, pp. 25350- 25365, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8- 89176-256-5. doi: 10.18653/v1/225 (005://1/222...nnnnnn----a findings-acl. URL https://aalaantholoy..orr 2025. findings-ach acl. 1300/-
14

---

APPENDIX CONTENTS
Notation Glossary
17
Background on Transducers
18
C Efficient Algorithms
19
C.I The Goal: An Efficient Implementation of the Autoregressive Interface
19
C.2 Frontier-Based Checks (is_cylinder, is _s_merber, is live)
21
C,3 Pruning (prune)
22
C.4 Fast Next-Symbol Decomposition (decompose_next)
23
C.5 Next-Symbol Decomposition Shortcuts
25
C.6 Inoot-Proeection Universality Shortcut
26
C.7 Memoization and Batching of pxx
26
C.8 Realizing the Autoregressive Interface
27
C.9 All-Universal Fast Path
28
Proofs for Finiteness Conditions
30
D.I Properties of Prefix Monotone Maps
30
D.2 Quotient Bound for Strict-Prefix Monotone Maps
hap.............................
D.3 Sufficient Conditions for Finite Quotients and Remainders
32
Example Decompositions
34
Experimental Setup
36
F.1
Datasets
36
F2
Models
36
F3
Parameters
36
F.4
GPU Usage
36
F55
Details on Transducers Used Experiments
37
G
Additional Experimental Results
39
G.1
Comparison Vieira al. (2025a)
39
G.2 Jensen-Shannon Divergence
40
G.3 Decomposition Size
43
G.4 Cross-Entropy
45
G.5 Benchmarking the Computational Shortcut
46
H State-Based Decomposition
47
Related Work
48
15

---

J Limitations
50
16

---

A NOTATION GLOSSARY
Notation
Gloss
Empty string
End-of-string symbol
R, x' E & n, x' E X X
Symbols in the source alphabet X' Source strings
Set of all source strings
Z, S X ax ZZ'
Sets of source strings Concatenation (strings)
Concatenation (sets of strings)
U.YL EY
Symbols in the target alphabet
y. E
Target strings
Set of all target strings
X" 3
Transformation from source strings X target strings y
18 3 x''
a is prefix of x!'
x
is strict-prefix of xx'
(2)
Cylinder set spanned by Z Prefix-base of Z
Df(
Px
Language model over source strings X" -*-uvllud random variable X px
Prefix probability of px Language model over target strings )" -*-valeed random variable fXX py
f(X)
PY
Prefix probability of py
Transducer implementation of
48
Input alphabet
41
Output alphabet
45
Set of states
4lgS
Set of initial states
4FCS
Set of accepting states
4T
Set of transitions
4US 8 - TT C( for
Set of IP-universal states ($C.6)
States
Transition from s' that scans x and emits y Outgoing transitions from state
Transducer composition
for
Relation composition Input projection
(f)
fll
Force-start in state
yd
Either a copy-transducer that accepts y or the corresponding relation. A transducer whose paths restricted to those that accept y)"
foy
(1)
Preimage of the target string y ($3)
(1)
The preimage of set )/ 1ifff(((6 (v) y ) ($3)
P(y)
Precover of the target string ($3)
C(y)
The largest cylinder set contained in P(y) ($4)
2(v)
Quotient ($4)
R(y)
Remainder ($4)
Notation conventions. Color encodes domain: magenta denotes source-domain objects (e.g., æ, X, P. Q, R) and olive green denotes target-domain objects (c.g., y, V. f). Font encodes type: lowercase italic for symbols (x,, y), bold italic for strings (æ,, y), calligraphic for alphabets and sets (X, ), P.
Q, R), sans-serif for transducer components (S. I, F, U), and typewriter for the transducer itself
(f) and for concrete strings in examples (abc, xyz). The overrightarrow ? marks prefix probabilities:
px is the prefix probability of px-
17

---

B BACKGROUND ON TRANSDUCERS
This section introduces additional information transducers, complementing $2.
Transducer variants. We say a transducer is functional it defines a function, and partially functional if it defines partial function. A transducer is input-determiniitic if for every state S, [T(x,e)| = 0 and (T x < 1 for all x E X² For input-deterministic transducers, each source string æ: x has most target string E ) Thus, every input-deterministi transducer defines a (partial) function. A copy- transducer is one where every transition emits the same symbol as it scans, i.c., every transition is of define partial iden-
accepting path that scans æ and, therefore, can emit at most one
the form s - s'. We abbreviate copy transitions as s 5 s'. Copy-transduue tity functions: they map each string in a designated subset to itself, and drop all others. In the same way that we abbreviate copy transitions, we may implicitly map them to a set of strings via (2r, x)) + æ.
Operations. Transducers support composition: given transducers f and f", their composition fo f a transducer denoting [f f'] def [f]] o [[']] 1920 We denote transducer that encodes the relationship [f]] o ((') y E (y)} with f o y) We freely coerce between these representations when the intent is clear from context. We define the input projection operation encoding the relationship [[roo (f)] = {( x) By: (æ, y) E [f]] as (f) XS, X, F, [ Si2, s') 2:9
s' E T)), which is copy-ooppaaaatte transduer.. Let f(-] denote the operation of force-starting in state
fl.] de (,, F. T); this operation yields a machine defining the set of source-target suffix pairs that are generated by paths starting at a given s and ending in an accepting state. We say that a state is IP-universal ctaput-projection universal) if [proj (f()) ] = X i... no matter what input follows, the transducer can still produce output. Let U S S denote the set of IP-universal states; this set can be precomputed for each transducer ($C.)).
Our algorithms use an input-determinization transformation determinize(f) that maps a (partially) functional transducer f to an equivalent one that is input-deterministic. In general, such mapping not always realizable with a finite number of states. 21 However, in the special case of copy- transducers, inputddeterminization is always possible, but may result in exponential blowup in the worst case. We use tfim(f) to denote a trimming operation that removes all states and edges that do not appear on any accepting path. These standard operations that are implemented in any FST library; more details can be found in (Pin, 2021; 2025).
Visual notation. We use diagrams like those shown in SE to represent transducers. Transitions without source states denote initial states; double- states indicate accepting states. Transitions 2:y s' are shown as arrows between states.
I Limitations.
Finite-state transducers define the class of rational relations (Berstel, 1979, Ch. III.. Because FSTs only have finitely many states, they are inherently limited in the relations they can represent. For example, FSTs cannot perform transformations that require unbounded matching or counting. In contrast, transducers with unbounded memory extend beyond the rational class, offering greater expressive power, but come with increased complexity and often undecidability of key properties, such universality.
The more general notion subsequential transducer additionally includes a final output function; this distinction does not arise for copy-transducers.
For readers familiar with finite-state automata, every copy-transducer is isomorphic to an acceptor.
"eere, relation composition is given by fo def ((x,2) (z,, v) E f, (v. E g} where f and g are relations. 20 Pii (2025, Ch. XIX, sec. 2) gives an efficient method for constructing f 21 Chofffut (1977) gives such algorithm, by using a power set construction determinization of nondeterministic finite automata. He shows it yields a finite machine if and only if the automaton has bounded variation, the constraint that for any two strings whose prefix distance (the combined length of the strings with the longest shared prefix removed) is bounded, then the output prefix distance is also bounded. He also provides testable condition for determinization. known as the twinning condition: once two runs have read the same imput prefix (i.c., we cut the input the same point), then for every common continuation, they append the same further output. For readers familiar with finite-state automata, anputddetermiiization of copy-transducer is isomorphic to the determinization of an equivalent finite-state automaton, see B.
the input side as in the
18

---

C EFFICIENT ALGORITHMS
The decomposition algorithm of $5 operates on a determinized, trimmed precover machine P trim (determinizee (proj, ))) In practice, both the composition with y3 and the explicit determinization are expensive and must be repeated for each target y. The algorithms in this section perform both steps lazily, operating directly on the original transducer f and avoiding explicit materialization. This requires careful bookkeeping of partial outputs via frontiers ($ C.I.1), but enables precomputation of IP-universal states and incremental reuse across targets.
We begin by stating the algorithmic goal ($C.1), then introduce the frontier data structure ($C.1.1) and show how each check reduces to frontier query ($C.2). We write F,, and omit the dependency on Px since it is clear from context.
throughout
C.I THE GOAL: AN EFFICIENT IMPLEMENTATION OF THE AUTOREGRESSIVE INTERFACE
We seek efficient algorithms for the prefix probabilities py (y)) string probabilities py()). and next- token distributions (- y) of transduced language models. Specifically, we want efficient implemen- tations of the following methods, which constitute the interface to the transduced language model ($2).
44 def wwwfii_probpppepp
49 def next rext_dist(t)) <- {
(Q.R) + decompose(y)
46 return Exsq (x) + ExERPX
s1
7 f prefix_prob(u)
for y E y::
47 def py): return prefix_probly) (oS)
53 p[y'I prefix
p[Eos] +- - Σ EveyPlyi
55 return p
The primitive operation above is prefix_prob, which requires single call to decompose. Both next_dist and prob are derived from it: next_dist computes [}] additional prefix probabilities and obtains (EOS ()) by complement; prob is one-line product. In an implementation, P. and px should be memoized so that extending (x) to px (xx) requires only a single conditional evaluation rather than replaying the entire history (see SC.7). In & SC., show how compute next_di dist with a more efficient, joint decomposition, rather than [)|+1 separate calls to prefix_prob.
The three checks in Fig. 2_-is_cyl weriissslssiiie cylinder, is ss_member, and is is_live-al all require determining which transducer states are reachable after reading a source string æ, and what output each has produced relative to y. We capture this information in single data structure: the frontier 1.1. In $C.2, we show how each check reduces to a simple query on the frontier. In practice, the quotient and remainder may be large or infinite, so we introduce pruning ($3.) obtain practical approximations.
C. FRONTIER COMPUTATION
Since can be nondeterministic even it is functional, the transducer may reach many states simultaneously for given source string æ and target y. Each of these paths may have produced
different output buffer. The frontier F = run,, (2) collects this information: it is the set of (s, b) pairs-where where s E reading from the initial states, filtered to buffers b compatible with y. 23 The frontier encodes all information needed for the three checks: is_ is_cyll s__cylinddrr, is_ is_member, and is_ is_live can each be evaluated from F alone, without retaining the full path history (& C.2; Fig. 8). The pseudocode in Fig. 7 describes how to compute the frontier using the three functions runy, step,, and closurey.
transducer state and b E y is the output produced so far- reachable by
The frontier replaces the explicit precover machine in $5. Rather than materializing P, the frontier tracks the same information directly on f, avoiding both the composition with y)" and the explicit determinization. The design reflects two-phase structure: before a path's buffer covers the target, the frontier tracks per-state output buffers (s. b) filtered by target compatibility; once the buffer reaches or passes y, the frontier can be truncated for universality checking ($ C.2). The frontier unifies the two phases into single lazy data structure.
(ommmdetermnizeeprgg (f y)"))) used
23 A buffer b is compatible with if and only if b 3 y 3 b, i.c., the buffer has either covered the target has yet diverge from it.
19

---

def (T # memoize
def closure, (FF): F + F q f- QUEUE(F)
if N = 0: return closurey x {s}) return (rup, (Nx
6
while |q| > 0:
def (te
(s, t q.pop()
60
F +
for ( Ei 8') ((8
for (8) in F:
72
b' by
for ( 2i 8') E 2() b' by if y y bb: F (' b)) return closure, (F))
if y 3b:
74
75
if b') F
64
F ()),('
q add ( (s'bb))
77
return F
Figure 7: Frontier-based state machine
q1
a:c
e:d
a: d b:d
qo
q3
b:c
a:d
Q2
91:C
a, b
Qu:E
:d
a,
b
92:0
Frontier
is live is_cylinder
is_member
Class
6 (yo, e)}
extend Q(c)
((11, c). (4s, cd)}
/
b
((92, c)}
x (g2 dead on b)
R(c)
Top: the transducer f. Middle: the frontier graph run,, whose nodes are sets of (s, b) pairs and whose edges are input symbols. Buffers truncated to length ly|+1= 2: advancing (43, 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 æ a reaches two states via e-closure: (/1 (buffer y) and (buffer > y). Yellow nodes are universal- every input leads to a non-empty accepting successor puccesoo-pplacing on b, so the BFS fails and b enters R(c).
Figure 8: Truncated frontier example for the target y
Q(c). The teal node d2 has no are
The frontier enjoys useful monotonicity property: extending the target by one symbol can only remove elements from the frontier, never add new ones. This means we can compute the frontier incrementally-fiitee rather than rebuilding the target grows.
Proposition C.1 (Frontier containment). For any source string x, target string 3/1 .* UN with >
rungi--yx (x)) {(s, b) E run (x):
NVby yN}
Proof. Buffer filtering in step and closure keeps only (s. b) pairs where and the target agree on their shared prefix. Since FST ares only append to the buffer, once b is long enough to have an /h symbol and by * yv then all descendant buffers would be filtered out by the / e---ompaaiiilltty filter. Therefore, filtering run, (a:) the end is equivalent to filtering each step.
20

---

To see this, note that the (2) direction holds because 2/ .M VN yy-compatible elements also y1 . 1-y-1-compatibe (the former is strictly more restrictive). The (5) direction holds because elements that are y1 TM -N-1 -compaaleeiiile but not y1 commpptii (i.e., |6| 2 N and by # yx) cannot produce descendants that become y/ yx-coppa,ible, since buffers only grow.
Proposition C.2. Prop. C.I generalizes beyond single-symbol extensions: for any y = y:
(an = {(s, b) E runy (a)): b 3 yVb y)
(10)
Proof. By induction on |y| l/'l. The base case y =y' is immediate. For the inductive step, write {(s, b) runy (x): |6| < N VV by = yN By the induction hypothesis, runy {(s,b) E runy b 3 y V b y'). Substituting,
y = y'uN with y' 3 y'. By Prop. C.I. (a)
(s, b) E runy (a) survives both filters iff agrees with on all positions up to min([b],N] N), i.e.
b 3 y VV
Prop. C.2 is the key property that enables warm warm-starting decompose_nex C.4) from any target prefix's s cached frontiers.
C.2 FRONTIER-BAN BASED CHECKS (is_cylinder, is is_member, is is_live)
Recall that the decomposition algorithm (Fig. 2) relies on three checks ris_cylinder, is is_member, is_ live). This section describes how to compute them in terms of the frontier.
19 def js__cylnder(e1, (x) # memoize
96 def is_ 1t_memberr(: y):
80
N < y
97 return 3(s, b) (a)y
F t trunc_buf (run,(())
+ (F]; q QUEUE((F))
82
99 def is_live( y): return run, (2) +
while q:
100
84
F F q. (op
def trunc_buf (F):
Accepting: some pair has matched target and is accepting
86
naz
N - |y
if (s, b) E F:
return {(s, bgx) Es b 3z Vy 3b
87
88
return False
104
89
Complete: every input leads non-empty successor
90
91
for x' E X:
F' + (runc_buf,(sttep,,C (F,zz)
if F = 0: return False
93
94
if F & V: add' q (F))
95
return True
Figure 9: Frontier-based checks. is_cylinder(z, y) verifies universality via powerset BFS over projected frontiers. is_member checks for an accepting covering state; is_live checks whether the frontier is non-empty.
To check whether (x) S Ply), the fronticr-based is_ ss_cllddderrr applics trunc_buf to the frontier (x)) which truncates buffers to length |y]. yielding truncated frontier set of (s, b) pairs whose buffers are compatible with y. It then verifies universality via BFS over truncated frontiers: each successor frontier is obtained by applying step, followed by crunc_buf. Unlike the ordinary frontier, where buffers can grow without bound, truncated buffers must be prefixes of y, so at most |y|+1 distinct buffers exist, making the truncated frontier state space finite. Each truncated frontier corresponds to state of the determinized precover machine P, so the BFS terminates. The BFS checks that every truncated frontier is both accepting (some pair has b 2 y and s F) and complete (every input symbol leads to a non-empty successor). Without this exploration, two nondeterministic paths may yield the same string yet end in different states 81 and 82, where neither is universal on its own, although [f[..]] U [f( x 24 The precomputation of IP-universal states and a cylinder check shortcut are discussed in CC.6.
Universality is decidable for finite-state automata; efficient algorithms include antichain -assd simulation (De Wulf et al., 2006), hisimulation up congruence (Bonchi & Pous, 2015), and classical equivalence checking (Meyer & Stockmeyer, 1972).
21

---

When the cylinder check fails, membership reduces to checking whether the frontier contains covering accepting pair (b ł y and E F): if so, a E P(y) and a enters Rzy).
Liveness is non-emptiness of the frontier. Since frontier pairs already filtered to target-compatibl buffers, a non-empty frontier witnesses that some extension of can reach the precover.
C.3 PRUNING (prune)
Even when the decomposition is finite, the quotient and remainder can be very large. Enumerating all of them often impractical, so pruning is essential for scalability. 25 At minimum, prune drops source strings with zero prefix probability, since these cannot contribute any mass:
wos def prune (q'): return {ar E c px( 0}
This simplistic filter drops only strings with zero probability. In practice, we use a probability-man mass pruning strategy: given candidates q' with total mass Z = Emmgq' px (æ), we sort by descending px and greedily retain candidates until their cumulative mass reaches (1 - -))- Z or the capacity naaa is reached, whichever comes first. The resulting decomposition is approximate: discarded candidates contribute most Z mass per step, but the vanishes - 0.
107
def prune_ caame_prob__mee prrob_massCo (T, 1max))
108
def prune
M lq'l
109
q' <- sort_de port_descending((
key=px)
W (x)(2r) for a E q') # wn 2 WM
III
W + cumulative_sum(v)
113
+ WAr
q 0
for m E f1.... mnin(nnex: M)):
115
q (q
117
if Wm 2 (1 7)Z: break
118
return
119
return prune
Approximation bound.
At each step, the discarded mass is at most T T Z. As r + and Thax - oc, the algorithm converges the exact decomposition.
Finite termination. Even when the decomposition is finite, its size can be enormous. Pruning makes the algorithm tractable by bounding the queue at nhax candidates per step. and also guarantees termination for transducers whose decomposition is infinite DS.)...
Backtracking. Pruning may occasionally lead to dead ends where no valid extension remains. When this occurs while scoring an observed sequence, the next symbol receives zero conditional probability under the approximate (- (- y). We recover using the procedure Fig. 10, which takes the current target string y, the next symbol y, the current pruning threshold т. and hyperparameters: maximum retries Rt threshold floor Tmin, and maximum eviction depth Dmax- On each retry, is halved (floored Tmin prevent unlimited growth), and cached decompositions for prefixes of y are evicted at exponentially increasing depth D min D ), forcing decompose to recompute with the relaxed threshold. The original threshold is restored afterward. The procedure heuristic: there is no guarantee that a fixed number of retries with halved thresholds will recover. Frequent backtracking signals that the pruning threshold is overly aggressive; in such cases, the overhead of repeated eviction and recomputation can dominate runtime. In our experiments, we use R 20, Jwin 10 D Dmax 32. Backtracking is infrequent in practice: for S le-3, zero fallbacks occur across all experiments. At the coarsest threshold (T = le-1), the mean number of fallbacks per paragraph reaches most 96 for Pepc2 fa (max 159), 5.1 for Pspt2 fa o peb (max 18), and 0.4 for Pana f fana2na (max 5).
An alternative deterministic pruning is importance sampling with proposal distribution over source strings; leave this direction future work.
22

---

def backtrack (3, Tmin, Dmax):
121
TO +- T
for i E 1,... R:
123
T - max(T/2
(T/2, Tmin)
D f (2in Dmax)
124
125
for d E 0 D-1:
126
if d > ly|: break
evict cached decompose(y<clll
127
128
P - next_ dist(y)
129
if ply] 0:
130
T - return p
131
132
T + To raise DeadEnd
133
Figure 10: Backtracking. On each retry, halve r (floored at Tmin) and evict cached decompositions for progressively longer prefixes of (depth D min(2 max)), then recompute next_dist Restore T afterward.
C.4 FAST NEXT-SYMBOL. DECOMPOSITION (decompose_next)
Since (Q(vv)) S (Q(y)), we have P(yy)= ((Q())) n (Q(w)))) R(yy). The decomposition for yy can therefore be obtained with incremental work starting from Q(v) U(y). The structural reason monotonicity: the precover for y and yy share the same alphabet and initial states; only the accepting states differ, as acceptability depends on which buffers cover the target. This is formalized by the frontier containment property (Prop. C.1).
The decompose_ as the exact preimage fy)) This the key efficiency improvement over calling decompose(yv) independently for each y.
method computes Q(vv) and R(yy) for all y E y simultaneously, well
The BFS seeded with Q(y) (line 152). For each source string e the queue, we first check whether is exw.eetttmembbeerre..... y) (line 156) and, if so, record æ in the preimage set. Next, for each y E prrcchable_oupuut((aa y) (defined below; line 159), we classify x as a cylinder or member for yy: by functionality of f, most one y can be cylinder (Prop. C.4). If cylinder for some y, the entire subtree rooted at æ is absorbed we skip extension for all symbols (line 164). Otherwise, extend by all reachable source symbols (line 165).
found
The decompose_nest _eet algorithm relies on two mechanisms described next: target recursion for cheap frontier computation, and three frontier-based helpers. We now introduce these.
Target recursion. The call is_cyll ss__cylinderd yv) internally triggers rungy (2). Target recursion is used opportunistically when the parent frontier run, (æ) is already cached: the frontier for the tended target is derived by filtering rather than recomputing the entire source-string chain (Prop. C.I). This is the typical case in decompose_nte _extte where decompose(s) has already populated the cache. This optimization is transparent: is_cyl js_cylinder is called unchanged; the logic lives entirely inside run.
Per-symbol frontier helpers. The BFS loop uses three frontier-based helpers.
eeeeettteebberrrrreeee (æ, y) checks whether æ maps to exactly, i.e., is_exact__tme exxct__emmee(aa y) <> (f(z) y).
bbschable_inputsc.. y) conservatively approximates the set of source symbols x' such that extending by x' remains compatible with y, i... {a' E X: (axr") P(y) # 0). The pseudocode checks for transitions from frontier states whose extended buffer is prefix-coppatible with this may over-report when the resulting state cannot reach acceptance.
reachable @eachable_outputs(aa y) conservatively approximates the set of target symbols y' such that some extension of can produce yy as an output prefix, i.e., {v/ E ):: (z) n P(ye') + 0}. The pseudocode checks single-step transitions from frontier states, which may over-report (a transition from a frontier state that cannot reach acceptance) because the frontier is not cotrimmed. Symbols requiring multiple transitions to extend past y are handled by the expansion loop.
23

---

All three computed directly from the frontier runy (2)):
def "s__excc__eens (æ, y):
def reachable_outputs(ce y):
return 3(s, b) (xr) 135
14] F+ (a))(a)
b b= F
# y is read from b (committed)
y): 138 return {x' (8, b) E (x),
def reachable_inputee
143
# or y (boundary)
return {v' (s., E
(s =' s') E T, by = v y by
145
8') E T(s), yy 3 by/}
Expansion loop. The following algorithm combines the seeding, shortcuts, and helpers above into single BFS that computes the per-symbol quotients and remainders for every y E E simultaanoussly.
146
def decompose :ecooppose__ex(())::
147
(Q. R) decompose
148
t [h; rs t {
map set of x
140
ps
150
# Remainders were not cylinders for y, hence not for any yy (Prop. C.
151
non_cyl R
+ QUR
153
while lq > 0:
q'<0
155
for æ in q:
156
if is eeeeexttmemebrrr... y) ps aad
f(x)= yy exactly
157
# Check reachable at most one can have æ as cylinder (Prop. C. 4)
158
y 1+ 1 for in secchable_oututtsie y)
159
160
if T = and x & non_cyl and is_cylineer(a, yv):
asly).ad
< continue
162
if is ss_memberr(x, yv)
183
(x) (s)
164
if 7 * L continue absorbed + skip extension for all y for x' reachable_inputss(r.p
186
q add('x)))
187
q + pr"
168
return (qs, rs, ps)
Figure 1I: Fast next-token decomposition algorithm.
decompose_nextlg computes Q(yy) and R(yy) for all y E y in single BFS pass. The is_cy cyl_ideeree,,,, yy) call triggers runyy (x), which is computed cheaply via target recursion (Prop. C.I) since the parent frontier runy (x) is already cached. The non-cylinder shorteut avoids the universality check entirely for seeds in R(y). After the BFS, the cache is populated so that subsequent decompose(yu)) calls are free. The exact preimage is collected as byproduct: if a is cylinder for some yy, every extension produces output strictly longer than y, so no extension can be an exact preimage of y.
Cache population. After the BFS, the computed Q(vy) and R(yy) should be writ- ten into decompose's memoization cache. subsequent decompose(y1) call (e.g.. from decompose_next((ggg hits the cache instead of re-running its own BFS.
169 def decompose_next(y)):
170
# Populate decompose's cache for all children for y E qs.keys() U Us.keess)): cache|decomposs yv] <- rsly))
122
173
174
return
24

---

C.5 NEXT-SYMBOL DECOMPOSITION SHORTCUTS
The decompose_ next algorithm (Fig. 11) shares work across all output symbols by making single BFS pass for all output symbols at once instead of calling the decomposition for each symbol as in decompose (Fig. 2). By starting with the decomposition from the prior step and using target recursion, the overall frontier computations are reused. The remaining bottleneck is the per-symbol cylinder check is s__cylinder (Fig. 9). Three shorteuts avoid reduce this cost, each justified by proposition about the structure of the precovers. Non-cylinder monolonicity and cylinder uniqueness enable skipping BFS for some settings. Combined universality resolves additional symbols by examining how a frontier partitions into committed and boundary elements.
(1) Non-cylinder shortcut.
Strings in R(y) cannot be quotient elements for y. And since (Q(yn')) S (2(y)), they are not quotient elements for the strictly more restrictive yy either. The expensive cylinder check (line 160) is thus skipped for these seeds (line 151).
Proposition C.3 (Non-cylinder monotonicity). If x E R(y) then Q(yy) for all y E V.
Proof. We have that x E R(y) implies (a) g P(y). Since P(yu) C P(y), and thus (a) g Plyv). so x & Q(yv).
(2) Cylinder uniqueness shortcut. Since the transformations we consider are functions, at most one output symbol y can have x as cylinder element. Once cylinder element is found, the cylinder check is skipped for the remaining output symbols (line 159).
Proposition C.4 (Cylinder uniqueness). For a function f and target prefix y. x E Q(yv) n
Q(vv') = y = v'.
Proof. Suppose y + yy and a E Q(yy) n Q(wy'). Then (x) S P(yy) n (-y))"
f (vv')* )'") = 0. where the last equality holds because f is a function and yy)" Nyn' = 0. This contradicts (a)) o 0.
(3) Combined universality shortcut. Given a E Qly) and T E Y, we want to determine whether E Q(yÿ) using the covering frontier at y without running a full powerset BFS. The frontier run(x, y) partitions into committed elements (s, b) with b 2 yÿ (the accumulated output already extends past y with symbol ?) and boundary elements (s, b) with = y (the next output symbol is undetermined). The committed states alone may not be universal- some input symbols may lack outgoing transitions from committed states. Boundary states can fill the gaps, provided every transition from a boundary state produces δ its next output symbol.
Proposition C.5 (Combined universality). Let
Q(y), 7 E Y, and define S. = {s| (s, b) E run(æ, y), b 2 yū), S. {s (s, b) E run(ar, y), b = yy
If the union S. U Sy, is universal (i.e., (f((xx(((ssss)))) = X*,, S. CF O, and every transition from a boundary state produces G. except that E-input transitions may produce e (i.e., E Sp and T or (x = Ay e)), then x E 2lyū)
8 sny, s' E T implies
Proof. Let w' X be arbitrary. By universality of S. U Sn. there exists (s, b) run(æ, y) with E S. U Sj, such that has an accepting run on x' in the input projection. If E Se. then b > yy. so the output of the corresponding path in already begins with yv. giving xæ' P(yr). If s Sp. then b = By the exclusivity hypothesis, every non-s-input transition from s produces output S. and E-input transitions produce 7 or e. States reachable from s via E:E ares are also in S, (since the frontier is e-closed and the buffer is unchanged), so they satisfy the same constraint. Therefore the first non-e output along any path from 8 is y. and the output begins with yū, giving wax E P(yÿ). Since x' was arbitrary, (ar) C Plýū), i.e., x Q(yÿ).
This shortcut complementary to the IP-universality shortcut (Prop. C.6): IP-universality a per- state property, while combined universality is set-level property that leverages partial coverage from both committed and boundary states.
The proposition requires set-level universality of S. U S, (the input-proeection NFA started from those states accepts X²*.. In practice, we use a stronger but cheaper sufficient condition: we require every individual state in S. U S, to be in the precomputed U. This runs in ((F)) time, whereas the set-level check requires a powerset BFS that may be as expensive as the full is s_dylinddrr check this shortcut is meant avoid.
25

---

175
def Combinedduniveree
yy): b yy)
176
S. f {s (s,
E 6
covered
177
St
if S.EESUS (s. b=
boundary
178
U: return False
179
Non- input must produce 7; E input may produce E
180
for 8 E Sp:
for ( s:y $ T(s):
182
if not (y= = or (x (==sΛy=E))
183
return False return S. F 0
184
C.6
INPUT-PROJECTION UNIVERSALITY SHORTCUT (fast_univ_filter)
Recall that the cylinder check is_ s__yylnnderr verifies whether every extension of a source prefix maps through the target prefix, using a powerset BFS that be expensive. A cheap sufficient condition universal if the input projection of the
avoids it in many cases: a state s E S is input-projection transducer started from accepts all of X -itiituutivell. no matter what input follows, the transducer can still produce output. Let U C S be the set of all imput-projectinn universal states.
Proposition C.6 (IP-universalitty shorteut). some covering frontier state of x with respect to y is IP- IP-universal, then is a cylinder: (3, b) E run(ar v): b 2 A U) + x E Q(v).
Proof. Let (s, b) E run(æ, y) with b > and E U be the witness from the antecedent. Then [projx(((()) = X so for any x' E X², there exists an accepting run of on æx.' passing through with output prefix y. Hence war E Pyy). Since xf' was arbitrary, (az) C Pyy), i.e., 2(y)-
Fig. 12 shows how to efficiently precompute the set of input- prput-projection universal states. We first input-project the transducer and remove e-transitions (replacing each path S ... s' S s" with direct transition 8 - s": see, e.g., Hopcroft et al. 2001, Ch. 2) to obtain an e-free NFA A over X. Both operations preserve the state set: input projection drops output labels, and e-removal modifies only transitions (adding shortcuts through s-closures), so S, S and states in U correspond universal iff it is accepting and, for every X. has at least z-successor that is also impu-projjectin universal greatest treatest-fippoin condition. We compute the fixpoint in linear time using an algorithm analogous to Kahn's algorithm for topological sorting (Kahn, 1962): initialize the candidate set U the accepting states of and maintain per-state, per-symbol successor counts. When a count reaches zero, remove the state and propagate the change to its predecessors via reverse transition index. Each transition is processed at most once, yielding ([[T)) time.
directly to transducer states in the frontier.
state s of A is input-projectio
The shortcut can be integrated into is_cylinder (Fig. 9) as a fast path in is_
205
def (s_ y): # memoize
206
if fast_univ_filter(aa y): return True # fast path
N yvl 207
208
# continue BFS as before
For transducers in which most accepting states are input-projection universal, this shortcut avoids the universality BFS in is_cylinder for the vast majority of cylinder checks. In BPE, where all states are input-projection universal, the universality BFS is never needed.
C.7 MEMOIZATION AND BATCHING OF px
The source LM is queried in two places: first during decomposition, where probability-man mass pruning calls (x)) to rank candidates, and then during scoring, where prefix_prob and next dist sum px (x) and (xx over the quotient and remainder. These calls involve many overlapping source prefixes. Naively, each call recomputes the entire chain (x1) (x22 x1)- --. from scratch. Memoizing the conditional (- x) avoids this: given a cached state for æ, extending by one symbol requires single conditional evaluation rather than replaying the entire history.
For transformer language models, the cached state is the key-value (KV) cache: the accumulated key and value tensors from the self-attention layers. Extending by one token reuses the cached KV entries and runs a single forward pass for the new position. Moreover, most LMs return the complete next-symbol distribution p.( ax) in single call, cache the full distribution rather than
26

---

185 # Preprocess: input-project and g-remove
186 + cps-removc(proix([]
queue-based greatest fixpoint
Is + FAi q
count|,, <
190 for (s 4 s') T with s' U:
count(s. +=1
192
for 8 E U:
193
if 3x E X: count(s (s, x] 0:
194
q (s)
while a 0):
s' - ppppp))
196
U {s'}
for (s with S s') E Tx
198
199
countss, [s, x] -
200
if count (8, a] = 0 and 8 E:
as)
202
def
203
Does any covering frontier state have a universal input projection? return 3(8,b) b) E run(a, y): b y U
Figure 12: Efficient computation of input-projection universal states and the fast_univ_filter method that uses them.
individual values. When the extension loop generates children 2001,-- ... w.a,, their prefix probabilities are read directly from the cached distribution without additional LM calls. 26
Batching while pruning. The prune step ($ C.3) needs (x) for every string in the queue. Many of these strings share a common prefix but extend by different symbols. We group the queue by parent: for each parent æ &<N whose next-symbol distribution p²(- .<N) not yet cached, we issue a single batched LM call. Each call returns the full distribution, from which Px (x<NZ) (=<N)) (x(
x<N) is read off for all children simultaneously. On GPU-based LMs, batching these parent contexts into single forward pass amortizes the per-call overhead.
C.8 REALIZING THE AUTOREGRESSIVE INTERFACE
Given the decomposition, the transduced LM interface from $C.1 is implemented follows. The prefix probability (yy sums LM prefix probabilities over Q and LM string probabilities over R. The string probability (3) sums over the exact preimage. The next-symbol distribution p 3) is computed via decompose_nevt _exxt, which provides the per-symbol decompositions and exact preimage in single BFS pass; the computational cost is dominated by decompose_nent and once the per- symbol quotients, remainders, and preimage are available, the scoring reduces to lookups into the memoized source LM (SC.7).
209 def prefix_prob(y): (Q,R) <- decompose (y)
215 def next_ text_dist(y):
(qs, rs, ps) decompose_next(y))
211 return Eec (x) + Emca (x)
P + { + prefix_prob(y))
217
212 def prob
218
for
ps: 7[Bos] += px (x
for E qs.keys() Urs.keys()
(__ps)) ps) decompose_nextt()
219
for x qs ys ply] += (x(x)
214
return Σmeps (x)
220
221
for a rryy:: y plu] += px(x)
222
return p
Figure 13: Fast implementation of the autoregressive interface using decompose_nexx
Our implementation uses genlm (https://gi wtwp:/uwww..omggen//ggeeeeleeeee backen)) for its seamless caching and auto-batching interface.
27

---

For reference, the naive next-symbol distribution computes prefix_prob(ppg independently for each y (see $C.11. The reference implementation correct, but inefficient because it does not share work: each pref prefixprrobyys/ call triggers its own decompose BFS, and it does not benefit from the non-cylinder shortcut, target recursion, or cache population described in $C.4.
C.9 ALL-UNIVERSAL FAST PATH
When every transducer state is IP-universal, the remainder always empty and every newly discovered element is immediately quotient element, so decomposition terminates in a single BFS round. If, additionally, every non-e-input are produces least one output symbol, then boundary frontier elements can be resolved in closed form via a precomputed first-output table. Together, these two conditions let next_dist (Fig. 13) simplify into all__nnveersal.. saarrsal__ext__ee mext_distt (Fig. 14). We describe the simplifications below (normalization is unchanged).
Decompose (simplified). Because every state is IP-universal, R(y) = 0 for all y: every source prefix in the precover is in the quotient. The call to decompase(y) (Fig. 2) terminates in a single BFS round-every newly discovered element is immediately classified as a quotient element. This makes decompose_nexx unnecessary: the per-symbol classification is absorbed into the scoring below.
Score (simplified). For each (F, a:) E Q, the frontier partitions into committed elements (s, b) with b > y and boundary elements with b y, in the combined universality shortcut ($ C.5). Committed elements have already determined their next output symbol 7 = bN+1; because all states IP-universal, each contributes (x:) directly plu]; thus, expansion is needed.
Boundary elements (b = 3/) need one more source symbol to commit to an output. The no-s-u precondition ensures that each non-s-input are produces at least output symbol, first-ouiput table fo(S, x) (defined in the pseudocode) maps each input symbol to the unique output it produces from given powerstate. This symbol is unique: functionality of requires that all transitions on æ: from states in S produce the same output, since IP-universality guarantees each successor has an accepting continuation (so both outputs would be realized). Each boundary element is thus resolved with a single batched LM call: L = (- x) is queried once per quotient element, (a))- {(x) is attributed fo(S. z)) If any boundary state is accepting.
precomputed
and for each X, the mass (x) the LM's EOS probability contributes (x) {(FOS) to p[EOs].
The fa transducers satisfy both preconditions (Tab. 4: all states IP-universal, no E-output on non-E- (87). The DNA transducer fdna2na has all states [P-universal but uses e-output ares (the first two bases of each codon emit no amino acid), so the fast path does not apply.
input arcs), explaining their substantially higher throughput
28

---

def all [lL_umiversa__nxx_ddst((/))
241 def fo(S,
(0. decompose(y) # R = 0 always
for (_ -: s') E x))
242
225
- [}; + prefix_prob(t)
243
Unique if functional all states IP-universal
for (F, in Q:
244
227
Committed output past target for ÿ {bN+1 (s, E F, by v):
245 return y
return 1
229
Plu += pz(x)
Boundary: output = target S. + {s (s. E b y}
231
if #000 0:
233
{ E<px' px( x))
# one LM call
for E X:
235
1 + fo 2),
236
if ū 1:
p += (x( ((r)
238
if 3 S.: S.:EEF
D[BOS] += (x) {(BOS)
240
return D/Z
Figure 14: all_universal_nex _istt: specialization of hext_disi (Fig. 13) when all states are IP- universal and every non-e-input are produces output. always, so only Q contributes. Boundary elements resolved via fo, requiring LM call per quotient element.
29

---

D PROOFS FOR FINITENESS CONDITIONS
D.1 PROPERTIES OF PREFIX MONOTONE MAPS
Proposition 6.1. The following are equivalent: (i) J is prefix monotone (ū) [((a)) S (f(x)) for all æ E X (iii) P(f(()) = C(f())) for all a E X (iv) f is prefix-continuous.
Proof. (1) + (2): Prefix monotonicity means that for any æ, x' X", if we have that 3 wæ' then f(x) 3 f(xx') and thus that there exists a y y such that f(xx') = f(x)y. And since x' was chosen arbitrarily (2) holds.
(2) = (3): Let E X Suppose f((x)) S (f(x)). Then, (a) S (f((() S P(f(z)) Note that, for any x' E P(f(#)) P(f(x') S P(f())). Therefore, (x') S P(f(z') C P(f(z) and so x' E C((())) This shows that P(f(z)) = C(/(a))
(3) (4): By assumption, any element in the precover is extension of quotient element, and thus a member in the cylinder over quotient elements.
(4) (1): Assume is prefix-continuous, i.e., P(y) is cylindrical for all y. Let x'. Since
f(x:) 3 f(x). we have æ E P()(x)). By prefix-continutty, (()())) is cylindrical, so (œ) S
(a)( In particular, o' E P[[(z)), which gives f(x) 3 fax'..
30

---

D.2 QUOTIENT BOUND FOR STRICT-PREFIX MONOTONE MAPS
The following proposition bounds the size of the quotient when the map is strict-prefix monotone.
Proposition D.1. Let f: X + y be a strict-prefix monotone map. Then, for every E y
(y) 2(v) eyy ( LyEY Q(vv) S 2(y) (2 {+}) [Q(v)) (1,8+ 1)lm!
Proof. (1) Observe that (using Proposition 6.1) for every )
C(y) = P = f (8) ( L
P(yv) f f (v) L NEY
c(vv)
(11)
NEY'
In partieular, the minimality of 2(y) in Ply) implies that
( n (vv) 2(v) L
(Q(yy)
(12)
yEY
VE>
Consequently, we obtain the identity (y) = C(v) \ L C(vv) = (Q(v)) \ (ee which in turn yields the inclusion
2(v) L 2(v))= 2 \ L (Q(0)) DEY
(13)
VEY
For the reverse inclusion, let w E (z). Then there exists unique Dy E Q3y) such that w 3 x', by definition of the quotient set. Since f is strict-prefix monotone and f(xg) 3 fxx'( ) = we must have 2.g = x'_ This shows that (1) C Q(y), and completes the proof of (1).
(2) Fix y V/ y E )" and let Qyyv). There exists unique By Q such that By Intersecting (m,,) with both sides of (11), one obtains
(xx,) = -(x,) n ff (v)) L L ((x)) nc(ye')
(14)
V'EY
= ((x,, nf (v)) (z) (Z) LC2
(15)
where C def Lyver (((yy)) \ (z). Note that this set is cylindrical. By strict monotonicity we have (m,,)) n (f--((1)) (v)) Hence either: (i) (x.,) ()) 0, in which case
By Q(y) n Q(vv),
or (ii) (xn)) ns (g) (a.)). Then there exists a word = E X such that x = Z, Let z'' < z. 2' Fe, then 2 E Cz. Since C., is cylindrical, it contains (Ir,=") and in particular it must contain (x) contradicting the definition Cz, Therefore no non-empty proper prefix z' exists, so is single symbol x E X and
x == E Q(v)x.
(3) For any
) and any y E V, we have from (2),
[Q(yy) - (IX1 + 1))
(16)
Iterating this bound along any string y E )", we have:
[(v)) < ([1)) 1)leI (1X1 + 1)le
31

---

D.3 SUFFICIENT CONDITIONS FOR FINITE QUOTIENTS AND REMAINDERS
Lemma 6.1 below gives sufficient conditions for when one can derive finite precover decomposition. An example of such a transducer given in Example 3.
Lemma 6.1. Let f: + y be a function realized by a transducer f. The decomposition (Q(v), R(y)) is finite for every y y if:
(i) No e-output eycles: f contains no cycle in which every are outputs E.
(ii) Safety: Every state of f is safe, defined inductively as the smallest set such that is safe if: (a) is IP-universal; (b) [[ < oo (finite closure); or (c) for all transitions 8 _ s', is safe.
Proof. Fix y E 3"; we show that 2(y) and R(y) are finite. Let Ily be the of all paths in f SNWN SN so E 1, YN = y). By condition (i), the e-output subgraph of is acyclic, so any sub-path that emits no output has length at most (S). Since the total output is y, each path has bounded length, and Hl is finite. Let IIy be the set of all valid paths formed by extending the roots in II until they reach a state satisfying safety base case. By condition (ii), every state of f is safe in particular, the end states of paths in Hy, This implies that no extension path can continue indefinitely without satisfying a base case (IP-universality or finite closure). Since finite-state transducer has finite branching and no infinite valid extension paths, Kónig's ' Lemma implies that the tree of extensions is finite." 27 Thus, II is a finite set.
that emit exactly y. i.e., 1ly {s0 2133, 81 81." SN-1
< s0) be the sets of states satisfying conditions (a) and (b), respectively, and let S Sy U US. We can decompose the set extended paths disjointly based on their end state:
Let Sy def {s E S: is uniierrerall] and Sc def {s S: [[]
1x {p ilzui Piel Sy) u tp llzui : Plal Sc}
(17)
[TT S|ml "t sN π E SN Su, ( Ssa = 0}
f | 5|m] " SN T E E Sc,
= 0}
(18)
The first term corresponds to Qyy) by definition. Since II is finite, this set finite. The second term collects paths leading to states s Sc. The remainder Ryy) consists of the input strings from these paths, concatenated with the finite language accepted by Since the number of paths is finite and the closure of each stopping state is finite, R(y) is finite.
d}, encoding a (partial) function f. The four states illustrate all cases of safery. State 83 is universal: it is accepting and loops on every input symbol with E-output, so I(s3) = X (base case a). State $2 has finite closure: it is accepting with no outgoing transitions, so [.(2) = {E} (base case b). State 81 neither universal nor finite closure, but is safe by the recursive step (c): its successors 53 (via a) and s2 (via b) are both safe. Similarly, so is safe because its successors 81 (via a) and 82 (via b) are both safe.
Example 3. Consider the transducer below over X' =
For target a, the path set II = {su - $1} is finite (condition i), with terminal state safe (condition ii). Extending from s1: input reaches the universal state 83, contributing aa to ((a): input b reaches the fnite-closure state $2, contributing ab to R(a). The root string a is also in R(a): 81 is accepting with [(a) x a, but is not cylindrical since ab cannot be further extended (stuck
a
at 82). Thus Q(a) {aa) and R(a) (a, ab).
K'nnis' Lemma states that every infinite tree with finite branching must have an infinite path. Since our alphahet is finite (finite branching) and the Safety condition forbids cycles among non-base-case states (no infinite paths), the resulting of extensions must be finite.
32

---

X
ara
a:d
93
b:b
b:b
82
33

---

E EXAMPLE DECOMPOSITIONS
We give three concrete examples of decompositions and prefix probabilities.
Example 4. The transducer below merges consecutive backticks ( ("") into quotation mark (") but otherwise keeps the symbols a and fixed. can be seen as a minimal example of text normalization.
a:a
ata
(19a)
When computing the prefix probability p () sequences starting with two backticks get mapped to a quote and thus do not appear in the precover. Instead, single bucktick remains in the remainder, while a backtick followed by a goes into the quotient, as any further extensions preserve the initial backtick. We thus have (by visually canceling out continuations that get mapped quotation marks),
P() = -
Jut "a", aa.....
(19b)
= ={)
(19c)
Thus,
('aaa.
a). Similarly, we have P(")= ={ } and thus p}(") px('))
Example demonstrates the efficiency of using the remainder and the quotient: both sets only have single element, yet they fully specify what probabilities contribute to P("). There are, however, edge cases that do not lend themselves to such efficient decompositions.
Example Consider the following mapping I and its representation as a transducer
a.b
qi
f(a")=
b" = if n is even else ca
(20a)
a.c
with X [a} and c). The precover for is given
P(b) {f, p, aad, aaaa, paaad, aaaaaa,...
(20b)
This example is, unfortunately, challenging for our approach as the remainder set is not finite:
R(b) = { > 0} @(b) =
(20c)
In other words, the mapping never releases the evenness constraint, and we sum forever.
Finally, we give an example of simple transducer with single remainder element in Example Example 6. Consider the following mapping f, visualized in Fig. 15.
ʃ(a") = b" if n. + 2 else X (a) and y {b, c). Suppose want compute the prefix probability (b).
(21a)
P(b) {a. 36, aaa, aaaa, aaaaa,... ...)
(21b)
R(b) = (a}, 2(b) {aaa}
(21c)
Thus.
p3(b) Σ (x( Σ (x)
(21d)
*ER(0)
xE
= px (a) + (axa)
(2le)
34

---

e:b
ate
qu
Q1
q4
a:b
a:e
8:C
a:b
e:b
8:b
q3
45
96
Q7
Figure 15: An FST that maps occurrences of 'a' to the same number of 'b's, except when the input exactly two "a's, which are mapped to 'c'.
91
b:c
a:g
go
b:c
a:c
a:c
Q2
Figure 16: An FST where the E-output 90 Q creates frontier element whose output has not yet reached the target. For target y c and source prefix æ = a, the frontier F ((gi,)) (q2, c)). The covering states {92) are not input-projection universal (g2 has on b), so ffileer(a, c) fails and a would be misclassified as non-quotient. However, qi handles bast_univ_filter(a
input and produces c, matching the target. The BFS in is is_cylslllll ss__cylnnee confirms universality over the full frontier, correctly placing a in Q(c).
35

---

F EXPERIMENTAL SETUP
Here we detail the experimental setup for reproducing the experiments in $7 and $G.5.
F.1 DATASETS
For the tokens-to-bye bo-ttee and PTB experiments in $7, we choose the first 10 paragraphs (excluding headers) of the test split the wikitext-22raw-vy dataset (Merity al., 2017) (corresponding to the first 7684 bytes) from the Hugging Face datasets library. We use the first 256 bytes of the same dataset and split to run the experiments in & G.5. For the DNA experiments in $7, we sample 65 human proteins each consisting of 4-12 amino acids, with their accession numbers given in Tab.
Table 1: Accession numbers used in this study.
COHLZS
PO1858
PODPI4
PODUSO
P84464
P84465
PODOYS
P67857
P67858
P67859
P81826
P23210
P85003
P84071
P86168
COHJFI
COHIGO
PO2729
P81010
P86909
P86922
B3EWE5
P0DMM6
PODQM6
PODQM7
P12481
P85002
B3EWR3
PO1358
PO2728
POC005
PODKX2
PODMM7
PODQM9
PODX30
P22103
P84200
P84785
P84868
P86600
A8C8X2
B3A0L6
B3EURS
C0HJM6
C0HLK7
PODJC3
PODJF4
P69208
P85444
P85870
P86942
A0A0AOMTS9
B3EWS0
CОHJB6
CUHL84
COHL88
POCSI8
PODQH7
PODQH8
PODQX4
PODQX5
P58805
P69437
P82820
P83127
F.2 MODELS
We conduct experiments using GPT-2 Large (Radford al., 2019), Llama 3.2-1B, Llama 3.I-BB and Phi-4 (14B; Abdin al., 2024) from the @ Hugging Face hub (Wolf et al., 2020). We use the GenLM library330 and the vLLM (Kwon et al., 2023) backend to efficiently evaluate the models.
convert token-level models into byte-level models and compose them with f fptb For GenLM G.ntMs we use a beam size of K=5 and a pruning threshold of 0.001. For the DNA experiments we train a custom GPT-2 Small model on a human DNA d3 The token set of the model is X' {A, C, G, Т} eliminating the need for composing the model with a transducer fo that maps from subword tokens to bytes. For training parameters, see Tab. 2, for training and validation metrics, see Tab. 3.
For the PTB experiments
Gyte
F.3 PARAMETERS
For all experiments, we use the pruning heuristic described in SC.3. For the experiments in $7 we report the results for different values of Tlax E (5000, 10000, 15000, 20000, 25000, 30000). For all other experiments, we set Thax 00.
F.4
GPU USAGE
All experiments in $7 use single NVIDIA GeForce RTX 4090 (24 GB), except Phi-4, which requires two. The benchmarks in G.5 use an NVIDIA GeForce RTX 3090.
Available under openai/gpt2-large,
meta-llama/Llams- 3-2-1B, meta-1lama/Llame 1 1-88 and
microsoft/phi-4 https:://uugiingfacee
30 "https://gi thub. http:uuw...ocooogeee//oonnnnla-a
32 http:tttbb...////e/////mmm///b/
36

---

Table Training parameters for the GPT-2 small model, trained on human DNA.
Table 3: Training and validation metrics for the
GPT-2 small model, trained on human DNA.
Parameter
Value
Step
Epoch
Train Loss
Val Loss
Acc ( (%)
Learning Rate
0.0003
5k
0.69
1.1252
1.1206
47.45
Optimizer
AdamW
10k
1.38
1.0835
1.0814
49.91
= 0.99 92 0.999.
15k
2.07
1.0641
1.0639
51.03
1e-8
20k
2.76
1.0563
1.0547
51.63
Learning Rate Scheduler
Linear
25k
3.45
1.0504
1.0486
52.04
Warm-up Steps
1000
30k
4.14
1.0439
1.0439
52.33
Train Batches (per device)
64
35k
4.84
1.0425
1.0407
52.54
Eval Batches (per device)
40k
5,53
1.0365
1.0380
52.71
Total Train Batches
256
(262,144 tokens)
45k
6.22
1.0325
1.0361
52.84
Total Eval Batches
32
50k
6,91
1.0322
1.0341
52.96
Epochs
10
55k
7.60
1.0307
1.0328
53.05
Seed
42
60k
8.29
1.2667
1.0316
53.13
Distributed Training
Multi-GPU (4 devices)
65k
8.98
1.0273
1.0306
53,20
Mixed Precision
Native AMP
70k
9.67
1.0270
1.0299
53.24
F.5 DETAILS ON TRANSDUCERS USED EXPERIMENTS
Tab. contains the number of states, IP-universal states, and transitions for the transducers described in $7. We construct all State transducers using Pynini (Gorman, 2016). Note that for experiments using the Penn Treebank FST ptb), we realize px o fa using GenLM.bytes thereby keeping the number of states and arcs constant.
Table 4: Number of states, IP-universal states, and transitions.
Model
States
IP-Univ. States
Transitions
Tokens Bytes
Papt2
75,723
75,723
125,979
Pilama1B fa
176,990
176,990
305,244
Pilama8B fa
176,990
176,990
305,244
Pphi4 fa
115,244
115,244
215,593
Tokens Words
Papt2 fa o fpb
479
26,962
Pilama1B fa fptb
479
56
26,962
Pilama8B 0 fa fptb
479
56
26,962
Pphi4 fa fptb
479
56
26,962
DNA amino acids
Pdna
dma2aa
21
21
84
Constructing the PTB transducer. We construct the PTB FST by encoding each tokenizer rule34 as an FST that segments character sequences by inserting a distinguished separator symbol SEP & y. Specifically, the transducer inserts SEP at punctuation and clitic boundaries, and collapses whitespace characters (spaces, tabs, newlines, etc.) into SEP. Note that the resulting transduced language model thus not a true distribution over PTB tokens, but over characters and separators corresponding to the same boundaries that the PTB tokens would have. This is pragmatic decision, as the PTB tokenizer can tokenize any sentence into orthographic words. In other words, it would accept an infinite vocabulary. Such a transducer can be built on the fly and would be equivalent to one with infinitely many states. In this paper, we only use the finite version. An example such rule is given in Fig. 5, which inserts SEP before comma if it not followed by digit. We then compose
3SSee https: http///wwttttt http:////.mmuuue///./tttoeeeeeea
html #T FrrebannkordTTokeniiz.. for
the full specification.
37

---

these FSTs into single transducer (f pcb). Note that context-dependent rules, such as the given in Fig. 5, introduce non- non-ePluniversal states. For example, state Q2 only accepts æ X' { {0-9, }. In fact, of the 479 states in f pth. just 56 are univeerrral..
The DNA to amino acid transducer. partially shown in Fig. 17.
The DNA to amino-acid transducer, described $7, is
AcK, C:N, G:K, T:N
QAA
Ats
A:s
QA
C:E
QAC
...7
C,G, Tis
G:6
T:8
QAG
QAT
Figure 17: An FST for converting DNA sequences to amino acids. Each triplet of nucleohases maps to one of 20 different amino acids. We only show proportion of the machine.
38

---

G ADDITIONAL EXPERIMENTAL RESULTS
Here provide complementary results the experiments presented in $7, using the algorithms described in $C. First, in $G.1 we compare our transducer-based method using fa to GenL.. bytes (Vieira et al., 2025a), then give full JSD (SG.2) comparisons for for ptb, and dna2aa- In $ we port cross-entropy comparisons for fo. and finally ablate the importance of IP-universal states (SG.5).
G.1 COMPARISON TO VIEIRA AL. (2025A)
Vieira et al. (2025a) convert token-level models byte-level models using beam-search algorithm parameterized by beam size K. We compare our transducer-bast approach with their method by computing the JSD between the two resulting distributions over the paragraphs from WikiText ($F). Tab. 6 uses genlm-byter (K = 32, pruning threshold of 0.0) as a reference and varies our pruning threshold т. As T decreases, JSD drops, and our distributions converge the baseline. At moderate thresholds (r S le-3), JSD is already below 1.5e-3 for all models, confirming that the two methods produce closely matching distributions.
To verify that the two methods compute the same underlying distribution the exact setting, we compare them with no pruning:
Table 5: Exact comparison: our method (r 0) vs. genlm-bytes (ex- act) for P2pt2 o f..
0 (no pruning) for method and exact inference for genlm-bytes (K = oo). Tab. shows the per- position JSD and maximum absolute difference for the first 10 bytes of the WikiTexx evaluation data using PEPt2 o fa- The JSD values
Pos
Byte
JSD
max AApl
the order of 1e-14-le-15, and the maximum absolute probability difference at most 3.4e- confirming that both methods give the same distribution within floating-poin precision.
0
3.9e-15
7.9c-7
I
6,5e-16
1.2e-6
2
3,5e-15
1.2e-6
3
4.4e-14
1.7e-6
4
4.5c-15
3.4c-6
Tab. reports the JSD and throughput of the baseline itself at K E {8, 16, 32}. showing the accuracy sccuracy-speed trade-ofi off within their method. Reducing K from 32 to 8 substantially increases throughput while introducing only modest changes JSD, indicating that the baseline's approximation error at K 32 is small. Note that the method of Vieira et al. (2025a) is designed specifically for strictly prefix monotone transformations, a property that fa satisfies. This specialization enables trie-based algorithm that achieves better accuracy-speed trade-off than our more ceneral-purpose approach on this class of transformations.
5
1.8c-15
2.4c-6
6
1.1c-14
1.4c66
7
B
1.9c-15
1.8c-6
8
6.1e-15
1.2e-6
9
1.3e-14
1.Se-6
39

---

Table 6: Average Jensen-Shannon divergence (JSD) and bytes/sec for various thresholds using Px o fa against reference distribution from Vieira et al. (2025a) with a beam size of K=32. 95% confidence intervals are given in parentheses.
Pgat2 fa
PiaamaBB o f.
7
average JSD/ byte
bytes sec
average JSD/ byte
bytes sec
Ic-1
4.0e-2 (3.7e-2, 4.2c-2)
70.95 (64. 14, 79.65)
2.8c-2 (2.5c-2, 3.0e-2)
84,21 (71.77, 99.54)
3c-2
1.9e-2 (1.8e-2, 2.1e-2)
44.68 (40.59, 48. 66)
1.2c-2 (1.1c-2, 1.4e-2)
72.23 (65.87, 78.10)
1c-2
6.7c-3 (5.8c-3, 7.8c-3)
25.13 (23.83, 26.69)
4.2c-3 (3.5c-3,
40.45 (37.60 43.43)
3e-3
2.5e-3 3,33--,
10.48 (9.89, 11.12)
1.le-3 (8.4e-4, 1.3e-3)
22.09 (20,94, 23.51)
le-3
1.4e-3 (9.3e-4, 1.9e33)
6.21 (5.89, 6.59)
4.0e-4 (2.9c-4,
11.86 (11.27, 12.49)
3e-4
7.6e-5 (6.0e-5, 9.9e-5)
1.97 (1.84, 2.11)
1.3e-4 (1.le-4, 1.5e-4)
5,90 (5.60, 6.22)
lc-4
3.7e-5 (3.0c-5, 4.7c-5)
0.65 (0.61, 0.71)
8.8c-5 (8. 18-1.,, 9.5e-5)
2.15 (2.04, 2.26)
30-5
2.5c-5 (2.4e-5, 2.7e-5)
0.21 (0.19, 0.22)
7.8c-5 (7.3e-5, 8.3e-5)
1.20 (1.15, 1.27)
le-5
2.5e-5 (2.3e-5, 2.7e-5)
0.19 (0.17, 0.21)
7.4e-5 (6.9c-5, 7.7c-5)
0.62 (0.59, 0.66)
Plaaman o fa
Pphia o fa
7
average JSD/ byte
bytes sec
average JSD / byte
bytes / sec
lc-1
2.2c-2 (2.0c-2, 2,4c-2)
79.03 (71.08, 87.28)
2.5e-2 (2.3e-2, 2.7c-2)
41.04 (36.96, 96, 45.33)
3e-2
8.8e-3 (7.7e-3, 1.0e-2)
66.41 (62.69, 70.69)
9.7e-3 (8.6e-3, 1.1e-2)
36,20 (33.26, 38.87)
le-2
3.5e-3 (2.9e-3, 4.2e-3)
45.47 (43.10, 47.91)
4.6e-3 33..ee3,55.4e))
22.85 (21.14, 24.77)
3e-3
1.3e-3 (9.3e-4, 1.8e-3)
26.71 (25.11, 28.34)
1.8e-3 (1,44-3,
14,80 (13.70, 15.83)
le-3
5.1e-4 (2.9e-4, 8.4e-4)
15.73 (14.88, 16.60)
(5.0e-44 1.3e-3)
8.75 (8.30, 9.27)
3e-4
1.3e-4 (1.le-4, 1.5e-4)
9.08 (8.68, 9.57)
1.9e (1.4e-,, 2.5e-4)
4.87 (4.60, 5,16)
le.4
9.1e-5 (8.0e-5, 1.0e4))
4.03 (3.84, 4.23)
1.0e-4 1.2e-4)
2.19 (2.07, 2.33)
3--5
7.5e-5 (6.8e-5, 8.3e-5)
2.38 (2.27, 2.49)
7.6c-5 (6.8c-5, 8.4e-5)
1,30 (1.23, 1.37)
16-5
7.3e-5 (6.6e-5, 8.1e-5)
1.40 (1.33, 1.47)
7.9c-5 (7.2e-5, 8.8e-5)
0.74 (0.70, 0.79)
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.
Pept2 fa
Pilama1B f.x
K
JSD
32
bytes sec
vs =32
bytes sec
8
3.0e-5 (2.5c-5, 3.9c-5)
37.81 (37.59, 37.98)
7.1c-5 (6. 7c-5, 7.6e-5)
46.94 (45.69, 47.97)
16
2.4e-5 (2.3e-5, 2.7
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)
PlaamBBB
Pohic fa
K
ISD vs 32
hytes see
JSD vs K=332
bytes / sec
6.8e-5 (6.3e-5, 5.
18.30 (18.17, 18.43)
4.6e-5 (4.3e-5, 4.9e-5) 5.3c-5 (4.9c-5, 5.60-5)
11.59 (11.29, 11.80)
16
6.9c-5 (6.2c-5, 7.8 7.8c-5)
10.55 (10.45, 10.65) 5.85 (5.79, 5.91)
7.90 (7.84, 7.96) 4.51 (4.44, 4.56)
32
(not applicable)
(not applicable)
G.2
DIVERGENCE
We benchmark how well the algorithm given in $C approximates the exact distribution when using high pruning thresholds the probability mass pruning described in $ C.3. Across all three PTB tokenization, and DNA-to-amino-acid JSD decreases as 7 decreases, the cost of throughput (bytes/sec).
Tab. 8 reports the token-to bottee results (px a for all four models. JSD drops by two to three orders magnitude from le-1 to 3e-5, with the tightest thresholds reaching JSD below le-4 for all models.
Tab. gives the corresponding results for PTB tokenization (px a fa ppb), complementing Fig. (right). Although peb has fewer states than the token-to-byte transducers, only 56 of its 479 states are IP-universal, making lower thresholds computationally expensive; the reference is therefore 7 = le-4 (3e-4 for Pphia) rather than le-5. Despite this, JSD converges quickly, reaching the order of le-5 at = 3e-4 for Poot2, PilamalB, and PilamaBB, while Pphit converges more slowly.
40

---

Tab. 10 reports the DNA-to-ann tottttommooaaatt acid results (Pána fdua2aa), where additionally vary the candidate- set cap Rmax to mitigate the combinatorial blow-up inherent in the three-to-ooe to-one nucleotide- to ao-amino-acid mapping. Tighter thresholds generally reduce JSD. However, the interaction between T and naax is less uniform, as both the evaluated and reference distributions depend on the cap.
Incomplete runs. As shown in $ G.3, the decomposition size grows rapidly tight thresholds mean [Q] exceeds 35,000 at = le-5 for fa- For some model-thheshon combinations, this growth prevents calculating the full distribution each position in all ten evaluation paragraphs. Specifically, Pgpt2 fo in Tab. completed only 7 of 10 paragraphs at T = le-5. In Tab. 9, Pphi4 fo o pth completed 7 of 10 paragraphs its reference threshold of r 3e-4, and Pilama1B f o ptb completed 9 of 10 at r = le-4. Additionally, Pphi4 o o f completed only 9 of 10 paragraphs at le-1 due to an unrecoverable backtracking failure (Fig. 10). In these cases, JSD and throughput are computed over the paragraphs shared across all thresholds for that model-transducer combination.
Table 8: Average Jensen-Shannon divergence (JSD) and bytes/sec for various thresholds using Px of against reference distribution (T =le-5). 95% confidence intervals are given in parentheses.
Pgat2 fa
PiaamaB fa
average JSD/ byte
bytes sec
average JSD/ byte
bytes / sec
le-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)
le-2
5.9e-3 7.1ee-)
25.71 (24.08, 27.89)
4.2e-3 5,
40.45 (37.65, 43.43)
3e-3
2.1e-3 2..9-)3
11.22 (10.44, 12.07)
1.le-3 (8.5e-4. 1.3e-3)
22.09 (20.90, 23.34)
le-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)
3c-4
5,5c-5 (4.7c-5, 6.7e-5)
2.28 (2.09, 2,48)
1.2c-4 (1. (1.1c-4, 1,4c-4)
5.90 (5.59, 6.23)
lc-4
3.6e-5 (2.9e-5, 4.8e-5)
1.00 (0.92, 1.09)
7.4c-5 (6.9c-5, 8.0c-5)
2.15 (2.03, 2.26)
3o-5
2.4e-5 (2.2e-5, 2.7e-5)
0.44 (0.40, 0.49)
5.2c-5 (4.9c-5, 5.6c-5)
1.20 (1.14, 1.26)
le-5
(not applicable)
0.19 (0.17, 0.21)
(not applicable)
0.62 (0.59, 0.65)
PiaaaaB average JSD/ byte
fa
Pphis fa
bytes
average JSD/ byte
bytes / sec
le-1
2.3e-2(2.1e.2) 2.5e-2)
79.03 (71.62, 87.24)
2.5e-2 (2.3e-2, 2.7e-2)
41.04 (36.75, 45.30)
3e-2
8,9e-3 (7.8e-3, 1.0e-2)
66.41 (61.90 16.99,777 70.51)
9.9e-3 (8.7e-3, 1.le-2)
36,20 (33.36, 38.85)
le-2
3.5e-3 (2.9e-3, 4.4e-3)
45.47 (43.16, 48.08)
4.7e-3 (.,6e-,,,6663)
22.85 (21.06, 24.55)
3o-3
1.3e-3 (9,4c-4, 1.8c-3)
26.71 (25.17, 28.24)
1.8c-3 (1.3e-3,2.4e-)
14.80 (13.74, 15.78)
le-3
5,2c-4 (3.0c-4, 8.4c-4)
15.73 (14.89, 16.61)
8.3e-4 (4.8c-4, 1.2c-3)
8.75 (8.30, 9.27)
3e-4
1.2e-4 (1.1e-4, 1.4e-4)
9.08 (8.64, 9.60)
1.9c-4 (1.1e-4,
4.87 (4.61, 5.19)
le-4
8.3e-5 (7.3e-5, 9.6e-5)
4.03 (3.83, 4.26)
7.4e-5 le-5, 9.2e-5)
2.19 (2.05, 2.33)
3e-5
5.9e-5 (5.3e-5, 6.6e-5)
2.38 (2.27, 2,49)
3.7e-5 (3.4e-5, 4.0e-5)
1,30 (1,23, 1.37)
le-5
(not applicable)
1.40 (1.34, 1.47)
(not applicable)
0.74 (0.70, 0.79)
41

---

Table 9: Average Jensen-Shannon divergence (JSD) and bytes/sec for various thresholds using
Px o fa ptb against a reference distribution (7 le-4; 3e-4 for Pphia). 95% confidence intervals are given in parentheses.
Pant2 fa ptb bytes sec
Piaaa18 o fa pdb
average JSD/ byte
average JSD/ byte
bytes sec
Ic-1
3.9e-3 (3.3e-3, 4.7e-3)
26.65 (25.79, 27.48)
3.0c-3 (2.6c-3, 3.5e-3)
30.44 (28.31, 32.19)
3c-2
1.4c-3 (1.2c-3, 1.5e-3)
17.03 (16.42, 17.66)
1.1c-3 (9.3c-4, 1.3e-3)
17.45 (16.67, 18.27)
lc-2
5.7c-4 (5.0c-4, 6.7c-4)
10.79 (10.23, 11.36)
3.7c-4 (3.4c-4, 4.0c-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)
le-3
5.5e-5 (5.1e-5, 6.
2.01 (1.88, 2.15)
6.le-5 (5.8e-5, 6.5e-5)
4.13 (3.91, 4.36)
3e-4
2.0e-5 (1.7e-5, 2.4e-5)
0.81 (0.77, 0.85)
3.3e-5 (3.le-5, 3.5e-5)
1.67 (1.59, 1.76)
lc-4
(not applicable)
0.20 (0.16, 0.25)
(not applicable)
0.70 (0.66, 0.74)
PilamaBR average JSD/ byte
pth bytes sec
Pphis f. fpt
average JSD byte
bytes / sec
lc-1
325e,3 3.0ce3)
19.25 (18.79, 19.76)
4.6c-3 (3.2e-3, 6.5c-3)
10.07 (9.53, 10.67)
3c-2
1.0c-3 (8.6e-44 1.2c-3)
13.38 (12.99, 13.83)
3.8e-3 (2.6e-3, 5.1e-3)
5.87 (5.37, 6.40)
le-2
(4.7c-44 7.8c-4)
9.49 (9.16, 9.88)
3.2c-3 (2.2c-3, 4.4c-3)
2.94 (2.59, 3,35)
3e-3
1.2e-4)
(5.62, 6.20)
4.2e-4 (3.0e-4, 5.8e-4)
2.95 (2.68, 3.26)
le-3
5.1e-5 (4.7e-5, 5.5e-5)
3.29 (3.13, 3.45)
3.6e-4 (2.5e-4, 4.8e-4)
1.54 (1.37, 1.74)
2.3e-5 (2.1es5, 2.5e-5)
1.42 (1.35, 1.49)
(not applicable)
0.48 (0.43, 0.54)
le-4
(not applicable)
0.56 (0.53, 0.59)
(not applicable)
(not applicable)
42

---

Table 10: Average Jensen-Shannon divergence (JSD) and bytes/sec for various thresholds and reference (r = =1e-6) using Pdna o f dma2aa- 95% confidence intervals are given in parentheses. We limit the candidate-sed set size (Axxx) to mitigate the combinatorial blow-up with increasing sequence length.
Páno O fdnaZsa (Trexx = 5000)
Páno fdna2sa (Mrax = 10000) average JSD/ / byte
average JSD / byte
bytes / sec
bytes / sec
le-1 2.8e-2 (2,4e 2.
9.55 (8.44, 10.90)
2.8e-2 (2.5e-2. 3.
9.54 (8.45. 10,82)
3e-2
3.2e-3 (2.8c-3, 3.6c-3)
2.90 (2.57, 3.26)
3.3e-3 (2.9c-3, 3.7e-3)
2.03 (1.74, 2.39)
lc-2
6.6e-4 (4.4cc4,,,4
2.20 (1.99, 2.47)
7.4c-4 (5.0c-4, 1.0e-3)
1.42 (1.25, 1.63)
3c-3
1.6c-4 (7.8c-5,
1.89 (1.72, 2.11)
2.7c-4 (1,1c-4,449e--)
1.16 (1.03, 1.31)
lc-3 7.1c-5 (1.7c-5, 1.6c-4)
1.79 (1.62, 1.97)
6.6c-5 1,5c-4)
1.08 (0.97, 1.22)
3e-4 4.9e-5 1.1.e-6,.11ee4
1.73 (1.58. 1.93)
3.5e-5 7,9-5)
1.04 (0.93, 1.17)
le-4 5.8e-5 (1.1e-5, 1.2e-4)
1.72 (1.56, 1.91)
2.1e-5 (9.9e-7,7.9e-))
1.02 (0.92, 1.16)
3e-5
3.0e-5 (7.9e-7,7.9t)
1.71 (1.55, 1.89)
2.1e-5 (6.66-7, 6.2e-5)
1.02 (0.92, 1.14)
le-5
2.2c-5 (1.0c-6, 5.4e-5)
1.71 (1.56, 1.89)
3.9c-6 (5. 6)
1.02 (0.91, 1.15)
3e-6
1.0e5 (2.3e-7, 2,9e-5)
1.70 (1.55, 1.89)
1.2e-5 (6.1e-7, 3,2e-5)
1.01 (0,91, 1.12)
le-6
(not applicable)
1.71 (1.55, 1.90)
(not applicable)
1.02 (0.92, 1.14)
idna o fdunzza (Yrax = 15000) average JSD / byte
idnaa fdnazan (Tlexx = 20000) average JSD / byte
bytes / sec
bytes / sec
le-1 2.9c-2 (2.552 3.3e-2)
9.52 (8.46, 10.82)
2.9e-2 (2.5ee2, 3.3
9.35 (8.21, 10.65)
3e-2
3.2e-3 3.5e3)
1.63 (1.37, 1.94)
3.2e-3 (2.8e33, 3.7e-3)
1.41 (1.18, 1.71)
le-2
6.8e-4 (4.5e-4,
1.10 (0.96, 1.27)
8.3e-4 (5.0e-4, 1.3e-3)
0.91 (0.78, 1.07)
3e-3 2.2c-4 (8.205,,4.ee-4)
0.88 (0.77, 1.00)
2.0e-4 5,,66-,,,,9
0.71 (0.62, 0.83)
le-3
5.0e-5 (8.5e-6, 1.3e-4)
0.80 0.91)
6.6e-5 (1.7e55, 1.5e-4)
0.64 (0.56, 0,73)
3e-4 2.8e-5 (3.6e-6. 7.2e-5)
0.77 (0,68, 0.88)
3.0e-5 (3.9e-6, 7.9e-5)
0.61 (0.55, 0.71)
le-4 2.4e-5 (1.1e-6, 7.0e-5)
0.75 (0.66, 0.84)
6.0e-5 (1.8e-6, 1.6e-4)
0.60 (0.54, 0.69)
3c-5 6.0e-5 (1.0e-6, 1.6e-4)
0.74 (0.66, 0.84)
1.8c-4 (5.0e-5, 3.7c-4)
0.60 (0.53, 0.68)
le-5 3.0e-7 (7.1c-9, 8,3e-7)
0.74 (0.66, 0.84)
7 (5.3e-8, 2.1c-6)
0.59 (0.53, 0.68)
3e-6
9.3e-7 (1.1e-8, 2.7e-6)
0.73 (0.65, 0.83)
7.3e-7 (8.9e-9, 2.1e-))
0.59 (0.53, 0.67)
le-6
(nol applicable)
0.74 (0.65. 0.84)
(not applicable)
0.60 (0.53, 0.69)
Pdna o ddna2aa (Trax = 25000)
Pona fdnalsa (Trex = 30000)
average JSD / byte
bytes / sec
average JSD / hyte
bytes / sec
le-1 2.9e-2 (2.5e-2.. 3,
9.50 (8.31, 10.78)
2.8e-2 (2.5e,2, 3.
9.52 (8.43, 10.99)
3e-2 3.3e-3 (2.9c33, 3.7c-3)
1.28 (1.06, 1.60)
3.3e-3 (2.9c-3, 3.8c-3)
1.18 (0.96, 1.45)
lc-2 7.9c-4 (4.9c44,4., 1.3c-3)
0.81 (0.70, 0.95)
8.2c-4 (4.9c-4, 1.2c-3)
0.72 (0.61, 0.86)
3c-3 2.3e-4 (8.1c)5,4.7c-4
0.62 (0.54, 0.72)
2.5c-4 (7.9c.5,, 4.8c-))
0.55 (0.47, 0.64)
lc-3 5.9c-5 (1.1c-5, 144c4))
0.56 (0.49, 0.65)
(1.1ec,, 1.4c-4)
0.49 (0.42, 0,57)
3e-4 2.6e-5 (3.5e-6, 6,8e-5)
0.53 (0.46, 0.61)
3.4e-5 (4.9e-6, 8.5e-5)
0.46 (0.41, 0.53)
le-4 2.4e-5 (8,2e-7,6.9e-5
0.52 (0.46, 0.59)
2.4e-5 (1.0e-6, 8.0e-S)
0.45 (0.39, 0.51)
3e-5
7.2e-5 (1.9e-5, 1.5e-4)
0.51 (0.45, 0.59)
2.4e-5 7.1ee)
0.45 (0.39, 0.52)
le-5
1.9e-6
(5.6e-8, 6.
0.51 (0.45, 0.59)
1.7e-7 (5.7e-9, 3.8e-)
0.44 (0.39, 0.51)
3
1.3e-6 (1.2e-8, 6)
0,51 (0.45, 0,58)
1.6e-6 (1.7e-8, 3.7e-6)
0.44 (0.38, 0,51)
le-6
(not applicable)
0.51 (0.45, 0.59)
(not applicable)
0.44 (0.39, 0.51)
G.3 DECOMPOSITION SIZE
Tab. 11 and Fig. 18 show how the quotient and remainder sizes grow as 7 decreases, explaining the throughput reduction observed in the JSD experiments.
For the all-IP-universs token-to-bee to-t and DNA transducers, the remainder is empty (R = 0) at every position, so only the quotient size is reported. In the token-to-bytt setting, the mean quotient size grows from 62 at lc-1 to over 35,000 at - = 1c-5, directly accounting for the throughput reduction at tight thresholds. The DNA transducer saturates early due to Tmax = 5000: mean |Q] reaches 465 by 3e-5 and remains flat beyond that.
For pth,, which has -nnivesullera states, both |Q] and |R| are reported. |Q] grows steadily with a tighter T, while [R] initially decreases as more candidates enter the quotient but then grows as the expansion loop over non-IP-universal states discovers additional remainder elements. The presence of non-trivial remainder is the key structural difference from the -Puuveerrs transducers: each
43

---

remainder element requires full string probability (x: rather than just prefix probability, making it more expensive per element.
Table 11: Mean and maximum quotient size [0] across sequence positions for three transducers at varying pruning thresholds т. Results are computed on paragraph WikiText (833 bytes for Papt2 f 850 bytes for Papt2 fo ptb) and on the longest protein in the test set (P83 127. 12 amino acids for Pdna ddnazaa). The fa and f ddaaaa transducers have all-universal states (|R) = everywhere). The ptb transducer has con-universal states, we additionally report the remainder size |R].
Post2 fo
Pána ddna2aa
7
Mcan [o]
Max [Q]
7
Mean [Q]
Max [Q]
le-1
2,238
le-1
104
344
3e-2
200
5,736
3e-2
288
1,274
le-2
439
11,998
le-2
346
1,329
3e-3
873
18,761
3e:3
439
2,011
1e-3
1,536
25,341
454
2,027
3e-4
3,161
65,536
3e-4
462
2,044
le-4
7,800
131,072
lc-4
463
2,044
3e-5
17,232
524,288
3e-5
465
2,046
lo-5
35,768
2,097,152
le-5
465
2,046
465
2,046
(c) Pspe2 fa fpsh
Mean [0]
Max [Q]
Mean [R|
Max [R]
le-1
1.3
31
1.0
113
3e-2
1.9
57
0.38
113
le-2
3.6
142
0.48
25
36-3
7.3
353
le-3
16
686
3.5
129
3e-4
47
1,807
11.4
408
le-4
128
5,101
33,9
1,195
t=
t=1c-2
t=lc-3 v-3e-4
T=
t=lc-5
v=3e-2
t=3e-3
t=3e-5
v=3e-6
Poo2 o Fa
Pepx2 F Fpb
Pána ddnalan
10a
10a
103
10a
10
10
10
100.
100.
100
200
400
600
800
200
400
600
860
2'5
5
7.5
10
Position in sequenee
Figure 18: Growth of the quotient size [Q] (solid lines) and remainder size |R| (dashed lines) with sequence position for three transducer compositions at varying pruning thresholds т. Left: Pap12 fa on paragraph of WikiText (833 bytes). Center: Pgpt2 o fa ptb on paragraph (850 bytes after transduction); dashed lines show [R], which is non-zero because fpth contains non-IP-universal states. Right: Pana ddnaaa the longest protein in the test set (P83127, 12 amino acids). For fo and fdna2aa. all FST states are IP-universal, so |R| = everywhere. The fdna2aa panel uses candidate-see cap of Alax 5,000, which limits the quotient size at lower thresholds and breaks monotonic growth at later positions.
44

---

G.4 CROSS-ENTROPE
Cross-entropy measures how well the transduced model assigns probability to held-out text; unlike JSD, only requires evaluating py y) for the observed next symbol rather than computing the full next-symbol distribution p>( y). Tab. 12 reports cross-entropy (in nats and bits per byte) together with throughput for (px a.). Because only a single probability is needed per position, throughput is higher than in the JSD tables above. Cross-entio Cross-entropy converges quickly decreases: for all four models, the tightest thresholds yield nearly identical values, confirming that moderate pruning suffices for accurate sequence scoring.
Table 12: Cross-entropy and throughput for various thresholds T using px o fa. 95% confidence intervals given in parentheses. Pgpt2 a at le-5 is computed over 6 paragraphs; all other configurations use 10.
7
bytes sec
Bits byte
Cross-entropy
Mean
95% CT
Mean
95% CI
Mean
95% CI
Pop12
1e-1
82.61
(73.33, 92.34)
1.2434
(1.1884,
1.2936)
0.8619
(0.8237, 0.8966)
3--2
49.10
(44.48, 54.24)
1.1466
(1.0978, 1.1949)
0.7948
(0.7609, 0.8282)
le-2
28.46
(26.73, 30.33)
1.0652
(1.0199, 1.1068)
0.7383
(0.7070, 0.7672)
3c-3
14.20
(13.47, 14.98)
1.0385
(0.9956, 1.0806)
0.7199
(0.6901, 0.7490)
le-3
6,46
(6.08, 6.84)
1.0293
(0.9909, 1.0664)
0.7134
(0.6868, 0.7392)
3e-4
2.18
(2.04, 2.33)
1.0220
(0.9831, 1.0604
0.7084
(0.6815, 0.7350)
le-4
0.75
(0.70, 0.80)
1.0220
(0.9823, 1.0610
0.7084
(0.6809, 0.7355)
3e-5
0.35
(0.33, 0.39)
1,0200
(0,9781,
0,7070
(0.6779, 0,7370)
le-5
0.34
(0.30, 0.38)
1.0025
(0.9461, 1.0550)
0.6949
(0.6558, 0.7313)
Pllama18 o fa
le-1
129.22
(112.82, 146.19)
0,9922
(0.9467, 1.0405)
0.6877
(0.6562, 0.7212)
3e-2
90.74
(82.63, 99.33)
0.9128
(0.8682, 0,9542)
0.6327
(0.6018, 0.6614)
le-2
47.81
(4..04,51.52)
0.8626
(0.8252, 0.9027)
0.5979
(0.5720, 0.6257)
3e-3
26.15
(7..7),
0.8402
(0.8037, 0.8790)
0.5823
(0.5571, 0.6093)
1e-3
14.89
(14.18, 15.69)
0.8364
(0.8001, 0.8725)
0.5797
(0.5546, 0.6048)
3e-4
6.80
(6.46, 7.18)
0.8358
(0.7999, 0.8724)
0.5793
(0.5545, 0.6047)
le-4
2.62
(2.49, 2.77)
0,8362
(0.8018, 0.8699)
0.5796
(0.5558, 0.6030)
3e-5
1.42
(1.35, 1.49)
0.8361
(0.8002, 0.8717)
0.5796
(0.5547, 0.6042)
le-5
0.73
(0.69, 0.77)
0.8360
(0.8002, 0.8717)
0.5795
(0.5546, 0.6042)
PilamauB fo
le-1
88.65
(79.18, 99.61)
0.8176
(0.7757, 0.8661)
0.5667
(0.5377, 0.6003)
3e-2
76.39
(71.27, 81.35)
0.7392
(0.7007, 0.7759)
0.5124
(0.4857, 0.5378)
le-2
52.05
54.933
0.7153
(0.6778, 0.7507)
0.4958
(0.4698, 0.5203)
3e-3
28.81
(27.18, 30.44)
0.6959
(0.6627, 0.7282)
0.4824
(0.4594, 0.5047)
le:3
16.86
(16.01, 17.82)
0.6913
(0,6584, 0.7251)
0.4791
(0.4564, 0.5026)
3e-4
9.73
(9.24, 10.25)
0.6870
(0.6513, 0.7179)
0.4762
(0.4515, 0.4976)
le-4
4.35
(4.15, 4.58)
0.6870
(0.6557, 0.7221)
0.4762
(0.4545, 0.5005)
3e-5
2.60
(2.47, 2.73)
0.6869
(0.6533, 0.7208)
0.4761
(0.4528, 0.4996)
le-5
1.57
(1.49, 1.66)
0.6869
(0.6552, 0.7180)
0.4761
(0.4541, 0.4977)
Pohia fa
le-1
42.39
(37.95, 47.19)
0.8714
(0.8217, 0.9208)
0.6040
(0.5695, 0.6382)
3e-2
34.48
(31.73, 37.33)
0.7748
(0.7317, 0.8180)
0.5371
(0.5072, 0.5670)
le-2
24.89
(23.05, 26.59)
0.7547
(0.7165, 0.7959)
0.5231
(0.4966, 0.5517)
3e-3
16.55
(15.34, 17.92)
0.7301
(0.6959, 0.7690)
0.5061
(0.4824, 0.5330)
le-3
9,91
(9.41, 10.52)
0.7241
(0.6882, 0.7595)
0,5019
(0.4770, 0.5264)
3e-4
5,81
(5.51, 6.14)
0.7170
(0.6803, 0.7509)
0.4970
(0.4716, 0.5205)
le-4
2.55
(2.41, 2.70)
0.7163
(0.6824, 0.7493)
0,4965
(0.4730. 0.5194)
3e-5
1.54
(1.46, 1.62)
0.7162
(0.6793, 0.7490)
0.4965
(0.4709, 0.5192)
le-5
0.86
(0.81, 0.91)
0.7162
(0.6828, 0.7502)
0.4964
(0.4733, 0.5200)
45

---

G.5 BENCHMARKING THE COMPUTATIONAL SHORTCUT
We benchmark the computational shorteut inherent in the prefix decomposition described in $4, which allows us to decompose the precover into remainder and quotient representatives. We generate suboptimal decompositions by randomly selecting IP-universal states in the transducer (see $4) and treating them as non-IP-unnd non-IP-universal size of the quotient and increases the remainder correspondingly. Tab. 13 shows the average JSD between the original and modified distributions over the first 256 bytes of the first 5 paragraphs of the wiki text----ra--v dataset (Merity al., 2017). For each value of n, repeat the sampling of new non-universal states three times, and report the mean JSD.
our algorithms (see $5). This gradually decreases the
The distributions diverge rapidly, and after converting roughly 15-20% of IP-universal states, the algorithm repeatedly encounters dead ends. This number varies between runs; as shown in Fig. 19, each repeat exhibits distinct step function: JSD remains low until particular high-connectivity state is converted, then jumps by 2-3 orders of magnitude and plateaus. In the PTB transducer, one IP- universal state (state 193) serves as routing hub with 274 ares spanning 245 output symbols. When this state is converted, frontiers containing it move from the quotient Q to the remainder R, causing the expansion loop to require fallhack scoring (Fig. 10). Different runs encounter this hub different depending on the permutation order, producing the staircase pattern. This shows that IP-universal states have a hierarchical importance structure: distribution quality is governed by a small number of high-connectivity hub states, while the majority can be converted with negligible impact (JSD le-4).
Table 13: Average Jensen-Shannon divergence (JSD) the PTB transducer (r =le-3) after randomly converting of the IP-universal states to non-IP-universal 95% confidence intervals are given parentheses. JSD is computed against the unmodified transducer (n 0).
Converted States (n)
PiaamaB fa o fpt
PitamaeB fa fptb
Pohis f f
(not applicable)
(not applicable)
(not applicable)
3.9e-5 (3.5e-5, 4.3e-
13.4ee7, 2.1e-4)
6.6e-5 (3.le-5, 1.le-4)
5
9.5e-4 (7.5e-4, 1.2e-3)
9.0e-4 (7.5e-4, 1.le-3)
7.8e-4 (6.4ee4, 9.4e-4)
8
9,8c-4 (8.0e44,,2 1.2e=3)
8.1e-4 (6.6c-4, 9.6e-4)
11
3.0e-2 (.36e22
(25e_
2.6e-2 2.9e-2)
2.9e-2 (2.6e22...
22.e22(2.5e2..3.1ee
2.6e-2 (2.3e-2, 2.9e-2)
2.9c-2 (2.6e-2, 3.2e-2)
2.8e-2 2,
2.6e-2 (2.3e-2, 2.9e-2)
19
2.9c-2 (2.6e-2, 3.3e-2)
2.8c-2 (2.5e-2, 3.2e-2)
2.6e-2 (2.3e-2, 2.9e-2)
Repeat
Repeat 2
Repeat 3
Pooled avg.
Plama1B o fa fub
Plamag fa fcbh
Pphis fa fp
10
JSD (bits)
10-2 2
10-3
10
12
16
8
12
16
Converted States
Figure 19: Per-repeat Jensen-Shannon divergence (ISD) vs. number of states converted from IP- universal to non-IP-universal for the PTB transducer (7 =le-3). Each repeat uses different random conversion order. The abrupt jumps are caused by individual high-connectivity states, whose conversion causes a jump in JSD.
46

---

H STATE-BASED DECOMPOSITION
The algorithms presented in the main text enumerate strings: the quotient Q(y) and remainder R(y) are represented as explicit sets of strings. When these sets are infinite, the string-enume ceniinenumeration approach does not terminate without pruning.
An alternative is to operate on the state space of the precover DFA rather than its string space. Since the precover DFA Py ($5.1) has finitely many states, state-based traversal always terminates, even when 2yy) or Ry) are infinite. The key idea is to represent the quotient and remainder as DFAs Q and R-auoomaaa that accept the (possibly infinite) sets (3)) and ( respectively-rathe than enumerating their elements. The full precover is then recovered as P(y) = (IoI)) u [R].
The algorithm in Fig. 20 performs a BFS over the states of py. At each state s, it checks whether is umiversal- i..., whether the sub-automaton rooted at accepts X (see is_ is_cylinder marked quotient member and accepting state, and its successors are not explored, since all extensions from a universal state are covered. If is accepting but not universal, it is marked as remainder member and accepting state, and exploration continues through its outgoing arcs.
If so,
The result is a pair of DFAs that share the same state space and truncated are set but differ in their accepting states. The quotient automaton Q has the universal states as accepting states, and ares leaving universal states are dropped (since the BFS does not expand past them); thus [[]] @(v), accepting exactly the quotient elements. The remainder automaton uses the same truncated are set but marks only the non-universal accepting states; thus, [R]] R(y).
247
def dfa lla_decoomosiiiion(f" y):
268
def is cylinder(ss)::
Py f trim
y)*)))
V < {s}; q q QUEUB((s))
249
q f QUEUE(Ly)
270
while q:
V 0; arcs 0
231
8 p.p(()
251 Q < 0; R R+0 0
212
if s $ Fy: return False for x x X:
while q:
273
253
+ p)
274
254
if = V: continue
275
s' t step, if s' = th: return False
255
V. add
256
if s E Fy: if is_cylinder(s):
277
if s' V::
278
V. add(s)); q. pssh(s')
258
Q. (s)
279
return True
continue
# do not expand
260
else:
R. add(s)
262
for x E X::
s' +- st,
if s 0: continue
265
q. (s))
arcs. (s 4 s
266
return DFA(V, ar DFA Rrcc,))
Figure 20: State-based decomposition of the precover into DFAs. Left: BFS over the precover DFA y. Universal states become accepting in Q; non-universal accepting states become accepting in R. Ares leaving universal states are not collected. Right: is_cylinder the same universality BFS as in Fig. 3, but takes a DFA state directly rather than computing it from source string via runy.
Comparison with saring- algorithms. The state-based algorithm always terminates in finite time even when Q(v) or R(y) are infinite-becausee Py has finitely many states. The resulting DFAs and provide compact, finite representations of these potentially infinite sets.
However, implementing the autoregressive interface ($C.1) still requires enumerating the strings accepted by these machines: computing p (y) via Eq. (8a) sums px (æ) over elements of Q and R(y), and when these sets are infinite, the sum must be truncated regardless. Thus, while the DFA representation guarantees a finite decomposition, it does not, on its own, yicld finite-time scoring.
47

---

I RELATED WORK
Modern language models define probability distributions over sequences of tokens (see $2). For efficiency and vocabulary (a.k.a. their alphabet) management, they usually rely on subword schemes such as BPE (Sennrich et al., 2016; Gage, 1994) Unigram (Kudo, 2018). Although these approaches have been remarkably successful, their units often don't tt coincide with linguistic boundaries, and any given string typically admits an exponential number of tokenization variants with non-zero probability mass under the language model. Recent work has tackled this issue by enforcing canonical tokenization to remove probability mass from noncanonical encodings (Vieira al., 2025b), while Geh et al. (2024) have shown that aggregating the probability mass of noncanonical tokenization choices carries a useful signal that can boost downstream accuracy.
Subword segmentation also gives rise to the prompt- hrapt--bundrry problem (Vieira et al., 2025a), where imperceptible changes to the final characters of a prompt (e.g., appending a single whitespace) can push the encoded token sequence onto completely different path in token space, causing the model to abandon otherwise highly probable continuations. To overcome these issues, Vieira et al. (2025a) introduce algorithm for transforming token-basee based language models into language models over characters. Although their contribution centers around characters, the underlying idea can be generalized (as shown in this work).
Many applications need a method to accurately convert the probability mass learned on subword tokens to other types of units, such as bytes, words, or morphemes in NLP, or amino acids in computational biology, as pointed out in $1. An additional example is found in psycholinguisties, where researchers often require fine-grained estimates of surprisal, e.g.. predict reader's 's likelihood of skipping word based on how predictable its first three characters are (Rayner et al., 1982; Blanchard et al., 1989). To this end, recent studies have tackled the challenges posed by subword tokenization (Nair & Resnik, 2023; Beinborn & Pinter, 2023; Pimentel & Meister, 2024; Oh & Schuler, 2024; Giulianelli et al., 2024). For example, Oh Schuler (2024) and Pimentel Meister (2024) argue that leading whitespace tokenization introduces confounder in surprisal estimates and instead advocate for incorporating the probability of trailing whitespaces into such calculations.
Furthermore, Pimentel & Meister (2024) give bespoke procedure for converting boken-based language models to word-based language models. However, their method does not model the contextually sensitive nature of English word segmentation, c.g., it treats both periods in Ex. (I) identically, where English orthography does not. Additionally, the justification of the procedure requires that there exists a set of distinguished end-of-word markers that appear the end of token, at all. We now consider how such a transducer can be constructed. Let fa be a transducer that converts token alphabet to a character alphabet, and D be the set of delimiters. The transducer f is given in Fig. 21. Given a language model px over X, we can then compose them into a transducer px o fa fD to get a transduced language model over separator-delimited words. However, such an approach would be rather naive. Unfortunately, delimiter- baseeer--bdddddee separation would not be able to distinguish when the dot should be its own symbol or not, as in ex. (3).
d:d, vd E D
FE VI E X X
3i Vo
d:d, Vd E
Figure 21: A simple FST that segments character streams into words without contextual information, inserting. the start of each word.
The delimiter-based approach also fails for most BPE-based language models because of the clustering
of delimiter candidates. For instance, GPT-4o's alphabet contains the token 1esse, which consists
48

---

!!!
solely of end-of-wee -orrd symbols. Under PTB guidelines, for example, resse should broken into three contrast, we argue that the proper tokenization scheme for psycholinguistic modeling should be specified based on the goals of the study and not based on the properties of any one specific tokenizer.
consecutive orthographic words !
Tokenization challenges are not unique to modeling natural language. In computational biology, DNA, RNA, and protein sequences are long, unsegmented strings over small alphabets that pose challenges in tokenization. Researchers thus alternate between different tokenization schemas, such as k-mers, learned subwords, and motif-aware segmenters (Ji et al., 2021; Nguyen et al., 2023; Dotan al., 2024; Wang al., 2024; Qiao et al., 2024). Because language models are often trained under different tokenization schemas, their autoregressive predictions stsectioonssss-byyyeesee step-by-step probabilities and conditional distributions-and not directly comparable across tokenization schemes.
bansdu approaches to tokenization are well-established Worddeece (Wu et al., 2016) can be implemented transducer (Song et al., 2021), and deterministic finite automata have been constructed for BPE (Berglund & van der Merwe, 2023; Berglund et al., 2024). Moreover, transducers also have long history in language modeling (Mohri, 1997) and have been adopted for constrained decoding, where an FST enforces lexical or structural constraints (Allauzen et al., 2014; Ghazvininejad al., 2016; Stahlberg et al., 2019; Willard & Louf, 2023; Koo al., 2024: Cognetta et al., 2025).
Closely related are neural finite-state transducers (Lin et al., 2019) and earlier neural FST hybrids (Rastogi al., 2016), which assign (neural) weights transitions and compute prefix/sequence probabilities as path-sums over all paths consistent with a given output. Our construction admits similar view: we marginalize over all source strings (paths) that map to given output. However, rather than learning transition weights, we focus on transducing an off-the-shelf pretrained LM, enabling efficient inference via quotient-remainder decomposition.
In this study, we generalize character-level conversion and extend Vieira et al. (2025a) into framework that enables transforming a language model into another language model, beyond the limited setting of strict-prefix monotonic mappings. We support conversions between sets of units and unee-pregg transformations, provided that the mapping between them can described by finite-state transducer.
49

---

J LIMITATIONS
Empirical scope. Although our framework theoretically enables transduction of any language model to any unit of interest, given a valid transducer, we test only a limited set of architectures (GPT-2, LLaMA and Phi-4) and target specifie units (bytes, Penn Treebank tokens, and amino acids). Future research could broaden the analysis to a wider range of models, datasets, and units.
Expressiveness. Our analysis has focused functional finite-state transducers and regular languages. Future work could consider dynamically built transducers and distributions over more expressive languages, well as stochastic maps encoded by non-functional transducers-wher the notion of universality would need to be adjusted.
Approximation quality. Our pruning-based inference algorithm performs well when the source language model concentrates most of its probability mass on small number of prefixes that map to the current target prefix under the transducer-i.e. when the effective size of the quotient and remainder after pruning is small. When the mass is dispersed across many source prefixes (such as in the DNA amino-acid case), pruning must discard larger fraction of the total probability, and the approximation degrades. An importance-sampling approach ($ C.3) could provide less systematically biased alternative.
Speed. The speed of our algorithms and implementations may not suit every use case. Obtaining the full distribution (for example, for decoding or model comparisons) currently requires speeds around 10-20 bytes/sec. While this is not prohibitive for many tasks, it leaves ample room for improvement.
Marginalization. A core property of transduced language models is the marginalization: the transduction sums source-string probabilities to compute target-string probabilities, aggregating mass across all source strings that map to the same target. Since natural language allows the same meaning representative
to be expressed in multiple ways, transduction could normalize these to obtain output distribution over the space of interest. Consider, for instance, math problem: "If 12 students younger than Tom and 12 students are older, how many there in total?" The answer could be '25', or 'twenty-five' or perhaps '12+1+12'. If any of these have significant probability mass, we would like sum them. chain-of-thouu of-thougtt reasoning, we can similarly imagine summing and normalizing probabilities across samples from the system, an approach known as celf-ionnis (Wang et al., 2023). We hope to see transduced language models applied such settings future work.
50


Reviews:
[{"review_id": "doRtg8PIYG", "reviewer": "Reviewer_bhMG", "summary": "The paper is about transduction -- taking a language model that was trained over a certain granularity of vocabulary and converting it to a model operating over a different granularity of vocabulary through a deterministic mapping. It extends prior work on converting subword models to character-level models by providing both exact and reasonable approximate algorithms for converting to arbitrary new vocabularies, then demonstrates this approach on three example transformations.", "questions": "Q1. This defines a fairly broad class of transductions that can be performed exactly; do you have any examples of reasonable-to-want transformations that *don't* fall into this class?\n\nQ2. One thing that I don't see mentioned here is that this makes it much easier to compare distributions across language models-- you could transduce model 1 into model 2's vocabulary space. Do you think this would ever be practical to do e.g. for speculative or contrastive decoding? \n\nComments/other notes:\n- purely a stylistic gripe, but I think the formatting for library names (e.g. GenLM.bytes) is super distracting to read in-line. \n- The color of symbols is also slightly annoying to me, but I see the argument for that as a way to track notation; I would just confirm they are colorblind-friendly where possibly\n- typo in line 144: \"efficienct\"\n- line 41: \"Such as normalizing output, ...\" is a sentence fragment\n- line 850: \"proportion\" -> \"portion\"\n- the introduction was much less dense relative to the rest of the paper-- I think the example could have been greatly condensed to spend a bit more main-body text time on the transduction \n- the trained model for transducing seems a bit out of place in the rest of the work; it doesn't weaken the paper, but it feels a bit like a last-minute (unnecessary) addition to satisfy a reviewer", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "S1. I think this is a really interesting problem, and it's both well-explained and well-explored in this work. I can immediately see how this would be useful.\n\nS2. I really like the framing of this with FSTs; it's an intuitive way to think about the class of transformations and a really nice formalism. The walkthrough of the math is detailed and cleanly developed.", "weaknesses": "W1. While overall I think the explanation is good, there are several parts of the paper that I think require context from \"From Language Models over Tokens to Language Models over Characters\" to fully understand. The two most obvious ones to me: (1) the discussion in lines 67-69 of applications to computational psycholinguistics and controlled generation; (2) the relation between transducing and token healing. \n\nW2. The work is largely a generalization of a prior (also cool!) result. I think this is still a valid contribution, but I could see the argument that this is a bit incremental. \n\nW3. While the speed of decoding is not a major focus of the work, it would be nice to see a bit more detail on the efficiency. In particular, bytes/sec is a bit hard to interpret, and a few baselines of the language model decoding in its original vocabulary would be helpful to put these numbers in context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1vwF6F80Sz", "reviewer": "Reviewer_CpW4", "summary": "The authors put forward an algorithm to sample and compute language model probabilities over transduced strings from the model's own distribution.\nThey also propose an approximate algorithm that estimates the transduced probabilities at a cheaper computational cost.", "questions": "Does this method potentially allow conversion between different language model tokenizers? This could be useful for cross-family language model distillation.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The idea is creative, well motivated, theoretically interesting, and practically useful.\nThis is a classic application of algorithms, probability, and formal language theory.\nThe examples in the appendix are informative and give a good intuition for how the method works.", "weaknesses": "I am quite satisfied with the presentation and ideas in this paper and do not see any significant reasons why it should not be accepted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WMkcv8hMCA", "reviewer": "Reviewer_9rp9", "summary": "The paper studies how to compute or approximate target-prefix probabilities when a language model over one unit type (e.g., tokens, bytes, DNA) is passed through a deterministic mapping (finite-state transducer) into another unit type (e.g., characters, words, amino acids). Because the mapping can merge, split, or be context-dependent, a target prefix corresponds to a complex set of source prefixes.\n\nVieira et al. (2025a) handle the special case of strict-prefix-monotone mappings (e.g., tokens→characters), where target-prefix probabilities reduce to sums over source-prefix probabilities. This paper generalizes to arbitrary deterministic FSTs via a precover decomposition: split the relevant source prefixes into a quotient (prefixes whose outputs already force the target prefix) and a remainder (prefixes that must be summed explicitly).\n\nFor practicality, the authors add lazy determinization, memoization/precomputation universal states, and probability-mass pruning with a threshold $\\tau$ (optionally with candidate-set caps and backtracking).", "questions": "Could you toggle, one at a time, (a) lazy determinization, (b) memoization/precompute, (c) composition strategy, (d) adaptive $\\tau$  candidate-set caps, and report the effect on JSD/accuracy, throughput, and peak memory ?\n\nOn the shared tokens→characters setup, can you report a matched comparison (same model, dataset, hardware) with throughput, wall-clock, and peak memory with Vieira2025a ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Clear, principled generalization of the strict-monotone case with an identity that is easy to implement (quotient + remainder). Practical algorithms with sensible speedups and demonstrated accuracy–speed trade-offs on non-trivial mappings. Overall the definitions, explanations, and conditions are crisp and easy to follow.", "weaknesses": "Key algorithms and experimental details are mostly in the appendix, and the approximations in 5.2 are described very briefly. Readers may miss core contributions if they don’t consult the appendix. Just a suggestion, feel free to ignore if it doesn't make sense: bring a minimal algorithm box/flowchart and a small table that lists each approximation knob (lazy determinization, memoization, pruning, caps) with default settings into the main text. \n\nThe paper varies $\\tau$ but does not isolate the contribution of each approximation, nor does it provide a direct runtime/memory comparison against Vieira in the shared setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vCUBOSgyqo", "reviewer": "Reviewer_Sa4U", "summary": "This work presents a general framework for transforming a language model over source strings into an LM over target strings, focusing on FST transformations. A major technical contribution is prefix decomposition of the preimage of a target prefix into a quotient and a remainder (Eq 6), which allows discussion of finite / infinite cases of quotient / remainder sets.\n\nThis paper also discusses exact and approximate algorithms for building the two sets.\n\nAs for experiments, this paper discusses 3 LM transduction applications: 1) token to character 2) token to word 3) DNA to Amino Acid.", "questions": "- Can you provide error bounds for the approximate algorithms?\n- Measure-theoretic foundations are implicit: could you spell out the underlying probability space / measurability assumptions of $p_Y$?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Clean formalization: the remainder-quotient decomposition allows quite general discussion of exact / approximate algorithms.\n- Makes algorithmic contributions.\n- Interesting applications that show effectiveness of transduced LMs.", "weaknesses": "- The formalism / accompanying algorithms / experiments seem to be designed specifically with FSTs in mind, which restricts its applicability. For example, Fig 3 (left) does not discuss the decidability of membership test in L10 and L13, which can actually be nontrivial in real LM usages (for example suppose you are trying to transform a code LM to a code-output LM). Decidability and complexity aspects should be discussed in a more rigorous fashion for the general case.\n- Limiting ourselves to the FST-as-transformation special case, the paper would benefit from a more extensive comparison to existing NLP approaches that compose LM outputs with classical formalisms, such as [neural finite-state transducers](https://aclanthology.org/N19-1024/): the proposed method appears to be a special case of the neural finite-state transducers where the prefix probability can be seen as a pathsum of some machine that transduces the precover of y to y.\n- Analysis of the pruning algorithm discussed in G.4 would strengthen the paper: e.g., can you bound the error?\n- The paper would also be strengthened if it could discuss learning scenarios, for example if the source LM is parametric, what are the gradients of next-token probabilities under $p_Y$ ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)