[Linkpost] ”[Paper] Stringological sequence prediction I” by Vanessa Kosoy

This is a link post. TLDR: The first in a planned series of three or more papers, which constitute the first major in-road in the compositional learning programme, and a substantial step towards bridging agent foundations theory with practical algorithms. Official Abstract: We propose novel algorithms for sequence prediction based on ideas from stringology. These algorithms are time and space efficient and satisfy mistake bounds related to particular stringological complexity measures of the sequence. In this work (the first in a series) we focus on two such measures: (i) the size of the smallest straight-line program that produces the sequence, and (ii) the number of states in the minimal automaton that can compute any symbol in the sequence when given its position in base as input. These measures are interesting because multiple rich classes of sequences studied in combinatorics of words (automatic sequences, morphic sequences, Sturmian words) have low complexity and hence high predictability in this sense. The most serious criticism of the learning-theoretic alignment agenda (LTA), and of agent foundations research more broadly, is the gap between the theory on the one hand and algorithms with practical relevance on the other hand. Until now, all the mathematical models in [...] --- First published: April 7th, 2026 Source: https://www.lesswrong.com/posts/EEvHYKLsq92LmQ78a/paper-stringological-sequence-prediction-i-1 Linkpost URL:https://arxiv.org/abs/2603.26852 --- Narrated by TYPE III AUDIO.