기술 요약: 유한 깊이 문법을 통한 딥 트랜스포머의 계층적 모델링 표현력 분석

문제 정의

딥 뉴럴 네트워크, 특히 트랜스포머는 계층적 표현을 형성함으로써 추상적이고 구성적인 특징을 포착하는 능력을 통해 표현력을 얻는다는 점이 경험적으로 관찰됩니다. 언어 모델링에서 초기 트랜스포머 레이어는 국소적인 구문 패턴을 포착하는 반면, 후기 레이어는 복잡한 절 수준의 의존성을 인코딩합니다. 이러한 직관은 모델 설계의 근간이 되고 있음에도 불구하고, 딥 트랜스포머가 어떻게 이러한 계층 구조를 표현하는지에 대한 엄밀한 이론적 연구는 부족한 실정입니다.

기존의 이론적 분석은 디크 언어(Dyck languages, 균형 잡힌 괄호)나 유한 상태 오토마타와 같이 제한된 설정에 집중하는 경우가 많으며, 이는 실제 문법이 가진 복잡한 분기 구조를 반영하지 못합니다. 또한, 기존 연구들(예: Allen-Zhu & Li, 2025; Saglam et al., 2025)은 "선형 표현 가설(linear representation hypothesis)"을 지지하며 추상적인 문법 상태가 잔차 연결(residual stream)을 통해 선형 프로브로 회복될 수 있음을 보여주었으나, 트랜스포머 아키텍처가 왜 이러한 복잡한 구조를 저차원의 선형 분리 가능한 부분 공간으로 명시적으로 인코딩할 수 있는 구조적 역량을 갖추고 있는지에 대해서는 이론적으로 설명하지 못했습니다.

본 논문은 **유한 깊이의 비재귀적 문맥 자유 문법(bounded-depth, non-recursive CFGs)**이라는 형식적 관점을 통해 딥 트랜스포머 모델의 표현력을 분석함으로써 이 간극을 메우고자 합니다. 목표는 이러한 문법을 예측적으로 모델링할 수 있는 트랜스포머의 명시적 구성을 제공하여, 계층적 구성성(hierarchical compositionality)의 메커니즘을 공식화하는 것입니다.

방법론

저자들은 다음과 같은 속성을 가진 특정 클래스의 CFG를 사용하여 문제를 정형화합니다:

• 고정 깊이 ($d$): 모든 유도 트리(derivation tree)의 높이는 정확히 $d$입니다.
• 비재귀성: 이 문법들은 유한 언어를 생성하며, 무한한 중첩을 피합니다.
• 균일성: 특정 비단말 기호(non-terminal)에 대한 생성 규칙은 동일한 길이를 가집니다.
• 제한된 파라미터: 분석은 최대 규칙 수($M$), 최대 분기 계수($B$), 그리고 유효한 유도 트리 형태의 수($c = |C(G)|$)를 고려합니다.

저자들은 이러한 문법을 모델링하기 위해 위치 주의 집중(positional attention) 메커니즘을 갖춘 디코더 전용 트랜스포머를 구축합니다. 이 구성은 세 가지 핵심 요소에 기반합니다:

1. 희소 어텐션 헤드(Sparse Attention Heads): 모델은 어텐션 가중치가 내용이 아닌 토큰 위치에만 의과하는 단순화된 상대적 위치 주의 집중 메커니즘을 활용합니다. 이를 통해 유도 트리 내의 특정 토큰을 위치에 따라 선택하는 "하드(hard)" 어텐션을 구현합니다.
2. 계층적 처리: 트랜스포머의 깊이는 문법의 깊이($d$)에 따라 선형적으로 증가합니다. 각 트랜스포머 블록은 문법적 계층의 한 레벨에 대응하며, 리프 노드(단말 기호)에서 루트 노드(시작 기호)까지 구성 성분을 처리합니다.
3. 피드포워드 암기(Feedforward Memorization): 위치별 피드포워드 네트워크(FFN)는 이산적인 룩업 테이블 역할을 하도록 구축됩니다. 신경망의 암기 능력에 관한 결과(Zhang et al., 2017)를 사용하여, 이 레이어들은 집계된 국소적 구문 맥락을 부모 비단말 기호로 매핑합니다.

이 구성은 다음과 같은 바텀업 동적 계획법 알고리즘(CKY 파서와 유사)을 구현합니다:

• 어텐션 헤드는 문법적 구성 성분의 경계를 식별하기 위해 자식 노드들의 국소적 구문 맥락을 집계합니다.
• FFN은 결과물인 부모 비단말 기호를 잔차 연결을 통해 잔차 스트림에 인코딩하며, 하위 레벨의 상태를 보존합니다.
• 최종 레이어는 축적된 계층적 상태를 바탕으로 유효한 다음 단어 예측을 계산하기 위해 스택된 피드포워드 네트워크를 활용합니다.

주요 기여

1. 명시적 트랜스포머 구성: 본 논문은 깊이 $d$인 트랜스포머가 깊이 $d$인 균일 비재귀적 CFG를 예측적으로 모델링할 수 있다는 구성적 증명을 제공합니다.
2. 확장성 경계: 저자들은 필요한 모델 크기에 대한 구체적인 경계를 도출했습니다:
   • 깊이: 문법의 깊이($d$)에 따라 선형적으로 증가합니다.
   • 뉴런 수: 유도 트리 형태의 수($c$)에 선형적으로, 생성 규칙의 수($M$)에는 이차적으로 비례합니다.
   • 은닉 차원: $c \cdot d$에 비례합니다.
3. 선형 표현에 대한 이론적 지지: 이 구성은 아키텍처가 추상적인 문법 상태를 잔차 스트림 내의 저차원 선형 분리 가능한 부분 공간으로 인코딩할 수 있는 구조적 역량을 갖추고 있음을 입증합니다. 구체적으로, 고정된 유도 트리 형태에 대해 파싱 계산은 별개의 부분 공간에서 수행되므로, 단순한 아핀 변환을 통해 비단말 기호를 격리할 수 있습니다.
4. 기존 연구와의 차별점: 문장의 최대 길이(문법 깊이에 따라 지수적으로 증가할 수 있음)에 따라 확장되는 기존의 경계들과 달리, 이 구성은 문법의 깊이 자체에 따라 확장됩니다. 이는 딥 CFG를 위한 평면적 표현(n-gram이나 유한 상태 오토마타 등)보다 계층적 모델링이 갖는 효율성을 강조합니다.

결과

주요 이론적 결과(정리 4.1)는 임의의 $\epsilon > 0$에 대하여, 언어 $L(G)$를 오차 $\epsilon$ 이내로 예측적으로 모델링하는 트랜스포머 언어 모델 $f_T$가 존재함을 확립합니다. 이 모델은 $d$개의 트랜스포머 블록과 그 뒤를 잇는 $5d + 7$개의 피드포워드 레이어로 구성됩니다.

• 효율성: 필요한 레이어의 수는 문법 깊이에 선형적이므로, 문장 길이에 따라 레이어 수가 증가하는 기존 구성들에 비해 상당한 개선을 보여줍니다.
• 희소성: 이 구성은 각 입력 시퀀스가 각 블록당 하나의 어텐션 헤드에 의해 처리되는 희소 회로를 활용하며, 이는 딥 러닝의 희소 계산 서브그래프에 대한 경험적 발견과 일치합니다.
• 선형 분리 가능성: 증명은 주어진 깊이의 비단말 기호들이 해당 잔차 스트림의 부분 공간 내 벡터로 매핑됨을 보여주며, 이는 선형 표현 가설을 뒷받침합니다. 다만, 저자들은 자신들의 구성이 엄격한 직교 기저(distinct indicator neurons)를 사용하는 반면, 실제 모델은 밀집된 중첩(dense superposition)을 통해 이를 달성할 가능성이 높다고 언급했습니다.

의의 및 한계

의의:
본 논문은 딥 트랜스포머가 계층적 문법 구조를 명시적으로 표현할 수 있다는 엄밀한 존재 증명을 제공합니다. 이는 선형 표현에 대한 경험적 관찰과 이론적 아키텍처 역량 사이의 간극을 메워줍니다. 트랜스포머가 어떻게 바텀업 동적 계획법을 구현할 수 있는지 정형화함으로써, 본 연구는 왜 더 깊은 아키텍처가 평면적 모델의 "차원의 저주"를 겪지 않고 복잡한 언어 구조를 포착하는 데 효과적인지에 대한 이론적 토대를 제공합니다.

한계:

• 단순화된 프레임워크: 분석이 유한 깊이의 비재귀적 CFG로 제한되어 있습니다. 이는 재귀적 문법이나 무한 언어를 직접 다루지는 않지만, 계층적 구성성을 분석하기 위한 추상화로서의 프레임워크임을 명시하고 있습니다.
• 직교성 대 중첩(Orthogonal vs. Superposition): 이론적 구성은 각 문법 상태가 전용 뉴런을 갖는 직교 기저 공간에 의존합니다. 이는 증명을 단순화하지만, 특징들이 밀집된 벡터로 압축되는 실제 모델에서 관찰되는 "중첩" 현상을 설명하지는 못합니다. 표준적인 학습 역학이 어떻게 이러한 압축된 표현을 생성하는지는 여전히 미해결 과제로 남아 있습니다.
• 실제 코퍼스로의 확장성: 경계값은 $c$(트리 형태의 수)에 의존하며, 이 값은 매우 커질 수 있습니다. 본 프레임워크가 핵심 메커니즘을 정형화하기는 하지만, Penn Treebank와 같은 복잡한 실제 코퍼스에 대해 타이트한 경계를 제공하지는 못한다는 점을 저자들도 인정하고 있습니다.

결론적으로, 이 연구는 형식 언어 이론을 통해 트랜스포머 모델의 내부 작동 원리를 이해하기 위한 기초를 마련하며, 트랜스포머의 깊이가 모델링하는 문법 계층의 깊이를 자연스럽게 반영한다는 점을 시사합니다.