arXiv:2608.29411v1 cs.LG

귀납이 끊기는 지점: 정수 수열 벤치마크에서 기술 길이(description-length) 난이도와 암기(memorisation) 격차

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

Sabilashan Ganeshan

제출 2026-08-29

한국어 초록

On-Line Encyclopedia of Integer Sequences(OEIS)의 정수 수열은 언어 모델의 수학적 추론 벤치마크로 점점 더 많이 쓰이고 있다. 우리는 이러한 벤치마크가 실제로 무엇을 측정하는지, 정확히 계산 가능한 참조 학습기—P-recursive(holonomic) 점화식 클래스에 대한 2-part 최소 기술 길이(minimum description length, MDL)를 항이 들어올 때마다 수열의 각 접두 구간에서 평가—를 사용해 묻는다. 세 가지 결과가 따른다. 첫째, MDL 난이도는 매개변수 개수이다. discovery point nd, 즉 그대로 저장(verbatim storage)보다 기호적 가설(symbolic hypothesis)이 이기기 시작하는 첫 접두 길이는, 선택된 연산자(operator)의 차수(order)와 degree에 대한 조합론적 식별 가능(identifiability) 상한으로 거의 정확히 예측된다. 이는 항의 크기에 불변이다. Fibonacci 수열의 크기를 12자릿수 스케일로 바꿔도 nd는 변하지 않는데, 가설이 자체 초기 조건을 인코딩해야 하고 크기 효과가 상쇄되기 때문이다. 둘째, 규모가 커지면 학습기는 우리가 큐레이션한 코퍼스에서는 단 한 번도 만들 수 없었던 영역을 보인다. OEIS 수열 20,000개 가운데, 어떤 접두 구간에서는 점화식(recurrence)에 맞지만 전체 길이에서는 맞지 않는 것이 89.98%이다. 우리는 이를 wilderness라 부른다—귀납(induction)이 이론을 얻었다가 잃고 다시는 회복하지 못한다. 셋째, 이러한 MDL 영역으로 계층화(stratified)한 수열에서 세 언어 모델을 평가한 결과, 사전 등록(pre-registered) 가설은 기각되었다. 모델은 MDL이 이론이 없다고 보고하는 곳에서 날조(confabulate)하지 않고, 적절히 hedge한다. 자신 있게 틀리는(confident errors) 경우는 반대로, 쉬운 층(easy stratum)에 집중되며, 겉보기 능력은 규칙의 귀납(induction)보다 수열 인식(recognition)을 따른다. 따라서 OEIS 기반 벤치마크는 상당 부분 암기(memorisation)를 측정하며, MDL은 현재 그들이 갖추지 못한 값싸고 오염(contamination) 없는 난이도 신호를 제공한다. 코드와 데이터를 공개한다.

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2608.29411v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.