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

Graph Interview 소식

Graph Interview - 10th - Tobias Rebert - · Luma

Differentiate from LPG: RDF’s Real PowerLPG 대비 RDF가 가지는 결정적인 차별점과, 추상적인 온톨로지를 실제 데이터 레이어에서 강력하게 구현해내는 RDF만의 파워 Great Modeling for RDF (Migration from Knowledge…

Yitae Jeong

• 오는 8월 25일(화) 오후 8시–10시, 저희 GUG에서 진행하는 Graph Interview 소식 하나를 전해드립니다. 위 Luma 링크로부터 사전 등록을 해주시면 되겠습니다.
• "From Ontology to RDF Graph Databases"를 주제로, 온톨로지와 RDF를 실제 엔터프라이즈 환경에서 활용하기 위한 그래프 데이터베이스를 개발하고 있는 DeepTech 스타트업 Tentris의 CEO, Tobias Rebert와 온라인 인터뷰를 진행합니다.
• 특히 Tentris가 이번 KGC Startup Pitch에서 FalkorDB를 제치고 우승한 놀라운 소식도 있던데요. 기술적인 이야기뿐 아니라, 그래프 데이터베이스 시장에서 Tentris만의 차별점을 어떻게 만들어가고 있는지 그 비결도 살짝 전수해주시지 않을까 기대해봅니다.
• 그래프 DB, RDF, 온톨로지등과 관련한 다양한 이야기에 관심 있으신 분들이라면 편하게 참석하셔서 직접 이야기도 듣고 디스커션도 하면서 값진 인사이트 많이 챙겨가시길 바랍니다 !

FROM AGENT LOOPS TO DETERMINISTIC GRAPHS: EXECUTION LINEAGE FOR REPRODUCIBLE AI-NATIVE WORK

From Agent Loops to Deterministic Graphs: Execution Lineage for Reproducible AI-Native Work

Large language model systems are increasingly deployed as agentic workflows that interleave reasoning, tool use, memory, and iterative refinement. These systems are effective at producing answers, but they often rely on implicit conversational state, making it difficult to preserve stable work products, isolate irrelevant updates, or propagate changes through intermediate artifacts. We introduce execution lineage: an execution model in which AI-native work is represented as a directed acyclic graph (DAG) of artifact-producing computations with explicit dependencies, stable intermediate boundaries, and identity-based replay. The goal is not to make the model a better one-shot writer, but to make evolving AI-generated work maintainable under change. We compare execution-lineage replay against loop-centric update baselines on two controlled policy-memo update tasks. In an unrelated-branch update, DAG replay preserved the final memo exactly in all runs, with zero churn and zero unrelated-branch contamination, while loop baselines regenerated the memo and frequently imported unrelated context. In an intermediate-artifact edit, all systems reflected the new constraint in the final memo, but only DAG replay achieved perfect upstream preservation, downstream propagation, unaffected-artifact preservation, and cross-artifact consistency. These results show that final answer quality and maintained-state quality are distinct. Strong loop baselines can remain competitive at producing polished final outputs when the task is a bounded synthesis/update problem and all current sources fit in context, but immediate task success can mask partial state inconsistency that may compound over future revisions. Execution lineage provides stronger guarantees about what should change, what should remain stable, and how work evolves across revisions.

arXiv.orgJosh Rosen

• 요즘 AI 에이전트 트렌드를 살펴보다 보면 저희에게 상당히 흥미로운 표현 하나가 눈에 들어옵니다. 바로 Graph Engineering입니다. 아직 엄밀하게 굳어진 학술 용어라기보다는 최근 에이전트 개발 커뮤니티에서 자주 등장하기 시작한 하나의 프레임에 가깝습니다.
• 하나의 에이전트가 반복해서 생각하고 도구를 쓰는 loop를 어떻게 잘 만들 것인가(루프 엔지니어링)에서 한 걸음 더 나아가, 여러 에이전트와 도구, 검증 단계와 상태를 어떤 구조로 연결할 것인가를 고민해보자는 흐름입니다.
• 이건 생각해보면 꽤 재미있는 변화입니다. 그동안 그래프라고 하면 지식 그래프처럼 무엇을 연결해 표현할 것인가를 먼저 떠올렸지만, 최근의 Graph Engineering 트렌드에서는 그래프의 대상이 조금 달라집니다. 이제 노드는 지식이나 데이터만이 아니라 에이전트, 도구, 판단 단계, 중간 작업물이 될 수 있고, 엣지는 그 사이의 실행 순서와 의존성을 나타낼 수 있습니다.
• 이번 주 오마카세에서 소개할 논문은 여기서 한 걸음 더 들어갑니다. 저자들이 사용하는 이름은 Graph Engineering이 아니라 Execution Lineage입니다.
• ReAct 기반 에이전트 루프는 추론과 도구 사용을 반복하며 답을 만들어내는 데는 강하지만, 그 과정에서 만들어진 중간 상태와 의존성은 대개 transcript 안에 암묵적으로 남습니다.
• 짧은 질문과 응답에서는 큰 문제가 아닐 수 있습니다. 하지만 분석 리포트처럼 여러 단계를 거쳐 계속 수정되는 작업에서는 작업 자체의 의존 구조를 시스템이 알고 있어야 하기 때문에 이야기가 달라집니다.
  • 어떤 자료가 바뀌었을 때 무엇을 다시 계산해야 하는지, 어떤 중간 결과는 그대로 남겨야 하는지, 이번 수정과 아무 관계 없는 작업까지 다시 생성할 필요가 있는지를 판단하려면 모델이 더 똑똑해지는 것만으로는 부족할 수 있습니다. 그 의존성을 정확하게 파악하고 판단할 수 있는지의 능력이 중요합니다.

• 저자들은 이 문제를 위의 다섯 가지 질문으로 연구 방향을 구체화합니다. 무관한 변경이 생겼을 때 최종 산출물을 정확히 그대로 보존할 수 있는지, 중간 아티팩트의 수정은 필요한 하위 결과에만 정확히 전파할 수 있는지, 그리고 이런 maintained-state quality에서 execution lineage가 기존 loop 방식보다 실제로 더 나은지를 묻습니다.
• 또한 최종 답변만 평가해서는 이런 차이를 놓치는 것은 아닌지, 그리고 이런 구조적 이점이 토큰 사용량, 모델 호출 수, 실행 시간에서는 어떤 trade-off를 만드는지까지 확인합니다.
  • 여기서 문제로 삼는 것은 실행 과정이 달라지며 생기는 Non-deterministic execution, 무엇이 무엇에 의존하는지가 프롬프트 속에 숨어버리는 Implicit dependencies, 구조화된 형식 상에서 중간 추론단계가 온전히 보존되지 못하는 Limited reproducibility, 그리고 작은 수정 하나에도 전체를 다시 돌려야 하는 Global recomputation입니다.
• 이 논문은 그래서 실행을 명시적인 DAG(방향성 비순환 그래프)로 표현합니다. 다만 이 논문이 LLM 자체의 확률성을 없애겠다는 것은 아닙니다. 고정된 입력, 모델, 도구 결과 아래에서 어떤 실행은 그대로 재사용할 수 있고, 어떤 변화는 정확히 어디까지 전파되어야 하는지를 구조적으로 관리하자는 것이 핵심입니다.

• 저자들은 기존의 프롬프트, 대화 기록 중심 상태 관리를 Prompt Lineage라고 대비시킵니다. 많은 기존 에이전트 루프에서는 작업의 계보가 사실상 이런 형태로만 남습니다. 감사나 서술에는 유용하지만, 다른 작업이 안정적으로 의존할 수 있는 경계가 없습니다.
• 즉, 무슨 일이 있었는지 사후적으로 파악하는 데는 좋지만, 시스템이 의존성을 선언하거나 결과를 재사용하는 메커니즘으로는 부적합하다는 것입니다. 저자들은 이를 log에 비유합니다.
• 반대로 Execution Lineage는 작업을 G = (V, E) 형태의 그래프로 명시합니다. 각 노드 v = (I_v, f_v, O_v)는 자신이 소비할 입력(I_v), 실행 절차(f_v), 그리고 산출물(O_v)을 명시적으로 선언합니다. 산출물은 단순 텍스트가 아니라, 안정된 경계를 가진 타입 있는 아티팩트로 취급됩니다.

• Figure 1이 논문의 문제의식을 가장 직관적으로 보여줍니다. 왼쪽의 agent loop에서는 상태가 prompt와 transcript 안에 함께 흘러가지만, 오른쪽의 execution lineage에서는 각 단계가 명시적인 artifact와 dependency로 분리됩니다. 그래서 변경이 생겼을 때 어디까지 다시 계산하고, 어디는 그대로 보존할지를 런타임이 구조적으로 결정할 수 있습니다.

Execution Lineage 설계 원칙

• 논문에서는 다음 설계 원칙을 총 네 가지로 카테고리화합니다.
  • 명시적 의존성 선언 : 노드는 선언되지 않은 상위 상태를 소비할 수 없다. 즉 워크플로우의 인과 구조가 프롬프트 조립 로직 속에 숨지 않고 그래프 자체에 드러나야 한다.
  • 지역적 가시성 경계 : 각 노드는 자신의 작업에 필요한 컨텍스트만 본다. 프롬프트 비대화를 줄이고, 왜 그런 결과가 나왔는지 파악하기 쉽게 만들기 위해서다.
  • 정체성 기반 재사용 : '비슷해보인다' 보다 '같은 구조와 같은 입력을 공유한다' 는 증명 위에서 재사용을 결정한다.
  • 정규 출력 고정 (Canonical publication) : 노드 내부에서 여러번의 생성, 검증, 수정이 일어나더라도, 다운스트림에서는 하나의 공식 산출물만 노출한다. 여기에서 다운스트림은 가장 최신의 대화 상태가 아닌 발행된 결과에만 의존한다.

• 실행 정체성은 식 4로 정의됩니다. 노드의 구조(σ_v), 입력 해시(x_v), 상위 노드들의 정체성을 함께 해시한 값입니다. 이 값이 그대로면 이전 실행 결과를 그대로 replay하고, 바뀌면 그 노드와 하위 노드만 다시 계산합니다. 무관한 브랜치는 건드리지 않습니다.

Policy-memo update task

• 세션 6에서 저자들은 Telehealth expansion 정책 메모라는 통제된 시나리오에서 두 가지 업데이트 과제를 설계합니다. 다음 세 가지 조건(naturalistic loop update, loop with explicit edit-event awareness, DAG replay) 상에서 동일한 모델 및 소스들을 비교하였습니다.

• 세 조건은 동일한 프롬프트 정보를 받는 비교가 아닙니다. DAG replay에는 의존성 그래프와 런타임이 계산한 재실행 범위가 함께 제공되고, 루프 조건들은 이를 받지 않습니다. 저자들도 이를 equal-prompt 비교가 아니라 system-level 비교라고 언급하며, 명시적인 의존성 구조를 실행 계층에 두었을 때 어떤 차이가 생기는가를 검증하는 실험 목표를 가지고 있습니다.
  • Loop final update : 이전 최종 메모, 현재 소스 자료, 요청된 출력 형식, 일반적인 업데이트 요청을 받습니다. 의존성 그래프, 영향/비영향 클레임 ID, 재계산 범위, 허용/비허용 아티팩트 목록, 오라클 라벨, 정답은 받지 않습니다.
  • Loop + edit event : 위와 동일한 조건에 더해, 소스나 아티팩트에서 무엇이 바뀌었는지 알려주는 edit event를 추가로 받습니다. DAG의 우위가 단순히 무엇이 바뀌었는지 아는 것만으로 설명되는지를 확인하기 위한 조건입니다.
  • DAG replay : 아티팩트&소스 edit event, 아티팩트 정체성, 의존성 그래프, 의존성 기반 재계산 계획, 보존된 아티팩트 상태를 받습니다. 런타임이 스스로 도출한 경우는 제외하고 채점 전용 라벨, 정답이 되는 최종 추천, 숨겨진 채점 기준, 오라클 영향-클레임 ID는 받지 않습니다.
• 위의 조건으로부터 두 가지 태스크를 수행합니다.
  • Unrelated-branch Update : 의존성 격리 테스트로서, 최종 메모와 무관한 인접 브랜치를 수정했을 때, 시스템이 최종 메모를 정확히 그대로 보존할 수 있는지를 봅니다.
  • Intermediate-artifact Edit : 전파 일관성 테스트로서, 중간 단계의 추천 기준 아티팩트에 새로운 제약을 추가했을 때, 상위 근거는 보존하면서 하위 산출물에는 제대로 전파되는지를 봅니다.

• 두 실험을 함께 보면 이 논문이 말하는 Maintained-State Quality가 조금 더 선명해집니다. 중요한 것은 단순히 최종 답변을 새 요구사항에 맞게 고쳤는가가 아니라 시스템이 작업의 의존 구조를 제대로 알고 있어야만 무엇을 그대로 둘지, 무엇을 다시 계산할지를 구분할 수 있습니다.
• 즉, 보존과 전파는 서로 반대되는 요구처럼 보이지만, 사실 같은 문제의 두 면입니다. Table 1과 Table 2는 이 차이가 최종 산출물 품질보다 유지되는 작업 상태의 품질에서 더 뚜렷하게 나타난다는 점을 보여줍니다.
• 첫 번째 unrelated-branch update는 최종 산출물에 전혀 영향을 주지 않아야 함을 봅니다. 최종 메모와 의존 관계가 없는 브랜치가 수정되었다면, 좋은 시스템은 기존 작업을 다시 쓰지 않고 그대로 보존해야 합니다.
  • 흥미로운 지점은, 무엇이 바뀌었는지를 알려준 loop & edit event조차 오염을 막지 못했다는 것입니다.
  • 즉 소스가 바뀐 사실을 아는 것과, 그 변경이 지금 이 산출물과 관련이 있는지를 판단할 의존성 구조를 갖는 것은 다른 문제라는 것을 보여줍니다.
• 두 번째 intermediate-artifact edit는 반대로 관련된 하위 산출물까지 정확하게 전파되어야 함을 봅니다. 중간 기준이 바뀌었다면 상위 근거와 무관한 상태는 보존하면서, 영향을 받는 하위 아티팩트에는 변경이 일관되게 전달되어야 합니다.
  • 여기에는  세 조건 모두 최종 메모에 새 제약을 반영했습니다. 최종 산출물만 채점하면 전부 통과했지만, 중간 상태를 함께 보면 두 루프 조건의 교차 아티팩트 일관성은 0.50에 그쳤습니다. 반면 DAG replay는 상위 아티팩트 보존, 하위 전파, 미영향 아티팩트 보존, 교차 아티팩트 일관성에서 모두 1.00을 기록했습니다.
  • 즉, 눈에 보이는 결과물은 새 제약을 담고 있어도, 그 옆에서 유지되고 있던 중간 아티팩트들과는 완전한 일관성을 이루지 못했다는 뜻입니다. 현재 재현 가능하다고 알려진 파이프라인의 상당수는 사실 최종 결과물 하나만 재현 가능한 것일 수 있다는 의문을 남기고 있습니다.
• 추가로 저자들은 DAG replay가 항상 더 빠르다고 주장하지 않습니다. unrelated branch 과제에서는 DAG가 입력 토큰과 시간 모두에서 압도적으로 유리했지만(7.9초 vs 33.5~55초), 중간 아티팩트 편집 과제에서는 다운스트림을 순차적으로 다시 계산해야 했기 때문에 오히려 더 느렸습니다(73.6초 vs 31.1~38.7초). 즉, 효율은 업데이트의 구조와 런타임 구현에 달려 있다는 정확한 사실을 보여주고 있습니다.

• 한계점도 짚고 넘어가면 하나의 정책 메모 도메인, 두 개의 과제, 3회 반복, 단일 모델 계열(GPT-5.2)에 한정되어 있고 포괄적인 벤치마크가 아니라 통제된 메커니즘 검증 연구(controlled mechanism study)로 규정되어 있습니다. 또한 비교 대상인 루프 베이스라인도 naturalistic한 형태이지 최선의 구현은 아닙니다. 저자들은 명시적 상태 추적을 갖춘 더 강한 커스텀 루프 하네스라면 격차가 줄어들 수 있다고 직접 인정합니다.
• 따라서 위 논문의 주장은 그래프가 루프보다 본질적으로 더 좋은 선택이라는 것이 아닙니다. 핵심은 변경이 발생했을 때 그 영향 범위를 시스템이 명시적인 의존 구조를 통해 추적할 수 있는가에 있습니다. 그래프는 이러한 의존 관계와 변화의 전파 범위를 구조적으로 표현하고 다룰 수 있게 해주는 하나의 수단입니다.
• 이러한 관점에서 에이전트 시스템 상의 그래프는 더 이상 에이전트와 도구를 연결하는 실행 토폴로지에만 머물지 않습니다. 앞으로의 Graph Engineering 관점에서 중요한 것은 단순히 노드를 어떻게 연결할 것인가만큼, 변화가 그래프 위에서 어떻게 흘러가고 어디에서 멈추어야 하는가를 설계하는 것이 중요해질 수 있습니다.

Reference

• Graph engineering에 대한 유튜브 영상: https://www.youtube.com/watch?v=nfUKLULchXE&t=2121s, https://www.youtube.com/watch?v=dR81q1bJVSA
• 에이전트 하네스, 실행 구조 : https://arxiv.org/abs/2603.25723
• DAG docs : https://airflow.apache.org/docs/apache-airflow/3.0.4/core-concepts/dags.html

[Contact Info]

Gmail: jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn