Aligning Progress and Feasibility: A Neuro-Symbolic Dual Memory Framework for Long-Horizon LLM Agents

Bin Wen; Ruoxuan Zhang; Yang Chen; Hongxia Xie; Lan-Zhe Guo

cs.AIApr 3, 2026

Aligning Progress and Feasibility: A Neuro-Symbolic Dual Memory Framework for Long-Horizon LLM Agents

Authors: Bin Wen, Ruoxuan Zhang, Yang Chen, Hongxia Xie, Lan-Zhe Guo

Organizations: Nanjing University · Jilin University

Abstract

Large language models (LLMs) have demonstrated strong potential in long-horizon decision-making tasks, such as embodied manipulation and web interaction. However, agents frequently struggle with endless trial-and-error loops or deviate from the main objective in complex environments. We attribute these failures to two fundamental errors: global Progress Drift and local Feasibility Violation. Existing methods typically attempt to address both issues simultaneously using a single paradigm. However, these two challenges are fundamentally distinct: the former relies on fuzzy semantic planning, while the latter demands strict logical constraints and state validation. The inherent limitations of such a single-paradigm approach pose a fundamental challenge for existing models in handling long-horizon tasks. Motivated by this insight, we propose a Neuro-Symbolic Dual Memory Framework that explicitly decouples semantic progress guidance from logical feasibility verification. Specifically, during the inference phase, the framework invokes both memory mechanisms synchronously: on one hand, a neural-network-based Progress Memory extracts semantic blueprints from successful trajectories to guide global task advancement; on the other hand, a symbolic-logic-based Feasibility Memory utilizes executable Python verification functions synthesized from failed transitions to perform strict logical validation. Experiments demonstrate that this method significantly outperforms existing competitive baselines on ALFWorld, WebShop, and TextCraft, while drastically reducing the invalid action rate and average trajectory length.

Figures & tables

Figure 1: Overview of our neuro-symbolic dual memory framework. The proposed system explicitly separates local feasibility alignment from global progress alignment according to the distinct reasoning demands of the two objectives. Top (Offline Phase): Failed interactions are compiled into executable symbolic verifier rules to construct the symbolic Feasibility Memory, while successful trajectories are distilled into stage-anchored procedural blueprints to form the neural Progress Memory. Bottom (Inference Phase): At inference time, Progress Memory provides stage-aware guidance for proposing progress-consistent actions, while Feasibility Memory performs symbolic feasibility verification and iterative refinement before execution.

Method	ALFWorld	WebShop		TextCraft
	Success Rate (%)	Success Rate (%)	Score	Success Rate (%)
ReAct ( Yao et al., 2022b )	76.87	32	0.5010	62
Reflexion ( Shinn et al., 2023 )	82.66	35	0.5204	69
ADaPT ( Prasad et al., 2024 )	72.39	32	0.5355	77
StateAct ( Rozanov and Rei, 2025 )	63.43	17	0.2973	68
ExpeL ( Zhao et al., 2024 )	85.07	29	0.4582	88

Table 1: Main Results. We compare our proposed dual-alignment framework against competitive baselines on ALFWorld, WebShop, and TextCraft. Our method achieves consistent and substantial improvements in both success rates and task scores across all domains.

Method	SR $\uparrow$	IAR $\downarrow$	ATL $\downarrow$
Ours w/o both memories	76.87	16.73%	22.57
Ours w/o Progress Memory	90.30	12.98%	20.30
Ours w/o Feasibility Memory	85.82	26.33%	20.49
Ours	94.78	11.81%	14.60

Table 2: Ablation study on the components of our dual-alignment framework. Evaluated on the full ALFWorld test set. Removing either Progress Memory or Feasibility Memory leads to performance degradation. The full system achieves the highest Success Rate (SR) and lowest Invalid Action Rate (IAR) alongside optimized Average Trajectory Length (ATL), demonstrating the complementary roles of the two memory modules.

Progress Setup	Blueprint	Success Demos	Retrieval	SR $\uparrow$	ATL $\downarrow$
No Memory	$\times$	$\times$	$\times$	90	21.22
Standard RAG	$\times$	$\checkmark$	Task	84	21.64
Blueprint + Task	$\checkmark$	$\checkmark$	Task	92	16.42
Blueprint + Anchor	$\checkmark$	$\checkmark$	Anchor	94	16.18

Table 3: Performance impact of different Progress Memory configurations. The results demonstrate that standard task-level retrieval is insufficient; combining structured procedural blueprints with anchor-level retrieval yields the highest success rate and best efficiency.

Feasibility Setup	SR $\uparrow$	IAR $\downarrow$	ATL $\downarrow$
No Rules	88	21.63%	20.90
Prompt Rules	84	12.11%	18.16
Verifier Rules	94	11.00%	16.18
Prompt + Verifier	92	4.66%	16.32

Table 4: Comparison of different Feasibility Memory constraints. Compared to purely prompt-based constraints which can lead to overly conservative behavior, executable Verifier Rules achieve the best balance between reducing local invalid actions (IAR) and maintaining continuous global progress (SR and ATL).

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Environment	Positive Transitions	Negative Transitions	Candidate Rules	Zero-FP Rules	Selected Rules
ALFWorld	644	159	17	15	6
WebShop	190	50	8	8	2
TextCraft	497	219	7	7	3

Appendix

Table 5: Environment-wise statistics of rule verification and pruning. Positive transitions are used to eliminate false-positive rules, and negative transitions are used for greedy coverage-based selection. The final rule bank used at inference time is intentionally compact.

Long-Horizon LLM Agents

Long-horizon large language model agents plan, use tools, and preserve task state across extended, multi-step interactions.

See all 446 papers

HiMAC: Hierarchical Macro-Micro Learning for Long-Horizon LLM Agents
Mar 1, 2026Hongbo Jin, Rongpeng Zhu, Jiayu Ding +2Long-Horizon LLM Agents Long-Horizon Agent Tasks
School of Electronic and Computer Engineering, Peking University
Meta-Cognitive Memory Policy Optimization for Long-Horizon LLM Agents
May 28, 2026Ziyan Liu, Zhezheng Hao, Yeqiu Chen +7Long-Horizon LLM Agents Memory-Augmented Language Model Agents
University of Science and Technology of China · Zhejiang University · Tencent
AdMem: Advanced Memory for Task-solving Agents
Jun 5, 2026Runzhe Wang, Huilin Lu, Shengjie Liu +2Continual Learning for LLM Agents LLM Agent Memory
Princeton University · Amazon · Arm

Mar 1, 2026J/K move · Enter open · S save

HiMAC: Hierarchical Macro-Micro Learning for Long-Horizon LLM Agents

Hongbo Jin, Rongpeng Zhu, Jiayu Ding, Guibo Luo+1

School of Electronic and Computer Engineering, Peking University

Long-Horizon LLM Agents Long-Horizon Agent Tasks Agentic RL RL for LLM Agents Long-Horizon RL Hierarchical RL

Open paper AskPDF arXiv

Large language model (LLM) agents have recently demonstrated strong capabilities in interactive decision-making, yet they remain fundamentally limited in long-horizon tasks that require structured planning and reliable execution. Existing approaches predominantly rely on flat autoregressive policies, where high-level reasoning and low-level actions are generated within a single token sequence, leading to inefficient exploration and severe error propagation over extended trajectories. In this work, we propose HiMAC, a hierarchical agentic RL framework that explicitly decomposes long-horizon decision-making into macro-level planning and micro-level execution. HiMAC models reasoning as a structured blueprint generation process followed by goal-conditioned action execution, enabling robust long-horizon planning within LLM-based agents. To train this hierarchy efficiently, we introduce a critic-free hierarchical policy optimization paradigm that extends group-based reinforcement learning to bi-level structures through hierarchical relative advantage estimation. Furthermore, we propose an iterative co-evolution training strategy that alternates between planner exploration and executor adaptation, mitigating the non-stationarity inherent in hierarchical learning. Extensive experiments on ALFWorld, WebShop, and Sokoban demonstrate that HiMAC consistently outperforms strong prompting and reinforcement learning baselines, achieving state-of-the-art performance and substantially improved sample efficiency across both text-based and visually grounded environments. Our results show that introducing structured hierarchy, rather than increasing model scale alone, is a key factor for enabling robust long-horizon agentic intelligence.

Abstract

Long-Horizon LLM Agents

Explore similar work

HiMAC: Hierarchical Macro-Micro Learning for Long-Horizon LLM Agents

Meta-Cognitive Memory Policy Optimization for Long-Horizon LLM Agents

AdMem: Advanced Memory for Task-solving Agents