기술 요약: 기계적 해석 가능성을 통한 다이크 경로(Dyck Paths) 상의 제타 맵(Zeta Map) 알고리즘 발견

문제 정의

머신러닝은 수학 연구에 점점 더 많이 적용되고 있으나, 높은 예측 정확도와 명시적이고 검증 가능한 수학적 구성물 생성 사이에는 근본적인 간극이 존재한다. 조합론에서 원하는 출력값은 수치적 근사가 아니라, 독립적으로 확인 가능한 추측, 구성 또는 알고리즘이다. 본 논문은 기계적 해석 가능성(mechanistic interpretability) 도구가 훈련된 신경망으로부터 명시적인 조합 알고리즘을 추출할 수 있는지 조사함으로써 이 간극을 해결하고자 한다.

구체적인 테스트 케이스는 $q,t$-카탈랑 수(Catalan numbers) 이론의 중심인 고전적 전단사 함수인 다이크 경로(Dyck paths) 상의 **제타 맵($\zeta$)**이다. 제타 맵은 $(dinv, area)$통계량을$(area, bounce)$ 통계량으로 교환한다. 제타 맵은 이미 area sequence나 sweep map을 통해 잘 알려진 여러 알고리즘적 설명을 가지고 있지만, 데이터가 정확하게 생성 가능하고, 정답 여부를 철저히 검증할 수 있으며, 목표가 이산적인 조합 절차라는 점에서 AI 보조 발견을 위한 이상적인 통제 환경 역할을 한다.

방법론

1. 실험 설정

저자들은 반길이(semilength) $n$인 다이크 경로에 대한 제타 맵을 학습하는 트랜스포머 모델을 훈련시켰다.

• 데이터: 다이크 단어(Dyck words)와 그 이미지인 $\text{rev} \circ \zeta$ (여기서 $\text{rev}$는 SAGEMATH 구현과 일치하도록 단어를 역순으로 읽고 0과 1을 바꾸는 것을 의미함)로 구성된 지도 학습 데이터셋.
• 초기 훈련: 표준 인코더-디코더 트랜스포머(4개 층, 8개 헤드)는 다양한 반길이($n=11$에서 $16$)에 대해$99%$ 이상의 정확도를 달와 성취했다.
• 압축: 기계적 분석을 가능하게 하기 위해, 저자들은 의도적으로 작은 아키텍처인 **최소 다이크 트랜스포머(Minimal Dyck Transformer)**를 훈련시켰다(1개의 인코더 층, 1개의 디코더 층, 1개의 어텐션 헤드로 구성, 임베딩 차원 128, 약 34만 개의 파라미터). 이 모델은 완벽하거나 완벽에 가까운 정확도를 달성했다.

2. 기계적 해석 가능성 분석

핵심 방법론은 세 가지 주요 도구를 사용하여 최소 다이크 트랜스포머의 내부 작동 방식을 분석하는 것이다.

• 디코더 교차 어텐션 분석(Decoder Cross-Attention Analysis): 저자들은 출력 시퀀스를 생성하는 동안 어떤 입력 위치가 가장 높은 어텐션 가중치를 받았는지 추적했다.
• 인과적 절제(Causal Ablation): 특정 입력 위치(예: $w_i=1$인 상승 단계)에 대한 교차 어텐션을 마스킹하여, 해당 위치가 디코딩에 기능적으로 필수적인지 테스트했다.
• 선형 프로빙(Linear Probing): 인코더 은닉 상태(hidden states)에 선형 분류기를 훈련시켜 다이크 경로의 각 위치의 "레벨(level)"을 예측함으로써, 이 조합 통계량이 표현 내에 선형적으로 접근 가능한지 테스트했다.

3. 알고리즘 추출

최소 모델에서 관찰된 패턴을 바탕으로, 저자들은 새로운 명시적 알고리즘인 **스캐폴딩 맵(Scaffolding Map)**을 공식화하였으며, 이후 제타 맵과의 동등성을 증명하였다.

주요 결과 및 기여

1. 레벨 기반 메커니즘의 발견

해석 가능성 분석은 모델이 제타 맵을 임의의 룩업 테이블(lookup table)로 취급하는 것이 아니라, 구조화된 레벨 기반 메커니즘을 통해 생성 과정을 조직한다는 것을 드러냈다.

• 최고 레벨 선택: 디코더는 관련 위치 중 최대 레벨을 가진 입력 위치에 지속적으로 어텐션을 집중하며, 특히 초기 생성 단계에서 그러하다.
• 상승 단계의 체계적 회피: 디코더는 $w_i=1$(북쪽 단계)인 위치에 거의 어텐션을 주지 않는다. 인과적 절제를 통해 이 위치들에 대한 어텐션을 마스킹했을 때 정확도 저하가 미미함을 확인했으며, 이는 디코더가 이들을 직접 "읽는" 것이 아니라 집계된 정보에 의존함을 의미한다.
• 삼각형 순차 이동: 어텐션 패턴은 고레벨의 동쪽 단계(East-step, $w_i=0$) 위치에서 다음 적격 동쪽 단계 위치($i+1$)로의 이동을 나타내며, 이는 레벨의 순차적 감소($\ell_{i+1} = \ell_i - 1$)에 대응한다.
• 선형 접근성: 선형 프로브 결과, 인코더 표현이 다이크 경로의 레벨 시퀀스($\ell_i$)를 선형적으로 접근 가능하게 함을 확인했다(84% 예측 정확도).

2. 스캐폴딩 맵(Scaffolding Map)

이 신호들을 조합론으로 번역하여, 저자들은 피크(peak) 중심의 순회 알고리즘인 스캐폴딩 맵을 제안했다.

• 메커니즘: 이 알고리즘은 피크 위치들을 레벨별로 그룹화한다. 피크에서 "에이전트(agents)"를 초기화한 후, 위에서 아래 방향으로 레벨별로 경로를 순회한다.
• 순회: 에이전트들은 인접한 동쪽 단계 및 비동쪽 단계 위치들을 따라 이동한다. 출력 단어는 이 에이전트들이 상승 단계에 의해 구축된 "스캐폴드(scaffold)"를 따라 이동하며 만나는 기호들을 읽음으로써 생성된다.
• 구조: 이 알고리즘은 잠재적 지지 구조(상승 단계에 의해 구축된 레벨)와 생성 프로세스를 담당하는 순회 과정을 분리한다.

3. 이론적 검증

저자들은 스캐폴딩 맵이 제타 맵(데이터셋에서 사용된 역순 컨벤션 모듈로)과 동등하다는 공식적인 증명(정리 6.1)을 제공했다.

• 증명 전략: 스캐폴딩 맵을 레벨별로 $\text{rev} \circ \zeta$의 area-sequence 기술과 비교한다. 이는 스캐폴딩 맵의 큐잉 메커니즘($Q'_k$)에 의해 생성된 부분 시퀀스가 area sequence를 역방향으로 스캔하는 표준 제타 맵 알고리즘($P_k$)의 부분 시퀀스와 정확히 일치함을 보여준다.

의의 및 주장

본 논문은 기계적 해석 가능성이 블랙박스 예측을 명시적이고 인간이 검증 가능한 조합 구성물으로 전환하는 AI 보조 수학적 발견의 통제된 사례를 제공한다고 주장한다.

• 새로움: 저자들의 지식 범위 내에서, 이는 훈련된 뉴럴 시퀀스 모델의 기계적 해석을 통해 잘 연구된 조합 맵의 새로운 명시적 전단사 기술을 추출한 첫 번째 사례이다.
• 워크플로우: 논문은 다음과 같은 워크플로우를 제시한다:
  1. 모델이 반복되는 구조적 신호(어텐션 패턴, 선형 프로브)를 제공한다.
  2. 인간 연구자가 이러한 신호를 조합론적 연산으로 해석한다.
  3. 개입(절제)을 통해 인과적 관련성을 테스트한다.
  4. 결과적인 절차가 수학적 대상(스캐폴딩 맵)이 되어, 신경망과 독립적으로 기술되고 증명될 수 있게 된다.
• 한계점: 저자들은 다음과 같은 점을 언급하며 범위를 제한적으로 설정했다:
  • 어텐션 패턴만으로는 증명이 될 수 없으며, 조합적 연산과 결합된 절제 및 공식적 증명이 필수적이다.
  • 학습된 메커니즘은 (프로빙 결과에서 나타난 불완전한 정확도처럼) 알고리즘의 "퍼지(fuzzy)"한 버전인 것으로 보이며, 이는 더 크거나 다르게 훈련된 모델이 더 복잡하거나 "깔끔한" 메커니즘을 구현할 수 있음을 시사한다.
  • 스캐폴딩 맵은 구체적으로 단순한 모델로부터 추출된 것이며, 더 큰 모델은 다른 내부 솔루션을 구현할 수 있다.

결론적으로, 이 논문은 특정 발견의 세부 사항이 모든 수학적 문제에 직접적으로 전이되지는 않을 수 있으나, 기계적 해석 가능성을 사용하여 블랙박스 예측과 명시적 조합 구성 사이의 간극을 메우는 개념은 조합론 연구 내에서 널리 적용 가능하다는 점을 강조한다.