TL;DR

What I did: built a controlled experiment that isolates one variable, relationship density, from everything usually confounded with it, using a fully deterministic agent policy instead of live model calls.

What I found: more communication pathways between agents did not automatically mean better multi-agent performance. Recovery stayed flat across the whole density sweep. But the pathways themselves didn’t stay flat — as density rose, the network used a shrinking fraction of the edges it had. The more useful engineering question isn’t simply how many connections exist. It’s how many of them actually carry information.

This is not just a conceptual proposal. It is a working system with measurable, reproducible behavior. The experiment is reproducible; timing numbers are reported only where actually measured.

The Assumption I Went In With

Most people assume a failing multi-agent system has a prompt problem.

You build a team of specialized agents, hook them up in a loose mesh, and run the pipeline. Instead of a finished result, you get endless loops, context drift, and a burnt-through token budget. The immediate knee-jerk reaction is to rewrite the system prompts or swap in a larger LLM.

I suspected the real culprit was structural: the actual ratio of open communication channels between agents versus the total channels possible.

In graph theory, that ratio is relationship density. For a directed graph with N nodes and E edges:

D = E / (N * (N - 1))Take an 8-agent setup: you have 56 possible directed communication paths. Density is simply the dial that controls how many of those 56 paths are actually open. I wanted to see if adjusting that single structural lever fundamentally changes how a network performs and whether more connectivity is actually better.

A quick note on the setup: all the data below comes straight from real benchmark runs executing locally (Python 3.12, CPU-only, zero external API calls), unless explicitly noted as a design-phase calculation.

Who This Is For

This experiment design is worth adapting if you are currently picking multi-agent topologies by gut feeling: defaulting to a fully connected mesh because it feels safer, or building a linear chain because it is easy to trace. It is also a solid template if you need to run controlled, reproducible experiments on agent architectures without blowing through your API budget on every iteration.

When to skip this:

  • If you just want a single magic density number to drop into production:The metrics here are tied to one specific task, one topology family, an 8-agent layout, and a deterministic messaging policy. They will not copy-paste cleanly into your codebase, and I am not claiming these exact thresholds hold for stochastic LLM runs.
  • If your bottleneck is individual model performance:If a single agent is failing at basic task execution, structural routing adjustments will not save it.
  • If your research requires true model non-determinism:This setup intentionally trades away LLM stochasticity to guarantee exact reproducibility across runs.

The complete code and the pre-specified test protocol are available in the repository.https://github.com/Emmimal/graph-density-engine/

Building the Experiment

Most comparisons that look at network topology make a fundamental mistake: they change two variables at once. They compare a chain to a mesh to a fully connected graph, which changes both the visual shape of the network and the actual edge count at the same time. When performance shifts, there is no way to know if the driver was relationship density or the specific layout of the graph.

To isolate the real cause, this design keeps every other factor static and sweeps a single variable.

Here is the pipeline, end to end:

The test plan evaluates five distinct density levels: 20%, 40%, 60%, 80%, and 100%.

The system uses a fixed count of eight agents throughout the entire benchmark. Each density level undergoes ten independent trials, totaling fifty runs. Every run uses a unique random seed, with all seeds locked before executing the test suite.

Component 1: The Topology Generator

The network topology family is strictly locked to connected Erdős–Rényi random graphs [1]. Edges are sampled uniformly at random until reaching the target density level. Any disconnected graph samples are immediately rejected and resampled until a fully connected path exists across all nodes.

This generation process represents the only graph construction pipeline in the entire project. There are no hidden central hubs, star topologies, or hand-tuned structural rules that could quietly confuse graph shape with pure edge density.

Here is how a 20% density graph compares to a 100% density graph for the exact same 8-agent setup. Each row represents an individual agent, and each indicator highlights an active, outbound communication path to another node:

def generate_connected_erdos_renyi(num_agents, target_density, rng, max_attempts=20000): edges = all_possible_directed_edges(num_agents) target_edge_count = round(target_density * len(edges)) for _ in range(max_attempts): chosen = rng.sample(edges, target_edge_count) adjacency = build_adjacency(chosen, num_agents) if is_strongly_connected(adjacency): return adjacency raise RuntimeError("no connected graph found")

Component 2: The Agent Policy

This part sets this build apart from a standard multi-agent demo, and it is an intentional design choice rather than a shortcut.

The agents are not powered by LLM API calls. Instead, each of the eight agents follows a simple, deterministic policy: contribute whichever of your own unshared facts is least similar (using TF-IDF [2]) to what has already been stated. Once an agent has shared all its facts, it falls back to repeating whichever of its facts is most relevant to the current topic.

There is no randomness in the decision logic, no API latency, and no hidden behavior inside a model’s weights.

I chose this approach for a specific reason. My first draft used a simulator that essentially forced the outcome it was trying to discover: redundancy was injected via a coin flip linked to message depth, which guaranteed that density correlated with redundancy.

Switching to live LLM calls would have fixed that artificial behavior, but it introduces different problems. Live model calls are expensive, subject to rate limits, and non-deterministic, making the results difficult to audit or replicate cleanly. A clear, rule-based policy avoids both issues. Every decision is fully inspectable, and the entire fifty-run benchmark reproduces bit-for-bit with the same initial seeds.

def _select_message(self, remaining, own_facts, shared_facts): if remaining: return self._most_novel(remaining, shared_facts) # novelty-seeking if not own_facts: return "NO_KNOWLEDGE_AVAILABLE" return self._most_on_topic(own_facts, shared_facts) # repeat fallback

Component 3: The Diagnostics

A single top-line metric cannot tell you why density did or did not affect the outcome, so five distinct diagnostics run underneath the main execution:

| Metric | What It Measures |
|---|---|
| Relationship Efficiency | Fraction of messages that added a genuinely new fact to shared state |
| TF-IDF Redundancy | Lexical similarity of each new message to what’s already been said |
| Information Gain | Novel facts contributed / total facts contributed |
| Edge Utilization | Actually-used edges / configured edges at a given density |
| Communication Depth | Total messages elapsed |

Edge Utilization turns out to be where the flat recovery curve gets interesting. It is the single diagnostic that separates how many pathways exist from how many pathways actually carry a message.

What I Did

To recap the setup before looking at the results: eight agents, each holding a small, non-overlapping slice of a 17-fact incident scenario. No single agent starts with the complete picture.

We test across five density levels, with 10 trials per level for a total of 50 runs. Every run gets a hard limit of a 35-message communication budget. The primary task is to measure how much of the ground-truth scenario the network manages to consolidate into its final shared state by the end of the run.

What I Got

Going into this, I expected to see an inverted U-curve: low density starves the network of connections, high density drowns it in redundant chatter, and somewhere in the middle lies a sweet spot.

That is not what happened, at least not for information recovery.

Recovery represents the fraction of the scenario’s ground-truth facts that made it into the final synthesized output. Here are the averages across 10 trials per density level:

| Density | Information Recovery | Relationship Efficiency | Redundancy |
|---|---|---|---|
| 20% | 0.959 ± 0.070 | 0.457 ± 0.034 | 0.240 ± 0.019 |
| 40% | 0.924 ± 0.083 | 0.440 ± 0.039 | 0.243 ± 0.027 |
| 60% | 0.971 ± 0.039 | 0.469 ± 0.019 | 0.240 ± 0.025 |
| 80% | 0.976 ± 0.039 | 0.471 ± 0.023 | 0.249 ± 0.019 |
| 100% | 0.959 ± 0.046 | 0.463 ± 0.021 | 0.250 ± 0.026 |

Recovery sits inside a tight band, roughly 92% to 98%, across the entire sweep. The sparsest network in the setup recovers practically as much ground truth as the fully connected graph.

The 40% condition shows the lowest average performance, landing at 0.924 mean recovery compared to 0.959–0.976 across the other four settings. That dip is worth flagging, but given the 10-trial sample size and within-condition variance, it is better treated as a candidate for further testing rather than definitive proof of a non-linear effect.

The take-away is specific: within this topology family, at this agent count, on this task, and with this deterministic communication policy, moving density from 20% to 100% did not materially alter recovery. That is a far more precise claim than saying “density never matters,” but it is what the benchmark data actually demonstrates.

Looking Underneath the Number That Didn’t Move

A flat recovery curve is not the end of the analysis. It is where the focus shifts from “did density change the outcome” to “why didn’t it, and what changed instead?”

Relationship Efficiency holds steady between 0.44 and 0.47 across every density level, showing no clear trend. Agents waste roughly the same proportion of their turns regardless of how many communication paths are open. Redundancy stays flat as well, remaining between 0.24 and 0.25 across all conditions. Contrary to my initial assumption, opening up more pathways did not lead to an increase in repeated chatter.

Edge Utilization is where the underlying mechanics become clear. Averaged across all 50 trials, here is how configured edges compare against the edges the network actually used:

| Density | Configured edges | Avg. used edges | Avg. utilization |
|---|---|---|---|
| 20% | 11 | 10.7 | 97.3% ± 6.1% |
| 40% | 22 | 15.8 | 71.8% ± 11.1% |
| 60% | 34 | 21.3 | 62.6% ± 5.4% |
| 80% | 45 | 24.8 | 55.1% ± 7.1% |
| 100% | 56 | 26.4 | 47.1% ± 4.6% |

That is a clean, monotonic drop.

At 20% density, the network uses almost every edge it is given. It operates close to its structural capacity, with barely any slack. At 100% density, it uses under half of what is configured, on average. In these runs, the fully connected network used about 47% of its configured edges. Not zero, and not “never carried a single message.” Just a steadily shrinking fraction as more edges were added.

The absolute number of edges in active use still climbs as density rises (roughly 11 edges at 20% density up to 26 edges at 100%), so those extra edges are not completely inert. However, they get used at a sharply diminishing rate relative to how many you add. Doubling the edge budget from 60% to 100% density nearly doubles the configured edges from 34 to 56, but adds only about 5 more active edges in practice (moving from 21.3 to 26.4).

That is the exact distinction the flat recovery curve was hiding: configured connectivity and behavioral connectivity are not the same thing, and they diverge further as the graph grows denser.

Performance Characteristics

Measured on a fifty-trial full sweep with zero API calls and zero cost:

| Operation | Cost / Execution Time |
| Phase 0:Metric unit tests (16 tests) | under 0.25 seconds |
| Phase 1:Graph engine validation, 50 runs, DummyAgent | under 1 second |
| Phase 2:The real experiment, 50 runs, PureAgent | Not separately benchmarked |
| API cost for the full experiment | $0 |

I have not separately benchmarked wall-clock time for Phase 2 or verified cross-platform reproducibility across different operating systems. What I can confirm is that the suite is fully deterministic given a fixed seed (Phase 0’s test suite explicitly verifies this), and every trial ran to completion without timeouts.

If you clone the repository and run the benchmark suite yourself, I would be interested to hear what timing and behavior you observe on your machine.

Honest Design Decisions

1. The Deterministic Agent Policy

The rule-based agent policy is a deliberate trade-off, not a free win. It gives us total reproducibility and zero API costs, but it means these results reflect how a fixed, rational routing strategy behaves under varying network topologies, rather than how a stochastic LLM population would. A model with less predictable output might interact with density quite differently, and I would not assume these exact numbers transfer directly to LLM calls without explicit testing.

2. Standard Library Keyword Matching

The Information Recovery metric uses keyword-overlap matching instead of semantic embedding similarity, keeping with the standard-library-only design. Early in development, this heuristic was miscalibrated: a threshold of 0.6 allowed facts from the same incident to cross-credit each other through shared entity tokens like service names or timestamps. As a result, sharing a single real fact could spuriously “recover” two or three unrelated ones. Raising the threshold to 0.85 after tracing the bug fixed the issue, ensuring exact recovery matching.

3. Removing Circular Early Exits

A more fundamental flaw surfaced during initial protocol design. The original stopping rule was set to “exit once recovery crosses 70%,” which made recovery both the termination condition and the output metric. That logic was circular: every trial result was mechanically pinned to whichever fact count hit the threshold first, making it structurally impossible to detect a density effect regardless of the true underlying dynamics. The fix was simple: remove the early exit entirely. Every trial now runs the full communication budget, and recovery is evaluated once at the very end.

4. Budget Size and Ceiling Effects

The 35-message limit proved quite generous for a 17-fact scenario, creating a ceiling effect. Most runs recovered the vast majority of facts well before exhausting their budget, which compressed the room available for density to show a clear impact.

To test whether this budget buffer was masking a real effect, I ran a smaller, pre-specified follow-up using a much tighter message budget. The results were suggestive rather than conclusive: the same drop at 40% density reappeared, and a paired comparison hinted that mid-density networks might lose more ground under severe message constraints than either very sparse or very dense ones. That is a distinct pattern worth exploring in a dedicated experiment, so I am flagging it here rather than claiming it as a proven rule.

5. Dependency Footprint

The core simulation runs purely on the Python standard library, requiring no external packages for the graph engine, agent logic, or diagnostic metrics. The project repository lists pytest only to run the 16-test validation suite, which is a testing utility rather than a runtime requirement for the experiment itself.

Trade-Offs and What Is Missing

Real Model Agents

The Agent interface was explicitly designed to be modular. The graph engine, message router, and diagnostic metrics are entirely agent-agnostic. Dropping a real LLM into that interface—trading away zero-cost reproducibility for stochastic behavior—would prove whether these exact structural patterns hold up when models introduce non-determinism and reasoning noise.

Richer Scenarios

The dataset corpus currently rotates three core incident templates across ten scenario files. A publication-grade iteration needs ten fully distinct scenarios, or at least a clear disclaimer that template rotation limits semantic variety.

A pre-specified Scarcity Study

The tight-budget follow-up pointed to an intriguing pattern, but it remains unconfirmed. Doing this justice means pre-registering a dedicated test suite with the scarcity-sensitivity hypothesis locked in before running the benchmark, rather than noting it after looking at the runs.

Weighted and Frequency-Based Density

Right now, density measures static graph geometry. A future version that weights edges by actual message frequency—rather than mere existence—would bridge the gap to Edge Utilization, which already proves that configured connectivity and realized traffic diverge rapidly as networks grow denser.

Closing

Within this experiment—this topology family, this agent count, this task, and this deterministic policy—graphs did not improve just because they had more edges, nor did they degrade. What dictated performance was not the sheer volume of open communication pathways, but how many of those pathways the network actually required. That operational core remained remarkably stable, even as the graph was given far more structural capacity to expand.

I originally expected this benchmark to tell a clean, dramatic story about dense networks collapsing under their own communication overhead. Instead, it delivered something quieter and far more practical: a clear reminder that a graph’s configured edge count is not the same thing as its actual behavior, and the only way to spot the difference is to instrument the system and measure it directly. https://github.com/Emmimal/graph-density-engine/

References

[1] Erdos, P., & Renyi, A. (1959). On Random Graphs I. Publicationes Mathematicae Debrecen, 6, 290-297.

[2] Salton, G., & Buckley, C. (1988). Term-weighting approaches in automatic text retrieval. Information Processing & Management, 24(5), 513-523.

Disclosure

All code in this article was written by me and is original work, developed and tested on Python 3.12. Benchmark numbers are from actual runs of the system, zero API calls, and are reproducible by cloning the repository and running the included test suite and experiment scripts, except where explicitly noted as protocol-design calculations. The simulation itself uses no external library beyond the Python standard library; the test suite uses pytest. All images and figures in this article, including the featured image and every diagram, were created by me. The featured image was generated with ChatGPT (DALL·E); the diagrams (system pipeline, adjacency matrices, decision tree, edge-utilization chart) were built directly from the experiment’s own data and design. I have no financial relationship with any tool, library, or company mentioned in this article.