Where Induction Runs Out: Description-Length Difficulty and the Memorisation Gap in Integer-Sequence Benchmarks

# Description-Length Difficultyand the Memorisation Gap in Integer-Sequence Benchmarks
Source: [https://arxiv.org/html/2608.29411](https://arxiv.org/html/2608.29411)
## Where Induction Runs Out: Description\-Length Difficulty and the Memorisation Gap in Integer\-Sequence Benchmarks

###### Abstract

Integer sequences from the On\-Line Encyclopedia of Integer Sequences \(OEIS\) are increasingly used to benchmark mathematical reasoning in language models\. We ask what such benchmarks actually measure, using an exactly computable reference learner: two\-part minimum description length \(MDL\) over the class of P\-recursive \(holonomic\) recurrences, evaluated on every prefix of a sequence as terms arrive\.

Three findings follow\. First, MDL difficulty is a*parameter count*\. The discovery pointndn\_\{d\}, the first prefix length at which a symbolic hypothesis beats verbatim storage, is predicted almost exactly by a combinatorial identifiability bound on the selected operator’s order and degree\. It is invariant to term magnitude: scaling Fibonacci over twelve orders of magnitude leavesndn\_\{d\}unchanged, because a hypothesis must encode its own initial conditions and the magnitude cancels\.

Second, at scale the learner exhibits a regime our curated corpus could not produce even once: across20,00020\{,\}000OEIS sequences,89\.98%89\.98\\%of those that fit a recurrence on some prefix fit*none*at full length\. We call this the*wilderness*—induction acquires a theory, loses it, and never recovers\.

Third, evaluating three language models on sequences stratified by these MDL regimes*refuted*our pre\-registered hypothesis: models do not confabulate where MDL reports no theory, but hedge appropriately\. Confident errors are*inverted*, concentrating on the easy stratum, where apparent competence tracks recognition of the sequence rather than induction of its rule\. OEIS\-derived benchmarks therefore substantially measure memorisation, and MDL supplies a cheap, contamination\-free difficulty signal they currently lack\. Code, data and all model responses are released at[https://github\.com/sabilashang/where\-induction\-runs\-out](https://github.com/sabilashang/where-induction-runs-out)\.

## 1Introduction

Integer sequences are an appealing test of mathematical reasoning: the input is short, the answer is checkable, and the OEIS\[[15](https://arxiv.org/html/2608.29411#bib.bib15)\]supplies hundreds of thousands of them for free\. They have become a standard benchmark for language models\[[4](https://arxiv.org/html/2608.29411#bib.bib4),[16](https://arxiv.org/html/2608.29411#bib.bib16)\]\. A benchmark is only as good as its difficulty measure, yet it is not obvious what makes one sequence harder than another—growth rate, mathematical depth, or the number of terms needed before the rule is pinned down\.

This paper answers that question with an exactly computable reference learner, then uses the answer to audit what the benchmark measures\. The learner is two\-part MDL\[[18](https://arxiv.org/html/2608.29411#bib.bib18),[10](https://arxiv.org/html/2608.29411#bib.bib10)\]over holonomic recurrences, applied to every prefix of a sequence as terms arrive one at a time\. We choose the class because its MDL hypothesis is exactly computable by linear algebra overℚ\\mathbb\{Q\}\(no search heuristic confounds the measurement\), and because it is the natural symbolic class for integer sequences\[[23](https://arxiv.org/html/2608.29411#bib.bib23),[26](https://arxiv.org/html/2608.29411#bib.bib26),[11](https://arxiv.org/html/2608.29411#bib.bib11)\]\.

A natural picture of what such a learner does is dynamic\. Given1,2,4,161,2,4,16it entertainsan=na\_\{n\}=n, is refuted, moves toan=2​na\_\{n\}=2n, is refuted, triesan=2na\_\{n\}=2^\{n\}, and perhaps ends up bolting a piecewise branch onto a formula that no longer fits as a whole\. This picture of induction as successive revision underlies formal learning theory’s notion of mind changes\[[9](https://arxiv.org/html/2608.29411#bib.bib9),[7](https://arxiv.org/html/2608.29411#bib.bib7),[1](https://arxiv.org/html/2608.29411#bib.bib1)\]and Schmidhuber’s account of interestingness as the derivative of compressibility\[[21](https://arxiv.org/html/2608.29411#bib.bib21)\]\. Yet the modern literature reports only*endpoints*: whether the final expression is right\[[4](https://arxiv.org/html/2608.29411#bib.bib4)\], or how short the final program is\[[8](https://arxiv.org/html/2608.29411#bib.bib8)\]\. We measure the trajectory, defining the*revision spectrum*R⁡\(n\)=L⁡\(n\+1\)−L⁡\(n\)R\(n\)=L\(n\{\+\}1\)\-L\(n\)and two exact landmarks, the discovery point and the stabilisation point\.

Our findings, in order:

1. 1\.Revision is rare on classical sequences, common at scale\(§[4](https://arxiv.org/html/2608.29411#S4)\)\. Only2/612/61classical sequences ever revise, because MDL is self\-regularising: an overfitted recurrence costs more bits than the data it explains and is never selected\. At OEIS scale the rate rises to 315/2,780 \(11\.3%\), and is length\-dependent\.
2. 2\.Difficulty is a parameter count\(§[5](https://arxiv.org/html/2608.29411#S5)\)\. The discovery point is predicted by the identifiability boundnid=\(r\+1\)​\(d\+1\)\+s\+rn\_\{\\mathrm\{id\}\}=\(r\{\+\}1\)\(d\{\+\}1\)\+s\+r, a combinatorial function of the selected operator’s order and degree alone—exactly in89%89\\%of a labelled classical corpus and within±1\\pm 1in100%100\\%, against mean absolute error \(MAE\)3\.203\.20for a compression\-based predictor\.
3. 3\.Growth is irrelevant\(§[6](https://arxiv.org/html/2608.29411#S6)\)\. A controlled scaling experiment over twelve orders of magnitude leavesndn\_\{d\}exactly unchanged, because magnitude inflates the hypothesis and the literal code at the same rate and cancels\.
4. 4\.The wilderness\(§[8](https://arxiv.org/html/2608.29411#S8)\)\.89\.98%89\.98\\%of sequences that fit some prefix fit nothing at full length—a regime our classical corpus could not produce once\. Structural revisions, when they occur, are almost always single events rather than cascades\.
5. 5\.Benchmarks measure memorisation\(§[9](https://arxiv.org/html/2608.29411#S9)\)\. Evaluating three language models on MDL\-stratified sequences refutes our pre\-registered hypothesis and yields a stronger one: confident errors concentrate on the*easy*stratum, where apparent competence turns out to be OEIS recognition rather than induction\.

We regard the last of these as the practical contribution\. MDL difficulty is cheap to compute, independent of term magnitude, and \(unlike accuracy on a public dataset\) cannot be inflated by memorisation\.

## 2Related work

#### Linear complexity profiles\.

The closest quantitative relative of the revision spectrum comes from cryptography, not machine learning\. The linear complexity profile \(LCP\)L⁡\(s,N\)L\(s,N\)of a binary sequence is the length of the shortest LFSR generating its firstNNterms, computed by the Berlekamp–Massey algorithm\[[13](https://arxiv.org/html/2608.29411#bib.bib13)\]; its*jumps*asNNincreases have been studied in depth\[[19](https://arxiv.org/html/2608.29411#bib.bib19),[14](https://arxiv.org/html/2608.29411#bib.bib14),[25](https://arxiv.org/html/2608.29411#bib.bib25)\]\. This is precisely a revision spectrum for the special case of linear recurrences over a finite field\. We differ in three ways that matter\. First, our hypothesis class is holonomic rather than𝔽q\\mathbb\{F\}\_\{q\}\-linear, admitting polynomial coefficients and hence factorials, binomials and Catalan\-type sequences\. Second, our metric is a codelength in bits under a two\-part MDL objective rather than a register length, so hypotheses of different shapes are directly comparable\. Third, the domain and the goal are inverted: the cryptographic literature studies pseudorandom keystreams and wants profiles to be irregular, whereas we study structured mathematical sequences and ask what their regularity implies\. We report the LCP as a baseline in Appendix[B](https://arxiv.org/html/2608.29411#A2); it separates holonomic from non\-holonomic sequences but cannot distinguish the classes within\.

#### Mind\-change complexity\.

Formal learning theory quantifies how often a learner changes its conjecture before converging in the limit\[[9](https://arxiv.org/html/2608.29411#bib.bib9),[7](https://arxiv.org/html/2608.29411#bib.bib7),[1](https://arxiv.org/html/2608.29411#bib.bib1)\]\. Mind\-change complexity is a worst\-case bound \(an integer or a constructive ordinal\) quantified over an entire class of targets, and it counts changes\. By contrast, the revision spectrum is an empirical, per\-sequence trajectory whose unit is bits\. The two measures are orthogonal in quantification, unit, and object; our result in §[4](https://arxiv.org/html/2608.29411#S4)can be read as the observation that the empirical mind\-change count of MDL induction on classical sequences is almost always exactly one\.

#### MDL stabilization\.

[Poland and Hutter \[17\]](https://arxiv.org/html/2608.29411#bib.bib17)prove convergence and loss bounds for two\-part MDL in online prediction over countable model classes, and give sufficient conditions under which the MDL estimator*stabilizes*\. That work is the theoretical backdrop for §[4](https://arxiv.org/html/2608.29411#S4); it establishes that stabilization eventually happens, whereas we measure, on concrete sequences, that it happens immediately and characterize exactly when it does not\.

#### Symbolic regression and sequence induction\.

[d’Ascoli et al\. \[4\]](https://arxiv.org/html/2608.29411#bib.bib4)train Transformers to infer recurrences for integer and float sequences, evaluating on an OEIS subset;[Gauthier et al\. \[8\]](https://arxiv.org/html/2608.29411#bib.bib8)search for short programs generating OEIS sequences; classical symbolic regression\[[22](https://arxiv.org/html/2608.29411#bib.bib22),[24](https://arxiv.org/html/2608.29411#bib.bib24),[3](https://arxiv.org/html/2608.29411#bib.bib3)\]and inductive program synthesis\[[6](https://arxiv.org/html/2608.29411#bib.bib6)\]pursue the same target in other domains\. All report final expressions or final program sizes\. Guessing holonomic recurrences from finitely many terms is standard in computer algebra\[[20](https://arxiv.org/html/2608.29411#bib.bib20),[11](https://arxiv.org/html/2608.29411#bib.bib11),[12](https://arxiv.org/html/2608.29411#bib.bib12)\]; we use it as an exact oracle rather than as an end in itself\. Compression\-based accounts of interestingness\[[21](https://arxiv.org/html/2608.29411#bib.bib21)\]and of intelligence\[[2](https://arxiv.org/html/2608.29411#bib.bib2)\]motivate studying the trajectory, but do not compute one\.

## 3Setup

Table[1](https://arxiv.org/html/2608.29411#S3.T1)lists the symbols used below\.

Table 1:Notation used throughout\.### 3\.1Codes

All description lengths are in bits under prefix\-free codes, so the two\-part sum is a genuine codelength and Kraft’s inequality holds\. For a natural numberk≥0k\\geq 0we use the Elias gamma code\[[5](https://arxiv.org/html/2608.29411#bib.bib5)\],ℓ⁡\(k\)=2​⌊log2⁡\(k\+1\)⌋\+1\\ell\(k\)=2\\lfloor\\log\_\{2\}\(k\{\+\}1\)\\rfloor\+1; a signed integer costs one further sign bit\. The*literal*\(verbatim\) model of a prefixs1:ns\_\{1:n\}costs

Llit\(s1:n\)=ℓ\(n\)\+∑i=1nℓ±\(si\)\.L\_\{\\mathrm\{lit\}\}\(s\_\{1:n\}\)\\;=\\;\\ell\(n\)\+\\sum\_\{i=1\}^\{n\}\\ell\_\{\\pm\}\(s\_\{i\}\)\.\(1\)This model always applies, which is what makes the MDL codelength finite for every sequence including those with no recurrence at all\.

### 3\.2Hypothesis class

Our classℋ\\mathcal\{H\}consists of holonomic operators

∑i=0rpi​\(n\)​sn\+i=0,pi​\(n\)=∑j=0dci​j​nj,\\sum\_\{i=0\}^\{r\}p\_\{i\}\(n\)\\,s\_\{n\+i\}\\;=\\;0,\\qquad p\_\{i\}\(n\)=\\sum\_\{j=0\}^\{d\}c\_\{ij\}\\,n^\{j\},\(2\)with integer coefficientsci​jc\_\{ij\}, together with therrinitial terms needed to run the recurrence forward\. Settingd=0d=0recovers the C\-finite \(constant\-coefficient\) case\. A hypothesisH∈ℋH\\in\\mathcal\{H\}costs

L⁡\(H\)=ℓ⁡\(r\)\+ℓ⁡\(d\)\+∑i,jℓ±​\(ci​j\)\+∑k=1rℓ±​\(sk\)\.L\(H\)\\;=\\;\\ell\(r\)\+\\ell\(d\)\+\\sum\_\{i,j\}\\ell\_\{\\pm\}\(c\_\{ij\}\)\+\\sum\_\{k=1\}^\{r\}\\ell\_\{\\pm\}\(s\_\{k\}\)\.\(3\)For Fibonacci,r=2r=2,d=0d=0, the coefficients are\(1,1,−1\)\(1,1,\-1\)\(encodingsn\+sn\+1−sn\+2=0s\_\{n\}\+s\_\{n\+1\}\-s\_\{n\+2\}=0\), and the initial terms are\(0,1\)\(0,1\)\. Thenℓ⁡\(r\)=3\\ell\(r\)=3,ℓ⁡\(d\)=1\\ell\(d\)=1, each of the three coefficients costs44bits, and the two initials cost22and44bits, soL⁡\(H\)=22L\(H\)=22\. We admitHHonly if it annihilates every available term and its leading polynomialprp\_\{r\}is nonvanishing on the range used, so thatHHgenuinely determines the sequence and is therefore a legitimate code for it\. BecauseHHreproduces the data exactly,L⁡\(D∣H\)=0L\(D\\mid H\)=0and the two\-part objective reduces to \([3](https://arxiv.org/html/2608.29411#S3.E3)\)\.

The MDL codelength of a prefix is then

L\(n\)=min\{minH∈ℋ,H⊧s1:nL\(H\),Llit\(s1:n\)\}\.L\(n\)\\;=\\;\\min\\Big\\\{\\;\\min\_\{H\\in\\mathcal\{H\},\\,H\\models s\_\{1:n\}\}L\(H\),\\;\\;L\_\{\\mathrm\{lit\}\}\(s\_\{1:n\}\)\\;\\Big\\\}\.\(4\)Finding the inner minimum is exact: for each\(r,d\)\(r,d\), \([2](https://arxiv.org/html/2608.29411#S3.E2)\) is a homogeneous linear system in the\(r\+1\)​\(d\+1\)\(r\{\+\}1\)\(d\{\+\}1\)unknownsci​jc\_\{ij\}, so we screen for rank deficiency modulo a large prime and then compute the nullspace exactly overℚ\\mathbb\{Q\}, taking the primitive integer vector of each basis element\. We enumerate\(r,d\)\(r,d\)in increasing parameter count with a branch\-and\-bound cut, and require the system to be over\-determined by a slack ofs=2s=2equations—the standard guard in computer\-algebra guessing\[[11](https://arxiv.org/html/2608.29411#bib.bib11)\]\. §[4](https://arxiv.org/html/2608.29411#S4)shows this guard is nearly redundant\.

### 3\.3The revision spectrum

A revision spectrum records, term by term, whether the next integer was predicted, merely stored, or forced the learner to change its hypothesis\.

###### Definition 1\(Revision spectrum\)\.

For a sequencesswithNNterms, the*raw revision*atnnisR⁡\(n\)=L⁡\(n\+1\)−L⁡\(n\)R\(n\)=L\(n\{\+\}1\)\-L\(n\), and the*normalized revision*is

ρ\(n\)=R⁡\(n\)Llit\(s1:n\+1\)−Llit\(s1:n\)=L⁡\(n\+1\)−L⁡\(n\)ℓ±​\(sn\+1\)\.\\rho\(n\)\\;=\\;\\frac\{R\(n\)\}\{L\_\{\\mathrm\{lit\}\}\(s\_\{1:n\+1\}\)\-L\_\{\\mathrm\{lit\}\}\(s\_\{1:n\}\)\}\\;=\\;\\frac\{L\(n\{\+\}1\)\-L\(n\)\}\{\\ell\_\{\\pm\}\(s\_\{n\+1\}\)\}\.\(5\)The*revision spectrum*is the trajectory\{ρ⁡\(n\)\}n\\\{\\rho\(n\)\\\}\_\{n\}\.

The normalization is by the verbatim cost of the newly arrived term, which makesρ\\rhoscale\-free and gives it a direct reading:ρ=1\\rho=1means the term was absorbed at full verbatim cost \(nothing was learned\),ρ=0\\rho=0means the term was free \(the standing hypothesis already implied it\),ρ<0\\rho<0means the term triggered a simplification, andρ≫1\\rho\\gg 1means it forced a costly restructuring\.

###### Observation 1\(Exactness\)\.

L⁡\(H\)L\(H\)does not depend onnn\. HenceR⁡\(n\)=0R\(n\)=0*exactly*whenever the selected hypothesis is unchanged and structural, and every nonzeroR⁡\(n\)R\(n\)is either a genuine revision or a literal\-regime absorption\.

This is why we work with the raw increment rather than with a compression ratio: a ratio drifts merely because its denominator grows, manufacturing spurious “events”\.

###### Definition 2\(Landmarks\)\.

The*discovery point*ndn\_\{d\}is the leastnnwithL\(n\)<Llit\(s1:n\)L\(n\)<L\_\{\\mathrm\{lit\}\}\(s\_\{1:n\}\), i\.e\. the first prefix at which structure beats verbatim storage\. The*stabilization point*is the leastnnafter which the selected hypothesis never changes again\. A*structural revision*is a change of hypothesis at somen≥ndn\\geq n\_\{d\}\.

### 3\.4Corpus

We use6161classical integer sequences, each generated from its definition \(never transcribed\) and truncated toN=34N=34terms, labeled by ground\-truth position in the hierarchy:poly\(polynomial closed form,1515\),cfin\(C\-finite but not polynomial,1616\),prec\(holonomic but not C\-finite,1515\), andnonh\(provably not holonomic,1515\)\. Thenonhlabels rest on standard results: the primes, the partition and Bell numbers, the ordered Bell numbers and the classical multiplicative functions are not holonomic, and the Hofstadter, Kolakoski and Recamán sequences satisfy no linear recurrence with polynomial coefficients\. Table[7](https://arxiv.org/html/2608.29411#A1.T7)\(Appendix[A](https://arxiv.org/html/2608.29411#A1)\) summarises the corpus by class, and OEIS A\-numbers are given there for cross\-reference \(Figure[6](https://arxiv.org/html/2608.29411#A1.F6), Appendix[A](https://arxiv.org/html/2608.29411#A1)\)\.

We deliberately use a corpus we can generate and label rather than a sample of the OEIS itself, because ground\-truth class membership is the independent variable of every experiment here and the OEIS does not carry it\. The pipeline is class\-agnostic and runs unchanged on the OEISstrippeddump; see §[11](https://arxiv.org/html/2608.29411#S11)\.

## 4Revision is rare, and rarer than it looks

On labelled classical sequences the learner almost never changes its hypothesis\.

Across the corpus,22of6161sequencesexhibit any structural revision \(the cubes A000578 and the square pyramidal numbers A000330, one each\)\. Every other sequence either finds its operator once and holds it forever, or never finds one\. The mean number of structural revisions is0\.0330\.033\.

The reason is not the over\-determination guard\. Sweeping the slackssfrom22down to−2\-2—that is, permitting systems that are exactly determined or even under\-determined, where a recurrence can interpolate the very data it was fitted on—barely changes the picture\. MDL rejects those hypotheses on its own: a recurrence with enough free parameters to interpolatennterms costs more bits under \([3](https://arxiv.org/html/2608.29411#S3.E3)\) than theLlitL\_\{\\mathrm\{lit\}\}of those terms, so \([4](https://arxiv.org/html/2608.29411#S3.E4)\) never selects it\. Regularization by validation guard and regularization by codelength are, here, nearly the same constraint, and the codelength binds first\.

###### Proposition 1\(informal\)\.

Under \([4](https://arxiv.org/html/2608.29411#S3.E4)\), a hypothesis is selected only if it is strictly cheaper than the data it explains\. Since aℚ\\mathbb\{Q\}\-linear interpolant ofnnterms requiresΘ⁡\(n\)\\Theta\(n\)coefficients, each costingΩ⁡\(1\)\\Omega\(1\)bits, no interpolating hypothesis is ever selected\.

The practical consequence is that the churning picture of induction is not a description of what MDL does\. A learner that revises repeatedly is either using a hypothesis class with free parameters that are cheap relative to the data, or is not regularizing by description length at all\.

#### At OEIS scale\.

The classical corpus is not representative, and the rate does not survive contact with the full database\. Applying the identical pipeline to20,00020\{,\}000OEIS sequences\[[15](https://arxiv.org/html/2608.29411#bib.bib15)\], 315 of 2,780 fully holonomic sequences \(11\.3%\) at a fixed3030\-term budget exhibit at least one structural revision—an order of magnitude above the classical3\.3%3\.3\\%\(oeis\_fixed30\.csv\)\. Two caveats govern this number and we report both rather than controlling them away\.

First,*a sequence counts as holonomic only if an operator is found at full length*\. A recurrence fitted to some prefix but absent at full length is a distinct phenomenon \(§[8](https://arxiv.org/html/2608.29411#S8)\) and never enters this denominator; conflating the two inflates the revision rate roughly fivefold\.

Second, binning the mixed\-length run \(oeis\_results\.csv; a different population\) by available terms gives true\-holonomic revision rates4\.2%4\.2\\%\(2020–2222\),6\.1%6\.1\\%\(2323–2525\),9\.3%9\.3\\%\(2626–2828\),5\.7%5\.7\\%\(2929–3131\) and12\.0%12\.0\\%\(3232–3434\)\. The dependence is real but modest \(far milder than anndn\_\{d\}\-present denominator suggested\), so any single headline figure remains somewhat budget\-dependent\. Cross\-study comparisons must fix the term budget\. A fully controlled sweep at fixed length is left to future work for the reasons given in §[11](https://arxiv.org/html/2608.29411#S11)\.

Structural revisions are overwhelmingly single events rather than cascades: of sequences that revise at all, the modal and near\-universal count is one\.

## 5Discovery is identification\-limited

Where a formula is found is a count of free parameters, not a race against verbatim cost\.

If the trajectory is a single jump, the informative statistic is where the jump occurs\. Two thresholds could in principle governndn\_\{d\}:

nid\\displaystyle n\_\{\\mathrm\{id\}\}=\(r\+1\)​\(d\+1\)\+s\+r\\displaystyle=\(r\{\+\}1\)\(d\{\+\}1\)\+s\+r\(identifiability: fewest terms that determine the operator\),\\displaystyle\\text\{\(identifiability: fewest terms that determine the operator\)\},\(6\)n×\\displaystyle n\_\{\\times\}=min\{n:Llit\(s1:n\)\>L\(H∗\)\}\\displaystyle=\\min\\\{\\,n:L\_\{\\mathrm\{lit\}\}\(s\_\{1:n\}\)\>L\(H^\{\*\}\)\\,\\\}\(profitability: fewest terms for which it pays\),\\displaystyle\\text\{\(profitability: fewest terms for which it pays\)\},\(7\)giving the predictionnd=max⁡\(nid,n×\)n\_\{d\}=\\max\(n\_\{\\mathrm\{id\}\},n\_\{\\times\}\)\. A sequence is*identification\-limited*ifnid≥n×n\_\{\\mathrm\{id\}\}\\geq n\_\{\\times\}and*compression\-limited*otherwise\.

Table[2](https://arxiv.org/html/2608.29411#S5.T2)shows the outcome on the4646fittable sequences\.

Table 2:Prediction of the discovery pointndn\_\{d\}\. The identifiability bound alone accounts for the data; the compression threshold alone does not\.The predictionmax⁡\(nid,n×\)\\max\(n\_\{\\mathrm\{id\}\},n\_\{\\times\}\)is exact for41/4641/46and within±1\\pm 1for46/4646/46, with MAE0\.110\.11\. Butnidn\_\{\\mathrm\{id\}\}*alone*achieves identical numbers, becauseevery fittable sequence in the corpus is identification\-limited:n×<nidn\_\{\\times\}<n\_\{\\mathrm\{id\}\}without exception\. Discovery is not gated by whether the formula pays for itself: by the time the formula can be pinned down, it already pays\.

#### The dichotomy at scale\.

On the OEIS the pooled prediction accuracy appears to degrade sharply\. It does not: it splits\. Restricting to sequences with a full\-length operator and conditioning on whether they ever revise gives Table[3](https://arxiv.org/html/2608.29411#S5.T3)\.

Table 3:Accuracy of the identifiability predictionnd=nidn\_\{d\}=n\_\{\\mathrm\{id\}\}on the27802780OEIS sequences with a full\-length operator \(fixed3030\-term budget\), split by whether the sequence ever revises\. The pooled figure is dilution, not decay: the law is near\-perfect on non\-revisers and fails completely on revisers\.Among non\-revisers the identifiability law holds as tightly as on the classical corpus \(91\.9%91\.9\\%exact; MAE0\.110\.11, matching to two decimals\)\. Among revisers it fails completely\. Identifiability predicts discovery exactly, with one named exception—a deceptive prefix, which the revision spectrum itself detects\.

Consequentlyndn\_\{d\}is determined by the pair\(r,d\)\(r,d\)and nothing else\. It correlates with structural size atr=\+0\.85r=\+0\.85and with growth rate atr=−0\.007r=\-0\.007\(Figure[1](https://arxiv.org/html/2608.29411#S5.F1)a,b\)\. Meanndn\_\{d\}is7\.19±0\.987\.19\\pm 0\.98forcfin,8\.73±1\.878\.73\\pm 1\.87forprecand8\.53±1\.648\.53\\pm 1\.64forpoly\(one\-way analysis of variance \(ANOVA\)F=4\.70F=4\.70,p=0\.014p=0\.014\); the separation is driven mainly bycfin, andpolyandprecoverlap substantially\. Fittability itself separates the hierarchy perfectly: all4646holonomic sequences are fitted and all1515non\-holonomic ones are not\.

Figure 1:\(a\) The discovery point lies on the identity line against the identifiability bound\. \(b\) It is uncorrelated with growth rate\. \(c\) Control A: scaling Fibonacci’s initial condition over twelve orders of magnitude leavesndn\_\{d\}and the compression ratioλ\\lambdaexactly unchanged\.

## 6Growth invariance

Larger terms do not make a sequence easier to discover\.

That growth does not matter—already suggested by the near\-zero correlationr=−0\.007r=\-0\.007above—is initially surprising: storing the first3434factorials verbatim costs35193519bits and storing the first3434naturals costs315315, so one might expect the expensive sequence to reward a formula much sooner\. It does not: the factorials, the Fibonacci numbers and the naturals all share the same discovery pointnd=7n\_\{d\}=7, though their verbatim costs differ by an order of magnitude\. A controlled experiment isolates the mechanism\.

#### Control A\.

Fix the operator and scale the data\. We take Fibonacci witha⁡\(0\)=0a\(0\)=0anda⁡\(1\)=ka\(1\)=kfork=1,10,…,1012k=1,10,\\dots,10^\{12\}\. The operator is identical throughout; only the magnitude of the terms changes\. The literal cost rises from759759to33773377bits\. The discovery point isnd=7n\_\{d\}=7for*every*value ofkk, and the final compression ratioλ=L⁡\(N\)/Llit​\(N\)\\lambda=L\(N\)/L\_\{\\mathrm\{lit\}\}\(N\)is0\.0290\.029throughout \(Figure[1](https://arxiv.org/html/2608.29411#S5.F1)c\)\.

The reason is visible in \([3](https://arxiv.org/html/2608.29411#S3.E3)\): a hypothesis must encode itsrrinitial conditions, which are terms of the sequence\. Multiplying the sequence by101210^\{12\}inflatesL⁡\(H\)L\(H\)from2222to9898bits andLlitL\_\{\\mathrm\{lit\}\}from759759to33773377bits—by the same factor\. Magnitude information appears on both sides of the comparison in \([4](https://arxiv.org/html/2608.29411#S3.E4)\) and cancels\. What survives is structure\.

#### Control B\.

Vary the operator and the alphabet independently, using periodic sequences of nominal periodppover an alphabet of sizeAA\. AcrossA∈\{2,3,10,1000\}A\\in\\\{2,3,10,1000\\\}andp∈\{2,…,7\}p\\in\\\{2,\\dots,7\\\}we findnd=nid=2​p∗\+3n\_\{d\}=n\_\{\\mathrm\{id\}\}=2p^\{\*\}\+3exactly in all2424cells, wherep∗p^\{\*\}is the*true*period of the generated sequence, with no dependence onAA\. \(In one cell a randomly generated binary block of nominal period66repeated at period33; the law predictedp∗=3p^\{\*\}=3correctly\.\) The compression\-limited regime does not appear\. This is not an accident of the corpus: for a C\-finite operator of orderrr,nid≈2​rn\_\{\\mathrm\{id\}\}\\approx 2rwhilen×≈L⁡\(H\)/ℓ¯≈2​rn\_\{\\times\}\\approx L\(H\)/\\bar\{\\ell\}\\approx 2ras well, sinceL⁡\(H\)L\(H\)containsr\+1r\{\+\}1coefficients andrrinitial terms andLlitL\_\{\\mathrm\{lit\}\}accumulates one term\-cost per step\. The two thresholds scale together, and identifiability wins by the additive slack\.

## 7Deceptive prefixes

A structural revision occurs when a cheap wrong hypothesis fits a prefix of a more expensive truth\.

###### Definition 3\(Deceptive prefix\)\.

A sequence has a*deceptive prefix*of depthmmif its firstmmterms are consistent with a strictly cheaper hypothesis than the one governing the whole sequence\.

Deception is the only mechanism we find that produces revisions, and it is exactly the phenomenon the churning picture imagines\. We construct it\. Let

Dj=\(0 1\)j​0⏟period​p=2​j\+1D\_\{j\}\\;=\\;\\underbrace\{\(0\\,1\)^\{j\}\\,0\}\_\{\\text\{period \}p=2j\+1\}\(8\)repeated\. Its first2​j2jterms alternate, so a period\-22recurrence fits them; the term at index2​j2jbreaks it; the true operator has orderppand cannot be identified untiln=2​p\+3n=2p\+3\.

Figure[2](https://arxiv.org/html/2608.29411#S7.F2)shows the resulting spectrum forD3D\_\{3\}and reveals a canonical five\-phase shape\. Recall thatρ\\rhois indexed by its*source*prefix length, so the revision atnnis what installs the state atn\+1n\{\+\}1: a literal phase, a*spurious discovery*\(ρ⁡\(6\)=−0\.75\\rho\(6\)=\-0\.75, adopting the period\-2 operator atn=7n=7\), a*refutation*\(ρ⁡\(7\)=\+4\.50\\rho\(7\)=\+4\.50, the hypothesis is discarded atn=8n=8\), a*wilderness*in which the learner holds no theory and absorbs each term at full cost \(ρ=1\\rho=1\), and a*true discovery*\(ρ⁡\(16\)=−3\.50\\rho\(16\)=\-3\.50, the true operator is found atn=17n=17\) followed by permanent stability \(ρ≡0\\rho\\equiv 0\)\.

Figure 2:The five phases of a revision spectrum on the planted deceptive sequenceD3D\_\{3\}\(true period77\)\. Top: MDL codelengthL⁡\(n\)L\(n\)against the verbatim costLlit​\(n\)L\_\{\\mathrm\{lit\}\}\(n\), shaded by the phase holding atnn—literal \(grey\), spurious period\-2 fit \(blue\), wilderness \(orange\), stable \(green\)\. Bottom: the normalized revisionρ⁡\(n\)\\rho\(n\)\. Sinceρ⁡\(n\)\\rho\(n\)is indexed by its source prefix length, the revision atnnis what installs the state atn\+1n\{\+\}1; the shading in the lower panel is shifted one step left accordingly, so each spike is coloured by the phase it leads into\.Sweepingjjrecovers exact laws \(Figure[3](https://arxiv.org/html/2608.29411#S7.F3)\)\. The spurious fit always appears atn=7n=7; the refutation always atn=p\+1n=p\+1; the true operator always atn=2​p\+3n=2p\+3, matchingnidn\_\{\\mathrm\{id\}\}exactly for allp∈\{7,9,11,13,15\}p\\in\\\{7,9,11,13,15\\\}\. Peak revision magnitude grows with period up top=11p=11\(max⁡\|ρ\|=4\.50\\max\|\\rho\|=4\.50,7\.507\.50,10\.5010\.50atp=7,9,11p=7,9,11\) and then plateaus at11\.011\.0forp≥13p\\geq 13\. We do not have a mechanism for the plateau\. Deeper deception is not merely later, it is*louder*: the size of the spike measures how much cheaper the refuted theory was than its replacement\.

Finally we ask how often deception arises unplanted\. Sampling random periodic binary sequences, the fraction exhibiting a structural revision generally rises with period:0%0\\%forp≤4p\\leq 4,7\.5%7\.5\\%atp=5p=5,27\.5%27\.5\\%atp=6p=6,35%35\\%atp=10p=10,45%45\\%atp=12p=12, with a dip atp=11p=11\(27\.5%27\.5\\%\) and an overall rate of21\.8%21\.8\\%over440440sequences\. More complex operators leave more room for a simpler one to fit a prefix by chance\.

Figure 3:Deceptive prefixes in the planted familyDjD\_\{j\}and in random periodic sequences\. \(a\) The three landmarks—spurious fit, refutation, and recovery of the true operator—scale exactly with the true periodpp\. \(b\) Peak revision magnitudemax⁡\|ρ\|\\max\|\\rho\|grows throughp=11p=11and then plateaus at11\.011\.0; the dashed line is an ordinary least\-squares fit over the five planted periods, drawn only as a straight\-line reference against which the plateau is visible, and its slope is not itself a claim\. \(c\) Fraction of random periodic binary sequences exhibiting a structural revision, by period\.
## 8The wilderness

Most sequences that fit a recurrence on a short prefix have no recurrence at full length\.

The classical corpus contains sequences that are fitted and sequences that are never fitted\. At OEIS scale a third category dominates: sequences that fit a recurrence on some prefix and fit*none*at full length\. We call this regime the*wilderness*, after the phase in Figure[2](https://arxiv.org/html/2608.29411#S7.F2)in which the learner holds no theory and absorbs each term at full verbatim cost\.

The obvious explanation is truncation\. A sequence whose operator requires4040terms to identify is indistinguishable, under a3030\-term budget, from one that has no operator at all\. We tested this directly\. Taking the18871887sequences exhibiting the pattern, we re\-ran the guesser once on every available term; Table[4](https://arxiv.org/html/2608.29411#S8.T4)gives the outcome\.

Table 4:Truncation audit of the18871887OEIS sequences that fit a recurrence on some prefix but none at the3030\-term budget\. Each was re\-run on every term the database holds\. Truncation accounts for1\.54%1\.54\\%; in roughly nine cases in ten the prefix fit is genuinely not extensible even with≥40\\geq 40terms\.Truncation explains1\.5%1\.5\\%\. The regime is real: in roughly nine cases out of ten, a recurrence that fits an initial segment is genuinely not extensible, and the learner is left permanently without a theory despite ample data\.

This is the deceptive\-prefix mechanism of §[7](https://arxiv.org/html/2608.29411#S7)at scale, without the second act\. In our planted family the learner is deceived, refuted, and eventually recovers the true operator\. On real OEIS data it is deceived, refuted, and recovers nothing—because most OEIS sequences are simply not holonomic, while still admitting short\-prefix coincidences\. Our classical corpus could not exhibit this at all: its non\-holonomic members are so irregular that no prefix fit is ever cheap enough to be selected\. Curating a corpus for clean class membership removes precisely the phenomenon that dominates the wild database\.

For benchmark construction this is the most consequential regime, and we return to it in §[9](https://arxiv.org/html/2608.29411#S9): these are the sequences on which a plausible wrong answer is available early and no right answer is available at all\.

## 9What OEIS benchmarks measure

Large language models \(LLMs\) err confidently on easy sequences and hedge on hard ones\.

The preceding sections give a difficulty measure that is cheap, exact, and independent of term magnitude\. We now use it to audit the benchmark\. We stratified6060sequences into three MDL regimes:*clean*\(holonomic, no revisions\),*revising*\(holonomic,≥1\\geq 1structural revision\), and*wilderness*\(prefix fit only,≥40\\geq 40terms\), sketched in Figure[4](https://arxiv.org/html/2608.29411#S9.F4), and evaluated three LLMs: Claude Sonnet 4\.5, GPT\-4o and Llama 3\.3 70B\. Each model saw the first2020terms and was asked, in JSON, for the next three terms, a closed form or the tokenNO\_FORMULA\_FOUND, a confidence rating11–55, and whether it recognised the sequence\. Temperature00, one call per \(sequence, model\),180180calls total;1212failed and are reported as failures rather than imputed\. All responses are released\.

Figure 4:The three MDL strata used to stratify the language\-model evaluation\. In each panel the solid line is the MDL codelengthL⁡\(n\)L\(n\)and the dashed line the verbatim costLlit​\(n\)L\_\{\\mathrm\{lit\}\}\(n\); the dotted vertical marks the discovery pointndn\_\{d\}, where structure first beats verbatim storage\.*Clean*: an operator is found once and held, soLLdrops atndn\_\{d\}and stays flat\.*Revising*: the operator is later refuted and replaced by a costlier one, soLLreturns towards the verbatim cost and then settles at a new, higher level\.*Wilderness*: the prefix fit is refuted and nothing replaces it, soLLrejoinsLlitL\_\{\\mathrm\{lit\}\}and never leaves it again: the learner is left permanently without a theory despite ample data\. The curves are schematic, drawn to show the characteristic shapes rather than any measured sequence; the axes are therefore unticked\.#### Our hypothesis was refuted\.

We predicted that models would be confidently wrong in the wilderness: that they would supply a formula where MDL correctly reports that no theory exists\. They do not\. All three hedge appropriately: abstention in the wilderness is64\.7%64\.7\\%\(Claude,11/1711/17\),95\.0%95\.0\\%\(GPT\-4o,19/2019/20\) and89\.5%89\.5\\%\(Llama,17/1917/19\), with mean stated confidence3\.183\.18,2\.452\.45and2\.682\.68\. Whatever else these models do, they signal uncertainty when they have no answer\.

#### Confident errors are inverted\.

Defining confabulation as a stated confidence≥4\\geq 4together with a wrong continuation, the rate is*higher*on the easy stratum than the hard one for every model \(Table[5](https://arxiv.org/html/2608.29411#S9.T5)\)\.

Table 5:Confabulation rate \(stated confidence≥4\\geq 4together with a wrong continuation\) on the clean stratum, where a closed form exists, against the wilderness, where none does\. For all three models the rate is higher where the task is easier\. Denominators differ because failed calls are reported, not imputed\.
#### Because clean accuracy is recall\.

The contamination split explains the inversion\. Conditioning clean\-stratum accuracy on whether the model reported recognising the sequence gives Table[6](https://arxiv.org/html/2608.29411#S9.T6)\.

Table 6:Clean\-stratum exact accuracy split by self\-reported recognition\. Llama’s performance is entirely recall \(5/65/6on sequences it recognises and0/140/14on those it does not\), while Claude retains accuracy without recognition and GPT\-4o is essentially unaffected\. Recognition is self\-reported and may be unreliable\.Llama is not inferring recurrences; it is retrieving OEIS entries, and it is most confident exactly where retrieval is available\. Claude retains non\-trivial accuracy without recognition \(4/74/7\), and GPT\-4o’s accuracy is essentially unchanged by recognition, so the effect varies substantially by model, but the direction of the confabulation inversion does not \(Figure[5](https://arxiv.org/html/2608.29411#S9.F5)\)\.

Figure 5:LLM behaviour by MDL stratum\. \(a\) Confabulation rate \(stated confidence≥4\\geq 4with a wrong continuation\) on the clean stratum \(orange\) against the wilderness \(light blue\): confident errors concentrate on the easy stratum, not the hard one\. \(b\) Clean\-stratum exact accuracy split by whether the model reported recognising the sequence \(blue\) or not \(grey\); Llama scores0/140/14without recognition\. \(c\) In the wilderness, abstention \(green\) against exact accuracy on the next three terms \(grey\): all three models hedge, refuting our pre\-registered hypothesis\. All three panels are percentages on a fixed00–100100scale\.
#### Reading\.

A benchmark whose tractable stratum is answered by retrieval measures memorisation, and its apparent difficulty gradient partly tracks how well\-known a sequence is rather than how hard it is to induce\. The OEIS is public, indexed, and heavily represented in pretraining corpora, so this is difficult to avoid by curation alone\. What MDL supplies is a difficulty signal computed from the sequence itself:nidn\_\{\\mathrm\{id\}\}depends only on operator order and degree, is unaffected by term magnitude, and cannot be inflated by having seen the sequence before\. We do not claim it measures reasoning; we claim it measures information\-theoretic difficulty, and that the gap between the two is now itself measurable\.

## 10Recommendations for benchmark construction

Three concrete suggestions follow from the preceding two sections\.

Report operator order and degree\.If difficulty is operationalised as “how many terms must be seen before the rule is inferable”, that quantity isnid=\(r\+1\)​\(d\+1\)\+s\+rn\_\{\\mathrm\{id\}\}=\(r\{\+\}1\)\(d\{\+\}1\)\+s\+runder an MDL learner—cheap to compute and almost perfectly predictive\. Strata built on subjective easy/hard labels may be measuring parameter count, or worse, fame, while appearing to measure reasoning\.

Report accuracy conditioned on recognition\.A single accuracy figure on a public dataset cannot distinguish induction from retrieval\. Asking the model whether it recognises the item costs one field and, in our data, changes the interpretation completely: Llama’s clean\-stratum accuracy falls from25%25\\%to0%0\\%once recognised items are removed\.

Sample the hard regimes deliberately\.Deceptive\-prefix sequences, where a plausible wrong answer is available early, are rare under uniform sampling \(2/612/61in our classical corpus;21\.8%21\.8\\%even among random periodic sequences\), and §[7](https://arxiv.org/html/2608.29411#S7)supplies a generator with tunable depth\. Wilderness sequences, where no answer exists at all, test whether a model can decline—a capability all three models here possess and which no accuracy\-only benchmark rewards\.

## 11Limitations

Term budget\.The headline OEIS rate uses a fixed3030\-term budget \(oeis\_fixed30\.csv\); length dependence in §[4](https://arxiv.org/html/2608.29411#S4)is from the separate mixed\-length run \(oeis\_results\.csv\)\. A fully controlled sweep at a fixed6060\-term budget was attempted and abandoned: calibration on a500500\-sequence slice with instrumented CPU timing gives16121612rows/hour wall\-clock, projecting12\.412\.4hours per configuration for20,00020\{,\}000sequences, which exceeded our compute budget once two encodings were required\. An earlier estimate of∼32\\sim 32hours was discarded as unreliable\. This is the single most valuable extension of the present work\.

Corpus\.The6161\-sequence classical corpus is hand\-labelled, not sampled, because ground\-truth class membership is the independent variable in §§[5](https://arxiv.org/html/2608.29411#S5)–[6](https://arxiv.org/html/2608.29411#S6)\. §[8](https://arxiv.org/html/2608.29411#S8)shows the cost of this directly: curating for clean class membership removes the regime that dominates the wild database\.

Hypothesis class\.ℋ\\mathcal\{H\}is holonomic withr≤6r\\leq 6,d≤4d\\leq 4\. A richer class—piecewise definitions, general programs, transcendental closed forms—could show revision where we see none\. §[4](https://arxiv.org/html/2608.29411#S4)is a statement about MDL overℋ\\mathcal\{H\}, not about induction in general\.

Encoding\.L⁡\(H\)L\(H\)depends on the universal code, and on whether operators with singular leading coefficients are admitted\. The paper reports the shipped default,strict\_leading=False\(singular leading coefficients allowed, charged viasingular\_terms\)\. The stricter encodingstrict\_leading=Trueis released alongside it inresults/ablation\_encoding\.csv\. Headline figures are invariant across the two—41/4641/46exact, MAE0\.110\.11, two structural revisers, Fibonaccind=7n\_\{d\}=7—but several secondary figures move: correlations ofndn\_\{d\}withL⁡\(H∗\)L\(H^\{\*\}\)and growth, meanndn\_\{d\}and meanL⁡\(H∗\)L\(H^\{\*\}\)withinpoly, reviser identity \(cubes/square\-pyramidal under the default; triangular/oblong under the strict encoding\), the unplanted deception rate \(21\.8%21\.8\\%default vs14\.3%14\.3\\%understrict\_leading=True; seeresults/deception\_random\_strict\.csv\), and the planted peak\-ρ\\rhocurve\. An earlier draft claimed a code change “could shiftn×n\_\{\\times\}, though notnidn\_\{\\mathrm\{id\}\}”; this is too strong, since the selected\(r,d\)\(r,d\)can itself change\.

A negative result on optimisation\.Skipping the re\-solve when the standing hypothesis still annihilates the new term is*not*sound: under the default encoding it removes both structural revisions \(cubes A000578 and square pyramidal A000330 fall from one revision each to zero\)\. The cheapest hypothesis is sometimes not the incumbent even when the incumbent still fits, so the full re\-solve cannot be elided\.

LLM evaluation\.Sixty sequences across three models is a small sample,12/18012/180calls failed, and the “revising” stratum is under\-analysed relative to the other two\. Recognition is self\-reported and may be unreliable\. The inverted\-confabulation direction is consistent across all three models; the magnitude is not, and should not be treated as a stable constant\.

## 12Conclusion

We set out to measure the dynamics of symbolic induction, and the measurement kept correcting us\. On a labelled classical corpus the trajectory is a single jump whose location is a count of operator parameters, invariant to the magnitude of the data\. That clean picture does not survive contact with the full OEIS: structural revision is an order of magnitude more common, and a third regime appears that the curated corpus could not produce once\. Roughly nine in ten sequences that fit a recurrence on some prefix fit none at full length—the learner acquires a theory, loses it, and never recovers\.

The same instrument, turned on LLMs, refuted our hypothesis and replaced it with a better one\. Models do not confabulate where no theory exists; they hedge, and correctly\. They confabulate where a theory does exist, because on that stratum they are retrieving rather than inducing, and retrieval on a public dataset is confident by construction\. The difficulty gradient of an OEIS benchmark therefore partly tracks fame rather than information content\. Description length offers a difficulty signal that does not: exactly computable, independent of term magnitude, and immune to having seen the answer before\.

#### Reproducibility\.

#### Acknowledgements\.

AI assistance \(Claude, Cursor\) was used for implementation, experiment execution, and drafting\. All experimental design decisions, verification of results, and final claims are the author’s\.

## References

- \[1\]Andris Ambainis, Sanjay Jain, and Arun Sharma\.Ordinal mind change complexity of language identification\.*Theoretical Computer Science*, 220\(2\):323–343, 1999\.
- \[2\]François Chollet\.On the measure of intelligence\.*arXiv preprint arXiv:1911\.01547*, 2019\.
- \[3\]Miles Cranmer\.Interpretable machine learning for science with PySR and SymbolicRegression\.jl\.*arXiv preprint arXiv:2305\.01582*, 2023\.
- \[4\]Stéphane d’Ascoli, Pierre\-Alexandre Kamienny, Guillaume Lample, and François Charton\.Deep symbolic regression for recurrent sequences\.In*Proceedings of the 39th International Conference on Machine Learning \(ICML\)*, volume 162 of*PMLR*, 2022\.
- \[5\]Peter Elias\.Universal codeword sets and representations of the integers\.*IEEE Transactions on Information Theory*, 21\(2\):194–203, 1975\.
- \[6\]Kevin Ellis, Catherine Wong, Maxwell Nye, et al\.DreamCoder: Bootstrapping inductive program synthesis with wake\-sleep library learning\.*Proceedings of PLDI*, 2021\.
- \[7\]Rūsiņš Freivalds and Carl H\. Smith\.On the role of procrastination for machine learning\.*Information and Computation*, 107\(2\):237–271, 1993\.
- \[8\]Thibault Gauthier, Miroslav Olšák, and Josef Urban\.Alien coding\.*International Journal of Approximate Reasoning*, 2023\.
- \[9\]E\. Mark Gold\.Language identification in the limit\.*Information and Control*, 10\(5\):447–474, 1967\.
- \[10\]Peter D\. Grünwald\.*The Minimum Description Length Principle*\.MIT Press, 2007\.
- \[11\]Manuel Kauers\.Guessing handbook\.Technical Report 09\-07, RISC, Johannes Kepler University Linz, 2009\.
- \[12\]Manuel Kauers, Maximilian Jaroschek, and Fredrik Johansson\.Ore polynomials in Sage\.In*Computer Algebra and Polynomials*, volume 8942 of*Lecture Notes in Computer Science*, pages 105–125, 2015\.
- \[13\]James L\. Massey\.Shift\-register synthesis and BCH decoding\.*IEEE Transactions on Information Theory*, 15\(1\):122–127, 1969\.
- \[14\]Harald Niederreiter\.The linear complexity profile and the jump complexity of keystream sequences\.In*Advances in Cryptology — EUROCRYPT ’90*, volume 473 of*Lecture Notes in Computer Science*, pages 174–188, 1990\.
- \[15\]OEIS Foundation Inc\.The on\-line encyclopedia of integer sequences\.[https://oeis\.org](https://oeis.org/), 2026\.
- \[16\]Daniel O’Malley, Manish Bhattarai, Javier Santos, et al\.Benchmarking large language models with integer sequence generation tasks\.*arXiv preprint arXiv:2411\.04372*, 2024\.
- \[17\]Jan Poland and Marcus Hutter\.Asymptotics of discrete MDL for online prediction\.*IEEE Transactions on Information Theory*, 51\(11\):3780–3795, 2005\.
- \[18\]Jorma Rissanen\.Modeling by shortest data description\.*Automatica*, 14\(5\):465–471, 1978\.
- \[19\]Rainer A\. Rueppel\.*Analysis and Design of Stream Ciphers*\.Springer, 1986\.
- \[20\]Bruno Salvy and Paul Zimmermann\.Gfun: A Maple package for the manipulation of generating and holonomic functions in one variable\.*ACM Transactions on Mathematical Software*, 20\(2\):163–177, 1994\.
- \[21\]Jürgen Schmidhuber\.Driven by compression progress: A simple principle explains essential aspects of subjective beauty, novelty, surprise, interestingness, attention, curiosity, creativity, art, science, music, jokes\.In*Anticipatory Behavior in Adaptive Learning Systems*, volume 5499 of*Lecture Notes in Computer Science*, pages 48–76, 2009\.
- \[22\]Michael Schmidt and Hod Lipson\.Distilling free\-form natural laws from experimental data\.*Science*, 324\(5923\):81–85, 2009\.
- \[23\]Richard P\. Stanley\.Differentiably finite power series\.*European Journal of Combinatorics*, 1\(2\):175–188, 1980\.
- \[24\]Silviu\-Marian Udrescu and Max Tegmark\.AI Feynman: A physics\-inspired method for symbolic regression\.*Science Advances*, 6\(16\), 2020\.
- \[25\]Muzhong Wang and James L\. Massey\.The characterization of all binary sequences with perfect linear complexity profiles\.In*Advances in Cryptology — EUROCRYPT ’86*, 1986\.
- \[26\]Doron Zeilberger\.A holonomic systems approach to special functions identities\.*Journal of Computational and Applied Mathematics*, 32\(3\):321–368, 1990\.

## Appendix ACorpus

Table 7:Corpus summary by ground\-truth class\.\|C\|\|C\|is class size, “fitted” the number for which a holonomic operator was found,λN\\lambda\_\{N\}the final compression ratio, and “revisions” the total structural revisions\.Figure 6:MDL curves for representative sequences, three per ground\-truth class\. Solid: the MDL codelengthL⁡\(n\)L\(n\)\. Dashed: the verbatim costLlit​\(n\)L\_\{\\mathrm\{lit\}\}\(n\)\. Dotted vertical: the discovery pointndn\_\{d\}\. The vertical axis is logarithmic\. Non\-holonomic sequences \(rightmost column\) never separate from the verbatim cost, which is what having no theory looks like\.
## Appendix BThe linear complexity profile baseline

Because the linear complexity profile is the closest existing analogue \(§[2](https://arxiv.org/html/2608.29411#S2)\), we compute it on the same corpus by reducing each sequence mod22and running Berlekamp–Massey\. The final profile value separatesnonh\(mean11\.2011\.20\) from the holonomic classes \(means1\.801\.80,1\.941\.94,5\.935\.93\) with one\-way ANOVAF=9\.81F=9\.81,p<0\.001p<0\.001\. However it does not distinguishpolyfromcfinat all \(1\.801\.80vs1\.941\.94\), because reduction mod22discards precisely the coefficient and magnitude structure that separates them\. The LCP is therefore a coarse detector of holonomy in this domain, not a substitute for the MDL spectrum—consistent with its design for binary keystreams rather than unbounded integer sequences\.