The Lempel-Ziv parse of Chad Gadya (חד גדיא), right-to-left, drawn as an arc diagram. Generated by Claude Opus 5.5

I have published a new paper on efficient string prediction. It was written during the PIBBSS 2026 summer fellowship, under the mentorship of Vanessa Kosoy.

This research builds on Kosoy's previous work in stringology. Kosoy built a polynomial-time algorithm for predicting repetitive sequences and I have used other algorithmic techniques to further decrease the runtime.

The goal of this post is to explain some of the ideas from Kosoy's paper and how my work builds on them. My writing will be mostly informal; the field of string algorithms has a lot of technical jargon which I will not try to fully explain. I hope to mostly communicate interesting ideas and topics I've bumped into during the research, while linking to external resources for anyone who wishes to learn more.

The prediction trinity

There are three things we want every good predictor to have:

• Power: can predict general, real-world patterns.
• Efficiency: can run in practice.
• Formal guarantees: we can prove what it can or can't do.

Unfortunately, no framework today satisfies all three properties at once.

Deep learning is powerful and efficient, but lacks a strong framework of formal guarantees. (This might be a problem!)

Solomonoff induction / AIXI are extremely powerful, and have formal guarantees, but can't actually run in practice.

My research is on the third edge: efficient algorithms with formal guarantees, though ones that are still not powerful enough for "actual" intelligence.

Of course, classical learning theory already has plenty of efficient algorithms with provable guarantees (e.g. linear regression). However, these algorithms assume the shape of the hypothesis is fixed in advance and learn its numerical parameters; our algorithms learn compositional structure, as described in Kosoy's compositional learning theory. (Deep learning also learns numerical parameters, but it uses them to represent hidden structure in opaque ways, while our goal is to make such structure explicit.)

The question is then: which structural prediction tasks can be done efficiently?

The hypothesis space given to Solomonoff induction is extremely ambitious: the environments are generated by any computer program. Solomonoff induction is thus uncomputable and can never be implemented in practice.

We could reduce to bounded-time programs, but it's still too expensive: going over all programs of length that run in time takes time to run. We want prediction time that is at most polynomial in the string's complexity . For that to work, we need a weaker notion of complexity than program length.

So we will work with a very specialized subset of computer programs, called straight-line programs. Straight-line programs (SLPs) are programs that have two types of instructions:

• : assign a single symbol to a variable. ( is a general alphabet but you can think of as an example)
• : define a new string as a concatenation of two previous ones ().

An SLP defines strings in order. The final variable is the program's output, and (the number of instructions) is called the size of the program.

We define the Straight-Line Complexity of a string , , to be the size of the smallest SLP that generates .

We write for the length of a string . We always have : we initialize variables for all symbols in the alphabet, then build the string one symbol at a time by concatenating the next symbol each instruction.

For special strings we can do much better. For example, we can build the Fibonacci words ^[1] by concatenating the two previous words at each step:

The lengths of follow the Fibonacci sequence. grows exponentially in the number of instructions , so these words have very short descriptions: .

Matching the string's history

An important property of small SLPs is that the strings they generate tend to be very repetitive. If a small number of instructions is used to generate a large string , it means that the variables in the program appear over and over again when constructing .

For example, expanding the definition of the Fibonacci word results in two occurrences of and three occurrences of : (they actually appear more than that if you look at the boundaries between different terms)

We can use that insight for prediction: when predicting the next symbol, we look at the last few symbols, search for all previous occurrences of this string, and return the symbol that followed them most often.

If we take a partial version of : , we see that the last 4 digits have two previous occurrences in the string ^[2] , and each such occurrence was followed by a 0. This correctly predicts that the last digit of is 0.

The idea of "match the last few symbols" is formalized by the Lempel-Ziv factorization of (optional technical explanation given below).

Lempel-Ziv factorization

Lempel-Ziv (LZ77) is a string processing algorithm that decomposes a string into repeating components. The Lempel-Ziv phrases are defined inductively: is either a single symbol (if that's its first occurrence in ), or the longest prefix of that has an earlier occurrence in . is defined as the number of phrases in the Lempel-Ziv decomposition of .

The prediction algorithms described in this post are proved in terms of and not . This suffices for predicting strings generated by small SLPs, because we can show that in general.

Lempel-Ziv Plurality (LZP) uses the last Lempel-Ziv phrase as its context and predicts the symbol that most often followed its earlier occurrences.

LZP has two operations:

• predict: Output the predicted next symbol,
• update: Process the actual next symbol after it is revealed.

In her paper, Kosoy proves the following result:

Theorem (Kosoy): Assume a constant-size alphabet and let be a string with . Then LZP predicts with at most mistakes. A single update and prediction costs .

Now we have an algorithm that runs in polynomial time in terms of the string's complexity !

Going faster

What are the conceptual inner workings of LZP? What is it bottlenecked by? Can we make it faster?

LZP provides a reduction: from predicting the future ("what is the next symbol?"), to querying the past ("how often did this substring appear before?"). The problem of string matching is widely studied, and for example, computational biologists use it all the time when searching for short DNA sequences within a genome.

Kosoy uses a data structure by Kempa and Kociumaka called -SA, which takes a compressed Lempel-Ziv representation of a string and "indexes" it to make pattern matching on much faster. The problem is that it's a static structure: once we get the new symbol , we have to throw away the index we built for and build a new one for . The amazing property of -SA is that its construction is fast for repetitive strings: the time complexity is , which is polynomial in and not in (which can be much larger).

Still, we would like a dynamic structure here.

For this purpose, I use a different string-processing technique called the Burrows-Wheeler Transform.

I won't get into the technical details here - see here for a great series of lectures on BWT.

The TL;DR is that instead of saving the string in memory, we save a certain permutation of it, called . This permutation has two great properties:

Fast string search: The occurrences of a string inside match a contiguous interval . To find the number of occurrences of in (where is a candidate next symbol), ^[3] we just have to count the number of occurrences of in . This can be calculated by two rank queries: , where is the number of occurrences of in . ^[4]

Compressed form: For repetitive strings , consists of a small number of long runs of the same symbol. This allows us to write much more succinctly, taking less space. This is called the Run-Length representation of BWT, and denoted RLBWT (not to be confused with the other type of RL).

Here's an example adapted from Langmead's lectures:

has 64 symbols but only has runs.

It can be shown that in general, so a string with small straight-line complexity will also have a short RLBWT representation.

We can implement dynamic RLBWT with efficient update and rank operations: both cost time, where is the number of runs in . By the statement above, this is time.

Using this construction, we get a predictor that:

• Updates in time ,
• Predicts the next symbol in time , where is the size of the alphabet. (There are rank queries, two for each candidate symbol.)

This is already very efficient: we went down from to . When the alphabet is small (like ), this is an exponential improvement!

Going even faster

But if is large, prediction is still too slow. What's the new bottleneck? How can we get around it?

If the last Lempel-Ziv phrase of is , then our task is to find the symbol that maximizes the number of occurrences of . By our reduction, this is equal to the symbol that appears most often in an interval . Our RLBWT-based algorithm does this by going over all symbols , calculating the number of occurrences of each one, and choosing the symbol with the most occurrences.

Can we skip the iteration over all symbols?

Let's define a different prediction rule, alternative to LZP, which we'll call Lempel-Ziv Majority (LZM):

• See if there is a symbol such that a strict majority of the past occurrences of in are followed by .
• If there is such a symbol , it is unique; predict .
• Else, predict an arbitrary symbol.

LZM is a weaker prediction rule than LZP: it doesn't always find the symbol that maximizes the number of occurrences, only when that symbol accounts for over half of all occurrences. Translating back to intervals, the interval has as the plurality choice (it appears twice while each appear once), but is not a majority (it fills only of the interval).

However, LZM gives the same mistake bound as LZP - (in fact the proof for LZP's mistake bound extends naturally to LZM). So relaxing the prediction rule doesn't cost us anything in the worst-case.

We do gain a lot in efficiency: now we don't have to calculate the occurrences of all symbols in an interval, only find the majority (if it exists). We have a more efficient algorithm for doing that, inspired by the Boyer-Moore majority algorithm.

Here's a rough idea for how it works (keeping in mind that we are working with the BWT string ):

Take the substring , and at each step take a pair of distinct symbols that appear next to each other in , and make both disappear. Repeat this process until nothing remains, or until has only one type of symbol left. If there is a strict majority , it is guaranteed to be the only symbol remaining.

Cancelling the symbols one step at a time still takes steps, but if we use the run-length representation to cancel entire runs plus use a binary tree to cache cancellations of many small intervals in , we can do this calculation in .

This results in a predictor that supports both updates and predictions in time , regardless of the alphabet size.

Going fastest

Yet, for small alphabets, we can do better.

To see how, we need to ask which computational model we are using.

For a lot of computational problems, this question doesn't matter: all types of computation are equivalent, and any computational model that's powerful enough can simulate any other model. Turing machines are the classic example, but since we can build a computer in Minecraft, the halting problem is just as relevant for redstone.

However, these different models do differ in terms of efficiency. Turing machines only read and write one bit at a time. Multiplying two 64-bit integers naively takes about bit-operations. But in modern CPUs, this is done by a single assembly instruction.

The word RAM model is a way to formalize that. The basic unit of memory is a -bit word, and we are allowed to add, multiply and do other basic operations with these words in a single instruction. CPUs often use , but we can abstract away to any value of : the larger the word-size gets, the more powerful our machine becomes, and it is useful to consider how efficient our algorithms get for different values of .

Allowing fast arithmetic on -bit integers uncovers a new toolbox of efficient operations.

One example is parallel comparison (explanation adapted from the Stanford lecture notes). Assume we have 8 pairs of 7-bit integers that we want to compare, that is, answer the following 8 queries:

Pack into one 64-bit word . Each number takes up the bottom 7 bits of a byte; we'll set the remaining top bits to 1. Similarly, pack into one 64-bit word , and set the top bit in each byte to 0. Then subtract from :

The th byte computes , so there is no borrowing between bytes. Its top bit gives the answer:

One subtraction achieves eight comparisons. ^[5] A similar trick is implemented in glibc for testing several bytes of a string at once.

In the RAM model, we can think of a machine word as a miniature database. It can be used to store many small values in a packed data structure, and using additions and multiplications, we can encode many clever operations on these values. Parallel comparison is just one example of many. (For another example, an array of integers can be sorted in time, beating the usual lower bound for comparison-based sorting.)

Bille et al.'s dynamic partial-sums structure uses such word-RAM techniques. Using it in our LZP predictor, we get a time of per symbol.

We need to fix the word size ahead of time. What value of do we use?

Assume the final string length is known ahead of time. If , this means that doesn't fit in a single machine word. This would make index calculations in expensive - it would take multiple operations just to calculate the difference between two offsets in , for example. Thus, a reasonable choice is .

Another way to think of it is first choosing , then limiting the string length up to . (For comparison, allows up to symbols - this is 18 Exabytes, likely more than the training data for all frontier models. supports much more data than humanity ever generated.)

So, choosing , we get a running time of . In particular, there are many highly-repetitive strings which satisfy for some constant . Fibonacci words are an example for and the constant alphabet . For these strings, all updates and predictions always run in constant time, .

In fact, I believe that we can do even better than that - a construction giving time per symbol. This would result in constant-time operations for , even for large alphabets. I also believe this runtime is asymptotically optimal for the "incremental RLE" data structure I use in my paper. The construction and proofs were generated with AI, and I haven't fully checked them yet, so I've left these last claims out of the paper.

Ending thoughts

The predictors described here, while interesting in theory, are clearly not sufficient for designing safe AI systems. These are all toy models that are not nearly powerful enough to compete with modern ML algorithms.

I think of it as a proof of concept for future research: given a tractable prediction goal, we can make tailor-made, highly optimized implementations that achieve this goal.

AI is already being used to improve the efficiency of its next generation. While my type of research feels similar to capabilities research in some ways (improving the runtime of algorithms), its output is an algorithm that we could fully understand and have formal guarantees on.

My ultimate goal is to have an AI that is built, not grown. We are obviously very far away from that point, and it is likely that the gap between verifiable and heuristic AI won't be closed in time absent a significant pause or slowdown. I still think researchers should put significant effort into formal methods. Optimizing LLMs all the way to the endgame is not an inevitable outcome, and advances in other, safer forms of intelligence could make all the difference.

1. The actual Fibonacci words start with instead. I chose a different convention for aesthetic reasons but the resulting structure is the same. ↩︎

2. I've chosen the last four symbols for clarity, but the actual algorithm would use a different context size. ↩︎

3. We actually use throughout the algorithm instead of . We have to reverse the string, because BWT allows us to extend string queries on the left ( to ), not on the right. This is called a backward step. ↩︎

4. We often define intervals as half-open, , and define as the number of occurrences of before position . The count is then . Apologies for any off-by-one confusions that will surely arise! ↩︎

5. Besides subtraction, we need to prepare the input (pack the values into and the values into ), and isolate the output (use the top bits as inputs to other functions). This incurs additional operations, but they are done in constant time as well. ↩︎