Functorial Neural Architectures from Higher Inductive Types

Each language version is independently generated for its own context, not a direct translation.

1. 핵심 문제: 레고 블록을 조립하는 로봇

상상해 보세요. 로봇이 '레드 블록'과 '블루 블록'을 각각 쌓는 법을 배웠습니다.

기존 AI (Transformer): 이 로봇은 블록을 쌓을 때, "아, 레드 블록이랑 블루 블록이 같이 있으면 어떡하지?"라고 모든 블록을 한 번에 훑어보며 복잡한 계산을 합니다.
- 문제는, 로봇이 '레드 + 블루'를 배웠을 때, '블루 + 레드'나 '레드 + 레드 + 블루' 같은 새로운 조합을 만나면 당황한다는 것입니다. 모든 블록을 한 번에 보느라, 순서와 조합의 규칙을 잊어버리기 때문입니다.
- 결과: 배운 것만 잘 하고, 새로운 조합은 엉망이 됩니다.
이 논문의 제안 (HIT 기반 아키텍처): 이 로봇은 각 블록을 따로따로 만든 다음, 규칙에 따라 딱딱 붙이는 방식을 사용합니다.
- "레드 블록은 이렇게 만들고, 블루 블록은 저렇게 만들고, 둘을 붙일 때는 '오른쪽 - 왼쪽' 규칙만 지키면 돼."
- 결과: 어떤 조합이든 (레드 100 개든, 블루 5 개든) 규칙만 따르면 완벽하게 조립됩니다.

2. 핵심 아이디어: "수학적 건축가" vs "요리사"

저자는 AI 의 구조를 **수학의 '위상수학 (Topology)'**과 **'범주론 (Category Theory)'**이라는 도구를 이용해 설계합니다.

비유: 지도를 그리는 두 가지 방법

기존 AI (Attention Mechanism): 마치 요리사처럼 모든 재료를 한 냄비에 넣고 섞습니다. "이 재료가 저 재료와 만나면 맛이 어떻게 날까?"라고 예측합니다. 하지만 재료가 너무 많으면 (문장이 길어지면) 맛이 망가집니다.
새로운 AI (Functorial Architecture): 마치 건축가처럼 블록 하나하나를 미리 설계합니다.
- HIT (고급 인덕션 타입): 이는 건축가에게 **"이 공간은 어떤 모양이고, 어떤 규칙으로 이어져야 한다"**는 설계도입니다.
- 컴파일러: 이 설계도를 보고 AI 가 자동으로 **"이 블록은 이 모양으로 만들고, 저 블록은 저 모양으로 만들어서 붙여라"**라는 코드를 짜줍니다.
- 결과: 설계도 (규칙) 자체가 AI 에 내장되므로, AI 가 실수할 여지가 아예 없습니다.

3. 실험 결과: 세 가지 미로 탈출하기

저자는 세 가지 다른 형태의 '미로 (공간)'에서 이 두 방식을 테스트했습니다.

토러스 (Torus, 도넛 모양):
- 규칙이 단순합니다 (A+B = B+A).
- 결과: 기존 AI 도 어느 정도 잘하지만, 새로운 길이가 나오면 실수가 늘어납니다. 새로운 방식은 2~2.7 배 더 정확했습니다.
원 두 개가 만나는 모양 (S1 ∨ S1):
- 규칙이 까다롭습니다 (A+B ≠ B+A). 순서가 중요해요.
- 결과: 기존 AI 는 완전히 망가졌습니다. "왼쪽 원"을 가야 할 때 "오른쪽 원"으로 가는 등 방향을 완전히 잃었습니다. 반면 새로운 방식은 5.5~10 배 더 정확했습니다.
- 비유: 기존 AI 는 "왼쪽, 오른쪽"을 섞어서 기억하다가 길을 잃은 관광객이고, 새로운 방식은 나침반을 들고 있는 가이드입니다.
클라인 병 (Klein Bottle):
- 가장 복잡한 규칙이 있습니다. "B 를 지나면 A 의 방향이 뒤집힌다"는 특수한 법칙이 있습니다.
- 결과: 기존 AI 는 이 법칙을 전혀 이해하지 못했습니다. 하지만 새로운 방식은 이 **복잡한 법칙 (2-셀)**을 학습시켜서, 방향이 뒤집히는 순간을 정확히 처리했습니다.
- 의미: 단순히 규칙을 외우는 게 아니라, 규칙이 변하는 순간을 수학적으로 증명하고 적용한 것입니다.

4. 왜 기존 AI 는 안 될까? (Attention 의 한계)

논문은 **"소프트맥스 어텐션 (Attention)"**이라는 현재 AI 의 핵심 기술이 수학적으로 '조합성 (Compositionality)'을 가질 수 없다고 증명합니다.

비유: 어텐션은 "모든 사람이 서로 눈을 마주치며 대화하는 회의"입니다.
- 회의가 길어질수록 (문장이 길어질수록) 서로의 말을 섞어 듣느라, 누가 먼저 말했는지, 어떤 순서로 진행되었는지를 잊어버립니다.
- 반면, 새로운 방식은 **"각자 역할이 정해진 팀"**입니다. A 팀은 A 일만, B 팀은 B 일만 하고, 마지막에 팀장만 규칙대로 합칩니다. 그래서 길이가 아무리 길어져도 실수가 없습니다.

5. 결론: "배우는 것"이 아니라 "설계하는 것"

이 논문의 가장 큰 메시지는 다음과 같습니다.

"AI 에게 '더 많이' 학습시키는 것만으로는 문제를 해결할 수 없습니다. AI 의 뼈대 (구조) 자체가 규칙을 따르도록 설계되어야 합니다."

기존 방식: "이거 잘해봐, 더 많이 공부해." (학습에 의존)
새로운 방식: "이게 규칙이야. 이 규칙을 따르는 기계로 만들어." (설계에 의존)

이 방법은 로봇이 장애물을 피하는 법, 복잡한 문장을 해석하는 법, 혹은 분자 구조를 설계하는 법 등 규칙이 있는 모든 작업에 적용할 수 있습니다. 마치 **"수학적으로 검증된 설계도"**를 통해 AI 를 만드는 첫걸음이라고 할 수 있습니다.

한 줄 요약:

"AI 가 새로운 상황을 잘 처리하지 못하는 이유는 머리가 나빠서가 아니라, 모든 것을 한 번에 섞어보는 '요리사' 방식이기 때문입니다. 이제부터는 규칙대로 블록을 쌓는 '건축가' 방식으로 AI 를 설계해야 합니다."

Each language version is independently generated for its own context, not a direct translation.

1. 문제 제기 (Problem)

구성적 일반화 (Compositional Generalization) 의 실패: 신경망은 알려진 부분들의 새로운 조합에 대해 올바른 출력을 생성하는 데 체계적으로 실패합니다. (예: 2 자리 수 덧셈을 배운 모델이 5 자리 수 덧셈을 처리하지 못함, 로봇이 단일 장애물 회피를 배웠으나 두 장애물 회피를 구성하지 못함).
실패의 원인: 이는 모델의 용량 (capacity) 부족이 아니라 아키텍처적 결함입니다. 기존 신경망 (특히 Transformer 의 Self-Attention) 은 입력 시퀀스의 토큰 순서에 의존하여 정보를 혼합하는 방식으로 작동하기 때문에, 구성적 규칙 (예: 군론적 관계) 을 구조적으로 보존하지 못합니다.
핵심 가설: 구성적 일반화는 디코더의 함자성 (Functoriality) 과 동치입니다. 즉, 입력 대수 (입력 시퀀스) 에서 출력 대수 (결과) 로의 매핑이 구조적 결합을 보존해야 합니다.

2. 방법론 (Methodology)

저자는 고차 유도 타입 (Higher Inductive Types, HIT) 의 명세를 신경 아키텍처로 컴파일하는 새로운 프레임워크를 제안합니다.

가. 이론적 기반: HIT 에서 아키텍처로의 컴파일

HIT 명세: 위상 공간 (예: 토러스, 원의 뒤틀림) 을 생성자 (basepoints, loops) 와 관계 (2-cells, homotopies) 로 정의합니다.
- 예: 토러스 ( $T^2$ ) 는 두 개의 루프 ( $a, b$ ) 와 교환 법칙 ($ab=ba$) 을 가진 2-cell 로 정의됨.
컴파일링 함자 (Compilation Functor): HIT 의 각 구성 요소를 신경망 구성 요소로 매핑합니다.
1. 생성자 (Generators): 각 루프 생성자 ( $a_i$ ) 는 독립적인 신경망 (MLP) $g_{a_i}$ 로 매핑되어 해당 호모토피 클래스에 속하는 루프를 생성합니다.
2. 합성 (Composition): 단어 $w = a_1 \cdot a_2 \dots$ 에 대한 출력은 각 생성자 네트워크의 출력을 구조적 연결 (Structural Concatenation, 리스트 연결) 하여 구성합니다. 이는 $D(w_1 \cdot w_2) = D(w_1) \oplus D(w_2)$ 를 만족시킵니다.
3. 2-셀 (2-cells): 군 관계 (예: $bab^{-1} = a^{-1}$ ) 를 만족시키기 위해 학습된 호모토피 (Learned Homotopy) $H$ 를 도입합니다. 이는 한 루프에서 다른 루프로의 연속적인 변형을 학습하는 별도의 MLP 입니다.

나. 아키텍처 분류 (Type-A vs Type-B)

Type-B (함자적 아키텍처): 위와 같이 독립적으로 생성된 세그먼트를 구조적으로 연결합니다. Strict Monoidal Functor로, 모든 파라미터 값에서 구성적 정확성이 보장됩니다.
Type-A (비함자적 아키텍처): Softmax Self-Attention 을 사용하는 기존 모델입니다.
- 이론적 증명 (Theorem 4.1): Softmax Attention 은 비자명한 군 (non-trivial group) 에 대해 어떤 파라미터 설정에서도 함자적일 수 없습니다.
- 이유: Attention 은 토큰의 내용 (content) 에 기반하여 가중치를 계산하므로, 군의 동치 클래스 (예: $ab $와$ ba$ 가 같은 원소를 가지는 경우) 를 구별하지 않고 토큰 순서 자체를 구별합니다. 이는 구성적 의미 보존을 위반합니다.

다. 형식적 검증

모든 핵심 정리 (함자성 보장, Attention 의 비함자성) 는 Cubical Agda를 사용하여 기계적으로 검증 (Formalized) 되었습니다. 이는 학습된 가중치가 아닌 아키텍처 자체의 속성으로 보장을 제공합니다.

3. 주요 기여 (Key Contributions)

HIT 기반 컴파일러: 위상 공간의 대수적 구조 (HIT 명세) 를 자동으로 신경 아키텍처로 변환하는 함자를 제시하여, 구성적 정확성을 '구현 시 (by construction)' 보장합니다.
이론적 증명:
- 구조적 연결을 사용하는 Transport Decoder가 엄격한 단사적 함자 (strict monoidal functor) 임을 증명.
- Softmax Attention이 어떤 파라미터에서도 함자적일 수 없음을 증명 (Theorem 4.1).
실험적 검증: 세 가지 위상 공간 ( $T^2$ , $S^1 \vee S^1$ , Klein Bottle) 에서 Type-B 아키텍처가 Type-A 아키텍처보다 월등히 우수한 성능을 보임을 입증했습니다.

4. 실험 결과 (Results)

세 가지 위상 공간에 대한 실험은 구성적 일반화의 세 가지 수준을 검증합니다.

공간	위상군 ( $\pi_1$ )	특징	결과 (Type-B vs Type-A)
토러스 ( $T^2$ )	$\mathbb{Z}^2$ (가환)	교환 법칙 존재	Type-B 가 Type-A 보다 2~2.7 배 우수. (단순한 회전 제약만으로도 차이 발생)
원의 뒤틀림 ( $S^1 \vee S^1$ )	$F_2$ (비가환 자유군)	순서 중요 ( $ab \neq ba$ )	Type-B 가 Type-A 보다 5.5~10 배 우수. Attention 은 순서 의존성으로 인해 위상적 의미를 완전히 붕괴시킴.
클라인 병 ( $K$ )	$\mathbb{Z} \rtimes \mathbb{Z}$	비자명한 2-cell 관계	학습된 2-cell (H) 이 핵심 역할. 관계가 적용되는 단어 (non-canonical) 에서 Type-B(Homotopy) 가 Transport 보다 1.85 배 (오차 46% 감소) 더 정확함.

길이 외삽 (Length Extrapolation): Type-A 아키텍처는 시퀀스 길이가 길어질수록 오차가 급격히 증가하는 반면, Type-B 는 세그먼트당 오차가 일정하게 유지됩니다.
학습된 2-cell 의 효과: 클라인 병 실험에서, 군 관계 ( $bab^{-1} = a^{-1}$ ) 를 학습하는 2-cell(Homotopy decoder) 을 추가함으로써, 관계가 적용되지 않는 단어에서는 성능 차이가 없으나 관계가 적용되는 단어에서는 오차를 크게 줄였습니다.

5. 의의 및 결론 (Significance)

구성적 일반화의 본질 규명: 신경망이 구성적 일반화에 실패하는 근본 원인이 '학습 능력'이 아니라 'Attention 과 같은 아키텍처의 비함자적 성질'임을 이론적으로 증명했습니다.
검증 가능한 ML 파이프라인: "명세 (HIT 작성) $\rightarrow$ 검증 (Agda 증명) $\rightarrow$ 컴파일 (아키텍처 생성) $\rightarrow$ 학습"의 단계를 통해, 학습된 가중치에 의존하지 않는 수학적 보장을 가진 신경망을 설계할 수 있음을 보여주었습니다.
실용적 적용 가능성: 모듈형 프로그램, 다단계 계획, 분자 구조 등 구성적 구조를 가진 모든 도메인을 HIT 로 명세하고 이를 함자적 아키텍처로 컴파일하여 신뢰성 높은 AI 를 구축할 수 있는 길을 열었습니다.

요약하자면, 이 논문은 위상수학과 범주론 (HIT, 함자) 을 신경망 설계에 적용하여, 기존 Transformer 의 구성적 일반화 실패를 해결하고 수학적으로 보장된 새로운 신경 아키텍처를 제안한 획기적인 연구입니다.