Learning to Interrupt in Language-based Multi-agent Communication

1. Problem Statement

Large Language Model (LLM)-based multi-agent systems have demonstrated success in complex tasks (reasoning, software engineering, social simulation). However, they suffer from inefficient communication characterized by:

• Verbose Outputs: LLMs tend to generate long, detailed messages, overloading the context window.
• High Computational Costs: Excessive token generation increases inference latency and compute costs.
• Listener-Agnostic Compression: Existing solutions focus on compressing messages from the speaker's side (e.g., prompting for conciseness). This fails because different listeners have different knowledge bases and needs; a message concise for one agent may be insufficient for another, while a detailed message may be redundant for a knowledgeable agent.

The paper proposes shifting the optimization paradigm from speaker-oriented compression to listener-oriented interruption, mimicking human conversation where listeners interrupt to ask for clarification or provide answers when they have sufficient information.

2. Methodology: HANDRAISER

The authors propose HANDRAISER, a framework that enables a listening agent to interrupt a speaking agent's generation stream dynamically.

A. Interruptible Communication Protocol

• Streaming Chunks: The speaker generates messages in fixed-size chunks (e.g., 16 tokens) rather than a single full message.
• Listener Decision: After receiving each chunk, the listener evaluates whether to interrupt.
• Mechanism: If the listener decides to interrupt, it sends a signal. The speaker immediately halts generation, and the listener begins generating its response.
• Benefits: This saves the generation cost of the remaining speaker tokens and reduces latency by allowing the listener to respond earlier.

B. Learning to Interrupt (The Core Innovation)

Initial experiments showed that LLMs are overconfident and interrupt prematurely (often in the first chunk), leading to task failure or increased rounds. To solve this, the authors developed a training pipeline:

1. Tree Sampling for Payoff Estimation:
   • To determine the optimal interruption point, the system simulates future interactions using a tree-based rollout.
   • For a given chunk $i$, the system branches into two possibilities: Interruption vs. No Interruption.
   • It rolls out the conversation to the end for both branches to estimate:
     • $\Delta$Cost: The reduction in total tokens generated.
     • $\Delta$Perf: The change in final task success rate.
2. Labeling Strategy:
   • A data point is labeled as a positive interruption only if it reduces communication cost ($\Delta$Cost < 0) while maintaining or improving task performance ($\Delta$Perf $\ge$ 0).
   • This creates a dataset of "good" vs. "bad" interruption points based on estimated future rewards.
3. Supervised Fine-Tuning (SFT):
   • The listener model (HANDRAISER) is fine-tuned on this dataset using cross-entropy loss to predict "Yes" (interrupt) or "No" (wait) for each incoming chunk.

3. Key Contributions

• Listener-Oriented Framework: Introduced a novel communication paradigm where the listener controls the flow of information, rather than forcing the speaker to compress.
• Payoff-Based Learning: Developed a method to train interruption policies by estimating the trade-off between communication cost and task performance via tree sampling, addressing the issue of LLM overconfidence.
• Generalization: Demonstrated that the learned interruption behavior generalizes across different speaker models (e.g., Llama, GPT-4o, Gemini) and different tasks without retraining the listener.
• Scalability: Showed the framework can be decomposed to handle complex multi-agent topologies (e.g., group chats, cascading interruptions).

4. Experimental Results

The framework was evaluated across three distinct multi-agent scenarios:

1. Text Pictionary: A 2-agent game (Describer vs. Guesser).
2. Meeting Scheduling: A 3-agent task with private information constraints.
3. MMLU-Pro Debate: A 3-agent reasoning debate (Pro, Con, Moderator).

Key Findings:

• Cost Reduction: HANDRAISER reduced communication costs significantly compared to baselines:
  • -24.3% in Text Pictionary.
  • -23.4% in Meeting Scheduling.
  • -48.9% in MMLU-Pro Debate.
• Performance Maintenance: Unlike "Prompting" (which caused premature interruptions and lower success rates) or "Random" interruption, HANDRAISER maintained comparable or superior task success rates.
• Robustness: The model trained on one speaker (e.g., Llama-70B) performed well when interacting with unseen speakers (e.g., GPT-4o).
• Cross-Task Transfer: While task-specific training is optimal, interruption behaviors learned in one task (e.g., Debate) could still improve performance and reduce cost in other tasks (e.g., Pictionary), though with slightly lower gains.

5. Significance and Implications

• Efficiency: This work addresses the "token tax" in multi-agent systems, offering a practical way to reduce inference costs and latency without sacrificing reasoning quality.
• Human-Like Interaction: By allowing interruptions, the system moves closer to natural human dialogue dynamics, where information exchange is bidirectional and adaptive.
• Future Direction: The paper suggests that combining listener-oriented interruption with speaker-oriented compression (e.g., using HANDRAISER with a "Concise" speaker) yields the best results, indicating these methods are orthogonal and complementary.
• Scalability: The ability to handle complex, multi-directional communication patterns suggests this framework is viable for large-scale, open-ended multi-agent deployments.

In conclusion, HANDRAISER proves that teaching agents when to stop listening and start speaking is a more effective strategy for communication efficiency than simply teaching them how to speak less.