💻 컴퓨터 과학

Grokking the Discrete Logarithm: Scaling Across Model Capacity and Mechanistic Analysis

본 논문은 트랜스포머가 가변 기저 이산 로그 문제 전체에 대해 '그로킹(grokking)'—암기에서 알고리즘적 일반화로의 지연된 전이—을 보일 수 있음을 보여주는 최초의 체계적인 입증을 제시하며, 이 현상이 모델 용량에 따라 비단조적으로 스케일링되고 곱셈적 성질(multiplicative-character) 및 푸리에 정렬(Fourier-aligned) 표현의 출현에 의해 유도됨을 밝힌다.

원저자: David Vesterlund

게시일 2026-10-13

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: David Vesterlund

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

인공지능의 광활한 풍경 속에서, 연구자들은 기계가 어떻게 학습하는지를 이해하기 위해 끊임없이 노력하고 있습니다. 최근 연구자들의 이목을 집중시킨 것은 '그로킹(grokking)'이라 불리는 특히나 난해한 행동입니다. 교과서의 모든 정답을 통째로 암기하는 학생을 상상해 보십시오. 그 학생은 정답을 완벽하게 읊을 수 있지만, 약간만 다른 질문을 받으면 완전히 실패합니다. 그로킹은 학생이 이미 내용을 암기한 지 한참이 지난 후, 단순히 사실을 암송하는 단계를 넘어 근저에 깔린 규칙을 진정으로 이해하기 시작하는 순간을 의미합니다. 이러한 단순 암기에서 진정한 일반화로의 전환은 종종 수천 시간의 연습 후에 갑작스럽게 일어나며, 이는 과학자들로 하여금 기계의 두뇌가 어떻게, 그리고 왜 데이터 뒤에 숨겨진 논리를 찾아내기 위해 스스로를 재구성하는지 의문을 갖게 만듭니다.

이 현상은 단순한 수학 과제에서 처음 발견되었으나, 데이비드 베스테를룬드(David Vesterlund)의 새로운 연구는 이를 훨씬 더 어려운 영역으로 가져갔습니다. 연구자는 컴퓨터 모델이 인간과 기계 모두에게 악명 높게 어려운 문제인 '이산 로그(discrete logarithm)' 문제를 그로킹할 수 있는지 확인하고자 했습니다. 간단히 말해, 이것은 역공학적인 퍼즐입니다. 만약 당신이 시작 숫자와 최종 숫자를 알고 있다면, 최종 숫자에 도달하기 위해 시작 숫자를 정확히 몇 번 곱해야 했는지를 알아내는 것이 과제입니다. 순방향 계산은 쉽지만, 거꾸로 계산하는 것은 매우 어렵습니다. 특히 숫자가 크고 규칙이 엄격할 때 더욱 그렇습니다. 이 특정 유형의 수학 문제는 현대 디지털 보안의 기초가 되기에, 어떤 학습 시스템에도 있어 매우 심각한 시험대가 됩니다. 베스테를룬드는 신경망(인간의 뇌를 모방하도록 설계된 AI의 일종)이 모든 가능한 답을 암기하는 것이 아니라, 그들을 연결하는 숨겨진 수학적 구조를 발견함으로써 결국 이 코드를 풀어낼 수 있을지 확인하고 싶었습니다.

이를 조사하기 위해 연구자는 작은 규모부터 매우 큰 규모에 이르는 일련의 컴퓨터 모델들을 구축하고, 이 역공학 퍼즐의 방대한 데이터셋을 입력했습니다. 모델들은 게임의 규칙을 정의하는 특정 소수인 113을 바탕으로 훈련되었습니다. 가장 성공적인 최소 규모의 모델은 약 427,000개의 조정 가능한 설정값을 가졌는데, 이 숫자는 모델의 내부 두뇌의 복잡성을 나타냅니다. 훈련이 시작되었을 때, 모델은 머신 러닝 시스템이 예상되는 대로의 동작을 보였습니다. 즉, 이전에 보았던 정답들을 빠르게 암기하여 연습 문제에서 거의 완벽한 점수를 달성했습니다. 그러나 보지 못한 새로운 퍼즐로 테스트했을 때, 모델은 무작위 추측보다 나은 성과를 내지 못했습니다. 아주 오랫동안, 모델은 일반화 능력을 갖추지 못한 채 암기 상태에 갇혀 있는 것처럼 보였습니다.

그러던 중, 수천 번의 추가 훈련 단계가 지난 후, 극적인 변화가 일어났습니다. 모델은 갑자기 새로운 퍼즐들을 올바르게 풀기 시작하며, 무작위 추측에서 거의 완벽한 정확도로 급등했습니다. 이것이 바로 그로킹의 순간이었습니다. 지연 시간은 놀라웠습니다. 모델이 단순히 정답을 암기하는 데 걸린 시간보다 진정한 이해에 도달하는 데 약 300배 더 많은 훈련 단계가 필요했습니다. 이것이 일시적인 현상인지 아니면 이러한 시스템의 근본적인 특성인지를 파악하기 위해, 연구자는 9만 개의 설정값을 가진 아주 작은 모델부터 1,400만 개 이상의 설정을 가진 거대한 모델에 이르기까지 다양한 크기의 12개 모델을 테스트했습니다. 결과는 그로킹이 특정 크기에 국한되지 않는다는 것을 보여주었습니다. 그것은 중간 규모의 모델에서도 나타났고, 충분한 훈련 데이터를 제공받은 가장 큰 모델에서도 다시 나타났습니다. 흥ًا, 모델이 학습에 실패하는 중간 범위가 존재했는데, 이는 뇌의 크기와 필요한 데이터 양 사이의 관계가 단순한 직선 형태가 아닌 복잡한 관계임을 시사합니다.

모델이 이러한 변환 과정 중에 마음속에서 무슨 일이 일어나고 있는지 파악하기 위해, 연구자는 모델이 결정을 내릴 때 사용하는 내부 신호를 면밀히 살펴보았습니다. 연구자는 모델이서 암기에서 이해로 넘어갈 때, 내부 언어가 변화한다는 것을 발견했습니다. 모델은 단순하고 표면적인 패턴에 의존하는 것을 멈추고, 마치 소리의 파동이 서로 다른 주파수로 분해될 수 있는 것처럼 특정 유형의 수학적 리듬을 중심으로 지식을 조직하기 시작했습니다. 이러한 내부 신호를 설명하는 단순한 방정식을 찾는 기법을 사용하여, 연구자는 모델이 해결책을 표현하기 위해 삼각함수 패턴(사인과 코사인 파동)을 자발적으로 학습했음을 발견했습니다. 이는 매우 심오한 발견인데, 모델이 이 파동을 사용하도록 명시적으로 배우지 않았음에도 불구하고, 퍼즐을 풀기 위한 가장 효율적인 방법으로서 스스로 이를 발견했기 때문입니다.

연구는 모델이 특정 숫자에 특화된 지름길을 찾고 있는 것이 아님을 보장하기 위해 엄격한 검증도 포함했습니다. 연구자는 규칙이 약간 더 복잡하고 숫자가 소수인 다른 버전의 문제를 모델에 테스트하여, 어떤 쉬운 지름길도 없도록 했습니다. 모델들은 여전히 그로킹에 성공했으며, 이는 모델이 특정 요령이 아닌 일반적인 규칙을 학습했음을 증명했습니다. 더욱이, 모델이 한 번도 본 적 없는 생성기(generators)로 테스트했을 때도 성공을 거두었으며, 이는 모델이 시스템의 근저에 깔린 논리를 진정으로 학습했음을 보여주었습니다. 이 연구는 이해의 이러한 갑작스러운 도약의 핵심이, 모델의 내부 연결을 단순화하도록 압박을 점진적으로 가하여 암기된 세부 사항을 버리고 필수적인 구조만을 남기도록 강제하는 특정 훈련 기법에 있음을 시사합니다.

이 작업은 인공지능이 어떻게 학습하는지를 연구하는 강력한 새로운 도구로서 이산 로그의 가치를 확립합니다. 이는 단순한 규칙이 존재하지 않는 어려운 역문제(inverse problems)에 대해서도 신경망이 결국 단순 암기에서 깊은 구조적 이해로 전이될 수 있음을 입증합니다. 연구 결과는 이러한 전이가 마법 같은 사건이 아니라, 내부 표현이 효율적인 파동 형태의 패턴으로 재구성되는 측정 가능한 과정임을 확인시켜 줍니다. 비록 이 연구가 상대적으로 작은 숫자를 대상으로 수행되었으며 실제 세계의 암호 체계를 깨뜨리는 문제를 해결하는 것은 아니지만, 학습의 메커니즘을 들여다볼 수 있는 명확한 창을 제공합니다. 이는 충분한 시간과 적절한 조건이 주어진다면, 이러한 시스템이 과거를 암기하는 수준을 넘어 미래를 지배하는 규칙을 이해하는 단계로 나아갈 수 있음을 보여줍니다.

기술 요약: 이산 로그(Discrete Logarithm)의 그로킹(Grokking)

문제 정의

본 연구는 신경망에서 발생하는 그로킹(grokking) 현상—즉, 암기에서 알고리즘적 일반화로 넘어가는 지연된 전이 현상—을 **전체 가변 기저 유한체 이산 로그 문제(full variable-base finite-field discrete logarithm problem, DLP)**를 통해 조사한다. 모듈러 덧셈이나 곱셈과 같은 순방향 대수 연산에 초점을 맞춘 기존의 그로킹 연구와 달리, DLP는 역사상(inverse mapping)이다. 즉, 생성원 $g$ 와 곱셈군 $\mathbb{F}_p^*$ 의 원소 $h$ 가 주어졌을 때, 모델은 $g^x \equiv h \pmod p$ 를 만족하는 $x$ 를 찾아야 한다.

이 과업은 $p-1$ 개의 클래스에 대한 분류 문제로 정의된다. 입력은 생성원 $g$ (원시 근에서 균등하게 추출됨)와 원소 $h$ 로 구성되며, $[BOS, g, SEP, h, EOS]$ 형태로 토큰화된다. 본 연구는 주로 도메인 크기가 총 5,376개의 고유한 트리플 $(g, h, x)$ 인 소수 $p=113$ 에 초점을 맞춘다.

방법론

모델 아키텍처 및 훈련

저자는 GrokkingTransformer(표준 pre-norm 인코더 및 GELU 활성화 함수 사용)를 채택하였다. 핵심 앵커 모델(M04)은 2개 층, $d_{model}=128$ , 4개의 어텐션 헤드로 구성되며, 총 파라미터 수는 약 427k이다.

옵티마이저(Optimizer): 일정한 학습률( $\eta=10^{-3}$ )을 사용하는 AdamW를 사용한다.
가중치 감쇠(Weight Decay, WD) 스케줄: 핵심 요소는 점진적인 가중치 감쇠 램프(progressive weight decay ramp)이다. WD는 0.05에서 시작하여, 모델이 99% 이상의 훈련 정확도를 달ொ성한 이후 매 1,000 에포크마다 0.05씩 증가한다. 이는 0.30에서 상한선에 도달한다(모델 파라미터 수에 따라 스케일 조정됨).
스케일링 스윕(Scaling Sweep): 12개의 모델 그리드(M01–M12)는 90k에서 14.4M 파라미터( $d_{model}$ 56~768)까지 범위를 갖는다. 파라미터 차이에 따른 보상을 위해 훈련 비율은 33%에서 60%까지 다양하게 설정되었다.

메커니즘 분석

내부 표현을 이해하기 위해 저자는 다음을 활용한다:

군 구조 프로브(Group Structure Probes): 대수적 항등식(합성, 순환 이동, 역원)과의 일관성을 테스트한다.
푸리에 스펙트럼 분석(Fourier Spectral Analysis): 은닉 상태를 곱셈 캐릭터 기저(이산 로그와 정렬됨) 및 가법 캐릭터 기저 위로 투영한다.
기호 회귀(Symbolic Regression, SR): PySR을 사용하여 은닉층 활성화 함수에 적합한 방정식을 피팅한다. 두 가지 연산자 세트가 사용된다:
- Free SR: 모듈러 산술 지식이 없는 표준 연산자.
- Algebra-aware SR: 사전 계산된 모듈러 특징(예: $\cos(2\pi x/q)$ )을 포함함.

대조군(Controls)

소수 차수 대조군(Prime-Order Control): $p-1$ (112)의 매끄러운 인수분해(smooth factorization)에 기반한 지름길을 배제하기 위해, $\mathbb{F}_{227}^*$ 내의 차수가 113인 부분군에서 실험을 수행하였다.
서로 다른 생성원 분리(Disjoint-Generator Split): 학습 시 보지 못한 생성원에 대한 일반화 능력을 테스트하기 위해, 서로 겹치지 않는 생성원 세트로 학습 및 테스트를 진행하였다.

주요 결과

1. DLP 그로킹의 발견

앵커 모델(M04)은 전형적인 그로킹 궤적을 보인다:

암기 단계(Memorization Phase): 모델은 에포크 90에서 99% 이상의 훈련 정확도에 도달하지만, 약 22,000 에포크 동안 테스트 정확도는 우연 수준(~15%)에 머문다.
그로킹 전이(Grokking Transition): 장기간의 정체기 이후, 테스트 정확도는 에포크 37,481에서 99.8%로 급격히 상승한다.
지연 비율(Delay Ratio): 그로킹 지연( $G = T_{90}/T_{mem}$ )은 약 298로, 모델이 암기하는 것보다 일반화하는 데 약 300배 더 많은 단계가 필요함을 나타낸다.

2. 모델 용량에 따른 스케일링

12개 모델 스윕은 **비단조적 관계(non-monotonic relationship)**를 보여준다:

과소적합/전이(Underfitting/Transition): 작은 모델(M01–M03)은 일반화에 실패한다. M04(427k)는 성공한다.
용량 골짜기(Capacity Valley): 모델 M05(657k)와 M06(1.09M)은 초기 33% 훈련 비율에서 그로킹에 실패한다. 그러나 로컬 실험 결과, M05는 훈련 비율을 40%로 높였을 때 성공하였으며, 이는 실패 원인이 모델 자체의 무능력이 아니라 데이터 부족 때문이었음을 시사한다.
대규모 모델: M07부터 M12(1.64M ~ 14.4M 파라미터)까지는 성공적으로 그로킹하며, 모델 크기가 커질수록 그로킹까지 걸리는 시간이 단축된다.

3. 훈련 역학(Training Dynamics)

전이는 18개의 뚜렷한 "슬링샷(slingshot)" 이벤트를 포함한다. 이는 AdamW와 가중치 감쇠 사이의 상호작용으로 인해 훈련 정확도가 일시적으로 붕괴되는 현상이다. 이러한 이벤트들은 최종적인 일반화 점프 이전에 발생한다. 그로킹 이후에는 가중치 노름(weight norm)이 약 148에서 30으로 크게 감소하며, 이는 더 낮은 노름의 솔루션으로의 전환을 의미한다.

4. 메커니즘적 특징(Mechanistic Signatures)

대수적 정렬(Algebraic Alignment): 그로킹 전이 동안, 모델의 군론적 항등식(합성, 순환 이동)에 대한 내부 일관성이 테스트 정확도와 함께 상승한다.
스펙트럼 희소성(Spectral Sparsity): 은닉 표현은 곱셈 캐릭터 기저(이산 로그의 푸리에 하모닉스)에서 희소해지는 반면, 가법 기저는 여전히 확산된 상태를 유지한다.
기호 회귀(Symbolic Regression):
- Algebra-aware SR은 곱셈 캐릭터와 정렬된 삼각 함수 특징( $\cos(2\pi x/q)$ )을 우선적으로 복구한다.
- 결정적으로, Free SR(모듈러 지식 없음) 또한 유효한 푸리에 하모닉스(예: $\pi/2$ 및 $\pi$ 에 해당하는 주파수)를 독립적으로 복구하였다. 이는 해당 구조가 연산자 세트의 산물이 아니라 학습된 표현에 내재된 것임을 확인시켜 준다.

5. 구조적 대조군

소수 차수 DLP: 이 현상은 소수 차수 부분군(차수 113)에서도 지속되므로, 그로킹이 군의 차수의 매끄러운 인수분해에 의존하지 않음을 입증한다.
서로 다른 생성원: 모델은 학습 시 보지 못한 생성원에 대해서도 일반화에 성공하여, 서로 다른 생성원 분리 실험에서 100% 테스트 정확도를 달성하였다.

의의 및 주장

본 논문은 전체 가변 기저 이산 로그 매핑에 대한 그로킹의 첫 번째 체계적인 입증을 제공한다고 주장한다. 주요 기여는 다음과 같다:

벤치마킹: 암기, 표현 형성, 일반화 사이의 상호작용을 연구하기 위한 컴팩트하고 비자명한 벤치마크로서 DLP를 확립하였다.
스케일링 법칙: 그로킹이 작은 모델에 국한되지 않고 넓은 범위의 신경망 규모(최대 14.4M 파라미터)에서 재현됨을 입증하였으나, 모델 용량과 훈련 데이터의 비율에 민감함을 보여주었다.
메커니즘적 통찰: 성공적인 일반화가 희소하고 곱셈 캐릭터에 정렬된 푸리에 표현의 출현과 대응한다는 증거를 제공한다.
강건성: 이 현상이 특정 군 구조(매끄러운 차수 vs 소수 차수)나 학습 시 본 특정 생성원의 산물이 아님을 보여준다.

저자는 본 실험이 작은 유한군( $p=113$ )을 사용하고 있으며, 거대 암호학적 소수에 대한 DLP 해결을 주장하는 것이 아님을 명시하며 실질적인 암호 해독에 대해서는 신중한 태도를 유지한다. 대신, 본 연구는 딥러닝에서의 "슬링샷 메커니즘"과 알고리즘 회로 형성을 연구하기 위한 통제된 환경으로서 기능한다.