Technical Summary: MAS-DecStream with LLM-Assisted Contract Net Negotiation

Problem Statement

Stream-processing systems operating across heterogeneous mobile edge–cloud infrastructures face significant challenges due to workload volatility, resource contention, and stringent Quality-of-Service (QoS) requirements. Decentralized scheduling is complicated by the fact that individual edge clusters possess only partial visibility of the global system state. Consequently, independent local decisions often lead to resource overcommitment, delayed execution of high-priority tasks, and QoS violations.

While recent approaches utilize Federated Learning (FL) and Reinforcement Learning (RL) to improve adaptability, they often rely on centralized aggregation or learned policies that obscure the reasoning behind scheduling decisions. Classical Multi-Agent Systems (MAS) using the Contract Net Protocol (CNP) offer explicit decentralized interaction but suffer from rigid, predefined message semantics that struggle to accommodate heterogeneous quantitative constraints alongside qualitative warnings (e.g., reliability alerts or privacy conditions). The core problem addressed is how to extend decentralized negotiation to handle uncertain, qualitative runtime contexts without sacrificing hard resource guarantees or introducing prohibitive communication overhead.

Methodology

The paper proposes MAS-DecStream, a hybrid scheduling architecture that integrates Large Language Models (LLMs) into a multi-round negotiation protocol. The system models the edge–cloud environment as a communication graph where representative agents observe local clusters and negotiate task migrations.

Hybrid Agent Architecture

The architecture separates local monitoring from collaborative decision-making:

1. Execution Layer: Monitors runtime telemetry, predicts near-future loads, and applies migration decisions.
2. Collaborative Layer: Orchestrated via LangGraph, each agent combines local state, task knowledge, and negotiation memory. It utilizes an LLM for contextual interpretation and message generation, while relying on deterministic tools for state retrieval, requirement validation, and utility computation.

LLM-Assisted Multi-Round CNP (LLM-MR-CNP)

The core contribution is an extension of the classical single-stage CNP. Unlike traditional CNP, which typically follows a single announcement–proposal–award cycle, LLM-MR-CNP introduces:

• Semantic CFP Formulation: The initiator broadcasts a Call for Proposal (CFP) enriched with task intent, QoS, and observed context, rather than just fixed numerical fields.
• Progressive Context Disclosure: If initial proposals are ambiguous or multiple candidates remain, the initiator discloses additional context (e.g., forecast load, reliability warnings) to unresolved candidates.
• Iterative Proposal Revision: Responders can issue provisional proposals and revise or withdraw them based on the newly disclosed context.
• Deterministic Validation: While the LLM interprets context and refines natural-language proposals, the final allocation is strictly constrained by deterministic feasibility checks (CPU, memory, bandwidth, deadlines) and utility maximization.

The protocol terminates when a single feasible candidate remains, a stable best candidate emerges, or a maximum round limit is reached.

Key Contributions

1. LLM-MR-CNP Protocol: An explicit extension of the classical CNP that introduces semantic CFP generation, progressive disclosure, iterative proposal revision, task-scoped negotiation memory, and bounded termination.
2. Hybrid Agent Architecture: A design where LLMs handle qualitative context and message generation, while deterministic tools enforce hard constraints and utility rankings, ensuring safety and feasibility.
3. Comprehensive Evaluation: A study distinguishing the impact of multi-round refinement from LLM assistance, evaluating scheduling quality, negotiation overhead, and accuracy–cost trade-offs across various models and prompting strategies.

Experimental Results

Experiments were conducted using workloads derived from the Alibaba ASI Trace 2026, simulating 1,000 task–cluster combinations across varying agent counts (5, 10, 20) and concurrent requests.

Performance Metrics

• Latency Violations: MAS-DecStream reduced latency violations to 3% (0.03), a significant improvement over the rule-based multi-round baseline (0.37) and the single-round baseline (0.53).
• Resource Overcommitment: The multi-round approaches (both rule-based and LLM-assisted) completely eliminated resource overcommitment across all tested configurations, whereas single-round methods failed to prevent it.
• Conflict Resolution: With 20 agents, the conflict-resolution rate reached 0.91 for MAS-DecStream, compared to 0.86 for the rule-based multi-round baseline.
• Utility: MAS-DecStream improved global utility by up to 22% over the multi-round rule-based baseline.
• Costs: These gains came with increased coordination costs. MAS-DecStream incurred approximately three times the collaboration cost of single-round methods and introduced an average LLM reasoning time of 83.56 seconds per scenario.

Model and Prompting Analysis

• Negotiation Depth: Multi-round negotiation significantly improved offloading accuracy (from 0.71 to 0.88 for a large LLM), suggesting that the interaction structure is as critical as model capability.
• Prompting Strategies: Performance was highly model-dependent. For instance, Gemini-3-Flash with a ReAct+few-shot+CoT prompt achieved 1.00 offloading accuracy, while other configurations showed varying trade-offs between accuracy and token consumption.
• Trade-offs: The study highlighted a clear accuracy–cost trade-off, where more complex prompting strategies (e.g., ReAct) increased token usage and latency without always guaranteeing superior outcomes compared to simpler strategies like CoT+Few-shot.

Significance and Claims

The paper positions its findings as an initial empirical assessment rather than a proof of general superiority over established schedulers. The authors make the following modest claims regarding the system's significance:

1. Protocol-Level Gain: The primary performance gain stems from extending the CNP to include multi-round proposal refinement. This iterative process reduces violations and eliminates overcommitment even without LLM assistance.
2. Contextual Value of LLMs: LLM assistance provides incremental value specifically for qualitative and uncertain runtime contexts (e.g., interpreting reliability warnings or ambiguous forecasts) where rule-based systems struggle.
3. Hybrid Necessity: The results support an adaptive deployment strategy where rule-based negotiation handles routine decisions, while agentic AI is selectively invoked for uncertain, conflicting, or high-impact scheduling decisions.
4. Safety First: The architecture demonstrates that LLM-generated semantic decisions can be safely integrated into critical infrastructure only when paired with deterministic validation to enforce hard resource and QoS guarantees.

The authors acknowledge limitations, including the lack of causal ablation for the LLM component (as it is coupled with qualitative context handling) and the reliance on trace-derived workloads rather than physical deployments. Future work is directed toward evaluating selective LLM escalation and larger decentralized topologies.