1. 문제 정의 (Problem)

트랜스포머 기반 에이전트 (LLM 에이전트) 는 체인 오브 씽킹 (Chain-of-Thought, CoT) 을 통해 추론 능력을 확장하고, 도구 호출을 통해 외부 메모리를 활용합니다. 그러나 에이전트의 외부 상태 (external state) 가 어떻게 조직화되는지가 추론 비용 (retrieval cost) 에 미치는 영향은 형식적으로 분석되지 않았습니다.

• 현재의 한계: 에이전트의 대화 기록은 대부분 순차적인 테이프 (sequential tape) 형태로 저장됩니다. 새로운 정보가 추가될 때마다 이전 내용을 스캔해야 하므로, 저장소 크기가 $N$일 때 특정 항목을 찾는 비용은 선형적으로 증가합니다 ($\Omega(N)$).
• 핵심 질문: 외부 메모리를 순차적으로 스캔하는 방식과, 색인 (index) 을 통해 무작위 접근 (random access) 을 하는 방식 사이에는 어떤 계산적 차이가 존재하며, 이것이 에이전트의 장기 추론 능력에 어떤 영향을 미치는가?

2. 방법론 (Methodology)

2.1 형식적 모델링 (The Library Theorem)

저자는 트랜스포머의 **컨텍스트 윈도우 (context window)**를 I/O 페이지로 정의하고, 외부 저장소를 파일 시스템이나 B-트리와 같은 구조로 모델링했습니다.

• 순차 접근 (Sequential Access): 대화 기록처럼 순서대로 읽는 방식. 최악의 경우 $N$개의 페이지를 읽어야 함 ($\Omega(N)$).
• 색인 접근 (Indexed Access): B-트리 구조를 통해 키 (키워드/파일명) 로 직접 접근하는 방식. $O(\log_b N)$의 비용으로 목표 페이지 도달.
• 정리 (Theorem):
  • 단일 검색 비용: 순차 접근은 $O(N)$, 색인 접근은 $O(\log_b N)$으로 지수적 격차가 존재함.
  • 누적 비용: $T$단계의 추론 과정에서 저장소가 성장할 때, 순차 접근의 누적 비용은 $\Theta(T^2)$인 반면, 색인 접근은 $O(T \log_b T)$로 훨씬 효율적임.

2.2 실험 설계

이론적 예측을 검증하기 위해 통제된 룩업 (lookup) 벤치마크를 설계했습니다.

• 모델: GPT-4o-mini (주력), GPT-5.4 (검증).
• 조건 (Access Models):
  1. FLAT: 페이지가 무작위 순서로 정렬됨. 색인 없음.
  2. INDEXED: 페이지가 색인 (목차) 을 통해 접근 가능.
  3. FLAT-SORTED: 페이지가 정렬되어 있으나 색인 없음 (이진 탐색 가능 여부 테스트).
  4. DEEP-INDEXED: 2 단계 색인 구조 (섹션 TOC $\to$ 페이지 TOC).
• 콘텐츠 유형 (Content Types):
  1. Hash: 무작위 문자열 (모델이 학습한 바 없음).
  2. Numeric: 정렬된 정수 (예측 가능하지만 추상적).
  3. Encyclopedia: 모델이 학습한 실세계 사실 (높은 친숙도).

3. 주요 기여 (Key Contributions)

1. 형식적 분리 증명: 트랜스포머 컨텍스트 윈도우를 I/O 페이지로 간주하여, 순차적 검색과 색인 기반 검색 사이의 지수적 비용 분리를 수학적으로 증명했습니다.
2. 3 가지 예측 및 검증:
   • 컨텍스트 천장 (In-context ceiling): 외부 메모리 없이 컨텍스트 윈도우 내에서만 추론할 경우, 선형적 검색 한계를 벗어날 수 없음.
   • 색인의 이점 (Indexed advantage): 구조화된 메모리가 비구조화된 메모리보다 $N$이 커질수록 성능 이점이 기하급수적으로 증가함.
   • 깊이에 따른 누적 (Compounding with depth): 추론 단계가 깊어질수록 색인 접근의 효율성 이득이 누적됨.
3. 파라메트릭 메모리 경쟁 (Parametric Memory Competition) 발견: 모델이 콘텐츠에 익숙할 경우, 색인 프로토콜을 따르기보다 학습된 지식 (파라메트릭 메모리) 에서 답을 생성하여 실패하는 새로운 실패 모드를 발견했습니다.
4. 설계 원칙 제시: 에이전트 메모리 시스템은 **색인 구축 (Index Construction)**에는 언어 모델 (의미 이해) 을 사용하고, **색인 탐색 (Index Traversal)**에는 결정론적 알고리즘을 사용해야 함을 제안했습니다.

4. 실험 결과 (Results)

4.1 추상적 콘텐츠 (Hash 및 Numeric)

• 색인 접근 (INDEXED): 저장소 크기 ($M$) 가 50 에서 5,000 으로 증가해도 중앙값 1 회의 페이지 읽기로 목표에 도달했습니다 ($O(1)$ 예측 확인).
• 순차 접근 (FLAT): 페이지 읽기 횟수가 $M$에 비례하여 선형적으로 증가 ($\approx M/20$).
• 정렬된 순차 접근 (FLAT-SORTED): 작은 규모에서는 이진 탐색을 시도했으나, 규모가 커지면 ($M=500$) 모델이 탐색 범위를 잃고 선형 스캔으로 회귀했습니다. GPT-5.4 는 더 잘 수행했으나 여전히 명시적 색인 (INDEXED) 에 비해 5 배 이상의 비용 차이가 발생했습니다.
• 토큰 비용: FLAT 방식은 $M^2$에 비례하여 토큰 소모가 급증한 반면, INDEXED 방식은 선형적으로만 증가했습니다 ($M=2,000$ 시 154 배 차이).

4.2 친숙한 콘텐츠 (Encyclopedia) 및 실패 모드

• 파라메트릭 메모리 경쟁: 모델이 encyclopedia 내용을 인식하자, 페이지를 읽는 대신 학습된 지식에서 답을 생성하려 했습니다.
• 결과: 토큰 예산을 소모하는 환각 (hallucination) 루프에 빠졌고, 정확도가 급격히 하락했습니다 (예: $M=200$ 시 정확도 27%). 이는 구조적 문제가 아니라 콘텐츠 친숙도로 인한 프로토콜 우회 실패였습니다.

4.3 다중 모델 검증

• GPT-5.4 는 GPT-4o-mini 보다 이진 탐색 능력이 우수했으나, **명시적 색인 (INDEXED)**을 사용할 때의 효율성 (1 회 읽기) 을 대체하지는 못했습니다. 이는 구조적 접근 방식의 이점이 모델의 능력 향상만으로는 해결되지 않음을 시사합니다.

5. 의의 및 결론 (Significance)

이 논문은 에이전트 아키텍처 설계에 다음과 같은 근본적인 통찰을 제공합니다:

1. 파일 시스템의 필요성: 에이전트가 자신의 추론 상태를 파일 시스템 (명명된 파일, 색인) 으로 조직화하는 것은 단순한 편의가 아닌 계산적 필수 조건입니다. 이는 2 차 (quadratic) 비용에서 로그 - 선형 (log-linear) 비용으로의 전환을 가능하게 합니다.
2. 구축과 탐색의 분리 (Separation of Concerns):
   • 색인 구축 (Construction): 언어 모델의 의미 이해 능력을 활용하여 데이터를 어떻게 이름 짓고 조직할지 결정합니다.
   • 색인 탐색 (Traversal): 모델이 내용을 "알고 있어" 프로토콜을 우회하는 것을 방지하기 위해, 색인을 탐색하는 과정은 결정론적 알고리즘이 수행해야 합니다. (파일명만 입력하고 페이지를 읽는 기계적 과정)
3. 확장된 인지 (Extended Cognition): 외부 메모리 구조는 에이전트의 인지 능력을 구성하는 핵심 요소입니다. 색인화된 외부 저장소는 에이전트에게 지수적으로 확장된 추론 능력을 부여하지만, 모델이 내부 지식에 의존하여 이를 우회할 경우 그 이점은 사라집니다.

결론적으로, "도서관 정리"는 에이전트의 성능 한계가 모델의 지능 자체보다는 외부 메모리의 조직화 방식에 의해 결정될 수 있음을 보여주며, 효율적인 에이전트 설계를 위해서는 의미적 이해와 결정론적 탐색을 분리하는 아키텍처가 필수적임을 주장합니다.