CS Paper Radar

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

Hanmin Li, Yury Demidovich, Peter Richtárik

cs.MA cs.AImath.OC ·submitted 2026-10-21 17:27 UTC · v1
theory

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.

Comment
24 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Verifying Coordination in Parallel Coding Agents: NP-Bench and a Scheduling Planner

cs.AI ·2026-10-05 ·Sumanyu Muku
benchmark similarity 0.64
Abstract

A team of coding agents can look fine agent by agent yet fail as a team: each passes its own tests while the merged result is broken, and single-agent evaluation never catches it. As teams run several LLM coding agents in parallel on one codebase, the agents collide: two rewrite the same function, one codes against a contract a teammate just changed, and integration fails after the work is done. Most coordination tools react (watch for a conflict, then warn), but at agent speed the warning arrives after the wasted edit. We recast the problem as scheduling: take each work item's declared scope, partition the work into disjoint scopes, and order merges along the producer->consumer graph, all up front. We build this planner into Nerveplane and evaluate it with NP-Bench, an environment-grounded three-arm benchmark (no coordination; reactive detection; proactive planning) that verifies integration off a real git merge, both in a deterministic simulation and with live agents. The planner lifts clean-integration from 1/9 to 9/9 scenarios and cuts merge conflicts from 13 to 0, with a gap that grows in the number of agents. On a live breaking contract change it rescues an outcome both baselines miss on every seed: the clean-integration rate rises from 0 (no coordination and reactive detection) to 1.0 on a frontier model and 0.6 on a small one, while agents respect assigned scopes (0/5 leakage). A cross-session memory drops the repeated-mistake rate from 1.00 to 0.00 on strong and weak models alike. We also report a negative result: routing facts to agents does not rescue long-context accuracy at window-fitting scales; its value is cost and capacity, not attention. Across two capability tiers and two vendors, the benefit did not shrink as models got stronger, because it comes from how work is allocated, not model reasoning.

0.18

Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration

cs.MA cs.AIcs.LGmath.OC ·2026-10-20 ·Ivan Ilin, Peter Richtárik
theorycode/data similarity 0.62
Abstract · 59 pages, 15 figures, 28 tables. Code: https://github.com/vectozavr/local-work-global-progress

Teams of large language model (LLM) agents are increasingly applied to complex tasks, but their collaboration protocols are mostly designed empirically, without convergence guarantees. We formalize collaborative problem solving as block optimization: each agent improves one part of a shared solution, guided by its local objective plus a correction for how its changes affect the other parts. A coordinator checks every proposal against the global objective and merges proposals that do not interfere with each other. We prove linear convergence up to an error floor that vanishes when the corrections are exact. Interfering proposals can also be merged once their combination has been checked; the rate then depends on how well the proposals actually combine, not on worst-case interactions. With GPT-OSS-120B agents on robot routing, a three-agent team finds collision-free plans in every run, better than those of a single agent that controls all robots. On a larger routing task, a six-agent team completes its search about twice as fast as the single agent (in median). Merging the best checked combination of proposals, rather than only proposals that do not interfere, cuts the team's search time by about 30%. With constants measured on the runs, our convergence bound holds in every round and follows the observed progress. We also test the theory on query planning in SQLite and on a synthetic task.

0.59

Dynamic Conflict Clustering with Lightweight Learning and Strategic Repair for Distributed Constraint Satisfaction

cs.MA cs.AIcs.DM ·2026-10-11 ·Raziyeh Moghaddas, Fabio Caraffini
similarity 0.59
Abstract

Distributed Constraint Satisfaction Problems (DCSPs) model distributed decision-making in multi-agent systems, where agents assign values to local variables while satisfying shared constraints. However, many DCSP solvers still rely on broad, repeated peer-to-peer communication and are largely reactive, with limited support for strategic coordination or learning. This increases communication overhead, can lead to stagnation, and reduces the success of hard instances. Hence, we propose Dynamic Conflict Clustering-Incomplete (DCC-Incomplete), a repair-based solver that combines conflict-centred decomposition, structured coordination, strategic repair, and lightweight learning for stagnation recovery. DCC-Incomplete groups the unsolved part of the problem into conflict clusters and restricts communication via a coordination layer to agents within the same conflict region. It also introduces memory-guided restart, enabling agents and clusters to pause, revise, and adapt repairs based on neighbouring conflict states. A thorough evaluation of DCC-Incomplete on distributed graph-colouring benchmarks with planted satisfying assignments shows that its memory-guided restart improves the success rate from 37.50% to 61.11%, reduces median runtime from 0.565s to 0.367s, and cuts median communication from 12.493 to 6.503 messages per constraint. These results suggest that dynamic conflict clustering, combined with lightweight strategic and learning-guided repair, improves both communication efficiency and robustness in incomplete DCSP solving.

0.22

From Recursion to Convolution: Parallel Self-Improvement for Multi-Agent Systems

cs.AI cs.CLcs.LG ·2026-11-16 ·Zheng Wang, Yuang Liu, Sachith Abeywickrama, Yangkai Ding, Tao Yu +5 more
code/data similarity 0.58
Abstract

Multi-agent self-improvement enables agents to improve through interaction and feedback. However, sequential dependencies across agents and refinement rounds can propagate errors, increase computational costs, and limit parallelism. Moreover, refining individual features or agents in isolation can overlook their dependencies and restrict collective coordination. To address these challenges, we propose ConvRSI, a framework for parallelizing multi-agent self-improvement through convolution. ConvRSI couples intra-agent convolution, which jointly refines related agent features, with inter-agent graph convolution, which aggregates messages according to the collaboration topology. Both stages operate in latent space, enabling parallel updates without repeatedly decoding and re-encoding intermediate messages. Experiments on MATH-500 show that ConvRSI achieves 5.04% performance improvement while reducing 17.27% inference cost, and 45.11% latency compared with RecursiveMAS. It also supports diverse collaboration patterns by representing their topologies as adjacency matrices. These results demonstrate the potential of convolutional co-evolution for efficient multi-agent self-improvement. Our code and datasets are provided in https://github.com/LYA2333/ConvRSI.

0.27

What You Earn from What You Learn: Characterization and Complexity of the Value of Information

cs.GT ·2026-10-14 ·Ratip Emin Berker, Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Tuomas Sandholm +1 more
publishedtheory similarity 0.58
Abstract · 40 pages, 7 figures, main body to be published in Proceedings of the Twenty-second Conference on Web and Internet Economics (WINE-26), Hong …

We examine the value of information in extensive-form decision problems: the largest multiplicative gain that a decision maker can obtain from an information refinement, taken over all payoff environments. This measures the structural importance of information disentangled from any particular payoff specification, and generalizes the notion of value of recall recently introduced by Berker et al. (AAAI'25). We establish a unifying characterization of the value of information under any information refinement, uncovering an intriguing connection to the maximum fractional chromatic number over a certain family of conflict graphs. We then employ our characterization to elucidate the complexity of two central information refinements. First, for the value of perfect information in perfect-recall decision problems, we find that the relevant conflict graphs are cographs, so the fractional chromatic number collapses to the clique number. Even though the clique number is tractable for a given cograph, we show that the additional layer of optimization (over the family of graphs) makes computing the value of perfect information NP-complete. On the positive side, we prove fixed-parameter tractability in terms of the degree of imperfect information. Second, for the value of recall in imperfect-recall decision problems (with no absentmindedness), we first show that the value of recall can realize the fractional chromatic number of any graph. Interestingly, this implies that, unlike the value of perfect information, the value of recall can take fractional values. Building on this reduction, we then establish S2P-completeness. This addresses questions left open by Berker et al. (AAAI'25)---both on the characterization and the complexity of the value of recall---and shows that computing the value of recall is strictly harder than the value of perfect information.

0.64

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

cs.AI cs.DCcs.DS ·2026-09-07 ·David A. Bader, Adil Chhabra, Ernestine Großmann, Monika Henzinger, Alexander Noe +1 more
benchmarkcode/data similarity 0.56
Abstract

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.

0.27

From Agents to Edges: Paired Optimization for Multi-Agent Collaboration

cs.CL ·2026-10-13 ·Feng Lin, Xiaotian Yu, Yifan Yang, Aijun Li
similarity 0.55
Abstract · 9 main pages, 14 appendix pages

Strong individual agents do not guarantee effective collaboration. Communication must align what one agent conveys with how another interprets and uses it. This dependency makes the communication edge a natural unit of optimization. We introduce Paired Automated Communication Optimization (PACO), which jointly optimizes the instructions at both ends of each edge and their shared communication convention in systems built on black-box language models. PACO keeps model weights, agent roles, and workflow topology fixed. A state-aware discounted bandit selects edges for refinement, while execution feedback guides paired revisions evaluated through staged end-to-end execution. The optimized instructions integrate into existing agent prompts without additional model calls at deployment. On a four-agent workflow evaluated across diverse multi-agent benchmarks, PACO consistently outperforms leading prompt-optimization and communication baselines. Configurations learned on HotpotQA retain their advantage in cross-dataset transfer without target-specific optimization. These results demonstrate that optimizing how agents communicate can substantially improve collaboration within an otherwise fixed system.

0.23

OpenMAS-GCom. A Diagnostic Benchmark for Graph-enhanced Multi-Agent Systems

cs.LG ·2026-09-18 ·Kairui Yang, Xunkai Li, Kaixiang Zhang, Minghao An, Zekai Chen +2 more
benchmark similarity 0.55
Abstract

Graph-enhanced multi-agent systems (G-MAS) coordinate large language model agents through communication graphs and role assignments, which determine how agents exchange information and divide responsibilities. However, final-score comparisons across systems combine differences in models, communication patterns, roles, and computation costs, making performance differences difficult to attribute to specific communication structures, role assignments, and information flows. To address this evaluation attribution problem, we introduce OpenMAS-GCom, a benchmark for diagnosing how these components affect G-MAS performance through controlled interventions. We represent systems through collaboration units, communication links, shared intermediate information, and execution rules. OpenMAS-GCom compares original systems with versions modified by changing one component while keeping tasks, models, prompts, and budget limits fixed. We rewire communication edges, remove specialist or critic agents, replace intermediate messages with incorrect content, and disable workers during execution. The benchmark evaluates 17 single-agent, ordinary multi-agent, and graph-enhanced configurations on 29 datasets across six domains. We add 400 G-MAS-Complex tasks requiring agents to combine information from multiple documents, resolve conflicting records, and return specified values with source identifiers. Experiments show larger mean losses after specialist removal than after critic removal, different performance degradation under incorrect messages and worker failures despite similar original scores, and different configurations achieving the highest accuracy and accuracy per token on G-MAS-Complex.

0.15