From Agent Loops to Structured Graphs: A Scheduler-Theoretic Framework for LLM Agent Execution

한눈에 보기

에이전트가 파일을 찾고, 읽고, 고치고, 시험하고, 보고하는 일을 한다고 하자. 보통의 agent loop에서는 모델이 길어진 대화를 읽고 다음 행동 하나를 고른다. Wei의 SGH(Structured Graph Harness)는 이 반복을 지금 실행 가능한 일들의 집합을 관리하는 스케줄러로 해석한다. 그 뒤 의존관계를 정적 DAG로, 실패 처리를 정해진 단계로, 실행 이력을 버전이 붙은 계획으로 밖에 꺼내자는 설계다.

중요한 분류가 있다. 이 논문은 성능 좋은 실행기를 구현해 비교한 연구가 아니다. 저자는 이를 position paper와 design proposal이라고 명시하며, 프로덕션 구현과 실증 결과는 제공하지 않는다고 쓴다. 여기서는 어떤 실행 계약을 코드로 강제할지 생각하는 언어를 얻을 수 있다. “그래프가 loop보다 빠르다”는 결론은 나오지 않는다.

질문	논문의 답	읽을 때의 범위
loop의 문제는?	의존성, 회복, 계획 이력이 문맥 안에 묻힌다	모든 loop가 반드시 실패한다는 뜻은 아니다
SGH의 수단은?	정적 DAG, 계획 버전, 상태기계, 세 단계 회복	제안 명세이며 구현 성능은 미측정
보장하는 것은?	유한 DAG와 유한 시간 제한 등 조건 아래 종료	계획 생성·의미 검증의 정답성은 보장하지 않는다

loop와 그래프를 같은 말로 보기

여기서 **준비 집합(ready set)**은 선행 작업이 끝나 지금 보낼 수 있는 노드들의 목록이다. 스케줄링 정책은 그 목록에서 무엇을 언제 보낼지 정하는 규칙이다. 논문은 순차 loop를 준비된 작업이 한 번에 하나인, 그리고 다음 선택이 LLM 추론에 의존하는 스케줄러로 묘사한다. 반대로 그래프 실행기는 독립 노드가 둘 이상 준비되면 동시에 보낼 수 있고, 그 순서와 조건을 그래프에 기록한다.

그림 1. Wei (2026), arXiv:2604.11378v1, Figure 2, 물리 PDF p. 14의 원도판. Naive/Parallel/Planner/Structured loop와 Graph Harness를 정책의 명시성·결정성 축으로 놓는다. 그림에서 볼 점은 그래프가 “더 많은 병렬성”만 뜻하지 않고, 선택 규칙을 대화 밖 구조로 옮긴다는 점이다. 한계는 Parallel Loop와 Graph Harness가 모두 준비 집합을 1 이상으로 표기해, 그림만으로는 병렬성 자체의 효과와 명시적 정책의 효과를 분리할 수 없다는 점이다. CC BY가 아닌 arXiv 영구 비독점 라이선스 원도판 인용.

예를 들어 search_auth와 search_utils는 함께 실행하고, 두 결과를 읽은 뒤에만 analyze를 연다. 분석 뒤 fix_A, fix_B, update_docs가 가능해진다면 그 의존성은 프롬프트의 기억이 아니라 그래프의 간선이 된다. 의존성을 그래프의 간선으로 기록할 때 SGH가 말하는 통제 가능성이 생긴다. 단, 논문도 이상적 예시에 계획기가 모든 병렬성과 의존성을 정확히 알아야 한다는 전제를 단다.

그림 2. Wei (2026), Figure 1, p. 4의 원도판. 두 검색과 두 읽기, 두 수정 후보와 문서 갱신을 파동별로 배치한 버그 수정 DAG다. any_of는 한 수정이 성공하면 다른 수정 경로를 건너뛴다는 예시다. 이 그림은 측정된 처리 시간 그래프가 아니라, 올바른 DAG와 노드 실행을 가정한 설명용 트레이스다.

SGH가 고정하려는 네 가지 계약

첫째, 계획 버전 불변성이다. 실행 중 구조를 바꾸려면 기존 계획을 몰래 고치는 대신 새 버전을 요청한다. 둘째, planner·runtime·recovery를 세 층으로 분리한다. 셋째, 노드는 pending, ready, running, executed, failed 같은 명시적 상태를 지나게 한다. 넷째, 회복은 local_retry → local_patch → request_replan 순서로만 올린다. 각 단계의 실패 원인과 재시도 예산을 기록하면, “왜 다시 계획했는가”를 나중에 추적할 수 있다.

그림 3. Wei (2026), arXiv:2604.11378v1, Figure 4, 물리 PDF p. 24의 원도판. 의존성 충족, dispatch, 성공·재시도·사람 검토·timeout이 상태 전이를 어떻게 제한하는지 보여 준다. terminal 상태에는 되돌아가는 간선이 없다는 것이 종료 논증의 발판이다. 상태표가 모든 실제 도구 오류를 분류하거나 의미적 오류를 판정해 주지는 않는다.

형식 보장은 어디까지인가

Theorem 6.2는 하나의 유한하고 순환 없는 유효 DAG 계획 버전에, 노드별 유한 timeout과 retry budget, 사람 대기에도 유한 timeout이 주어졌을 때 그 주 실행 loop가 끝난다고 주장한다. 이는 무한 재시도 방지에 유용한 실행 제어의 조건부 보장이다. request_replan이 새 계획 버전을 임의로 계속 만드는 경우까지 전역적으로 끝난다는 정리는 아니다. 계획기가 빠뜨린 의존성을 알아내거나, LLM이 만든 코드가 실제로 옳다는 보장도 아니다. 논문은 이를 별도로 validation gap이라고 부른다. 출력 형식 검사는 코드로 강하게 할 수 있지만, “이 수정이 요구사항을 만족한다” 같은 의미 검증은 검증기 품질에 달린다.

또 한 가지 주의점이 있다. 논문은 agent loop의 준비 집합을 1로 특징짓지만, 병렬 tool call·비동기 실행은 스스로 다중 준비 단위 경계 사례라고 인정한다. SGH는 의존성·정책·회복을 명시해 감사를 가능하게 한다. 그래프라는 도형만으로 차이가 생기지는 않는다.

적용 판단과 결론

작업 순서가 미리 비교적 잘 보이고, side effect가 큰 도구 호출을 검증·감사해야 하며, 실패가 같은 자리에서 반복되는 일을 막고 싶을 때 SGH의 설계 언어가 유용하다. 탐색하면서 목표와 하위 작업 자체가 계속 바뀌는 일에는 정적 DAG의 고정 비용이 더 클 수 있다. 실제 채택 전에는 7군 실험 프로토콜을 그대로 성능 증거로 쓰지 말고, 같은 모델·도구·예산에서 loop와 그래프를 비교하는 자체 측정이 필요하다.

References

Wei, H. (2026). From agent loops to structured graphs: A scheduler-theoretic framework for LLM agent execution (arXiv:2604.11378v1). arXiv. https://arxiv.org/abs/2604.11378

상세 검토: /blog/from-agent-loops-to-structured-graphs-scheduler-theoretic-framework?view=deep