Symbolic Working Memory Enhances Language Models for Complex Rule Application (2024)

Abstract: Large Language Models (LLMs) have shown remarkable reasoning performance but struggle with multi-step deductive reasoning involving a series of rule application steps, especially when rules are presented non-sequentially. Our preliminary analysis shows that while LLMs excel in single-step rule application, their performance drops significantly in multi-step scenarios due to the challenge in rule grounding. It requires anchoring the applicable rule and supporting facts at each step, amidst multiple input rules, facts, and inferred facts. To address this, we propose augmenting LLMs with external working memory and introduce a neurosymbolic framework for rule application. The memory stores facts and rules in both natural language and symbolic forms, enabling precise tracking. Utilizing this memory, our framework iteratively performs symbolic rule grounding and LLM-based rule implementation. The former matches predicates and variables of symbolic rules and facts to ground applicable rules at each step. Experiments indicate our framework’s effectiveness in rule application and its robustness across various steps and settings.

## introduction large language models (llms) @xcite @xcite have demonstrated impressive performance across diverse reasoning tasks. however, they still face challenges with multi-step deductive reasoning @xcite @xcite , where llms are provided with a set of facts and logical rules, and need to derive an answer to the query through a sequence of rule application steps. specifically, each step of rule application requires applying a specific rule to its supporting facts to deduce new conclusions. moreover, llms especially struggle when the surface ## framework complex reasoning often necessitates multi-step rule application amid non-sequential and irrelevant rules and fact. to address this, we propose a twostage paradigm for each rule application step: rule grounding and rule implementation. rule grounding anchors the applicable rules and supporting facts at each step. rule implementation then infers new facts based on the grounded rules and facts. following this paradigm, we introduce a working memory-based neurosymbolic framework for rule application. it first initializes the working memory with all facts and rules from the input context. it then iteratively performs multi-step rule application, each step involving symbolic rule grounding based on symbolic formulations of facts and rules, followed by llms-based rule implementation. this process continues until the query is solved or a maximum number of steps is reached. the detailed workflow is shown in figure 3 . ## related work llms with external memory llms @xcite have demonstrated remarkable performance across tasks, but struggle with complex reasoning that involves memorizing or grounding long-term information from context or interaction history. beyond extending llms' context length @xcite , recent advancements augment llms with external memory. @xcite ; @xcite equip llms agents with external memory modules to store and reference long-term dialogue history for better interaction. for knowledge-intensive tasks, @xcite ; @xcite encode long-form context into memory for retrieval and utilization. however, previous working memory mainly stores natural language or parametric entries, making accurate referencing and updating challenging. symbolic memory is further proposed to address this issue. chatdb @xcite uses databases as symbolic memory for precise information recording and processing, but is limited to product inventory. statler @xcite introduces symbolic world memory to maintain robot states for embodied reasoning. our work leverages external memory to store both natural language and symbolic facts and rules, enabling more precise rule grounding for multi-step rule application. rule application for reasoning rules are wellestablished principles abstracted from broad realworld observations @xcite , or predetermined constraints designed for specific situations @xcite . they serve as a crucial basis for drawing inferences in complex contexts by applying them to known facts to derive new conclusions. for example, logical reasoning @xcite @xcite involves applying rules to contextual facts to answer queries, with @xcite ; @xcite operating in a symbolic manner. constraint satisfaction @xcite applies rules to find solutions meeting all restrictions. complex reasoning requires multi-step deductive rule application, each step involving rule grounding and rule implementation for more faithful reasoning @xcite . we propose to iteratively perform these two processes in a neurosymbolic manner based on working memory. ## conclusion in this paper, we augment llms with an external working memory and propose a neurosymbolic framework for multi-step rule application to enhance llms' reasoning capabilities. the memory stores facts and rules in both natural language and symbolic forms, facilitating accurate retrieval during rule application. after writing all input facts and rules into the working memory, the framework iteratively performs symbolic rule grounding based on predicate and variable matching, followed by llm-based rule implementation. it effectively combines the strengths of both symbolic and llm methods. our experiments demonstrate the framework's superiority over cot-based and symbolicbased baselines, and show its robustness across various rule application steps and settings. in the future, we will extend our framework to incorpo-rate more backbone llms and datasets, especially on more complex and long-term reasoning tasks.