TLDR: VERIMAP is a novel framework that significantly improves collaboration among large language model (LLM) agents by integrating explicit verification into the planning process. It breaks down complex tasks into subtasks, each with specific Python or natural language verification functions (VFs) defined by a central planner. This allows agents to receive precise feedback, self-refine their outputs, and ensures reliable information handoffs. The system includes a Planner, Executor, Verifier, and Coordinator, working together to manage tasks, contexts, and errors, including dynamic replanning. Evaluations show VERIMAP outperforms existing single and multi-agent baselines on diverse tasks like math, coding, and question answering, enhancing system robustness and interpretability.
Large language models (LLMs) are increasingly being used to tackle complex tasks, often requiring multiple specialized AI agents to work together. However, this collaboration introduces significant challenges in how these agents plan, coordinate, and verify their work. Common problems arise not just from faulty reasoning, but from subtle misunderstandings in task interpretation, output formats, or how information is passed between agents.
To address these issues, researchers have introduced VERIMAP, a new framework designed for multi-agent collaboration that incorporates verification directly into the planning process. VERIMAP’s planner breaks down complex tasks into smaller subtasks, maps out their dependencies, and defines clear ‘passing criteria’ for each subtask. These criteria are encoded as verification functions (VFs), written in both Python code and natural language.
The VERIMAP system is built around four main components: the Planner, the Executor, the Verifier, and the Coordinator. The Verification-Aware Planner is central, not only decomposing tasks into a directed acyclic graph (DAG) of subtasks but also generating specific VFs for each. It ensures a precise flow of information by enforcing structured inputs and outputs (like JSON objects) and using consistently named variables across the entire plan. This means downstream agents can reliably use outputs from upstream agents, reducing ambiguity.
For each subtask, the planner creates two types of VFs. Python VFs are used for tasks with clear functional or structural requirements, providing deterministic checks for output type, format, and correctness. Natural language VFs are used for tasks requiring more subjective or open-ended judgments, such as summarizing text, guiding a verifier agent with semantic criteria.
The Executor is responsible for completing its assigned subtask using the planner’s instructions and any necessary context from previous tasks. These executors are typically LLMs using general-purpose agent methods, like ReAct-style agents, and can invoke external tools. Importantly, they are not exposed to the overall global task, allowing them to focus on their specific, well-scoped subtask. This modularity means smaller, more cost-efficient models can be used for execution.
After an executor completes a subtask, the Verifier steps in. It evaluates all the VFs against the executor’s structured output. If any VF fails, the subtask is marked as failed. The verifier also collects signals, such as error traces from Python VFs or explanations from LLM-based VFs, to guide subsequent retries.
The Subtask Coordinator acts as the central orchestrator. It sequences tasks according to the plan, manages the context passed between agents, monitors execution and verification, and handles errors. If a subtask fails verification after multiple retries, the coordinator triggers a replanning phase, generating a revised task plan based on the execution traces. This adaptive approach prevents error propagation and enhances overall task correctness.
VERIMAP has been evaluated on a range of datasets covering mathematics, coding, and question answering. The results show that it consistently outperforms both single-agent and other multi-agent baseline systems. For instance, it achieved significant gains on challenging benchmarks like BigCodeBench-Hard and Olympiads. The framework’s ability to replan and refine tasks based on detailed verification feedback is a key factor in its superior performance.
The analysis of verification functions revealed that the planner intelligently adapts the type and complexity of VFs to the task domain. For programming tasks, it generates more Python VFs, while for text-based tasks, it relies more on LLM-based VFs for semantic checks. This tailored approach leads to lower false positive rates in verification, meaning it’s better at correctly identifying when an execution has truly failed.
While VERIMAP generally incurs higher costs than single-agent methods due to the added verification and retry mechanisms, this overhead is partially offset by its ability to delegate execution to less costly models. The cost increase is often justified by the significant performance gains, especially on more difficult tasks where verification and replanning are crucial for achieving correct results.
A case study involving an Olympiads math problem highlighted VERIMAP’s effectiveness. Even when an executor made an initial mistake, the planner-generated Python verification function, combined with necessary context, successfully identified the error and provided feedback. This allowed the executor to self-correct and arrive at the right solution, a feat missed by a baseline system with generic natural language verification.
Also Read:
- Guiding AI to Better Answers: Exemplar-Guided Planning for Knowledge Graph Question Answering
- Enhancing LLM Multi-Agent Reasoning Through Strategic Self-Play
In conclusion, VERIMAP offers a robust and interpretable framework for multi-agent collaboration by tightly integrating planning with verification. Its planner-generated verification functions enable reliable coordination, iterative refinement, and improved performance across diverse and complex tasks. You can read the full research paper for more details here.
