CONFORMALGUARD: DISTRIBUTION-FREE FALSEBLOCK GUARANTEES FOR MULTI-AGENT LLM SYSTEMS VIA CONFORMAL PREDICTION ON DYNAMIC EXECUTION GRAPHS

Multi-agent LLM systems built on AutoGen, MetaGPT, LangGraph and CrewAI execute as dynamic graphs whose topology emerges at inference time. They exhibit compositional unsafe behaviour that no per-call guard can see, and existing runtime defences return no finite-sample guarantee of any kind. We present ConformalGuard, which applies conformal prediction to the multi-agent execution graph. We (i) formalise the execution as a continuous-time heterogeneous graph with four node types and six edge types and compute nonconformity scores over temporal subgraphs with a DyGFormer-HGT encoder; (ii) instantiate split conformal prediction on execution subgraphs, obtaining finite-sample 1−α coverage of the ground-truth safe action - a distribution-free bound on the false-block rate that holds marginally per decision under trace-level exchangeability, for any underlying LLM; and (iii) apply adaptive conformal inference to maintain long-run coverage under distribution shift with an explicit 1/(γT) bound. We are explicit that the guarantee bounds false blocks, not missed violations: violation-block rates are empirical properties of the learned scorer. On AgentChain-26, a new benchmark of 12,400 labelled multi-agent traces across four platforms and 11 violation classes, and on R-Judge, ConformalGuard attains 94.9% empirical coverage (95% CI [94.4, 95.4]) at target 0.95, blocks 96.1% of critical-violation traces versus 18.3–31.2% for per-call guards, 74.6% for GPT-4-as-judge and 84.3% for a rule-based graph-provenance monitor, at 3.4% false-block rate, 1.8 safe continuations per step, and 23 ms per step.