GIVE: Structured Reasoning with Knowledge Graph Inspired Veracity Extrapolation

Authors: Jiashu He, Mingyu Derek Ma, Jinxuan Fan, Dan Roth, Wei Wang, Alejandro Ribeiro
Primary area: foundation or frontier models, including LLMs
Keywords: Large Language Model, Structured Reasoning, Biomedical QA, Intelligent Agent

Abstract:
Existing retrieval-based frameworks to enhance large language models (LLMs) requires accessibility to a rich non-parametric knowledge source which contains factual information that directly solves the query. Reasoning based approaches heavily rely on the parametric knowledge of the model to provide domain-specific explicit reasoning chain. However, inclusive knowledge sources are expensive or infeasible to build for scientific or corner domains, thus not applicable in either training or inference time. To tackle the challenges, we introduce Graph Inspired Veracity Extrapolation (GIVE), a novel reasoning framework that integrates the parametric and non-parametric memories to enhance both knowledge retrieval and faithful reasoning processes using very limited external clues. By leveraging the structured knowledge to inspire LLM to model the interconnections among relevant concepts, our method facilitates a more logical and step-wise reasoning approach akin to experts' problem-solving, rather than gold answer retrieval. Specifically, the framework prompts LLMs to decompose the query into crucial concepts and attributes, construct entity groups with relevant entities, and build an augmented reasoning chain by probing potential relationships among node pairs across these entity groups. Our method incorporates both factual and extrapolated linkages to enable comprehensive understanding and response generation. Extensive experiments on domain-specific and open-domain benchmarks demonstrate the effectiveness of our proposed method, thereby underscoring the efficacy of integrating structured information and internal reasoning ability of LLMs for tackling difficult tasks with limited external resources.

Decision: reject
Reviewer scores: 5, 6, 8, 5

Reviews and discussion:
<thread>
creation date:
1730525173462

thread_type:
official_review

<thread_object>
creator: reviewer_op2q

<content>
summary:
This paper presents a novel framework called GIVE (Graph Inspired Veracity Extrapolation), aiming at improving the reasoning ability of LLMs in knowledge-intensive tasks with sparse KGs. GIVE obtains similar entities for queried entities to construct relevant entity groups, then finds inter-group and inner-group connections with LLMs. By using LLMs to extrapolate probable relationships, GIVE addresses the limitation of traditional RAG methods when reasoning on domain-specific sparse KGs. Experiments on biomedical and commonsense datasets demonstrate the effectiveness.

strengths:
S1. GIVE focuses on an important and practical issue. Traditional RAG approaches show poor performance on reasoning-rich tasks when domain knowledge cannot be easily obtained and domain-specific KGs are hard to construct and maintain. The idea behind GIVE could promote the application of LLMs in specialized domains with scarce data.

S2. Massive experiments are designed to support the authors' claim. As shown in Section 4, four datasets from two different domains are involved to demonstrate the effectiveness of GIVE. From Appendix, many ablation studies and detailed analysis are performed, showing robustness. The attached prompt templates also ensure that GIVE is easy to reproduce.

S3. The organization is good. The organization of Section 3 is clear and easy to follow.

weaknesses:
W1. In general, this paper is well-written. However, some parts are very brief and hard to comprehend. It is better to present more details with some equations in Section 3.3 and 3.5.

W2. Limited evaluation and incomplete analysis. While massive experiments are conducted, there are still some experiments needed to enhance robustness. As for efficiency, comparison of LLM calls is not comprehensive enough. Details are listed in Questions.

questions:
Q1. Could you provide a definition of "sparse"? From Section 4.1.1, we can see that each node in UMLS connects to about 87 nodes in average. In my opinion, UMLS is a "small" KG with only 135 nodes, but it's not a sparse KG if you take the degree of nodes into account.

Q2. The authors mentioned that KBQA datasets are unsuitable because GIVE is designed for reasoning with sparse KGs. I wonder whether GIVE works for KBQA with incomplete KGs if some edges are removed, just like EmbedKGQA (https://aclanthology.org/2020.acl-main.412), one of related works mentioned in Section 2.

Q3. The authors evaluate efficiency based on the number of LLM calls. How about the context length? Could you provide the averaged number of input tokens to solve one question for GIVE.

Q4. About multi-step reasoning. I wonder why only 2-hop paths are selected? Do you experiment with longer paths?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730696352808

thread_type:
official_review

<thread_object>
creator: reviewer_7idj

<content>
summary:
The paper introduces GIVE (Graph Inspired Veracity Extrapolation), a structured reasoning framework aimed at enhancing the factual reliability of large language models (LLMs) when working with sparse knowledge graphs (KGs). Recognizing the limitations of LLMs in specialized or scientific domains where comprehensive KGs are infeasible, GIVE leverages both internal and external knowledge sources. It decomposes queries into core concepts, creates entity groups for each query, and induces reasoning chains by identifying potential relationships among these groups. The framework incorporates both factual and counterfactual connections to mitigate hallucination risks in reasoning. Experiments on biomedical and commonsense QA benchmarks demonstrate that GIVE enables LLMs, such as GPT-3.5-turbo, to surpass even more advanced models like GPT-4 without additional training costs

strengths:
The paper is clear and well-organized, making the technical contributions easy to follow.

Given the increasing reliance on LLMs for knowledge-intensive tasks, addressing the factuality of LLM outputs in specialized domains is a critical area of research.

The GIVE framework introduces an innovative approach by combining structured KG-inspired reasoning with parametric and non-parametric memories, presenting an original solution to a well-recognized problem in LLM performance.

weaknesses:
The framework appears quite complex, combining multiple distinct modules into a single system. This layered approach raises concerns about the simplicity and elegance of the solution, as well as its general applicability.

 Although the paper includes a few ablations, the complexity of the approach warrants a more thorough exploration of each module's contribution to overall performance. For instance, it would be valuable to have a clearer understanding of how each step (e.g., inner-group and inter-group connections, counterfactual relations) affects the final results.

questions:
How does GIVE perform in comparison to GraphRAG or similar frameworks that incorporate KG information into LLM-based reasoning? Since GraphRAG is specifically designed for KG integration, this would be a valuable comparison to include.

Why do some baselines without external knowledge outperform those with retrieval? It raises the question of whether the implementation of the baselines was correct. Could the authors clarify if there might be any explanation for these results?

GIVE is tested on specialized datasets, but commonly used benchmarks such as TruthfulQA and Natural Questions (NQ) are not included. Testing GIVE on these datasets would provide a broader perspective on its generalizability and effectiveness in widely used tasks.

The paper compares GIVE primarily against RAG and ToG. However, there is a substantial amount of literature on KG-enhanced LLMs. Adding comparisons with other KG-based enhancements would strengthen the experimental results and help position GIVE more accurately within the state of the art.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730702823526

thread_type:
official_review

<thread_object>
creator: reviewer_z1eq

<content>
summary:
This paper introduces GIVE, a novel framework that enhances LLM's reasoning capabilities by leveraging sparse knowledge graphs. Rather than relying on direct knowledge retrieval, GIVE uses KG structure as "inspiration" for LLMs to conduct structured reasoning. The framework operates by decomposing queries into key concepts, constructing entity groups, and building connections within and across these groups through a combination of KG guidance and LLM knowledge.
The paper's main contribution is a new paradigm that bridges parametric (LLM internal knowledge) and non-parametric (external KG) memories for structured reasoning, while preventing hallucination through counterfactual knowledge incorporation. GIVE employs a progressive answer generation approach that combines affirmative, counter-factual, and expert knowledge to produce reliable responses. Through extensive experiments on both biomedical and commonsense reasoning tasks, the authors demonstrate that GIVE enables GPT3.5-turbo to outperform more advanced models like GPT4 on biomedical reasoning using only a sparse knowledge graph, without additional training.

strengths:
The paper exhibits several notable strengths in its motivation, methodology, and empirical findings.

**Clear Motivation**: The authors identify a critical gap in current retrieval-based reasoning approaches for LLMs, which typically require dense, high-quality knowledge sources. This requirement poses a significant challenge in specialized domains like healthcare where comprehensive knowledge bases are expensive or impractical to build. The paper's focus on enabling effective reasoning with sparse knowledge graphs addresses a real-world constraint in deploying LLMs for domain-specific applications.

**Novel and Intuitive Method**: The proposed GIVE framework presents an elegant solution by treating knowledge graphs as inspiration rather than mere information sources. The method intuitively mimics human expert reasoning by first identifying relevant concepts, building semantic groups, and then discovering relationships both within and across these groups. The progressive answer generation strategy, which incorporates affirmative, counter-factual, and expert knowledge, provides a natural way to prevent hallucination while leveraging both the LLM's internal knowledge and external information.

**Interesting Findings**: The experimental results reveal several compelling insights. Most notably, GIVE enables GPT3.5-turbo to outperform GPT4 on biomedical reasoning tasks using only a sparse knowledge graph of 135 nodes, demonstrating that structured reasoning can compensate for model size. The ablation studies also reveal an interesting correlation between performance and expert knowledge ratio, suggesting that even a small amount of expert knowledge can effectively guide LLM reasoning when properly structured.

weaknesses:
**Limited Scope and Comprehensive Evaluation**: While GIVE is presented as a general framework applicable across domains, the empirical evaluation heavily focuses on medical QA tasks with sparse KGs. The experiments on CommonsenseQA with denser KGs are limited to GPT-3.5-turbo and lack comprehensive comparisons with competitive baselines. Despite claiming effectiveness "in retrieving information from both sparse and dense KG," there isn't sufficient experimental evidence demonstrating how GIVE helps bridge the performance gap between smaller and more advanced LLMs across different KG densities. A more thorough evaluation across different model sizes and KG configurations would better support the framework's generalizability claims.

**Scalability and Computational Analysis**: The paper's experiments primarily focus on sparse KGs with relatively small numbers of entity groups (m) and entities per group (n), typically less than 5 for biomedical datasets. While the authors mention potential optimizations through batch pruning, the paper lacks a thorough analysis of how the method scales with increasing m and n when applied to larger or denser KGs. The computational complexity of O(rm²n²) could become significant with larger KGs, and the paper would benefit from a detailed cost comparison with existing methods like RAG and ToG. This analysis is crucial for understanding the practical applicability of GIVE in real-world scenarios with larger knowledge bases.

**Knowledge Conflict Resolution**: The paper does not adequately address how GIVE handles conflicts between LLM's internal knowledge and KG-sourced information. While the progressive answer generation approach incorporates both knowledge sources, there isn't a clear mechanism or analysis of how the system resolves contradictions when they arise. This becomes particularly important in specialized domains where LLM's pre-trained knowledge might conflict with domain-specific KG information, potentially affecting the reliability of the reasoning process. A systematic approach to knowledge conflict resolution would strengthen the framework's robustness.

questions:
1. **Comprehensive Evaluation and Generalization**
   - Could you provide additional experimental results comparing GIVE's performance across different LLM sizes (e.g., GPT-4, GPT4o-mini, Llama) on CommonsenseQA with the full ConceptNet?
   - What is the performance gap between smaller and larger LLMs when using GIVE with denser KGs? This would help substantiate the claim about GIVE's effectiveness across different KG densities.

2. **Scalability and Efficiency**
   - Could you provide an analysis of how computational costs scale when applying GIVE to denser KGs? Specifically, how does GIVE's running cost compared to RAG and ToG in the current setting and in a denser KG setting?
   - What is the practical upper limit for m and n on a large KG where GIVE remains competitive against RAG (probably with pruning as mentioned)?

3. **Knowledge Conflict Resolution**
   - How does GIVE handle cases where the LLM's internal knowledge directly contradicts the KG information? Is there a way to evaluate the reliability of conflicting information from different sources?
   - Could you provide examples of how the progressive answer generation approach handles such conflicts in practice?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731305520585

thread_type:
official_review

<thread_object>
creator: reviewer_qxmg

<content>
summary:
This work aims to enhance RAG by systematically integrating external knowledge from KGs and leveraging the model's internal knowledge. It induces potential relations between different entity groups, identifies intermediate nodes for multi-hop reasoning, and employs a guided reasoning process that combines affirmed knowledge, counters potential inaccuracies, and incorporates ground-truth data.

strengths:
1. The authors provide a clear motivation and a good introduction to the problem.
2. Using LLMs to generate divergent thinking on additional entities and relationships to mitigate the sparsity problem in KG-RAG is a valuable approach worth exploring.
3. The performance of the method is overall positive.

weaknesses:
1. Limited novelty, as leveraging triple-based reasoning in RAG and iterative self-checking are already common practices.
2. There are relatively few evaluation datasets and baselines. (See Questions)

questions:
1. Using LLMs for selection will inevitably be constrained by the input length. Considering the case where there are a large number of 2-hop path combinations between two nodes, this method seems only suitable for very sparse knowledge graphs (where there are few 2-hop path combinations on average).
2. There are relatively few evaluation datasets, and the experiments are based on scenarios involving incomplete domain-specific knowledge graphs. It remains to be seen whether it can also be competitive against baselines in open-domain benchmarks with larger KG.
3. ToG assumes that it is based on a relatively large and complete knowledge graph. Considering the issue of corpus graph sparsity, could it be compared with methods like GraphRAG(From Local to Global: A Graph RAG Approach to Query-Focused Summarization)?
4. In addition to Questions_2, it's necessary to quantify the sparsity of the knowledge graphs mentioned in this paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732492032310

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response && We would like to hear your feedback

comment:
Dear reviewers,

We would like to thank you for taking time to review our paper and provide extremely valuable and constructive feedback. The discussions raised by each of you have been very fruitful for us to improve both presentation and experimental completeness of our paper. We would like to further answer some common questions and highlight the major changes in our revised manuscript. We are convinced that we have addressed all your concerns and would be delighted to hear your thoughts on our response and the revised manuscript.

1. $\textbf{Novelty/Contribution:}$ GIVE is a novel reasoning framework inspired from human cognitive process, which is to use the limited expert information as high-level hints for LLM to conduct divergent thinking, thus solve the reasoning-intensive query. We are glad that all reviewers recognize the motivation of our paper: We provide an approach (GIVE) for LLM to retrieve and reason on sparse KGs, whereas all previous methods fail heavily because (1) LLM does not have enough self-knowledge to solve the query (CoT). (2) There is no direct information in the external knowledge source to directly solve the query (ToG).  

2. $\textbf{Inclusiveness of experiments:}$ We include KGs of different sizes and sparsities: small and dense(umls), large and sparse(10% / 50% ConceptNet), large and dense (full ConceptNet), QA datasets from different domains (biomedical, commonsense, open-domain), of different types (yes-no, multiple-choice, text generation), LLMs of different sizes (LLama3.1, GPT3.5T, GPT4, GPT4o-mini). In every one of these comparisons, GIVE achieves the best performance. For every experimental setting, we clarify in both the comments and the revised manuscript the reason to choose this setting: We aim to test GIVE’s ability in boosting the model’s reasoning ability, especially when it is hard to get enough knowledge during training.

3. $\textbf{Efficiency of GIVE:}$ We include detailed analyze and numerical results on GIVE’s efficiency in Appendix F.2 of the revised manuscript, covering every factor that could potentially influence GIVE’s efficiency in both time and context length. Reasoning guarantees better performance, but at the same time, takes time (like human).  GIVE (and its efficient alternative) achieves balanced tradeoff between efficiency and accuracy in these hard tasks. The results itself proved that the knowledge generated by GIVE is of high quality.

$\textbf{Summery of Changes:}$ 

  $\textbf{Experiments:}$ $\textbf{New baseline}$: GraphRAG (Section 4.2); $\textbf{New dataset}$: TruthfulQA (Appendix D); $\textbf{New ablation studies}$: inner/inter group connections (Appendix E.1); $\textbf{Additional detailed efficiency comparison}$: time/context length (Appendix F.2) 
 
$\textbf{Presentation:}$ formalize description of Section 3.3 and 3.5, clarification of "sparse" in Section 4.1.1 and change description of UMLS from “sparse” to be “small and dense”, quantify all datasets in Appendix C, discussion about connections/difference between GIVE and RAG in Appendix B, more clear motivation statement in abstract and conclusion, as well as all the other new findings from the discussions with the reviewers.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733108850563

thread_type:
public_comment

<thread_object>
creator: ~surya_tej_kodali1

<content>
comment:
I would like to share how the GIVE framework has significantly improved our company's medical coding and billing processes. In our industry, we often deal with incomplete or proprietary insurance guidelines. Companies like InterQual and MCG do not publicly disclose their guidelines, resulting in sparse and sometimes inconsistent information. While these guidelines may broadly align with Medicare policies, critical differences exist that we must accurately identify and apply.

By implementing GIVE, we developed a customized solution that integrates sparse knowledge graphs with our existing systems. This framework allowed us to:

- **Model Complex Relationships:** GIVE helped us understand intricate dependencies between medical codes, such as identifying mutually exclusive codes and handling conditional billing rules. This is crucial when certain procedures cannot be billed together or when specific guidelines take precedence.

- **Handle Data Sparsity Effectively:** Even with limited external information, GIVE enabled us to combine our internal knowledge with sparse external data, filling gaps in proprietary or incomplete guidelines. This was instrumental in adapting to various insurance-specific rules that deviate from standard Medicare guidelines.

- **Improve Efficiency Through Pruning:** To address the challenge of numerous 2-hop neighbors in the knowledge graph, we utilized additional metadata and embeddings to prune irrelevant results. This optimization allowed us to focus on the most pertinent relationships without compromising efficiency, ensuring the framework scaled well with larger datasets.

- **Enhance Compliance and Accuracy:** By accurately modeling and prioritizing guidelines from CMS, NCCI, and individual insurance providers, GIVE reduced the risk of claim denials and audits. It ensured that we consistently applied the most relevant policies in our coding and billing practices.

Implementing GIVE has led to improved coding accuracy, enhanced compliance with regulatory requirements, and increased operational efficiency. The framework's ability to handle data sparsity and complex relationships has been invaluable in our real-world setting, where guidelines are often incomplete or proprietary.

Our successful application of GIVE underscores its practical applicability and effectiveness in specialized domains.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces GIVE, a framework leveraging sparse knowledge graphs (KGs) to enhance large language models (LLMs) for reasoning tasks. While the reviewers acknowledge that the approach is well motivated, several critical shortcomings are identified:

- Limited evaluation scope: The experiments focus on specialized tasks, like biomedical QA, with insufficient general-domain benchmarks (qXMg, Z1Eq).
- Scalability concerns: The computational complexity for larger and denser KGs remains unaddressed, raising concerns about practical applicability (qXMg, Z1Eq).
- Baseline issues: Comparisons with relevant methods, such as GraphRAG, are incomplete, and the choice of baselines leaves gaps in experimental rigor (7idj, qXMg).
- Conflict resolution: Mechanisms for handling discrepancies between KG-derived and LLM-internal knowledge are inadequately explored (Z1Eq).