Multi-User Large Language Model Agents

1. Problem Statement

Current Large Language Model (LLM) agents are predominantly optimized for a Single-Principal–Agent paradigm. In this setting, the agent interacts with one user, treating their instructions as the sole source of authority and utility. However, as LLMs are integrated into organizational workflows, they increasingly face Multi-Principal–Agent scenarios where a single agent must serve multiple users simultaneously.

These multi-user settings introduce three critical challenges that current models are ill-equipped to handle:

1. Conflicting Objectives: Different users (e.g., a CEO vs. an Engineer) may issue contradictory instructions requiring the agent to prioritize based on authority or global goals.
2. Information Asymmetry & Privacy: Users possess private contexts (e.g., salary data, personal drafts) that should not be shared with other users. The agent must enforce strict access control while facilitating collaboration.
3. Coordination Complexity: Agents must manage iterative information gathering and negotiation among multiple parties with heterogeneous constraints (e.g., scheduling meetings) without hallucinating availability or prematurely committing to invalid solutions.

The paper argues that existing training pipelines (Instruction Tuning and RLHF) implicitly assume a single user role, collapsing multi-user inputs into a serialized format. This prevents models from natively reasoning about user identities, roles, authority hierarchies, and privacy boundaries.

2. Methodology

A. Formalization

The authors formalize multi-user interaction as a multi-objective decision problem.

• Setting: A single agent interacts with a set of users $U = \{u_1, ..., u_N\}$.
• User Attributes: Each user $u_i$ has an authority persona $p_i$, a private context $C_i$, and a utility function $U_i$.
• Objective: The agent aims to maximize a weighted social objective:
  $$\max_{a \in A} \sum_{i=1}^{N} w_i U_i(a; C_i, p_i)$$
  where $w_i$ represents priority weights based on authority (e.g., CEO > Intern).
• Constraints: The agent operates under selective visibility, where it only sees $C_i$ when explicitly shared, and must adhere to access-control policies to prevent unauthorized disclosure.

B. Stress-Testing Framework (Muses-Bench)

To evaluate frontier LLMs, the authors introduce a unified interaction protocol and three targeted stress-testing scenarios:

1. Multi-User Instruction Following:

   • Task: Resolve conflicting instructions based on authority hierarchy and global objectives.
   • Example: A CEO orders a halt to model development, while an Engineer requests to continue and post updates.
   • Metrics: Selection F1 (correctly identifying which instructions to accept/refuse) and Execution Accuracy (faithfully executing the accepted instructions).

2. Cross-User Access Control:

   • Task: Enforce privacy boundaries when multiple users query sensitive resources.
   • Example: An unauthorized user asks for salary data while an authorized HR Director requests the same data for budgeting. Includes adversarial attacks (social engineering, role-playing).
   • Metrics: Privacy Score (zero leakage to unauthorized users) and Utility Score (successful delivery to authorized users).

3. Multi-User Meeting Coordination:

   • Task: Schedule a meeting among users with partial or conflicting availability.
   • Challenge: The agent must proactively query missing information and negotiate without hallucinating user constraints.
   • Metrics: Success Rate (valid slot found for all), Turns Taken (efficiency), and Attendance Rate.

C. Experimental Setup

• Models Evaluated: A diverse suite of 19 state-of-the-art models, including proprietary (GPT-4o/5, Claude 3.5/4.5, Gemini 2.5/3, Grok) and open-weight (Llama 3, Qwen3, DeepSeek-R1, GLM-4).
• Serialization: Since current models lack native multi-user message schemas, the study simulates multi-user interactions by serializing inputs (e.g., "User A says:...", "User B says:...") into a single prompt.

3. Key Contributions

1. First Systematic Study: This work provides the first formal definition and systematic evaluation of LLM agents in multi-principal settings.
2. Unified Protocol & Benchmark: Introduction of a rigorous protocol for simulating multi-user interactions and the Muses-Bench benchmark covering instruction conflict, access control, and coordination.
3. Identification of Fundamental Gaps: The study reveals that current frontier models, despite high single-user performance, suffer from specific failure modes in multi-user environments:
   • Fragile Conflict Resolution: Performance degrades significantly when instructions conflict.
   • Privacy Erosion: Privacy guarantees degrade over multi-turn interactions, even for models that pass single-turn checks.
   • Coordination Inefficiency: Agents struggle to proactively identify missing information, often leading to premature commitments or excessive interaction turns.

4. Key Results

• Instruction Following: There is a clear mismatch between selection and execution. Models often correctly identify which instruction to follow (high Selection F1) but fail to execute it faithfully (low Execution Acc), or vice versa. For instance, Claude-Sonnet-4.5 achieved 95.9% Selection F1 but only 79.9% Execution Acc.
• Privacy vs. Utility Trade-off: Models face a difficult trade-off. Grok-3-Mini achieved near-perfect Privacy (99.7%) but low Utility (59.0%), indicating over-conservatism. Conversely, GPT-OSS-120B had high Utility (94.8%) but lower Privacy (92.2%).
• Multi-Turn Privacy Leakage: Privacy scores decline consistently as interaction rounds increase. For example, Claude-3.5-Haiku dropped from >0.95 privacy in Round 1 to <0.75 by Round 4, suggesting models fail to maintain long-term context of access policies.
• Coordination Bottlenecks: Even the best models (e.g., GPT-OSS-120B) achieved only ~77% success in meeting coordination under partial information. Models often fail to ask clarifying questions, instead hallucinating consensus or committing to invalid times (e.g., Llama-3-70B exhibited "premature commitment").
• Scalability: Success rates drop sharply as the number of users increases (especially in partial disclosure settings), while the number of required turns scales linearly, highlighting an efficiency bottleneck.

5. Significance and Future Directions

This paper highlights a critical gap between current LLM capabilities and the requirements of real-world organizational deployment. The findings suggest that simply scaling models is insufficient; a qualitative shift in problem formulation is required.

Future Directions proposed:

• Native Multi-User Interfaces: Moving beyond serialized prompts to message schemas that explicitly encode user identity, roles, and authority as first-class primitives.
• Long-Horizon Safety: Developing benchmarks that test privacy and policy consistency over extended interactions rather than single-turn checks.
• Principled Conflict Resolution: Integrating social choice theory and mechanism design to formalize utility aggregation and conflict arbitration.
• Auditability: Creating tools for inspecting and auditing multi-user decision logs to ensure transparency.

In conclusion, the paper establishes that while frontier LLMs show promise, they are currently not robust for multi-principal settings due to inherent training biases toward single-user optimization. Addressing these limitations requires rethinking training objectives, interaction protocols, and evaluation metrics.