기술 요약: 신경-기호적 구문 분석: CYK 알고리즘을 통한 신경망의 형상화

문제 정의

본 논문은 현재의 대규모 언어 모델(LLM) 및 트랜스포머 기반 아키텍처가 가진 근본적인 한계, 즉 훈련 데이터로부터 복잡한 알고리즘적 지식을 안정적으로 학습하고 외삽(extrapolate)하는 능력이 부족하다는 점을 다룹니다. 트랜스포머는 단순한 작업에서는 '그로킹(grokking, 과적합을 넘어선 일반화)' 현상을 보이지만, Cocke-Younger-Kasami(CYK)와 같은 복잡한 파싱 알고리즘을 처음부터 학습하는 것과 같은 고난도의 알고리즘 일반화에는 어려움을 겪습니다. 저자들은 트랜스포머가 알려진 알고리즘을 데이터로부터 순수하게 발견하기를 기대하는 것은 과도한 기대이며, 이 모델들이 알고리즘 엔진이라기보다는 단순히 "거대한 언어 메모리"로서 기능하는 경우가 많다고 주장합니다. 핵심 문제는 알려진 알고리즘을 단순히 거대한 규모와 훈련을 통한 수동적인 능력의 발현에 의존하는 것이 아니라, 행렬-벡터 곱셈에 의해 제어되는 신경망 아키텍처 내에 직접 인코딩할 수 있는지 여부입니다.

방법론

저자들은 CYK 알고리즘을 신경망 프레임워크에 직접 주입하도록 설계된 단순 순환 신경망 아키텍처인 CYKNN을 제안합니다. 이 방법론은 세 가지 핵심 요소에 의존합니다:

1. 홀로그래픽 축소 표현(Holographic Reduced Representations, HRRs): 2차원 CYK 파싱 테이블과 기호적 문법 규칙을 인코딩하기 위해 저자들은 HRR을 활용합니다. 이 프레임워크에서 기호는 무작위 벡터로부터 유도된 행렬로 표현됩니다. 이러한 표현의 특정 속성은 기호와 그 역(예: $[a]^\oplus$ 와 $[a]^\ominus$)이 행렬 곱셈에서 서로 상쇄되어 항등 행렬에 근사한다는 점입니다. 이를 통해 기호의 시퀀스를 마치 테트리스 조각처럼 대수적으로 조작할 수 있는 "전체론적(holistic)" 연산이 가능해집니다.

2. 행렬 연산을 통한 알고리즘 주입:

   • 표현(Representation): CYK 테이블 셀 $P[i, j]$는 분산된 행렬로 표현됩니다. 문법 규칙(예: $A \to BC$)은 비단말 기호(non-terminals)의 역행렬과 정방향 표현으로부터 구축된 가중치 행렬($W$)로 인코딩됩니다.
   • 전체론적 업데이트(Holistic Update): 테이블 셀을 하나씩 채우기 위해 루프를 반복하는 대신(고전적인 $O(n^3)$ CYK 알고리즘처럼), 저자들은 업데이트 단계를 단일 행렬-벡터 곱셈 $P' = PRP$로 공식화합니다. 여기서$P$는 현재 테이블의 상태이고,$R$은 문법 규칙을 인코딩합니다. 이 연산은 이론적으로 구성 성분들을 병렬로 결합하는 로직을 수행합니다.
   • 정교화(Refinement): $O(n^3)$ 복잡도를 단일 연산으로 압축하면서 발생하는 근사 오류를 완화하기 위해, 아키텍처에는 **대각선 디코더(Diagonal Decoder, Dd)**가 포함됩니다. 이 모듈은 분산된 행렬에서 특정 대각선 정보를 추출하여 신호를 정제하고, 이를 다시 순환 루프로 피드백하여 정교화합니다.

3. 아키텍처 (CYKNN): 네트워크는 다음으로 구성됩니다:

   • 홀로그래픽 인코더 (Holographic Encoder, He): 입력 토큰을 초기 행렬 $P_0$로 변환합니다.
   • 단항 모듈 (Unary Module, U): 첫 번째 대각선을 초기화하기 위해 단항 문법 규칙을 적용합니다.
   • 이항 모듈 (Binary Module, B): 이항 규칙 적용을 전파하기 위해 핵심 연산인 $P_{i+1} = P_i R_B P_i$를 구현합니다.
   • 대각선 디코더 (Diagonal Decoder, Dd): 분산된 행렬로부터 기호적 내용을 추출하고 정제합니다.

주요 기여

• 직접적인 알고리즘 주입: 본 논문은 알려진 알고리즘(CYK)이 데이터로부터 암시적으로 학습되는 것이 아니라, 신경망 아키텍처에 명시적으로 형상화될 수 있음을 보여주는 새로운 신경-기호적 방법론을 제시합니다.
• 선형 대수를 통한 전체론적 추론: 저자들은 동적 계획법(파싱 테이블을 채우는 과정)의 반복적 로직이 HRR의 특성을 활용하여, 단 한 번의 연산으로 데이터의 상태를 변화시키는 전체론적 행렬-벡터 곱셈으로 변환될 수 있음을 보여줍니다.
• 알고리즘 작업에서의 우수한 성능: 제안된 CYKNN은 훨씬 더 큰 규모(20B+ 파라미터)이거나 LoRA로 미세 조정된 기존의 최첨단 LLM들보다 특정 CYK 파싱 작업에서 더 뛰어난 성능을 보였습니다.

실험 결과

저자들은 CYKNN을 두 가지 클래스의 트랜스포머 기반 모델과 비교 평가했습니다:

1. 미세 조정 모델 (Fine-tuned Models): CYK 작업에 대해 LoRA로 미세 조정된 Qwen2.5-1.5B 및 Qwen3-8B.
2. 인컨텍스트 러닝 (In-Context Learning, ICL) 모델: 몇 개의 예시(few-shot)가 포함된 프롬프트가 주어진 gpt-oss-20B 및 Gemma-27B.

결과:

• CYKNN의 우위: 특히 올바른 문법 규칙으로 초기화되었을 때, CYKNN은 작은 시퀀스(길이 5-8)와 전체 테스트 세트 모두에서 비교된 모든 LLM보다 현저히 높은 F-measure 점수를 달 기록했습니다.
• LLM의 한계: 미세 조정된 Qwen 모델들은 알고리즘 구조를 학습하기보다는 접두사 연관성(prefix associations)을 암기하는 경향이 있어 성능이 저조했습니다. 이들은 매우 긴 시퀀스(>12 토큰)에서만 무작위 초기화된 CYKNN보다 높은 성능을 보였는데, 이는 이들이 알고리즘을 유도(inducing)하지 못했음을 시사합니다. 인컨텍스트 러닝 모델은 높은 정밀도(precision)를 보였으나 재현율(recall)이 낮았으며, 이는 테이블을 채우는 데 있어 알고리즘적이지 않고 보수적인 접근 방식을 취하고 있음을 나타냅니다.
• 초기화 민감도: CYKNN의 성능은 문법 행렬의 초기화에 크게 의존했습니다. 무작위 초기화는 낮은 성능을 보인 반면, 특정 문법 규칙으로 초기화했을 때는 높은 정확도로 수렴할 수 있었습니다.
• 일반화: 시퀀스 길 변화에 어려움을 겪는 트랜스포머와 달리, CYKNN은 더 복잡한 문법에서도 성능을 유지하며 시퀀스 길이에 대해 더 직관적인 동작을 보여주었습니다.

의의 및 주장

본 논문은 신경-기호적 방법론의 다른 방향을 제시한다고 주장합니다. 저자들은 알고리즘이 이미 알려져 있다면, 거대한 트랜스포머의 "창발적 능력"에 의존하는 대신, 이러한 알고리즘을 신경 아키텍처에 직접 인코딩하는 것이 실행 가능한 대안임을 강조합니다.

그 의의는 다음과 같습니다:

1. 알고리즘이 아키텍처를 형성할 수 있음: 신경망은 단순히 통계적 패턴을 학습하는 것을 넘어, 행렬-벡터 연산을 통해 특정 알고리즘 로직(CYK)을 체화하도록 설계될 수 있습니다.
2. 신경-기호적 작업의 효율성: 엄격한 알고리즘 준수가 필요한 작업(파싱과 같은)의 경우, 특화되고 알고리즘적으로 형상화된 네트워크가 수십억 개의 파라미터를 가진 범용 대규모 LLM보다 더 뛰어난 성능을 발휘할 수 있습니다.
3. '그로킹'에 대한 대안: 본 논문은 복잡한 알고리즘 작업에 대해 트랜스포머가 데이터로부터 해결책을 '그로킹'하기를 기다리는 것은 비효합적이고 종종 성공하기도 어렵다는 점을 시사하며, 알고리즘 구조를 명시적으로 주입하는 것이 더 견고한 경로임을 제안합니다.

저자들은 사용된 문법이 단순하고 현재의 구현이 계산적으로 최적화되지 않았음을 인정하면서도, 문법의 단순함만으로도 현재의 트랜스포머 기반 LLM들의 한계를 드러내기에 충분했다고 주장합니다.