Do Claims, Evidence, and Actions Align? Evidence-Linked Consistency Checking in Multi-Agent Systems

Evidence can appear in a multi-agent log without reaching the agent whose claim depends on it. A factually correct claim can therefore lack task-required support, even when no statements contradict one another. We formulate consistency as satisfaction of task-defined obligations relating evidence, claims, and actions. This definition accounts for which sources an agent may use and the context in which it acts. We introduce ECoCheck (Evidence-linked Consistency Checking), which combines graph-based retrieval, source-linked fact extraction, symbolic checking, and diagnostic feedback. We evaluate detection on perturbed traces and task outcomes in tool collaboration, coordination, and social simulation. Across 120 recorded perturbation outcomes, ECoCheck records 38 detections versus 18 for a transcript-order comparator, Linear, with the largest difference on unsupported claims (17/30 versus 6/30). Under the full treatment, macro-average overall goal success in tool collaboration is 20.00 percentage points above the baseline without verification feedback, and coordination utility is higher in all nine task–scale cells. These comparisons assess checking and feedback together and do not isolate the effect of checking. The selected evidence, encoded requirements, and diagnostics show what each check is based on.