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

Aug 12, 2026

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

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.

Tom Adamczewski

Epoch AI

LLM Evaluation Automated Theorem Proving Mathematical Reasoning

Ask PDF

Apr 8, 2026

Too long; didn't solve

Mathematical benchmarks consisting of a range of mathematics problems are widely used to evaluate the reasoning abilities of large language models, yet little is known about how their structural properties influence model behaviour. In this work, we investigate two structural length variables, prompt length and solution length, and analyse how they relate to model performance on a newly constructed adversarial dataset of expert-authored mathematics problems. We find that both prompt and solution lengths correlate positively with increased model failure across models. We also include a secondary, exploratory analysis of cross-model disagreement. Under a difficulty-adjusted normalised analysis, both variables retain weak negative associations with realised model separation, slightly stronger for prompt length. Overall, our main robust finding is that structural length is linked to empirical difficulty in this dataset.

Lucía M. Cabrera, Isaac Saxton-Knight, Jocelyn D'Arcy

Instituto Balseiro · Poindexter Labs

Mathematical Reasoning Benchmarks LLM Mathematical Reasoning LLM Evaluation

Ask PDF

Sep 26, 2026

LANTERN: Illuminating Hidden Mathematical Knowledge in Language Models

Language models can now prove theorems, but people still decide which problems to pursue. We ask whether a model's internal representations can help identify promising mathematical connections. We develop LANTERN, a fast, cost-efficient pipeline that uses a classifier over pretrained-model activations to rank candidate relations, followed by staged filtering, hypothesis generation, executable verification, and analytical checking. Applied to the On-Line Encyclopedia of Integer Sequences (OEIS), LANTERN ranked 50 million pairs among 10,000 frequently referenced sequences and produced 62 verified relations between pairs without an existing OEIS cross-reference. A content screen retained 13 relations worth presenting; nine of these are informative or insightful, including four which are entirely novel to the best of our knowledge: none appears in the OEIS or in our targeted literature search. The entire end-to-end process including classifier training, candidate ranking, filtering and verification took under 8 hours.

Pavel Tikhonov, Elena Tutubalina, Ivan Oseledets +2

Large Language Model-Guided Scientific Discovery

Ask PDF