💬 NLP

Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth

본 논문은 회로 복잡성, 근사 이론, 통신 복잡성이라는 세 가지 이론적 관점을 종합하여 트랜스포머가 기호 계산 및 이산 추론 과제를 수행할 때 직면하는 구조적·계산적 한계를 명확히 규명하고, 이를 극복하기 위한 향후 방향을 제시합니다.

원저자: Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros, Yassine Benajiba

게시일 2026-02-13

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros, Yassine Benajiba

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

변형기 (Transformer) 가 왜 '논리 퀴즈'를 못 풀까?

(심층 분석: 깊이, 정확도, 정보 전달의 한계)

이 논문은 최근 AI 의 핵심인 '변형기 (Transformer)' 모델이 왜 수학 계산이나 논리 추론 같은 **'정확한 규칙이 필요한 작업'**에서는 자주 실패하는지, 그 근본적인 이유를 세 가지 관점에서 설명합니다.

AI 가 시나리오를 요약하거나 글을 쓰는 것은 잘하지만, "1234 + 5678 을 계산해"나 "A 가 B 이고 B 가 C 면 A 는 C 인가?" 같은 딱딱한 논리 문제는 왜 잘 못 할까요? 이 논문은 그 답을 건축물, 부드러운 점토, 메시지 전달 게임이라는 세 가지 비유로 설명합니다.

1. 건축물의 높이 제한 (회로 복잡성: Circuit Complexity)

비유: "층수가 고정된 빌딩"

변형기 모델은 여러 층 (Layer) 으로 된 빌딩과 같습니다.

문제: 현재 AI 는 빌딩의 층수가 고정되어 있습니다. 예를 들어 32 층짜리 빌딩을 만들었다고 칩시다.
한계: 만약 어떤 문제를 풀기 위해 100 단계의 사고가 필요하다면? 32 층만으로는 그 사고를 끝까지 이어갈 수 없습니다.
결과: AI 는 복잡한 논리 문제를 풀 때, 중간에 사고가 끊어지거나 (층이 부족해서) 단순한 패턴만 기억하려 합니다. 마치 32 층 빌딩에서 100 층까지 올라가야 하는 사람을 위해 계단을 만들지 않은 것과 같습니다.
해결책: 사고를 한 번에 끝내지 말고, '생각의 메모 (Chain of Thought)'를 종이에 적어가며 단계를 나누어 풀면 (층을 더 늘리는 효과) 훨씬 잘 풀립니다.

2. 부드러운 점토 vs 날카로운 칼 (근사 이론: Approximation Theory)

비유: "부드러운 점토로 날카로운 칼날 만들기"

변형기 모델은 학습 과정에서 **'부드러운 곡선'**을 그리도록 훈련됩니다.

문제: 수학이나 논리는 '0 아니면 1'처럼 갑자기 뚝 끊기는 (불연속적인) 규칙이 많습니다. (예: 9+1=10 이 되자마자 자리수가 바뀌는 것)
한계: AI 는 이 뚝 끊기는 부분을 부드럽게 이어주려고 합니다. 마치 날카로운 칼날을 부드러운 점토로 덮으려다 칼날이 무뎌지는 것과 같습니다.
결과: 작은 실수가 하나 생기면, 그 실수가 다음 단계로 넘어가며 기하급수적으로 커집니다. (예: 100 번의 덧셈을 할 때, 첫 번째 자리에서 0.001 의 오차가 생기면 100 번째 자리에서는 큰 오차로 변함)
결론: AI 는 "대략 9.999999"라고 답할 수는 있어도, "정확히 10"이라고 확신하기 어렵습니다.

3. 좁은 통로와 긴 줄 (전송 복잡성: Communication Complexity)

비유: "긴 줄에서 메시지를 전달하는 게임"

변형기는 문장 속 모든 단어가 서로 대화할 수 있게 만들어졌습니다. 하지만 이 대화에는 제한이 있습니다.

문제: 문장이 매우 길 때, 문장의 **시작 부분 (A)**과 **끝 부분 (B)**의 정보를 연결해야 한다고 칩시다.
한계: AI 는 한 번의 대화 (Layer) 에서 정보를 전달할 수 있는 '대역폭 (정보량)'이 정해져 있습니다. 그리고 층이 고정되어 있으니, 정보를 전달할 수 있는 '대화 횟수'도 정해져 있습니다.
결과: 정보가 A 에서 B 로 가려면 중간에 수많은 단어 (filler) 를 거쳐야 하는데, 정보가 너무 길어지거나 중간에 섞이면 (메시지가 왜곡되거나) 중요한 정보가 사라집니다.
비유: 긴 줄에서 "내 이름은 김철수야"라는 말을 처음 사람에서 마지막 사람까지 전달할 때, 중간에 100 명이 끼어 있다면 마지막 사람은 "김철수"가 아니라 "김... 철... 수?"라고 기억할 확률이 높습니다.

📝 요약: 왜 AI 는 논리 퀴즈를 못 할까?

이 세 가지 비유가 합쳐지면 다음과 같은 결론이 나옵니다.

층이 부족해서: 복잡한 문제를 한 번에 끝내지 못함.
부드러워서: 딱딱한 규칙 (0 또는 1) 을 정확히 구분하지 못함.
정보가 흐려져서: 긴 문장 속의 중요한 연결 고리를 놓침.

🚀 앞으로의 해결책은?

이 논문은 단순히 "AI 를 더 크게 만들면 (데이터를 더 많이 주면)" 해결될 문제가 아니라고 말합니다. 대신 다음과 같은 새로운 접근이 필요하다고 제안합니다.

뇌 + 컴퓨터의 결합: AI 의 직관 (패턴 인식) 과 컴퓨터의 정확한 계산 능력을 섞는 '뉴로 - 심볼릭 (Neuro-symbolic)' 모델 개발.
메모리 활용: 생각할 때 종이에 적듯이, 외부 메모리를 써서 정보를 저장하고 다시 불러오는 방식.
경계 인식: "여기는 0 이고 저기는 1 이다"라는 딱딱한 경계를 인식하도록 훈련하는 새로운 방법.

한 줄 요약:

"현재 AI 는 '감'과 '유추'는 천재지만, '정확한 계산'과 '엄격한 논리'는 약합니다. 이를 고치려면 단순히 크기를 키우는 게 아니라, **건축 구조를 바꾸고 (층수 증가), 계산 방식을 다듬고 (정확도 향상), 정보 전달 방식을 개선 (메모리 활용)**해야 합니다."

1. 문제 제기 (Problem)

변환기 (Transformer) 아키텍처는 자연어 처리, 비전 등 다양한 시퀀스 모델링 분야에서 획기적인 성과를 거두었으나, 이산적 추론 (Discrete Reasoning) 작업에서는 근본적인 한계를 보입니다.

구체적 문제: 산술 연산, 논리적 추론, 알고리즘적 구성 등 정확한 규칙 기반의 조작이 필요한 작업에서 변환기는 신뢰할 수 있는 성능을 내지 못합니다.
현상: 모델은 패턴 매칭이나 보간 (interpolation) 에는 탁월하지만, 조합적 복잡성 (combinatorial complexity) 이 있거나 결정적 경계 (sharp decision boundaries) 를 가진 문제 (예: 다중 자리수 덧셈, 논리식 평가, 체스보드 조합 문제 등) 에서는 오류를 범하거나 일반화에 실패합니다.
핵심 질문: 왜 현재 변환기 아키텍처는 심층적인 이산적 알고리즘을 정확하게 구현하는 데 실패하는가?

2. 방법론 (Methodology)

이 논문은 경험적 평가나 점진적인 개선을 넘어, 세 가지 이론적 프레임워크를 종합하여 변환기의 구조적 및 계산적 장애물을 체계적으로 분석합니다.

회로 복잡성 (Circuit Complexity): 모델의 용량을 계산 깊이 (depth) 와 병렬성 관점에서 분석합니다. 특정 알고리즘이 순차적 계산을 필수로 하는 이유를 규명합니다.
근사 이론 (Approximation Theory): 변환기가 연속적인 매핑을 학습하는 반면, 이산적 추론은 불연속적인 함수를 다룬다는 점을 강조합니다. 불연속 함수를 근사하는 데 내재된 어려움을 분석합니다.
통신 복잡성 (Communication Complexity): 자기 주의 (self-attention) 메커니즘 내에서의 정보 교환 한계를 정량화합니다. 토큰 간 다중 홉 (multi-hop) 추론 및 조율에 대한 아키텍처적 제약을 규명합니다.

이 세 가지 관점을 연결하여 변환기가 왜 심볼릭 계산에 실패하는지 통합된 설명을 제공합니다.

3. 주요 기여 및 핵심 결과 (Key Contributions & Results)

A. 회로 복잡성 관점: 깊이의 병목 현상 (Depth as a Bottleneck)

유한 정밀도 (Finite Precision): 실제 변환기는 유한 정밀도 산술을 사용하며, 이는 임계 회로 (threshold circuits) 에 해당합니다. 하드 어텐션 기반의 인코더만 있는 변환기는 $AC^0$ 회로에 해당하여 패리티 (parity) 나 다수결 (majority) 같은 논리 연산을 인식할 수 없습니다.
상수 깊이 (Constant Depth): 현재 변환기는 고정된 층 수 (layer) 를 가지므로, 계산 깊이가 제한됩니다. 이는 $TC^0$ 이하의 표현력을 갖게 하여, 다중 자리수 덧셈이나 중첩된 형식 언어 인식과 같은 심층적 구성 작업을 불가능하게 만듭니다.
상수 출력 길이 (Constant Output Length): 체인 오브 씽킹 (CoT) 이나 스크래치패드 없이 한 번의 순전파 (forward pass) 로만 출력을 생성할 경우, 모델은 얕은 회로로 제한됩니다. 반면, CoT 를 통해 출력 길이를 늘리면 (예: $O(t(n))$ ), 변환기는 튜링 완전 (Turing-complete) 한 표현력을 가질 수 있음이 이론적으로 증명되었습니다.

B. 근사 이론 관점: 정확성의 어려움 (Why Exactness is Hard)

불연속 함수의 근사 한계: 변환기는 부드러운 (smooth) 함수 근사에 최적화되어 있지만, 이산적 추론은 불연속적인 단계 함수 (piecewise-constant functions) 를 다룹니다. (예: 자리수 올림 (carry) 발생 시 급격한 값 변화).
오차 누적: 다중 단계 문제에서 각 단계의 오차는 지수적으로 누적됩니다 ( $L^k \epsilon$ ). 고정된 깊이의 신경망은 단계 수가 증가함에 따라 경계에서의 정밀도를 유지할 수 없습니다.
최악의 경우 오차: 평균 오차 ( $E_{avg}$ ) 는 작을 수 있지만, 결정 경계 근처나 분포 외 (OOD) 데이터에서 최악의 경우 오차 ( $E_{max}$ ) 는 매우 커집니다. 이는 모델이 "이진적 오류 (bimodal error)"를 보이며, 대부분의 경우 정확하지만 경계에서 치명적인 실패를 일으킴을 의미합니다.

C. 통신 복잡성 관점: 대역폭과 라운드의 중요성 (Bandwidth and Rounds)

순차적 릴레이 제한: 변환기는 모든 토큰이 한 번의 어텐션 레이어 (라운드) 에서 정보를 교환할 수 있지만, 깊이가 $M$ 인 모델은 최대 $M$ 단계의 정보 전달만 가능합니다.
포인터 체이싱 (Pointer Chasing): 긴 시퀀스에서의 의존성 (예: $n$ 비트 덧셈에서의 자리수 올림 전파) 을 해결하려면 $n$ 단계의 순차적 전달이 필요합니다. 고정된 깊이 $M < n$ 인 경우, 모델은 정확한 계산을 수행할 수 없습니다.
대역폭의 한계: 히든 차원 (hidden dimension) 을 늘려 대역폭을 증가시켜도, 필요한 순차적 라운드 수를 줄일 수 없습니다. 긴 시퀀스에서의 정보 전달은 손실 (lossy) 이 발생하거나 왜곡됩니다.

4. 의의 및 시사점 (Significance & Implications)

이론적 통합: 세 가지 프레임워크 (회로, 근사, 통신) 는 서로 독립적이지 않으며 상호 강화됩니다.
- 깊이 - 통신 연결: 제한된 깊이는 계산 단계와 정보 전달 라운드를 동시에 제한합니다.
- 깊이 - 근사 연결: 문제의 복잡도에 맞춰 깊이를 동적으로 늘릴 수 없으므로, 불연속 함수 근사 시 오차가 누적됩니다.
- 근사 - 통신 연결: 부드러운 근사 경향과 먼 거리의 정보 수집 한계가 결합되어 정확한 추론 실패를 초래합니다.
현재 기술의 한계: CoT 프롬프팅이나 스크래치패드와 같은 기법은 부분적인 완화를 제공하지만, 변환기의 설계에 내재된 근본적인 한계 (고정 깊이, 유한 정밀도, 대역폭 제약) 를 완전히 극복하지는 못합니다.
미래 방향성 제안:
- 뉴로 - 심볼릭 모델 (Neuro-symbolic): 신경망의 패턴 인식 능력과 명시적인 심볼릭 구성 요소 (논리 회로, 파서 등) 를 결합.
- 상태 인식 및 메모리 증강 아키텍처: 외부 메모리나 상태 공간 모델을 통해 무제한의 순차적 계산 지원.
- 경계 인식 학습: 불연속성과 결정 경계를 인식하도록 유도하는 인덕티브 바이어스 (inductive bias) 또는 학습 목표 개발.

결론

이 논문은 변환기의 이산적 추론 실패가 단순한 데이터 부족이나 학습의 문제가 아니라, 아키텍처의 구조적 속성 (깊이, 정밀도, 통신 대역폭) 에 기인한 근본적인 이론적 한계임을 명확히 증명합니다. 차세대 추론 가능 머신러닝 시스템을 설계하기 위해서는 단순한 스케일링을 넘어, 심볼릭 연산과 순차적 계산을 통합한 구조적 혁신이 필요함을 강조합니다.