Evaluating Step-by-Step Reasoning through Symbolic Verification (2024)

Abstract: Pre-trained language models (LMs) have shown remarkable reasoning performance using explanations or chain-of-thoughts (CoT)) for in-context learning. On the other hand, these reasoning tasks are usually presumed to be more approachable for symbolic programming. To understand the mechanism of reasoning of LMs, we curate synthetic datasets containing equivalent (natural, symbolic) data pairs, where symbolic examples contain first-order logic rules and predicates from non-parametric knowledge bases (KBs), supporting automated verification of intermediate reasoning results. Then we revisit neuro-symbolic approaches and propose to learn from demonstrations containing logic rules and corresponding examples to iteratively reason over KBs, recovering Prolog’s backward chaining algorithm and supporting automated verification of LMs’ outputs. Comprehensive experiments are included to systematically compare LMLP with CoT in deductive reasoning settings, showing that LMLP enjoys more than 25% higher accuracy than CoT on length generalization benchmarks even with smaller model sizes.

## introduction there are emerging interests in leveraging lms to enable planning @xcite ), heuristic search @xcite and symbolic inference @xcite @xcite . among them, chain of thought prompting or scratchpads @xcite shows that taking (input, explanation, output) as in-context examples for lms can lead to significant performance gain in reasoning tasks. however, like many fine-tuning approaches, it can be difficult for these models to generalize compositionally @xcite , meaning they may struggle to apply their knowledge to solve new problems that * work done outside of amazon. involve novel combinations of information @xcite @xcite . one notable case is that lms would suffer from catastrophic performance degradation when tested on sequences longer than training ones (figure 1 ). as a solution, least-to-most prompting @xcite takes inspiration from symbolic programs and proposes to tackle the challenge by modularizing the prompt on the reduced problem. the divide-and-conquer strategy is useful to improve the reasoning ability of language models, but it also presents additional challenges: what are the appropriate representations for factual knowledge and in-context samples that can ensure the correctness of each individual reasoning step? how do natural language explanations compare to symbolic provenance, which is easily verifiable, when used as prompts for reasoning? our goal is to evaluate the natural and symbolic paradigms closely in order to answer these questions. to enable fine-grained comparison and gain insight into in-context learning for reasoning tasks, we study relational reasoning over both natural language and knowledge bases (kbs). kbs are particularly useful for this purpose because they are constructed using clear pipelines and strong su-pervision, which makes them reliable and easy to control. this allows us to verify and evaluate reasoning paths and provenances without the need for human-provided rationales or explanations @xcite @xcite @xcite . we study language models as logic programmers (lmlp) to enable few-shot learning from symbolic demonstrations and simultaneous planning in an explainable and scalable way. lmlp uses logic rule templates, examples, and pre-trained knowledge to iteratively perform in-context learning and answer relational queries. specifically, given a goal query as the in-context example that can be interpreted as a question answering (qa) task, lmlp searches or retrieves a related task example with a corresponding logic rule (figure 2 ). then the context and task description are concatenated as the input prompt for an autoregressive planning lm. at each step of generation, we use a masked translation lm to compare the similarity between the generated natural language sentences and encoded it into @xcite predicates in the kb. in this way, each generated sentence is transformed into the most similar predicate and the reasoning path is confined within the kb. the process is iterated until a predefined maximum iteration or the target of interest is reached (figure 2 ) and the generated reasoning path is evaluated manually. to evaluate the reasoning capability of cot and lmlp, we curate two datasets and design a series of experiments, aiming to compare two recent in-context learning paradigms and explore both symbolic and naturalistic scenarios. specifically, we adopt synthetic datasets containing (natural, symbolic) data pairs. the symbolic part contains predicates and first-order logic (fol) rules, which are well-suited for investigating the role of symbolic representations for few-shot reasoning. the natural part of our study includes a story written in natural language that describes a set of entities and relations, as well as the reasoning paths that connect them. these reasoning paths can be seen as explanations for the relationships and events described in the story. moreover, we create experimental settings that are unfavorable for lmlp since (i) we use gpt-2 and sentencebert as its backbones, which is known to be of much smaller scale compared to cot which is usually based on gpt-3 @xcite or palm (chowdhery prompt task: a's sister is c step 1: a's brother is b step 2: b's sister is c task: george's sister is nancy step 1: george's brother is dale step 2: dale's sister is nancy task: joseph's sister is katherine step 1: joseph's mother is mary prompt task: a's sister is c step 1: a's brother is b step 2: b's sister is c task: george's sister is nancy step 1: george's brother is dale step 2: dale's sister is nancy task: joseph's sister is katherine output joseph's mother is mary output mary's daughter is katherine et al., 2022a); (ii) lms are pre-trained over natural language sentences as opposed to kbs, which creates substantial gaps in semantics and representations, thus posing a grounding challenge where lms are known to be ineffective @xcite . controlled experiments on relational reasoning have shown that (i) cot prompting struggles to solve the compositionality challenge @xcite , while with explicit verification, lmlp can work more reliably as reasoning length increases by taking symbolic inputs that explicitly separate logic and control @xcite . (ii) while it is commonly believed that large pre-trained language models (lms) are not grounded in contexts that require rich experiences, experimental results suggest that in-context learning, which maps the conceptual structure of a space learned from text onto a new structured space, is sufficient to solve some challenging reasoning tasks over knowledge bases (kbs). (iii) lms struggle to effectively solve relational reasoning tasks without proper demonstrations containing the target relation and correct input-label mappings. this is supported by evidence in in-context examples, which are poorly understood and have many intricate design choices @xcite @xcite . retrieval-augmented generation. our study is also related to retrieval-augmented generation @xcite ) like knn-lm @xcite , dpr @xcite , ralm @xcite , and retro @xcite , which integrates parametric models with non-parametric kbs to address key lm challenges like knowledge staleness @xcite and hallucination @xcite , reasoning @xcite . we explore more controllable environments where the evaluation of intermediate reasoning can be automated, demonstrating that this verification process helps filter out incorrect reasoning paths. this, in turn, enhances reasoning performance by assessing how effectively language models can reason when instances of hallucination are minimized. ## methodology overview we consider the reasoning task with an srl query as the question and some background knowledge as the context. the relational information in the query and context can be expressed either using natural language or a (subject, relation, object) predicate/triplet. there is a kb with facts f and (fol) rules r to support the above qa. there are two equivalent ways for representing the problem, symbolic or natural language, which leads to the designs below. ## experiments we now describe the experimental setups, empirically evaluate lmlp and compare it with existing methods. see appendix c for full details of data preprocessing and performance evaluation. settings. we curate two datasets for evaluating the in-context learning capability of lms for reasoning: clutrr-lp and countries-lp, which are based on clutrr @xcite and countries @xcite datasets respectively. clutrr @xcite ) contains a group of kbs, where each node denotes a family member and edges are family relations. the target of clutrr dataset is to infer a two-family members' relationship that is not explicitly mentioned. the training set of clutrr consists of graphs that the target relation can be inferred by traversing a limited number of edges while the relation in the test set needs more traversing steps for inference, which allows controlled studies on compositionality. another intriguing property of clutrr is that there are ground truth one-to-one correspondances between kbs and natural language stories, which exactly suits our needs. countries @xcite concerns link prediction, where countries, regions, and sub-regions are entities and relations containing locatedin and neighborof. countries has three tasks, r1,r2, and r3, each requiring reasoning skills of increasing complexity @xcite . implementation details. for lmlp, we implement the planning lm p θ as gpt-2 @xcite , the translation lm t ϕ as sentence bert (sent-bert) (reimers and gurevych, 2019) based on hugging face transformers @xcite . the default model for translation lm is sentence-roberta-large and for planning lm is gpt2-large @xcite pretrained on large corpora by default. for cot, we follow the original paper @xcite to sample in-context samples. we conduct all the experiments on a machine with four nvidia titan xp (10gb) gpu cards. since prompt formats lead to significant performance variations @xcite , we propose to explore two simple design choices for lmlp and find that they can further boost the reasoning capacity. (i) multiple examples for prompting. denote n the number of examples we used in one proof task. ## concluding remarks in this study, we systematically examine incontext learning of language models (lms) from a symbolic reasoning perspective, demonstrating that lms can be prompted with logical demonstrations to generate plausible explanations for reasoning tasks over knowledge bases (kbs). our evaluation results show that constraining outputs of lms and ensuring intermediate reasoning correctness are important for reasoning performance, providing new insights into in-context learning and a mechanism to reduce incorrect reasoning through symbolic verification.