Closed-Loop Graph Algorithm Execution with Small Language Models: Step Accuracy and Rollout Reliability
원문 초록
Small language models offer an efficient alternative to large-scale systems, but their ability to execute structured algorithms over multiple dependent decisions remains poorly understood. We study graph algorithm execution as a closed-loop prediction problem in which a model repeatedly selects the next action from the current graph and algorithmic state. Our evaluation framework covers several classical graph procedures, multiple synthetic graph families, and disjoint training, validation, and test partitions. It assesses both local decision quality and global execution behaviour using step accuracy, exact rollout accuracy, constraint validity, partial solution quality, prefix survival, and intervention-based diagnostics. The results show that adaptation can produce reliable policies for structural procedures such as traversal and coloring, while weighted algorithms remain substantially more sensitive to error accumulation. More broadly, the findings demonstrate that strong next-step prediction does not necessarily translate into reliable autonomous execution and motivate evaluating algorithmic language models through complete closed-loop rollouts rather than isolated decisions.
요약
소규모 언어 모델(SLM)을 BFS, DFS, 그래프 색칠, Dijkstra 등 고전 그래프 알고리즘의 클로즈드-루프(closed-loop) 실행 정책으로 평가한 연구로, Llama-3.2-1B와 Qwen2.5-1.5B에 LoRA 어댑테이션을 적용하여 순회(traversal)·색칠 알고리즘에서는 높은 롤아웃 정확도를 달성했으나, 가중치 기반 알고리즘(Prim, Borůvka, Dijkstra)에서는 스텝 정확도가 높더라도 오차 누적으로 인해 전체 실행 신뢰도가 크게 저하됨을 실증적으로 보여준다. 이 결과는 개별 스텝 예측 성능이 자율적 알고리즘 실행 신뢰성을 보장하지 않으므로, 알고리즘 언어 모델의 평가는 단일 스텝이 아닌 완전한 클로즈드-루프 롤아웃을 기준으로 수행해야 함을 시사한다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.24980v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
StoreBench: 자율 운영자 에이전트의 평가 및 학습을 위한 라이브 커머스 환경
StoreBench: A Live-Commerce Environment for Evaluating and Training Autonomous Operator Agents
강화학습(RL) 환경은 이제 사후 학습(post-training)에서 대규모 언어 모델(LLM)의 역량을 향상시키는 주요 수단이 되었으나, 대부분의 에이전트 벤치마크는 여전히 정적입니다. 즉, 에이전트가 행동할 때만 환경이 변화하고, 보상은 최종적인 판정으로 주어지며, 통과 기준은 자의적으로 설정됩니다. 본 논문에서는 에이전트가 프로덕션 수준의 상거래 백엔드에서 중간 규모의 온라인 의류 매장을 운영하며 불확실성 속에서 장기 계획 수립 및 경제적 판단력을 시험받는 라이브 커머스 환경인 StoreBench를 소개합니다. 고객은 24시간 내내 주문하고, 공급업체는 가격을 재책정하거나 공급에 실패하며, 시장 충격은 부분적인 예고만 있거나 예고 없이 발생합니다. 에이전트는 실제 인간 운영자가 사용하는 것과 동일한 29개의 판매자 도구를 통해 행동하며, 취해진 행동의 함수로 시뮬레이션 시간을 계산하는 윈도우 기반 운영 예산 하에서 작동하므로 모델 지연 시간이 시뮬레이션 시간에 영향을 미칠 수 없습니다. 통과 임계값은 스크립트 기반 앵커 정책을 기준으로 보정되었고, 보상은 다양한 보상 해킹 목록에 대비해 강화되었으며, 일련의 행동이 주어지면 모든 에피소드가 동일하게 재현됩니다. 본 연구에서는 추론 노력을 일치시킨 상태에서 세 가지 월드 시드에 걸쳐 30~45일 및 시뮬레이션된 1년 전체에 해당하는 11개 시나리오를 바탕으로 7개의 프론티어 LLM을 평가합니다. 평균적으로 스크립트 기반 스마트 트리아지(smart-triage) 정책에 필적하는 모델은 없었습니다. 최고 성능을 보인 DeepSeek-V4-Pro는 휴리스틱의 97% 대비 49%의 태스크-시드 셀을 통과했습니다. 동일한 도구와 예산을 사용하여 작업한 인간 전문가는 모든 모델보다 높은 점수를 기록했습니다(평균 종합 점수 0.708 대 0.700). Claude Code 하네스 기반의 시뮬레이션된 1년 전체에 걸쳐 대다수 모델은 극적인 성능 향상을 보입니다. GRPO 사후 학습 실행에서 서로 다른 5개의 태스크로만 학습된 Qwen3.5-27B는 홀드아웃(held-out) 평가 태스크에서의 평균 종합 점수를 0.136에서 0.373으로 향상시켰습니다. 본 연구에서는 학습 분할용 예시 태스크 5개, 샘플 궤적 10개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.
핸드오프 곡선: 멀티턴 LLM 라우팅에서의 초기 선택, 사후 핸드오프 및 지도 타깃
Handoff Curves: Initial Selection, Later Handoff, and Supervision Targets in Multi-turn LLM Routing
본 연구에서는 여러 턴(turn)에 걸친 대규모 언어 모델(LLM) 태스크에서 초기 모델(model) 선택, 사후 핸드오프(handoff), 그리고 학습(training) 타깃이 성공률과 비용에 미치는 영향을 연구합니다. 핸드오프 단계 변화에 따른 태스크 성공률과 비용을 기록하는 핸드오프 곡선을 활용하여 여러 라우터 아키텍처를 비교합니다. 연구진이 구축한 데이터셋(dataset)은 BFCL, MultiWOZ, $τ$-retail 전반에 걸친 3개 Qwen 모델의 34,204건의 완전한 실행 기록을 포함하며, 라우팅 결정을 위한 오프라인 지도 정보를 제공합니다. 주요 비교 분석에서 Qwen3.5 35B-A3B를 시작 모델로 사용했을 때, 사후 핸드오프를 허용하는 것은 BFCL 또는 MultiWOZ에서 초기 선택 대비 효용 개선을 보이지 못했으며 다양한 비용 가중치 범위에 걸쳐 BFCL에서 비용을 증가시켰습니다. 지도 타깃을 변경하면 자체 데이터셋과 TwinRouterBench 모두에서 라우터 성능이 향상됩니다. 자체 데이터셋의 경우 노이즈가 있는 학습 성공 곡선을 단조 적합(monotone fit)으로 대체함으로써 보고된 작동 지점 전반에 걸쳐 동일한 비용에서 성공률이 0.2~4.1%포인트 향상되었습니다. TwinRouterBench에서는 남은 작업 및 앞으로 닥칠 어려운 단계에 필요한 모델 성능을 기술하는 타깃을 구성했습니다. 벤치마크의 단계별 라벨로 학습하는 것과 비교하여, 이러한 타깃은 전체 정적 뱅크에서 궤적 통과 점수를 7.8%포인트, 비용 절감 효과를 6.3%포인트 높였습니다. 이 타깃으로 학습된 라우터의 실제 배포에서는 인스턴스당 0.59달러의 라우터 비용으로 100개 인스턴스 중 79개를 해결했습니다.
Humanize MLE 에이전트: 단일 에이전트 한계를 넘어서는 다중 에이전트 세션 교대
Humanize MLE Agents: Multi-Agent Session Alternation Beyond Single-Agent Limits
장기 시계(long-horizon) 머신러닝 엔지니어링(MLE)을 위한 기존 LLM 기반 에이전트 접근법들은 흔히 컨텍스트 엔지니어링을 사용하며, 이는 도구, 스킬, 축적된 경험을 관리하는 커스텀 하니스(harness)를 통해 구현된다. 그러나 우리는 단일 세션 실행이 길어질수록 에이전트의 추론 강도가 저하되며 진행 속도가 느려진다는 것을 발견했으며, 이를 장기 시계 둔화(long-horizon deceleration)라고 요약한다. 또한 기반 모델이 개선됨에 따라 이러한 커스텀 하니스의 이점이 사라진다는 것을 발견했으며, 이를 하니스 노후화(harness staleness)라고 요약한다. 이러한 발견은 이러한 이점이 버전 간에 지속되지 않을 수 있음을 시사하며, 이는 에이전트들이 세션에 걸쳐 서로의 작업을 기반으로 발전시키는 워크플로우 수준의 접근법을 동기화한다. 우리는 이러한 교대하는 에이전트 세션을 컨텍스트 재설정 준-마르코프 결정 과정(context-reset semi-Markov decision process, CR-SMDP)으로 모델링하고, 교대가 단일 에이전트 기준선 한계를 초과하기 위한 충분 조건을 수립하며, 명시적인 실험 예산 경계를 도출하고, 세션 상한이 이러한 이점을 보존하는 시점을 규명한다. 이러한 분석에 따라, 우리는 Humanize MLE 에이전트(HMA)를 소개한다. HMA는 공유 작업공간에서 두 에이전트를 교대시키며, 각 세션을 최대 k개의 실험으로 제한하고 세션 간 컨텍스트를 재설정하며, 추가적인 태스크별 하니스나 사전 지식 보강 없이 동작한다. MLE-bench의 75개 캐글(Kaggle) 과제에서 HMA는 78.2%의 최신(state-of-the-art) any-medal 비율을 달성하며, 가장 강력한 오픈소스 기준선을 8.0포인트 상회하면서도 그 시간 예산의 4분의 1만을 사용한다. 또한 다섯 개의 이질적인 에이전트 쌍에 걸친 여섯 가지 구성 중에서, HMA는 구성 요소 기준선들에 비해 any-medal 비율을 평균 6.4포인트 향상시켜, 에이전트 쌍 간 일반성을 입증한다. 커널(kernel) 최적화에 대한 보충 사례에서는 878 사이클에 도달하여 커뮤니티 리더보드 선두와 1.6% 이내의 차이를 보이며, MLE를 넘어선 적용 가능성을 입증한다.
MAGMA-Bench: 동적 태스크 및 실행 실패 환경에서의 장기 임바디드 에이전트 평가
MAGMA-Bench: Evaluating Long-Horizon Embodied Agents under Dynamic Tasks and Execution Failures
장기(long-horizon) 임바디드 에이전트(embodied agent)는 실행이 진행됨에 따라 태스크 관련 정보를 유지하고, 이종 로봇들을 조율하며, 의사결정을 적응적으로 변경할 수 있어야 합니다. 기존 벤치마크는 동적 태스크 실행 및 임바디드 멀티 에이전트 조율을 조사하지만, 둘의 교차점에 대한 평가는 제한적입니다. 본 연구에서는 동적 멀티 로봇 환경에서의 지속적 태스크 추론을 위한 아키텍처 비종속적 벤치마크인 MAGMA-Bench를 소개합니다. MAGMA-Bench는 이종 역량을 가진 로봇 간의 조율이 필요한 시나리오와 함께, 실행 실패, 태스크 중단, 미션 업데이트를 포함한 통제된 온라인 섭동(online perturbation) 및 늘어나는 태스크 범위에 걸쳐 에이전트를 평가합니다. 본 벤치마크는 구조화된 스킬 수준 인터페이스를 활용하여 태스크 수준 추론을 인지 및 저수준 제어로부터 분리합니다. 저자들은 로컬 배포가 가능한 오픈 가중치 플래너, 멀티 에이전트 상태 추적 전략, 그리고 프론티어 모델들을 평가합니다. 평가된 가장 강력한 모델조차도 섭동이 없는 에피소드의 상당 부분에서 실패하며, 온라인 섭동 하에서는 성공률이 더욱 감소합니다. 지도 적응(supervised adaptation)은 소형 모델의 성능을 크게 향상시키지만, 더 길고 다중 로봇이 관여하는 미션에서는 성능이 여전히 크게 낮게 유지됩니다. 저자들은 벤치마크, 261,646개의 태스크 수준 학습 예제, 그리고 아키텍처 비종속적 전문가 궤적 생성 파이프라인을 공개합니다.
Kepler: ARC-AGI-3를 위한 감사 가능한 월드 모델
Kepler: Auditable World Models for ARC-AGI-3
ARC-AGI-3는 관찰을 통해 규칙과 목표를 추론해야 하는 상호작용 환경(environment)에서 에이전트(agent)를 평가합니다. 본 논문에서는 가설을 실행 가능한 월드 모델(world model)로 표현하고, 소급적 전이 검증과 조건부 예측 검증을 통해 이를 검증하는 오픈소스 하네스인 Kepler를 제시합니다. 단일 고정 Claude Opus 5 설정 하에서, Kepler는 게임별 모델(model) 선택이나 점수 조건부 재실행 없이 25개 공개 게임 전체에서 서버 검증 100.00 RHAE를 달성했습니다. 완료된 183개 레벨 중 181개에서 최종 Opus 시도는 해당 인간 중앙값 기준선(baseline)보다 더 많은 행동을 사용하지 않았습니다. 보존된 보드 실행에는 8,256회의 환경 행동이 사용되었으며, 이 중 7,292회는 점수가 매겨지는 레벨에서 발생했습니다. 보존된 로컬 제공자 세션 기록 기준으로 8억 5,800만 토큰(token), 97.37%의 캐시 읽기, 2026년 9월 1일 API 정가 기준 777.72달러의 비용이 소요되었습니다. 또한 세 가지 평가 실패 사례를 보고합니다: 유효하지 않은 완벽한 실행을 초래한 소스 코드 유출, 대조 조건에서 에이전트가 제거된 하네스를 재구축한 사례, 그리고 자율 복구가 고장 난 플래너를 은폐한 사례입니다. 단일 게임 관찰 사례 연구에 따르면, 애니메이션 프레임에는 안정화된 텍스트 그리드에는 없는 작업 관련 정보가 포함되어 있었습니다. 최종 Claude Opus 5 및 GPT-5.6 Sol 보드 전체에서 50개 게임-모델 셀 중 48개가 100에 도달했습니다. 이러한 결과는 공개 세트 점수만으로는 변별력이 제한적임을 나타내며, 첫 시도, 비용 조건부 및 검증 인식 보고의 필요성을 시사합니다.
LLM 에이전트 환경에서의 행동 결제 감사: 순서, 진행도 및 리플레이
Auditing Action Settlement in LLM Agent Environments: Order, Progress, and Replay
대규모 언어 모델(LLM) 에이전트 환경에서 동시 발생하는 행동은 각 제안이 개별적으로 유효하더라도 중재가 필요합니다. 본 연구에서는 타입화된 스냅샷 결제(snapshot-settlement) 계약을 구현하고 세 가지 고유한 특성인 순서 민감도, 유용한 진행도, 리플레이 일관성을 감사(audit)합니다. 28,800회의 완전 순열 실험과 2,160회의 스크립트 기반 다단계 에피소드에서 5가지 결제 정책을 테스트합니다. 결합 정책은 고정된 우선순위를 조건으로 할 때 공간적으로 순서 불변성을 보이지만, 보수적 거부 정책은 6개 에이전트 출입구 태스크에서 31.25%의 에이전트만 완료한 반면 무작위 티켓 정책은 90.28%를 완료하여 대응 개선 폭은 59.03%포인트(95% 부트스트랩 구간: 50.00-68.06)에 달했습니다. 모든 정책은 테스트된 공간적 제약을 보존하지만, 우선순위 중재는 여전히 독립적인 소규모 인스턴스 최적해를 놓칩니다. 별도의 전체 상태 저널 감사는 보존된 최종 앵커를 바탕으로 156개의 체크포인트를 정확히 리플레이하고 인위적으로 생성된 1,332개의 손상을 거부합니다. 본 연구의 실증적 증거는 인간적 사실성이나 장기적 공정성이 아닌 실행 의미론(execution semantics)에 관한 것입니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.