Imagine asking a language model how likely a short protein sequence is—not as a string of DNA letters, but as the chain of amino acids the DNA could produce. The question sounds simple until you notice that several DNA codons can specify the same amino acid. To find the protein sequence’s probability, a computer must gather probability from all the DNA sequences that translate into it.
That pile of possibilities grows fast. Add another amino acid, and many new DNA sequences can lead to it. A model that assigns probabilities to DNA strings may spread its weight across a huge number of possible routes to the same protein. Calculating the total exactly can become impractical long before the protein sequence is long.
This is one version of a broader problem in AI: a language model works in one kind of string, while an application needs probabilities over another. Researchers can connect the two with a finite-state transducer, a compact rule system that maps one sequence into another. But the probability of a target sequence still depends on summing the weights of every source sequence that maps to it—an enormous search through what the paper calls a “precover.”
A common shortcut is to explore the most promising partial sequences first and discard the faintest branches. It resembles searching a maze by following the bright, obvious corridors and abandoning dim side passages. The method is fast, but it has a built-in blind spot: discarded branches may contain meaningful probability. The result is a lower estimate, and the amount missing is unknown.
The researchers’ new approach changes what happens to those branches. Rather than permanently throwing away low-weight candidates, it samples distinct partial sequences without replacement. Each sampled sequence gets a correction based on its chance of being selected, so that, across repeated runs, the estimates recover the probability mass on average. The correction does not make every run exact; individual estimates still vary. But the lost mass is no longer silently treated as zero.
The method also adjusts its workload as it proceeds. At first, it may need to track many candidates. As probability accumulates toward the estimate, it can reduce the number it keeps. A randomized stopping rule ensures the calculation eventually halts with probability one—even in cases where the relevant set of source strings could keep expanding. The researchers prove that this adaptive sampling preserves the estimator’s unbiasedness.
DNA offered a demanding test. The team used a DNA-to-amino-acid mapping and compared its method with threshold-based pruning. With a DNA bigram model, the older method passed five minutes of computation by amino-acid position 13. The adaptive sampler, with a maximum budget of 256 particles, reached position 200 in about five seconds. Here, “particle” means a candidate sequence prefix carried through the computation—not a biological particle. The result is a much longer run of probability estimates, not a prediction that a particular protein exists or will be made.
The researchers checked accuracy where exact answers could be computed by brute-force enumeration, comparing estimates across 64 random seeds and three target sequences. Their tests also included a GPT-2 model trained on human DNA. In these experiments, increasing the sampling budget generally reduced estimation error. The gain is not that randomness magically solves the problem; it is that the algorithm can trade computing time against variation while keeping an honest accounting of what it has sampled.
The same issue mattered in a very different setting: estimating how surprising a word is to a language model, a quantity used in studies of reading time. The researchers replaced threshold pruning in an earlier analysis of eye-tracking data with their unbiased sampling method. The estimated corpus surprisal came out 106 nats lower. Yet the rerun found no evidence that the change produced different predictions of reading time, and the original broad conclusion remained intact.
That contrast is revealing. An estimator can shift a numerical total without overturning the scientific result built on it. But without a way to measure what pruning discards, researchers cannot tell whether a stable conclusion is robust or simply resting on an unexamined approximation. Repeating the estimate with weighted sampling gives them a way to check.
The work does not teach AI a new biological fact, nor does it turn a language model into a tool for discovering proteins. It offers a more careful way to calculate probabilities when a transformation hides many possible routes between the model’s input and the question researchers want to ask. In that sense, the advance is less like a faster shortcut through the maze than a new rule for exploration: some paths can be skipped, provided their missing weight is still counted.
