Newest papers

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

Hanmin Li, Yury A. Demidovich, Peter Richtárik · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.30074 · cited by 0 works (OpenAlex) · open-access PDF

Chinese

并行验证的AI代理可以生成有用的局部编辑,但在其编辑相结合时退化共享解决方案。我们将这种协调问题模型为可评估的目标和已知的依赖图的分散式区块优化。独立集能够认证兼容的编辑,其验证的收益与相同的当前解决方案相比,准确增加。协调员构建一条路线的安全兼容的候选人,也可以评估互动编辑以捕捉有利的交互。我们证明,最佳的分散式共享色彩产生了连接,保留了相应的编辑的1美元/χ_f(G)美元的部分,相对于相同的当前解决方案进行验证的总局部改进,而 $χ_f(G)$是路线的安全兼容的染色编辑

Machine translation (Meta M2M100); the English original follows.

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/χ_f(G)$ fraction of the total verified local improvement, where $χ_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.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Computer science, Block (permutation group theory), Scheduling (production processes), Computation, Task (project management), Fraction (chemistry)

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange