Unraveling Syntax: How Language Models Learn Context-Free Grammars

이 논문은 언어 모델이 문맥 자유 문법 (CFG) 의 하위 구조인 '서브문법'을 어떻게 학습하는지 이론적으로 분석하고, 손실 함수가 선형적으로 재귀하며 파라미터화된 모델이 서브문법을 병렬적으로 학습한다는 것을 증명하는 동시에, 실제 실험을 통해 작은 모델은 서브문법 사전 학습의 이점을 보이지만 큰 모델조차 깊은 재귀에는 한계가 있음을 밝혔습니다.

핵심

이 논문은 거대 인공지능 (LLM) 이 어떻게 언어를 배우는지에 대한 깊은 의문을 던지며 시작합니다. "인공지능이 아이들처럼 먼저 쉬운 문법을 배우고 점점 어려운 것을 배울까, 아니면 모든 것을 한 번에 동시에 배우는 걸까?"라는 질문이죠.

연구자들은 복잡한 언어 규칙을 수학적으로 정의한 문법 (CFG) 을 이용해 이 문제를 파헤쳤습니다. 핵심은 문법이라는 거대한 나무를 작은 가지 (서브문법, Subgrammar) 로 쪼개어 보는 것입니다.

이 논문의 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 문법이라는 거대한 레고 세트

언어 문법 (CFG) 을 상상해 보세요. 마치 거대한 레고 성을 짓는 것과 같습니다.

• 전체 문법: 완성된 거대한 성.
• 서브문법 (Subgrammar): 이 성을 이루는 작은 부품들 (벽, 창문, 지붕) 이나, 성의 특정 층 (1 층, 2 층) 을 의미합니다.

연구자들은 "AI 가 이 거대한 레고 성을 배울 때, 작은 부품부터 하나하나 배우는가, 아니면 성 전체를 한 번에 통째로 이해하는가?"를 연구했습니다.

2. 놀라운 발견: AI 는 '동시 학습'을 한다!

아이들은 보통 먼저 '사과'나 '사과' 같은 간단한 단어를 배우고, 나중에는 복잡한 문장을 배웁니다. 하지만 이 연구에서 작은 AI 모델 (트랜스포머) 을 실험해 보니 놀라운 결과가 나왔습니다.

• 아이의 학습: 계단식 (쉬운 것 → 어려운 것).
• AI 의 학습: 동시 학습 (Parallel Learning).

AI 는 문법의 작은 조각 (서브문법) 하나하나를 따로따로, 그리고 동시에 배우고 있었습니다. 마치 거대한 레고 성을 짓는 데, 벽돌 하나하나를 동시에 쌓아 올리는 것처럼요. 이론적으로 증명된 바에 따르면, AI 가 배우는 '손실 (오차)'이라는 것은 각 작은 부품 (서브문법) 의 오차들을 모두 더한 것과 같습니다. 그래서 AI 는 모든 부품을 한꺼번에 최적화하는 경향이 있습니다.

3. '미리 공부' (프리트레이닝) 의 효과: 작은 아이에게는 도움이 되지만...

연구자들은 "먼저 작은 문법 (서브문법) 만 가르치고, 그다음에 전체 문법을 가르치면 (커리큘럼 학습) 더 잘 배우지 않을까?"라고 궁금해했습니다.

• 작은 모델 (초보 학생): 미리 작은 문법을 배우게 했더니, 최종 점수가 올라갔습니다. 마치 수학 문제를 풀 때 먼저 덧셈을 완벽하게 익히고 나눗셈을 배운 것처럼요.
• 큰 모델 (고수 학생): 이미 머리가 좋은 큰 모델은 미리 공부하든 말든, 처음부터 다 배우든 최종 점수는 비슷했습니다.

하지만 흥미로운 점은, 내부적인 생각 (표현) 이 달라졌다는 것입니다. 미리 공부한 모델은 문법의 구조를 더 명확하게 이해하고 있었습니다. 마치 레고 부품을 분류해 둔 상자를 가진 것과 같아서, 전체 성을 지을 때 부품을 찾는 속도가 훨씬 빨라진 것입니다.

4. AI 의 한계: '깊이'가 문제지 '길이'가 아니다

가장 중요한 결론 중 하나는 AI 가 문장의 길이는 잘 처리하지만, 문법의 깊이 (중첩된 구조) 에는 여전히 약하다는 것입니다.

• 비유: 긴 줄을 밧줄로 묶는 것 (길이) 은 쉽지만, 밧줄을 여러 번 겹겹이 감아 복잡한 매듭을 만드는 것 (깊이/재귀) 은 AI 가 어려워합니다.
• 실험 결과: 아주 간단한 괄호 문법 ( ( ( ... ) ) ) 에서, 괄호의 깊이가 깊어질수록 AI 는 실수를 하기 시작했습니다. 최신 거대 모델 (GPT 등) 도 이 '깊이' 문제에서는 여전히 고전하고 있었습니다.

5. 요약: 이 논문이 우리에게 주는 메시지

1. AI 는 아이와 다릅니다: AI 는 쉬운 것부터 배우지 않고, 문법의 모든 조각을 동시에 배우는 경향이 있습니다.
2. 작은 모델은 '미리 공부'가 효과적: 아주 작은 AI 에게는 단계별 학습 (커리큘럼) 이 도움이 되지만, 큰 AI 에겐 큰 차이가 없습니다.
3. 깊은 생각은 아직 어렵다: AI 는 긴 문장은 잘 읽지만, 문장 안의 복잡한 중첩 구조 (깊은 재귀) 를 이해하는 데는 한계가 있습니다. 이는 AI 가 단순히 패턴을 맞추는 것이지, 진짜 문법 구조를 완벽하게 이해하지는 못함을 시사합니다.

한 줄 결론:
AI 는 거대한 언어 문법을 '조각조각'으로 나누어 동시에 배우는 천재이지만, 그 조각들이 너무 깊게 겹쳐진 복잡한 구조 앞에서는 여전히 인간의 두뇌처럼 유연하게 생각하지 못하는 '약점'을 가지고 있습니다.

기술 요약

1. 연구 배경 및 문제 제기 (Problem)

대규모 언어 모델 (LLM) 은 놀라운 성능을 보이지만, 그 학습 역학 (learning dynamics) 과 문법 구조를 어떻게 습득하는지에 대한 이해는 여전히 부족합니다. 특히 다음과 같은 두 가지 주요 미해결 과제가 존재합니다.

• 학습 역학의 부재: 훈련된 모델의 정적 표현 (static representations) 이나 논리는 연구되었으나, 모델이 언어를 어떻게 습득하는지 (학습 과정) 에 대한 연구는 부족합니다.
• 문법의 하위 구조 (Substructure) 무시: 문맥 자유 문법 (CFG) 을 연구하는 기존 연구들은 CFG 가 수학적으로 '하위 문법 (subgrammars)'으로 분해될 수 있다는 점과, 학습이 이 하위 구조와 어떻게 상호작용하는지를 고려하지 않았습니다.

이 논문은 CFG 의 하위 구조, 즉 **'하위 문법 (subgrammars)'**을 중심으로 언어 모델링의 역학을 분석하여 이 격차를 해소하고자 합니다.

2. 방법론 및 정의 (Methodology & Definitions)

저자들은 CFG 의 하위 구조를 정의하고, 이를 언어 모델링 손실 (loss) 과 연결하는 이론적 프레임워크를 구축했습니다.

2.1. 하위 문법의 정의

CFG 의 하위 구조를 두 가지 유형으로 정의했습니다.

• 내부 하위 문법 (Inner Subgrammar): CFG 유도 (derivation) 트리의 부분 트리에 해당합니다. 비단말 기호 (non-terminal) 에서 생성될 수 있는 부분 문자열들의 문법입니다.
• 외부 하위 문법 (Outer Subgrammar): CFG 규칙의 부분 집합을 유지하여 생성된 언어의 단순화된 버전입니다. 상위 문법 (supergrammar) 의 부분 집합을 포함합니다.

2.2. 이론적 기반

• 손실의 분해 (Decomposition): 언어 모델링 손실 (KL 발산) 이 하위 문법 구조에 대해 어떻게 분해되는지 증명했습니다.
• 재귀적 관계: 손실이 하위 문법의 손실의 합으로 선형적으로 재귀됨을 보였습니다.
• 기대 재귀 (Expected Recursion): 재귀의 깊이가 손실의 발산 (blow-up) 에 미치는 영향을 분석했습니다.

3. 주요 기여 및 이론적 결과 (Key Contributions & Theoretical Results)

3.1. 손실의 재귀적 분해 정리 (Theorem 4.3 & 4.6)

• 선형 재귀: 언어 모델링 손실 (또는 KL 발산) 은 최상위 하위 문법들에 대해 선형적으로 재귀합니다. 이를 반복 적용하면 손실은 '환원 불가능한 (irreducible)' 하위 문법들의 손실로 분해됩니다.
• 기대 재귀의 역할: 이 선형 재귀의 상수는 **기대 재귀 (expected recursion, $E[R]$)**의 함수임을 증명했습니다.
  • 공식: $DKL(P_G \| Q_\theta) = \frac{\sum DKL(P_{A_i} \| Q_\theta(A_i))}{1 - E[R]}$
  • 만약 기대 재귀가 1 이상이면 KL 발산이 무한대로 발산합니다 (학습이 불가능해짐).
  • 재귀가 깊어질수록 (기대 재귀가 1 에 가까워질수록) 모델이 문법을 학습하기 어려워짐을 수학적으로 보였습니다.

3.2. 병렬 학습 (Parallel Learning)

• 이론적 조건: 특정 조건 (모델이 하위 문법에 대해 '문맥 무감각 (context-insensitive)'하고, 하위 문법 간의 학습이 서로 방해하지 않는 경우) 하에서, 모델은 모든 하위 문법을 병렬로 학습함을 증명했습니다 (Corollary 4.7).
• 실증적 발견: 실험 결과, 작은 Transformer 모델들은 CFG 를 학습할 때 복잡한 문법보다 단순한 하위 구조를 먼저 마스터하는 것이 아니라, 모든 하위 문법을 동시에 (병렬로) 학습하는 경향을 보였습니다. 이는 어린이의 언어 습득 과정 (단순 구조에서 복잡 구조로 점진적 학습) 과는 대조적입니다.

4. 실험 결과 (Empirical Results)

4.1. 손실 분해 시각화

• 다양한 하위 문법 구조를 가진 합성 CFG 로 작은 Transformer 를 훈련시켰습니다.
• 훈련 과정에서 전체 KL 발산이 각 하위 문법에 대한 손실의 합으로 정확히 분해됨을 확인했습니다.

4.2. 커리큘럼 학습 및 프리트레이닝 (Subgrammar Pretraining)

• 작은 모델: 하위 문법으로 먼저 프리트레이닝한 후 전체 문법으로 훈련하면, 최종 성능 (손실) 이 향상되었습니다.
• 큰 모델: 모델 크기가 커질수록 프리트레이닝의 성능 향상 효과는 감소했으나, **내부 표현 (internal representations) 의 정렬 (alignment)**에는 긍정적 영향을 미쳤습니다.
• CKA 분석: 프리트레이닝된 모델은 하위 문법 문자열과 비하위 문법 문자열을 내부적으로 더 잘 구분하며, 문법의 하위 구조를 더 잘 반영하는 표현을 학습했습니다.

4.3. 재귀 깊이 (Recursion Depth) 의 한계

• 깊이 vs 길이: 모델은 문장의 '길이'에는 강하지만, '재귀의 깊이 (depth)'에는 약함을 보였습니다.
• 실험: 중괄호 (Nested Parentheses) 나 산술 표현식 테스트에서, 깊이가 깊어질수록 모델의 예측 오류가 급격히 증가했습니다.
• LLM 의 한계: GPT-5.1 과 같은 최신 모델조차도 깊은 재귀 구조 (depth 7 이상) 를 가진 산술 문제를 풀 때 실패하는 경향을 보였습니다. 이는 모델이 문법 규칙을 완전히 내재화하지 못했거나, 최적화 과정에서 깊은 재귀를 처리하는 가중치 설정을 찾지 못했음을 시사합니다.

5. 의의 및 결론 (Significance & Conclusion)

1. 이론적 통찰: 언어 모델링 손실이 CFG 의 하위 구조에 따라 어떻게 분해되는지에 대한 근본적인 정리를 제공했습니다. 이는 모델이 문법을 학습하는 메커니즘을 이해하는 새로운 렌즈를 제시합니다.
2. 학습 역학의 발견: Transformer 모델이 하위 문법을 병렬로 학습한다는 사실을 발견하여, 기존에 가정되었던 점진적 학습 (단순 $\to$ 복잡) 과는 다른 학습 역학을 규명했습니다.
3. 최적화 전략: 하위 문법 기반 프리트레이닝이 작은 모델의 성능 향상과 내부 표현의 구조적 정렬에 기여함을 보였습니다.
4. 현존 모델의 한계: 현재의 언어 모델 (LLM 포함) 이 깊은 재귀 (deep recursion) 를 처리하는 데 본질적인 어려움을 겪고 있음을 확인했습니다. 이는 모델의 표현 능력 (representational capacity) 이 아닌, 경사 하강법 (gradient descent) 을 통한 최적화의 한계일 가능성이 높음을 시사합니다.

이 논문은 언어 모델이 문법 구조를 어떻게 이해하고 학습하는지에 대한 이론적, 실증적 토대를 마련하며, 특히 재귀적 구조 학습의 한계와 하위 구조 학습의 병렬성에 대한 중요한 통찰을 제공합니다.