Message Passing Framework for Recursive Solution of Word-Math Problems

This repository presents a recursive message-passing framework that coordinates specialized agents to solve complex word-based math problems by breaking them down into smaller sub-problems. The framework recursively applies agents on each sub-problem, enabling efficient and accurate solutions through adaptive tool selection.

Recursion is a cornerstone of human cognition, crucial for both language and reasoning. In language, it enables the hierarchical structuring of sentences, allowing phrases and clauses to nest within each other to convey nuanced meanings. For example, in "The cat [that chased the mouse [that stole the cheese]] is sleeping," recursive embedding organizes complex ideas with grammatical clarity. Generative grammar relies on recursion to explain how finite rules produce an infinite variety of sentences, highlighting the creative capacity of human language. In computational linguistics, recursive structures are central to parsing algorithms, which process intricate sentence patterns in natural language processing tasks.

In reasoning, recursion underpins problem-solving by breaking complex challenges into simpler subproblems. It fosters creativity and abstract thinking, evident in fields like mathematics and multi-step planning. The Socratic method exemplifies recursive reasoning, as it uses iterative questioning to refine ideas, challenge assumptions, and guide participants toward deeper understanding. This recursive dialogue mirrors the way humans explore concepts, revisiting and refining thoughts to reach clarity. While recursion is immensely powerful, balancing its complexity is vital to avoid inefficiencies or overthinking. Overall, recursion is foundational to language, reasoning, and the philosophical inquiry that drives human intellect.

Overview

1. Recursive Problem Solving: Each problem is recursively broken down into smaller sub-problems, enabling finer-grained application of agents at each step. This recursive approach allows for handling complex, multi-step problems by tackling smaller, manageable parts first and then integrating their solutions.

2. Agent Roles:

   • Problem Classification Agent - Analyzes each sub-problem to determine its type (e.g., algebra, calculus) and recommends the initial tool (Chain of Thought (CoT), or Program-aided Language (PAL)).
   • Tool Selection Agent - Chooses the optimal tool based on recommendations and past performance, balancing exploration and exploitation through either randomization or bandit algorithms.
   • Execution Agent - Executes the chosen tool for each sub-problem, generating initial solutions that can be further refined.
   • Feedback Agent - Validates the solution of each sub-problem, providing feedback and suggesting adjustments or alternative tools if necessary.
   • Explanation Agent - Compiles detailed explanations for each step or the final solution, ensuring interpretability and clarity for the user.

The execution agent is the main agent that orchestrates the execution of agent calls.

Key Features

• Recursive Solution Generation: Each complex math problem is decomposed into sub-problems. The message-passing agents are then recursively applied to each sub-problem, allowing for precise, step-by-step solutions.

• Adaptive Tool Selection: Uses an exploration-exploitation strategy (contextual multi-armed bandit algorithms with Thompson Sampling) to select the most suitable tool for each sub-problem. This adaptive selection enhances problem-solving efficiency by learning from feedback.

• Flexible, Modular Architecture: The framework's agents communicate through a message-passing protocol, allowing dynamic iteration and retooling based on feedback. Each agent's responsibilities are modular, making it easy to expand the framework with additional tools or more complex recursive logic.

Contextual Multi-Armed Bandit Tool Selection

It has been observed that different tools have different performance characteristics. Some tools are better at solving certain types of problems, while others are better at solving other types of problems. The contextual multi-armed bandit (C-MAB) algorithm is used to select the most suitable tool for each sub-problem. This adaptive selection enhances problem-solving efficiency by learning from feedback.

The task class classfies the subproblems into different categories, and the C-MAB algorithm is used to select the most suitable tool for each sub-problem. The improves over tiem while solving the subproblems based on the feedbacks provided from the feedback agent.

Setup

1. create a .env to set the environment variables for LLM API key and endpoint. For OpenAI, .env looks like:

   API_SOURCE="openai"
   MODEL_NAME="gpt-4o-mini"
   OPENAPI_API_KEY = "sk-xxxx"

2. update awms/config.py to set the model name and endpoint

Example Output

A problem that is broken down into 4 sub-problems. One of the sub-problems is further broken down into 4 sub-problems. The final solution is the combination of the solutions of the sub-problems.