Call Me When Necessary: LLM s can Efficiently and Faithfully Reason over Structured Environments (2024)

Abstract: Large Language Models (LLMs) have shown potential in reasoning over structured environments, e.g., knowledge graphs and tables. Such tasks typically require multi-hop reasoning, i.e., match natural language utterance with instances in the environment. Previous works adopt LLMs to incrementally build a reasoning path, where LLMs either invoke tools or pick up items by step-by-step interacting with the environment. We propose Reasoning-Path-Editing (Readi), a novel framework where LLMs can efficiently and faithfully reason over structured environments. In Readi, LLMs initially generate a reasoning path given a query, and edit the path only when necessary. We instantiate the path on structured environments and provide feedback to edit the path if anything goes wrong. Experimental results on three KGQA and two TableQA datasets show the effectiveness of Readi, significantly surpassing previous LLM-based methods (by 9.1% Hit@1 on WebQSP, 12.4% on MQA-3H and 9.5% on WTQ), comparable with state-of-the-art fine-tuned methods (67% on CWQ and 74.7% on WebQSP) and substantially boosting the vanilla LLMs (by 14.9% on CWQ). Our code will be available on https://aka.ms/readi .

## introduction large language models (llms) have demonstrated remarkable performance in nlp fields @xcite @xcite . to further unleash their reasoning ability in complex scenarios, delicate strategies are proposed to equip llms with human-like thought process (e.g., chain-of-thought @xcite or leverage them as autonomous agents capable of planning, reflection and execution @xcite . one compelling scenario where llms showcase their potential is reasoning over structured environments (ses) @xcite . with dedicate schemas, ses (e.g., knowledge graphs, tables) abstract real-world semantics for representing, storing, and querying data with relational structures. for instance, freebase @xcite captures 45m entities and 3b facts over 100 domains, organized in triple patterns. the crux of successful reasoning lies in bridging the gap between natural language and the mechanism of how the ses are represented and operated @xcite . while llms exhibit promising capabilities, their performance often falls short when faced with multi-hop reasoning involving large-scale ses. to faithfully reason, prior works adopt an iterative way that start from certain elements (e.g., entity, relation in kg, column in table), instantiate on ses and then gradually expand the reasoning path while consuming just relevant portions instead of the entire environment @xcite @xcite . this step-by-step interaction could mitigate hallucination of llms to some extent. however, the reasoning efficiency is sacrificed and thus hinder the practical feasibility. for a simple constraint, say "the daughter of obama", such methods probably require two llmcalls to first query the relations around "obama" and then select "father_of" from returned candidates. moreover, at each step, llms make one choice based on history, making it prone to error propagation. alternatively, fine-tuned methods inject environments into model parameters by tuning with human-labeled supervision. during inference, they recall schema patterns to build reasoning paths @xcite @xcite @xcite without interaction with ses. this end-to-end paradigm is efficient. however, it is never ensured that the model output can be grounded on ses. study shows that 50% paths of @xcite failed to yield faithful results. in addition, they heavily rely on annotations, which are difficult to obtain for large-scale ses. further research is thus needed to achieve efficient (i.e., less llm-calls) and faithful (i.e., grounded on ses) reasoning over massive ses. therefore, we seek to propose an interaction paradigm that leverage llms to support complex reasoning on large-scale ses faithfully and efficiently. conducting empirical study on kgqa task, we find that 46%-60% of reasoning paths initially generated by llms can be well instantiated, which inspires us to fully exploit llm's intrinsic planning ability in complex reasoning. while the idea of plan-and-refine is straightforward and applied in various real world tasks @xcite @xcite , it's worth noting that there exists few research on application in ses when the initial plan encounters obstacles. in this paper, we propose reasoning-path-editing (readi), a novel framework that leverages the intrinsic planning ability of llms (figure 1 ). in readi, llms initially generate a reasoning path, which is then instantiated on ses to facilitate faithful reasoning. path editing is triggered only if corrections are necessary. this way, we alleviate the burden of step-by-step interaction for llms, resulting in improved overall efficiency. to harness the information of large-scale ses, instead of injecting the entire static ses into the model, we collect reasoning log as immediate feedback which includes details such as the position of stuck points, associated relations, half-way done instances, etc. this dynamic guidance refines the reasoning path more targeted and further enhances faithfulness. our experiments on question answering over knowledge graphs (kgqa) and tables (tableqa) demonstrate that readi surpasses existing solutions in terms of both llm-calls and accuracy. we summerize our contributions as follows: ## task definition reasoning over structured environments (ses), e.g., question answering over knowledge graphs (kgqa) and tables (tableqa), typically requires matching a question with instances in ses to constrain the answer. an intermediate reasoning path is a structural representation of the question, as a bridge between the question and ses. figure 2 exemplifies some reasoning paths and their instances on kg. note that a kg is a set of triple patterns, i.e., {(e, r, e ′ )|e, e ′ ∈ e, @xmath0, where e and r refers to the set of entity and relation, respectively. implementation -kb as a demo h path instances france compound node german nijmegen wz air. adjoin country airports contains example 𝑄𝑄2 what country bordering france contains an airport that serves nijmegen? reasoning path [nijmegen] @xmath1, the reasoning path p is conditioned by several constraints in q. it is worth noting that p can represent complex constraints, (i.e., p can be single-constrained or multi-constrained). a single-constrained p is from only one topic entity. for example, a sequence of relations from the entity to the answer (example q1) or a chain-of-thought @xcite . a multiconstrained p is from multiple topic entities, consisting of multiple paths to constrain the answer (example q2). correspondingly, we instantiate p on kg to obtain instances. for example q1, the reasoning path "@xmath2 following sun et al. (2018), we model reasoning over structured environments as an retrieve-thenreason task, where we leverage llms to build the reasoning path given q. then we reason over the path instances to obtain the answer. ## experiments to comprehensively evaluate the reasoning ability of readi on large-scale structured environments, we experiment on two complex tasks, kgqa and tableqa. (please refer to appendix a for detailed implementation of tableqa). ## analysis we further analyze readi's modules, reasoning path and efficiency on 1000 test samples of cwq. for fairness, we base all evaluation on our instantiation and reasoning modules. please refer to appendix d for more detailed analysis of readi. ## conclusion in this paper, we propose a novel framework readi where llms can reason over structured environments efficiently and faithfully. in readi, llms initially generate a reasoning path which is then instantiated on environments to facilitate faithful reasoning. path editing is triggered only if the instantiation gets stuck. we showcase the implementation of readi on knowledge graph, evaluate the effectiveness on kgqa and tableqa and analyze extensive features of readi. our work also shed lights on practically interaction between natural language and structured environments, where llms plays a crucial role to bridge the gap.