🤖 machine learning

The Discrete-Log Clock: How a Transformer Learns Modular Multiplication

이 논문은 트랜스포머가 모듈로 곱셈을 학습할 때 나타나는 겉보기 복잡성이 잘못된 분석적 기저를 사용한 데서 비롯된 인위적인 결과임을 입증하며, 이들이 곱셈의 성질을 가진 캐릭터(character) 공간 내에서 곱셈을 덧셈으로 환원함으로써 실제로는 희소하고 해석 가능한 "이산 로그 시계(Discrete-Log Clock)" 알고리즘을 구현하고 있음을 밝힌다.

원저자: Huu Danh Nguyen (Stanford University)

게시일 2026-06-17

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Huu Danh Nguyen (Stanford University)

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

거대한 미스터리: 왜 AI는 "혼란"스러워 보였을까?

로봇에게 수학을 가르치고 있다고 상상해 보세요. 구체적으로, 당신은 로봇에게 모듈로 곱셈(두 수를 곱한 뒤 특정 숫자(예: 113)로 나눈 나머지만 남기는 것)을 가르치고 싶습니다.

오랫동안 과학자들은 이상한 점을 발견했습니다. 로봇이 마침내 문제를 "깨우쳤을" 때(단순히 답을 암기하는 단계를 넘어 규칙을 이해하게 되는 현상을 **그로킹(grokking)**이라고 합니다), 로봇의 내부 수학 구조가 매우 무질서해 보였던 것입니다.

기존의 관점: 과학자들이 표준 도구를 사용하여 로봇의 뇌를 들여다보았을 때, 그들은 '조밀한(dense)' 혼돈을 보았습니다. 마치 로봇이 문제를 해결하기 위해 가능한 모든 소리의 주파수를 다 사용하고 있는 것처럼 보였습니다. 이는 단순한 덧셈을 해결할 때 보여주었던 깔끔하고 조직적인 모습과는 달리, 매우 혼란스럽고 이해하기 어려워 보였습니다.
문제점: 과학자들은 잘못된 안경을 쓰고 로봇의 뇌를 보고 있었습니다. 그들은 덧셈을 위해 설계된 "표준 자"를 사용하고 있었지만, 로봇은 실제로 곱셈을 하고 있었던 것입니다.

해결책: 렌즈를 바꾸다

이 논문의 저자들은 곱셈을 이해하려면 숫자를 있는 그대로(1, 2, 3...) 보는 것을 멈추고, 숫자를 생성원(generator)의 거듭제곱으로 보기 시작해야 한다는 것을 깨달았습니다.

이렇게 생각해보세요:

표준 관점 (덧셈): 1부터 12까지 적힌 시계 판을 상상해 보세요. 1을 더하면 한 칸 움직입니다. 이것은 보기 쉽습니다.
숨겨진 관점 (곱셈): 이제 시계 위의 숫자들이 뒤섞여 있다고 상상해 보세요. 숫자 "1"은 사실 "3"이고, 숫자 "2"는 "9"이며, 이런 식입니다. 이 뒤섞인 세계에서는 곱셈이 실제로는 덧셈과 똑같이 작동합니다.

이 논문은 이를 **"이산 로그 시계(Discrete-Log Clock)"**라고 부릅니다. 이는 복잡한 곱셈 문제를 단순한 덧셈 문제로 변환하는 비밀 코드와 같습니다.

그들이 발견한 것 ("아하!"의 순간)

연구진이 이 새로운 "뒤섞인" 렌즈(저자들은 이를 **곱셈적 특성 변환(multiplicative character transform)**이라 부릅니다)를 사용하여 로봇의 뇌를 재검토했을 때, 혼돈은 사라졌습니다.

노이즈가 신호가 되다: 무질서하고 조밀한 스펙트럼을 보는 대신, 그들은 매우 깨끗하고 희소한(sparse) 패턴을 발견했습니다. 로봇은 모든 주파수를 사용하는 것이 아니라, 수학을 하기 위해 오직 4개의 특정 주파수만을 사용하고 있었습니다. 이는 마치 소음 가득한 방 안에서 단 하나의 맑은 멜로디를 찾아낸 것과 같았습니다.
뉴런이 조직화되다: 로봇에게는 수천 개의 작은 처리 장치(뉴런)가 있습니다. 기존의 관점에서는 이들이 무작위로 보였습니다. 하지만 새로운 관점에서 보면, 97%의 뉴런이 정확히 그 4개 주파수 중 하나에 맞춰져 있었습니다. 그들은 마치 모든 가수가 어떤 음을 내야 할지 정확히 알고 있는 합창단과 같았습니다.
패턴의 출현: 데이터를 이 비밀 코드를 바탕으로 재배열했을-때, 로봇의 내부 활동은 완벽한 대각선 줄무늬를 형성했습니다. 이는 로봇이 특정 기술을 학습했음을 증명했습니다:
- 1단계: 숫자를 "비밀 코드"(이산 로그)로 변환합니다.
- 2단계: 코드를 함께 더합니다(일반적인 덧셈처럼).
- 3단계: 결과를 다시 일반적인 숫자로 변환합니다.

"시계" 비유

이 논문은 덧셈에 사용되는 유명한 "시계 알고리즘(Clock Algorithm)"에 비유합니다.

덧셈의 경우: 로봇은 시계 바늘을 회전시키는 법을 배웁니다.
곱셈의 경우: 로봇은 다른 종류의 시계(이산 로그 시계)의 바늘을 회전시키는 법을 배웁니다. 일단 이 특별한 시계의 바늘을 회전시키면, 정답이 바로 그곳에 나타납니다.

이전의 과학자들은 왜 놓쳤을까?

당신이 노래를 들으려고 하는데, 베이스 소리만 통과시키는 노이즈 캔슬링 헤드폰을 쓰고 있다고 상상해 보세요. 당신은 쿵쾅거리는 무질서한 소리를 듣고 "이 노래는 그냥 소음일 뿐이야"라고 결론 내릴 것입니다.

이전의 연구자들은 그런 "헤드폰"(표준 수학 도구)을 쓰고 있었습니다. 그들은 "쿵쾅거리는 소리"(조밀한 스펙트럼)를 보고서 로봇이 복잡하고 설명할 수 없는 방법을 사용하고 있다고 생각했습니다. 저자들은 단순히 헤드폰을 벗고, 올바른 주파수로 전환하여, 로봇이 사실은 아름답고 단순한 멜로디를 연주하고 있었다는 것을 깨달았습니다.

핵심 요약

이 논문의 주요 교훈은 단순히 수학에 관한 것이 아니라, 우리가 사물을 바라보는 방식에 관한 것입니다.

교훈: 복잡한 시스템(AI나 집단 같은)을 이해하려고 한다면, 반드시 그 작업에 맞는 올바른 "언어"나 "기저(basis)"를 사용하고 있는지 확인해야 합니다.
결과: 분석 도구를 실제 문제의 구조(이 경우에는 곱셈을 위한 "곱셈적" 렌즈 사용)와 일치시키면, 무질서하고 설명할 수 없는 소음은 명확하고 단순하며 이해 가능한 알고리즘으로 변합니다.

로봇은 수학을 하는 새롭고 신비로운 방법을 발명한 것이 아닙니다. 그저 어려운 문제를 쉬운 문제로 바꾸는 비밀 코드를 찾아냈을 뿐이며, 연구자들은 마침로 그 코드를 읽는 법을 알아낸 것입니다.

기술 요약: 이산 로그 시계 (The Discrete-Log Clock)

문제 정의
트랜스포머가 모듈로 덧셈( $a + b \mod p$ )을 학습하는 내부 메커니즘은 희소 푸리에 표현(sparse Fourier representation)인 "시계(Clock)" 알고리즘으로 완전히 역공학된 반면, 모듈로 곱셈( $a \cdot b \mod p$ )의 메커니즘은 여전히 미해결 상태로 남아 있었다. 선행 연구들(Doshi et al., 2024; Furuta et al., 2024)은 곱셈을 학습한 트랜스포머가 모든 주파수를 필요로 하는 "밀집된(dense)" 푸리에 스펙트럼을 보인다고 보고했으며, 이는 덧셈에서 발견된 희소한 구조와 극명하게 대조되었다. 이는 곱셈이 근본적으로 다른, 해석하기 어려운 알고리즘에 의존할 수 있음을 시사했다.

방법론
저자들은 입력값 $a, b \in \{1, \dots, 112\}$ 에 대해 $a \cdot b \mod 113$ 을 예측하도록 1-레이어 디코더 전용 트랜스포머를 학습시킨다. 모델은 데이터의 30%로 학습되며, 나머지 70%에 대해 일반화되어야 한다. 이 과정에서 모델은 암기 기간 이후 갑작스럽게 일반화가 일어나는 "그로킹(grokking)" 현상을 보인다.

핵심적인 방법론적 혁신은 분석 기저(analysis basis)의 전환이다. 저자들은 토큰 임베딩에 표준적인 가법적 이산 푸리에 변환(additive DFT)을 적용하는 대신, **곱셈적 캐릭터 변환(multiplicative character transform)**을 적용한다. 이 과정은 다음과 같다:

소수 $p$ 에 대한 0이 아닌 정수들은 순환군 $(\mathbb{Z}/p\mathbb{Z})^*$ 를 형성함을 인식한다.
원시근(primitive root) $g$ (여기서는 $g=3$ )를 사용하여 입력을 이산 로그 $\alpha = \log_g(a)$ 및 $\beta = \log_g(b)$ 로 매핑한다.
이 이산 로그에 따라 임베딩 행렬의 행을 재정렬한다.
재정렬된 데이터에 표준 DFT를 적용한다.

이 접근 방식은 원래 공간에서의 곱셈이 로그 공간에서의 덧셈( $a \cdot b \equiv g^{\alpha + \beta} \mod p$ )에 대응한다는 군 동형성(group isomorphism)을 활용한다.

주요 결과

스펙트럼 희소성: 가법적 기저에서 분석했을 때 임베딩 스펙트럼은 평탄하고 밀집되어 보이지만(지니 계수 0.07), 곱셈적 캐릭터 기저에서는 스펙트럼이 매우 희소해지며(지니 계수 0.58), 에너지가 단 4개의 핵심 주파수( $\{2, 8, 47, 56\}$ )에 집중된다.
뉴런 튜닝: 곱셈적 기저에서 MLP 뉴런의 96.9%(496/512)가 단일 주파수에 "깔끔하게 튜닝"되어 있으며, 이들의 활성화 에너지 중 85% 이상이 해당 주파수에 집중되어 있다. 가법적 기저에서는 이 기준을 충족하는 뉴런이 전무하다.
구조적 시각화: 이산 로그에 따라 재정렬된 뉴런 활성화 히트맵은 명확한 2D 주기적 대각선 줄무늬를 보여준다. 이는 뉴런이 $\cos(k(\alpha + \beta))$ 형태의 함수를 계산하며, 실질적으로 로그 공간에서 덧셈을 수행하고 있음을 나타낸다.
SVD 분석: 이산 로그에 의해 재정렬된 임베딩 행렬의 주성분(principal components)은 명확한 사인파 구조를 보이며, 이는 곱셈적 캐릭터의 인코딩을 확인시켜 준다.

"이산 로그 시계" 알고리즘
본 논문은 트랜스포머가 덧셈을 위한 "시계" 알고리즘과 유사한 알고리즘인 **이산 로그 시계(Discrete-Log Clock)**를 구현한다고 결론짓는다. 메커니즘은 다음과 같이 진행된다:

임베딩: 정수는 이산 로그의 사인 함수 형태로 임베딩된다.
라우팅: 어텐션 메커니즘은 이러한 임베딩을 출력 위치로 전달한다.
합성: MLP는 삼각 항등식을 적용하여 이산 로그의 합(실질적으로 $\alpha + \beta$ 를 더함)을 계산한다.
디코딩: 모델은 핵심 주파수들 사이에서 보강 간섭(constructive interference)이 발생하는 지점을 통해 로그 공간에서의 계산된 합과 일치하는 후보 출력의 점수를 매긴다.

의의 및 주장
본 연구의 주요 기여는 선행 연구에서 관찰된 "밀집된 스펙트럼"이 알고리즘의 복잡성을 반영하는 것이 아니라, **데이터를 잘못된 기저에서 분석한 결과로 나타난 아티팩트(artifact)**임을 입증한 것이다. 분석 기저를 문제의 대수적 구조(곱셈군)와 일치시킴으로써, 저자들은 곱셈이 이산 로그 공간에서의 덧셈으로 환원됨을 밝혀냈다.

논문은 이 방법론이 일반화 가능함을 주장한다:

희소한 곱셈 스펙트럼은 10개의 서로 다른 소수( $p=59$ 에서 $113$까지)에 대해 확인되었다.
이 메커니즘은 무작위 시드에 대해 보편적이다(약 80%의 시드).
예비 결과에 따르면, 이 접근 방식은 2-레이어 트랜스포머를 사용하여 모듈로 거듭제곱( $a^b \mod p$ )으로 확장될 수 있음을 시사한다.

저자들은 대수적 작업에 대해, 표준적인 가법적 DFT(additive DFT) 대신 해당 군(group)에 적합한 푸파 변환을 적용하는 것이, 기존의 도구들이 노이즈로 간주했던 곳에서 해석 가능한 구조를 드러내는 데 필수적임을 강조한다.