State Space (상태 공간 / 문제 공간)

초기 상태에서 목표 상태로 나아가는 지능의 지도(Map of Intelligence). 뉴얼과 사이먼의 고전 문제 해결 탐색부터 침팬지 술탄의 통찰, 최신 LLM의 Tree-of-Thoughts 및 추론 시간 탐색(o1/R1), 그리고 트랜스포머의 계산 한계를 극복하는 혁신적 차세대 아키텍처인 상태 공간 모델(SSM, Mamba)까지 총체적으로 조망합니다.

💡 "문제는 상태들의 미로이며, 조작자는 통로이고, 지능적 해결은 상태 공간의 최적 탐색 과정이다" — Allen Newell & Herbert Simon

📑 핵심 목차 안내

1. 상태 공간의 기본 개념과 문제 해결 → 2. 침팬지 술탄과 암시적 그래프 표현 → 3. 탐색 분류: 무정보 vs 휴리스틱 → 4. [인포그래픽 1] 상태 공간 70년 진화도 ★ 5. [Deep Research] LLM 추론과 상태 공간 ★ 6. [아키텍처 혁신] 상태 공간 모델(SSM / Mamba) ★ 7. Transformer vs SSM (Mamba) 전면 비교 ★ 8. [인포그래픽 2] 모델 비교 매트릭스 ★

1. 상태 공간(State Space)의 기본 개념과 문제 해결

문제 해결 (Problem Solving) 은 다양한 문제 상태로 구성된 문제 공간(Problem Space)의 탐색 (Search) 으로 흔히 설명됩니다. 한 상태 (State) 는 문제의 해결 정도를 나타냅니다:

출발점

초기 상태 (Initial State)

문제 해결자가 처음 당면하는 현재 상황과 초기 조건 자료구조.

경로상태

중간 상태 (Intermediate State)

연산자를 적용하여 목표를 향해 한 단계씩 나아가고 있는 과도기 상황.

도달점

목표 상태 (Goal State)

문제의 최종 요구조건이 완벽히 충족된 성공 상태.

"여기서 문제는 문제 공간의 초기 상태에서 목표 상태에 이르기까지 일련의 가능한 조작자들을 찾는 것이다."

"문제 공간은 상태의 미로로, 그리고 조작자는 상태 간을 이동하는 통로로 생각할 수 있다. 이렇게 생각하면, '해결'은 검색(Search), 즉 문제 해결자가 상태들의 미로에서 적절한 통로를 찾는 과정을 통해 이루어진다."

카네기 멜런 대학교의 Allen Newell 과 Herbert Simon 이 문제 해결을 상태 공간의 검색(Search in State Space)으로 보는 인지주의적 입장을 확립하였고, 이 패러다임은 인지심리학과 인공지능 (Artificial Intelligence) 모두에서 반세기 이상 지배적인 문제 해결 분석의 근간이 되었습니다.

— John R. Anderson (1995), 문제 공간과 검색 (Problem Space and Search)

2. 침팬지 술탄의 문제 해결과 암시적·명시적 상태 그래프

Chimpanzee problem solving : 침팬지는 바나나를 어떻게 먹을 것인가?

볼프강 쾰러(Wolfgang Köhler)의 통찰 학습 실험: 침팬지 술탄은 바나나에 닿지 않는 초기 상태에서, '상자 쌓기'와 '막대기 연결'이라는 연산자(조작자)를 결합하여 목표 상태(바나나 획득)에 도달하는 상태 공간 탐색을 성공시켰습니다.

실제적인 문제들의 대부분은 탐색 공간이 너무 방대하기 때문에 명시적인(explicit) 전체 그래프로 미리 메모리에 펼쳐둘 수 없습니다. 이 경우에는 명시적인 계획 (planning) 에서 설명한 기본적인 탐색 방법에 다음과 같은 근본적 수정이 필요합니다:

첫째: 이러한 문제들을 상태 공간 탐색 문제로 정형화(Formulation)하는 방법에 있어서 매우 신중해야 합니다.
둘째: 방대한 탐색 그래프를 암시적으로 (implicitly) 표현하는 방법이 있어야 합니다.
셋째: 이런 방대한 그래프를 실시간으로 탐색하기 위한 효율적인 휴리스틱 방법이 있어야 합니다.

시작 상태로부터 행동을 취하여 도달될 수 있는 상태 공간 그래프의 영역은 시작 상태의 정의와 각 행동들에 대한 정의에 의해 암시적으로 표현됩니다. 따라서 원칙적으로 암시적인(implicit) 그래프 표현으로부터 필요한 부분의 명시적인(explicit) 그래프를 그때그때 동적으로 만들어 내는 것이 가능합니다.

⚙️ 상태공간 그래프 암시적 표현의 3가지 기본 요소

1. 시작 노드 (Start Node) 의 표현: 문제의 초기 상태를 나타내는 컴퓨터 내부 자료 구조.

2. 연산자 (Operator) / 행동 전이 함수: 하나의 상태를 어떤 행동의 결과 상태로 바꾸어주는 함수. 부모 노드에 연산자가 적용되면 새로운 자식 노드를 동적으로 생성(Expand)합니다.

3. 목표 조건 (Goal Condition): 어떤 상태 표현에 대해 참 또는 거짓을 판정하는 검증 함수이거나, 목표 상태들의 집합 리스트.

3. 탐색(Search)의 2대 분류: 무정보 탐색 vs 휴리스틱 탐색

상태 공간에서 경로를 찾아내는 탐색 (Search) 방법은 크게 두 종류로 나뉩니다:

Blind Search

무정보 (Uninformed / Blind) 탐색

목표까지의 경로를 찾는 데 있어서 탐색 공간의 어떤 한 부분을 다른 부분에 비해 더 유망하다고 선호할 만한 판단 근거가 전혀 없는 경우에 사용하는 방법입니다. (예: 너비 우선 탐색 BFS, 깊이 우선 탐색 DFS).

Heuristic Search

휴리스틱 (Heuristic) 탐색

탐색을 가장 유망한 한 부분에 집중시킬 수 있도록 해주는 그 문제 고유의 도메인 지식(평가 함수 h(n))이 있는 경우에 사용하는 방법입니다. (예: 최적 우선 탐색, A* 알고리즘).

— Nils J. Nilsson (1998), 상태공간 그래프 (State-Space Graphs), 상태공간의 설정 (Formulating the State Space)

4. [인포그래픽 1] 상태 공간(State Space) 패러다임의 70년 진화

1950~70s

심볼릭 탐색 공간

뉴얼&사이먼의 General Problem Solver. 하노이 탑, 퍼즐 등 기호 논리 규칙에 따른 이산 그래프 탐색.

1990~2010s

게임 트리 & MCTS

체스(Deep Blue)와 바둑(AlphaGo). 10¹⁷⁰의 천문학적 상태 공간을 딥러닝 가치망과 몬테카를로 탐색으로 돌파.

2020~2024

LLM 사고 사슬 탐색

Tree-of-Thoughts, o1, DeepSeek-R1. 언어 생성 과정을 다단계 사고 상태 공간(Reasoning State Space)으로 정형화.

2024+ 차세대

상태 공간 모델(SSM)

Mamba, S4, Jamba. 트랜스포머의 O(N²) 병목을 고정 은닉 상태 h_t의 선형 O(N) 순환으로 대체하는 모델 혁신.

Deep Research

5. 최신 LLM에서 State Space가 중요한 의미를 갖는 이유와 실전 활용

"단순한 텍스트 완성을 넘어선 다단계 추론 탐색" & "트랜스포머의 메모리 한계를 부수는 차세대 시퀀스 아키텍처"

🧭 1. 토큰 생성을 '상태 공간 탐색(State-Space Search)'으로 재정의

과거의 LLM은 단순히 이전 단어들을 보고 다음 단어를 좌에서 우로 탐욕스럽게 출력(Greedy Decoding)하는 1차원 생성기였습니다. 그러나 수학, 코딩, 복잡한 정책 수립과 같은 고난도 문제에서는 이러한 탐욕적 생성이 치명적인 오류와 환각으로 이어집니다.

현대 AI는 LLM의 생성 과정을 상태 공간 탐색으로 엄밀히 재정의했습니다:

상태 (State s_t): 현재까지 누적된 프롬프트와 중간 사고 단계(Thought Step)의 컨텍스트.
행동 (Action a_t): 어휘 사전에서 선택할 다음 토큰 또는 한 단위의 논리적 문장.
전이 (Transition): 선택된 행동이 컨텍스트에 덧붙여져 다음 상태 s_t+1로 전이.
목표 판정 (Goal Condition): 최종 코드가 단위 테스트를 통과하거나 수학적 증명이 완결된 상태.

🌳 2. Tree-of-Thoughts(ToT)와 추론 시간 연산 (OpenAI o1, DeepSeek-R1)

이러한 상태 공간 프레임워크 위에서 탄생한 것이 바로 사고 트리 (Tree-of-Thoughts, ToT) 와 최신 추론 특화 AI인 OpenAI o1 및 DeepSeek-R1의 핵심 아키텍처입니다.

모델은 오답 가능성이 높은 외길 경로를 맹목적으로 달리지 않고, 체스 컴퓨터처럼 여러 대안 사고 상태를 전개한 후 프로세스 보상 모델(PRM, Process Reward Model)을 통해 각 상태의 유망성을 평가합니다. 유망하지 않은 분기는 조기에 가지치기(Pruning)하고, 막다른 골목에 도달하면 이전 상태로 되돌아가는 역추적(Backtracking)을 수행함으로써 난공불락의 복잡한 문제를 완벽히 해결합니다.

🤖 3. 자율 에이전트(Agentic AI)의 행동 계획과 환경 상태

웹 브라우징, 데이터 분석, 소프트웨어 개발을 자율 수행하는 LLM 에이전트에게 상태 공간은 외부 환경(Environment)의 동적 변화를 의미합니다. 에이전트는 사용자의 컴퓨터 환경을 관찰(Observation)하여 현재 상태를 파악하고, 터미널 명령이나 API 호출이라는 연산자(Operator)를 실행하여 시스템을 목표 상태로 전이시키는 전통적 스트립스(STRIPS) 계획의 현대적 계승자입니다.

6. [아키텍처 혁신] 상태 공간 모델 (State Space Models, SSM: S4 & Mamba)

딥러닝 모델 아키텍처 관점에서 '상태 공간'은 전혀 다른 혁명적 의미를 갖습니다. 고전 제어 이론(Control Theory)의 연속 시간 상태 공간 미분 방정식을 인공신경망으로 이산화하여 시퀀스 데이터를 처리하는 상태 공간 모델(SSM, State Space Models)이 바로 그것입니다:

h'(t) = A h(t) + B x(t) (상태 방정식: 입력 x가 은닉 상태 h를 갱신)

y(t) = C h(t) + D x(t) (출력 방정식: 은닉 상태 h로부터 출력 y 생성)

기존의 S4 모델은 행렬 A, B, C가 시간에 따라 고정된 시불변(Time-invariant) 시스템이어서 복잡한 언어의 문맥 의존성을 담아내지 못했습니다. 이를 돌파한 것이 2023년 Albert Gu와 Tri Dao가 발표한 맘바(Mamba, Selective SSM)입니다:

맘바(Mamba)의 핵심 혁신: 선택적 상태 공간 (Selective SSM)

입력 토큰 x_t에 따라 파라미터 B, C, 및 시간 간격 Δ를 동적으로 변화(Data-dependent Selection)시킵니다. 이를 통해 중요한 정보는 고정 크기 은닉 상태 h_t에 선택적으로 기억하고, 불필요한 조사나 노이즈는 완벽히 망각함으로써 트랜스포머 수준의 정밀한 언어 이해 능력을 선형 시간 O(N)으로 달성했습니다.

7. Transformer vs State Space Model (Mamba) 심층 비교

현대 인공지능 학계의 최대 화두는 "트랜스포머의 어텐션 메커니즘을 상태 공간 모델(SSM)이 대체할 수 있는가?" 입니다. 두 아키텍처는 시퀀스 데이터를 바라보는 철학과 계산 복잡도에서 극명한 차이를 보입니다:

1) 연산 복잡도: O(N²) vs O(N)

트랜스포머: 모든 토큰이 과거의 모든 토큰과 어텐션을 맺으므로 시퀀스 길이 N에 대해 2차(Quadratic) 비용 O(N²) 발생.
SSM (Mamba): 고정된 상태 벡터 h_t만 순환 갱신하므로 선형(Linear) 비용 O(N)으로 초고속 처리.

2) 추론 메모리: 폭증 vs 상수 O(1)

트랜스포머: 추론 시 과거 토큰들의 Key-Value 벡터를 저장하는 KV Cache 메모리가 N에 비례하여 폭발하여 긴 문맥 서빙 불가.
SSM: 과거 전체를 저장하지 않고 고정 크기 은닉 상태 h_t만 유지하므로 메모리 사용량 O(1).

3) 문맥 인출: 완전 기억 vs 정보 압축

트랜스포머: 과거 모든 토큰에 직접 접근(Lossless Memory)하므로 정밀한 단서 인출과 복사에 탁월.
SSM: 모든 정보를 고정된 상태 공간에 압축(Compressed Memory)하므로 10만 토큰 이전의 지엽적 정보 복원에 상대적 약점.

💡 최신 트렌드: 하이브리드 아키텍처 (Jamba & Samba)

트랜스포머의 정밀한 다단계 어텐션 능력과 Mamba의 초고속 선형 처리량을 결합한 하이브리드 모델(예: AI21 Labs의 Jamba)이 급부상하고 있습니다. Mamba 레이어 7개당 어텐션 레이어 1개를 교차 배치하여, KV 캐시 용량을 80% 이상 절감하면서도 트랜스포머와 대등한 정밀 추론 능력을 유지합니다.

8. [인포그래픽 2] Transformer vs State Space Model (Mamba) 비교 매트릭스

비교 항목	트랜스포머 (Transformer Self-Attention)	상태 공간 모델 (Mamba / Selective SSM)
기본 작동 메커니즘	모든 토큰 쌍 간의 유사도를 직접 연산하는 All-to-All 주의집중	연속 시간 미분 방정식을 이산화한 은닉 상태 h_t의 순환 갱신
훈련 연산 복잡도	O(N²) — 시퀀스 길이가 길어질수록 비용 폭증	O(N) — 병렬 스캔(Parallel Scan)을 통한 초고속 병렬 훈련
추론 메모리 (Memory)	O(N) — 과거 모든 토큰의 KV Cache 유지 필수	O(1) — 시퀀스 길이와 무관한 고정된 은닉 상태 크기 유지
토큰 생성 처리량	시퀀스가 길어질수록 메모리 대역폭 병목으로 점차 감속	시퀀스 길이에 무관하게 균일한 고속 생성 (최대 5배)
장문 문맥 처리 (Context)	32k~128k 토큰 이상에서 GPU VRAM 한계 봉착	100만~1,000만 토큰(1M~10M)까지 선형적으로 확장 가능
복잡한 인출 & 복사	과거 토큰의 직접 참조로 지엽적 복사/인출 능력 극강	고정 차원 압축으로 인해 세밀한 복사(Copying)에서 미세 열세
대표 모델	GPT-4, Claude 3.5, Gemini, LLaMA-3	Mamba-1/2, S4, RWKV, Jamba (하이브리드)

🎬 상태 공간 추천 강좌: 고전 탐색부터 Mamba SSM까지 (Videos)

하버드 대학교의 고전 상태 공간 탐색 기초와 머신러닝 엔지니어 Umar Jamil의 Mamba 아키텍처 수학적 심층 분석 강좌.

[하버드 CS50] 탐색 이론과 상태 공간(State Space)

초기 상태, 연산자, 목표 조건 및 BFS/DFS와 A* 휴리스틱 탐색 알고리즘 원리.

[딥러닝 아키텍처] Mamba와 상태 공간 모델(SSM) 완벽 해설

연속 시간 미분 방정식, 선택적 상태 공간 메커니즘, 병렬 스캔 및 트랜스포머와의 비교.

9. 학술 원전 논문 및 관련 핵심 용어 (Reference Hub)

인지심리학 고전

🔗 관련 핵심 개념 및 탐색 알고리즘

문제해결 (Problem Solving) 탐색 (Search) 무정보 탐색 (Blind Search) 휴리스틱 탐색 계획 (Planning) 인공지능 (AI) Allen Newell Herbert Simon