Procedural Graphs: Self-Evolving Execution Structures for LLM Agents

Paper: Yuxing Lu; Yicheng Chen; Shanchan Wu; Sercan Ö. Arık (2026). "Procedural Graphs: Self-Evolving Execution Structures for LLM Agents". arXiv:2609.09153v1 / PDF

긴 도구 사용 과제에서 에이전트는 방금 한 일을 읽고도 다음 순서를 잃기 쉽다. 검색 뒤에는 근거를 읽어야 하고, 답을 낸 뒤에는 확인해야 하는데, 긴 기록 속에서 이런 절차가 자유 텍스트로 흩어진다. Procedural Graph(PG)는 이를 외부 그래프로 꺼내 “지금 이 상태에서는 무엇이 다음에 가능한가”를 안내한다. 답을 강제하는 규칙 엔진이 아니라, 현재 위치에 맞는 조언을 생성 모델의 prompt에 더하는 방식이다.

1. 지식 그래프와 절차 그래프의 차이

지식 그래프의 (개체, 관계, 개체)는 “모나리자는 어디에 있나?” 같은 사실 질문에 답한다. PG의 (절차, 관계, 절차)는 “이 과제에서 다음에는 무엇을 해야 하나?”를 다룬다. 노드는 검색·검증·도구 호출·상태처럼 추상화한 행동이고, 간선은 가능한 전이와 함께 조건, guidance, 피해야 할 실수를 기록한다.

가령 ‘검색 → 근거 읽기 → 답 검증 → 제출’이라는 연결이 있다면, 제출만 검색해 prompt에 넣는 것보다 그 앞의 검증 단계를 같이 볼 수 있다. 단순한 메모리 검색과는 다르다. 그래프가 순서와 이웃 관계를 보존하므로, 특정 행동의 문장 설명만 찾는 대신 그 행동이 성립하는 맥락을 보여 준다.

그림 1. Lu et al. (2026), Figure 1, PDF p. 2의 원도판이다. 왼쪽은 사실 관계, 오른쪽은 검색·읽기·추출·검증·출력이라는 다음 행동의 연결을 보인다. 실제 실험의 행동과 관계 어휘가 이 예시 그림과 같다는 뜻은 아니며, 그림은 표현 방식의 차이를 설명한다.

2. 실행 중에는 그래프를 고정하고, 주변만 읽는다

온라인 실행에서 PG는 세 단계로 쓰인다. 먼저 최근 행동을 노드에 맞춰 현재 위치를 찾는다. 다음으로 그 노드의 최대 2-hop 주변 그래프를 꺼낸다. 마지막으로 별도 guidance LLM이 질문, 최근 궤적, 주변 그래프를 읽고 “다음에 확인할 것”을 자연어 지침으로 바꾼다. solver는 그 지침을 받은 뒤에도 스스로 다음 행동을 생성한다.

따라서 PG는 action space를 엄격히 막는 state machine이 아니다. 일치하는 노드를 찾지 못하면 논문 구현은 전체 그래프로 fallback한다. 이 유연성은 낯선 실행을 계속할 여지를 주지만, 잘못된 안내를 완전히 막는 장치는 아니라는 뜻이기도 하다. 논문은 현재 행동을 그래프의 추상 노드에 안정적으로 맞출 수 있어야 한다고 본다.

그림 2. Lu et al. (2026), Figure 2, PDF p. 4의 원도판이다. 가운데는 고정된 그래프로 위치를 찾고 이웃을 읽어 guidance를 만드는 온라인 단계, 오른쪽은 궤적으로 후보 수정을 만드는 오프라인 단계를 나타낸다. validation이 같거나 좋아진 후보만 채택하지만, 이는 그 검증 분할의 비감소 규칙이지 모든 미래 과제의 단조 향상을 보장하지 않는다.

3. 그래프는 실패 기록만 보고 바로 바뀌지 않는다

자기 진화는 실행 도중이 아니라 배치 실행 뒤에 이루어진다. refiner LLM은 성공 궤적과 실패 궤적을 비교해 노드·간선을 추가하거나 삭제하고 간선의 조건·안내·pitfall을 바꾼다. 구조 검사를 통과한 후보는 독립 validation set에서 평가한다. 기존 그래프보다 점수가 같거나 높아야 유지되며, 기각 후보도 다음 제안에서 반복하지 않도록 기록한다.

이 검증 문턱은 그럴듯한 설명을 곧바로 절차 지식으로 굳히지 않으려는 장치다. 그러나 training과 validation 모두 작거나 비슷한 시나리오라면 특정 분할에 맞는 수정을 고를 가능성은 남는다. 논문도 그래프의 최종 성능을 선택하는 데 test를 쓰지 않는다. EnterpriseArena 진화 실험에서 Round 7은 validation 80%, test 생존율 95%를 보였지만, 반환 그래프는 Round 9이며 validation 90%, test 생존율 85%로 보고한다. 저자들은 중간 test 최고치를 보고 반환 그래프를 고르지 않는다.

4. 무엇이 좋아졌고, 비용은 무엇인가

저자들은 6개 benchmark와 4개 LLM의 24개 조합 중 21개에서 PG가 단독 또는 공동 최고였다고 보고한다. 구성 실험에서는 HotpotQA scratch evolution의 test F1이 78.79, baseline은 71.21이었다. MultiChallenge에서는 expert-initiated evolution이 92.86으로 가장 높았다. 다만 Table 1의 각 본평가 PG 행이 어떤 construction mode나 evolved checkpoint에서 왔는지는 논문이 명시적으로 연결하지 않는다. 그러므로 21/24의 우세 전체를 self-evolution 하나의 효과로 귀속할 수 없고, 본평가의 accuracy·rubric score·success·Pass@1과 구성 실험의 EM/F1도 하나의 ‘정확도’로 평균하면 안 된다.

그림 3. Lu et al. (2026), Figure 6, PDF p. 35의 원도판이다. HotpotQA와 MultiChallenge에서 candidate의 validation 추세와 채택·기각이 표시된다. 이 값은 최종 test 점수가 아니며, 기각 후보의 점도 곡선에 포함되어 있으므로 유지된 그래프의 성능이 매 세대마다 실제로 상승했다는 그래프로 읽으면 안 된다.

토큰도 봐야 한다. local subgraph guidance는 전체 그래프 guidance보다 적은 토큰을 쓸 수 있지만, baseline 대비 guidance LLM 호출은 추가 비용이다. 예를 들어 ALFWorld에서 local guidance는 full guidance보다 토큰을 약 70.9% 줄였지만, baseline보다 약 55.4% 많았다. 실행 step이 줄었다는 것과 총 지연·비용이 줄었다는 것은 다른 주장이다.

5. 어디에 맞는가

PG는 반복되는 도구 순서, 확인 지점, 실패 루프가 분명한 업무에 잘 맞는다. 우선 행동 vocabulary와 성공 판정을 정의하고 실제 궤적에서 노드 일치 실패가 얼마나 자주 나는지 측정해야 한다. 그다음 전체 그래프와 지역 그래프의 비용, validation split의 대표성, 불필요한 간선 추가가 미치는 영향을 따로 확인하는 것이 안전하다.

이 리뷰는 2026년 9월 8일 공개된 arXiv v1을 기준으로 한다. 저자 보고 성능은 흥미롭지만, 이 글은 외부 환경에서 재실행하지 않았고 공개 v1의 모델·judge·simulator 조건 밖 일반화를 주장하지 않는다.

References

Lu, Y., Chen, Y., Wu, S., & Arık, S. Ö. (2026). Procedural graphs: Self-evolving execution structures for LLM agents (arXiv:2609.09153v1). https://arxiv.org/abs/2609.09153v1

심층 리뷰 보기