💬 NLP

Learning State-Tracking from Code Using Linear RNNs

이 논문은 순열 합성(permutation composition)을 코드 기반의 REPL 트레이스로 변환함으로써 상태 추적 연구와 다음 토큰 예측 사이의 간극을 메우며, 선형 RNN이 트랜스포머에 비해 이 작업에서 탁월한 성능을 보이는 반면, 상태 노출은 결정론적이지만 행동이 완전히 관찰되지 않는 경우에는 비선형 RNN보다 성능이 저하될 수 있음을 입증한다.

원저자: Julien Siems, Riccardo Grazzi, Korbinian Pöppel, Kirill Kalinin, Hitesh Ballani, Babak Rahmani

게시일 2026-06-26

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Julien Siems, Riccardo Grazzi, Korbinian Pöppel, Kirill Kalinin, Hitesh Ballani, Babak Rahmani

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

개요: 코드의 "셸 게임(Shell Game)"

당신이 마술사가 하는 "셸 게임"을 보고 있다고 상상해 보세요. 테이블 위에 세 개의 컵이 있고, 그중 하나에 공이 숨겨져 있습니다. 마술사가 컵을 이리저리 바꿉니다. 당신의 임무는 공이 어디로 갔는지 계속 추적하는 것입니다.

공: 컴퓨터 프로그램 내의 변수 (예: 상자에 담긴 숫자).
컵 바꾸기: 변수를 이동시키는 코드 명령들.
목표: 일련의 긴 컵 바꾸기 과정이 끝난 후 공이 정확히 어디에 있는지 알아내는 것.

오랫동안 연구자들은 이 특정 설정으로 AI 모델의 "셸 게임" 능력을 테스트해 왔습니다. 즉, AI에게 컵 바꾸기 목록을 보여준 뒤, "지금 공은 어디에 있는가?"라고 물었습니다. 이 논문은 이것이 마치 학생에게 영화 대본 전체를 암기하게 한 뒤 결말을 읊어보라고 요구하는 것과 같다고 주장합니다. 이는 AI가 이야기가 진행되는 동안 실제로 어떻게 '이해'하는지를 테스트하는 것이 아닙니다.

새로운 접근 방식: "실시간 해설"

저자들은 실제 AI(현재 당신과 대화하고 있는 것과 같은 모델)가 학습하는 방식인 **다음 토큰 예측(Next-Token Prediction)**에 맞춰 테스트 방식을 변경했습니다.

전체 컵 바꾸기 목록을 한꺼번에 보여주는 대신, 컴퓨터 프로그램이 실행되는 과정을 한 줄씩 실시간 스크립트로 제공했습니다.

1행: "컵 A를 B로 이동."
2행: "컵 A 밑을 확인하세요!" (컴퓨터가 결과를 출력함).
3행: "컵 B와 C를 교체."
4행: "컵 C 밑을 확인하세요!"

AI는 스크립트의 다음 단어를 예측해야 합니다. 이를 수행하기 위해서는 인간이 이야기를 따라가듯, 스크립트를 읽으면서 머릿속으로 컵의 상태를 추적해야만 합니다.

대결 구도: "선형(Linear)" vs "트랜스포머(Transformer)"

논문은 두 가지 유형의 AI 아키텍처를 맞붙였습니다.

트랜스포머 (The "Photographic Memory"): 현재 AI의 챔피언들입니다 (이 채팅의 기반이 되는 모델들과 같은 모델). 이들은 정보가 눈앞에 바로 있을 때 사실을 기억하고 패턴을 찾는 데 탁능합니다.
선형 RNN (The "Mental Note-Takers"): 책을 한 단어씩 읽어나가는 것처럼 정보를 순차적으로 처리하도록 설계된 더 빠르고 새로운 모델들입니다.

결과:

셸 게임이 완전히 공개되었을 때(AI가 모든 컵 바꾸기와 확인 과정을 볼 수 있을 때), 선형 RNN(특히 DeltaNet이라 불리는 유형)은 놀라운 성능을 보였습니다. 이들은 게임이 매우 길어져도 공을 완벽하게 추적할 수 있었습니다.
트랜스포머는 고전했습니다. 이들은 흐름을 놓치지 않기 위해 상태가 매우 빈번하게 드러나야 했습니다. 만약 "확인(peek)" 사이의 간격이 넓어지면, 트랜스포머는 길을 잃었습니다.

반전: 게임이 "모호해질(Fuzzy)" 때

그다음 논문은 질문합니다. 게임이 완벽하게 명확하지 않다면 어떻게 될까?

실제 컴퓨터 코드에서 상황은 항상 결정론적이지 않습니다. 때때로 코드는 무작위 선택을 하거나, 변수가 AI가 볼 수 없는 것(예: 숨겨진 환경 변수)에 의존하기도 합니다.

저자들은 AI가 확률에 기반하여 상태를 추측해야 하는 시나리오를 만들었습니다 (예: "공이 왼쪽으로 이동했을 확률 50%, 그대로 있을 확률 50%").

선형 RNN의 문제점:
이 논문은 이러한 "모호한" 불확실성을 다룰 때 선형 RNN이 가진 근본적인 약점을 발견했습니다.

비유: 당신이 종이 뭉치를 균형 있게 쌓아두려고 노력하고 있다고 상상해 보세요. 새로운 단서(확인)를 얻을 때마다 당신은 뭉치를 다시 정리해야 합니다.
선형 RNN에서는 뭉치를 업데이트하는 수학적 방식이 "선형적"입니다. 이는 마치 구멍 난 양동이와 같습니다. 부분적인 단서를 얻을 때마다, 당신의 "확신"(수학적 질량)이 조금씩 새어 나갑니다.
만약 "완전한 리셋"(명확하고 전체적인 공개) 없이 일련의 부분적인 단서들이 길게 이어진다면, 당신의 답변에 대한 확신은 기하급수적으로 줄어듭니다. 결국 그 숫자는 너무 작아져서 컴퓨터는 이를 0으로 처리합니다. AI는 모든 것을 잊어버립니다.

"적대적(Adversarial)" 함정:
저자들은 다음과 같은 특정 움직임의 순서로 선형 RNN을 속일 수 있음을 보여주었습니다.

컵을 무작위로 섞는다 (불확실성 생성).
특정 컵 하나만의 위치를 밝힌다 (부분적인 단서 제공).
이를 반복한다.

이 과정이 반복될 때마다, 선형 RNN은 다른 컵들을 추적하는 능력을 조금씩 잃어갑니다. 충분한 횟수가 반복되면, 다른 컵들의 위치에 대한 AI의 내부적 "믿음"은 완전히 사라집니다. 비록 인간은 여전히 논리적으로 답을 도출할 수 있음에도 불구하고 말입니다.

결론

선형 RNN은 규칙이 명확하고 경로가 결정론적일 때(완벽한 셸 게임처럼) 상태를 추적하는 데 매우 뛰어납니다. 훈련이 제대로 설정된다면 트랜스포머를 이길 수도 있습니다.
선형 RNN은 상황이 확률적이거나 부분적으로 숨겨져 있는 실제 세계의 코드를 다룰 때 어려움을 겪습니다. 이들의 수학적 구조는 불확실성을 다룰 때 시간이 지남에 따라 세부 사항을 "망각"하게 만드는데, 이는 선형 구조를 깨뜨리지 않고는 확신도를 다시 조정하거나(re-normalize) 회복할 수 있는 메커니즘이 부족하기 때문입니다.

요약하자면, 선형 RNN은 명확한 대본을 따르는 데는 탁월하지만, 대본이 모호하고 무작위해지면 정신을 놓치기 쉽습니다.

기술 요약: 선형 RNN을 이용한 코드 기반 상태 추적 학습

문제 정의

상태 추적(State-tracking)은 프로그램 실행, 게임 상태, 그리고 세계 모델을 이해하는 데 있어 근본적인 능력입니다. 이론적 연구들은 트랜스포머(Transformer)가 연합 회상(associative recall)에 탁월하고, 순환 신경망(RNN)이 상태 추적에 강점이 있다는 분리된 구도를 확립해 왔으나, 모델의 평가 방식과 훈련 방식 사이에는 상당한 격차가 존재합니다.

기존의 대부분의 상태 추적 벤치마크(예: 치환 합성)는 시퀀스-투-시퀀스(sequence-to-sequence) 설정을 사용합니다. 즉, 일련의 액션을 직접 누적 상태의 시퀀스로 매핑하는 방식입니다. 이는 현대 대규모 언어 모델(LLM)이 사용하는 다음 토큰 예측(next-token prediction) 패러다임과 근본적으로 다릅니다. 후자의 경우, 모델은 액션과 부분적인 상태 노출(예: print 문)이 교차되는 스트림 내에서 다음 토큰을 예측해야 합니다. 또한, 실제 코드 실행은 **부분 관측 가능성(partial observability)**과 확률적 전이(probabilistic transitions)(예: 숨겨진 상태에 따른 분기 또는 무작위 선택)를 포함하는 경우가 많습니다. 이는 진정한 상태가 완전히 관측되지 않는 환경을 조성하며, 결정론적 상태가 아닌 믿음 분포(belief distribution)를 유지할 것을 요구합니다.

방법론

1. 코드를 통한 상태 추적의 재구성 (REPL 트레이스)

저자들은 추상적인 오토마타 벤치마크와 LLM 훈련 목적 사이의 간극을 메우기 위해, 치환 합성 작업을 Python REPL 트레이스로 변환합니다.

메커니즘: 모델이 치환 시퀀스 $\sigma_1, \dots, \sigma_m$ 을 누적 상태로 매핑하는 대신, 부분적인 상태 정보를 드러내는 print 문과 함께 파이썬 명령(변수 할당, 스왑 등)의 시퀀스를 처리하도록 합니다.
목표: 모델은 다음 토큰이 명령이든 혹은 드러난 상태 값이든 관계없이, 트레이스의 다음 토큰을 예측하도록 다음 토큰 예측 방식으로 훈련됩니다. 이를 통해 모델은 예측 과업을 통해 상태 추적을 암시적으로 학습하게 됩니다.

2. 아키텍처 비교

본 연구는 이러한 과업에 대해 세 가지 아키텍처 클래스를 비교합니다:

Transformers: 표준적인 어텐션 기반 모델.
Linear RNNs (DeltaNet [0, 1]): 고윳값(eigenvalues)이 $[0, 1]$ 범위로 제한된 선형 RNN으로, 패리티(parity)나 치환 합성 같은 복잡한 상태 추적을 수행할 수 없는 것으로 알려져 있습니다.
Linear RNNs (DeltaNet [-1, 1]): 고윳값 범위를 $[-1, 1]$ 로 확장하여, 이론적으로 결정론적 치환 합성을 해결할 수 있는 선형 RNN입니다.

3. 이론적 프레임워크: PFSA-SR

실제 코드에서의 상태 추적 난이도를 분석하기 위해, 저자들은 **상태 노출이 있는 확률적 유한 상태 오토마타(PFSA-SR)**를 도입합니다.

정의: 튜플 $(Q, \Sigma, \delta, \rho, q_0)$ 로 정의되며, 여기서 $\delta$ 는 확률적 전이 커널이고 $\rho$ 는 입력을 상태의 부분 집합으로 매핑하는 노출 함수입니다.
역학: 시스템은 확률적 전이를 통해 진화하지만, 관찰자는 소프트한 가능성(likelihood)을 받는 대신 상태 집합을 깎아내는(pruning) "하드" 제약 조건(reveals)을 받습니다.
믿음 업데이트(Belief Update): 추적을 위해서는 상태에 대한 믿음 분포 $b_t$ 를 유지해야 합니다. 업데이트는 노출 단계(일관되지 않은 상태를 제거하고 정규화함)와 전이 단계를 포함합니다. 결정적으로, 정규화 단계 $f(x) = x/\|x\|_1$ 는 **비선형(non-linear)**입니다.

4. 표현 분석

본 논문은 선형 RNN의 믿음 상태에 대한 두 가지 표현을 조사합니다:

결합 표현(Joint Representation): 모든 $n!$ 개의 치환을 명시적으로 열거합니다. 저자들은 입력 주입 항 $B(x_t)$ 가 부분 노출 이후 생존한 구성들의 확률 질량을 적응적으로 보충할 수 없기 때문에, 선형 RNN에서 수치적으로 불안정하다고 주장합니다. 이는 지수적인 노름(norm) 감소를 초래합니다.
주변 표현(Marginal Representation): 각 위치의 주변 확률을 독립적으로 추적합니다(하나의 $n \times n$ 이중 확률 행렬). 이는 $B(x_t)$ 가 드러난 항목에 대해 확실성을 직접 주입할 수 있게 해주지만, 저자들은 특정 미노출 항목이 직접적으로 보충되지 않는 적대적 노출 시퀀스(adversarial reveal sequences) 하에서는 여전히 지수적 감소에 취약함을 보여줍니다.

주요 결과

1. 감독 밀도와 아키텍처

Transformers: 상태 추적을 학습하기 위해 조밀한 상태 감독이 필요합니다. print 문(노출) 사이의 간격이 넓어질수록 트랜스포머의 성능은 급격히 떨어집니다. 이들은 조밀한 감독이 있더라도 전체 치환으로 일반화하는 데 실패합니다.
Linear RNNs (DeltaNet [-1, 1]): 이 설정에서 탁월한 성능을 보입니다. 이들은 희소한 감독 하에서도 상태를 안정적으로 추적하는 법을 배우며, 강력한 길이 외삽(length extrapolation, 훈련보다 긴 시퀀스로 일반화) 능력을 보여줍니다.
Linear RNNs (DeltaNet [0, 1]): 과업 해결에 실패하며, 이는 복잡한 상태 추적을 위해 확장된 고윳값 범위 $[-1, 1]$ 가 필수적임을 확인시켜 줍니다.

2. 상태 추적의 해석 가능성

학습된 DeltaNet [-1, 1]에 대한 분석은 상태 추적이 특정 컴포넌트에 국한되어 있음을 밝혀냅니다:

고윳값 확장: 특정 레이어(예: Layer 12, Head 3)의 최소 하나 이상의 어텐션 헤드가 감쇠 파라미터 $\beta$ 를 2로 설정하여 고윳값 $-1$을 생성하는 법을 배웁니다.
부분 공간 구조: 이 특정 헤드는 다른 헤드들에 비해 현저히 낮은 차원의 선형 부분 공간에서 작동하며, 이는 치환 추적에 필요한 이론적 요구 사항과 일치합니다.
개입(Intervention): 이 특정 헤드의 $\beta$ 범위를 $[0, 1]$ 로 다시 제한하면 즉각적인 성능 붕괴가 발생하며, 다른 헤드들을 조정하는 것은 아무런 영향을 미치지 않습니다. 이는 해당 헤드가 전용 상태 추적 메커니즘임을 확인시켜 줍니다.

3. 확률적 설정에서의 선형 RNN의 한계

본 논문은 선형 RNN이 결정론적 과업은 해결하지만, 확률적 설정(PFSA-SR)에서는 본질적인 장벽에 부딪힌다는 점을 입증합니다:

지수적 감소: 결합 표현 하에서, 부분 노출은 비정규화된 상태 노름을 지수적으로 감소시킵니다( $1/2 \to 1/4 \to 1/8 \dots$ ). 이는 선형 재귀가 필요한 비선형 정규화를 수행할 수 없기 때문입니다.
적대적 취약성: 주변 표현 하에서도, 적대자는 확률적 스왑과 선택적 노출을 구성하여 미노출 항목의 확률 질량이 유한한 정밀도 내에서 사라질 때까지 지수적으로 감소하게 만들 수 있습니다.
결론: 재귀 과정 내의 비선형 정규화나 빈번한 전체 상태 리셋 없이는, 부분 관측성이 존재하는 확률적 설정에서 안정적인 믿음 유지는 선형 RNN에게 불가능해 보입니다.

의의 및 주장

본 논문은 단순한 시퀀스-투-시퀀스 벤치마크를 넘어, 언어 모델의 다음 토큰 예측 목적에 부합하는 더 현실적인 상태 추적 테스트베드를 제공한다고 주장합니다.

간극 해소: 선형 RNN(특히 확장된 고윳값을 가진 DeltaNet)이 코드와 같은 트레이스의 다음 토큰 예측을 통해 상태 추적 능력을 학습할 수 있는 반면, 트랜스포머는 그렇지 못함을 보여줍니다.
이론적 장벽: 실세계 코드 시나리오에서의 선형 RNN의 근본적인 한계를 식별합니다. 실제 코드는 확률적 전이와 부분 관측 가능성(예: 숨겨진 분기, 무작위 선택)을 포함하는 경우가 많습니다. 저자들은 이러한 환경에서 상태를 추적하려면 비선형 정규화가 필요하며, 선형 RNN은 이를 내부적으로 수행할 수 없음을 보여줍니다. 이는 관찰된 "복잡성 격차"가 단순히 시퀀스 길이이나 복잡성 때문이 아니라, 확률적 성격에서 기인할 수 있음을 시사합니다.
벤치마킹에 대한 시사점: 결정론적 유한 상태 오토마타(DFA) 과업만으로 아키텍처를 벤치마킹하는 것은 비선형 RNN의 잠재력과 선형 RNN의 한계를 가릴 수 있다고 주장합니다. 제안된 PFSA-SR 프레임워크와 그 실패 모드(지수적 노름 감소)는 왜 표준적인 선형 재귀 모델이 불확실성 추론이 요구될 때 어려움을 겪는지에 대한 이론적 설명을 제공합니다.

결론적으로, 저자들은 실험이 합성 치환 그룹에 집중되어 있음을 언급하며, 향후 연구를 통해 이를 실제 실행 트레이스로 확장하고 선형 재귀와 주기적인 비선형 정규화를 교차하는 하이브리드 아키텍처를 조사할 필요가 있다고 겸허히 밝히며 마무리합니다.