Algebraic Decomposition Theory for Transformer Length Generalization

트랜스포머가 학습 때보다 긴 입력에도 버티는지(길이 일반화)를 정규 언어(규칙 기반 문자열 문제) 대상으로 수학적으로 완전히 규명하고, 다항 시간 판정 알고리즘까지 만든 이론 논문.

이 논문은 한마디로 '트랜스포머가 어떤 문제에서는 입력이 길어져도 잘하고, 어떤 문제에서는 급격히 망가지는지'를 수학으로 완전히 설명한 이론 연구다. 저자들은 C-RASP(트랜스포머가 배울 수 있는 프로그램의 종류를 표현하는 형식 도구)에 속하는 정규 언어에서만 길이 일반화가 일어남을 증명하고, 임의의 정규 언어가 여기 속하는지 다항 시간에 판정하는 알고리즘을 만들었다. 돌파구는 기존 유한 대수 이론(크론-로즈 분해)이 안 되던 걸 정수의 무한 덧셈 군을 쓰는 새 분해 이론으로 푼 것이다. GPT-2로 125개 정규 언어를 실험한 결과 이론 예측이 실제 길이 일반화 성패를 정확히 맞췄다.

핵심 요약

• 구조가 거의 같아 보이는 두 문제도 길이 일반화가 되는 쪽과 안 되는 쪽으로 갈리는데, 기존 이론은 이 차이를 설명하지 못했다. 이 논문이 처음으로 완전한 판정 기준을 줬다.
• 판정 알고리즘이 다항 시간에 돈다. 이론에 그치지 않고 실제로 확인 가능한 도구를 준 셈이다.
• 핵심 발견은 '무한히 세는 능력(unbounded counting)'이 트랜스포머 길이 일반화의 씨앗이라는 것. 이를 정수 덧셈 군의 반복 wreath product로 형식화했다.
• GPT-2를 길이 50까지 학습시키고 최대 500까지 테스트했더니, C-RASP 안의 언어는 정확도를 유지하고 밖의 언어는 훈련 길이 직후 급락했다.
• JSON 같은 구조화 출력과 에이전트의 상태 추적이 길어지면 왜 무너지는지 이해하는 이론적 기초를 준다.

논문 링크

외부 연구를 정리한 자료입니다. HDATF가 발표한 논문이나 제품 성능을 측정한 결과는 아닙니다.