Agentic AI 논문 읽기: Halo — DAG로 에이전트 워크플로우를 최적화하다

논문 정보

• 제목: Batch Query Processing and Optimization for Agentic Workflows
• 저자: Junyi Shen, Noppanat Wadlom, Yao Lu (National University of Singapore)
• 출판: arXiv 2509.02121 (2025.09)

지난 글에서 Paradigms 서베이는 에이전트 연구를 도구 사용, 계획, 피드백 학습이라는 세 패러다임으로 분류했다. 그 세 패러다임이 교차하면서 네 가지 범용 워크플로우가 만들어진다는 것이 핵심 기여였다. 하지만 워크플로우가 아무리 정교해도, 결국 물리적 하드웨어 위에서 실행되어야 한다. GPU에서 LLM 추론이 돌아가고, CPU에서 SQL 쿼리와 API 호출이 처리된다. 설계도가 아름다운 건물도 시공이 부실하면 무너진다. 이 실행의 효율성을 누가 책임지는가?

시리즈의 지금까지 논문들은 에이전트가 무엇을 하는가를 다뤘다. 추론하고(CoT), 행동하고(ReAct), 도구를 쓰고(Toolformer), 반성하고(Reflexion), 탐색한다(LATS). 하지만 이 모든 능력은 토큰으로 환산되고, 토큰은 GPU 사이클을 소비한다. 에이전트 하나가 작동할 때는 이 비용이 감당할 만하다. 에이전트 수백 개가 동시에 작동할 때, 비용은 곱셈이 아니라 조합 폭발이 된다. 논문 한 편의 실험에서는 10개의 에이전트가 동시에 수익 감소 원인을 조사하는 분석 워크플로우를 실행했는데, 각 에이전트가 searcher, connector, analyzer, editor라는 네 가지 역할에 걸쳐 수십 번의 LLM 호출과 도구 호출을 수행했다. 이 규모에서 중복과 유휴가 지배적 비용이 된다.

2025년 9월, National University of Singapore의 연구팀이 이 질문에 답하는 시스템 논문을 발표했다. Halo는 에이전트 워크플로우를 데이터베이스 시스템의 관점에서 바라본다. 워크플로우를 DAG(Directed Acyclic Graph)로 표현하고, 여러 워크플로우 사이에서 공유할 수 있는 계산을 발견하고, GPU와 CPU 사이의 작업 스케줄링을 최적화한다. 에이전트의 지능이 아니라, 에이전트의 인프라를 다루는 논문이다.

세 겹의 비효율 -- 왜 에이전트가 느린가

Halo가 해결하려는 문제는 세 가지 비효율이다.

첫째, 구조적 중복이다. 여러 에이전트가 같은 하위 과제를 수행할 때, 같은 SQL 쿼리를 각자 실행하고, 같은 API를 각자 호출한다. 10개의 에이전트가 같은 고객 데이터를 조회하면 10번의 동일한 데이터베이스 쿼리가 실행된다. 기존 에이전트 프레임워크(LangGraph, AgentScope)는 각 세션을 독립적으로 처리하므로 이 중복을 감지하지 못한다. 기존 LLM 서빙 엔진(vLLM, SGLang)도 마찬가지다 -- 개별 요청을 격리하여 최적화하므로, 요청 사이의 논리적 중복을 볼 수 없다.

둘째, 이종 파이프라인 버블이다. 에이전트 워크플로우는 GPU에서 실행되는 LLM 추론과 CPU에서 실행되는 도구 호출이 교차한다. LLM이 "이 SQL을 실행해라"고 출력하면, GPU가 멈추고 CPU가 SQL을 실행하고, 결과가 돌아오면 GPU가 다시 LLM을 돌린다. 이 왕복 과정에서 GPU와 CPU가 번갈아 유휴 상태에 빠진다. 파이프라인 안에 거품이 끼는 것이다.

셋째, LLM 연산자의 상태 관리 문제다. 서로 다른 워크플로우가 서로 다른 모델을 요구하면 모델 전환 비용이 발생한다. 같은 프롬프트 접두사를 공유하는 요청들이 있어도, 기존 시스템은 이를 인식하지 못해 KV 캐시를 재활용하지 못한다. 따뜻한 캐시를 차가운 캐시로 되돌리는 것은, 이미 끓인 물을 버리고 다시 끓이는 것과 같다.

Halo의 아키텍처 -- Parser, Optimizer, Processor

Halo의 구조는 세 단계 파이프라인이다. 데이터베이스 시스템의 쿼리 처리 파이프라인 -- 파싱, 최적화, 실행 -- 을 에이전트 워크플로우에 적용한 것이다. 이 대응은 우연이 아니다. 에이전트 워크플로우의 구조가 데이터베이스 쿼리의 구조와 본질적으로 유사하기 때문이다. 둘 다 의존관계가 있는 연산의 그래프이고, 둘 다 공유 가능한 중간 결과를 가지며, 둘 다 이종 자원 위에서 실행된다.

Parser는 YAML로 선언된 워크플로우를 DAG 형태의 중간 표현(GraphSpec)으로 변환한다. 핵심 변환은 의존성 분리(dependency decoupling)다. LLM 프롬프트 안에 묻혀 있는 SQL 쿼리나 API 호출을 별도의 노드로 추출한다. 프롬프트 내부의 불투명한 부작용이 아니라, 스케줄링 가능한 독립 단위로 만드는 것이다. 이 단계가 없으면 이후의 모든 최적화가 불가능하다.

Optimizer는 DAG를 실행 계획으로 변환한다. 연속 시간 최적화는 다루기 어려우므로, 계획을 결정 윈도우(에포크)로 분할한다. 각 에포크에서 옵티마이저는 현재 시스템 상태 -- 완료된 노드 집합과 각 워커의 상주 모델 및 KV 캐시 상태 -- 를 참조하여 GPU 워커에 배정할 LLM 노드를 선택한다. 비용 모델은 병목 워커의 지연 시간(makespan)과 총 시스템 부하를 동시에 고려한다.

기존 옵티마이저가 고정 비용을 가정하는 것과 달리, Halo의 비용 모델은 상태 인식적이다. 현재 워커에 이미 올라와 있는 모델과 다른 모델이 필요하면 전환 비용을 반영하고, 같은 프롬프트 접두사를 가진 요청이면 프리픽스 캐싱 할인을 적용한다. MILP(Mixed Integer Linear Programming) 오라클이 1.44시간 걸리는 최적 스케줄을, Halo의 DP 솔버는 상태 공간을 위상적 프론티어로 가지치기하여 2.24초에 거의 동일한 품질로 산출한다.

Processor는 계획을 실행한다. Coordinator가 DAG 상태를 비차단 이벤트 기반으로 관리하고, GPU 실행자가 LLM 추론을, CPU 실행자가 도구 호출을 처리한다. 웨이브프론트 스타일 실행을 통해, 하나의 LLM 노드가 완료되면 느린 형제 노드를 기다리지 않고 후속 노드가 즉시 실행될 수 있다. Coordinator는 잠금 없는 이벤트 루프로 완료 이벤트를 소비하고, 새로 준비된 노드를 타입에 따라 GPU 큐 또는 CPU 큐로 승격한다.

이 세 단계 구조에서 주목할 점은 Parser의 의존성 분리가 나머지 두 단계의 전제 조건이라는 것이다. 프롬프트 안에 묻혀 있는 도구 호출을 독립 노드로 추출하지 않으면, Optimizer는 최적화할 대상을 볼 수 없고, Processor는 CPU-GPU 오버랩을 만들 수 없다. 투명성이 최적화의 필요 조건인 것이다.

핵심 최적화 기법 -- 중복 제거, 유휴 시간 활용, 캐시 재사용

Halo의 구체적 최적화 기법 세 가지가 성능 향상의 원천이다.

요청 합체(Request Coalescing): 동일한 도구 호출을 자동으로 감지하여 한 번만 실행한다. 10개의 에이전트가 같은 SQL 쿼리를 요청하면, 물리적으로 한 번 실행하고 결과를 10개 노드에 팬아웃한다. 데이터베이스의 공유 스캔(shared scan)과 같은 발상이다. 제거 실험에서 이 기법을 빼면 복잡한 워크플로우(W6)의 지연이 154% 증가했다 -- 세 가지 기법 중 가장 큰 영향이다.

기회적 실행(Opportunistic Execution): 계획된 작업이 외부 요인(느린 API 응답 등)으로 지연될 때, 데이터 의존성이 이미 충족된 다른 노드를 빈 슬롯에서 실행한다. 유휴 시간을 생산적 시간으로 바꾸는 것이다. 정적 스케줄의 한계를 동적으로 보완하는 전략으로, W6에서 이 기법을 제거하면 지연이 56% 증가했다.

KV 캐시 공유 및 프리페칭: 같은 시스템 프롬프트나 같은 컨텍스트 접두사를 공유하는 LLM 요청들의 KV 캐시를 재사용한다. 프리필 단계에서 이미 계산된 토큰을 다시 계산하지 않으므로, 추론 비용이 절감된다. 동일 워커에서 계보(lineage)를 유지하도록 배치하는 로컬리티 인식 전략이 이를 가능하게 한다. 비용 모델에서 이를 "프리픽스 캐싱 할인"이라 부르는데, 공유 접두사가 길수록 유효 프리필 토큰 수가 줄어들어 할인 폭이 커진다.

세 가지 기법은 독립적이지 않다. 요청 합체가 동일 도구 호출의 물리적 중복을 제거하고, KV 캐시 공유가 동일 프롬프트 접두사의 연산 중복을 제거하며, 기회적 실행이 두 기법이 만들어낸 빈 슬롯을 채운다. 겹겹이 쌓인 최적화가 서로를 보완하는 구조다.

실험 결과 -- 숫자가 말하는 것

6개 벤치마크에서의 결과다. 논문이 발표된 2025년 기준, NVIDIA H200 GPU 3대와 AMD EPYC CPU 환경에서 측정되었다.

vLLM 대비 400배라는 숫자는 문맥 없이 보면 비현실적으로 보인다. 이는 vLLM이 에이전트 워크플로우를 전혀 인식하지 못하고 모든 요청을 순차적으로 처리하기 때문에 발생하는 극단적 비효율이 기준선이기 때문이다. 더 공정한 비교 대상인 OpWise(토폴로지 인식 배칭)와 LangGraph(에이전트 오케스트레이터) 대비에서도 1.6배에서 3.6배 향상을 보인다는 것이 실질적 의미가 있다.

핵심은 출력 품질 저하 없이 이 성능을 얻었다는 점이다. Halo는 에이전트의 행동 자체를 바꾸지 않는다. 같은 입력에 같은 출력을 내되, 그 과정의 물리적 실행만 최적화한다. 알고리즘의 의미론을 건드리지 않고 구현의 효율만 개선하는 것 -- 컴파일러가 프로그래머의 의도를 보존하면서 기계어를 최적화하는 것과 같은 원리다.

제거 실험(ablation study)의 결과도 각 기법의 기여를 선명하게 드러낸다.

워크플로우가 복잡해질수록(W1에서 W6으로 갈수록) 요청 합체와 기회적 실행의 중요성이 급격히 커진다. 단순 워크플로우에서는 프로파일링이 더 큰 영향을 미치지만, 복잡한 토폴로지에서는 중복 I/O 제거가 지배적 요인이 된다.

스케일 측면에서도 배치 크기 256에서 2048까지 거의 선형적으로 확장되고, GPU 워커 수 1개에서 3개까지 준선형 탄성을 보이며, 모델 크기 0.4B에서 32B까지 일관된 효율을 유지했다. 또한 A100, H100, H200 등 서로 다른 GPU에서도 일관된 개선을 보여, 특정 하드웨어에 종속되지 않는 범용성을 입증했다.

한계와 열린 문제 -- 지도의 빈칸

논문이 스스로 인정하는 한계가 두 가지 있고, 읽으면서 발견한 한계가 하나 더 있다.

첫째, 배포 범위가 단일 머신에 한정된다. 다중 GPU는 지원하지만, 다중 노드(여러 서버) 배포에는 분산 배치, 캐시 이동, 네트워크 인식 스케줄링이 추가로 필요하다. 프로덕션 규모의 에이전트 시스템이 수십 대의 서버에 분산되는 현실을 고려하면, 이 한계는 무시하기 어렵다.

둘째, 고정 논리 플랜을 가정한다. Halo는 워크플로우의 DAG 구조가 주어진 것으로 간주하고, 실행 순서와 자원 배분만 최적화한다. 비용을 줄이기 위해 프롬프트를 수정하거나, 정확도를 약간 희생하여 더 작은 모델로 교체하는 등의 상위 수준 재작성(semantic rewriting)은 범위 밖이다. AI Agents That Matter가 제기한 비용-정확도 트레이드오프를 시스템 수준에서 자동으로 탐색하려면, Halo 위에 한 층 더 필요하다.

셋째, 의존성 분리가 YAML 선언에 의존한다. Parser가 프롬프트 안에 묻힌 도구 호출을 추출하려면, 워크플로우가 YAML로 명시적으로 선언되어 있어야 한다. 자연어 지시만으로 에이전트가 자율적으로 도구를 선택하는 시나리오 -- ReAct나 Toolformer가 다루는 바로 그 시나리오 -- 에서는 DAG 자체를 사전에 구성할 수 없다. Halo의 최적화는 워크플로우의 구조가 사전에 알려져 있을 때 가장 강력하고, 구조가 동적으로 결정될 때 적용이 어려워진다.

2026년의 시선 -- 실현된 것, 확장된 것, 열린 것

이 논문이 발표된 지 반년이 지난 2026년 4월의 시점에서, Halo가 제기한 문제의식이 어떤 궤적을 그렸는지 세 가지 축으로 돌아본다.

실현된 것. DAG 기반 워크플로우 최적화라는 아이디어는 이미 현실로 들어왔다. 주요 LLM 서빙 프레임워크들이 프리픽스 캐싱과 연속 배칭을 기본 기능으로 탑재하기 시작했고, 에이전트 오케스트레이터와 서빙 엔진의 경계가 흐려지고 있다. Halo가 지적한 "오케스트레이션과 서빙의 분리"라는 비효율을 업계가 인식하기 시작한 것이다. 클라우드 API 수준에서도 프롬프트 캐싱이 기본 기능이 되었고, 이는 Halo의 KV 캐시 공유 개념이 API 인터페이스로 노출된 사례라 할 수 있다.

확장된 것. Halo는 CPU-GPU 이종 파이프라인을 다뤘지만, 2026년의 에이전트 시스템은 더 다양한 이종성을 보인다. 로컬 모델과 클라우드 API의 혼용, 캐시 서버와 벡터 데이터베이스, 코드 실행 샌드박스까지. 이종 파이프라인 최적화의 범위가 Halo가 그린 것보다 넓어지고 있다. 특히 MCP(Model Context Protocol)와 같은 표준이 도구 호출을 규격화하면서, 도구 노드의 시그니처 정규화 -- Halo의 요청 합체가 의존하는 바로 그 메커니즘 -- 가 더 자연스럽게 가능해지는 환경이 조성되고 있다.

열린 것. 가장 근본적인 질문은 여전히 열려 있다. 에이전트 워크플로우를 고정 DAG로 표현할 수 있는가? LATS처럼 탐색 과정에서 동적으로 분기하는 워크플로우, Reflexion처럼 실패에 따라 구조 자체가 바뀌는 워크플로우는 정적 DAG로 포착되지 않는다. 동적 워크플로우의 런타임 최적화는 아직 해법을 기다리고 있다. 또한 Halo가 다중 노드 분산 환경을 지원하지 않는 한계도 프로덕션 채택의 벽으로 남아 있다. 네트워크 레이턴시와 캐시 이동까지 비용 모델에 포함시키는 것은 단일 머신 최적화와는 차원이 다른 문제다.

CoALA 좌표계 위의 Halo

Halo는 CoALA 좌표계의 바깥에 있다. 기억, 행동, 판단이라는 인지적 축이 아니라, 에이전트를 실행하는 하부 구조의 최적화다. CoALA가 에이전트의 마음을 설계한다면, Halo는 에이전트의 신체 -- 물리적 실행 환경 -- 를 최적화한다.

이 위치가 중요한 이유가 있다. 시리즈에서 다룬 대부분의 논문은 에이전트의 인지적 능력 -- 추론, 계획, 반성, 학습 -- 에 집중한다. 그 인지적 능력이 프로덕션에서 실제로 작동하려면, 시스템 수준의 효율이 뒷받침되어야 한다. 마음과 신체가 분리될 수 없듯, 알고리즘 연구와 시스템 연구도 결국 합류해야 한다. Halo는 그 합류 지점의 좌표를 보여준다.

마무리

한 문장으로 줄이면 이렇다. 에이전트의 지능을 높이는 것만으로는 충분하지 않다 -- 지능이 실행되는 인프라의 효율이 지능 자체만큼 중요하다.

Halo의 DAG 노드 안에는 도구 호출이 들어 있었다. 검색 API를 부르고, SQL을 실행하고, 코드 인터프리터를 돌리는 것. Halo는 그 노드들의 실행 순서와 자원 배분을 최적화했지만, 노드 안에서 무슨 일이 일어나는지 -- 어떤 도구를 왜 선택하고, 어떻게 조합하고, 실패하면 어떻게 복구하는지 -- 는 다루지 않았다. 다음 글에서는 바로 그 안을 들여다본다. Tool Use Evolution -- 단일 도구 호출에서 다중 도구 오케스트레이션까지, 에이전트가 도구를 다루는 방식이 어떻게 발전해왔는지 여섯 가지 차원으로 분석한다.

이 글은 "Agentic AI 논문 읽기" 시리즈의 열세 번째 글입니다. 시리즈 전체 목록은 시리즈 페이지에서 확인할 수 있습니다.