Exercises — Multi-agent collaboration

(a) Parallel with Aggregation — same problem, independent solves, then a vote. (b) Sequential Pipeline — output of one is the input of the next. (c) Manager-Worker (Dynamic Coordination) — one delegates, others execute, plan adapts. (d) Debate / Adversarial — opposing positions, then synthesis. (e) Peer-to-peer Negotiation — direct talk, no central authority.

Statement 2. An ensemble (Ensemble-methods) averages/votes over model outputs with no communication between models. Agents exchange messages ($M$) and can change what they do based on what a peer said. Speed (statement 1) is not the defining line.

What we do: plug into ${\text{Cost}}_{\text{multi}}={\sum }_i\text{Cost}(A_i)+\text{Cost}(M)$. ${\text{Cost}}_{\text{multi}}=(20+25+15)+12=60+12=72.$ Compare: $72<90$, so multi-agent is cheaper. Why it works here: the specialisation gain is $90-60=30$, which comfortably exceeds the $12$ of communication overhead.

Read the figure: the tall grey bar on the left is the single agent (90). The three blue bars are the specialists; the orange bar is messaging. Their stacked total sits at the green dashed line (72), visibly below the grey bar. The picture makes the inequality "sum of blues + orange < grey" literal: multi-agent wins exactly when the blue+orange stack ends below the grey top.

${\text{Cost}}_{\text{multi}}=60+35=95.$ Now $95>90$: multi-agent is worse. The specialisation gain is still $30$, but it is eaten by $35$ of communication overhead ($35>30$). This is exactly condition 3 in the parent note — "communication overhead must not dominate."

Parallel time uses ${\text{Time}}_{\text{multi}}\approx {\max }_i\text{Time}(A_i)+\text{Time}(M)$: ${\text{Time}}_{\text{multi}}=\max (8,10,6)+3=10+3=13\text{ min}.$ Why $\max$, not sum? In parallel everyone runs at once, so you wait only for the slowest one (the bottleneck), then pay a single messaging-latency cost $\text{Time}(M)$.

What "speed-up" means and why it is a ratio. Speed-up asks: how many times faster is the new method than the old one? If the old (sequential) method takes ${\text{Time}}_{\text{seq}}$ and the new (parallel) method takes ${\text{Time}}_{\text{multi}}$, then "how many parallel runs fit into one sequential run" is the quotient $\text{Speed-up}=\frac{{\text{Time}}_{\text{seq}}}{{\text{Time}}_{\text{multi}}}.$ We divide (rather than subtract) because we want a scale factor independent of units: a $2\times$ speed-up means the same whether you measure in minutes or seconds, while a difference of "11 minutes" does not. Here: $\text{Speed-up}=\frac{24}{13}\approx 1.85\times .$ So the parallel team finishes in about $54\%$ of the sequential time.

Read the figure: the top row shows the three tasks laid end-to-end (sequential), reaching 24. The lower rows show the same three tasks stacked vertically — they overlap in time, so the clock only reaches the end of the longest (10), after which the red messaging block (3) runs. The horizontal distance to the end of the red block, 13, is the parallel wall-clock time.

Edge case — overlapping / streaming communication: the formula ${\max }_i\text{Time}(A_i)+\text{Time}(M)$ assumes messaging happens strictly after every agent finishes. Real systems often let agents stream partial results and message while still working. If messaging overlaps computation, the true time is closer to ${\max }_i\text{Time}(A_i)$ alone (the $\text{Time}(M)$ term is partly or fully hidden). So ${\max }_i\text{Time}(A_i)+\text{Time}(M)$ is an upper bound; streaming designs can beat it, and a slow synchronising barrier (everyone must wait for the last agent before any messaging) is what makes it tight.

What we do: the chain is correct only if every stage is correct. Stages are independent, so multiply: $P(\text{correct})=p^k.$ For $k=3,p=0.9$: $0.9^3=0.729$. What it means: even with 90%-reliable agents, a 3-stage pipeline is only $\approx 73\%$ reliable — reliability decays geometrically with pipeline length. This is the "error propagation" risk from the parent note, made quantitative.

Read the figure: each coloured curve is $p^k$ for a fixed per-stage reliability $p$, plotted against pipeline length $k$. Notice all curves fall, and the lower $p$ curves crash faster — doubling the pipeline length roughly squares the failure. The green dot marks our answer $(k=3,0.729)$. The takeaway you can see: long pipelines are fragile, so keep them short or harden the weakest stage.

What we do: majority-of-3 is correct if exactly 2 or all 3 are correct. $P=\left(\genfrac{}{}{0ex}{}{3}{2}\right)p^2(1-p)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)p^3.$ With $p=0.8$: $P=3(0.64)(0.2)+(0.512)=0.384+0.512=\mathrm{0.896.}$ Compare: $0.896>0.8$ — the vote is better. This is the Parallel+Aggregation robustness gain, and it's exactly the same maths as Ensemble-methods (Condorcet's jury theorem): voting helps when agents are better than a coin-flip and reasonably independent.

A defensible design: Parallel + Aggregation nested inside a Sequential Pipeline, in three numbered stages.

1. Stage 1 — Searcher: finds the 6 papers.
2. Stage 2 — Paired Readers (parallel + agreement): for each paper, run 2 Reader agents in parallel and keep their summary only if they agree (a mini agreement vote → catches hallucination).
3. Stage 3 — Synthesizer: merges the 6 agreed summaries into the final claim.

Why this combination: the parallel-agreement step in Stage 2 buys reliability (Exercise 3.2 logic) exactly where hallucination is dangerous; the pipeline gives clean stage separation and specialisation. This mirrors the parent's Worked Example 2 but hardened against single-reader bias. Related idea: a Debate stage could replace agreement in Stage 2 if you want the readers to argue rather than just vote — see Game-theory for why adversarial pressure surfaces weak claims.

What we do: start from the win condition and solve for the messaging budget. ${\text{Cost}}_{\text{multi}}<{\text{Cost}}_{\text{single}}⟹S+\text{Cost}(M)<90.$ $\boxed{\text{Cost}(M)<90-S.}$ Why this is useful: $90-S$ is exactly the specialisation gain $G$ defined at the top of the page — the effort you saved by splitting. You are allowed to spend up to that saving on communication and no more. For $S=60$: $G=30$, so $\text{Cost}(M)<30$. (Matches Ex 2.1 where $M=12<30$ won, and Ex 2.2 where $M=35>30$ lost.)

$\max$ over the utilities is $0.85$; but we don't want the value, we want the worker who achieves it. That is $\arg \max$ — "the argument (agent) that maximises." So $A_2$ is assigned. Mastery point: $\max$ answers "how good is the best?"; $\arg \max$ answers "who is the best?". The assignment function needs the who.

(a) Voted-Coder stage. Same majority-of-3 form as Exercise 3.2, with $p=0.9$: $P_{\text{coder}}=\left(\genfrac{}{}{0ex}{}{3}{2}\right)(0.9{)}^2(0.1)+(\genfrac{}{}{0ex}{}{3}{3})(0.9{)}^3=3(0.81)(0.1)+0.729=0.243+0.729=\mathrm{0.972.}$

(b) Whole pipeline. The four stages are independent, so multiply their success probabilities — Planner $0.95$, voted-Coder $0.972$, Tester $0.95$, Reviewer $0.95$: $P=0.95\times 0.972\times 0.95\times \mathrm{0.95.}$ Compute step by step: $0.95\times 0.972=0.9234$; then $0.9234\times 0.95=0.87723$; then $0.87723\times 0.95=0.8333685$. $P\approx \mathrm{0.83337.}$

(c) Total cost. Four base stages $=4\times 10=40$; two extra coders $=2\times 10=20$; vote messaging $=5$: $\text{Cost}=40+20+5=65.$

Mastery synthesis: we traded 25 extra cost units to lift the Coder stage from $0.95$ to $0.972$, nudging end-to-end reliability up. Whether that trade is worth it depends on the value of a correct output — exactly the cost/reliability reasoning that governs all of multi-agent design.

Multi-agent beats single when messaging cost is below the... ::: specialisation gain, $\text{Cost}(M)<\text{Cost}(A)-{\sum }_i\text{Cost}(A_i)$. Parallel wall-clock time uses which operator over agent times? ::: $\max$ (plus one messaging-latency cost $\text{Time}(M)$, as an upper bound). Pipeline reliability with $k$ stages of success $p$? ::: $p^k$ (geometric decay). The operator that returns who is best, not how good? ::: $\arg \max$.