Compositional Permission Flow Verification for Multi-Agent LLM Systems with Adaptive Security Consolidation

Multi-agent systems built on large language models share tools, messages, and delegated authority in ways that create security risks invisible under per-agent analysis. Privilege escalation across agents, confused-deputy misuse, and transitive exfiltration arise from interaction structure rather than from any single prompt or tool call. We present ProMeTheUSE, a framework that formalizes Security Contracts for agents, builds a Permission Dependency Graph (PDG) with algebraic flow operators, and verifies three properties, namely least privilege, data confidentiality, and delegation integrity. A polynomial-time analyzer detects six compositional vulnerability classes and synthesizes minimal repairs. Across large-scale evaluation on nearly 10,000 samples spanning a synthetic corpus, public-template PDG encodings, and a held-out transfer set, the sound verifier recovers injected structural witnesses when the full graph is visible and stays in the mid-90s F1 under contract and edge degradation. A distilled Adaptive Security Consolidation (ASC) student remains competitive under partial observability while nearest-centroid and feature baselines fall behind. The analyzer scales to 50 agents in under 50 ms. ASC adds hierarchical security memory, runtime motif monitoring, and verification-gated contract updates. Generative Adversarial Verification expands the threat taxonomy beyond the initial six classes.