PaperlayerView exact revision on arXiv

Source-linked AI summary

Knowledge Graph Prompting for Multi-Document Question Answering

Yu Wang, Nedim Lipka, Ryan A. Rossi, Alexa Siu, Ruiyi Zhang, Tyler Derr

arXiv:2308.11730v3cs.CLcs.AIcs.IRcs.LG

TL;DR

Multi-document question answering requires LLMs to reason across passages and document structures, a setting with limited prior investigation. KGP constructs a document knowledge graph and uses an LLM-based traversal agent to gather relevant context. Experiments support KGP’s efficacy for MD-QA, while the approach remains bounded by graph scalability and construction-method trade-offs.

  • Problem

    The pre-train, prompt, and predict paradigm has been little studied for MD-QA, which requires logical associations across multiple documents and structures.

  • Method

    KGP constructs graphs with passage or document-structure nodes and similarity or structural edges, then uses an LLM-based agent to traverse promising nodes for context retrieval.

  • Results

    KGP-T5 ranks first among non-Golden baselines in the reported MD-QA comparison.

  • Takeaways & Limitations

    Graph construction provides a global transition structure while adaptive traversal selects question-relevant context for prompting LLMs in MD-QA.

  • Takeaways & Limitations

    The passage-node graph may not scale well when extremely large, although folders typically contain around 10-100 documents.

Abstract

from arXiv · show

The `pre-train, prompt, predict' paradigm of large language models (LLMs) has achieved remarkable success in open-domain question answering (OD-QA). However, few works explore this paradigm in the scenario of multi-document question answering (MD-QA), a task demanding a thorough understanding of the logical associations among the contents and structures of different documents. To fill this crucial gap, we propose a Knowledge Graph Prompting (KGP) method to formulate the right context in prompting LLMs for MD-QA, which consists of a graph construction module and a graph traversal module. For graph construction, we create a knowledge graph (KG) over multiple documents with nodes symbolizing passages or document structures (e.g., pages/tables), and edges denoting the semantic/lexical similarity between passages or intra-document structural relations. For graph traversal, we design an LLM-based graph traversal agent that navigates across nodes and gathers supporting passages assisting LLMs in MD-QA. The constructed graph serves as the global ruler that regulates the transitional space among passages and reduces retrieval latency. Concurrently, the graph traversal agent acts as a local navigator that gathers pertinent context to progressively approach the question and guarantee retrieval quality. Extensive experiments underscore the efficacy of KGP for MD-QA, signifying the potential of leveraging graphs in enhancing the prompt design for LLMs. Our code: https://github.com/YuWVandy/KG-LLM-MDQA.

1 Introduction

MD-QA extends LLM question answering to reasoning and retrieval across multiple documents and structures, where context selection remains underexplored. KGP addresses these challenges with graph construction and LLM-guided traversal.

  • 1 Introduction: 25.07%/10.58% F1 and 18.60%/4.60% EM are achieved without context on 2WikiMQA/MuSiQue, versus 59.69%/47.75% F1 and 40.20%/30.60% EM with supporting facts.The comparison demonstrates the importance of retrieved context for these multi-document questions.
  • 1 Introduction: MD-QA requires logical associations across passages, pages, tables, and other structures from multiple documents.Questions may bridge passages sequentially, compare passages in parallel, or retrieve content from specified structures.
  • 1 Introduction: KGP constructs a knowledge graph whose nodes represent passages or document structures and whose edges encode lexical, semantic, or structural relations.The graph supports context formulation across heterogeneous document content.
  • 1 Introduction: An LLM-based traversal agent generates the next evidence and selects promising neighboring nodes while traversing the graph.Instruction fine-tuning augments the agent’s reasoning capability and reduces repeated prompting of non-open-sourced LLMs.
  • 1 Introduction: The paper evaluates generally applicable graph construction methods and compares graph-traversal agents for MD-QA.The introduction identifies graph-quality evaluation and agent comparisons as experimental components.

2 Notations

The paper represents a document collection as a graph whose nodes are passages or document structures, with features containing their textual, tabular, or positional information.

  • 2 Notations: A knowledge graph is defined as G = (V, E), where V contains document-structure nodes and E contains connections among them.Connections may encode semantic or lexical similarity and belonging relations among structures.
  • 2 Notations: Node features X_i may contain passage text, markdown-formatted table content, or a page number.The feature form depends on the represented document structure.
  • 2 Notations: The construction framework also treats extracted tables and pages as structural nodes alongside passage nodes.These structures expand the graph beyond passages.

3 Knowledge Graph Construction

KGP builds document graphs using lexical or semantic passage relations and intra-document structure, then uses traversal to manage irrelevant neighbors during retrieval.

  • 3 Knowledge Graph Construction: Established knowledge graphs centered on entities and relations are less applicable to general or non-Wikipedia documents, motivating the paper’s document-oriented construction.The paper emphasizes use cases such as legal and financial documents.
  • 3 Knowledge Graph Construction: Passage connections can use shared keywords, embedding similarity, or Wikipedia entities, while pages and tables encode document structure.The paper compares TF-IDF, sentence-transformer KNN, KNN-MDR, and TAGME-style construction choices.
  • 3 Knowledge Graph Construction: Pages and tables are added as structural nodes, with directed page-to-content edges and markdown features for tables.The construction can include more structure types, although this paper considers pages and tables.
  • 3 Knowledge Graph Construction: As graph density increases on HotpotQA, SF-EM increases while precision decreases; KNN-MDR offers a better trade-off than TF-IDF and KNN-ST.TAGME constructs denser graphs than the other methods.
  • 3 Knowledge Graph Construction: High SF-EM can coexist with low precision, so blind traversal may retrieve irrelevant passages and compromise MD-QA performance.This motivates question-tailored traversal by an LLM-based agent.

4 LLM-based KG Traversal Agent

The LLM-based graph traversal agent ranks candidate neighbors using the question and previously retrieved passages, while grounding generated evidence in KG nodes. It also handles structure-focused questions by retrieving content from corresponding structural nodes.

  • The agent ranks neighboring candidate nodes by reasoning over the question and previously retrieved passages, rather than relying only on lexical or embedding similarity.The retrieved passage history is concatenated as context for selecting the next node.
  • The traversal uses an LLM to generate the next evidence passage and selects a matching candidate neighbor to reduce factual errors in generated text.In the Simpson’s Theme example, a generated birth date is corrected by selecting the document-sourced matching node.
  • For structure-focused questions, the method locates structural KG nodes and retrieves table content or page-associated passages.Table nodes provide markdown content, while page nodes are handled through one-hop traversal.
  • The traversal algorithm receives a question, document KG, fine-tuned traversal model, context budget, and TF-IDF search function as inputs.These inputs define the retrieval environment for the LLM-guided traversal procedure.

12 Terminate

The traversal iteratively ranks candidate neighbors and updates its queues until no candidates remain or the retrieved-passage budget is reached.

  • Terminate: The method initializes seed passages and a reasoning-path queue using TF-IDF search before traversal begins.
  • Terminate: At each step, candidate neighbors are ranked, the next node is visited, and both candidate and reasoning-path queues are updated.
  • Terminate: Traversal terminates when the candidate-neighbor queue is empty or the preset retrieved-passage budget is met.

5 Experiment

The experiments evaluate KGP against baselines, inspect graph and traversal-agent effects, and analyze sensitivity to graph density, branching factor, and document count. KGP generally ranks first, supports structural questions, and trades higher retrieval quality for increased latency as graph density grows.

  • Performance Comparison: KGP-T5 ranks Top-1 among the non-Golden baselines in MD-QA performance comparisons.None and Golden provide the worst and best contexts, respectively, while retrieved-context baselines fall between them.
  • Performance Comparison: KGP achieves 67% Struct-EM on PDFTriage structural questions by retrieving contexts represented as document-structure nodes.The evaluated questions include comparisons between pages and queries about table contents.
  • Impact of the Constructed Graph: As KG density increases, F1/EM increases or remains stable while latency for selecting the next promising neighbor also increases.The study varies KG-construction hyperparameters and measures MD-QA performance and neighbor-matching time using KGP-T5.
  • Impact of Graph Traversal Agent: LLM-guided traversal outperforms random traversal, while KGP-T5 performs better than LLaMA despite using fewer parameters.The authors hypothesize that LLaMA-7B requires more fine-tuning data than T5-0.7B.
  • Sensitivity Analysis: Performance first rises and then falls with branching factor because larger branching creates more reasoning paths but reduces initial seeding coverage under a fixed context budget.Across different document counts, KGP maintains higher performance than other baselines and higher efficiency than embedding-based DPR.

6 Related Work

Related work frames QA as retrieval followed by answer extraction, but MD-QA requires alternating reasoning and retrieval across multiple documents. Existing heuristic and neural retrievers do not directly address this multi-document setting.

  • Question Answering: Most QA systems combine information retrieval of relevant passages with answer extraction from those passages.Retrieval may use heuristic methods such as BM25 or neural ranking methods such as DPR.
  • Multi-Document QA: MD-QA differs from open- and single-document QA because it requires alternating reasoning and retrieval across multiple documents.The related-work discussion identifies this requirement as an unresolved focus of previous work.

7 Conclusion

The paper concludes that KGP supports MD-QA by combining graph representations of passages and document structures with selective LLM-guided traversal. It identifies graph-topology understanding and encoding as future directions.

  • Conclusion: KGP constructs graphs whose nodes represent sentences or document structures and whose edges represent lexical, semantic, or structural relations.An LLM-based traversal agent selectively visits promising nodes to gather question-relevant context.
  • Conclusion: Future work will investigate whether LLMs can understand graph topology and encode complex topological signals through fine-tuning or prompting.

8 Supplementary

The supplementary section describes the datasets, graph construction, training procedures, prompting setups, and traversal-algorithm inputs used for the experiments.

  • Datasets: The authors create MD-QA datasets by sampling questions from HotpotQA, IIRC, 2WikiMQA, and MuSiQue, then retrieving supporting Wikipedia documents.These datasets simulate users asking questions over folders containing multiple documents.
  • Knowledge Graph Construction: Knowledge graphs contain passage nodes for Wikipedia-based datasets, while PDFTriage additionally includes page and table nodes extracted with ExtractAPI.The graph representation therefore includes document structure when the task requires it.
  • Training: DPR training pairs questions with supporting facts as positive passages and randomly sampled passages as negative passages.MDR training uses supporting-fact order and constructs new questions by concatenating the original question with an earlier supporting fact.
  • Instruction Fine-tuning: LLaMA and T5-Large are fine-tuned on the same instruction data, with LLaMA-7B trained using LoRA under computational constraints.T5-Large removes the instruction from the input format and uses default repository hyperparameters.
  • Prompting LLMs for MD-QA: Baseline prompting reports performance using randomly selected development-set questions, 30 retrieved passages, and ChatGPT for answer generation.The baselines include KNN, MDR, and KGP-TF-IDF, which replaces LLM-guided traversal with TF-IDF passage selection.
  • LLM-based KG Traversal: The LLM-based traversal algorithm takes a question, document KG, fine-tuned traversal model, context budget, and TF-IDF search function as inputs.Its control flow includes queues, a retrieved-passage counter, and a returned passage queue.

12 Terminate

The paper analyzes KG construction trade-offs, traversal complexity, scalability, and performance as graph density changes. It concludes that no single construction method is best across use cases.

  • Complexity: O((|V|+|E|) ˆdγ) is the graph traversal time complexity, combining breadth-first search with neighborhood ranking.The authors describe this as between linear and quadratic in graph size and suggest LSH or KD-tree methods to reduce ranking cost.
  • Complexity: O(|V|(α + β)) space is required to maintain the KG, which remains affordable for typical folders containing 10–100 documents.The authors note that passage-level nodes may not scale well for extremely large graphs.
  • Structural content: Long tables exceed ChatGPT’s input-token limit when represented in markdown, motivating future SQL or grid-graph solutions.Markdown tables otherwise support table-content understanding and retrieval.
  • KG construction comparison: TAGME extracts Wikipedia entities effectively but requires more than 8 hours for 12 documents and cannot generalize beyond Wikipedia entities.TF-IDF and KNN-ST lack guaranteed relationship precision, while KNN-MDR requires costly logically ordered supporting-fact annotations.
  • KG construction comparison: There is no one-size-fits-all KG construction method; the best choice depends on the use case and domain.The paper contrasts TAGME or knowledge bases for broad factual domains with TF-IDF/KNN-ST or domain-specific encoders in niche settings.
  • Density and quality: As KG density increases on MuSiQue, MD-QA performance and retrieval latency increase, while precision decreases and supporting-fact coverage improves.KNN-ST achieves better F1/EM and Precision/SF-EM trade-offs than KNN-MDR on MuSiQue, consistent with the observed KG quality.

8.7 Case study on Structural/Content Questions

The case studies demonstrate KGP across table, page, single-document, and multi-document questions. The examples show retrieval of structured content and progressively linked evidence.

  • Case studies: The interface evaluates six MD-QA case studies spanning two table questions, one page question, one single-document question, and two multi-document questions.Users upload documents, which the backend splits into multiple passages before answering questions.
  • Table QA: ChatGPT retrieves the number of people with membership grade ‘Fellow’ from a markdown-formatted table.This example tests table-structure understanding.
  • Page QA: The page question receives a high-level summary of Page 2 that covers the title of each section.
  • Single-document QA: For the single-document question about sedentariness, the second retrieved sentence contains the answer and matches the paper abstract’s first sentence.
  • Multi-document QA: The multi-document examples require linking Lebron James’s basketball background to Ohio’s area ranking and comparing Lebron James’s and Michael Jordan’s birthdays.The bridging example retrieves Lebron’s relevant state before judging Ohio’s ranking; the comparison example gathers both birthdays.

8.8 Visualizing the Reasoning-and-Retrieving Process of LM-guided Graph Traverser

The supplementary visualizations show the graph traversal process for two multi-document question-answering examples.

  • Traversal visualization: Figure 19 visualizes graph traversal over MD-QA-Example 1.
  • Traversal visualization: Figure 20 visualizes graph traversal over MD-QA-Example 2.

8.9 Prompt template used throughout this work

The paper uses prompt templates for answering questions with or without retrieved context, and for training or evaluating retrieval agents. Examples illustrate final-answer and next-evidence instructions.

  • Prompt templates: Listing 1 contains instruction data examples for fine-tuning LLaMA.
  • Evidence selection: The retrieval-agent instruction asks what evidence is needed next given current evidence, using magazine-start-date and Simpson’s Theme examples.One example connects the current arrangement of Simpson’s Theme to Alf Clausen’s birth date.
  • Prompt templates: Listing 2 provides a prompt template for answering a question without retrieved context.The template includes a question and requests a short final answer.
  • Prompt templates: Listing 3 provides a prompt template that asks an LLM to create a final answer from a question and retrieved contexts.
  • Prompt templates: Listing 4 gives the retrieved-context prompt used for MDR, KGP-T5, KGP-LLaMA, and KGP-MDR.The examples include evidence passages for connecting Anthony Avent’s high school location with Newark’s position west of lower Manhattan.
  • Retrieved contexts: Additional retrieved-context examples enumerate alternative evidence passages for the Anthony Avent question, including biographical, school, district, and city information.
Loading 2308.11730v3…