PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel AI Agent Collaboration as Graph-Structured Distributed Block Optimization

Hanmin Li, Yury Demidovich, Peter Richtárik

arXiv:2610.30074v1cs.MAcs.AImath.OC

TL;DR

Parallel agents can make useful local edits that interfere when combined, creating a coordination problem for shared solutions. The paper models integration with verified gains and a dependency graph, using fractional coloring to guarantee retained improvement. It also establishes tightness of the subset-based bound and describes experimental effects on repair, road-network, and route-search tasks.

  • Problem

    Parallel edits can improve components individually yet interfere when combined, so the challenge is deciding which verified local edits can be safely integrated.

    Source: §1 · p. 1

  • Method

    The coordinator verifies proposals against a common artifact and uses dependency-certified independent sets, with fractional coloring to select compatible edits.

    Source: §1 · p. 1, §2 · p. 3, §3 · p. 3

  • Results

    An optimal fractional coloring guarantees retention of at least 1/χ_f(G) of total verified singleton gain, and the subset-based bound is tight; experiments report conflict resolution and faster parallel execution in specified settings.

    Source: §1 · p. 2, §7 · p. 10

  • Takeaways & Limitations

    Compatibility in the shared artifact’s dependency structure links integration quality and parallel scheduling, with observed benefits and costs varying by task and setting.

    Source: §7 · p. 10

    The route-search comparison depends on route-pair locks held throughout search chunks and does not cover immutable snapshots with parallel searches and serialized commits.

    Source: §6.7 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

Parallel agents can improve separate components yet create conflicts when their edits are combined. The paper frames safe integration of these verified local edits as a coordination problem and gives a tight worst-case retention result.

1 Introduction

  • Edits to different modules can conflict: pricing and checkout can each apply a discount correctly alone but apply it twice together.This example shows why local improvement does not itself establish compatibility.Source: §1 · p. 1
  • A coordinator must decide which independently useful edits can be safely integrated, because their value can change when combined.Agents propose edits concurrently from the same artifact; a dependency certificate helps determine which proposals to combine.Source: §1 · p. 1
  • The paper formulates verified proposal integration for black-box edits and gives a tight worst-case bound for integrating fixed proposals.The coordinator observes verified singleton gains and a dependency certificate identifying subsets whose gains add exactly.Source: §1 · pp. 1–2
  • The paper distinguishes integrating submitted edits from distributed search over solution choices, which is the focus of DCOP.In this setting, agents have already generated candidate edits; the coordinator decides which proposals to combine.Source: §1 · p. 2
  • The dependency graph concerns interactions among shared-artifact components, unlike agent collaboration graphs that represent communication or agent structure.The graph identifies subsets of proposed edits whose verified gains add exactly and supports their certified integration.Source: §1 · p. 2

2 Problem Formulation

The formulation treats a shared artifact as blocks evaluated by a known loss, with a dependency graph recording which blocks can affect the same objective factor. Agents propose block replacements that are verified individually against a common base before integration.

2 Problem Formulation

  • The objective may couple blocks through factors, so the loss need not separate across components.Each factor depends only on a known subset of blocks, inducing edges between blocks that share a factor.Source: §2 · p. 2
  • Figure 2’s example has a joint pricing-checkout discount factor and a receipt-only factor, so pricing and receipt can share a color but checkout cannot.The graph therefore contains only the pricing-checkout edge.Source: Figure 2 · p. 3, §2 · p. 3
  • An independent set contains blocks that do not share an objective factor, so edits to those blocks are compatible and their gains add exactly.The dependency graph has an edge when some objective factor depends on both blocks.Source: §2 · pp. 2–3
  • A dependency certificate conservatively encodes factor scopes: extra edges may weaken guarantees, while omitting a true dependency can misclassify interacting edits as compatible.The graph represents shared dependence in the objective, not physical overlap between edited components.Source: §2 · p. 3
  • Each assigned agent proposes a replacement for one block, and the evaluator retains it only if it is valid, timely, and reduces loss against the same base artifact.This separate evaluation is singleton verification.Source: §2 · p. 3

3 Verified Proposal Integration

Verified proposal integration uses a dependency graph to certify compatible edits and a fractional coloring to guarantee retained local improvement. The method can also evaluate the full proposal union, while the subset-based guarantee is worst-case tight.

3 Verified Proposal Integration

  • In the running example, all three proposals have singleton gains 2, 2, and 1, but applying blocks 1 and 3 reaches loss 0 while the full union reaches loss 2.This demonstrates that evaluating an improving full union can miss a better compatible subset.Source: §3 · p. 3
  • A feasible fractional coloring yields a certified merger retaining at least 1/Λ of total verified singleton gain, and an optimal coloring gives 1/χ_f(G).The guarantee holds for every realized collection of proposals under the dependency assumption.Source: §3 · pp. 3–4
  • The 1/χ_f(G) retention bound is tight for any finite dependency graph among coordinators that select a subset of submitted proposals.The worst-case ratio can approach the bound even when all singleton gains are strictly positive.Source: §3 · p. 4
  • Ordinary coloring is a practical restriction of the fractional rule; for separable loss, all retained proposals can be merged and the guarantee retains their full gain sum.A maximum-weight independent set may improve a round’s candidate but must be resolved as gains change; greedy coloring guarantees 1/κ.Source: §3 · p. 4
  • Independent-set integration avoids harmful interactions but can miss beneficial ones; interaction surplus measures joint gain beyond the sum of singleton gains.A positive surplus means the joint gain exceeds that sum; independent sets have zero surplus.Source: §3 · p. 4
  • Optimistic integration compares the safe candidate with the full union and preserves the safe rule’s per-round guarantee while allowing a better union to be selected.The extra evaluation and accepted artifact can affect the subsequent trajectory.Source: §3 · p. 5

4 Global Convergence from Local Progress

The paper derives geometric convergence from verified local improvements by combining agent quality, assignment coverage, task structure, and proposal integration. The guarantee requires both conditional local-improvement bounds and a block error bound.

4 Global Convergence from Local Progress

  • Conditional local-improvement bounds require each assigned agent to recover a guaranteed expected fraction of the best available single-block improvement.The bound is conditioned on the history and full assignment, so agent outputs may be arbitrarily correlated; timeouts and imperfect edits are reflected in it.Source: §4 · p. 5
  • A positive block error bound requires available single-block improvements to capture a nonzero fraction of the remaining global objective gap.Without this condition, a state can have no individually improving block even when a joint update improves the objective.Source: §4 · p. 5
  • Assignment coverage measures the worst-case guaranteed improvement across blocks under the assignment distribution, combining assignment probabilities with local-solver quality.If coverage a is zero, the bounds cannot certify positive worst-case progress.Source: §4 · p. 6
  • The convergence rate combines assignment coverage a, block error bound μ, and integration retention 1/Λ(λ) into θλ = μa/Λ(λ).An optimal fractional coloring gives Λ(λ) = χf(G).Source: §4 · p. 6
  • Under the stated assumptions, expected objective gap contracts geometrically by at least θλ = μa/χf(G) per round with optimal fractional coloring.The rate holds in expectation across protocol randomness; it does not require every round to achieve the same reduction.Source: §4 · p. 6

5 Work and Cost Allocation

The paper allocates agents by optimizing weakest-block coverage subject to an expected token budget. It makes the trade-offs between per-round progress, duration, token cost, and integration evaluation explicit.

5 Work and Cost Allocation

  • For a fixed deadline and token budget, a linear program chooses the assignment distribution to maximize the weakest block coverage.Its coverage constraints require every block's coverage to be at least a, while the budget limits expected token cost.Source: §5 · p. 6
  • Evaluating the full union adds per-round cost but may reduce the number of rounds when that union yields greater progress.The time and token bounds account for the additional full-union evaluation cost.Source: §5 · p. 6
  • For a target expected error, the convergence bound gives sufficient rounds and corresponding elapsed-time and expected token-cost bounds.The bound assumes positive assignment coverage and a target error below the initial objective gap.Source: §5 · pp. 6–7
  • A longer deadline can improve agent capability and coverage while increasing each round's duration and token cost.Candidate deadlines can be compared using the resulting total-time bound and token-cost constraint.Source: §5 · p. 7

6 Experiments

Experiments test verified integration across code repair, scaling, graph coloring, road networks, timetabling, and route-search scheduling. The results show that compatible verified edits can avoid conflicts and retain improvement, while parallel execution trades higher resource use or setting-specific costs for reduced completion time.

6.1 Repairing conflicting edits

  • Both verified rules solve all 28 repair runs; MA solves none of the 11 conflict runs, while MAG recovers only one conflict.All 108 audited color merges satisfy additivity; under MA, agents repeatedly add or remove the same transformation in one example.Source: §6.1 · p. 7, Table 1 · p. 7

6.2 Scaling compatible parallel work

  • At 32 modules, OPT reduces modeled completion time from 15.3 minutes for SGL to 4.1 minutes when verification latency is zero, using 2.02× the input cost.With verification latencies of 60 and 300 seconds, the corresponding speedups decrease from 3.69× to 2.42× and 1.32×.Source: §6.2 · pp. 7–8, Table 2 · p. 8

6.3 Comparing ordinary and fractional coloring

  • On identical proposal sets, FRAC5 never retains less verified gain than COL3 and improves on it in four of twelve units, raising mean retained fraction from 0.5615 to 0.6167.The full union gains more than the sum of verified singleton gains in all twelve units, so optimistic integration selects the union throughout this benchmark.Source: Figure 3 · p. 8, §6.3 · p. 8

6.4 Repairing held-out tasks over multiple rounds

  • FOPT reduces mean failed checks from 34.38 to 6.29, compared with 20.02 for MA, and has lower final loss on every task–replicate unit and design mean.The first-round fractional candidate has lower loss than the full union on 47 of 48 units; none of the six parallel rules fully solves a task within three rounds.Source: §6.4 · p. 8, Figure 4 · p. 9

6.5 Integrating proposals on road networks

  • 922 of 1,617 verified singleton-gain units (57.0%) are retained by FRAC, versus 799 (49.4%) by fixed COL, a 15.4% relative increase.FRAC and adaptive ordinary coloring tie at 922; unguarded full union worsens the objective in 31 runs despite individually improving proposals.Source: §6.5 · pp. 8–9, Table 3 · p. 9

6.6 Integrating proposals in course timetabling

  • FRAC retains 10% more improvement than fixed COL on nine timetabling instances, winning on two and tying on seven; adaptive ordinary coloring matches FRAC.All 45 compatible-pair merges pass exact additivity, and selected compatible updates pass the official validator; MA creates a room conflict on comp13.Source: Table 4 · p. 9, §6.6 · p. 9

6.7 Scheduling parallel route searches

  • Fractional scheduling reduces measured wall time by a median 15.00% across twelve pairs, while route cost is better in four, tied in five, and worse in three.Summed agent CPU time is nearly unchanged, with a fractional/integral median ratio of 1.008; all 24 final route sets meet capacity and customer-coverage constraints.Source: Table 5 · p. 9, §6.7 · p. 9

7 Conclusion

The paper frames parallel collaboration as verified proposal integration: dependency-aware merging retains compatible gains, captures favorable interactions, and converges geometrically under stated assumptions. Experiments show compatibility shapes both repair quality and parallel-work costs.

7 Conclusion

  • Fractional coloring gives a tight 1/χ_f(G) worst-case retention guarantee; evaluating the full union can also capture favorable interactions.Under local-improvement and block error-bound assumptions, repeated integration converges geometrically, with a rate separating task structure, agent allocation, and integration.Source: §7 · p. 10
  • Experiments connect compatibility to repair quality and cost: verified merging resolves conflicts, while parallel work can reduce modeled completion time at higher input cost.Fractional scheduling shortened measured route-search time under exclusive route access.Source: §7 · p. 10

Appendix

  • The appendix reports experimental protocols and detailed results, controlled allocation and merging examples, and the convergence proof.Source: Appendix · p. 12

AI use statement

  • The authors report using ChatGPT/Codex and Claude for discussion, implementation, literature checks, and editing, then reviewing AI-assisted content and validating proofs, citations, and results.Source: AI use statement · p. 12

A Repair benchmark and evaluation protocols

The repair benchmark tests whether dependency-aware merging resolves conflicts and how its coordination costs compare with other repair protocols. It uses modular Python tasks, common-base proposals, explicit merge rules, and measured input-cost and modeled-time accounting.

Benchmark construction

  • The seven three-module tasks have path dependencies; six allow either adjacent module to implement a transformation, but applying it twice causes an error.Tasks contain 26–35 checks and 9–49 faulty editable lines; unit checks involve one module and integration checks involve adjacent modules.Source: Table 6 · p. 12, A Repair benchmark and evaluation… · p. 12

Agent assignments and information

  • Haiku runs use three replicates per task and Sonnet one; parallel agents receive the same program, edit only assigned modules, and cannot see one another’s changes.Agents can run visible checks, while the coordinator uses visible and hidden checks for acceptance and stops when all checks pass.Source: A Repair benchmark and evaluation… · p. 12

Repair schedules and merge decisions

  • The protocols cap repair at four whole-program sessions, two sequential module passes, or three parallel rounds, with edits accepted only when they reduce failed checks.MA applies the proposal union; MAG gates that union; COL selects the best compatible color class; OPT can instead choose a better evaluated union.Source: A Repair benchmark and evaluation… · p. 12

Proposal reuse

  • After a color-class merge, deferred verified proposals are re-evaluated against the updated program, allowing progress without requesting the same edit again.Skipping modules whose checks pass makes later work assignments depend on the current program.Source: A Repair benchmark and evaluation… · p. 12

Cost and time accounting

  • Input-token-equivalent cost weights input, cache-write, and cache-read tokens and excludes output tokens; modeled time uses the slowest parallel call plus sequential verification latency.Verification charges vary per full-objective evaluation, and the time model examines 0, 60, or 300 seconds per sequential verification step.Source: A Repair benchmark and evaluation… · p. 13

Experimental design

  • The task protocols, cost measures, and planned analyses were fixed before the main experiment; Sonnet replication was added after similar first-round Haiku behavior.Tasks, protocols, and cost accounting remained unchanged in the replication.Source: A Repair benchmark and evaluation… · p. 13

B Repair outcomes and coordination costs

Verified merging resolves diagnosed edit conflicts that defeat naive union merging, but its additional verification can cost time and budget. Favorable interactions also let full-union evaluation outperform compatible-only merging on conflict-free repairs.

Conflict outcomes

Conflict diagnosis and model dependence

  • Conflicts appeared in 9 of 18 Haiku units and 2 of 6 Sonnet units; every difference among parallel rules arose on a diagnosed conflict.All 108 audited color merges satisfied additivity exactly, while the models differed in which module owned the transformation.Source: B Repair outcomes and coordination costs · p. 13

Resolving repeated conflicts

  • On a repeated ownership conflict, MA oscillated at 21, 5, 5, 5 failures, while OPT selected one owner and reached 21, 5, 0.On T3, OPT kept a union when it improved more than the color candidate and could address remaining interference in a later round.Source: B Repair outcomes and coordination costs · p. 13

First merges and interaction surplus

  • On conflict-free units, first-round unions solved all 12 Haiku and 5 Sonnet runs, while color candidates left mean failure counts of 12.3 and 11.6.On nine conflicted Haiku units, first merges left mean failures of 5.3 for MA, 9.1 for COL, and 5.1 for OPT.Source: B Repair outcomes and coordination costs · p. 13

Sequential repair

  • Sequential acceptance can retain a locally helpful edit that doubles quoting; two Haiku failures also reached the pass cap with one hidden check still failing.Those hidden-check failures involved name trimming and total precision.Source: B Repair outcomes and coordination costs · p. 14

Task-level comparisons

  • The four task-level wins and no losses yield a two-sided sign-test p-value of 0.125; treating nine conflict units as independent would give approximately 0.004.The Sonnet replication changed which tasks produced conflicts while preserving the observed mechanism and rule ordering.Source: B Repair outcomes and coordination costs · p. 15

Resource use and matched budgets

  • At a ten-minute budget with 60-second verification latency, COL, OPT, and MA solved 17, 13, and 12 Haiku runs, respectively.At nine median-call-equivalent units with v=1, MA solved 12 of 21 Haiku units and each verified rule solved eight; small-task verified teams also used more resources than SGL.Source: B Repair outcomes and coordination costs · p. 13, Figure 6 · p. 16

C Scaling to larger repair tasks

Scaling experiments find that parallel repair can outperform compatible-only merging when edits have favorable interactions, with modeled time savings traded against input cost. On a five-cycle dependency graph, fractional coloring retained more verified gain than fixed ordinary coloring on the same proposals.

C Scaling to larger repair tasks

  • The scaling benchmark uses 4, 8, 16, or 32 modules with five bugs per module and a bipartite dependency graph whose fractional and ordinary chromatic numbers are both 2.Contracts specify ownership, and module agents are instructed to rely on other modules’ contracts.Source: C Scaling to larger repair tasks · pp. 16–17, Table 12 · p. 16
  • The union outperformed the color candidate on all 12 scaling instances, leaving zero failures except two on one 16-module instance, versus 19–156 failures for the color candidate.The positive interaction surplus ranged from 5 to 36 checks, and OPT selected the union in every instance.Source: C Scaling to larger repair tasks · p. 17
  • At zero verification latency, the modeled time crossover occurs between 4 and 8 modules; at 60 seconds, the speedup at 8 modules is 1.04.The team costs about twice as much as the single agent at every tested size, and the modeled time advantage depends on slowest-call duration and verification overhead.Source: C Scaling to larger repair tasks · pp. 17–18, Table 13 · p. 17, Figure 7 · p. 18
  • At 32 modules, the merge-on-finish team reaches 90% repaired 4.61× sooner than the single agent, or 3.61× sooner when the slowest call is included.This is an optimistic reference that merges edits as they arrive and omits verification; executed OPT waits for proposals and verifies before merging.Source: Figure 8 · p. 18, C Scaling to larger repair tasks · p. 18, Table 14 · p. 19
  • With one second per executed check at 32 modules, projected OPT speedup is 7.41× at zero verification latency and 4.92× at 60 seconds.The projection holds recorded agent behavior fixed; a fixed cost per test-runner invocation instead favors the single agent.Source: C Scaling to larger repair tasks · p. 19, Table 15 · p. 19

D Comparing ordinary and fractional coloring

  • On paired five-cycle proposals, fractional coloring matched or exceeded ordinary coloring in all 12 units and improved four, raising mean retained fraction from 0.5615 to 0.6167.Every additivity audit passed; the paired comparison uses identical proposals and distinguishes fractional from ordinary coloring.Source: D Comparing ordinary and fractional… · p. 19

E Held-out interface migrations

On held-out interface migrations, fractional integration outperformed the full union in nearly every first-round proposal set, although none of the parallel methods solved all checks within three rounds. The real-repository check passed selected public tests in two repositories, but its graph was not semantically certified and the blocks were run sequentially.

E Held-out interface migrations

  • The fractional candidate retained more gain than ordinary coloring on 30 of 48 first-round sets; final FRAC loss was lower than COL in ten units, equal in 33, and higher in five.FOPT and FRAC finished with equal loss in 47 units and FRAC was lower in one; later outcomes depend on proposals generated from each method’s repair trajectory.Source: E Held-out interface migrations · p. 20
  • FOPT left fewer failed checks than MA and MAG on all 48 held-out units, while none of the six parallel methods reached zero loss within three rounds.The first-round fractional candidate improved on the full union in 47 units; FOPT selected the union in the remaining unit, and all safe-candidate additivity audits passed.Source: Table 16 · p. 20, E Held-out interface migrations · p. 20
  • At twice FOPT’s token use, SGL-MF finished below FOPT in four units, tied in three, and above it in 41; 130 calls produced unparsable outputs.At the checkpoint matching FOPT’s token use, SGL-MF’s mean loss was 24.17 and exceeded FOPT’s in all 48 units.Source: E Held-out interface migrations · p. 20
  • Resource comparisons do not isolate method effects: calls and token budgets leave differences in context, evaluation cost, and edit permissions, and shared calls prevent measuring each method’s latency.The paper therefore compares repair quality and charged resources on this benchmark.Source: E Held-out interface migrations · p. 20

F Exploratory real-repository feasibility check

  • In two real repositories, module-restricted agents passed the selected public tests, but inferred static-import graphs were not certified against semantic interactions and sequential blocks tested no parallel-time advantage.The related test files are not whole-repository suites; the three repeats per case are not independent repository tasks.Source: F Exploratory real-repository… · pp. 20–21

G External exact-factor road-network merger

On three public road networks, fractional integration retained more verified gain than fixed ordinary coloring across 90 paired comparisons. Adaptive ordinary coloring matched FRAC, while FRAC scored five candidate pairs rather than COL’s three classes.

G External exact-factor road-network merger

  • The evaluation used 30 held-out regions across roadNet-PA, roadNet-CA, and roadNet-TX, with three initializations per region and a shared improved incumbent for all rules.The common first stage gained 8,395 cut edges across the 90 units and was charged to every method.Source: G External exact-factor road-network… · p. 21
  • Across 90 units, FRAC retained 922 verified cut-edge gains (57.0%) versus fixed COL’s 799 (49.4%), a relative difference of 15.4%.The best singleton retained 629, MAG 242, and FOPT 926; unguarded MA worsened the incumbent in 31 units.Source: G External exact-factor road-network… · p. 21
  • Adaptive ordinary coloring matched FRAC in every unit, while FRAC exceeded MAG in 84 units, lost in three, and tied in three.Adaptive coloring can place the highest-gain independent pair in a proper three-coloring after observing gains.Source: G External exact-factor road-network… · p. 21
  • FRAC scored five candidate pairs from cached singleton gains, requiring two extra score checks per unit but no additional agents or direct objective calls.The complete local run took 25.99 seconds; measured critical-path agent wall time was 14.15 seconds.Source: G External exact-factor road-network… · p. 21

H Exploratory fractional route-search schedule

Fractional preemptible route-search schedules were faster in all twelve paired runs, with a pooled median wall-time reduction of 15.00%. Final route costs varied across comparisons despite equal per-agent search budgets.

H Exploratory fractional route-search schedule

  • The five-route cycle deliberately induced a C5 conflict graph from route-pair locks, rather than estimating naturally occurring conflicts.Four public CVRPLIB/DIMACS inputs were used, with three paired repeats per input.Source: H Exploratory fractional route-search… · pp. 21–22
  • Both schedules used five agents with the same 500,000 candidate-move evaluations per agent, but fractional scheduling split each agent’s budget across two visits.The fractional schedule used five independent pairs, whereas ordinary scheduling used three fixed color classes.Source: H Exploratory fractional route-search… · p. 22
  • Fractional scheduling reduced wall time by a pooled median 15.00% across twelve paired runs, with reductions from 13.16% to 17.28%.Summed CPU-time ratios were near one, with median fractional/integral ratio 1.008; route cost improved in four pairs, tied in five, and worsened in three.Source: Table 18 · p. 22, H Exploratory fractional route-search… · p. 22

I Allocation and verified integration on controlled tasks

Controlled examples connect agent allocation, merge behavior, and convergence: optimized allocation improves worst-block coverage, while verified merging can preserve gains or exploit favorable interactions. The proof’s geometric rate depends jointly on retained local gains, conditional agent quality, and a block error bound.

I Allocation and verified integration on controlled tasks

  • At h=2, optimized allocation equalized all six coverage values at approximately 0.2211, versus uniform allocation’s 0.1585, 0.1359, and 0.0850; worst-block horizons were 19 versus 52 rounds.The corresponding modeled times were 45.6 and 124.8 time units.Source: I Allocation and verified integration… · p. 23
  • Enumeration of 64 states and 64 edit subsets verified the merge identity and expected-drift bound; the union beat the best color candidate in 1,369 of 4,096 state/subset pairs and tied in 2,727.Optimistic integration satisfied the merge bound throughout.Source: I Allocation and verified integration… · p. 23
  • On the complete-graph instance, the best subset retained one gain out of total singleton gain m, attaining the 1/m factor; optimistic integration rejected the worsening union for m≥3.Applying all r proposals gives gain r(2-r).Source: I Allocation and verified integration… · p. 23
  • In the three-agent pilot, the best color class gained 11 against the union’s 23, and re-evaluating the stored middle-block proposal after that merge completed repair.Optimistic integration completed repair in one merge, but both verified policies used five objective evaluations; merge-all used two.Source: Table 20 · p. 23, I Allocation and verified integration… · pp. 23–24

J.1 Proof of Theorem 5

  • Theorem 5’s proof combines retained local gains, conditional agent-quality bounds, and a block error bound to establish geometric convergence in the objective gap.The proof notes that boundary rates can yield monotonicity only or force a zero gap after one round.Source: §J.1 · p. 24

K Extended related work

  • Extended related work covers graph coloring, agent interaction and orchestration, distributed optimization and training, and convergence of corrected local search with verified merging.The cited work includes Ilin and Richtárik [25] on convergence of corrected local search with verified merging.Source: K Extended related work · p. 24

Related papers

Loading 2610.30074v1…