Probing Structural Mathematical Reasoning in Language Models with Algebraic Trapdoors

기술적 요약: 대수적 트랩도어를 활용한 언어 모델의 구조적 수학 추론 탐지

문제 제기
기존의 수학 추론 벤치마크 (예: GSM8K, MATH, ProofNet) 는 일반적으로 검증이 해결보다 어렵지 않은 대칭성을 보입니다. 이러한 대칭성은 계산 유창성을 선호하지만, 명명된 정리를 배포하고, 대수적 패턴을 인식하며, 적용 가능한 구조적 사전 지식을 식별하는 능력인 "구조적 추론"을 평가하지는 못합니다. 또한, 표준 점수 산정은 "잘못된 답을 고수하는 것"과 "정직하게 유보하는 것"을 혼동하여 둘 다 0 점 실패로 간주합니다.

본 논문은 $SL(3, \mathbb{Z})$ 군 내에서 암호학적 스타일의 검증자 - 증명자 비대칭성을 활용하여 이러한 대칭성을 깨도록 설계된 벤치마크 세트를 소개합니다. 핵심적인 도전 과제는 각 문제의 답이 "트랩도어" 데이터 $(N, K)$를 보유한 구성자 (constructor) 에게는 $O(1)$ 폐쇄형으로 계산 가능하지만, 이 데이터를 갖지 못한 해결자 (solver) 에게는 휴리스틱 구조 탐지 또는 알 수 없는 결정 가능성 (특히 $SL(3, \mathbb{Z})$에서의 멤버십 문제) 을 가진 알고리즘적 질문이라는 점입니다.

방법론
본 벤치마크는 비밀 쌍 $(N, K)$ (여기서 $K \subseteq SL(3, \mathbb{Z}/N)$) 로부터 생성된 유한 생성 부분군 $H \subseteq SL(3, \mathbb{Z})$를 생성하여 구성된 네 가지 문제 계열로 구성됩니다. 생성자들은 니켈슨 스램블링 (생성자를 깊게 중첩된 곱으로 재작성) 과 멘니케 전단 (shears) 을 사용하여 은폐되었으며, 그 결과 행렬 항은 $10^{40}$에 달합니다.

1. 계열 I (멤버십): 생성자와 후보 행렬이 주어졌을 때, 멤버십을 결정합니다. "YES" (명시적 단어) 또는 "NO" (mod-$p$ 축소) 에 대한 증명이 존재하지만, $SL(3, \mathbb{Z})$의 일반 멤버십 문제는 결정 불가능합니다.
2. 계열 II (리스트-소수 YES/NO): $(A, B)$가 생성한 부분군이 일련의 큰 소수 $p$에 대해 $SL(3, \mathbb{F}_p)$로 전사 (surject) 하는지 판단합니다. 답은 스미스 정규형 (Smith Normal Form) 과 같은 직교 구조를 탐지하는 데 의존하며, 이는 구성자에게는 $O(1)$이지만 해결자에게는 구조적 탐지가 필요합니다.
3. 계열 III (합동 확장 YES/NO): $H$가 합동 확장 $\pi^{-1}(K)$인지 판단합니다. "나쁜 소수"는 $K$가 진부분군인 $N$의 인수들입니다.
4. 계열 IV (지수): 정확한 지수 $[SL(3, \mathbb{Z}) : H]$를 출력하거나 "무한/알 수 없음"을 출력합니다. 이 계열은 세 가지 하위 계열을 포함합니다:
   • v1: $H = SL(3, \mathbb{Z})$ (지수 1). mod-$p$ 분석을 통해 일반적인 무한 지수 부분군과 구별할 수 없습니다.
   • v2: $H = \pi^{-1}(K)$ (유한 지수). 코커널은 계산 가능하지만, 커널 포함 여부는 멤버십 문제를 해결해야 합니다.
   • v3: $H = \langle g_1, g_2 \rangle \subset \Gamma(N)$ (성질 (T) 에 의해 무한 지수). 코커널만 추론하면 잘못된 유한 답이 나오며, 올바른 추론은 무한한 성질을 인식해야 합니다.

평가 설정
저자들은 최첨단 모델 두 개 (GPT Pro (사고) 및 Gemini) 를 평가했습니다. 핵심적으로, 프롬프트는 부분군이 유한 지수임을 단정하지 않습니다. 이 설계는 모델이 코커널 계산 (쉬움) 과 커널 포함 검증 (어려움/알 수 없음) 을 구별하도록 강요하여 "보정 테스트"를 생성합니다.

저자들은 4 가지 분류 점수 산정을 제안합니다:

1. 정답 고수 (Commit-correct): 올바른 구체적 답을 제시.
2. 오답 고수 (Commit-wrong): 잘못된 구체적 답을 제시.
3. 정답 유보 (Abstain-correct): 정답이 무한/알 수 없음 (v3) 일 때 "무한/알 수 없음"을 출력.
4. 오답 유보 (Abstain-wrong): 정답이 특정 정수 (v1, v2) 일 때 "무한/알 수 없음"을 출력.

주요 결과
본 논문은 다섯 가지 상세한 추론 흔적을 보고합니다:

• 구조적 추론 (계열 II 및 III): 두 모델 모두 구조적 탐지가 필요한 사례 (예: 맥클라클란 정리, 번사이드 정리, 또는 콕서터 표현식 식별) 를 성공적으로 해결했습니다.
  • Gemini는 명명된 정리 매칭에 의존하여 Coxeter 표현식 ($S_4$용) 을 인식하는 등 몇 초 만에 짧고 선언적인 응답을 생성했습니다.
  • GPT는 구성적 유도에 의존하여 교환자 항등식을 유도하고 행렬을 첫 번째 원리에서 인수분해하는 데 수 분에서 수 시간이 걸렸습니다.
• 보정 테스트 (계열 IV-v2, 인스턴스 X10):
  • GPT는 정답이 25 자리 정수인 인스턴스에 152 분을 보냈습니다. 코커널을 성공적으로 계산했지만, 명시적으로 커널 측 멤버십 질문을 병목 현상으로 인식했습니다. 구성적 검증 시도 (필요한 모든 전단을 인증하지 못함) 후, 계산된 상한에 고수하는 대신 "모르겠습니다 (DON'T KNOW)"로 유보했습니다. 이는 개방형 결정 가능성 경계에서의 보정된 메타인지를 보여줍니다.
  • Gemini는 추론 흔적을 생성하지 못했고, 수 분 후 내부 오류를 노출했습니다.
• SL(2, Z) 기준선 (계열 V):
  • 결정 가능한 $SL(2, \mathbb{Z})$ 기준선에서 테스트했을 때, GPT는 유한 대 무한 지수를 구별하기 위해 연분수, 스탈링 접이식, 라인데메이스터 - 슈라이어, 니켈슨 축소 등 전체 랭크 1 툴킷을 성공적으로 배포했습니다.
  • Gemini는 동일한 기준선에서 확장된 계산 시간 후 충돌하여 출력을 생성하지 못했습니다.

의의 및 주장
본 논문은 이 벤치마크가 표준 정답 키 점수 산정이 가리는 모델 행동의 4 가지 분류를 드러낸다고 주장합니다. 주요 기여점은 다음과 같습니다:

1. 보정된 유보의 증거: 152 분간의 GPT 흔적은 최첨단 모델이 부분 계산 (코커널) 이 가능하더라도 증명이 불완전할 때 인식하고 고수를 거부할 수 있는 능동적인 "메타인지 계층"을 보유하고 있다는 가장 강력한 기존 증거를 제공합니다.
2. 아키텍처 비대칭성: 결과는 추론 아키텍처의 근본적인 차이를 시사합니다. 저자들은 GPT 에 대해 3 계층 모델(명명된 정리 $\to$ 첫 번째 원리 $\to$ 보정된 유보) 을 제안하는 반면, Gemini 에 대해서는 단일 계층 모델(명명된 정리만) 을 제안합니다. 여기서 대체 메커니즘의 부재는 주요 휴리스틱이 실패할 때 무한 루프나 충돌로 이어집니다.
3. 프롬프트 설계의 진단적 가치: 본 논문은 프롬프트에서 "유한 지수" 약속을 생략하는 것이 중요한 설계 선택임을 보여줍니다. 이것이 없으면 커널/코커널 비대칭성이 모델로 하여금 결정 가능성 경계에 직면하게 하여, "유보"를 실패가 아닌 측정 가능하고 의미 있는 행동으로 만듭니다.
4. 계산 유창성 너머: 이 벤치마크는 큰 정수 산술을 수행할 수 있는 모델과 구조적 사전 지식 (아슈바허 클래스, 성질 (T), 합동 부분군 성질) 을 배포하고 알고리즘적 한계를 인식할 수 있는 모델을 구분합니다.

저자들은 벤치마크가 "명명된 정리를 아는 것"과 "우아한 대체 메커니즘을 갖는 것"을 성공적으로 분리하며, 현재 모델들이 구조적 추론을 수행할 수는 있지만 니켈슨 - 그래프 검색과 같은 알고리즘적 전략을 더 높은 랭크로 일반화하는 능력은 여전히 별도의 조사 영역임을 밝힌다고 결론지었습니다.