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

• URL: http://arxiv.org/abs/2608.29411v1
• Date: Sat, 29 Aug 2026 19:25:31 GMT
• Title: Where Induction Runs Out: Description-Length Difficulty and the Memorisation Gap in Integer-Sequence Benchmarks
• Abstract summary: The On-Line Encyclopedia of Sequences (OEIS) are increasingly used to benchmark mathematical reasoning in language models.<n>We ask what such benchmarks actually measure, using an exactly computable reference learner.<n>Across 20,000 OEIS sequences, 89.98% of those that fit a recurrence on some prefix fit none at full length.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Wrong Prediction, Right Answer: Recovering Evidence from Collapsed LLM Sequence Scores [31.709549159768727]
  We observe a consistent readout gap across diverse reasoning benchmarks.<n> hidden-state probes successfully decode correct answers even when native sequence scoring completely collapses.<n>Our results show that many apparent zero-shot reasoning deficits are expression failures masking intact internal logic.
  arXiv  Detail & Related papers  (2026-08-31T16:43:55Z)
• Hypothesis Frontier: Verifier Guided LLM and Symbolic Search for First-Order Induction [0.0]
  First-order concept synthesis asks a system to infer one formula that classifies labeled objects consistently across several finite relational structures.<n>We introduce Hypothesis Frontier, a verifier-guided neurosymbolic framework that evaluates each LLM formula on every training object.
  arXiv  Detail & Related papers  (2026-08-11T12:13:35Z)
• How Much is Left? LLMs Linearly Encode Their Remaining Output Length [3.541590945326217]
  Large language models generate one token at a time, yet their responses show remarkably consistent length structure.<n>We ask whether the model carries an internal estimate of how much response remains.<n>We train minimal-capacity linear probes on frozen hidden states of three open-weight 7-8B models across seven completion-style datasets.
  arXiv  Detail & Related papers  (2026-07-06T16:56:04Z)
• DEL: Digit Entropy Loss for Numerical Learning of Large Language Models [63.37357414497361]
  Number prediction is a fundamental capability of large language models (LLMs) in mathematical problem-solving and code generation.<n>We present Digit Entropy Loss (DEL) for auto-regressive numerical learning.<n>Our formulation can incorporate integers, decimals, and decimal points, expanding the learning objective from a single digit to the floating-point number domain.
  arXiv  Detail & Related papers  (2026-05-19T18:18:59Z)
• Probing Structural Mathematical Reasoning in Language Models with Algebraic Trapdoors [0.0]
  We introduce a benchmark suite for evaluating structural mathematical reasoning in language models.<n>Each instance presents a finitely generated subgroup as a list of integer matrices.<n>We report empirical results across five representative reasoning traces from two state-of-the-art models.
  arXiv  Detail & Related papers  (2026-05-05T23:16:30Z)
• Prior Aware Memorization: An Efficient Metric for Distinguishing Memorization from Generalization in Large Language Models [9.915106680104268]
  Training data leakage from Large Language Models (LLMs) raises serious concerns related to privacy, security, and copyright compliance.<n>Existing approaches to measuring memorization often conflate these phenomena, labeling outputs as memorized even when they arise from generalization over common patterns.<n>This work introduces Prior-Aware Memorization, a theoretically grounded, lightweight and training-free criterion for identifying genuine memorization in LLMs.
  arXiv  Detail & Related papers  (2026-02-21T06:31:17Z)
• Primender Sequence: A Novel Mathematical Construct for Testing Symbolic Inference and AI Reasoning [0.0]
  Primender sequence is a novel integer sequence that combines classical primality with modular digit-based conditions.<n>We propose the sequence as a benchmark for evaluating the symbolic reasoning capabilities of Large Language Models.
  arXiv  Detail & Related papers  (2025-06-12T11:21:58Z)
• Demystifying Verbatim Memorization in Large Language Models [67.49068128909349]
  Large Language Models (LLMs) frequently memorize long sequences verbatim, often with serious legal and privacy implications. We develop a framework to study verbatim memorization in a controlled setting by continuing pre-training from Pythia checkpoints with injected sequences. We find that (1) non-trivial amounts of repetition are necessary for verbatim memorization to happen; (2) later (and presumably better) checkpoints are more likely to memorize verbatim sequences, even for out-of-distribution sequences.
  arXiv  Detail & Related papers  (2024-07-25T07:10:31Z)
• Language Model Cascades: Token-level uncertainty and beyond [65.38515344964647]
  Recent advances in language models (LMs) have led to significant improvements in quality on complex NLP tasks. Cascading offers a simple strategy to achieve more favorable cost-quality tradeoffs. We show that incorporating token-level uncertainty through learned post-hoc deferral rules can significantly outperform simple aggregation strategies.
  arXiv  Detail & Related papers  (2024-04-15T21:02:48Z)
• LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers [60.009969929857704]
  Logical reasoning is an important task for artificial intelligence with potential impacts on science, mathematics, and society. In this work, we reformulating such tasks as modular neurosymbolic programming, which we call LINC. We observe significant performance gains on FOLIO and a balanced subset of ProofWriter for three different models in nearly all experimental conditions we evaluate.
  arXiv  Detail & Related papers  (2023-10-23T17:58:40Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm. We first define an incomplete probable decoding algorithm which includes greedy search, top-$k$ sampling, and nucleus sampling. We then propose a non-monotonic self-terminating language model, which relaxes the constraint of monotonically increasing termination probability.
  arXiv  Detail & Related papers  (2022-10-03T00:28:44Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.