LRPLAN : A Multi-Agent Collaboration of Large Language and Reasoning Models for Planning with Implicit & Explicit Constraints (2025)

Abstract: Our goal is to build language model based multi-agent systems for complex planning problems involving multiple explicit and implicit constraints, some of which may be commonsense. Our initial investigations reveal that large language models (LLMs) are often unable to maintain consistency across the planning process, whereas large reasoning models (LRMs) struggle with handling implicit commonsense constraints. In response, we introduce LRPlan, a novel domain-independent, language-based multi-agent architecture where LLM and LRM-based agents collaborate at training time to abstract important patterns, heuristics and insights about the domain. At test time, they collaborate in implementing these learned patterns and insights for a new planning instance. We perform experiments on two datasets, TravelPlanner and TimeArena-Static, and use two LLM-LRM combinations from GPT and DeepSeek families. We find that LRPlan outperforms various multi-agent and single-agent baselines obtaining notably higher accuracy as well as cost efficiency. We make the code publiclyavailable.

## introduction planning, a cornerstone of artificial intelligence, involves generating a sequence of actions to achieve a specified goal while adhering to various constraints. we study planning problems specified in natural language, where some constraints may be explicit, i.e., directly stated in the input, and others implicit, often requiring commonsense reasoning. our goal is to develop domain-independent approaches that do not require human intervention per domain; rather, make use of minimal training data from that domain to invoke a domain-specific architecture for handling any new instance from the same domain. agentic architectures over modern large language models (llms), e.g., @xcite have the potential to tackle planning problems in a generalizable manner. however, by themselves, llms often encounter difficulties with complex, multi-constraint problems. they struggle with maintaining constraint consistency throughout the planning process and often cannot perform robust planning or self-verification on their own @xcite . a recent alternative are the large reasoning models (lrms), which are trained to "think" before generating responses @xcite and might be more suitable for planning. our initial explorations with lrms suggest that while they indeed exhibit better performance on problems with explicit constraints, they underperform if the domain has many implicit commonsense constraints. we hypothesize that, similar to a human brain, where specialized skills in right and left hemispheres work together for handling complex stimuli @xcite , agentic ai architectures will require collaboration between llms and lrms for solving such complex planning problems. in response, we design lrplan, a domainindependent, language-based, multi-agent architecture for complex planning that uses both llms and lrms at both training and test times. lrplan first generates reasoning traces over training samples in a domain. it then implements several agents that are tasked with inducing common patterns, heuristics and an understanding of mistakes by analyzing these traces. this acquired domain-specific understanding informs a simple, streamlined planning process for any new problem instance, involving just two components: initial plan generator and refiner. reasoning trace generation (train) and refinement of initial plan (test) are done by lrms, and all other agents use llms. to study the effectiveness of the architecture, we use two datasets, travelplanner @xcite plan: [{"days": 1,… "accom.": beautiful manhattan 1br…}, {"days": 2,… "accom.": beautiful manhattan 1br…}, …] query: "could you help design a 3-day trip for a group of 4 from las vegas to santa maria from march 10th to march 12th, 2022? we have a budget of $3,700. we have a preference for american and mediterranean cuisines." @xcite ✓ ✗ ✗ ✓ ✗ ✗ react @xcite ✗ ✓ ✗ ✓ ✗ ✗ reflexion @xcite ✗ ✓ ✗ ✓ ✓ ✗ self-refine @xcite ✓ ✓ ✗ ✓ ✗ ✗ multi-agent debate @xcite ✓ ✓ ✓ ✓ ✗ ✗ autoagents @xcite ✓ ✓ ✓ ✓ ✗ ✗ spp @xcite ✓ ✓ ✓ ✓ ✗ ✗ autobuild foot_0 @xcite ✓ ✓ ✓ ✓ ✗ ✗ agentverse @xcite ✓ ✓ ✓ ✓ ✗ ✗ llmfp @xcite ✗ ✗ ✓ ✓ ✗ ✗ llm-modulo @xcite ✗ ✓ ✓ ✗ ✗ ✗ pmc @xcite ✓ ✓ ✓ ✗ ✗ ✗ expel @xcite 2024) and timearena @xcite . since timearena is originally conceived as an online planning dataset, we reformulate it into the static planning setting, where a single final plan is outputted instead of repeated planner-simulator interaction. we compare lrplan with state-of-the-art multi-agent systems applicable to our setting. we use standard prompting, chain-of-thought prompting, autogen's autobuild 2 @xcite , and multi-agent debate techniques @xcite as strong baselines to compare with. fig. 1 shows the supremacy of lrplan on an example from travelplanner. we experiment on two families of models, ope-nai and deepseek, that both have at least one llm and lrm each. our results demonstrate that lr-plan outperforms all baselines on each model family obtaining notable accuracy gains. our best result is lrplan on timearena-static with gpt-4o and o3-mini achieving a 12.7 pt accuracy improvement over the closest baseline, mad with o3mini. similarly for travelplanner, our best result is lrplan with deepseek-v3 and deepseek-r1 achieving a 8.89 pt accuracy improvement over the closest baseline, autobuild with gpt-4o. moreover, lrplan's cost efficiency is superior to its nearest competitor model. additional ablations assess the value of llm-lrm collaboration versus using just llm or lrm. in summary, our main contributions are as follows. @xcite we study complex multi-constraint planning problems that contain both explicit and implicit constraints, including commonsense constraints. we propose lrplan, a multi-agent architecture that combines llms and lrms for this task. @xcite we reformulate timearena dataset to a static setting, and introduce evaluation metrics for this dataset. @xcite we perform several experiments on two domains and two model families to find that lrplan substantially outperforms the state of the art in both accuracy and overall costs. we release all code and timearena-static dataset for reproducibility and fostering further research on the topic. 1 ## related work planning has long been a central challenge in ai, traditionally addressed through classical planners @xcite @xcite that rely on domain-specific modeling and optimization. while effective in structured settings, these approaches require significant manual effort and lack adaptability. supervised machine learning and imitation learning techniques learn from examples of problems and their solutions; but need large-scale domain-dependent training data. the emergence of llms introduced new paradigms for planning via zero-shot prompting and chain-of-thought reasoning @xcite , enabling generalization without domainspecific training. however, single-agent llm frameworks @xcite @xcite often struggle with constraint consistency and implicit reasoning. multi-agent systems (mas) such as auto-build @xcite , autoagents @xcite , and agentverse @xcite improve task decomposition and collaboration, but frequently lack mechanisms for learning from cumulative past experiences. debatebased methods @xcite enhance reasoning through iterative critique but are resource-intensive. role-based mas like pmc @xcite and llm-modulo @xcite introduce structured agent roles, yet require manual domain adaptation and prompt engineering. recent work emphasizes learning from experience @xcite , enabling agents to reflect and adapt using past trajectories. however, these are typically llm-centric and do not leverage the complementary strengths of reasoning-focused models. in contrast, our proposed architecture, lr-plan, introduces a domain-independent, multiagent framework that synergistically combines llms and lrms. lrplan learns from reasoning traces to induce domain-specific heuristics and patterns, enabling robust planning with minimal domain-specific supervision. as opposed to previous works, in lrplan the validator is only being used on a very small number of training examples (4-10 per domain). the cost of validating this tiny set is negligible, a simple pass/fail verdict can be provided by a human expert in minutes or handled by an llm-based evaluator if a plan validator does not exist. unlike prior systems, lrplan handles both explicit and implicit constraints, including commonsense reasoning, and generalizes across domains without re-engineering. ## problem setting we wish to design planners that map a naturallanguage query q (planning problem instance) to a plan p using a structured, step-by-step sequence of actions, @xmath0, s 2 , . . . , s t ⟩, that satisfies two types of constraints: for each domain, as supervision, we are given a few-shot training set d @xmath1, v i )} n @xmath2. here v i : p @xmath3, fail} is a black-box validator that returns a binary correctness verdict for a candidate plan for each sample in training set. given d train , our problem is to design a language-agent system that, for unseen query q test , produces a plan p test that passes all implicit and explicit constraints. ## the lrplan framework lrplan is a domain-independent planner, i.e., applies to any domain out-of-the-box. specifically, it induces a test-time planner, which is targeted to a domain, without any human intervention. at a high level (see fig. 2 ), lrplan first prompts an lrm m with each of the n training samples q i to generate a plan p i along with a reasoning trace r i . the validator v i is then queried with the plan p i , which generates a pass/fail label v i that is added to the trace. all the labeled reasoning traces are collated and up to c samples per label (pass/fail) are then input to two meta-agents, pattern recognizer, and self-corrector. we call these meta-agents, because their output is at the domain-level, not at a query-level. pattern recognizer is an llm prompted to identify recurring structures (patterns) useful for solving problems in the domain. the output patterns are then provided to yet another meta-agent, rule extractor, whose job is to induce concrete rules required for a plan to be correct. we find that the use of two successive steps allows the llms to reflect on the domain better, with patterns denoting bottom-up first observations, and rules denoting a higher-level abstraction of these observations. finally, the self-corrector meta-agent is tasked with extracting insights for correcting an incorrect plan. these patterns, rules and insights are combined to automatically construct prompts for planner and refiner agents. given a test query q test , the planner agent drafts a candidate plan ptest guided by the domain's patterns and the rules. the refiner agent identifies and corrects any problems in ptest based on the self-corrector's insights to generate the output plan p test . we now describe these components in detail. ## datasets we conduct experiments on two challenging benchmarks: travelplanner and a static version of timearena, both requiring long-horizon planning under explicit and implicit constraints. we now describe the two datasets and evaluation metrics used in each. ## experimental setup through our experiments, we seek answers to the following research questions. (1) how does lr-plan compare with other domain-independent architectures for planning with multiple constraints? ( 2 ) what is the incremental value of using an llm-lrm combination compared to just using an llm or an lrm? (3) how valuable is each meta-agent in the lrplan architecture? ( 4 ) what is the nature of errors made by lrplan? experimental details. we use llms and lrms from two model families (one proprietary and one open source). we use a combination of gpt-4o and o3-mini as llm and lrm, respectively. in another setting, we use deepseek-v3 with deepseek-r1. we run the models using autogen library for inference, employing caching and setting temperature to 0.01 for reproducibility. we always use deepseek-r1 as the lrm to generate reasoning traces. this is because as of may 2025, o3-mini is a proprietary model which does not offer detailed reasoning traces via its api. baselines. for fair comparison in domainindependent planning, we wish to identify baselines that represent state-of-the-art multi-agent frameworks that minimize human intervention in agent configuration and prompt engineering. hence, we select autobuild 2 @xcite ,generalized multi-agent debate (mad) @xcite , and expel @xcite as our baselines. autobuild dynamically provisions a team of agents and orchestrates a group chat based on the input task description and query to derive a final response. the multi-agent debate involves iterative group interaction, typically among homogeneous agents over multiple rounds, to converge on a solution. expel extracts insights from reflexion @xcite traces generated on training samples and infers using these insights via a react @xcite framework. these approaches are suitable, as they automate key aspects of agent creation and interaction logic. this contrasts with alternative multi-agent methods that require significant manual effort in defining agent roles or crafting specific prompts for each agent in a domain. we also compare against a vanilla single-agent baseline that queries an llm ## conclusion we explored the capabilities of language models in solving complex multi-constraint planning problems, introducing a novel multi-agent architecture lrplan, which trains over a domain using very few training instances and creates a streamlined, simple and cost-efficient inference planning process for new instances of the domain. we reformulate timearena @xcite to a static setting for efficient and easier inference and explore the planning domains travelplanner @xcite and timearena-static using various methods, standard prompting, cot, mad @xcite , and autobuild @xcite , with both llms and lrms. we found that llms show poor results in adhering to explicit constraints while showing better results in implicit ones. on the other hand, lrms show poor results for implicit constraints, being good at explicit constraints. we show that the complementary nature of llms and lrms can be leveraged in a synergistic system to produce best results.