무한을 넘어서: 도구 사용이 상태 공간 모델의 길이 일반화를 해제하다

기본 정보

• 논문 ID: 2510.14826
• 제목: To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models
• 저자: Eran Malach, Omid Saremi, Sinead Williamson, Arwen Bradley, Aryo Lotfi, Emmanuel Abbe, Josh Susskind, Etai Littwin
• 기관: Apple
• 분류: cs.LG
• 발표 시간: 2025년 10월 17일
• 논문 링크: https://arxiv.org/abs/2510.14826

초록

상태 공간 모델(SSMs)은 시퀀스 모델링에서 Transformer의 주요 대안으로 부상했으며, 고정 크기 메모리와 선형 계산 복잡도를 통해 긴 컨텍스트와 긴 시퀀스 생성의 효율성을 실현하는 것이 주요 장점입니다. 본 논문은 먼저 SSMs이 공식적으로 정의된 의미에서 어떤 "진정한 긴 시퀀스" 생성 문제도 정확하게 해결할 수 없음을 증명하는 간단한 이론적 결과를 제시하며, 이는 주요 경쟁 우위를 약화시킵니다. 그러나 연구에 따르면 이러한 제한은 SSMs에 대화형 외부 도구 접근을 제공함으로써 완화될 수 있습니다. 실제로 도구 접근과 문제 관련 훈련 데이터를 올바르게 선택하면 SSMs은 모든 처리 가능한 문제를 해결하고 임의의 문제 길이/복잡도로 일반화하는 방법을 학습할 수 있습니다. 이론적 발견을 바탕으로 저자들은 도구 증강 SSMs이 다양한 산술, 추론 및 프로그래밍 작업에서 현저한 길이 일반화 능력을 달성함을 증명했습니다.

연구 배경 및 동기

문제 배경

1. Transformer의 계산 병목: Transformer는 주의 메커니즘으로 인해 계산 복잡도가 시퀀스 길이에 따라 이차적으로 증가하고 메모리가 길이에 따라 선형적으로 증가하여 긴 컨텍스트와 긴 시퀀스 생성 작업에서 주요 제한이 됩니다.
2. SSMs의 부상: 이 문제를 해결하기 위해 연구자들은 선형 Transformer 및 상태 공간 모델(SSMs)(Mamba, DeltaNet 등 포함)과 같은 다양한 대체 아키텍처를 제안했으며, 이들은 고정 메모리와 선형 계산 복잡도를 실현합니다.
3. SSMs의 한계: SSMs이 효율성에서 장점이 있음에도 불구하고 일부 연구에서는 긴 시퀀스 메모리와 컨텍스트 학습이 필요한 작업에서 상당한 한계가 있음을 지적합니다.

연구 동기

저자들은 특히 출력 길이가 문제 복잡도에 따라 증가하는 작업에서 긴 시퀀스 생성 작업에서 SSMs의 능력과 한계를 이해하는 것을 목표로 합니다. 이들은 SSMs이 Transformer에 비해 명백한 추론 효율 우위를 보이는 작업 유형입니다.

핵심 기여

1. 이론적 부정적 결과: SSMs이 사고의 사슬(CoT) 생성의 임의 길이를 허용하더라도 "진정한 긴 시퀀스 생성 문제"를 정확하게 해결할 수 없음을 증명합니다.
2. 도구 사용의 이론적 프레임워크: ReAct 에이전트 연구를 위한 새로운 이론적 프레임워크를 도입하고 대화형 도구 사용이 SSMs의 능력을 크게 향상시킬 수 있음을 증명합니다.
3. 길이 일반화의 충분성 정리: 적절한 도구 접근과 특정 훈련 데이터를 갖춘 SSMs이 모든 처리 가능한 긴 시퀀스 생성 작업에서 길이 일반화를 달성할 수 있음을 증명합니다.
4. 실험 검증: 산술, 논리 추론 및 프로그래밍 작업에서 도구 증강 SSMs의 우수한 길이 일반화 능력을 시연합니다.

방법 상세 설명

작업 정의

긴 시퀀스 생성 작업의 공식적 정의:

• Σ를 어휘집합이라 하고, X₁,X₂,...와 Y₁,Y₂,...를 각각 입력 및 출력 공간 시퀀스라 합니다.
• D₁,D₂,...를 분포 시퀀스라 하며, 여기서 Dₙ은 Xₙ 위의 분포입니다.
• f: Σ* → Σ*를 f(Xₙ) ⊆ Yₙ을 만족하는 실제 함수라 합니다.

정의 2.2: (f, {Dₙ})을 커버리지 α의 긴 시퀀스 생성 작업이라 부르는 것은 suppₐ(f(Dₙ))이 n에 대해 단조 증가하고 limₙ→∞ suppₐ(f(Dₙ)) = ∞일 때만입니다.

일반화된 상태 공간 모델(GSSM)

정의: GSSM은 다음 구성 요소로 정의됩니다:

• 상태 공간 S (유한 집합)
• 초기 상태 s₀ ∈ S
• 업데이트 규칙 u: S × Σ → S
• 출력 규칙 r: S → Δ(Σ)

도구 사용 설정:

1. CoT만: 생각과 출력 토큰만 허용
2. 단일 라운드 도구 사용: 단일 도구 호출 허용
3. 대화형 도구 사용: 임의 횟수의 도구 호출 및 자유로운 교차 허용

핵심 이론적 결과

정리 2.1(부정적 결과): 커버리지 α의 모든 긴 시퀀스 생성 작업 f에 대해, 모든 n ≥ n₀에 대해 CoT만 또는 단일 라운드 도구 사용의 모든 GSSM h가 다음의 오류율을 갖도록 하는 문제 복잡도 n₀이 존재합니다: errₙ(h) ≥ 1-α.

정리 2.2(긍정적 결과): 메모리 도구 오라클 O와 단순 GSSM 학습 알고리즘 A가 존재하여, 모든 계산 가능한 긴 시퀀스 생성 작업 f에 대해, A가 대화형 설정에서 길이 일반화를 달성하도록 하는 훈련 분포 시퀀스 {Pₙ}이 존재합니다.

기술적 혁신점

1. 메모리 도구 설계: 외부 메모리 접근에 대한 읽기/쓰기를 제공하는 포인터 기반 도구로, 튜링 기계 작동을 시뮬레이션할 수 있습니다.
2. 대화형 훈련 패러다임: 도구 사용 궤적을 포함하는 훈련 데이터를 구성하여 SSMs이 외부 메모리를 활용하여 내부 메모리 제한을 극복하도록 학습합니다.
3. 알고리즘 궤적 생성: 다양한 작업(덧셈, 곱셈, 논리 추론 등)에 대해 필요한 알고리즘을 정확하게 시뮬레이션하는 합성 도구 사용 궤적을 설계합니다.

실험 설정

데이터셋

1. 산술 작업: 다중 자릿수 덧셈 및 곱셈, 훈련 길이 최대 5-10자리, 테스트 최대 1000자리
2. 하노이 탑: 훈련 최대 8개 디스크, 테스트 최대 12개 디스크
3. 논리 그래프 추론: 훈련 최대 10개 노드, 테스트 최대 1000개 노드
4. 코드 수정: 훈련 최대 16개 함수의 코드베이스, 더 큰 규모 테스트

모델 구성

• SSMs: Mamba-130M/1.4B, LSTM, GRU
• Transformers: Pythia-160M/1.4B, Mistral (슬라이딩 윈도우 주의)
• 모든 모델 규모 동일(~130M 파라미터)

도구 유형

1. 포인터 기반 메모리: 초기화, 이동, 읽기 작동 지원
2. 검색 도구: 컨텍스트에서 패턴 검색 지원
3. Bash 명령: 코드 수정 작업을 위한 파일 작동

실험 결과

주요 결과

산술 작업 성능:

• Mamba는 5자리 훈련 후 1000자리 덧셈을 완벽하게 실행(100% 정확도)
• 곱셈 작업: 10자리×1자리 훈련 → 1000자리×1자리 테스트(100% 정확도)
• Transformer 모델은 훈련 길이를 초과하여 거의 일반화하지 못함

추론 작업 성능:

• 논리 그래프 추론: 10노드 훈련 → 1000노드 테스트(98% 정확도)
• 하노이 탑: 8디스크 훈련 → 12디스크 테스트(49% 정확도, 지수 수준 출력 길이 증가)

코드 수정 작업:

• 대화형 에이전트 훈련 하에서 Mamba는 대규모 코드베이스에서 더 나은 성능 유지
• Transformer는 소규모 코드베이스에서 더 나은 성능을 보이지만 더 큰 규모로 일반화하지 못함

소거 실험

주요 발견:

1. CoT 또는 도구 사용 제거는 길이 일반화 능력을 거의 완전히 상실
2. 단일 라운드 도구 사용의 효과는 제한적이며 대화형 사용이 필수
3. 작업 혼합 훈련은 제한된 예산 하에서 일반화 개선 가능

실험 발견

1. 아키텍처 우위: SSMs/RNNs는 도구 증강 설정에서 Transformer보다 현저히 우수
2. 상호작용의 중요성: 대화형 도구 사용은 길이 일반화 달성의 핵심
3. 훈련 데이터 품질: 정교하게 구성된 알고리즘 궤적이 성공에 필수
4. 확장성: 방법은 다양한 알고리즘 작업으로 확장 가능

관련 연구

주요 연구 방향

1. 사고의 사슬 및 스크래치패드: CoT는 LLMs의 추론 능력을 크게 향상시키고 이론적으로 표현 능력과 학습 가능성을 개선
2. 신경 튜링 기계: 신경망으로 튜링 기계를 시뮬레이션하려는 초기 시도이나 광범위하게 채택되지 않음
3. 길이 일반화: Transformer의 길이 일반화를 연구하는 광범위한 작업으로 다양한 개선 기술 제안

본 논문의 기여

• SSMs의 길이 일반화 이론적 제한을 처음으로 체계적으로 연구
• 도구 사용을 제한 극복의 효과적인 솔루션으로 제안
• 독립 모델이 아닌 에이전트 시스템의 맥락에서 아키텍처 성능 분석

결론 및 논의

주요 결론

1. SSMs은 독립적으로 사용할 때 근본적인 길이 일반화 제한이 존재
2. 대화형 도구 사용은 이러한 제한을 완전히 극복 가능
3. 에이전트 설정에서 SSMs은 Transformer보다 우수할 수 있음

한계

1. 이론 분석의 학습 알고리즘은 상대적으로 단순(문자열 매칭)
2. 하노이 탑 등 지수 출력 길이 작업의 일반화는 제한적
3. 정교하게 설계된 훈련 궤적 필요
4. 코드 수정 작업의 일반화 정도 제한적

향후 방향

1. SSM 기반 도구 사용 에이전트 개발
2. 더 자연스러운 학습 알고리즘(예: 경사 하강법)의 이론적 보장 연구
3. 더 복잡한 추론 및 에이전트 작업으로 확장
4. 혼합 아키텍처의 잠재력 탐색

심층 평가

장점

1. 이론적 엄밀성: SSMs 한계의 엄격한 수학적 증명 제공
2. 실용적 가치: 도구 사용의 실제 효과성 시연
3. 실험의 포괄성: 다양한 작업 유형 및 모델 아키텍처 포함
4. 깊이 있는 통찰: 아키텍처가 시스템에서의 성능이 독립적 사용과 다를 수 있음을 드러냄

부족한 점

1. 이론과 실제의 간격: 이론 분석의 단순 학습 알고리즘과 실제 신경망 훈련 간의 차이
2. 작업 한계: 주로 알고리즘 작업에 초점으로 개방형 생성 작업에 대한 적용 가능성 불명확
3. 공학적 복잡성: 각 작업에 대해 특정 도구 및 훈련 궤적 설계 필요
4. 확장성 문제: 더 복잡한 실제 작업에서의 성능 아직 검증 필요

영향력

1. 이론적 기여: 다양한 아키텍처의 근본적 능력 차이 이해를 위한 새로운 관점 제공
2. 실무 지침: 에이전트 시스템에서 SSM 적용을 위한 이론적 지원 제공
3. 연구 방향: 도구 증강 언어 모델에 관한 더 많은 연구를 추진할 가능성

적용 시나리오

1. 알고리즘 실행: 알려진 알고리즘의 정확한 실행이 필요한 작업
2. 긴 시퀀스 처리: 계산 자원이 제한적이지만 긴 시퀀스 처리가 필요한 시나리오
3. 에이전트 시스템: 외부 도구와 상호작용이 필요한 지능형 에이전트 응용
4. 교육 응용: 알고리즘 실행 과정을 시연하는 교육 시스템

참고 문헌

본 논문은 해당 분야의 중요한 작업을 인용하며, 다음을 포함합니다:

• Transformer 원본 논문 (Vaswani et al., 2017)
• Mamba 등 SSM 아키텍처 (Gu & Dao, 2023)
• 사고의 사슬 관련 연구 (Wei et al., 2022)
• ReAct 프레임워크 (Yao et al., 2023)
• 길이 일반화 관련 작업 (Zhou et al., 2024 등)

요약: 이는 이론과 실험을 모두 중시하는 고품질 논문으로, SSMs의 능력 경계와 도구 사용의 가치를 이해하기 위한 중요한 통찰력을 제공합니다. 실제 응용의 확장성 측면에서 아직 검증이 필요하지만, 이론적 기여와 실험 발견은 해당 분야 발전을 추진하는 데 중요한 의미를 갖습니다.