Exploring the Role of Reasoning Structures for Constructing Proofs in Multi-Step Natural Language Reasoning with Large Language Models (2024)

Abstract: When performing complex multi-step reasoning tasks, the ability of Large Language Models (LLMs) to derive structured intermediate proof steps is important for ensuring that the models truly perform the desired reasoning and for improving models’ explainability. This paper is centred around a focused study: whether the current state-of-the-art generalist LLMs can leverage the structures in a few examples to better construct the proof structures with in-context learning. Our study specifically focuses on structure-aware demonstration and structure-aware pruning. We demonstrate that they both help improve performance. A detailed analysis is provided to help understand the results.

## introduction large language models (llms) have played an essential role in a wide range of applications @xcite @xcite including intelligent agents @xcite . their ability to perform complex multi-step reasoning has become critical @xcite @xcite @xcite @xcite . in complex multi-hop reasoning tasks, the proof steps often form a graph but not just a chain. the capability to construct correct, structured proofs is essential for ensuring that llms perform the desired reasoning and important for the explainability of the reasoning models @xcite . in this paper, we perform a focused study, providing evidence to understand whether the stateof-the-art llms can leverage a few examples to better construct the proof structure with in-context learning. unlike previous work that fine-tunes the proof models @xcite @xcite , we focus on in-context learning @xcite since in many applications, the number of available examples with proof structures is small. in general, an important goal of generalist models is solving different tasks with the built-in ability and without extensive fine-tuning. in our research, we consider two key components that can utilize the known proof structures: (i) demonstration, and (ii) proof path search and pruning. we equip the state-ofthe-art llms, e.g., gpt-4 and llama-3-70b, with structure-aware demonstration and structureaware pruning. we set up our study with three benchmark datasets, entailmentbank @xcite , ar-lsat @xcite and prontoqa @xcite . the experiment results show that both structure-aware demonstration and structure-aware pruning improve performance. we provide a detailed analysis to help understand the results. ## related work recently, llms' reasoning ability has been significantly improved. chain-of-thought (cot) @xcite is arguably the simplest but effective way to elicit linear reasoning chains of llms. tree-of-thought (tot) @xcite can further provide deeper insights into the model's reasoning structures. however, tot has been applied to tasks such as game-of-24 and creative writing, but not to natural language entailment and reasoning tasks with complex proof structures. in this paper, we will compare our models to the cot and tot models. reasoning in natural language has been a central topic of artificial intelligence research since its inception, including the research in natural language inference @xcite @xcite @xcite . in addition to producing accurate results, another key ## method given a hypothesis h and context c consisting of evidence sentences, the objective of the task is to provide a proof graph g to prove h based on some of the evidence sentences in context c, if h can be proven. in entailment or multiple-choice questionanswering tasks, h is often a concatenation of a question q and a candidate answer, or sometimes a paraphrase of such a concatenation. since we will use both q and h to retrieve demonstrations and pro-pose reasoning steps, both q and h will be included in our input. as a result, each instance u in the task is a tuple @xmath0, h, c⟩. a proof database d, containing examples of structured proofs, is provided for searching demonstrations that will be used in in-context learning. these demonstrations are exemplars provided to llms to help them understand the task requirements and output format. formally, we denote p θ to be a pre-trained language model with parameter θ. suppose @xmath1, . . . , x n ) is a language sequence with n tokens, the probabilistic language model can be written as p θ (x) = n @xmath2,...,i-1 ). following yao et al. (2023), we use p prompt θ (y|x) to represent p θ (y|prompt(x)) , where prompt(x) is the input sentences x wrapped with the prompt instructions and templates; y is the output. in this paper, we hypothesize that the proof structures of similar examples can help llms to construct a structured proof for the target problem. in particular, we consider two key components that can utilize the known proof structures: demonstration and proof-path pruning. the overall architecture of our model is depicted in figure 1 and algorithm 1. at the high level, to support our study, this paper proposes a comprehensive framework consisting of six building blocks: structure-aware demonstration, candidate retrieval, reasoning step proposal, reasoning step evaluation, proof hint generation, and structure-aware pruning, which enables us to perform structure-aware proof construction, and based on that, to conduct a deep study on the advantages and limitations of this construction process within the in-context learning setup. as shown in figure 1 , given an example u with a question q, a hypothesis h, and context c, we first derive suitable demonstrations from the provided database d in the structure-aware demonstration stage. subsequently, the llm is prompted to retrieve c s , the subset of the context c, that will be used in the reasoning (candidate retrieval). specifically in the example in figure 1 , the llm returns sentences 4, 7, 12, 21, 23, and 24. with these retrieved sentences, the llm is asked to provide the next potential reasoning step @xcite . this can be performed in multiple iterations. for the first iteration, the llm provides two proof steps: sent7 & sent4, sent23 & sent12, and in the second iteration, the llm proposes two additional steps for each branch. we then evaluate each reasoning step @xcite . next, the model performs structure-guided path pruning and selection (structure-aware pruning). we note that for each retained branch, the llm is required to generate a proof hint to guide the next iteration (proof hint generation). in the example, we keep two branches and show the generated proof hint for the proposed step r p 1,2 . in the following subsections, we will discuss each component in detail and describe how the known proof structures are utilized. structure-aware demonstration. given an example @xmath3, h, c⟩ and a database d where instances feature structured proofs, the search for most similar demonstrations e can be expressed as @xmath4, d). usually, s is defined as manually selecting several fixed demonstrations @xcite or choosing the top k demonstrations with the example u based on the similarity @xcite . at the initial stage, we prompt llms to provide a guessed proof graph g a u of the example u which is used to find the most similar examples as the demonstrations. as the proof moves forward, the partially constructed proof tree will be simply merged into the guessed tree. this process follows the idea of the em algorithm. we first obtain the guessed structure through llms, and then generate one reasoning step based on the demonstrations with the highest similarity after encoding the example with this estimated structure. subsequently, we update the guessed structure based on the generated reasoning step. the generation of reasoning steps and the updating of the guess structure are performed iteratively. specifically, we use the graph attention network (gatv2) @xcite and calculate the similarity between the proof graph e a u and each candidate demonstration v's proof graph e v , which considers both the structure and content of the graphs. we choose the candidates with the higher similarity scores as the demonstrations. candidate retrieval. given @xmath5, h, c⟩, a proof hint m (discussed below), and a set of selected demonstrations e, the candidate retrieval component aims to retrieve a set of most relevant sentences c s : the proof hint m measures the difference between the current proof status and the hypothesis, which will be discussed later in the proof hint generation subsection. note that the retrieval models can be replaced by a search engine, but we focus more on reasoning itself. ## experiment set-up datasets. we perform experiments on three benchmark datasets, entailmentbank @xcite , ar-lsat @xcite and prontoqa @xcite . details can be found in appendix b. evaluation metrics. we evaluate the predicted proof graph g p against the golden graph g g using the following metrics: f1 over evidence (ev-f) @xcite , f1 over proof (pr-f) @xcite , and reasoning graph similarity (g sim) @xcite . details can be found in appendix e. baselines. we compare the proposed method with cot, self-consistency cot (cot-sc), tot, and reasoning-via-planing (rap) @xcite . each model is prompted with three demonstrations. details can be found in appendix c. ## experiment results we conducted experiments on the representative closed-source (gpt-3.5/gpt-4) and opensource llms (llama-2-70b/llama-3-70b). ## conclusion enabling llms to generate their proof structure is critical for the reliability and explainability of such models. by incorporating structure-aware components into the state-of-the-art llms, we demonstrate that llms can benefit from utilizing the given proof structures of similar examples. we find that measuring the gap between the intermediate steps and the final hypothesis can help narrow down the search space and enhance the performance. further analysis of sequential and non-sequential reasoning reveals that our model offers greater advantages in the more complex task of non-sequential reasoning.