Can Proof Assistants Verify Multi-Agent Systems?
Julian Alfredo Mendez, Timotheus Kampik · 2025
Read Can Proof Assistants Verify Multi-Agent Systems? by Julian Alfredo Mendez, Timotheus Kampik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06812.txt.
Introduction
Julian Mendez and Timotheus Kampik ask whether proof assistants can certify systems of cooperating software agents. Their answer is a language, Soda, built for the double life such proof demands. Soda code compiles to Scala for real deployment and to the Lean proof assistant for formal checking. Their 2025 paper introduces the language informally and walks through a demonstration. An interaction protocol between agents is designed in Soda, then verified in the same source.
The demo surfaces the friction points where real-world use strains the method. One codebase serving both running and proving is the core bet. Agent systems increasingly negotiate, bid, and commit on our behalf, which raises the stakes for proof. The paper offers a working sketch, not a finished discipline.
Catalog record
| CREATOR | Julian Alfredo Mendez, Timotheus Kampik |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-06812
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Can Proof Assistants Verify Multi-Agent Systems? Julian Alfredo Mendez, Timotheus Kampik Abstract This paper presents the Soda language for verifying multi-agent systems. Soda is a high-level functional and object-oriented language that supports the compilation of its code not only to Scala, a strongly statically typed high-level programming language, but also to Lean, a proof assistant and programming language. Given these capabilities, Soda can implement multi-agent systems, or parts thereof, that can then be integrated into a mainstream software ecosystem on the one hand and formally verified with state-of-the-art tools on the other hand. We provide a brief and informal introduction to Soda and the aforementioned interoperability capabilities, as well as a simple demonstration of how interaction protocols can be designed and verified with Soda . In the course of the demonstration, we highlight challenges with respect to real-world applicability. 1 Introduction Multi-agent systems (MAS) are systems composed of multiple interacting intelligent agents, working towards joint or conflicting goals. MAS have emerged as an approach for modeling and implementing complex distributed systems, because MAS-based systems can solve problems that are very difficult or impossible to solve using monolithic architectures. Due to their dynamic and distributed nature, MAS are notoriously difficult to test. At the same time, ensuring desirable behavior in MAS components is crucial to verify that the autonomy that agents are granted does not lead to safety or compliance issues. Consequently, testing and verification of MAS has emerged as a substantial branch of MAS engineering research. Here, most research focuses either on finite state model checking [ 4 ] or–presumably less frequently–on testing in the software engineering sense (as in test-driven development ) [ 1 ] . In this paper, we take a novel path and present a prototypical approach where parts of a MAS are implemented in Soda , a high-level programming language that can be compiled to Scala for integration with a mainstream programming ecosystem, as well as to Lean, a proof assistant and programming language that applies calculus of constructions [ 13 ] . The formal verification of the program code can then be executed in Lean. To illustrate the approach and demonstrate its feasibility, we provide a simple running example of interaction protocol verification with Soda and Lean, which we introduce conceptually below. In our example, we want to implement an interaction protocol for a platform on which multiple agents buy and sell items. We assume that the transactions are safe and conducted by a mediator that is trusted by all involved agents and can transfer possession of items and money between the agents. In the following, we provide an example interaction sequence that can serve as an archetype for the protocol that our MAS should enact. 1. A seller C notifies the mediator A to advertise a certain item R at a price P . 2. The mediator A informs all agents that the item is available for sale. 3. While no buyer has shown interest, C can remove the ad. 4. If a buyer B wants to buy R and has money P to pay for it, the buyer notifies A . 5. When A is notified of the purchase, it removes the ad, and it transactionally transfers the item R from C to B , and the amount of money P from B to C . In our approach, we use lists to store items. As a proof of concept, we prove a technical but important property: Property. Changing an item in the list does not change the size of the list . This property is important, but it is usually taken for granted. Proving these kinds of properties in a proof assistant like Lean requires substantial effort because lemmas and tactics require maturity to be employed. All cases need to be covered, and the resulting object after the execution must always be defined. In the particular case of our functions, we work with immutable lists. Our lists are thread-safe, which allows them to run in parallel execution, and follow the standard construction in functional languages. They are defined as being either an empty list or an element prepended to a list. This makes them memory-efficient because replacing an arbitrary position requires reconstructing the list until the given position. As we can see, the property we prove looks simplistic from an intuitive software engineering perspective. Still, we chose to prove this property as a minimal demonstrating example, due to the following reasons: i) even such simple facts are somewhat effortful to prove with proof assistants such as Lean; ii) our example is sufficient for highlighting practical challenges, while also serving as a proof-of-concept with respect to purely technical feasibility. In the remainder of this paper, we give a brief overview of research on testing and verifying MAS (Section 2 ) to then introduce Soda and its interoperability capabilities, both with the Scala/Java ecosystem and with the Lean proof assistant (Section 3 ). We then continue our running example to demonstrate how agent interaction protocols can be specified and verified with Soda (Section 4 ). Subsequently, we discuss in detail the formal proofs (Section 5 ). We show with practical experiments that the example is efficient (Section 6 ). After that, we discuss our work and its limitations, and conclude with a future outlook (Section 7 ). 2 Why Formal Verification for MAS? Software verification ensures that specific components meet specification requirements. We can compare software verification with software validation, since both are software evaluation processes. The former focuses on determining whether a software artifact meets the conditions with respect to its broader purpose, imposed at the beginning of a development phase, whereas the latter determines whether the requirements are satisfied at the end of a development phase. The verification of agents and MAS has been subject to extensive study over the years. Here, verification can either be seen from an applied software engineering perspective, i.e., testing without “hard” guarantees, or as the formal analysis ( formal verification ) of MAS or components thereof. Jason [ 5 ] and SARL [ 16 ] are specialized multi-agent programming languages, with Jason focusing on logical reasoning and SARL on dynamic, distributed environments. Jason is an interpreter for an extended version of AgentSpeak(L) [ 15 ] , a BDI (Belief-Desire-Intention) agent-oriented logic programming language. Jason provides a platform for developing multi-agent systems with customizable features, especially for environments requiring logical reasoning and decision-making. SARL is a general-purpose agent-oriented programming language designed to handle concurrency, distribution, interaction, decentralization, reactivity, autonomy, and dynamic reconfiguration. It integrates well with the Janus [ 8 ] platform for distributed multi-agent systems. Although agent testing is certainly a relevant research domain, e.g., in the context of technologies for agent-oriented programming [ 1 , 2 ] , a well-informed assumption is that for MAS, testing is insufficient because of agents’ and MAS’ highly dynamic behavior [ 19 ] , in particular if contrasted with mainstream software components in server-client architectures. Because mainstream software testing approaches are often deemed insufficient for engineering MAS, researchers have devised a range of formal approaches to verify agents or other components of MAS. These approaches typically rely on model checking techniques [ 4 , 7 , 10 ] .