🤖 machine learning

Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

이 논문은 비음수 커널 어텐션(nonnegative kernel attention)이 풀 어텐션(full attention)이나 밀집 소프트맥스(dense softmax)는 효율적으로 처리할 수 있는 특정 3-토큰 불리언 태스크를 해결하기 위해 지수적인 수의 특징량을 필요로 한다는 점을 입증함으로써, 커널 기반 메커니즘과 풀 어텐션 메커니즘 사이의 근본적인 표현력 격차를 확립한다.

원저자: Vicente Opazo

게시일 2026-08-13

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Vicente Opazo

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

거대한 토큰의 대결: 왜 "짧고 간결함"만으로는 항상 충분하지 않은가

당신이 붐비는 방 안에서 완벽한 짝을 찾으려 노력하고 있다고 상상해 보세요. 인공지능의 세계, 특히 머신러닝이라는 분야에서 컴퓨터는 항상 이 작업을 수행합니다. 컴퓨터는 문장 속의 단어나 이미지 속의 픽셀과 같은 아이템 목록을 보고, 어떤 것들이 서로 가장 잘 어울리는지 파악하려고 노력합니다. 이 과정을 흔히 "어텐션(attention, 주의 집중)"이라고 부릅니다.

컴퓨터가 이를 수행하는 두 가지 주요 방법이 있습니다. 첫 번째 방법은 매우 사교적인 호스트가 방 안의 모든 사람에게 다가가 한 명 한 명과 악수를 하며 비교하는 것과 같습니다. 이를 "풀 어텐션(full attention)"이라고 합니다. 철저하지만, 방이 거대해지면 매우 느려지고 비용이 많이 듭니다. 두 번째 방법은 호스트가 방 전체의 빠르고 압축된 요약본, 즉 "스케치(sketch)"를 만든 다음, 그 요약본을 사용하여 누가 서로 매치되는지 추측하는 방식입니다. 이를 "커널 어텐션(kernel attention)" 또는 "리니어 어텐션(linear attention)"이라고 합니다. 이는 훨씬 빠르며 책 한 권이나 긴 비디오와 같은 방대한 양의 데이터를 처리하도록 설계되었습니다.

오랫동안 과학자들은 이 "스케치" 방식이 "풀(full)" 방식보다 약간 덜 정확할 뿐이며, 스케치를 충분히 크게 만들기만 하면 잘 작동할 것이라고 가정해 왔습니다. 큰 의문은 이것이었습니다: 만약 스케치가 아무리 똑똑하게 만들어지더라도, 도저히 해낼 수 없는 지점이 존재할 것인가? 이 논문은 거대하고 무질서한 실제 데이터를 보는 대신, 아주 작고 구체적인 퍼즐을 설정하여 스케치가 정확히 어디에서 무너지는지를 탐구함으로써 이 질문에 파고듭니다.

세 개의 토큰 함정

이 논문의 저자인 비센테 오파조(Vicente Opazo)는 Min-IP(최소 내적, Minimum Inner Product)라는 게임을 사용하여 이러한 "스케치" 모델의 한계를 테스트하기로 했습니다. 당신이 0과 1로 이루어진 비밀 코드 목록을 가지고 있다고 상상해 보세요. 리스트에 있는 모든 코드에 대해, 당신은 해당 코드와 겹치는 부분이 가장 적은(최소인) 다른 코드를 찾아내야 합니다. 이는 방 안에서 공통점이 가장 적은 두 사람을 찾는 것과 같습니다.

연구진은 두 종류의 AI 모델 간의 경주를 설정했습니다:

풀 어텐션 모델 (The Full Attention Model): 이 모델은 모든 코드 쌍을 직접 살펴봅니다. 이는 모든 비교에 대해 돋보기를 사용하는 것과 같습니다.
커널 어텐션 모델 (The Kernel Attention Model): 이 모델은 모든 코드를 고정된 크기의 "스케치"(요약본)로 압축한 다음, 그 요약본을 바탕으로 수학적 계산을 수행하여 퍼즐을 풀려고 시 합니다.

논문은 다음과 같은 간단한 질문을 던집니다: 리스트에 코드가 몇 개 있을 때 스케치 모델이 실패하는가?

마법의 숫자는 3이다

이 논문에서 발견한 가장 놀라운 사실은 스케치 모델이 리스트가 거대해질 때 실패하는 것이 아니라, 거의 즉시 실패한다는 것입니다.

길이 1과 2: 리스트에 하나 또는 두 개의 코드만 있다면 스케치 모델은 완벽합니다. 아주 작은 요약(단 하나의 "특징")만으로도 퍼즐을 정확하게 풀 수 있습니다. 이는 단 두 명만 있는 방에서 최고의 짝을 찾는 것과 같으며, 매우 쉽습니다.
길이 3: 리스트에 세 번째 코드가 추가되는 순간, 스케치 모델은 벽에 부딪힙니다. 논문은 단 세 개의 코드로 구성된 리스트에 대해 퍼즐을 올바르게 풀기 위해서, 스케치 모델이 코드의 크기에 따라 기하급수적으로 증가하는 수의 특징(features)을 필요로 한다는 것을 증명합니다.

이를 체감할 수 있도록 설명하자면: 만약 당신의 코드가 100비트 길이라면, 스케치 모델은 이를 제대로 맞추기 위해 수십억 개의 특징이 필요할 수도 있습니다. 만약 200비트라면, 그것은 실질적으로 불가능할 정도로 거대한 숫자가 필요합니다. 반면, "풀 어텐션" 모델(개별적으로 확인하는 모델)은 동일한 세 개의 코드 퍼즐을 아주 적은 양의 일정한 노력만으로 쉽게 해결합니다.

왜 이런 일이 발생하는가?

저자는 이를 "도미노 효과" 또는 "증폭"의 비유를 들어 설명합니다.

스케치 모델이 후보 A와 후보 B 사이에서 결정하려고 한다고 가정해 봅시다.

리스트에 두 사람만 있다면, 모델은 단순히 A와 B를 비교합니다. 쉽습니다.
리스트에 세 사람(A, B, C)이 있다면, 모델은 A를 B와 비교해야 하고, 동시에 A를 C와도 비교해야 합니다.

논문은 모델이 모든 것을 하나의 요약본으로 압축하도록 강제되기 때문에, "매우 다른 것"과 "약간 다른 것" 사이의 날카로운 구별 능력을 상실한다는 것을 보여줍니다. 두 명의 경쟁 후보가 있으면 모델의 요약본은 혼란에 빠집니다. 이 혼란을 해결하기 위해 모델은 요약본을 믿을 수 없을 정도로 상세하게 만들어야 하며, 이는 결국 요약본이 아니라 모든 가능성을 나열한 리스트가 되어버리는 결과를 초래합니다.

저자는 수학적으로 세 개의 항목이 있는 리스트에 대해 필요한 특징의 수가 대략 $2^m$ (여기서 $m$ 은 코드의 길이)임을 증명했습니다. 이는 기하급급적인 폭발입니다. 이는 문을 여는 데 단 하나의 열쇠가 필요한 것과, 우주의 모든 원자의 조합에 대응하는 열쇠가 필요한 것의 차이와 같습니다.

"부호가 있는" 커널이나 "멀티 헤드"는 어떤가?

이 논문은 자신이 무엇을 증명하지 않았는지 매우 신중하게 밝힙고 있습니다. 이 논문은 "비음수(nonnegative)" 커널(수학적으로 더하기만 수행하고 빼기는 하지 않는 방식)과 단일 "헤드"(하나의 추론 경로)에 초점을 맞춥니다.

"부호가 있는(Signed)" 루프홀: 만로 모델이 숫자를 뺄 수 있다면(음수 특징을 사용한다면), 이 시스템을 우회할 수 있을지도 모릅니다. 논문은 "이 접근 방식이 뺄셈 기반 모델에서도 작동하는지는 알 수 없으나, 덧셈 전용 모델의 경우 벽은 실재한다"라고 말합니다.
"멀티 헤드(Multiple Heads)" 루프홀: 만약 모델에게 여러 개의 "헤드"(데이터를 바라보는 다양한 관점)를 부여한다면, 그것들이 협력하여 퍼즐을 풀 수도 있습니다. 논문은 이를 인정하면서도, 그들이 전달해야 하는 정보의 총량이 엄청나게 증가한다는 점을 보여줍니다.

증명과 실험

저자는 단순히 추측한 것이 아니라, 이를 수학적으로 증명했습니다. 어떤 모델이 이 특정 세 토큰 퍼즐을 50% 미만의 오차율로 해결하려고 할 때, 특징의 수는 반드시 기하급수적이어야 함을 보여주었습니다.

또한, 이를 뒷받침하기 위해 컴퓨터 시뮬레이션을 실행했습니다. 연구진은 세 개의 코드가 담긴 리스트로 AI 모델을 훈련시키고, "특징 랭크(feature rank)"(요약의 크기)를 높임에 따라 어떤 일이 발생하는지 관찰했습니다.

랭크 1에서 15까지: 모델들은 처참하게 실패하며 큰 실수를 저질렀습니다.
랭크 32: 갑자기 모델들이 정답을 맞히기 시작했습니다.
이 실험은 이론을 확인시켜 주었습니다: 모델이 기하급수적 임계값을 넘을 수 있는 충분한 특징을 갖게 되는 순간, 급격한 "상전이(phase transition)"가 일어납니다.

시사점

여기서 얻는 주요 교훈은 속도에는 대가가 따르며, 그 대가는 우리가 생각했던 것보다 훨씬 빨리 나타난다는 것입니다.

우리는 종-종 선형 어텐션(빠른 스케치 기반 방식)이 처리해야 할 토큰의 양이 너무 많을 때만 문제가 될 것이라고 생각합니다. 하지만 이 논문은 문제가 데이터의 양이 아니라, 선택의 복잡성에 있다는 것을 보여줍니다. AI가 몇 가지 특정 항목 사이에서 정밀하고 날카로운 비교를 수행해야 하는 상황(세 개의 항목이 있는 리스트)에 놓이는 즉시, "스케치" 방식은 무너집니다. 이때 엄청난 양의 메모리를 제공하지 않는 한 말입니다.

현실 세계에서 이는 빠른 어텐션 모델이 긴 문서를 요약하는 데는 훌륭할 수 있지만, 몇 가지 특정 항목 간의 정밀하고 날카로운 비교를 요구하는 작업에서는 어려움을 겪을 수 있음을 시사합니다. 느리긴 하지만 "풀 어텐션" 모델은 불가능한 수준의 컴퓨팅 파워를 요구하지 않고도 이러한 날카로운 선택을 처리할 수 있는 유일한 방법입니다. 논문은 빠른 모델과 정확한 모델 사이의 "기하급급적 격차"가 단순히 쉽게 고칠 수 있는 버그가 아니라, 이러한 특정 유형의 AI가 작동하는 근본적인 법칙이라고 결론짓습니다.

기술 요약: 비음수 커널 어텐션에서의 지수적 특징 랭크를 유발하는 세 개의 토큰

문제 정의
본 논문은 커널화된 선형 어텐션(kernelized linear attention)의 표현 능력을 전체 셀프 어텐션(full self-attention)과 비교하여 조사한다. 전체 어텐션은 $N^2$ 개의 쌍별 점수(pairwise scores)를 명시적으로 계산하는 반면, 커널 어티브는 특징 맵(feature map)을 통해 시퀀스를 고정된 차원의 "스케치"(충분 통계량)로 압축하며, 이 과정에서 쌍별 행렬을 피한다. 핵심 질문은 이 압축된 가산적(additive) 표현이 특정 작업에 대해 명시적인 토큰 간 비교를 대체할 수 있는지 여부이다.

저자는 불리언(Boolean) 입력을 대상으로 하는 최소 내적(Minimum Inner Product, Min-IP) 작업을 사용하여 이 문제를 격리한다. 시퀀스 $X = (x_1, \dots, x_N)$ 가 불리언 토큰( $x_i \in \{0, 1\}^m$ )으로 구성될 때, 모델은 모든 위치 $i$ 에 대해 타겟 $t_i(X) = \min_{1 \le j \le N} \langle x_i, x_j \rangle$ 를 계산해야 한다. 이 작업은 키-값 라우팅이나 출력 인코딩과 관련된 복잡성을 제거하고 오직 비교 연산에만 집중한다. 본 연구는 특히 컨텍스트 길이 상전이(context length phase transition), 즉 시퀀스 길이가 2에서 3개의 토큰으로 성장함에 따라 요구되는 특징 차원이 어떻게 변하는지를 중점적으로 다룬다.

방법론
본 논문은 **정규화된 비음수 커널 어텐션(normalized nonnegative kernel attention)**을 분석하기 위해 이론적 하한 증명과 통제된 실험을 채택한다. 아키텍처는 다음과 같이 구성된다:

특징 맵(Feature Maps): 비음수 커널 $\alpha(x, z) = \langle \phi_Q(x), \phi_K(z) \rangle \ge 0$ 를 유도하는 $\phi_Q, \phi_K: \{0, 1\}^m \to \mathbb{R}^r$ .
어텐션 메커니즘: 커널에 의해 결정되는 가중치를 가진 값(values) $v(x_j)$ 의 정규화된 가중 합.
리드아웃(Readout): 어텐션 출력에 적용되는 임의의 쿼리 의존적 아핀 맵(affine map).

이론적 접근 방식은 다음 세 가지 주요 기법에 의존한다:

간극 지배(Gap Domination): 길이가 $n \ge 3$ 인 시퀀스에 대해 모델이 오차 $< 1/2$ 로 성공하기 위해서는, "더 나은" 후보(더 낮은 내적)에 대한 커널 가중치가 두 후보 간의 중첩(overlap) 차이에 의존하는 인자에 의해 "더 나쁜" 후보의 가중치를 엄격하게 지배해야 함을 증명한다.
증폭(Amplification): 중간 단계의 불리언 중첩을 통해 이 지배 조건을 반복하여 커널 가중치 간의 요구되는 비율을 지수적으로 증폭시킨다.
랭크 하한(Rank Lower Bounds): 상수 가중 코드(constant-weight code)와 근사 항등식 보조정리(approximate identity lemma)를 활용하여 이러한 가중치 비율을 특징 차원 $r$ 에 대한 하한으로 변환한다.

또한, 본 논문은 유한 알파벳 교차 토큰 채널을 가진 결정론적 다층 스케치 모델에 대한 **유한 정밀도 정보 하한(finite-precision information bound)**을 도출하며, 독립적인 답변의 수에 선형적이고 알파벳 크기의 로그에 비례하는 트랜스크립트(transcript) 하한을 증명한다.

주요 기여 및 결과

날카로운 3-토큰 상전이:
- 길이 1 & 2: 랭크-1 정규화 커널 어텐션 헤드는 길이 2까지의 시퀀스에 대해 Min-IP를 정확하게 해결하는 데 충분하다. 길이 2에서는 쿼리에 단 하나의 교차 토큰 후보만 존재하므로, 단순 평균이 충분한 정보를 유지할 수 있다.
- 길이 3: 쿼리가 두 개의 경쟁하는 후보 사이에서 선택을 해야 하는 길이 3의 시퀀스의 경우, 오차를 $1/2$ 미만으로 달성하는 임의의 단일 정규화 비음수 커널 어텐션 헤드는 $2^{\Omega(m)}$ 의 특징을 필요로 한다.
- 이 하한은 임의의 유한 차원 토큰 값, 임의의 쿼리 의존적 아핀 리드아웃, 위치 의존적 토큰 맵, 그리고 인과적 최종 쿼리(causal final-query) 정식화에 대해서도 유효하다.
Dense Softmax와의 비교:
- Dense softmax 어텐션은 $m$ 차원의 점수와 상수 온도를 사용하여 동일한 길이-3 작업을 해결한다.
- 본 논문은 지수적 특징 요구 사항이 비음수 커널 제약 조건에 특이적임을 보여준다. Dense softmax 구현은 모든 쌍별 비교를 효과적으로 노출하는 반면, 커널 방식은 이를 압축하려고 시도한다.
- 이 하한은 고정된 컨텍스트 길이가 길어짐에 따라 정확한 $2^m$ 특징 실현에 근접하며, 이는 양의 특징 실현을 위한 이론적 종착점과 거의 일치한다.
유한 정밀도 정보 하한:
- (다중 헤드/레이어를 가진) 더 넓은 범위의 결정론적 다층 스케치 모델에 대해, 본 논문은 총 통신된 정보(트랜스크립트)가 반드시 $q \log_2(s+1)$ 비트로 스케일링되어야 함을 증명한다. 여기서 $q$ 는 독립적인 답변의 수이고 $s$ 는 알파벳 크와 관련된다. 이는 여러 헤드를 사용하더라도 총 정보 용량이 이 작업을 해결하기 위해 증가해야 함을 확립한다.

실험적 검증
저자는 유한한 패밀리의 길이-3 시퀀스에 대해 실험을 수행하였다:

위트니스 스위트(Witness Suite): 24비트 벡터에서 유도된 1,272개의 입력으로 구성된 구조화된 패밀리에 대해 모델을 학습시켰다. 결과에 따르면 특징 랭크 $r < 8$ 인 모델은 작업을 해결하는 데 실패(오차 $> 0.80$ )한 반면, $r=32$ 인 모델은 이를 정확하게 해결했다. 이는 사용된 특정 구조에 대한 이론적 하한 $r \ge 8$ 과 일치한다.
OOD 스케일링: 더 큰 규모의 서로 다른 훈련/테스트 풀에 대한 실험에서, 특징 차원이 증가함에 따라 정확도에 급격한 전이가 나타났다. 문제의 규모가 커짐에 따라 전이 지점은 $r=8$ 에서 $r=16$ , $r=64$ 로 이동한 반면, dense attention은 모든 시드에 대해 정확도를 유지했다.

의의 및 주장
본 논문은 커널 어텐션의 한계가 단순히 긴 컨텍스트를 압축하는 결과가 아니라, 두 개의 경쟁하는 후보가 포함된 바로 첫 번째 컨텍스트 길이에서 나타나는 근본적인 장애물이라고 주장한다.

이 분리는 무조건적이다 (Orthogonal Vectors Conjecture와 같은 복잡도 추측에 의존하지 않음).
이 결과는 **비음수성(nonnegativity)**이 핵심적인 제약 조건임을 강조한다. 부호가 있는 커널(signed kernels)이나 다중 헤드는 항을 상쇄하거나 전문화함으로써 이 특정 랭크 경계를 우회할 수 있다.
본 연구는 왜 선형 어텐션 메커니즘이 특징 차원이 토큰 차원에 대해 지수적으로 스케일링되지 않는 한, 짧은 컨텍스트에서도 여러 후보를 명시적으로 비교하는 작업에 어려움을 겪을 수 있는지에 대한 엄격한 이론적 근거를 제공한다.

저자는 자신의 정리가 아핀 리드아웃을 가진 단일 헤드 비음수 커널 어텐션에 적용됨을 명시적으로 밝힌다. 이는 모든 선형 어텐션 모델이 이러한 작업을 수행할 수 없다고 주장하는 것이 아니라, 고정된 스케치로 비음수 특징을 통해 압축하는 특정 메커니즘이 Min-IP에 대해 길이 3에서 지수적 장벽에 직면한다는 것을 의미한다.