acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Estimation of Transduced Language Models

Abstract

Transduced language models (TLMs) compose a pretrained source language model with a functional finite-state transducer to induce a model over the target strings of the transducer. Computing the probability of a target prefix under a TLM amounts to summing the source-model probabilities of all strings that map to strings beginning with that target prefix. This set can be infinitely large, so prior work uses a computational shortcut and biased pruning to make the breadth-first search feasible. We instead propose an algorithm that samples source prefixes without replacement, reweighting each prefix by the inverse of its inclusion probability. Applying this correction gives an unbiased estimator of the TLM's prefix probability and lets us estimate the mass lost by pruning. The algorithm reduces the number of prefixes as more probability mass is added to the running estimate. This can save computation and guarantees that the run halts with probability one. The algorithm achieves a better compute–variance tradeoff on English text when converting a model over subwords to a model over whole words, and lower error on DNA-to-amino-acid transduction than other sequential Monte Carlo baselines. On the DNA-to-amino-acid transduction, it reduces runtime by orders of magnitude and makes scoring long target strings feasible. Repeating a published reading-time analysis substantially lowers estimated corpus surprisal while confirming its conclusions.

Primary area:
foundation or frontier models, including LLMs
Keywords:
transduced language models, sequential monte carlo, unbiased estimate

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_y8VkOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+2)
Read review
Paper summary

The paper proposes an unbiased stochastic algorithm for estimating prefix probabilities of transduced language models (TLMs), which compose a pretrained source LM with a finite-state transducer. The authors sample source prefixes without replacement and apply Horvitz–Thompson reweighting, and they prove unbiasedness provided the run halts almost surely. They further propose an adaptive-budget variant that shrinks the particle count as mass accumulates and uses Russian roulette to guarantee almost-sure halting. They evaluate the method in 5 experimental settings covering text and DNA-to-amino-acid conversion.

Critical strengths

The paper tackles this question by providing an algorithm with a solid proof, and evaluates the method in 5 experimental settings covering text and DNA-to-amino-acid conversion.

Critical weaknesses

The evaluation mainly measures how accurate the estimates are, but it does not test whether the transduced model itself is useful. For example, in the DNA-to-amino-acid setting, there is no comparison with a model trained directly on amino acid sequences, and no downstream task.

Questions for authors
  • Could you compare against strong existing baselines, for example, a model of similar size that performs well on a related downstream task, to evaluate how useful the transduced model is?
  • Minor formatting issue: on line 468, a space is missing after the period in "direction.To".
1 comment

We thank the reviewer for the review and for catching the typo on line 468, which will be fixed in the revision.

W1 and Q1: usefulness of the transduced model, and comparison with a model trained on amino acids.

We would like to point out that the contribution of this paper is methodological: an estimator for the probabilities of transduced language models, with proofs that it is unbiased and that it halts. Our goal is not to present a scientific application, and we do not claim that a transduced model outperforms a model trained on the target units. The case for transduced models themselves is made in the two works we build on. Snæbjarnarson et al. (2026) introduce them as a way to obtain a model over the units a task needs, such as bytes, words or amino acids, from a pretrained model without retraining, and Kiegeland et al. (2026) apply them in psycholinguistics to predict human reading times, the analysis we repeat in §4.3. What our paper adds is the ability to compute these probabilities without bias, and at lengths where the existing methods fail (in Fig. 6 the capped baseline returns zero after 16 amino acids).

We agree that an example for the DNA-to-amino-acid setting helps to show what this makes possible, so we ran a small proof of concept. We took 198 randomly sampled ClinVar missense variants (single amino-acid changes in human proteins) and classified them as pathogenic or benign with the 7B-parameter Evo2 DNA model transduced to amino acids. It scores a variant by how much less probable the changed sequence (the new amino acid and the five after it) is than the original, given up to 1,000 bases of upstream DNA. With no training, it reaches an AUROC of 0.83, against 0.81 for the same DNA model scored directly on DNA and 0.86 for ESM-1v, an existing model trained directly on amino-acid sequences and a widely used baseline for this task (650M parameters). At this sample size none of these differences is distinguishable from zero. Note that this is an illustration of the kind of study the estimator enables and we would look forward to seeing it studied in dedicated future work with domain experts.

More generally, a transduced DNA model gives probabilities that neither a DNA model nor a protein model provides on its own: (i) the probability of a protein given its surrounding DNA, for example the sequence upstream of the gene, which a protein model cannot condition on; (ii) the probability of a protein summed over all of its synonymous DNA encodings, where a DNA model alone scores only one encoding; and (iii) by Bayes' rule, the probability of a particular DNA encoding given the protein it encodes, the quantity relevant to choosing codons in gene design. Again, we hope these open avenues for future studies; pursuing them is beyond the scope of this paper, which develops and evaluates the estimator itself.

Soundness.

The paper's contribution is a method with guarantees, and each of its claims is supported as follows.

  • The estimator is unbiased, and the adaptive algorithm halts with probability one. These are proved (Theorem 3.1, Proposition 3.2) and confirmed against exact probabilities wherever these can be computed (Fig. 4, Figs. 17–18, App. J), and now also with Evo2-7B (see our reply to Reviewer 867u).
  • It has a better compute–variance tradeoff on text, and lower error on DNA, than the sequential Monte Carlo baselines. We test this in five experimental settings against five estimators (Tabs. 2 and 5, Figs. 4–6, App. K), with up to 256 runs per setting.
  • It makes long, high-entropy targets feasible. Shown on DNA-to-amino-acid transduction up to 200 amino acids with the bigram DNA model, where the estimate is within 0.06 nats of the exact value (Fig. 6), and now at 200 amino acids with a 1B Evo2 network (see our reply to Reviewer 867u).

We appreciate that the review describes the proof as solid and does not question any of these claims. Its concern is that the usefulness of the transduced model was not evaluated, which the prior work and the example above address. We hope this allows you to reconsider the soundness score.

Reviewer_867uOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper focuses on transduced language models, which convert a pretrained language model into one over a different kind of string (e.g., DNA to amino acids). Specifically, it looks at estimating the probability that the converted model's output begins with a given target string. Prior work computes this with a beam search that prunes unlikely source prefixes, but pruning biases the estimate and becomes too slow when probability is spread across many prefixes. To address this, the authors replace the pruning step with sampling without replacement and reweight each kept prefix by its inclusion probability. An adaptive version reduces the number of kept prefixes as probability mass accumulates, so the search is guaranteed to halt. Experiments show lower error than sequential Monte Carlo baselines, while the introduced method's runtime grows roughly linearly with sequence length on DNA-to-amino-acid conversion.

Critical strengths
  • The method is a reasonable fix for a limitation of prior work. It keeps the existing beam-summing algorithm and changes only the pruning step, with proofs that the resulting estimate is unbiased and that the search halts.
  • This works makes estimation possible in high-entropy settings where pruning fails. On DNA-to-amino-acid conversion, the capped baseline returns a probability of exactly zero after 16 amino acids, while the new method's estimate at 200 amino acids is within 0.06 nats of the exact value.
Critical weaknesses
  • All neural experiments use GPT-2 (GPT-2 Large for text and a GPT-2 model trained on DNA), but it's unclear whether the results hold for current models. This matters especially for cost, since the method creates every live child before pruning and modern models have substantially larger vocabularies. Experiments with more recent open model such as Llama3 or Qwen3 would generally be expected in modern NLP/ML research. EDIT: the authors pointed to results that address this concern, so feel free to disregard this weakness.
  • The pruning bias that motivates the paper seems to have little practical effect on text. The reading-time reanalysis done in Section 4.3 lowers corpus surprisal by only 1.4% and leaves every conclusion unchanged, which suggests the method primarily matters in high-entropy settings like DNA.
  • The main text has no related-work section, and Appendix L is a single paragraph that lists alternative SWOR and SMC methods (e.g., Kool et al., 2019; Meister et al., 2021; Lew et al., 2023) without explaining how this method differs from them or comparing against them experimentally.
Questions for authors

Is there a practical obstacle to running the method on a recent open model (e.g., Llama 3 or Qwen3)?

4 comments

Response (1/2). We thank the reviewer for the detailed review. This comment covers W1 and Q1; the next covers W2, W3 and the soundness score.

W1 and Q1: recent models, and the cost of forming every live child.

To answer Q1 directly: no, the method runs on, e.g., Llama 3 as it stands. The algorithm and proofs do not depend on the architecture or vocabulary of the source model, and the beam-summing computation we build on has already been run with Llama-3.2-1B, Llama-3.1-8B and Phi-4 by Snæbjarnarson et al. (2026); note that our method mainly changes its pruning step.

Do the text results hold on a recent model? Yes. We ran our estimator with Llama-3.1-8B alongside GPT-2 Large on the first paragraph of §4.1 (850 target symbols) with the PTB transducer on an RTX 3090:

Source modelParametersVocabularyPruning τ=10−3\tau=10^{-3}, time (s)Pruning τ=10−4\tau=10^{-4}, time (s)Ours M=200M=200, time (s)Ours M=1600M=1600, time (s)Ours −- pruning τ=10−3\tau=10^{-3} (nats)Ours −- pruning τ=10−4\tau=10^{-4} (nats)
GPT-2 Large0.8B50k5626645962.38 [2.31, 2.43]2.26
Llama-3.1-8B8.0B128k856411232494.22 [4.03, 4.38]3.64

Times are per run, averaged over four runs. The last two columns use a pooled estimate for four runs at M=1600M=1600, with a bootstrap 95% interval; a single run at M=200M=200 differs from it by about 0.2 nats. The τ=10−4\tau=10^{-4} Llama run needed smaller batches to fit in memory.

With Llama-3.1-8B, pruning at τ=10−3\tau=10^{-3} puts the paragraph's log probability 4.2 nats below our estimate, a factor of about 68. Tightening the threshold tenfold costs seven times the compute and recovers 0.6 nats of the 4.2, while one run of ours at M=1600M=1600 costs less than half of that tighter threshold. This is the pattern of GPT-2 Large in the paper (Tab. 4).

Do the DNA results hold on a recent model? Yes. Besides the GPT-2 DNA model, we have now also run a 7B-parameter Evo2 genomic model (Brixi et al., 2026) in three settings.

First, we checked the estimate against an exact answer. A 5-amino-acid target is encoded by 288 different DNA sequences, few enough to score every one with the model and add them up. We then ran our estimator on the same target with a budget of only 16 or 32 particles (reweighted prefixes), so that it cannot enumerate and has to sample. Averaged over 300 runs, its estimate is 99.1% of the exact value at M=16M=16 and 100.1% at M=32M=32.

Second, we moved to a target where the exact answer is out of reach: 20 amino acids, encoded by 1.6×10101.6 \times 10^{10} DNA sequences. None of our 160 runs returns zero, and two runs on the same input differ by 0.10 nats (median). Neither deterministic baseline copes. Threshold pruning at τ=10−3\tau=10^{-3}, which keeps as many prefixes as it needs to cover 1−τ1-\tau of the mass, gets through only 8 of the 20 amino acids within the paper's five-minute limit. Capping the beam at the 256 heaviest prefixes instead, the same budget as ours but with no sampling or reweighting, does finish, but it falls 3.6 nats below our estimate, a factor of about 37.

Third, we used the estimator in a small biological example, scoring 198 ClinVar variants, each with up to 1,000 bases of genomic context, where its scores do not change with the particle budget (the example is described in our reply to Reviewer y8Vk).

For a 200-amino-acid target (about 109310^{93} encodings) we used a smaller 1B Evo2 network. Four runs finish with no zeros and a standard deviation of 0.20 nats, and the beam capped at the same budget is 63 nats below our estimate. So the result the review highlights at 200 amino acids is no longer confined to the bigram model of Fig. 6.

Does forming every live child become expensive with a large vocabulary? No. First, this step is shared with the baseline (Snæbjarnarson et al., 2026): threshold-pruned beam summing builds the same child pool and differs only in the prune applied to it (Fig. 1, lines 24–26). Second, as in the paper (App. K), in the PTB experiments the estimator runs on the already byte-converted form of the model, so a prefix has at most 256 children whatever the tokenizer, and far fewer are live: on the Wikipedia paragraph of the text experiment, 6.3 per extended prefix with GPT-2 Large and 7.5 with Llama-3.1-8B. Runtime is thus mainly governed by the number of retained prefixes times the cost of a forward pass, and moving to a model with ten times the parameters and 2.5 times the vocabulary raised our estimator's time by 2.7×2.7\times.

We used GPT-2 in the submission for comparability with the work we re-evaluate. For the reading-time analysis it remains the standard choice, because its surprisal predicts human reading times better than that of larger models (Oh & Schuler, 2023; de Varda & Marelli, 2023; Shain et al., 2024).

Response (2/2).

W2: the pruning bias seems to have little practical effect on text.

The review bases this on §4.3, where we repeat a published reading-time study with our estimator in place of threshold pruning: total surprisal falls by 1.4% and the study's conclusions do not change. We read that result differently, for three reasons. First, until now there was no unbiased estimate to compare against, so it was not possible to tell whether pruning had affected that study. We now find no evidence that it did. Had the conclusions changed, that would have been the finding. Second, the 1.4% is an average that hides large individual errors. One percent of the units (roughly, words) account for 95% of the change, and the surprisal of single units moves by up to 14.5 nats (App. I). An analysis that leans on those units would be affected. Third, the bias on text is not confined to that study. For the same word-level transduction, pruning is 8.4 nats from the exact corpus value with the bigram source (Fig. 5), 33 nats below our estimate over ten paragraphs with GPT-2 Large (Tab. 4), and 4.2 nats below it on a single paragraph with Llama-3.1-8B (W1).

We agree that the runtime gains are largest for DNA, but we would not call that a narrow case. Language models over biological sequences are a large and active area, proteins run from tens to thousands of amino acids, and at those lengths threshold pruning is not usable.

W3: no related-work section, and no explanation of or comparison with other SWOR and SMC methods.

The work our method builds on is deliberately discussed in the main text, where it is used: the transduced-model framework of Snæbjarnarson et al. (2026) in §2 and §3.1, and Horvitz–Thompson reweighting and sampling without replacement (Horvitz & Thompson, 1952; Fearnhead & Clifford, 2003; Shah & Kroese, 2018) in §3.2. App. L is something else: a list of papers that use similar tools for different problems. Our introduction pointed to it as "the connection to related work", which gave the impression that it was our whole treatment of prior work. We will correct that sentence so that it directs readers to §2 and §3, and we will add to App. L an explanation of how these papers differ from ours. They use some of the same tools in other settings: Kool et al. and Meister et al. sample complete sequences without replacement for decoding, using Gumbel-top-k and conditional Poisson designs, and Lew et al. use SMC to steer constrained generation. Our quantity is a sum over a possibly infinite set of source prefixes, which needs a halting guarantee that those settings do not.

The comparison that is informative in our setting is therefore between the tools themselves, and that is the paper's main experiment. Our baselines smc_simple and smc_rb are standard sequential Monte Carlo with resampling with replacement (Del Moral et al., 2006; Naesseth et al., 2019; App. C) applied to transduced models, and they are compared with our without-replacement estimators throughout (Figs. 4 and 5, Tabs. 2 and 5). App. K also changes only the resampling scheme and keeps everything else fixed: 71 of 320 with-replacement runs return zero, and none of the 320 without-replacement runs do.

Soundness.

The paper's contribution is a method with guarantees, and each of its claims is supported as follows.

  • The estimator is unbiased, and the adaptive algorithm halts with probability one. These are proved (Theorem 3.1, Proposition 3.2). They are also confirmed against exact probabilities in every setting where these can be computed: the bigram text model (Fig. 4, Figs. 17–18), brute-force enumeration for the bigram and neural DNA models (App. J), and now Evo2-7B (above).
  • It has a better compute–variance tradeoff on text, and lower error on DNA, than the sequential Monte Carlo baselines. This is an empirical claim, and we test it in five experimental settings against five estimators: threshold-pruned and capped beam summing, two sequential Monte Carlo baselines, and an ablation that changes only the resampling scheme (Tabs. 2 and 5, Figs. 4–6, App. K), with up to 256 runs per setting and sweeps over the method's parameters (App. F).
  • It makes long, high-entropy targets feasible. Shown on DNA-to-amino-acid transduction up to 200 amino acids with the bigram DNA model, where the estimate is within 0.06 nats of the exact value (Fig. 6), and now at 200 amino acids with a 1B Evo2 network (above).

We appreciate that the review lists the proofs as a strength and does not question any of these claims. Its concerns are whether the experiments extend to recent models, how much the bias matters on text, and how prior work is presented, and we have addressed each above. We hope this allows you to reconsider your assessment.

As the discussion process is drawing to an end, we'd greatly appreciate hearing whether the reviewers' concerns have been resolved by our responses. We're also happy to answer any further questions or comments.

Thank you for pointing out the results I had missed using newer models. This addresses a primary concern, so I have increased my score to a weak accept.

Reviewer_tKR8OpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors introduce an efficient, unbiased estimator for transduced language model probabilities. They compare this primarily to the method from Snaebjarnarson et al (2026), and demonstrate a favorable compute-variance tradeoff.

Critical strengths

The sampling method seems to be a large improvement over the baseline. I am generally excited about methods that adapt language models trained with one tokenizer to score sequences under another. I also appreciate that the method gives an unbiased estimate and allows quantifying the sample variance.

Critical weaknesses

I believe the paper may mislead a reader to expect the sampling method be faster in most cases when it could be the case that only a few specific types of transductions benefit from the speedups. In particular, the DNA example seems uniquely suited to advantage the sampling method. My understanding is that, since there are many roughly equivalent ways to represent a sequence of proteins, the probability mass will be spread out fairly evenly across an exponentially large set of sequences, while in more natural language settings, the speedups often fail to appear.

Questions for authors

Could this algorithm help with, say, converting a trained subword language model to a byte-level model?

3 comments

We thank the reviewer for the careful reading and for supporting our work.

W1: speedups may be specific to DNA-like transductions.

We agree on this point, and the reviewer's reading of why is correct. Threshold pruning must keep enough source prefixes to cover 1−τ1-\tau of the mass. When each target symbol leaves several source continuations plausible, as with synonymous codons (different base triplets that encode the same amino acid), that number grows exponentially with target length, and this is where our method is orders of magnitude faster. When ambiguity is rarer, relatively few prefixes may carry most of the mass and pruning will then be cheaper. The same structure arises whenever a transduction maps source units to much coarser classes, for example words to their part-of-speech class, but DNA is the only such case we evaluate.

For transducing text the speedup is less dramatic than for DNA, but it is there once accuracy is matched. With the bigram source model, where exact probabilities are available, pruning improves slowly with compute: its error is 63, 22 and 8.4 nats after 39, 184 and 752 s, while our estimator's standard deviation is 0.16 nats at 623 s (Fig. 5). On one paragraph with GPT-2 Large, tightening τ\tau from 10−310^{-3} to 10−410^{-4} raises the time from 56 s to 266 s and the estimate by 0.1 nats, leaving it 2.3 nats below our reference estimate; a single run of ours at M=200M=200 takes 45 s and is within about 0.2 nats of that reference. With Llama-3.1-8B the same step raises the time from 85 s to 641 s and leaves a gap of 3.6 nats, against 123 s and about 0.2 nats for ours (see our reply to Reviewer 867u). Over ten paragraphs with GPT-2 Large, our estimator at M=200M=200 takes 772 s against 1224 s for pruning and lies 29 nats above it (§4.2, Fig. 19). Note that pruning's error is a bias, while ours is the run-to-run spread of an unbiased estimate.

We will revise the abstract and introduction to more clearly separate these cases: large runtime gains for high-entropy transductions, a smaller gain at matched accuracy on PTB text, and no gain for subword-to-byte conversion (see Q1).

Q1: Could this algorithm help with converting a trained subword language model to a byte-level model?

The algorithm applies to this conversion unchanged, but it does not help there. We tested this on a full 833-byte Wikipedia paragraph with GPT-2 Large: threshold pruning at τ=10−3\tau=10^{-3} changes by only 0.03 nats when the threshold is tightened tenfold, and it agrees with our estimator at very large budgets to within about 0.1 nats, so there is almost no bias to remove. For this conversion we recommend threshold pruning as in Snæbjarnarson et al. (2026), or the dedicated algorithm of Vieira et al. (2025).

Thank you for your clarifications and confirmation. Despite the slightly weaker usefulness in generic/practical applications, I stand by my assessment that the paper is of interest to the community.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.