Multi-hop Database Reasoning with Virtual Knowledge Graph (2024)

Abstract: Application of LLM to database queries on natural language sentences has demonstrated impressive results in both single and multi-hop scenarios.In the existing methodologies, the requirement to re-encode query vectors at each stage for processing multi-hop queries presents a significant bottleneck to the inference speed.This paper proposes VKGFR (Virtual Knowledge Graph based Fact Retriever) that leverages large language models to extract representations corresponding to a sentence’s knowledge graph, significantly enhancing inference speed for multi-hop reasoning without performance loss.Given that both the queries and natural language database sentences can be structured as a knowledge graph, we suggest extracting a Virtual Knowledge Graph (VKG) representation from sentences with LLM.Over the pre-constructed VKG, our VKGFR conducts retrieval with a tiny model structure, showing performance improvements with higher computational efficiency. We evaluate VKGFR on the WikiNLDB and MetaQA dataset, designed for multi-hop database reasoning over text. The results indicate 13x faster inference speed on the WikiNLDB dataset without performance loss.

## introduction if open-domain question-answering models could accurately reason with large-scale facts in databases, it would make it feasible to substitute or augment existing database management systems with nlp technology @xcite . several benchmarks have been proposed @xcite @xcite , which range in size and complexity and require systems to conduct discrete reasoning (incorporating numerical operations like counting and argmax) by collating multiple facts within the database. to facilitate the reasoning at the scale of databases, nlp systems are required to access numerous sets of relevant sentences, often in combination with multi-hop retrieval (figure 1 ). for open-domain nlp systems to reason over only the relevant subset of facts from a corpus, a two-stage architecture of retrieval and reasoning is typically used @xcite . however, challenges in database-style reasoning require additional complexity with retrieving nonredundant sets of tens or hundreds of facts. for the wikinldb benchmark, @xcite proposed an incremental retrieval architecture called 1 ssg (support set generator) built on sentence-bert @xcite . the inference speed of the ssg is not scalable because it encodes query vectors for each reasoning step in multi-hop retrieval through the transformer @xcite , causing computation inefficiency. as the size of the database increases, retrieval slows down significantly. for example, with 25 facts in the database, ssg processes 21.51 queries per second, but as the number of facts increases to 1000, ssg only processes 1.46 queries per second. in this paper, we propose vkgfr (virtual knowledge graph based fact retriever) which significantly improves the inference speed and retrieval performance. since the wikinldb dataset can be represented in the knowledge graph structure, we suggest constructing a virtual knowledge graph @xcite for fact retrieval with llm. the vkg embedding provides compressed vectorized representations of facts and queries and can be pre-indexed, enabling efficient and accurate multi-hop retrieval. recent works have used vkg to predict target entities from knowledge bases @xcite or retrieve facts to claim verification @xcite . however, the number of reasoning steps and hop lengths are predetermined for these specific tasks, making it challenging to adapt them directly to database reasoning. applying the vkg to the database reasoning task is non-trivial because it requires various hops of reasoning, and the candidates per each reasoning step are not known a priori, and our work is the first to employ vkg for database reasoning. we evaluate vkgfr on wikinldb, a database reasoning task consisting of various sizes of database facts and corresponding queries, and metaqa @xcite , a conventional multihop qa dataset over the knowledge base. vkgfr performs best compared with several other vkgbased models and multi-hop dense retrieval models @xcite on both datasets. furthermore, vkgfr shows at least 4.7 times faster inference time than ssg in all database sizes of wikinldb (figure 6 ). we conduct an ablation study with different types of entity embedding and model structure, and our approach shows the best performance. our main contribution is to propose a significantly more efficient and accurate vkg-based retriever enabling natural language database reasoning. ## methods our multi-hop fact retriever vkgfr comprises two key steps: first, facts and queries are embedded into vkgs (section 3.1, figure 3 ); second, multi-hop retrieval is performed over the embedded vkg (section 3.2, figure 4 ). in contrast to ssg @xcite , the embeddings of facts are immutable and can be pre-indexed, yielding faster retrieval. for inference, vkg embeddings of new facts or queries can be embedded on demand. ## experiments and results on metaqa experiment setup to verify vkgfr on other tasks, we experiment with metaqa @xcite , which is a multi-hop retrieval over a predefined knowledge base built on the wikimovies ## related works building a semi-structured representation from textual sources has been an important direction in handling reasoning queries @xcite @xcite . this is because reasoning tasks often require entity matching, and previous dense retrieval methods are insufficient for entity representation learning. for this reason, many studies have focused on entitymatching-based retrieval methods @xcite @xcite . these studies find supporting facts by iteratively matching entities that appeared in a given question and documents, similar to human information-seeking processes. furthermore, contextualized entity embedding methods have been proposed. these methods are specifically designed for entity representation and capture more fine-grained semantic meanings of entities @xcite . inspired by previous entity-matching-based approaches, some studies propose to use relations between entities as well as entity vectors @xcite @xcite . these approaches use a relation encoder to encode the semantic meaning of the relation of entities, then construct a graph consisting of entity vectors and their relation vectors. @xcite proposes a virtual knowledge base, which consists of trainable entity vectors. @xcite further develops this approach to use the relation between entities and propose a virtual knowledge graph (vkg), which consists of entity and relation vectors. @xcite adopts the vkg to the domain-specific document retrieval with insufficient training data. unlike the previous approach, our methods target variable length of multi-hop database reasoning and show the best performance. ## conclusions in this paper, we propose vkgfr enable multihop retrieval with faster speed and high performance over the wikinldb dataset. our multi-hop retrieval mechanism does not require re-embedding of facts, resulting in fewer queries to an encoder model and allowing it to take advantage of preindexed fact representations. vkgfr retrieves upon that pre-indexed vkg representation which is highly contributing to the faster inference speed. on other tasks, vkgfr shows the best performance on the general knowledge-base multi-hop qa dataset, metaqa. this research demonstrates the applicability of vkg text representation in the task of multi-hop database reasoning.