2025-11-12T10:58:10.220342

AI Agents as Universal Task Solvers

Achille, Soatto
AI reasoning agents are already able to solve a variety of tasks by deploying tools, simulating outcomes of multiple hypotheses and reflecting on them. In doing so, they perform computation, although not in the classical sense -- there is no program being executed. Still, if they perform computation, can AI agents be universal? Can chain-of-thought reasoning solve any computable task? How does an AI Agent learn to reason? Is it a matter of model size? Or training dataset size? In this work, we reinterpret the role of learning in the context of AI Agents, viewing them as compute-capable stochastic dynamical systems, and highlight the role of time in a foundational principle for learning to reason. In doing so, we propose a shift from classical inductive learning to transductive learning -- where the objective is not to approximate the distribution of past data, but to capture their algorithmic structure to reduce the time needed to find solutions to new tasks. Transductive learning suggests that, counter to Shannon's theory, a key role of information in learning is about reduction of time rather than reconstruction error. In particular, we show that the optimal speed-up that a universal solver can achieve using past data is tightly related to their algorithmic information. Using this, we show a theoretical derivation for the observed power-law scaling of inference time versus training time. We then show that scaling model size can lead to behaviors that, while improving accuracy on benchmarks, fail any reasonable test of intelligence, let alone super-intelligence: In the limit of infinite space and time, large models can behave as savants, able to brute-force through any task without any insight. Instead, we argue that the key quantity to optimize when scaling reasoning models is time, whose critical role in learning has so far only been indirectly considered.
academic

AI 에이전트를 범용 작업 해결자로: 모두 시간에 관한 것

기본 정보

  • 논문 ID: 2510.12066
  • 제목: AI Agents as Universal Task Solvers: It's All About Time
  • 저자: Alessandro Achille, Stefano Soatto (AWS Agentic AI)
  • 분류: cs.AI, cs.LG
  • 발표 시간: 2025년 9월 12일 (arXiv preprint)
  • 논문 링크: https://arxiv.org/abs/2510.12066

초록

본 논문은 AI 에이전트의 역할을 계산 능력을 갖춘 확률적 동역학 시스템으로 재검토하며, 추론 학습의 기초 원리에서 시간의 핵심적 역할을 강조한다. 저자들은 고전적인 귀납 학습에서 전도 학습(transductive learning)으로의 전환을 제안하며, 목표는 역사적 데이터의 분포를 근사하는 것이 아니라 데이터의 알고리즘 구조를 포착하여 새로운 작업 해결에 필요한 시간을 줄이는 것이다. 연구 결과는 범용 해결자가 역사적 데이터를 활용하여 달성할 수 있는 최적 가속이 알고리즘 정보와 밀접한 관련이 있으며, 관찰된 추론 시간과 훈련 시간의 멱법칙 스케일링에 대한 이론적 유도를 제공한다.

연구 배경 및 동기

핵심 문제

  1. AI 에이전트의 범용성: 사슬 사고 추론(chain-of-thought reasoning)이 모든 계산 가능한 작업을 해결할 수 있는가?
  2. 학습 메커니즘: AI 에이전트는 어떻게 추론을 학습하는가? 모델 규모인가 아니면 훈련 데이터 규모인가?
  3. 스케일링 법칙의 본질: 현재의 정확도 기반 스케일링 법칙이 지능을 진정으로 반영하는가?

연구 동기

전통적인 기계학습은 귀납 학습(inductive learning)에 중점을 두며, 이는 표시된 데이터의 함수를 적합시키고 유사한 입력으로의 일반화를 기대한다. 그러나 에이전트 설정에서는 사전 훈련된 모델이 새로운 작업의 특정 인스턴스를 처리하고 해당 인스턴스를 해결할 수 있어야 한다. 이 과정을 **전도(transduction)**라고 부른다: 테스트 시간에 모델은 모든 사용 가능한 데이터를 활용하고 현재 작업을 해결하기 위해 적극적으로 추론한다.

기존 방법의 한계

  • 현재 스케일링 법칙은 예측 오류를 지능의 대리로 사용하며 시간 비용을 무시한다
  • 모델이 더 강력해질수록, 학습이 불필요해진다. 왜냐하면 모델이 데이터 구조에서 얻은 통찰력이 아닌 전수 계산에 의존할 수 있기 때문이다
  • 무한 자원의 극한에서 모델은 어떤 학습 없이도 무차별 대입을 통해 모든 작업을 해결할 수 있다

핵심 기여

  1. 이론적 프레임워크: AI 에이전트를 확률적 동역학 시스템으로 모델링하여 범용 해결자 이론을 튜링 기계에서 일반 동역학 시스템으로 확장
  2. 시간 개념의 재정의: "고유 시간(proper time)" 개념을 도입하여 확률적 시스템에서 시간 정의의 비자명한 문제 해결
  3. 정보-속도 동등성: 정보가 속도라는 것을 증명 (정리 1.1: log speed-up = I(h : D))
  4. 스케일링 법칙 이론: 추론 모델에서 관찰된 추론 시간과 훈련 시간의 멱법칙 스케일링에 대한 이론적 유도 제공
  5. 스케일링 법칙 역전: 정확도-규모 그래프의 오도성을 드러내고 시간 최적화의 중요성 제안

방법 상세 설명

작업 정의

연구는 **검증 가능한 작업(verifiable tasks)**에 중점을 둔다: 각 문제 인스턴스 x는 작업 특정 함수 f(x,y)와 쌍을 이루며, 모든 후보 해 y를 대화식으로 검증하거나 평가할 수 있다.

핵심 이론 구성

1. 계산으로서의 동역학 시스템

LLM의 사슬 사고 추론을 확률적 동역학 시스템으로 모델링:

  • 상태 공간: S의 상태 s
  • 궤적: h = (s₁, ..., sₙ), 길이 T(h) = n
  • 전이 확률: ν(sₜ₊₁|sₜ)
  • 궤적 확률: ν(h) = ∏ν(sₜ₊₁|sₜ)

2. 고유 시간 정의

정의 2.3: 확률적 동역학 시스템에 대해, 입력 x에서 출력 a로의 고유 시간은 다음과 같이 정의된다:

τᵥ(x ↓ a) = min[T(h)/ν(h|x)]

여기서 최솟값은 enc(x)에서 시작하여 출력 a로 끝나는 모든 궤적 h에 대해 취해진다.

정리 2.4: 결정론적 튜링 기계 Mᵥ가 존재하여:

T_Mᵥ(x ↓ a) ≤ 2τᵥ(x ↓ a)

3. 범용 해결자의 존재성

정리 3.2: 프로그램을 인코딩하는 분포 m이 주어질 때, 동역학 시스템 Uₘ이 존재하여 모든 해결자 A에 대해:

τ_Uₘ(x ↓ y) ≤ C'_A 2^(-log m(A)) τ_A(x ↓ y)

기술적 혁신점

1. 정보-속도 동등성

정리 4.2: 데이터 관찰 후 탐색 알고리즘의 로그 가속은:

log[τᵥ(h)/τᵥ(h|D)] = Iᵥ(h : D)

여기서 Iᵥ(h : D)는 ν-알고리즘 상호 정보이다.

2. Hilberg 추측의 일반화

정의 4.4: 일반화된 Hilberg 추측(GHC) 스케일링:

I(Xₙ : Yₘ) ∝ n^β + m^β - (m+n)^β

3. 시간 스케일링 법칙

정리 4.5: n개 토큰의 충분히 큰 데이터셋 D에서 훈련하여 얻은 로그 가속은:

log[τᵥ(h)/τᵥ(h|D)] = T(h)^β - βT(h)/n^(1-β)

실험 설정

이론적 검증

본 논문은 주로 이론적 작업이며 수학적 증명을 통해 각 정리를 검증한다. 실험적 검증은 주로 다음에서 나타난다:

  1. Santa Fe 프로세스 구성: GHC 스케일링을 만족하는 데이터 생성 프로세스의 명시적 구성
  2. 멱법칙 스케일링의 이론적 유도: 경험적으로 관찰된 추론 시간과 훈련 시간의 멱법칙 관계에 대한 이론적 기초 제공

주요 매개변수

  • β ∈ (0,1): 복잡도 매개변수, "유용한 사실" 분포의 긴 꼬리를 제어
  • 자연어의 경우: β ≈ 0.5, n ∝ L²의 스케일링 관계를 의미

실험 결과

주요 이론적 결과

1. 최대 가속 경계

정리 4.3: 프로세스 q로 생성된 데이터로 달성할 수 있는 최대 가속은:

log[τᵥ(h)/τᵥ(h|D)] ≤ K(q)

여기서 K(q)는 q의 Kolmogorov 복잡도이다.

2. 학습과 시간 최적화

정리 1.5:

  • 시간 페널티가 없을 때, 최적 추론은 학습 없이 무차별 대입을 통해 달성될 수 있다
  • 시간을 최적화하는 모든 시스템은 역사적 데이터에서 최소 I(h : D) = log speed-up 비트를 학습해야 한다

3. 메모리-시간 트레이드오프

따름정리 4.7: 메모리 사용이 최적이라고 가정하면, 사용된 메모리의 함수로서의 가속은:

log[τᵥ(h)/τᵥ(h|D)] = T(h)^β - T(h)/M^(1/β-1)

주요 발견

  1. 복잡성 역설: 오컴의 면도날 원리와 반대로, 복잡한 데이터 생성 프로세스는 실제로 학습에 더 유리하다
  2. 스케일링 법칙 역전: 모델 규모가 증가함에 따라 "학자 모드(savant regime)"에 진입할 수 있으며, 무차별 계산을 통해 높은 정확도를 달성하지만 진정한 통찰력이 부족하다
  3. 시간의 핵심 지위: 지능적 행동은 단순히 정확도가 아닌 단위 시간/계산당 오류 감소를 통해 측정되어야 한다

관련 연구

주요 연구 분야

  1. Solomonoff 귀납법과 범용 탐색: Levin과 Solomonoff의 고전적 작업에 기반
  2. 전도 학습: Vapnik 등의 전도 추론 프레임워크
  3. 문맥 내 학습: 현대 LLM의 문맥 내 학습 능력
  4. 알고리즘 정보 이론: Kolmogorov 복잡도와 알고리즘 상호 정보

본 논문의 기여

  • 범용 탐색 이론을 튜링 기계에서 일반 확률적 동역학 시스템으로 확장
  • 학습에서 시간의 기초적 역할을 제안하여 Shannon 정보 이론의 전통적 관점에 도전
  • LLM의 추론 능력에 대한 이론적 기초 제공

결론 및 논의

주요 결론

  1. 시간은 지능의 핵심: 진정한 지능은 단순히 정확도를 추구하는 것이 아니라 시간 효율성을 최적화해야 한다
  2. 학습의 본질은 가속: 전도 설정에서 학습의 가치는 미보유 작업 해결에 필요한 시간 감소에 있다
  3. 복잡성의 가치: 복잡한 데이터 생성 프로세스는 학습을 위한 더 많은 기회를 제공한다
  4. 스케일링 전략의 재검토: 단순한 모델 규모가 아닌 시간을 최적화해야 한다

한계

  1. 이론적 성질: 주로 이론적 작업이며 대규모 실증적 검증이 부족하다
  2. 가정 제한: GHC 스케일링 가정에 의존하며, 실제 데이터는 완전히 부합하지 않을 수 있다
  3. 계산 가능성 문제: 일부 이론적 결과는 계산 불가능한 양(예: Kolmogorov 복잡도)을 포함한다

향후 방향

  1. 실증적 검증: 실제 LLM 시스템에서 이론적 예측 검증
  2. 알고리즘 설계: 이론적 통찰력을 바탕으로 더 나은 훈련 및 추론 알고리즘 설계
  3. 평가 지표: 시간 비용을 고려하는 지능 평가 지표 개발

심층 평가

장점

  1. 이론적 깊이: AI 에이전트 추론 능력에 대한 깊은 이론적 기초 제공
  2. 개념적 혁신: 학습의 목표를 재정의 (정확도에서 시간 효율성으로)
  3. 수학적 엄밀성: 증명이 완전하고 논리가 명확하다
  4. 실제적 의의: 현재 LLM 스케일링 전략에 중요한 성찰 제공

부족점

  1. 실증적 부족: 이론적 결과는 더 많은 실험적 검증이 필요하다
  2. 복잡성: 수학적 내용이 상당히 추상적이며 실제 적용 진입 장벽이 높다
  3. 가정의 강도: 일부 핵심 가정(예: GHC)의 보편적 적용 가능성은 검증이 필요하다

영향력

  1. 이론적 기여: AI 추론 연구에 새로운 이론적 프레임워크 제공
  2. 실용적 가치: 향후 AI 시스템의 설계 및 평가 지도
  3. 패러다임 전환: 정확도 중심에서 효율성 중심으로의 연구 전환을 촉진할 수 있다

적용 시나리오

  • 대규모 언어 모델의 훈련 전략 설계
  • AI 에이전트의 추론 능력 평가
  • 계산 자원이 제한된 환경에서의 모델 최적화
  • 자동 추론 시스템의 이론적 분석

참고문헌

논문은 풍부한 관련 작업을 인용하며, 다음을 포함한다:

  • Levin (1973): Universal sequential search problems
  • Solomonoff (1964): A formal theory of inductive inference
  • Hilberg (1990): 텍스트 중복 정보에 관한 고전적 작업
  • 현대 심층 학습 및 LLM 관련 연구

본 논문은 AI 에이전트의 추론 능력에 대한 깊은 이론적 통찰력을 제공하며, 특히 학습에서 시간의 핵심적 역할을 강조한다. 주로 이론적 작업이지만, 그 관점은 향후 AI 시스템의 설계에 중요한 영향을 미칠 수 있다.