💻 computer science

Composable Verification Pipelines for Multi-Agent Systems

This paper introduces a modular, functional programming framework implemented in Soda that enables composable verification pipelines for multi-agent systems, allowing users to define domain descriptions in YAML and execute transparent, guaranteed-terminating reasoning workflows for dynamic systems involving complex scenarios like misinformation and emotional reasoning.

Original authors: Julian Alfredo Mendez, Andreas Brännström

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Julian Alfredo Mendez, Andreas Brännström

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computer programs aren't just lines of code, but characters in a living story. In the realm of computer science, there's a field dedicated to figuring out how these characters move, change, and interact over time. This is the study of "action and change." Think of it like a board game where pieces move, rules dictate what's allowed, and the goal is to predict if the game will end in a fair win or a chaotic mess. For years, scientists have used heavy, logic-based tools to write down these rules, trying to prove that a system behaves correctly. But these tools can be clunky, like trying to build a complex Lego castle using only a single, giant brick. They work, but they aren't very flexible or easy to share with other types of builders.

Now, imagine if you could build that castle using modular, snap-together pieces that anyone could understand and rearrange. That's the problem Julian Alfredo Mendez and Andreas Brännström are tackling. They want to create a way to check if a digital story (a sequence of actions and states) follows the rules, but they want to do it using a modern, flexible approach that feels more like building with high-tech LEGO than solving a math puzzle. They are asking: Can we make the verification of complex, multi-agent systems (like a team of robots or a social network of bots) as easy and transparent as connecting pipes in a factory?

The authors introduce a new framework called "Composable Verification Pipelines." Instead of using the old, heavy logic bricks, they built a system based on "Tiles" and a language called "Soda." Think of "Tiles" as a set of magical, transparent pipes. Each pipe does one simple job: it takes in a piece of data (like a state of the world or an action an agent took), processes it, and passes it to the next pipe. By snapping these pipes together, you create a "pipeline" that can watch a whole story unfold and check every single step against the rules.

The paper proposes that you can describe a complex system—like a group of agents sharing news or making decisions—using a simple, readable format called YAML (which is like a structured to-do list). Once you write down your rules and your story in this format, the framework automatically turns them into a chain of these functional pipes. As the story plays out, the data flows through the pipeline. One pipe might check if an action was allowed; another might see if a rule was broken; a third might combine everything to give a final "Yes" or "No" on whether the story is valid.

The researchers show that this approach is not just a theory; they built it and tested it. They demonstrated that by breaking the verification process into these small, reusable components, they can handle complex scenarios, like misinformation spreading on a social network or how emotions affect an agent's decisions. For instance, in one example, a story about an agent sharing a lie looked like a rule violation at first. But when they added "emotional fluents" (rules about how the agent feels) into the pipeline, the story suddenly made sense and became valid. This proves that their system can be easily tweaked to include new, richer details without having to rebuild the whole machine.

Crucially, the paper proves that these pipelines will always finish their job. Because the system is built from simple, finite steps, it guarantees that the verification process won't get stuck in an endless loop. They also measured how fast it runs, showing that the time it takes grows in a predictable, linear way as you add more rules or longer stories. The authors suggest that this method bridges the gap between the heavy math of action languages and the flexible, modular world of modern software engineering, making it easier to build and verify complex, rule-based systems in the future.

Technical Summary: Composable Verification Pipelines for Multi-Agent Systems

Problem Statement

The increasing complexity of dynamic and multi-agent systems has intensified the need for executable verification mechanisms capable of analyzing evolving executions under rule-based constraints. While seminal work on action languages (e.g., CMT, GOLOG, STRIPS) provides expressive semantics for reasoning about action and change, existing implementations are predominantly based on logic programming systems. This creates a barrier to integrating verification solutions with mainstream software engineering practices, particularly within functional and object-oriented programming communities. The authors identify a gap in providing modular, composable, and transparent verification workflows that can be operationalized within standard software ecosystems (such as the JVM) while maintaining rigorous formal semantics.

Methodology

The paper proposes a modular framework for transition and trajectory verification that operationalizes action language semantics through executable functional pipelines. The methodology is built upon three core pillars:

Formal Model (CMT-based): The framework utilizes the CMT action language, which defines a domain description language ( $D_{MT}$ ) consisting of static and dynamic causal laws. These laws govern state evolution through trajectories defined as sequences of states and action sets ( $\langle s_0, A_1, s_1, \dots, A_n, s_n \rangle$ ).
- Fluent Representation: Unlike traditional tuple-based representations, the model partitions fluent values to ensure global uniqueness (e.g., distinguishing 'goal-high' from 'goal-low' as distinct identifiers).
- Verification Function ( $\phi_{verify}$ ): A formal verification function evaluates whether a transition (input state, action set, output state) satisfies a specific rule. The function handles various rule types including causes-if, triggers, inhibits, no-concurrency, and contravenes.
- Transition Construction: A sliding window mechanism is defined to incrementally construct transitions from a raw trajectory sequence, ensuring a formal basis for the verification procedure.
Compositional Architecture (Tiles & Soda):
- Tiles: A framework for composing typed functions into graphical and modular specifications. Verification procedures are represented as pipelines where "tiles" (functions) are connected to process states, actions, and rules.
- Soda: A statically typed descriptive language used to implement the specifications. Soda specifications are translated into Scala for execution on the Java Virtual Machine (JVM) and can be partially translated into Lean for formal verification.
- Pipeline Structure: The verification process is structured as a sequence of typed transformations:
  - Trajectory Processing: A fold operation constructs a sequence of transitions from the input trajectory.
  - Rule Application: A cross-product operation combines transitions with the set of rules.
  - Verification: A map operation applies $\phi_{verify}$ (and $\phi_{inhibit-set}$ for handling inhibited actions) to each transition-rule pair.
  - Aggregation: A final fold operation aggregates results to determine overall validity.
Operationalization: The framework includes a YAML-based specification layer. Users define domain descriptions (fluents, actions, rules) and input trajectories in YAML, which are parsed and operationalized into the underlying verification model and executable pipeline.

Key Contributions

The paper outlines four primary contributions:

Modular Framework: Introduction of a modular framework for transition and trajectory verification based on the Tiles and Soda technologies.
Operationalized Semantics: The framework operationalizes action language semantics (specifically CMT) through executable verification pipelines, treating states, actions, and rules as compositional functional components.
YAML Specification Layer: Provision of a YAML-based specification layer and parser that allows users to define domain descriptions and trajectory inputs, bridging the gap between formal models and executable code.
Transparent Execution: Demonstration that the approach provides a transparent, executable, and scalable method for verifying rule-based system executions, with guaranteed pipeline termination.

Results and Evaluation

The authors provide an open-source implementation and illustrate the framework through two specific examples involving misinformation propagation and emotional reasoning:

Misinformation and Emotional Reasoning: The paper demonstrates how the framework supports modular refinement. In a scenario involving misinformation spread, a trajectory initially appears invalid when only informational states are considered. However, by extending the model with emotional fluents (e.g., "emotionally conflicted" vs. "emotionally aligned"), the same trajectory becomes valid. This illustrates the framework's ability to incorporate contextual information without altering the underlying verification structure.
Performance and Complexity: Theoretical analysis (Proposition 4) establishes the complexity of the pipeline as $O(r \times t \times d)$ , where $r$ is the number of rules, $t$ is the number of states/action sets, and $d$ is the bound for evaluating the verification function. Empirical evaluation on a standard multi-core Linux computer shows that execution times scale linearly with the number of rules, consistent with theoretical expectations, with minor deviations attributed to memory management overhead.

Significance and Claims

The paper claims that its primary significance lies in bridging the gap between action reasoning/planning research and compositional software engineering approaches. By moving away from purely logic-programming-based implementations, the framework:

Enables integration with mainstream JVM-based software ecosystems.
Provides a graphical overview of specifications (via Tiles), improving transparency and interpretability.
Ensures termination of the verification process by construction.
Supports reusable reasoning components and modular refinement of trajectory models.

The authors maintain a modest scope, noting that the current work is limited to verification over explicitly specified trajectories and domain descriptions. It does not address automated trajectory generation or planning, but rather provides a full semantic embedding of the CMT action language that is extensible by design.