acceptodds
Under review as a conference paper at ICLR 2027

SkeletonPlan: Experience-Guided Decision Skeletons over Compositional Constraint Programs

Abstract

Neuro-symbolic mulit-agents methods have become a promising solution for Real-world agent planning which requires coordinating heterogeneous decisions under numerous explicit and implicit constraints. However, existing neuro-symbolic planners commonly expand planning requirements into lengthy collections of low-level constraints, obscuring the higher-level dependencies among decision families and increasing the representation burden placed on planning agents. They also solve the resulting models either jointly or through decompositions fixed before inference, preventing the solving structure from adapting to the feasibility bottlenecks of each instance; moreover, effective solving structures discovered for one instance are rarely abstracted and reused across related problems. To address these limitations, we propose SkeletonPlan, a neuro-symbolic multi-agent framework that combines a compositional representation of constraint structure with instance-adaptive organization of symbolic solving. First, SkeletonPlan represents recurring constraint patterns as executable compositions over typed and indexed variable families, making family-level dependencies explicit to planning agents while preserving deterministic compilation into the complete constraint model. Based on this structural representation, a constraint-guided skeleton agent selects interface families whose commitments are expected to shape downstream feasibility and constructs an instance-specific organization for symbolic solving; full-model completion verifies whether the selected commitments extend to a solution of the complete constraint system. Finally, SkeletonPlan learns an online structural memory from solver and evaluator feedback. The memory distills recurring observations, guidance, and exceptions into compact natural-language advice that informs route, interface, and support decisions on later instances, while concrete assignments and final validity remain the responsibility of the symbolic solver. Experiments on Travelplanner demonstrate that SkeletonPlan achieves state-of-the-art planning performance. while ablation studies confirm the respective contributions of compositional constraint representation, instance-adaptive skeleton construction, and online structural memory learning.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
neuro-symbolic planning, constraint programming, large language models, compositional constraints, adaptive decomposition

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_pVGbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how to improve symbolic solving for constrained planning tasks with tightly coupled decisions under a limited computation budget. It proposes SkeletonPlan, which represents planning requirements as compositional constraint programs and uses an LLM agent to choose between joint solving and a two-stage strategy that first commits to selected decisions and then completes the full plan. The framework further learns reusable textual guidance from execution feedback to improve the selection of these solving strategies and decision interfaces. Experiments cover TravelPlanner and three NaturalPlan tasks. In the reported 180-instance TravelPlanner replay, SkeletonPlan achieves a final pass rate of 95.00%, compared with 90.56% for joint solving and 59.44% for its empty-memory variant. On NaturalPlan, it reports an average accuracy of 93.33% using disjoint task-specific memory-learning and evaluation subsets.

Critical strengths
  1. A flexible neuro-symbolic solving framework. The paper proposes a framework that adapts solver organization to individual planning instances. It can choose between joint and two-stage solving and select which decision families and constraints enter the first-stage skeleton. Combined with guidance learned from execution feedback, this offers greater flexibility than using a fixed solving strategy.
  2. Promising empirical performance on planning tasks. The reported experiments demonstrate strong performance on TravelPlanner and three NaturalPlan tasks. On TravelPlanner, SkeletonPlan reports a final pass rate of 95.00%, exceeding the reported results of the compared neuro-symbolic methods, including RigorFormal at 93.30%. These results provide empirical support for the framework’s potential effectiveness in constrained planning.
Critical weaknesses
  1. Comparability of results across different backbone models. The proposed method and several published baselines use different backbone models, which makes it difficult to separate the contribution of the framework from differences in model capabilities. While the within-framework ablations provide useful comparisons, the performance advantage over existing methods would be more convincing with comparisons using a shared backbone and evaluation protocol.
  2. Clarification of the TravelPlanner evaluation split. There appears to be an inconsistency between the main text and Appendix H regarding the TravelPlanner evaluation. The main text describes the results as held-out evaluation, whereas Appendix H states that the same 180 instances were used to provide memory-learning evidence and evaluate the learned memory. Clarifying this distinction would be helpful. If the protocol follows the appendix, the reported improvement would demonstrate effectiveness on previously encountered instances, while generalization to unseen TravelPlanner instances would remain unclear.
Questions for authors
  1. Could you provide a comparison with an existing neuro-symbolic method using the same backbone model and evaluation split?
  2. Were the 180 TravelPlanner evaluation instances also used for memory learning? Please clarify the apparent discrepancy between the main text and Appendix H.
  3. Could you report results on the official TravelPlanner test set, using memory learned from a disjoint split and frozen during evaluation?
  4. Could you provide a learning curve showing performance on a fixed held-out set after each memory update?
  5. Have you explored allowing the agent to choose the number of solving stages, including more than two, instead of using a fixed two-stage procedure?
Reviewer_6R8DOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes SkeletonPlan, a memory-augmented adaptive solving framework for agent planning. Specifically, the agents formulate planning problems as constraints and then determine the solving strategy based on the characteristics of the problem and historical experience. If hierarchical solving is selected, the agents identify key variable families and constraints, allowing the solver to solve the corresponding subproblem first, and then incorporate the resulting partial solution into the original constraints for global solving. Solving information is summarized into natural-language experiences to guide subsequent tasks. The authors evaluate SkeletonPlan against baselines on the TravelPlanner dataset and conduct generalization experiments on the NaturalPlan dataset.

Critical strengths

The idea proposed in this paper of using large language models to identify key variables and constraints for solving subproblems is somewhat insightful.

Critical weaknesses

The experiments in this paper fail to demonstrate the superiority of the proposed method. In the experiments on both TravelPlanner and NaturalPlan, all baselines use backbone models different from the backbone model used in this paper (DeepSeek-Flash). The paper should investigate whether the proposed framework can outperform previous frameworks under the same backbone model.

Furthermore, some statements made by the authors themselves in the paper acknowledge and further exacerbate concerns about the credibility of certain conclusions. For example, at line 435, the authors state: "Because published systems may use different random partitions, their values are contextual rather than paired comparisons." At line 427, the authors state: "These values provide context rather than a controlled comparison because the published systems use different backbones and may use different evaluation partitions." In Appendix H of the supplementary material, the authors explicitly state: "Since the same 180 instances supplied the memory evidence, these values diagnose the mechanism but do not constitute a held-out generalization result."

In addition, the paper is not clearly presented. Some key details are missing from the methodological description. For example, the algorithm that the authors state is provided at line 188 cannot be found. Furthermore, the paper uses formal mathematical language with undefined symbols (e.g., J in Equation (2)) to describe the method, while lacking concrete examples, making the paper difficult to understand. Additionally, the paper lacks an AI use statement.

Questions for authors

How does the paper's framework perform compared with the baselines when using the same backbone model?

The authors themselves are also aware of the lack of rigor in some experiments. Please provide corresponding rigorous versions of these experiments.

Reviewer_AKh4OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SkeletonPlan, a multi-agent framework for multivariable planning tasks described in natural language. The framework first compiles natural-language requirements into a standardized encoding consisting of variable families, constraint templates, and support relations. Then, based on the problem structure and historical experience, the skeleton agent chooses between joint and hierarchical solving and determines the interface variables and related constraints. Finally, a symbolic solver completes the solving process. The framework also summarizes solver diagnostics and task evaluation results into natural-language structural memory to guide the solving of subsequent instances.

Experiments are conducted on TravelPlanner and NaturalPlan. On TravelPlanner, learned memory improves the final success rate from 59.44% to 95.00% and significantly reduces full-model completion conflicts. The NaturalPlan experiments cover Calendar Scheduling, Meeting Planning, and Trip Planning to evaluate the applicability of the method to different planning tasks. The ablation experiments further compare joint solving, fixed-width interfaces, and adaptive skeleton strategies.

Critical strengths
  • The paper establishes a clear division of responsibilities between the language model and the symbolic solver. The language model is responsible for understanding the problem structure and organizing the solving process, while the symbolic solver is responsible for concrete assignments and full-constraint verification. This design can make full use of the respective strengths of LLMs and solvers and reduce decision biases caused by LLM hallucinations and subjective factors.

  • The experimental effects of structural memory and adaptive skeletons are relatively significant. Learned memory not only improves the final success rate but also significantly reduces completion conflicts caused by interface commitments. The ablation comparisons among joint solving, fixed-narrow interfaces, fixed-broad interfaces, empty memory, and learned memory also provide relatively good evidence for the effects of interface selection and experience reuse on framework performance.

Critical weaknesses
  1. A lack of fine-grained analysis of end-to-end pipeline stability.

    Although the framework improves final planning accuracy, it also introduces more interfaces between language models and symbolic programs, as well as additional mathematical abstraction steps. For example, the agent must produce structured decisions according to a predefined schema and select the solving route, interface variable families, and support constraints. These decisions must also be successfully completed by the full model within the given time budget. Formatting errors, inappropriate structural choices, infeasible completion, or solver timeouts may all cause the entire task to fail. The reported results already show relatively high failure rates under some settings, while the long-tail latency of the final method approaches the solver time limit. However, the current experiments do not sufficiently separate the sources of failure at different stages. The authors should report the numbers and proportions of schema validation failures, agent correction failures, skeleton unsatisfiability, full-model completion failures, solver timeouts, and formalization or decoding errors. Such an analysis is important for comprehensively evaluating pipeline stability and locating the weak points of the system. It would also be helpful for possible follow-up research.

  2. A lack of evaluation of adaptability to different underlying models.

    The framework requires the language model to perform structured output, understand constraint structures, select solving routes and interfaces, and summarize and reuse experiential memory. Therefore, its performance may be affected by the model’s instruction-following and structural reasoning capabilities. The current ablation experiments demonstrate that, in the current implementation using DeepSeek-Flash as the skeleton policy model, learned memory and adaptive mechanisms can improve performance. However, they do not show whether these gains can be consistently extended to other models or characterize the framework’s sensitivity to the capabilities of the underlying model. In addition, the paper does not sufficiently specify the backbones used by the semantic agent, constraint agent, and memory updater. The authors should clarify the models and configurations of the neural modules and conduct controlled evaluations using different model families or model scales under unified experimental conditions.

  3. Minor weakness: A link is missing in the “Planning Problem” subsection of Section 3. (Appendix ??)

Questions for authors
  1. Could the authors provide a detailed classification of end-to-end failures, including structured-output or schema-validation failures, failures after a bounded number of corrections, skeleton unsatisfiability, full-model completion failures, solver timeouts, and formalization or decoding errors? At which stages do the remaining failed instances mainly occur?

  2. Please clarify which models, prompts, and decoding configurations are used by the semantic agent, constraint agent, skeleton policy, and memory updater. Do all these modules use DeepSeek-Flash?

  3. Could the authors evaluate SkeletonPlan with different model families or model scales while keeping the data, constraint programs, prompts, solving budgets, and evaluation protocol unchanged, and report the structured-output failure rate, number of corrections, completion success rate, final accuracy, and computational cost?

Reviewer_X3YVOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

SkeletonPlan organizes wide-horizon planning around instance-specific structural dependencies via three contributions: (i) a compositional constraint program over typed, indexed variable families that compiles deterministically into a complete executable solver model; (ii) an LLM "skeleton agent" that chooses an instance-specific route, interface families, and support kinds, verified by full-model completion; and (iii) an online learner that distills solver and evaluator feedback into a bounded natural-language structural memory.

Validation: Main experiment on TravelPlanner and on NaturalPlan; ablations cover Joint, Fixed-Narrow, Fixed-Broad, and Adaptive±memory variants

Critical strengths
  1. Conceptual contribution and clear correctness scoping. Learning how to organize symbolic solving (route, interface, support) rather than learning assignments, with full-model completion as the sole acceptance criterion, is a clean and well-motivated separation that yields an explicit acceptance-soundness guarantee and is distinct from prior work

  2. Clean ablation design. The fixed-variant controls (Joint, Fixed-Narrow, Fixed-Broad) versus adaptive skeletons isolate the roles of decomposition, interface width, and memory, and the results are reported with latency/token costs rather than hidden, even though the resulting evidence damages the paper's claim, the design is informative.

Critical weaknesses
  1. The headline result is unsupported and plausibly an artifact of within-distribution memory. The adaptive policy without memory is worse than every deterministic control (59.44% vs. 90.56% Joint and 90.00% Fixed-Broad); only the learned-memory variant separates from the pack, in a single-seed, same-distribution setting with no controlled baselines. As Table 1's comparison uses published numbers from different backbones with unstated splits (and Table 2 itself concedes its references are "contextual rather than paired"), the abstract's "state-of-the-art" claim is not established

  2. The manuscript is a non-compliant, incomplete draft. There is no AI-use disclosure; essential components are deferred to a nonexistent appendix; Table 1 just bolds the authors method independently of its performance. the text reads as work in progress (Table 3 is labeled "currently completed"); and reported costs complicate the "efficient balance" claim — p95 latency is 117.87s against the 120s budget, with +137% median latency and +43% tokens, while residual failures are never decomposed

Questions for authors
  1. Why does empty-memory adaptation (59.44%) underperform all deterministic controls, and what are the route/interface distributions in the two memory conditions?
  2. Is the 35.56-point gain stable across ≥5 seeds with variance/significance tests, and does learned memory transfer under distribution shift or across NaturalPlan tasks?
  3. What is the failure decomposition of the remaining 9 failures, and what share of runs approaches the 120s budget given p95 = 117.87s (given timeouts establish neither feasibility nor infeasibility)?
  4. Can Joint, Fixed-Broad, and a solver-augmented baseline be run under identical split, budget, and evaluator to test the null hypothesis that the gain is a budget-allocation artifact?
  5. Please state the skeleton-model vs. full-model relation as a proposition (is the skeleton constraint set a subset/logical consequence of the full system?) and specify how J, I_0, and support kinds are mechanically determined.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.