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

Sabilashan Ganeshan

cs.LGAug 29, 2026

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

Authors: Sabilashan Ganeshan

Organizations: Independent Researcher

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 point nd, 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 leaves nd 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: across 20,000 OEIS sequences, 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 and data are released.

Figures & tables

symbol	meaning
$n$	prefix length
$r$	operator order
$d$	degree of the coefficient polynomials
$s$	over-determination slack
$c_{ij}$	integer coefficient of $n^{j}$ in $p_{i}$
$L(n)$	MDL codelength of the prefix of length $n$

Table 1: Notation used throughout.

predictor	exact	within $\pm 1$	MAE
$\max(n_{\rm id},n_{\times})$	41/46	46/46	0.11
$n_{\rm id}$ alone	41/46	46/46	0.11
$n_{\times}$ alone	0/46	0/46	3.20
corpus mean	0/46	11/46	1.41

Table 2: Prediction of the discovery point

n_{d}

. The identifiability bound alone accounts for the data; the compression threshold alone does not.

	$n$	exact	within $\pm 1$	MAE
never revises	$2465$	$91.9\%$	$99.0\%$	$0.11$
revises	$315$	$0.0\%$	$48.6\%$	$4.37$

Table 3: Accuracy of the identifiability prediction

n_{d}=n_{\mathrm{id}}

on the

2780

OEIS sequences with a full-length operator (fixed

30

-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.

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 leaves

n_{d}

and the compression ratio

\lambda

exactly unchanged.

Figure 2: The five phases of a revision spectrum on the planted deceptive sequence

D_{3}

(true period

7

). Top: MDL codelength

L(n)

against the verbatim cost

L_{\mathrm{lit}}(n)

, shaded by the phase holding at

n

—literal (grey), spurious period-2 fit (blue), wilderness (orange), stable (green). Bottom: the normalized revision

\rho(n)

. Since

\rho(n)

is indexed by its source prefix length, the revision at

n

is what installs the state at

n{+}1

; the shading in the lower panel is shifted one step left accordingly, so each spike is coloured by the phase it leads into.

Figure 3: Deceptive prefixes in the planted family

D_{j}

and in random periodic sequences. (a) The three landmarks—spurious fit, refutation, and recovery of the true operator—scale exactly with the true period

p

. (b) Peak revision magnitude

\max|\rho|

grows through

p=11

and then plateaus at

11.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.

class	count	share
operator found at full length (truncation artefact)	$29$	$1.54\%$
no operator, $\geq 40$ terms available (genuine)	$1698$	$89.98\%$
no operator, $<40$ terms (undetermined)	$160$	$8.48\%$
total	$1887$	$100\%$

Table 4: Truncation audit of the

1887

OEIS sequences that fit a recurrence on some prefix but none at the

30

-term budget. Each was re-run on every term the database holds. Truncation accounts for

1.54\%

; in roughly nine cases in ten the prefix fit is genuinely not extensible even with

\geq 40

terms.

Figure 4: The three MDL strata used to stratify the language-model evaluation. In each panel the solid line is the MDL codelength

L(n)

and the dashed line the verbatim cost

L_{\mathrm{lit}}(n)

; the dotted vertical marks the discovery point

n_{d}

, where structure first beats verbatim storage. Clean : an operator is found once and held, so

L

drops at

n_{d}

and stays flat. Revising : the operator is later refuted and replaced by a costlier one, so

L

returns towards the verbatim cost and then settles at a new, higher level. Wilderness : the prefix fit is refuted and nothing replaces it, so

L

rejoins

L_{\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.

model	clean (has formula)	wilderness (none)
Claude Sonnet 4.5	$3/17$ ( $17.6\%$ )	$2/17$ ( $11.8\%$ )
GPT-4o	$9/20$ ( $45.0\%$ )	$1/20$ ( $5.0\%$ )
Llama 3.3 70B	$13/20$ ( $65.0\%$ )	$4/19$ ( $21.1\%$ )

Table 5: Confabulation rate (stated confidence

\geq 4

together 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.

model	overall	recognised	not recognised
Claude Sonnet 4.5	$12/17$ ( $70.6\%$ )	$8/10$ ( $80.0\%$ )	$4/7$ ( $57.1\%$ )
GPT-4o	$8/20$ ( $40.0\%$ )	$4/11$ ( $36.4\%$ )	$4/9$ ( $44.4\%$ )
Llama 3.3 70B	$5/20$ ( $25.0\%$ )	$5/6$ ( $83.3\%$ )	$0/14$ ( $0.0\%$ )

Table 6: Clean-stratum exact accuracy split by self-reported recognition. Llama’s performance is entirely recall (

5/6

on sequences it recognises and

0/14

on those it does not), while Claude retains accuracy without recognition and GPT-4o is essentially unaffected. Recognition is self-reported and may be unreliable.

Figure 5: LLM behaviour by MDL stratum. (a) Confabulation rate (stated confidence

\geq 4

with 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 scores

0/14

without 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 fixed

0

–

100

scale.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

class	$\|C\|$	fitted	mean $n_{d}$	range	mean $L(H^{*})$	mean $\lambda_{N}$	revisions
POLY	15	15	8.5	7–13	33	0.059	2
CFIN	16	16	7.2	6–9	24	0.024	0
PREC	15	15	8.7	7–13	34	0.014	0
NONH	15	0	–	–	–	1.000	0
all	61	46	8.1	6–13	30	0.270	2

Appendix

Table 7: Corpus summary by ground-truth class.

|C|

is class size, “fitted” the number for which a holonomic operator was found,

\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 codelength

L(n)

. Dashed: the verbatim cost

L_{\mathrm{lit}}(n)

. Dotted vertical: the discovery point

n_{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.

Explore similar work

OEIS Open: How many conjectures can language models turn into theorems?
Aug 12, 2026Tom AdamczewskiLLM Evaluation Automated Theorem Proving
Epoch AI
Too long; didn't solve
Apr 8, 2026Lucía M. Cabrera, Isaac Saxton-Knight, Jocelyn D'ArcyMathematical Reasoning Benchmarks LLM Mathematical Reasoning
Instituto Balseiro · Poindexter Labs
LANTERN: Illuminating Hidden Mathematical Knowledge in Language Models
Sep 26, 2026Pavel Tikhonov, Elena Tutubalina, Ivan Oseledets +2Large Language Model-Guided Scientific Discovery

Aug 12, 2026J/K move · Enter open · S save

OEIS Open: How many conjectures can language models turn into theorems?

Tom Adamczewski

Epoch AI

LLM Evaluation Automated Theorem Proving Mathematical Reasoning

Open paper AskPDF arXiv

We construct OEIS Open, a benchmark based on 492 open mathematical conjectures from the OEIS, formalized in Lean by Tsoukalas et al. Whereas these conjectures had previously been attempted only with a bespoke agent, our open-source evaluation code runs any generic language model (LM) against them, and is secure against LM cheating attempts. We find that LMs equipped with a minimal set of tools resolve 147 of these conjectures with a budget of $50 per attempt, scoring 30% on OEIS Open. OEIS Open Lite is a random subset of 100 conjectures for cheaper evaluation. When evaluated with a budget of $200 per attempt, the best current LM scores 44% on OEIS Open Lite. Giving LMs access to the mathematics literature via 476,000 papers from arXiv did not increase performance on OEIS Open Lite, and nor did using more sophisticated agent loops. The conjectures covered in this work are of uncertain mathematical significance, and most have likely received little previous attention. Nevertheless, our results show that LMs can resolve open research conjectures autonomously and at modest cost.

Abstract

Explore similar work

OEIS Open: How many conjectures can language models turn into theorems?

Too long; didn't solve

LANTERN: Illuminating Hidden Mathematical Knowledge in Language Models