🤖 machine learning

Indexing: the Beginning and the End

이 논문은 인덱스가 입력의 끝에 나타날 때 RNN 및 선형 어텐션 트랜스포머와 같은 마스크 기반 딥러닝 아키텍처가 인덱싱 프리미티브를 해결하는 데 근본적으로 제한된다는 것을 입증하기 위해 인과적 복잡성(causal complexity)이라는 개념을 도입하며, 반면 소프트맥스 및 비마스크 선형 어텐션 트랜스포머는 이를 효율적으로 해결할 수 있다는 이론적 분리를 제시하고 이를 실험적 실험을 통해 뒷받침한다.

원저자: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

게시일 2026-07-27

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

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

당신은 이야기를 읽고 그에 대한 질문에 답할 수 있는 아주 똑똑한 로봇을 만들려고 한다고 상상해 보세요. 이것이 바로 인공지능, 구체적으로는 '딥러닝'이라 불리는 분야의 세계입니다. 여기서 컴퓨터는 방대한 양의 데이터를 관찰하며 패턴을 학습합니다. 오랫동안 이 작업에 가장 인기 있었던 로봇들은 '트랜스포머(Transformers)'라고 불렸습니다. 이들은 특정 사실을 찾기 위해 책 전체를 순식간에 훑어볼 수 있는 아주 유능한 사서와 같습니다. 하지만 여기에는 함정이 있습니다. 책이 길어질수록 사서는 점점 더 느려지며, 이들을 만드는 데는 많은 에너지와 비용이 듭니다.

이를 해결하기 위해 과학자들은 새로운 유형의 로봇들을 발명했습니다. 예를 들어 'RNN'은 인간처럼 단어를 하나씩 읽고, 'SSM'은 매우 효율적인 방식으로 이야기 전체를 한꺼번에 읽으려고 시도합니다. 모두가 던지는 큰 질문은 이것입니다: "이 새로운, 더 빠른 로봇들이 기존의 느리지만 똑똑한 로봇들만큼 똑똑한가, 아니면 숨겨진 약점을 가지고 있는가?" 이 질문에 답하기 위해 연구자들은 단순히 추측하는 대신, 로봇들에게 작고 까다로운 퍼즐을 줍니다. 이 퍼즐들은 AI 세계의 '수학 숙제'와 같습니다. 만약 로봇이 간단한 숙제조차 풀지 못한다면, 그것은 로봇의 두뇌에 근본적인 한계가 있음을 증elt하는 것이며, 아무리 많이 훈련시킨다 해도 해결할 수 없음을 의미합니다.

"Indexing: the Beginning and the End"라는 제목의 이 논문은 '인덱싱(Indexing)'이라는 매우 구체적이고 단순한 퍼즐을 사용하여 서로 다른 로봇 구조들의 두뇌를 테스트합니다. 이 퍼즐은 보기에는 매우 쉬워 보입니다. $n$ 개의 비트(0과 1로 이루어진 문자열)와 특정 비트를 선택하라고 알려주는 숫자 $i$ 가 있다고 가정해 봅시다. 목표는 단순히 그 특정 비트의 값을 출력하는 것입니다. 이는 마치 당신에게 64개의 전등 스위치가 있는 줄을 건네주며, "17번 스위치는 켜져 있습니까, 꺼져 있습니까?"라고 묻는 것과 같습니다.

연구자들인 알렉산더 코자친스키(Alexander Kozachinskiy), 비센테 오파조(Vicente Opazo), 펠리페 우루티아(Felipe Urrutia)는 정보를 받아들이는 순서가 모든 것을 바꾼다는 사실을 발견했습니다. 그들은 어떤 로봇들은 이 작업에 매우 빠르지만, 어떤 로봇들은 아무리 많은 '생각'의 층(layer)을 쌓더라도 결코 넘을 수 없는 벽에 부딪힌다는 것을 발견했습니다.

여기에는 반전이 있습니다. 논문은 특정 유형의 로로봇들(구체적으로 '인과적(causal)'이거나 '마스크(masked)'된 방식으로 정보를 처리하는 로봇들, 즉 자신보다 앞에 나온 정보만 볼 수 있고 뒤에 올 정보는 볼 수 없는 방식)에게 있어, 만약 비트의 목록이 길고 인덱스 숫자가 맨 마지막에 나타난다면 이 퍼즐을 푸는 것이 수학적으로 불가능하다는 것을 증명합니다. 이는 마치 로봇에게 긴 사람들의 줄을 보여주며 모든 사람의 얼굴을 기억하라고 시킨 뒤, 맨 마지막에 이르러서야 "42번째 사람의 이름을 말해봐"라고 속삭이는 것과 같습니다. 이 논문은 RNN, Mamba, 그리고 마스크드 선형 어텐션(masked linear-attention) 트랜스포머와 같은 로봇들이 '메모리 병목 현상'을 겪는다고 보여줍니다. 이들은 인덱스가 마침내 도착했을 때 그 모든 정보를 충분히 작은 패키지로 압축하여 기억해낼 수 없습니다. 저자들은 로봇이 무한한 정밀도(즉, 반올림 오차로 인해 혼란을 겪지 않는 상태)를 가지고 있더라도 성립하는 엄격한 수학을 사용하여 이를 증명했습니다.

하지만 상황을 뒤집으면 이야기는 달라집니다. 만약 인덱스 숫자가 리스트의 시작 부분에 나타나서(로봇에게 사람들의 줄을 보여주기도 전에 "42번째 사람을 기억해"라고 미리 알려주는 경우), RNN은 슈퍼히어로가 됩니다. 이들은 단 한 단계 만에 이 문제를 해결할 수 있는 반면, 유명한 트랜스포머를 포함한 다른 로봇들은 이를 알아내기 위해 최소 두 단계 이상의 과정이 필요합니다.

저자들은 단순히 수학적 계산만 한 것이 아니라, 실제 모델들을 가지고 실험도 수행했습니다. 그들은 최대 64비트의 리스트를 가지고 이 로봇들을 훈련시켰습니다. 결과는 그들의 이론과 완벽하게 일치했습니다. 수학적으로 실패할 것이라고 예측되었던 로봇들(긴 리스트의 끝에서 비트를 찾아야 하는 인과적 로봇들)은 리스트가 길어짐에 따라 지속적으로 포기하는 모습을 보였습니다. 반면, 수학적으로 성공할 것이라고 예측되었던 로봇들은 이 과제를 쉽게 학습했습니다.

그렇다면 핵심은 무엇일까요? 어떤 로봇이 다른 모든 면에서 "더 낫다"는 것이 아닙니다. 대신, 이 논문은 서로 다른 구조들이 각기 다른 '초능력'과 '크립토나이트(치명적인 약점)'를 가지고 있음을 밝혀냅니다. 로봇이 정보를 처리하는 방식—왼쪽에서 오른쪽으로 읽는지, 모든 것을 한꺼번에 보는지, 혹은 과거를 요약하려고 노력하는지에 따라—그들이 풀 수 있는 퍼즐과 그들을 영원히 당황하게 만들 퍼즐이 정확히 결정됩니다. 이는 과학자들이 AI의 근본적인 한계를 이해하도록 도와주며, 우리가 차세대 스마트 기계를 만들 때 그들이 무엇을 할 수 있고 무엇을 할 수 없는지를 정확히 알 수 있게 해줍니다.

기술 요약: 인덱싱: 시작과 끝

문제 정의

본 논문은 현대적 딥러닝 아키텍처—구체적으로 순환 신경망(RNN), Softmax 트랜스포머, 선형 주의력(Linear-Attention) 트랜스포머, 그리고 상태 공간 모델(SSM)—의 표현력과 정보 병목 현상을 **인덱싱 프리미티브(indexing primitive)**의 관점에서 조사한다.

인덱싱 작업은 다음과 같이 정의된다: $n$ 개의 비트 시퀀스 $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ 와 인덱스 $i \in \{1, \dots, n\}$ 가 주어졌을 때, 모델은 $i$ 번째 비트인 $\sigma_i$ 를 출력해야 한다. 저자들은 서로 다른 아키텍처의 한계를 탐구하기 위해 두 가지 특정 변형을 분석한다:

우측 인덱싱 (Right-Hand Indexing, RHI): 인덱스 $i$ 가 입력 시퀀스의 끝(비트들 뒤)에 나타난다. 모델은 앞선 $n$ 개의 비트로부터 처리된 정보를 바탕으로 $\sigma_i$ 를 검색해야 한다.
좌측 인덱싱 (Left-Hand Indexing, LHI): 인덱스 $i$ 가 입력 시퀀스의 시작(비트들 앞)에 나타난다. 모델은 인덱스 정보를 시퀀스 전체를 통해 전달하여 마지막에 $\sigma_i$ 를 검색해야 한다.

본 연구는 "작은" 아키텍처, 즉 시퀀스 길이 $n$ 에 대해 파라미터 수가 $o(1)$ (상수 개수)이며 잠재적으로 무한 정밀도의 실수 산술을 사용하는 모델을 대상으로 한다.

방법론

저자들은 **인과적 복잡도(causal complexity)**와 **VC 차원(VC dimension)**에 기반한 이론적 프레임워크를 사용하여 무조건적 하한(unconditional lower bounds)을 도출한다.

인과적 복잡도

출력이 $k$ 번째 입력 $1 $부터$ k $까지의 입력에만 의존하는 인과적(마스크된) 아키텍처의 경우, 저자들은 **인과적 복잡도**라는 개념을 도입한다. 이는 히스토리($ x_1, \dots, x_{k-1} $)가 얼마나 낮은 차원$ s $로 압축될 수 있는지(즉, "지문" 함수를 통해)를 측정하며, 이 압축된 표현과 현재 입력$ x_k $로부터$ k$번째 출력을 낮은 산술 복잡도로 계산할 수 있는지를 의미한다.

핵심 통찰: 만약 아키텍처가 낮은 인과적 복잡도( $o(1)$ )를 가진다면, 정보가 즉각적으로 접근 가능하지 않을 때 필요한 과거 정보를 검색하기 위한 히스토리를 충분히 압축할 수 없다.

이론적 도구

VC 차원: 저자들은 Kozachinskiy 등(2025)의 기법을 응용하여, 만약 모델이 인덱싱 작업을 해결한다면 해당 개념 클래스의 VC 차원이 최소 $n$ 이상이어야 함을 보여준다.
산술 복잡도: 레이어들이 계산하는 함수(지수 함수, 산술 연산, 조건문 포함)의 산술 복잡도를 활용하여 VC 차원을 제한한다.
무조건적 하한: 이전 연구들이 유한 정밀도 가정에 의존했던 것과 달리, 본 결과는 무한 정밀도 실수를 사용하는 모델에서도 유효하다.

실험적 검증

이론적 결과는 시퀀스 길이 $n \in \{8, 16, 32, 64\}$ 에 대한 이진 인덱싱 작업 실험을 통해 검증된다. 저자들은 다음을 비교한다:

Softmax 및 선형 주의력 트랜스포머의 전체(Full) 및 인과적(Causal) 변형.
RNN (특히 GRU).
SSM (특히 Mamba).
모든 모델은 $n$ 이 증가함에 따라 학습 역학을 관찰하기 위해 고정된 하이퍼파라미터로 처음부터 학습된다.

주요 기여 및 결과

1. 우측 인덱싱 (끝에 위치한 인덱스)

이 시나리오에서 모델은 인덱스를 보기 전에 모든 $n$ 개의 비트를 처리한다. 이 작업을 해결하려면 모델은 전체 $n$ 비트 문자열을 인덱스 토큰이 처리할 수 있을 만큼 작은 상태로 압축해야 한다.

낮은 인과적 복잡도를 가진 아키텍처의 불가능성: 저자들은 $o(1)$ $o (1)$ 의 인과적 복잡도를 가진 상수 개의 레이어를 가진 모델은 RHI를 해결할 수 없음을 증명한다.
- 영향을 받는 아키텍처: 작은 RNN, SSM(예: Mamba), 그리고 마스크된 선형 주의력 트랜스포머는 모두 $o(1)$ 의 인과적 복잡도를 갖는다. 따라서 이들은 무한 정밀도를 사용하더라도 상수 개의 레이어로는 RHI를 해결할 수 없다.
- 실험적 확인: 이 범주에 속하는 모델들(1-레이어 및 멀티 레이어 인과적 선형 주의력, GRU, Mamba)은 $n$ 이 증가함에 따라 RHI 학습에 지속적으로 실패하며, $n=64$ 에서 성공률 0%에 도달한다.
높은 인과적 복잡도를 가진 아키텍처의 가능성:
- Softmax 트랜스포머: $O(1)$ 의 파라미터를 가진 단일 레이어는 RHI를 해결할 수 있다. 이는 전역 주의력(global attention)을 허용하는 소프트맥스 메커니즘을 통한 높은 인과적 복잡도 덕분이다.
- 전체 선형 주의력(Full Linear-Attention): $O(1)$ 의 파라미터를 가진 2개의 레이어는 RHI를 해결할 수 있다.
- 실험적 확인: 이러한 구성은 $n=64$ 에서도 높은 성공률을 보이며 작업을 쉽게 학습한다.

2. 좌측 인덱싱 (앞에 위치한 인덱스)

이 시나리오에서는 인덱스가 먼저 처리되어 시퀀스를 통해 관련 비트 위치까지 전달되어야 한다.

RNN의 우위: 작은 RNN은 $O(1)$ 의 파라미터를 가진 단일 레이어로 LHI를 해결할 수 있다. RNN은 인덱스 $i$ 를 운반하고 $i$ 번째 비트를 만났을 때 특정 좌표를 업데이트할 수 있는 은닉 상태를 자연스럽게 유지한다.
기타 아키텍처의 한계:
- SSM 및 선형 주의력: 1-레이어 SSM이나 1-레이어 선형 주의력(마스크형 또는 전체형)은 $o(1)$ 의 파라미터로 LHI를 해결할 수 없다. SSM 업데이트의 선형성은 인덱스에 의해 결정된 특정 위치에 비트 값을 선택적으로 "쓰는" 것을 방해하며, 정보를 혼합하여 검색을 불가능하게 만든다.
- Softmax 트랜스포머: 1-레이어 Softmax 트랜스포머 역시 $o(1)$ 의 파라미터로 LHI를 해결하는 데 실패한다.
깊이에 따른 해결: 모든 아키텍처(SSM, 선형 주의력, Softmax 트랜스포머 포함)는 $O(1)$ 의 파라미터를 가진 2개의 레이어가 주어진다면 LHI를 해결할 수 있다. 첫 번째 레이어는 인덱스를 전파하고, 두 번째 레이어는 비트를 검색할 수 있다.
실험적 확인: 1-레이어 GRU는 모든 길이에 대해 성공한다. 1-레이어 Mamba와 선형 주의력 모델은 $n \ge 16$ 에서 실패한다. 2-레이어 버전의 모든 아키텍처는 성공한다.

최소 레이어 요구량 요약 표

아키텍처	좌측 인덱싱 (LHI)	우측 인덱싱 (RHI)
Full Softmax	2	1
Causal Softmax	2	1
Full Linear-Attention	2	2
Causal Linear-Attention	2	$\omega(1)$ (불가능)
SSM (예: Mamba)	2	$\omega(1)$ (불가능)
RNN	1	$\omega(1)$ (불가능)

(참고: $\omega(1)$ 은 레이어의 수가 상수로 제한되지 않음, 즉 $n$ 에 따라 증가함을 나타냄.)

의의 및 주장

본 논문은 SSM, RNN, 마스크된 선형 주의력 트랜스포머를 포함한 낮은 인과적 복잡도를 가진 아키텍처 클래스에 대해 최초의 다중 레이어, 무한 정밀도 하한을 제공한다고 주장한다.

아키텍처 간의 분리: 인덱싱 프리미티브는 아키텍처 간의 근본적인 구분을 드러낸다. Softmax 트랜스포머와 전체 선형 주의력 모델은 RHI를 효율적으로 해결할 수 있는 반면, 마스크된 변형과 SSM은 그렇지 못하며, 이는 정보 병목을 극복하는 데 있어 전역 주의력 메커니즘의 특정한 역할을 강조한다.
선형성의 역할: 이 결과는 SSM의 선형 업데이트 규칙이 흔히 효율적이라고 칭송받지만, 단일 단계에서 비선형적인 선택적 쓰기가 필요한 LHI 작업에서는 오히려 약점이 될 수 있음을 시사한다.
이론과 실제의 일치: 실험은 이론적 불가능성 결과(점근적 하한)가 유한한 훈련 환경에서도 질적으로 나타남을 보여준다. 이론적 솔루션이 존재하는 구성은 작업을 견고하게 학습하는 반면, 그렇지 않은 구성은 시퀀스 길이가 길어짐에 따라 어려움을 겪는다(비록 작은 $n$ 에서는 성공할지라도).
겸손한 결론: 저자들은 훈련 실패가 불가능성을 증명하는 것은 아니며, 작은 $n$ 에서의 성공이 점근적 하한과 모순되는 것도 아니라고 명시한다. 그러나 이론적 하한과 경험적 성능 사이의 강한 상관관계는 인과적 복잡도가 검색 작업의 학습 가능성을 예측하는 강력한 지표임을 시사한다.

본 연구는 트랜스포머의 표현력 분석(기존의 함수 합성 및 유도 헤드 중심)을 현대적이고 효율적인 대안들로 확장하여, 특정 정보 검색 시나리오에서의 한계에 대한 엄밀한 수학적 근거를 제공한다.