자기 개선 에이전트의 상대적 계산가능성 이론
A Relative-Computability Theory of Self-Improving Agents
원문 초록
Self-improving agents can acquire a procedure without knowing when its supporting teacher can safely be removed. We extend an oracle-relative model of evolving agents with explicit acquisition and completion contracts, separating learning a solver from certifying its independence. For a known finite-dimensional Boolean feature language, a query history determines exactly the answers in its feature span. A guarded protocol permits query-proposer revision while guaranteeing completion with the optimal number of teacher calls, and a supplied separating specification gives a finite-family extension. The resulting solver answers every input without its teacher and remains in the baseline computability layer. The central obstruction concerns supplying the completion specification: no baseline-effective procedure can extract a valid span or separating specification uniformly from arbitrary total programs, already in one feature dimension or with two candidate descriptions. Classical relative computation and limiting-revision results locate these claims without imposing a ceiling on practical improvement. Controlled experiments distinguish exact teacher removal from low-risk stopping and measure adaptation benefits and costs against a stronger greedy baseline. The framework makes the information required to acquire, certify, and deploy a capability explicit.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
붉은 여왕 괴델 머신: 에이전트와 평가자의 공진화
The Red Queen Gödel Machine: Co-Evolving Agents and Their Evaluators
자기 개선(self-improving) 에이전트는 에이전트 기반 코딩 벤치마크에서 최고 수준의 성능(SOTA)을 보이고 있지만, 이들의 탐색 방법은 정적 평가 기준을 가정한다. 이는 종이 자신과 함께 변화하는 환경에 적응한다는 진화의 핵심적 특징을 간과하는 것이다. 본 논문에서는 비정적 효용 하에서 재귀적 자기 개선을 수행하는 진화 프레임워크인 붉은 여왕 괴델 머신(Red Queen Gödel Machine, RQGM)을 소개한다. 이를 통해 학습된 평가자가 자신이 안내하는 에이전트와 함께 개선될 수 있다. DeepSWE에서 RQGM은 보완적인 판사 에이전트(agent-as-a-judge) 코드 리뷰 신호를 추가하여 고정 평가자 기준선(baseline) 대비 성능을 개선한다. 즉, 함께 진화한 리뷰어가 코더의 패치를 채점하여 탐색을 안내한다. 낮은 추론 연산량에서 RQGM 코더는 기준선의 75.0% 대비 82.1%의 미보유(held-out) 태스크를 통과하며, 높은 연산량에서는 GPT-6 Astra 모델과 거의 대등한 수준을 보인다. 과학 논문 작성 및 리뷰, 그리고 올림피아드 수준의 증명 작성 및 채점에서도 함께 진화한 평가자가 평가 기준을 제공한다. 인간 IMO 채점을 기준으로 고정했을 때, 함께 진화한 채점자는 자체적인 단계별 루브릭을 작성하고 3배 낮은 탐색 비용으로 정적 기준선을 능가하여 증명 모델이 최고의 평균 점수를 기록하도록 이끈다. RQGM은 에포크에 걸쳐 탐색 목표를 수정할 수 있으므로 탐색을 정규화(regularize)할 수 있다. 예를 들어, RQGM은 AI 작업과 인간 작업 모두에 동등하게 엄격한 리뷰어를 찾아내기 위한 추가적인 적대적 목표를 통해 자기 선호 바이어스를 줄인다. 이렇게 보정된 리뷰어의 안내를 받아, 함께 진화한 작성자는 판사 에이전트 패널 평가에서 기준선보다 1.78배~1.86배 높은 채택률을 달성한다. RQGM은 에이전트와 평가자가 정적 평가를 넘어 재귀적으로 서로를 부트스트랩하는 자기 개선 시스템을 가능하게 한다.
자기 수정 하에서의 라이스 정리: 고양 연산자와 정규형
Rice's Theorem under Self-Modification: Elevation Operators and a Normal Form
우리는 자기 수정(self-modifying) 계산 시스템이 안전성 속성을 다음 단계에서 보존하는지(보존, preservation), 그리고 전체 진화 과정에 걸쳐 보존하는지(지속, persistence)를 알고리즘적으로 인증할 수 있는지를 묻는다. 자기 수정의 한 단계는 프로그램 인덱스에 대한 전체 계산 가능 변환 $\Phi$이며, 보존은 고양된(elevated) 속성 $\Lambda_\Phi(P)=\{x\in P:\Phi(x)\in P\}$로 표현된다. $\Phi$가 외연적(extensional)이면 $\Lambda_\Phi(P)$는 행동적(behavioural) 속성이 되어 라이스 정리가 적용된다. $\Phi$가 코드를 읽는 경우 $\Lambda_\Phi(P)$는 더 이상 행동적이지 않지만, 균일 교란(uniform disruption, $K$를 인코딩하는 비활성 래퍼) 하에서는 라이스 정리를 증명하는 s-m-n 환원이 단일한 행동적 파이버(fibre) 내부에서 작동하며, $\Lambda_\Phi(P)$는 정지 문제의 차수(halting degree)를 물려받는다. 이는 두 가지 스케일에서 나타나는 라이스 정리의 하나의 풀백(pullback)이다. 한 단계의 차수는 $P$의 차수를 넘지 않으며, 지속은 $\Phi$가 외연적인 경우에도 $\Sigma^0_1$ 속성에 대해 $\Pi^0_2$-완전(complete)일 수 있다. 이어서 우리는 재작성(rewriting), 감독(supervision), 시스템 비교에 공통된 메커니즘을 분리해 내는데, 이것이 의미론적 고양 연산자(semantic elevation operator)이다. 이 연산자는 기저 시스템을 감싸고, $K$에 고정된 하나의 유한한 사건, 즉 속성으로의 진입 또는 이탈에 반응한다. 이 부류에서 고양된 속성은 트리거와 극성(polarity)만으로 결정되는 $P\cap S_a$ 또는 $P\setminus S_a$이며, $K$ 또는 그 여집합을 물려받고, 안전 영역은 재귀적으로 열거 가능하지 않다. 라이스-샤피로(Rice-Shapiro) 정리는 극성을 제한한다. 즉 유한 트리거는 $\Sigma^0_1$ 속성에만 진입할 수 있고 $\Pi^0_1$ 속성에서만 이탈할 수 있다. 네 가지 축(기능적, 연역적, 참조 대상에 대한 적합성, 모니터링)은 검증된 사례이며, 감독자의 탑(tower)을 쌓아도 이 장벽은 낮아지지 않는다. 또한 이 부류 밖에 있는 $K$-난해(K-hard) 내포적(intensional) 연산자를 제시하고, 미해결 특성화 문제를 명시한다.
휴리스틱 자기 개선 에이전트에서 자가 작성 검증은 신뢰할 수 없다
Self-Authored Verification Is Unreliable in Heuristic Self-Improving Agents
자기 개선 에이전트는 절차적 정책, 컨트롤러, 또는 휴리스틱 규칙을 반복적으로 재작성함으로써 능력을 축적한다. 이들은 일반적으로 이후 편집을 수용할지 여부를 결정하기 위해 자가 작성 테스트 또는 지표에 의존한다. 에이전트는 최적화 대상과 그 검증자 모두를 통제한다. 그 결과, 실제 배포 성능이 저하되거나 낮은 수준에 머무르는 동안에도 자가 부여 점수는 거의 완벽한 수준을 유지할 수 있다. 우리는 검증자-배포 간극(verifier--deployment gap)을 통해 이 문제를 연구한다. 이 간극은 에이전트의 자가 작성 검증 신호와 에이전트가 관찰하거나 접근할 수 없는 봉인된 배포 평가 간의 불일치를 가리킨다. 우리는 반복적인 정책-및-테스트 재작성 하에서 자가 작성 검증이 어떻게 실패하는지, 능력에 따라 실패가 어떻게 변하는지, 그리고 실제 회귀가 배포되는 것을 방지하기 위해 얼마나 적은 외생적(exogenous) 신뢰가 충분한지 묻는다. 이 문제를 해결하기 위해 우리는 Sealed Exogenous Acceptance Loop(SEAL)을 도입한다. SEAL은 자가 작성 테스트를 유지하지만, 각 후보를 현행(incumbent) 상태와 고정된 하네스 측 감사(audit)를 통해 비교한다. 에이전트는 감사를 작성하거나 검사할 수 없으며, 수락/거부만 받고, 명확한 회귀 이후에는 전체 현행 상태가 보존된다. 우리의 실험은 이 문제가 휴리스틱 학습 설정에서 자주 나타남을 보여준다. 이러한 설정은 목표 목적 함수의 시행착오적 발견을 요구한다. 우리는 또한 자가 작성 검증의 실패가 능력에 따라 계층화(stratified)됨을 발견한다. 더 약한 에이전트는 쉬운 자가 테스트 뒤에 이전에 습득한 전략을 손상시키는 경향이 있다. 더 강한 에이전트는 더 안정적이지만, 여전히 배포 분포를 잘못 측정한다. 표준 자가 작성 제약은 이 간극을 신뢰할 수 있게 메우지 못한다. 대조적으로, SEAL은 여섯 개 모델과 세 개의 무작위 시드에서 보호되지 않은 기준선(baseline)들을 능가한다. 신뢰할 수 있는 자기 개선은 자가 검증을 포기할 필요가 없지만, 에이전트의 통제 밖에 있는 적어도 하나의 배포 수락 신호를 요구한다.
MetaSkill-Evolve: Recursive Self-Improvement of LLM Agents via Two-Timescale Meta-Skill Evolution
최근 LLM 에이전트는 점점 더 장기적이고 개방형 태스크를 처리하며, 에이전트에 제공되는 재사용 가능한 절차적 지식인 외부 스킬이 이 능력을 더욱 확장한다. 그러나 고정된 수작업 스킬은 최적이기 어렵고, 에이전트가 마주하는 다양한 태스크에 적응할 수 없다. 자기 개선 에이전트는 실행 트레이스로부터 자신의 스킬 파일을 재작성함으로써 이 문제를 해결하며, 어려운 벤치마크에서 의미 있는 성능 향상을 달성한다. 그러나 이러한 자기 진화는 비재귀적으로, 태스크 스킬(에이전트가 무엇을 하는가)만 개선할 뿐, 개선 절차(어떻게 개선하는가) 자체는 한 번 작성된 채 고정된다. 우리는 에이전트의 스킬 개선을 재귀적으로 만드는 이중 시간 척도 프레임워크인 MetaSkill-Evolve를 제안한다. 각 브랜치는 태스크 스킬 $s$와, 개선 파이프라인의 Analyzer, Retriever, Allocator, Proposer, Evolver 에이전트를 매개변수화하는 다섯 가지 구성 요소 $m=(ψ,σ,α,π,\varepsilon)$로 이루어진 브랜치 로컬 메타-스킬을 함께 보유한다. 태스크 스킬은 빠른 루프에서 진화하고, 메타-스킬은 동일한 파이프라인이 자기 자신에게 적용되는 느린 루프에서 진화하며, 추가적인 모델이나 목적 함수는 필요하지 않다. 다섯 가지 파이프라인 에이전트가 단일 고정 백본을 공유하는 환경에서, MetaSkill-Evolve는 세 가지 에이전트 벤치마크(OfficeQA, SealQA, ALFWorld)에서 스킬 없음, 정적 스킬, 단일 수준 진화 기준 모델을 능가하며, 원시 백본 대비 보류 테스트 정확도를 각각 +23.54, +16.09, +1.92 포인트 향상시킨다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
20 pages, 3 figures, 1 table. Added diagrams of mutable-state simulation and certified teacher removal; clarified the introduction and discussion of relative computability as a foundation for evolving AI systems. Main results and proofs unchanged. Includes ancillary finite-check code