arXiv cs.MA· Hanmin Li, Yury Demidovich, Peter Richt\'arik·· 13 小时前AI 评分34
并行 AI 智能体协作建模为图结构分布式块优化
Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization
AI 导读
研究将并行 AI 智能体的协作冲突建模为带依赖图的离散块优化问题，证明最优分数着色合并可保留总验证局部改进的 1/χ_f(G) 比例，且该保证在同类合并中紧致。在代码修复实验中，验证式合并解决了朴素合并失败的编辑冲突；三个公开路网 90 次配对运行保留 922 单位图割改进，路线搜索智能体的分数调度将实测墙钟时间中位数降低 15%。
正文 · 原文
Abstract:Parallel AI agents can produce useful local edits yet degrade a shared solution when their edits are combined. We model this coordination problem as discrete block optimization with an exactly evaluable objective and a known dependency graph. Independent sets certify compatible edits whose verified gains, measured against the same current solution, add exactly. A coordinator constructs a safe compatible candidate and can also evaluate interacting edits to capture favorable interactions. We prove that an optimal fractional coloring yields a merger that preserves a $1/\chi_f(G)$ fraction of the total verified local improvement, where $\chi_f(G)$ is the graph's fractional chromatic number. This guarantee is tight among mergers that select a subset of the same proposals. Under conditional local-improvement guarantees and a block error-bound condition, repeated collaboration converges geometrically in the objective gap. The rate separates task structure, agent allocation, and computation cost, yielding a linear program for agent assignment and an explicit time-cost trade-off. Code-repair experiments show that verified merging resolves conflicts between individually useful edits that cause naive merging to fail. On larger conflict-free tasks, parallel agents reduce modeled completion time at higher input-token-equivalent cost. On three public road networks, fractional integration retains 922 units of verified graph-cut improvement across 90 paired runs. For route-search agents sharing exclusive access to vehicle routes, fractional scheduling reduces measured wall time by a median of 15% across twelve paired runs, with route-cost changes varying across runs.
| Comments: | 24 pages, 8 figures |
| Subjects: | Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI); Optimization and Control (math.OC) |
| MSC classes: | 68T42, 90C27 |
| Cite as: | arXiv:2610.30074 [cs.MA] |
| (or arXiv:2610.30074v1 [cs.MA] for this version) | |
| https://doi.org/10.48550/arXiv.2610.30074 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Hanmin Li [view email]
[v1]
Wed, 21 Oct 2026 17:27:17 UTC (224 KB)
来源：arXiv cs.MA · arxiv.org