# CalBench: Evaluating Coordination-Privacy Trade-offs in Multi-Agent LLMs

arXiv: https://arxiv.org/abs/2605.09823 · HTML: https://mlsanity.com/paper/2605.09823/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 16 of its 63 references that are in the map.
- First posted on arXiv 10 May 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)

## Builds on (most cited first, 16 of 16)

- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025)
- [SOTOPIA: Interactive Evaluation for Social Intelligence in Language Agents](https://mlsanity.com/paper/2310.11667/) (2023)
- [Can LLMs Keep a Secret? Testing Privacy Implications of Language Models via Contextual Integrity Theory](https://mlsanity.com/paper/2310.17884/) (2023)
- [Deal or No Deal? End-to-End Learning for Negotiation Dialogues](https://mlsanity.com/paper/1706.05125/) (2017)
- [MultiAgentBench: Evaluating the Collaboration and Competition of LLM agents](https://mlsanity.com/paper/2503.01935/) (2025)
- [PrivacyLens: Evaluating Privacy Norm Awareness of Language Models in Action](https://mlsanity.com/paper/2409.00138/) (2024)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [How Well Can LLMs Negotiate? NegotiationArena Platform and Analysis](https://mlsanity.com/paper/2402.05863/) (2024)
- [Cooperation, Competition, and Maliciousness: LLM-Stakeholders Interactive Negotiation](https://mlsanity.com/paper/2309.17234/) (2023)
- [AirGapAgent: Protecting Privacy-Conscious Conversational Agents](https://mlsanity.com/paper/2405.05175/) (2024)
- [CooperBench: Why Coding Agents Cannot be Your Teammates Yet](https://mlsanity.com/paper/2601.13295/) (2026)
- [OpenSkill: A faster asymmetric multi-team, multiplayer rating system](https://mlsanity.com/paper/2401.05451/) (2024)
- [MAGPIE: A dataset for Multi-AGent contextual PrIvacy Evaluation](https://mlsanity.com/paper/2506.20737/) (2025)
- [Reproducibility Study of Cooperation, Competition, and Maliciousness: LLM-Stakeholders Interactive Negotiation](https://mlsanity.com/paper/2502.16242/) (2025)
- [CRAFT: Grounded Multi-Agent Coordination Under Partial Information](https://mlsanity.com/paper/2603.25268/) (2026)

## Built on by (most cited first, 7 of 7)

- [Graph Engineering in the Era of LLM Agents: From Individual Intelligence to System Intelligence](https://mlsanity.com/paper/2608.21156/) (2026)
- [PiSAs: Benchmarking Contextual Integrity in Multi-User Agentic Systems](https://mlsanity.com/paper/2607.05318/) (2026)
- [SoK: When Safe Agents Fail Together: The Security of Multi Agent LLM Systems](https://mlsanity.com/paper/2609.00595/) (2026)
- [Selection-Invariant Communication Compilers for Privacy-Aware Multi-Agent LLM Workflows](https://mlsanity.com/paper/2609.26076/) (2026)
- [MNC: Scope-Bound Semantic Declassification for Private LLM-Agent Communication](https://mlsanity.com/paper/2608.01719/) (2026)
- [From Passive Delegates to Strategic Negotiators: Reinforcing Social Reasoning in Small Language Models with SocialRL](https://mlsanity.com/paper/2608.13787/) (2026)
- [Worse Together: How Performance Breaks Down in Multi-User Multi-Agent Teams](https://mlsanity.com/paper/2610.00583/) (2026)

## Abstract (arXiv)

Personal AI assistants are beginning to act as delegates with access to calendars, inboxes, and user preferences. Calendar scheduling makes the trust problem concrete: an assistant must coordinate with other assistants while deciding what to reveal about the person it represents. We introduce CalBench, a controlled benchmark for multi-agent calendar scheduling under private information. In each task, N agents manage separate private calendars and schedule a stream of M incoming meetings while minimizing disruption costs. Because no agent can inspect another agent's calendar, success requires language-mediated coordination rather than centralized planning. CalBench generates solvable scenarios with CP-SAT oracle solutions and decentralized non-LLM reference protocols, enabling evaluation of task success, excess cost, communication efficiency, burden fairness, and privacy leakage under matched information constraints. Across seven model families, we find that completion alone misses important failures: agents leave avoidable cost on the table, communication volume does not predict lower regret, and privacy-preserving silence can deprive teammates of cost information needed for fair burden allocation. CalBench provides a reproducible testbed for studying whether autonomous assistants can coordinate on behalf of users before deployment at scale.