Source-linked AI summary
Where Induction Runs Out: Description-Length Difficulty and the Memorisation Gap in Integer-Sequence Benchmarks
Sabilashan Ganeshan
TL;DR
Integer sequences are increasingly used to test mathematical reasoning in language models, but what makes one sequence difficult is unclear. The paper tracks an exactly computable MDL learner over holonomic recurrences and finds a large prefix-fit/full-length-fit gap, while model errors cluster in the easy stratum. It argues that OEIS benchmarks partly measure recognition and that MDL offers a magnitude-independent difficulty signal.
Problem
Integer-sequence benchmarks are widely used for language-model mathematical reasoning, but it is unclear what makes one sequence harder than another.
Source: §1 · p. 1Method
The paper applies two-part MDL over holonomic recurrences to every sequence prefix, using an exactly computable reference learner.
Source: §1 · p. 1Results
89.98% of sequences that fit a recurrence on some prefix fit none at full length; across MDL strata, confident model errors concentrate on easy sequences, while models hedge where MDL reports no theory.
Source: §1 · p. 2, §12 · p. 12Takeaways & Limitations
OEIS-derived benchmarks partly measure memorisation, while MDL provides a cheap difficulty signal that is independent of term magnitude and cannot be inflated by prior exposure.
Source: §1 · p. 2, §12 · p. 12The reference class is holonomic with r ≤ 6 and d ≤ 4; richer classes could show revisions absent under this class.
Source: §11 · p. 10
Abstract
from arXiv · showhide
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.
1 Introduction
Integer sequences offer checkable reasoning benchmarks, but it is unclear what makes one sequence harder than another. The paper tracks a two-part MDL learner over holonomic recurrences at every prefix and uses its difficulty measure to audit what benchmarks capture.
1 Introduction
- The reference learner uses two-part MDL over holonomic recurrences at every prefix, with exact computation by linear algebra over Q rather than a search heuristic.Source: §1 · p. 1
2 Related work
- The revision spectrum tracks successive hypothesis changes, extending endpoint-focused work on final expressions or program size; related measures include LFSR profiles [13] and mind-change complexity.The paper also situates its trajectory measurement against MDL stabilization theory and symbolic-regression or sequence-induction work.Source: §1 · p. 1, §2 · p. 2
1 Introduction
- Discovery point is predicted by an order-and-degree identifiability bound: exact in 89% of the classical corpus and within ±1 in 100%, versus MAE 3.20 for a compression-based predictor.Scaling over twelve orders of magnitude leaves discovery point unchanged because magnitude inflates hypothesis and literal codes equally.Source: §1 · p. 2
- 89.98% of sequences that fit a recurrence on some prefix fit none at full length, a regime absent from the curated classical corpus.The paper calls this the wilderness.Source: §1 · p. 2
- Evaluating three language models refutes the preregistered hypothesis: confident errors concentrate on the easy stratum, where apparent competence reflects OEIS recognition rather than induction.Source: §1 · p. 2
- MDL difficulty is cheap to compute, independent of term magnitude, and cannot be inflated by memorisation as accuracy on a public dataset can.Source: §1 · p. 2
3 Setup
The setup defines a two-part MDL learner whose codelength is evaluated on successive sequence prefixes, then measures its trajectory on a generated, labelled classical corpus. The recurrence class and exact search procedure make the reference learner computable without a heuristic search.
3.1 Codes
- Prefix-free codes make the two-part description a genuine codelength; natural numbers use Elias gamma codes, and verbatim storage keeps the codelength finite even when no recurrence fits.Source: §3.1 · p. 3
3.2 Hypothesis class
- The hypothesis class encodes holonomic operators with integer coefficients and the initial terms needed to run each recurrence; exact nullspace computation over Q finds candidates, with a two-equation slack guard.For Fibonacci, the stated recurrence and initial terms yield L(H) = 22 bits.Source: §3.2 · pp. 3–4
3.3 The revision spectrum
- The revision spectrum records prefix-to-prefix MDL changes, normalized by the arriving term’s verbatim cost; discovery is the first prefix where structure beats literal storage, and stabilization begins when the selected hypothesis stops changing.A normalized value of 1 means nothing was learned; 0 means the standing hypothesis implied the term for free.Source: §3.3 · p. 4
3.4 Corpus
- The 61-sequence classical corpus has 34 terms per sequence and four ground-truth classes; it was generated and labelled because OEIS lacks the class labels needed as experimental ground truth.The pipeline also runs unchanged on the OEIS stripped dump.Source: §3.4 · p. 4
4 Revision is rare, and rarer than it looks
MDL rarely revises on the classical corpus because interpolating recurrences cost more than the data they explain. At OEIS scale, the revision rate is higher but depends on the term budget and on counting only sequences with a full-length operator.
Classical corpus
- On the classical corpus, only 2 of 61 sequences revise, and structural revisions are overwhelmingly single events rather than cascades.The two cases are the cubes and square pyramidal numbers; all others either find and retain an operator or never find one.Source: §4 · pp. 4–5
Why revision is rare
- MDL rejects interpolating recurrences because their free parameters cost more bits than the data, so codelength binds before the validation guard.Even when the over-determination slack permits exactly determined or under-determined fits, the result barely changes.Source: §4 · pp. 4–5
- Table 2 shows that the identifiability bound alone accounts for discovery points, while the compression threshold alone does not.The paper concludes that repeated churning is not characteristic of description-length induction under this setup.Source: Table 2 · p. 5, §4 · p. 5
At OEIS scale
- 315 of 2,780 fully holonomic sequences (11.3%) revise at a fixed 30-term budget, versus 3.3% on the classical corpus.The OEIS rate depends on available terms; reported mixed-length bins range from 4.2% to 12.0%, so cross-study comparisons must fix the term budget.Source: §4 · p. 5
- A sequence counts as holonomic for the OEIS revision rate only when an operator is found at full length; prefix-only fits are excluded.Combining prefix-only fits with this denominator would inflate the revision rate roughly fivefold.Source: §4 · p. 5
5 Discovery is identification-limited
Discovery is governed by when a recurrence can be identified, not by when it becomes cheaper than verbatim storage. This law holds tightly for non-revisers, but fails for sequences that revise.
Two thresholds
- The discovery point is predicted as max(nid, n×), where nid is the identifiability threshold and n× the profitability threshold.A sequence is identification-limited when nid ≥ n×, and compression-limited otherwise.Source: §5 · p. 5
Classical corpus
- The identifiability bound predicts discovery exactly for 41/46 fittable classical sequences and within ±1 for all 46, with MAE 0.11.It matches the combined identifiability-and-profitability prediction because every fittable sequence is identification-limited.Source: §5 · p. 5
The dichotomy at scale
- Among OEIS non-revisers, identifiability predicts discovery with 91.9% exact accuracy and MAE 0.11, while it fails completely among revisers.Table 3 conditions on the 2,780 sequences with a full-length operator at a fixed 30-term budget; a deceptive prefix is the named exception to exact prediction among revisers.Source: Table 3 · p. 6, §5 · p. 6
What determines discovery
- Discovery point correlates with structural size (r = +0.85), but not growth rate (r = −0.007).Mean discovery points differ across CFIN, PREC, and POLY; the reported ANOVA gives F = 4.70, p = 0.014, with separation driven mainly by CFIN.Source: §5 · p. 6
- Fittability separates the sequence classes: all 46 holonomic sequences are fitted, while all 15 non-holonomic sequences are not.POLY and PREC overlap substantially.Source: §5 · p. 6
6 Growth invariance
Scaling sequence values does not change when MDL discovers a formula: magnitude raises the cost of both the hypothesis and the literal data. The same lack of alphabet-size dependence appears across the tested periodic sequences.
Observed invariance
- Factorials, Fibonacci numbers, and naturals all have nd = 7 despite differing verbatim costs by an order of magnitude.For the first 34 terms, the verbatim costs are 3519 bits for factorials and 315 bits for naturals.Source: §6 · p. 6
Control A
- Across Fibonacci scalings spanning twelve orders of magnitude, nd remains 7 and the compression ratio λ remains 0.029.The literal cost rises from 759 to 3377 bits as the scale increases.Source: §6 · p. 6
Why magnitude does not matter
- Scaling multiplies the cost of a hypothesis’s initial conditions and the literal data by the same factor, so magnitude cancels from the comparison.For the largest scaling, L(H) rises from 22 to 98 bits while Llit rises from 759 to 3377 bits.Source: §6 · p. 6
Control B
- For periodic sequences across 24 tested operator-period and alphabet-size combinations, nd = nid = 2p*+3 exactly, with no dependence on alphabet size A.The period p* is the true period of the generated sequence; the compression-limited regime does not appear in these tests.Source: §6 · p. 7
7 Deceptive prefixes
A deceptive prefix is a stretch of terms that supports a cheaper but incorrect hypothesis than the rule governing the full sequence. Such prefixes produce revisions, with a characteristic sequence of spurious fit, refutation, wilderness, and eventual discovery in the constructed example.
Definition and mechanism
- A deceptive prefix of depth m is one whose first m terms fit a strictly cheaper hypothesis than the one governing the whole sequence.The paper identifies deception as the only mechanism it finds that produces structural revisions.Source: §7 · p. 7
Constructed example
- In the constructed D3 example, the learner moves from a spurious period-2 fit through refutation and wilderness to true discovery at n = 17, then remains stable.During wilderness, it holds no theory and absorbs each term at full cost.Source: §7 · p. 7
Sweeping the construction
- For the constructed family, spurious fit occurs at n = 7, refutation at n = p + 1, and true discovery at n = 2p + 3, matching identifiability for all tested periods.The tested periods are p ∈ {7, 9, 11, 13, 15}.Source: §7 · p. 7
Revision magnitude
- Peak revision magnitude plateaus at 11.0 for p ≥13, and the authors report no mechanism for the plateau.They interpret larger spikes as reflecting a greater cost gap between the refuted theory and its replacement.Source: §7 · p. 7
Unplanted deception
- Among random periodic binary sequences, revisions occur in 21.8% of 440 cases overall, generally rising with period but dipping at p = 11.Reported rates include 0% for p ≤ 4, 7.5% at p = 5, 27.5% at p = 6, 35% at p = 10, and 45% at p = 12.Source: §7 · p. 7
8 The wilderness
At OEIS scale, many sequences fit a recurrence on a prefix but none at full length; this wilderness is not mainly an artifact of limited term availability. It matters for benchmarks because an early plausible fit can have no corresponding right answer.
8 The wilderness
- The wilderness is the regime where a sequence fits a recurrence on some prefix but fits none at full length.Unlike the classical corpus’s fitted and never-fitted cases, OEIS-scale data contains a dominant third category.Source: §8 · p. 7
- Only 1.5% of the prefix-fit cases are explained by truncation; roughly nine in ten remain non-extensible even with ample terms.The authors reran the guesser using every available term, including for sequences with at least 40 terms.Source: §8 · p. 7
- For benchmark construction, these sequences offer a plausible wrong answer early but no right answer at all.The authors identify this as the most consequential benchmark regime.Source: §8 · p. 8
9 What OEIS benchmarks measure
In an evaluation of three language models across MDL difficulty regimes, models hedge when the learner finds no full-length theory, while confident errors concentrate on easy sequences. The paper connects that pattern to sequence recognition, making apparent benchmark competence partly a measure of memorisation rather than induction.
9 What OEIS benchmarks measure
- The evaluation stratified 60 sequences into clean, revising, and wilderness regimes and tested Claude Sonnet 4.5, GPT-4o, and Llama 3.3 70B.Each model received the first 20 terms and was asked for the next three terms, a formula or NO_FORMULA_FOUND, confidence, and whether it recognized the sequence.Source: §9 · p. 8
- In the wilderness, abstention was 64.7% for Claude, 95.0% for GPT-4o, and 89.5% for Llama; all three models hedged appropriately.Mean stated confidence was 3.18, 2.45, and 2.68, respectively.Source: §9 · p. 8
- For every model, confabulation rates were higher on the easy stratum than on the hard stratum.Confabulation is defined as stated confidence of at least 4 together with a wrong continuation.Source: §9 · p. 8
- Recognition effects varied by model: Llama’s clean-stratum accuracy tracked reported recognition, while Claude retained accuracy without recognition and GPT-4o’s was essentially unchanged.The paper describes Llama as retrieving OEIS entries rather than inferring recurrences; Claude’s accuracy without recognition was 4/7.Source: §9 · p. 9
- A tractable OEIS benchmark stratum answered by retrieval measures memorisation, and its difficulty gradient can track sequence familiarity rather than induction difficulty.The paper presents MDL as a sequence-derived difficulty signal that is unaffected by term magnitude and cannot be inflated by prior recognition.Source: §9 · p. 9
10 Recommendations for benchmark construction
The recommendations pair MDL-based difficulty reporting with recognition-conditioned accuracy and deliberate sampling of hard regimes. The limitations qualify the corpus, hypothesis class, encoding, compute budget, and language-model evaluation.
10 Recommendations for benchmark construction
- Report operator order and degree: under MDL, n_id=(r+1)(d+1)+s+r nearly predicts how many terms are needed to infer a rule.The bound is cheap to compute and is exactly right in 89% of the labelled classical corpus and within ±1 in 100%.Source: §10 · p. 9
- Condition accuracy on recognition: Llama’s clean-stratum accuracy drops from 25% to 0% after recognised items are removed.A single accuracy figure cannot distinguish induction from retrieval in a public dataset.Source: §10 · pp. 9–10
- Sample hard regimes deliberately: deceptive-prefix cases are rare, and wilderness means a prefix fit is refuted with no replacement.Wilderness cases test whether models can decline; all three models in this evaluation did so.Source: §10 · p. 10, Figure 4 · p. 10
11 Limitations
- The evaluation has bounded scope: the OEIS headline uses 30 terms, while the 60-sequence, three-model study had 12/180 failed calls and unreliable self-reported recognition.The attempted fixed 60-term OEIS sweep was abandoned because its projected runtime exceeded the compute budget.Source: §11 · pp. 10–11
- The classical corpus is hand-labelled rather than sampled, and its holonomic class is limited to r≤6 and d≤4, excluding regimes a richer class may reveal.The curated corpus’s clean-class selection removes the wilderness regime that dominates the wild database.Source: §11 · p. 10
- Encoding choices leave headline figures invariant across the two released encodings, but several secondary results and even selected (r,d) can change.The encoding depends on the universal code and on whether operators with singular leading coefficients are allowed.Source: §11 · p. 11
- Skipping the full re-solve is unsound: it removes structural revisions for the cubes and square-pyramidal sequences even when the incumbent still fits.The cheapest hypothesis is sometimes not the incumbent hypothesis that continues to fit.Source: §11 · p. 11
12 Conclusion
At OEIS scale, the clean, parameter-count picture from the curated corpus breaks: many prefix-fitted sequences lose their recurrence. In the language-model audit, confident errors cluster on the easy stratum, while models hedge in the wilderness.
12 Conclusion
- Structural revision is an order of magnitude more common at OEIS scale, and 89.98% of sequences that fit a recurrence on some prefix fit none at full length.The learner acquires a theory, loses it, and never recovers.Source: §12 · pp. 11–12
- Models hedge where no theory exists, while confident errors concentrate where apparent competence tracks OEIS recognition rather than induction.The authors conclude that OEIS benchmark difficulty partly tracks fame rather than information content.Source: §12 · p. 12
- The authors release the code, corpus generator, model responses, and scripts for regenerating each number, table, and figure.The classical pipeline runs in under two minutes on a laptop without a GPU.Source: §12 · p. 12
A Corpus
The corpus summary describes class sizes, fit counts, compression, and revisions; the linear-complexity baseline detects holonomy coarsely but misses a distinction between two holonomic classes.
A Corpus
- Table 7 summarizes each ground-truth class by class size, number fitted, final compression ratio λN, and total structural revisions.Source: Table 7 · p. 14
- Figure 6 shows three representative MDL curves per ground-truth class; non-holonomic sequences never separate from the verbatim cost.The vertical axis is logarithmic.Source: Figure 6 · p. 14
B The linear complexity profile baseline
- The LCP final profile value separates NONH (mean 11.20) from the holonomic classes (means 1.80, 1.94, 5.93), but not POLY from CFIN (1.80 vs 1.94).It is therefore a coarse detector of holonomy in this domain, not a substitute for the MDL spectrum.Source: B The linear complexity profile baseline · p. 14