26년 8월 4주차 그래프 오마카세

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

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

The dominant paradigm for building LLM based agents is the Agent Loop, an iterative cycle where a single language model decides what to do next by reading an ever growing context window. This paradigm has three structural weaknesses: implicit dependencies between steps, unbounded recovery loops, and mutable execution history that complicates debugging. We characterize the Agent Loop as a single ready unit scheduler: at any moment, at most one executable unit is active, and the choice of which unit to activate comes from opaque LLM inference rather than an inspectable policy. This perspective places Agent Loops and graph based execution engines on a single semantic continuum. We propose SGH, Structured Graph Harness, which lifts control flow from implicit context into an explicit static DAG. SGH makes three commitments: execution plans are immutable within a plan version, planning execution and recovery are separated into three layers, and recovery follows a strict escalation protocol. These choices trade some expressiveness for controllability, verifiability, and implementability. Our contributions are fourfold: a scheduler unified framework that applies classical scheduling theory to LLM agent execution and identifies challenges introduced by non deterministic LLM nodes; a trade off analysis of controllability, expressiveness, and implementability across 70 surveyed systems; a formal specification including a node state machine with termination and soundness guarantees; and an attributable experimental framework with a seven group design for future validation. This is a position paper and design proposal. We provide a theoretical framework, design analysis, and experimental protocol, not a production implementation or empirical results.

arXiv.orgHu Wei

• 최근 에이전트 엔지니어링의 관심사는 점점 모델이 얼마나 잘 추론하는가에서 그 추론을 어떤 실행 구조 안에서 움직이게 할 것인가로 넓어지고 있습니다. 긴 작업을 여러 단계에 걸쳐 수행하려면 어떤 상태를 남길지, 다음 작업을 누가 선택할지, 실패한 실행을 어디서 다시 시작할지, 여러 작업을 언제 병렬화할지 같은 문제가 점점 중요해집니다.
• 이런 흐름에서 그래프는 단순히 데이터를 연결하는 표현 방식뿐 아니라, 실행을 조직하는 구조로도 다시 등장하고 있습니다. 핵심은 모든 에이전트를 DAG로 만들자는 것이 아니라, 시스템이 복잡해질수록 실행 상태와 제어 정책을 모델의 즉흥적인 판단에만 맡기기 어려워진다는 데 있습니다. (OpenAI 블로그 참고)
• 이번 주 오마카세에서 소개할 논문은 이 문제를 조금 더 이론적인 관점에서 바라봅니다. ReAct류의 Agent Loop부터 Graph Harness까지를 모두 스케줄러라는 하나의 언어로 다시 보고, 누가 다음 작업을 결정하는지, 동시에 몇 개의 작업이 준비될 수 있는지, 그리고 그 규칙이 얼마나 명시적이고 결정적인지를 비교합니다.
  • 이 논문의 위치가 포지션 페이퍼라는 것을 염두에 두면, 프로덕션 구현이나 실증 결과를 공유하는것이 아닌 이론적 프레임워크와 설계 분석, 실험 프로토콜을 제공하는데 초점이 맞춰져 있습니다.
• 50페이지에 달하는 원문은 처음부터 끝까지 읽기에 다소 무겁게 느껴질 수 있습니다. 이번 오마카세에서는 관련 연구 비교와 반복되는 포지셔닝 문단은 최대한 걷어내고, 이 논문을 읽으며 함께 생각해볼 만한 네 가지 질문을 골라 전달해드리고자 합니다. 정답을 전달하기보다, 네 질문을 따라가며 같이 생각해보고 고민해보면 좋겠습니다.

• 저자는 Agent Loop의 구조적 약점을 크게 세 가지로 짚습니다. 단계 간 의존성이 암묵적이고, 실패 복구에 명시적인 한계가 없으며, 실행 과정에서 계획이 조용히 다시 작성될 수 있다는 점입니다.
• 흥미로운 것은 저자가 이 문제를 단순한 프롬프트나 모델의 문제가 아니라 스케줄링 구조의 문제로 다시 본다는 점입니다.
  • Agent Loop에서는 매 순간 실행 가능한 유닛이 사실상 하나뿐이고, 다음 행동은 LLM의 추론에 맡겨집니다.
  • 반면 그래프 기반 실행에서는 의존성이 허용할 경우 여러 노드가 동시에 준비될 수 있고, ready set과 scheduling policy를 실행 구조에 더 명시적으로 옮길 수 있습니다.
• 논문에서 저자가 제안하는 Structured Graph Harness(SGH)는 이 차이를 밀어붙여 계획을 한 버전 동안 고정하고, 계획,실행,복구를 분리하며, 실패 처리에도 명시적인 경계를 둡니다.
• 여기에서 궁금해진 부분은 다음과 같습니다.
  • Agent loop를 스케줄러로 본다는 것이 정확히 무슨 뜻인지?
  • 그래프로 옮겼을 때 실제로 무엇이 달라지고, 무엇을 포기해야 하는지?
  • 우리가 얻을 수 있는 이점은 무엇인지?

왜 Agent Loop를 스케줄러라고 보는가?

• 논문이 정의하는 Agent Loop에서는 한 시점에 다음으로 실행할 유닛을 하나씩 선택합니다. 그리고 무엇을 실행할지는 외부의 명시적인 scheduling rule보다 LLM의 내부 추론에 크게 의존합니다.
• 이 틀 위에서 graph-based executor은 의존성이 허용할 때 여러 유닛이 동시에 준비될 수 있는 multi-ready-unit scheduler로 자리매김합니다. 즉 Loop와 Graph를 다른 종류의 시스템으로 구분짓기보다, ready-set (U) 크기와 policy의 명시성 및 결정성이라는 같은 시스템 좌표에 둡니다.
• 여기서 흥미로운 구분이 하나 나옵니다. 병렬 tool call처럼 한 턴에 여러 도구를 동시에 부르는 경우도 |U|>1인 실행이 가능하지만, 무엇을 병렬로 할지 그때그때 LLM이 결정하는 것과, DAG 토폴로지가 구조적으로 준비 집합을 계산하는 것은 다른 문제로 바라봅니다.

• Planner Loop라고 부르는 루프 앞단에 플래너를 붙인 구조에서도 마찬가지입니다. 아무리 정교한 플래너가 계획을 짜도 실행기가 여전히 한 번에 하나씩만 처리한다면 |U| = 1이라는 실행 특성은 바뀌지 않습니다. 따라서 병렬 호출 자체보다 중요한 것은 ready set과 scheduling policy가 어떻게 정해지는가입니다.
• Figure 2에서처럼 왼쪽에서 오른쪽으로 갈수록 정책이 명시적인 구조에 의해 제약되고, Graph Harness에서는 실행 가능한 노드가 DAG의 의존성과 명시적 scheduling policy에 의해 결정됩니다. 다만 이 연속체는 증명된 정리가 아닌 저자가 제안한 분류 프레임워크입니다.

Graph Harness는 일부러 무엇을 제한하는가?

• Structured Graph Harness(SGH)는 에이전트의 작업 계획을 명시적인 DAG로 표현하고, 그 의존성에 따라 실행 가능한 노드를 스케줄링하며, 실패 복구까지 경계 지어진 규칙으로 관리하는 실행 구조입니다.

• SGH를 이해하는 데 세부 formalism보다 중요한 건 trade입니다. trade 의미는 표현력의 일부를 포기하는 대신 그 대가로 예측 가능성을 얻는다는 것입니다. SGH는 이 trade를 몇 가지 구체적인 설계 선택으로 구현합니다.
  • 계획을 실행 중 몰래 바꾸지 않는다 : plan 버전이 살아있는 동안 DAG는 불변이고, 구조를 바꾸려면 replan으로 새 버전을 만들어야 합니다.
  • 계획,실행,복구를 분리한다 : 런타임은 실패의 왜? 까지 판단하지 않고 별도 계층에 넘깁니다.
  • 실패 복구에 끝을 둔다 : retry → patch → replan 순서를 반드시 지키는 에스컬레이션이며, 건너뛸 수 없습니다.
  • 부작용 수준에 따라 다르게 스케줄한다 : 되돌리기 어려운 작업은 투기적 병렬 실행 대상에서 제외됩니다.
• 같은 원칙은 여러 작업이 다시 합쳐지는 방식(join)에도 적용됩니다. SGH는 모든 선행 작업이 성공한 뒤 진행하는 all_of와, 여러 후보 중 하나만 성공해도 다음 단계로 넘어가는 any_of를 지원합니다. 반면 여러 작업을 동시에 시작한 뒤 첫 번째 결과가 나오면 나머지를 중간에 취소하는 first_of 방식은 제외합니다. 이미 실행 중이던 작업을 취소하면 부분적으로 발생한 변경을 어떻게 되돌릴지까지 관리해야 하기 때문입니다.
• 결국 SGH는 더 많은 것을 표현하기보다, 실행을 더 명확하게 통제할 수 있는 쪽을 택합니다. 하나의 plan version이 시작되면 그 안에서는 그래프 구조를 고정하는 것도 같은 이유입니다.

실제로 뭐가 달라지나? ㅡ 버그 수정 예시

• search_auth, utils 모듈을 각각 검색하고 읽은 뒤, 결과를 분석해 두 가지 패치 후보를 시도하고 테스트·문서 갱신을 거쳐 최종 리포트를 만드는 태스크를 예로 듭니다.
• Agent Loop에서는 이 과정을 사실상 순차적으로 진행하지만, Graph Harness에서는 서로 의존하지 않는 작업들을 같은 ready set에 올려 병렬로 실행할 수 있습니다.

• Figure 1은 병렬 실행뿐 아니라 언제 다음 단계로 넘어갈 수 있는지의 조건까지 그래프에 표현되는 모습을 보여줍니다. 이 DAG를 이상적인 조건에서 실행하면 6개의 스케줄링 라운드로 진행할 수 있으며, 논문은 같은 태스크를 Agent Loop로 수행하는 비교 예시를 11턴으로 제시합니다.
• 하지만 중요한 차이는 단순히 단순히 11턴이 6라운드로 줄어드는 데 있지 않습니다. 어떤 작업을 동시에 실행할 수 있는지, 어떤 대안 중 하나만 성공하면 충분한지, 어떤 작업들이 모두 끝나야 다음 단계로 갈 수 있는지가 실행 구조에 명시된다는 점이 핵심입니다.

그래서 정말 더 좋은가 — 아직은 모른다

• 70개 오픈소스 프로젝트 조사에서 Agent Loop 패턴이 약 60%로 가장 흔했다는 것이 이 논문이 제시하는 실질적 근거에 가깝습니다. 다만 표본 선정과 분류가 주관적이고, 본문의 42/70과 부록의 41개 목록처럼 집계가 완전히 일치하지 않는 부분도 있습니다. 저자도 이 조사를 정량적 증명이라기보다 qualitative evidence임을 언급합니다.

• 오히려 흥미로운 부분은 수행하지 않은 실험의 설계방식입니다. 설계의 핵심은 인접한 두 그룹의 차이를 비교하는 데 있습니다.
  • 저자는 G0부터 G6까지 일곱 그룹을 두고, G1을 기준으로 planner, structured scaffold, graph scheduler, local patch, replan을 단계적으로 추가합니다. 핵심은 인접한 두 그룹의 차이를 비교해 각 요소의 효과를 따로 떼어보는 것입니다.
• 예를 들어 Structured Loop(G3)와 Graph Harness Core(G4)를 비교하면, 앞서 추가된 planner나 scaffold의 효과와 구분해 graph scheduling 자체가 성능에 어떤 변화를 만드는지 살펴볼 수 있습니다. 즉 전체 시스템이 좋아졌는가만 보는 것이 아니라, 어떤 설계 요소가 성능 변화에 얼마나 기여했는지를 attribution하려는 설계입니다.
• 하지만 SGH가 모든 태스크에서 유리하다고 가정하지는 않습니다. 오히려 태스크 복잡도에 따라 이점이 달라질 것이라고 봅니다.

• 1–3단계의 단순 태스크에서는 구조적 오버헤드 때문에 SGH가 오히려 손해일 수 있고, branching과 recovery가 늘어나는 중·복잡 태스크에서 그래프 구조의 이점이 커질 것으로 예상합니다. 하지만 이 역시 아직 검증되지 않은 가설입니다.
• 즉 이 논문은 Graph Harness가 좋을 것이다라고만 주장하기보다, 그 주장을 나중에 반증 가능한 형태로 쪼개 놓은 셈입니다. 위 Table들은 앞으로 무엇을 검증해야 하는지를 정리한 설계표에 가깝습니다.

• 핵심 네 가지 질문을 엔지니어링 관점에서 다시 바라보면, 결국 핵심은 실행 과정의 의존성과 선택 조건을 시스템이 얼마나 명시적으로 표현하고 추적할 수 있느냐에 있습니다. Agent Loop를 ready set과 scheduling policy의 언어로 다시 바라본 것도 Loop와 Graph를 서로 다른 기술로 구분하기보다, 같은 실행 문제에 대한 서로 다른 설계점으로 비교하기 위해서입니다.
• SGH가 일부 표현력을 의도적으로 포기하는 이유도 여기에서 이어집니다. 그래프는 가능한 행동을 더 많이 표현하기 위한 장치라기보다, 어떤 작업이 준비되었고, 무엇을 기다려야 하며, 실패했을 때 어디까지 복구할지를 구조 안에 드러내기 위한 장치로 사용됩니다. 앞서 살펴본 버그 수정 예제는 이런 차이를 가장 직관적으로 보여줍니다.
• 그렇다고 그래프가 언제나 더 좋은 선택이라는 결론이 나오는 것은 아닙니다. 플래너가 좋은 의존 구조를 만들지 못하거나 태스크가 충분히 단순하다면 병렬성의 이점은 줄어들고, 오히려 그래프를 관리하는 비용이 더 커질 수도 있습니다. 논문이 제안한 여러 gain과 태스크 복잡도별 가설 역시 아직 실제 실험으로 검증되지는 않았습니다.
• 결국 이 논문의 포지션은 루프와 그래프의 차이를 어떤 질문으로 나누고, 그것을 어떻게 검증할 것인가에 대한 틀을 제공하는 것에 가깝습니다. 완성된 해답을 제시하기보다는, 앞으로 우리가 어떤 기준으로 비교하고 어떤 실험으로 답을 찾아갈지 그 방향성을 잘 구조화한 논문이라고 볼 수 있습니다.

• 이번 오마카세 내용을 참고하시면서 원문을 읽어보실 때 Section 3.2–3.5 → Section 4 → Section 9.5·9.8 → Conclusion 순서로 읽어보심을 추천드립니다. 여기에 설계 및 구현 관점까지 더 깊게 보고 싶으시다면 여기에 Section 5–7, Section 8을 더해 읽으시면 좋을 것 같습니다.

[Contact Info]

Gmail: jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn