Parallel ai agents safely combine edits for better solutions
Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization
Multiagent SystemsArtificial Intelligence
Summary
When many AI agents work on improving a shared problem solution, their individual helpful changes can sometimes interfere and make things worse overall. The authors studied this problem by representing agent interactions as a graph and showed how to pick compatible edits that add up safely using colorings of the graph. They proved mathematically how much of the combined improvement can be preserved and demonstrated that repeating this process helps the solution improve steadily. Experiments on code repair, route searches, and graph tasks show this approach keeps edits useful while reducing conflicts and speeding up work.
What this means in practice
- •For software engineers: Merge multiple independent code fixes safely to avoid conflicts and improve reliability in automated code repair.
- •For logistics planners: Coordinate multiple route optimization agents to efficiently improve vehicle routing without conflicts and reduce total planning time.
Authors
Hanmin Li, Yury Demidovich, Peter Richtárik
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.