병렬 AI 에이전트의 편집 충돌을 그래프 색칠로 안전하게 합치는 방법

무엇인가

병렬로 돌린 AI 에이전트가 각자 그럴듯한 국소 수정을 내놓아도, 그것을 한꺼번에 합치면 공유 산출물이 오히려 나빠지는 일이 흔하다. 논문이 드는 예는 프로그램 수리에서의 할인 로직이다. 가격 모듈과 결제 모듈 중 어느 쪽이든 할인을 한 번 적용하도록 고치면 각각은 개선이지만, 둘을 함께 적용하면 할인이 두 번 적용된다. 저자들은 이 문제를 '검증된 제안 통합(verified proposal integration)'으로 정식화한다. 제안 생성과 제안 통합을 분리하고, 통합 단계에서 어떤 편집을 합칠 수 있는지를 의존 구조만으로 판정하겠다는 것이다.

어떻게 동작하나

형식화는 이렇다. 공유 산출물 x를 m개의 블록 x_b로 나누고, 손실 F는 알려진 인수분해 F(x)=Σ_a ℓ_a(x_{N(a)})를 따른다. 이 인수분해가 의존 그래프 G를 유도하는데, 두 블록이 같은 인수에 등장하면 간선으로 잇는다. G의 독립집합에 속한 블록들은 어떤 목적함수 항도 공유하지 않으므로 그 편집들의 이득은 정확히 더해진다. 각 에이전트는 같은 기저 산출물 x를 받아 자기 블록만 고치고, 코디네이터는 제안을 하나씩 x에 대보아 검증된 싱글턴 이득 g_ib = F(x) − F(x_{−b}, Y_ib) ≥ 0을 계산한다. 문제는 이 검증된 이득 총합 중 얼마를 통합 후에도 보장할 수 있느냐다.

무엇과 다른가

답은 그래프의 분수 색칠(fractional coloring)이다. 독립집합마다 가중치 λ_I를 주되 모든 블록이 총 가중치 1 이상으로 덮이게 하고, 그 총량 Λ(λ)의 최솟값이 분수 색칠수 χ_f(G)다. 코디네이터는 λ_I > 0인 독립집합 중 검증 이득 합이 가장 큰 것을 골라 적용한다. 정리 1은 이 규칙이 매 라운드 F(x^k) − F(x^{k,safe}) ≥ (1/Λ)Σg_ib를 만족함을, 즉 최적 분수 색칠에서 검증된 국소 개선의 1/χ_f(G)를 보존함을 증명한다. 정리 2는 이 한계가 본질적임을 보인다. 어떤 그래프 G에 대해서도, 제출된 제안의 부분집합을 고르는 방식으로는 최악의 경우 1/χ_f(G)보다 큰 비율을 보장할 수 없다. 증명은 분수 색칠 LP의 쌍대해 w로 F(z) = C − Σ w_b z_b + B Σ_{간선} z_b z_c를 구성해, 독립집합의 이득은 1 이하로 묶고 비독립집합은 벌점 B로 음수가 되게 만든다. 실무적 근사로 일반 색칠의 색 클래스 중 최고 점수를 고르면 1/κ 보장이 따라온다(따름정리 3). 여기에 안전 후보와 전체 합집합을 모두 평가해 손실이 낮은 쪽을 택하는 낙관적 통합(식 13)을 얹으면, 보장은 유지하면서 우호적 상호작용까지 취할 수 있다. 4장은 국소 솔버 품질·블록 오차 한계·배정 커버리지 가정을 더해, 목적함수 격차가 기하급수적으로 줄어드는 조건과 그 속도가 과제 구조·에이전트 배정·계산 비용으로 분리되는 결과를 제시한다. 이 분해에서 배정은 선형계획법이 되고 시간–비용 트레이드오프가 명시적으로 나온다.

어떻게 쓰나

실험은 먼저 충돌 상황을 겨냥한다. 3개 모듈 과제 7개(의존 그래프가 경로, χ_f = χ = 2)에 claude-haiku-4-5로 3회, claude-sonnet-5로 1회씩 돌려 28개의 과제–반복 단위를 만들었다. 검증 기반 규칙 COL과 OPT는 28개를 모두 해결했지만, 모든 제안을 그대로 적용하는 MA는 1라운드 충돌이 없던 17개는 모두 풀고 충돌이 있던 11개는 하나도 풀지 못했으며, 합집합이 손실을 낮출 때만 받아들이는 MAG도 그중 1개만 회복했다. T1 과제에서 MA의 실패 횟수 궤적은 21, 5, 5, 5로 제자리였고 OPT는 21, 5, 0으로 끝냈다. OPT는 37번의 합집합 평가 중 11번 색 클래스 후보를 선택했고, 감사한 108건의 색 병합은 모두 이득 가산 조건을 만족했다. 다만 작은 과제에서는 단일 에이전트(SGL)가 자원 면에서 유리했다. SGL은 28개를 모두 중앙값 1회 호출로 풀었고 입력 비용은 COL·OPT의 약 1/4, t_ver = 0일 때 모델링 완료 시간은 약 1/3이었다. 입력 비용 예산 9단위에서는 MA가 21회 중 12회를 푼 반면 COL과 OPT는 8회였다. 병렬 작업량을 키운 두 번째 벤치마크는 4~32개 모듈, 크기별 3개씩 12개 인스턴스다. 의존 그래프는 희소 이분 그래프로 χ_f = χ = 2였고 실제 제안 충돌은 관찰되지 않았다. 32개 모듈에서 OPT는 t_ver = 0일 때 모델링 완료 시간을 SGL의 15.3분에서 4.1분으로 줄이면서 입력 비용은 2.02배를 썼다. 검증 지연을 60초, 300초로 두면 속도 향상은 3.69배에서 2.42배, 다시 1.32배로 줄었다. 충돌이 없으니 OPT는 폴백 규칙을 한 번도 쓰지 않았고, t_ver > 0 구간에서는 추가 검증 단계 때문에 MA보다 느렸다.

전제와 한계

분수 색칠 자체의 효과를 보려고 χ(C5) = 3, χ_f(C5) = 5/2인 C5를 쓴 실험이 있다. 4개 도메인에 걸친 12개 단위에서 고정 일반 색칠의 3개 클래스 중 고르는 COL3와 5개 독립 쌍을 모두 평가하는 FRAC5를 비교했는데, FRAC5는 한 번도 뒤지지 않았고 12개 중 4개에서 앞섰다. 평균 보존 비율은 0.5615에서 0.6167로 올랐다. 이 벤치마크에서는 12개 단위 모두 전체 합집합의 이득이 싱글턴 이득 합보다 커서 낙관적 통합이 내내 합집합을 선택했다. 여러 라운드 실험은 5~10개 모듈의 인터페이스 마이그레이션 설계 16개(C5 또는 프리즘 그래프), 48개 과제–반복 단위를 Qwen2.5-Coder-32B-Instruct로 돌렸다. FOPT는 평균 실패 검사 수를 34.38에서 6.29로 줄였고 MA는 20.02였다. 1라운드 분수 후보는 48개 중 47개에서 전체 합집합보다 손실이 낮았다. 다만 여섯 병렬 규칙 중 3라운드 안에 과제를 완전히 해결한 것은 없었고, 종료 시점에는 FRAC 6.17 대 COL 6.19로 차이가 거의 사라졌다. 이후 제안이 각 규칙이 채택한 프로그램에 의존하기 때문에 1라운드 우위가 끝까지 가지는 않는다는 것이 저자들의 설명이다.

실제 구조에 가까운 진단도 있다. 공개 도로망 3개에서 블록 5개가 유도 C5를 이루는 30개 영역을 뽑아 시드 3개씩 90개의 짝지은 단위를 만들고, CPU 에이전트 5개가 블록마다 3만 번의 균형 교환을 시도했다. 분수 지원 규칙은 1,617단위의 검증된 싱글턴 이득 중 922단위(57.0%)를 보존해, 미리 고정한 일반 색칠의 799단위(49.4%)보다 15.4% 상대적으로 많았다. 90쌍 중 52쌍에서 엄격히 우세하고 나머지는 동률이었다. 보호하지 않은 전체 합집합은 모든 제안이 개별적으로는 개선임에도 31회에서 그래프 컷 목적함수를 오히려 악화시켰다. 흥미롭게도 싱글턴 이득을 본 뒤 고르는 적응적 일반 색칠도 922단위로 같은 성적을 냈다. ITC-2007 시간표 9개 인스턴스에서는 FRAC이 고정 COL보다 10% 많은 개선을 보존했고(2개 우세, 7개 동률), 45건의 호환 쌍 병합이 모두 정확한 가산성을 만족했으며 MA는 comp13에서 강의실 충돌을 만들었다. CVRP 경로 탐색에서는 분수 스케줄링이 12쌍에서 측정 벽시계 시간을 13.16~17.28%(중앙값 15.00%) 줄였고, 에이전트 CPU 시간 합은 거의 같았지만(중앙값 비율 1.008) 최종 경로 비용은 4쌍에서만 개선되고 5쌍 동률, 3쌍 악화였다.

개발자 입장에서 이 논문의 실용적 메시지는 병렬 에이전트 오케스트레이션에서 '합치기'를 별도 계층으로 분리하라는 것이다. 여러 에이전트에게 같은 저장소의 서로 다른 모듈을 맡기고 결과를 그대로 머지하는 방식은, 각 편집이 개별 테스트를 통과하더라도 공유 인터페이스나 공유 목적함수 항에서 충돌할 수 있다. 테스트–모듈 범위나 정적 분석으로 의존 그래프를 뽑고, 그 그래프의 색 클래스(또는 분수 색칠 지원 집합) 중 검증 이득 합이 가장 큰 것을 적용하는 규칙은 구현이 단순하면서 최악의 경우 보장을 준다. 다만 수치가 말하듯 병렬화 이득은 과제가 클수록 나오고, 작은 과제에서는 검증·조정 오버헤드가 단일 에이전트보다 비쌀 수 있다. 검증 지연 t_ver가 속도 향상을 3.69배에서 1.32배까지 깎는 민감도도 함께 봐야 한다.

저자들이 밝힌 전제와 한계는 분명하다. 의존 인증서는 보수적이어야 한다. 간선을 더 넣으면 보장이 약해질 뿐이지만, 실제 의존을 빠뜨리면 상호작용하는 편집을 호환으로 잘못 분류한다. 수렴 보장은 조건부 국소 개선과 블록 오차 한계, 배정 커버리지 가정 위에 서 있고, 낙관적 통합의 비교는 현재 라운드에 국한된 국소적 판단이다. 실험 쪽에서는 C5 구조를 결정론적 경로 배정으로 인위적으로 유도했다는 점, CVRP 입력 4개 중 2개는 개발 중에 나머지 2개는 초기 결과를 본 뒤에 골랐다는 점, 속도 향상이 탐색 청크 전체에 걸쳐 경로 쌍 잠금을 유지한다는 가정에 의존한다는 점을 명시했다. 모든 탐색을 병렬화하고 커밋만 직렬화하는 불변 스냅샷 방식은 비교 대상에서 제외됐다. 또한 여러 라운드 실험에서 어떤 병렬 규칙도 3라운드 내에 과제를 완전히 해결하지 못했다.