TRACE-MAS: Provenance Guided Selective Recovery for Multi-agent Incidents

In multi-agent systems, a message that seems safe locally can become harmful after it enters shared memory, reaches another agent, or drives a tool action. Current runtime controls flag a risky record or stop a run, leaving the downstream state requiring repair unspecified. We present TRACE-MAS, a runtime controller for selective recovery. At each checkpoint, it builds a typed event graph over observed messages, state changes, and tool interactions, then uses that graph to locate a likely source, estimate the affected state, and choose an allowable action through a shared action-permission interface. We evaluate TRACE-MAS on TRACE-Bench, which covers resource competition, collective deliberation, shared memory, and tool transfer, together with incomplete runtime records, public interface adapters, and a bargaining game interface. The evaluation pairs TRACE-MAS with a matched Direct-risk control that keeps the same alerts, permitted actions, recovery templates, and input allowance. TRACE-MAS additionally receives the graph and source and scope output. Paired replay tests the selected action on the same trajectories under true root, decoy, global, and no intervention branches. The matched resource competition comparison lowers Harm by 12.0% and ASR by 49.0% while raising Utility by 13.0% relative to Direct-risk. Supplementary evaluations examine noisier provenance and alternative ranking rules. Our findings show that typed dependencies and selective actions can repair affected state while preserving unrelated work.