DPBench: Structural Determinants of Multi-Agent LLM Coordination Under Simultaneous Resource Contention

TL;DR

• DPBench is a benchmark that adapts the Dining Philosophers problem into a controlled setting where the action protocol, the communication structure, the prompting strategy, and the group size each vary independently.
• Protocol moves more than model. Holding Gemini 2.5 Flash fixed, structural protocol changes drive deadlock from 90% to a 0% point estimate. The negotiation rounds and prompt are doing the work; the model weights are not.
• Cross-model spread. Under the default protocol, deadlock ranges from 25% (GPT-5.2) to 90% (Gemini 2.5 Flash). GPT-5.2 is not statistically distinguishable from the uniform-random baseline; the other four LLMs are worse than random in point estimate.
• Scope. The prompt and communication-rounds ablations were run only on Gemini 2.5 Flash; the group-size ablation is replicated on Llama 4 Maverick.

Why we built this

The same Gemini 2.5 Flash model deadlocks 90% of the time under one protocol and 0% under another. The model is identical. The protocol is not. Multi-agent LLM systems are now in production: software-engineering agents share a codebase across multiple roles, and retrieval pipelines route sub-queries through specialised LLM calls. Frameworks like LangGraph and AutoGen run multiple instances against shared state, and practitioners hit coordination bugs in production. Distributed-systems work on these failures dates back to Dijkstra. We did not benchmark LangGraph or AutoGen specifically; our claim is about the single-round-messaging default pattern they share.

The benchmark literature for multi-agent LLM systems has so far mostly measured one thing: do the agents succeed when given a particular protocol? We ask the inverse: under what protocols does coordination succeed at all?

In distributed-systems terms, the failure mode we care about is deadlock: several agents claim shared resources at once and end up in a circular wait (each agent holds one resource and waits on another, with no agent able to make progress) that does not resolve. The Dining Philosophers problem formalised the simplest setting where this shows up. The classical literature also gave sufficient conditions for deadlock freedom: per-agent asymmetric grab orders (Dijkstra's textbook "one philosopher reverses" solution) and global resource ordering, in which every agent acquires resources in a fixed global order. These are statements about the protocol, not about the agent.

DPBench adapts that classical setting into a controlled LLM benchmark. Each LLM sits at a philosopher's seat. We vary the protocol around the model (action mode, communication, group size, prompt) while holding the model fixed.

What DPBench measures

Each episode is a small game where every agent sees only its local situation, not the full global state (formally a Dec-POMDP, a decentralised partially observable Markov decision process). The agents are the philosophers. The state is who is holding which fork and who has eaten how often. The action set is the same for every agent: grab the left fork, grab the right fork, release both, wait. When a philosopher holds both adjacent forks at the end of a timestep, the meal is automatically recorded (eating is not itself an action) and the forks are released.

In simultaneous mode, all agents commit their action at the same time. When two agents try to grab the same fork in the same timestep, the lowest-indexed requester acquires the fork. In sequential mode, agents act one at a time in round-robin order and each one sees the state produced by the previous agent. Every episode runs for at most T=30 timesteps with a target meal count of M=5 meals per agent. We use provider-default temperatures, with OpenRouter slugs and snapshot dates per model listed in the released configs/models.yaml.

For each episode we compute four metrics and report mean and a 95% Wilson confidence interval across episodes (the Wilson interval is the standard choice for proportions near 0 or 1 because it does not collapse to width zero at the boundary):

• Deadlock rate. Fraction of episodes that either trigger the per-timestep deadlock predicate (every fork is held and no philosopher holds both adjacent forks) or reach the horizon T=30 without the target meal count.
• Throughput is group meals per timestep, summed across all philosophers.
• For fairness we use a Gini-style measure (one minus a normalised sum of pairwise differences) of how meals are distributed across agents; 1 is perfectly equal and 0 is fully concentrated.
• Message-action consistency: when communication is on, the fraction of stated intentions ("I will grab my left fork next") that match the action actually taken.

DPBench ships with five frontier LLMs accessed through a single OpenRouter interface (GPT-5.2, Claude Opus 4.5, Grok 4.1, Gemini 2.5 Flash, Llama 4 Maverick) plus a uniform-random baseline. The random baseline is a reference point: any LLM whose deadlock CI overlaps random is, at this sample size, indistinguishable from chance.

Cross-model behaviour under the default protocol

Under simultaneous play at N=5 with no communication and the default prompt:

Model	Deadlock rate	95% Wilson CI	n
GPT-5.2	25.0%	[11.2, 46.9]	20
Claude Opus 4.5	55.0%	[34.2, 74.2]	20
Grok 4.1	70.0%	[48.1, 85.5]	20
Llama 4 Maverick	76.7%	[59.1, 88.2]	30
Gemini 2.5 Flash	90.0%	[74.4, 96.5]	30
Random baseline	13.3%	[5.3, 29.7]	30

Cross-model deadlock under default conditions (N=5 simultaneous, no communication; n=20 for GPT-5.2/Claude/Grok, n=30 for Gemini/Llama/Random). All five LLMs sit at or above the random baseline. Under sequential action, GPT-5.2, Gemini 2.5 Flash, and Llama 4 Maverick (plus the random baseline) reach 0% deadlock; Claude Opus 4.5 (60.0%) and Grok 4.1 (25.0%) remain anomalous. We trace this to their tendency to immediately grab in single-agent turns; details and per-episode logs are in the appendix. Bars are 95% Wilson CIs.

GPT-5.2's confidence interval (25.0%, [11.2, 46.9]) overlaps the random baseline (13.3%, [5.3, 29.7]). A two-proportion z-test (two-sided, alpha=0.05) fails to reject equality at this sample size; we make this statement as a test result, not as an inference from CI overlap. The other four LLMs are clearly worse than random in point estimate. CIs overlap too much to rank the models, but all five sit at 25% deadlock or above; the random baseline is at 13.3%. Under the same default protocol, deadlock spans from 25% to 90% across models, so model identity does matter at the cross-model level; the "protocol moves deadlock more than the model does" result that follows is a within-Gemini statement.

Three protocol changes that take Gemini 2.5 Flash from 90% deadlock toward zero

We took the model that fails most under the default conditions (Gemini 2.5 Flash, 90% deadlock at the 30-episode baseline) and held it fixed. We then varied three structural elements of the protocol around it, one at a time. The prompt and multi-round communication sweeps used n=20 per condition on Gemini only; the no-comm baseline, the 1-round Gemini condition, and the N=10 group-size cells used n=30, and the group-size sweep was replicated on Llama 4 Maverick.

Two of the three changes drive deadlock to a 0% point estimate (Wilson 95% upper bound 16.1% at n=20). The third reduces it from 90% to 10% (CI [3.5, 25.6] at n=30, which excludes zero).

Three protocol variables that take Gemini 2.5 Flash from 90% deadlock toward a zero or near-zero point estimate. n=20 per condition for prompt and three/five-round comm sweeps; n=30 for the no-comm baseline, the 1-round Gemini condition, and the N=10 group-size cells. (a) Prompt: resource-ordering and symmetry-breaking eliminate deadlock; the minimal prompt without goal language reaches 100%. (b) Communication: three rounds eliminate deadlock; single-round messaging does not. (c) Group size: N=5 to N=10 reduces deadlock for both LLMs and the random baseline. Bars show Wilson 95% CIs.

Communication rounds

The default condition is no communication. Single-round communication adds one round of message exchange between agents before each commitment. Three-round and five-round conditions add three or five rounds. Messages are broadcast to all philosophers and are capped at 256 tokens per turn.

Single-round messaging produces a 3.3-point drop, from 90.0% [74.4, 96.5] at zero rounds (n=30) to 86.7% [70.3, 94.7] at one round (n=30), with overlapping CIs. Giving a multi-agent system a single message before each commitment is, by this measurement, not enough.

Three rounds drive deadlock to a 0% point estimate (Wilson 95% upper bound 16.1% at n=20). Five rounds yields a 5% point estimate (Wilson CI [0.9, 23.6]); we cannot statistically detect an improvement beyond three rounds at n=20. By three rounds the deadlock rate is at zero; at one round it is unchanged from baseline.

We checked one trivial explanation. Message-action consistency at three rounds is 76.2%, so when an agent says "I will grab my left fork next," it actually does so about three times out of four. The agents are using the channel and they mostly follow through.

One round does not give the agents enough back-and-forth to converge on an asymmetric assignment of intentions; three rounds do. We do not claim this round-count threshold generalises beyond DPBench. This is consistent with a well-established result in the MARL emergent-communication literature: communication channels help coordination only when there is something non-trivial to resolve.

Prompt strategy

We tested five prompt variants of equivalent length and tone but different content. The default prompt states the goal in neutral terms. The minimal prompt strips the goal description, so the agent is told what the actions are but not asked to make progress. The theory-of-mind prompt adds an instruction to reason about what the other philosophers will do. The symmetry-breaking prompt asks the agent to randomise its commitment timing rather than grabbing immediately. The resource-ordering prompt encodes a parity-based grab order on the philosopher index (even-indexed philosophers grab right first, odd-indexed grab left first). This is a per-agent positional asymmetry that prevents the circular wait, not a global resource hierarchy on the forks.

Both classical-concurrency prompts (resource-ordering, symmetry-breaking) hit a 0% point estimate. Theory-of-mind comes in at 5%, against 90% for the default and 100% once the goal language is stripped.

A one-paragraph change to the system prompt flips Gemini 2.5 Flash from 100% deadlock to no deadlock observed in 20 episodes. We did not retrain anything; we wrote a paragraph. The minimal prompt is a useful sanity check: when the goal is removed, deadlock is total.

Throughput varies across the deadlock-free prompts, but the deadlock numbers do not. The symmetry-breaking prompt reaches 0.275 group meals per timestep (the asymmetric "sometimes wait" rule reduces meals for one philosopher). Resource-ordering reaches 0.733. Theory-of-mind reaches 0.585.

Group size

We went from five philosophers to ten. Gemini 2.5 Flash dropped from 90% deadlock at N=5 to 10% at N=10 (Wilson CI [3.5, 25.6], n=30). Llama 4 Maverick dropped from 76.7% to 16.7% [7.3, 33.6] (n=30). The random baseline dropped from 13.3% to a 0% point estimate (Wilson upper bound 11.4% at n=30).

The textbook deadlock configuration (small N, symmetric topology) is the configuration where deadlock shows up most. At N=5, the symmetric all-one-fork-each configuration accounts for a large share of the reachable state distribution. At N=10, the same configuration is one configuration among many; we present this as a qualitative observation rather than a derived basin size.

Group throughput at N=10 also rises substantially: from 0.146 meals per timestep at N=5 to 1.111 at N=10 for Gemini. This is summed over all N philosophers, so roughly 3.8x per-agent at N=10 (0.111 vs 0.029 meals/agent/timestep).

What explains all three results

Each structural change, varied one at a time, reduces deadlock. The default protocol is symmetric in three independent ways. Agents are interchangeable, commit happens before any signal could differentiate them, and N is small enough that the symmetric jam dominates the state distribution.

Each fix breaks the same symmetry differently. The prompt fixes hard-code the asymmetry up front, and multi-round messaging gives agents room to negotiate one before commit. Larger N dilutes the symmetric configuration into a larger reachable state space. The classical concurrency literature proved these deadlock-freedom conditions analytically; DPBench reproduces them empirically with LLMs as the agents. The memory ablation (n=20) is underpowered, so it neither confirms nor refutes the symmetry-breaking account.

A caveat on scope. The prompt and communication-rounds ablations were run only on Gemini 2.5 Flash, which is the model that fails most under the default conditions. Only the group-size ablation was replicated on a second model (Llama 4 Maverick).

A memory ablation with no detectable effect

We tested whether giving the agent memory of past timesteps would help, the hypothesis being that the agents need more observational history (what just happened to me last timestep), not more pre-commitment communication. We ran three memory conditions on Gemini 2.5 Flash, simultaneous mode, N=5, default prompt, n=20 per condition: a window of three past timesteps with no communication (85% deadlock), a window of five timesteps with no communication (90%), and a window of three timesteps plus one round of communication (80%). For every memory condition, a two-proportion comparison against the no-memory baseline fails to reject equality at our sample size.

Memory ablation. Memory of past states does not produce a detectable change in deadlock at n=20. All three memory conditions fall within the 95% CI of the no-memory baseline (dashed line, 90.0%).

Memory shows no detectable effect on deadlock at n=20. Our power there only catches drops of about 30 points or more, so this is a null result, not evidence the effect is zero. The negotiation rounds are doing the work; the history window is not, as far as this experiment can tell.

For practitioners

If you are building a multi-agent LLM system where agents share resources, here is what worked on the model that failed most. These recommendations are extrapolated from ablations on Gemini 2.5 Flash; the only cross-model replication so far is the group-size axis on Llama 4 Maverick.

Single-round pre-commitment messaging is the default in many orchestration frameworks. On Gemini, our numbers show it produced only a 3.3-point drop with overlapping CIs. Either encode an explicit ordering rule directly in the prompt, or give the agents three or more rounds of negotiation before commitment. A one-paragraph addition is enough on the model we tested most. The form that worked in our experiments was a parity-based grab order keyed on the agent's index (paraphrased here; the verbatim system prompt is in the released prompts/resource_ordering.txt file in the repo):

When deciding which resource to acquire first, consult your agent index. If your index is even, attempt to acquire the right-hand resource before the left. If your index is odd, attempt to acquire the left-hand resource before the right. Only grab your second fork after securing your first. If your first fork is unavailable, wait rather than grabbing the other. Apply this rule consistently every time you commit.

Cost considerations:

• Prompt-level ordering rule. Zero extra LLM calls, zero extra latency. Recommended default.
• Three-round negotiation. Per commit, three serialised rounds of broadcast messaging (3N LLM calls instead of N), which is roughly 3x more LLM calls than single-round messaging (not the no-comm default). 1-round throughput 0.141 rose to 3-round throughput 0.557 (about 4x); the no-communication baseline is 0.146. Cost per meal drops, but per-commit cost rises.
• Larger N. Architectural; you change the agent count rather than the protocol. Often not under your control.

If you are evaluating multi-agent LLM systems, measure protocol-level conditions directly, not just task success under a fixed one. On the model that fails most, the same model can fail on 90% of episodes or succeed on 100%. Which one you get depends on the protocol around it.

Using DPBench

The released package is a one-function interface. You write a function that calls your model and returns a string. You hand it to Benchmark.run. DPBench gives you back the four metrics with confidence intervals.

from dpbench import Benchmark

def my_model(system_prompt: str, user_prompt: str) -> str:
    # Your LLM call here. Returns the agent's response as a string.
    ...

results = Benchmark.run(
    model_fn=my_model,
    system_prompt="...",
    philosophers=5,
    episodes=30,
    mode="simultaneous",
    communication=False,
)

print(f"Deadlock rate: {results['deadlock_rate']:.1%}")
print(f"Throughput:    {results['avg_throughput']:.3f}")
print(f"Fairness:      {results['avg_fairness']:.3f}")

Every numerical result in the paper regenerates from the released per-episode logs. Each log records the LLM input and output for every call, every action and message, and the full table state at every timestep. Any of the four metrics defined in the paper can be recomputed without re-running the agents.

We released the benchmark, the experiment configurations, the aggregated CSVs, the figure-generation scripts, and the test suite. Production multi-agent systems ship with defaults that produce 90% deadlock on the model that fails most. The protocols we vary are not the only protocols worth varying, and the package is built so other axes can be added; see the repository for the full setup.

@misc{hasan2026dpbenchstructuraldeterminantsmultiagent,
      title={DPBench: Structural Determinants of Multi-Agent LLM Coordination Under Simultaneous Resource Contention}, 
      author={Najmul Hasan and Prashanth BusiReddyGari},
      year={2026},
      eprint={2602.13255},
      archivePrefix={arXiv},
      primaryClass={cs.AI},
      url={https://arxiv.org/abs/2602.13255}, 
}