Neural Symbolic Methods for Strategy Synthesis in Multi-Agent Systems: Fusion of Large Models and Formal Verification

This article introduces a neural symbolic framework proposed in the latest arXiv study (2606.17962v1), which combines the generative capabilities of large language models (LLMs) with the rigor of formal verification to address the computational bottleneck in strategy synthesis for multi-agent systems (MAS). This framework significantly improves efficiency while maintaining the formal correctness of strategies, providing new solutions for complex scenarios such as autonomous driving and robot collaboration.

Multi-agent systems consist of autonomous entities and need to address the question: 'Can an agent coalition achieve its goals through coordinated strategies?' Formal logics like ATL provide a mathematical foundation, but strategy synthesis faces state explosion: the strategy space grows exponentially with the number of agents, making traditional symbolic methods difficult to handle large-scale systems (e.g., autonomous driving, distributed robot collaboration).

The framework adopts a two-stage 'generate-verify' architecture: 1. Generation phase: LLM acts as an oracle to heuristically generate candidate strategies; 2. Verification phase: A MAS model checker performs formal verification on the candidate strategies to ensure they meet the target properties. This architecture has a clear division of labor: LLM navigates the strategy space, and the verifier ensures correctness, avoiding false positives.

The research team built the first NatATL dataset, containing 4211 instances covering different system scales, strategy complexities, and target property types, providing a public platform for benchmarking and supporting systematic evaluation of the framework's effectiveness.

Experiments using the open-source Qwen3-32B model showed that the certification pipeline achieved a strategy synthesis accuracy of 92%. The results indicate that lightweight open-source models can effectively support the application of formal methods under a reasonable architecture, enabling deployment in resource-constrained environments.

The technical contribution lies in the general neural symbolic fusion paradigm (the generate-verify architecture can be extended to other combinatorial optimization problems); the methodological significance is to alleviate the tension between the black-box nature of neural networks and the interpretability of formal methods, providing inspiration for cross-research between AI and formal methods.

Limitations: Dependence on the quality of LLM-generated candidates, current focus on bounded strategy scenarios, and the need to improve dataset complexity. Future directions: Explore the impact of stronger foundation models, develop adaptive candidate generation strategies, extend to unbounded systems, and study theoretical completeness and complexity boundaries.

The framework can be applied to fields such as autonomous driving (vehicle coordination strategies), robot collaboration (task allocation), and smart contract verification (vulnerability detection and repair). With the advancement of LLM and formal verification technologies, neural symbolic methods are expected to promote the development of trustworthy AI systems, balancing computational efficiency and correctness guarantees.