GARLIC: LLM-Guided Dynamic Progress Control with Hierarchical Weighted Graph for Long Document QA

Authors: Xinyu Wang, Yanzheng Xiang, Lin Gui, Yulan He
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: retrieval, LLM, graph, dynamic, summary, attention, KV cache, QA

Abstract:
In the past, Retrieval-Augmented Generation (RAG) methods split text into chunks to enable language models to handle long documents. Recent tree-based RAG methods are able to retrieve detailed information while preserving global context. However, with the advent of more powerful LLMs, such as Llama 3.1, which offer better comprehension and support for longer inputs, we found that even recent tree-based RAG methods perform worse than directly feeding the entire document into Llama 3.1, although RAG methods still hold an advantage in reducing computational costs. In this paper, we propose a new retrieval method, called LLM-Guided Dynamic Progress Control with Hierarchical Weighted Graph (GARLIC), which outperforms previous state-of-the-art baselines, including Llama 3.1, while retaining the computational efficiency of RAG methods. Our method introduces several improvements: (1) Rather than using a tree structure, we construct a Hierarchical Weighted Directed Acyclic Graph with many-to-many summarization, where the graph edges are derived from attention mechanisms, and each node focuses on a single event or very few events. (2) We introduce a novel retrieval method that leverages the attention weights of LLMs rather than dense embedding similarity. Our method allows for searching the graph along multiple paths and can terminate at any depth. (3) We use the LLM to control the retrieval process, enabling it to dynamically adjust the amount and depth of information retrieved for different queries. Experimental results show that our method outperforms previous state-of-the-art baselines, including Llama 3.1, on two single-document and two multi-document QA datasets, while maintaining similar computational complexity to traditional RAG methods.

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

Reviews and discussion:
<thread>
creation date:
1730200089560

thread_type:
official_review

<thread_object>
creator: reviewer_lanf

<content>
summary:
The authors propose a method using LLMs to summarize long text into key information points, organizing these points into a hierarchical structure through recursive processing. This results in a directed acyclic graph where edge weights between nodes are generated based on attention mechanisms. For QA tasks, the authors apply a weighted BFS to retrieve relevant information from the graph. An LLM dynamically controls the retrieval process by determining if the information collected so far is sufficient to answer the question.

strengths:
1. The system uses a large language model to recursively generate key information from long texts, constructing an information structure graph. It employs the model's attention mechanism to assign weights to edges, introducing a new structure for information representation.

2. The authors propose using a priority-based breadth-first search to retrieve information points within the graph. The search process is controlled by the large language model, allowing retrieval to stop as soon as relevant information is found. This approach, compared to depth-first search, offers greater flexibility while maintaining efficiency. Final experimental results outperform recent benchmarks, including Llama 3.1.

weaknesses:
1. The paper does not explain how edge weights between nodes are calculated using the attention mechanism of the LLM, lacking crucial algorithmic details.

2. In Section 3.2.2, the paper discusses calculating the relevance between the query and information points using attention. How is this calculation performed, especially if it needs to be precomputed? This method may have limited scalability for new queries and new documents.

3. No code is released, making it difficult for others to use the proposed method or reproduce the result.

questions:
see weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730354661228

thread_type:
official_review

<thread_object>
creator: reviewer_myax

<content>
summary:
This paper proposes a new retrieval method, GARLIC (LLM-Guided Dynamic Progress Control with Hierarchical Weighted Graph), which aims to improve information retrieval in long document question answering tasks. It replaces the traditional tree structure by building a hierarchical weighted directed acyclic graph and uses the attention weights of large language models (LLMs) to perform multi-path search and dynamically control the retrieval process. Experiments show that this method surpasses the existing state-of-the-art baselines, including methods that directly use Llama 3.1 to process the entire document, while maintaining the computational efficiency of the RAG method.

strengths:
1. Overall, this paper is well-written and easy to read.
2. While existing RAG methods perform worse than directly feeding the entire document into Llama 3.1, the authors propose a new RAG method outperforms Llama 3.1 and retaining the computational efficiency of RAG methods. This approach can be used for reference by other researchers.

weaknesses:
1. In line 292, the author mentioned that the node's attention is multiplied by the corresponding position information to track the earlier information in the sequence. I think the author should conduct experiments to explain whether other adjustment methods have been tried? Why is this adjustment method effective? 
2. Lack of comparative analysis with other methods: Although the proposed model achieved excellent performance, the authors did not clearly explain why HWDAG is superior to the tree-based RAG method? Tree-based retrieval also seems to be able to summarize long documents and answer questions by selecting important nodes that are highly relevant to the query in a top-down manner through the GRAPH SEARCH method proposed by the authors. In addition, HWDAG seems to organize documents into a top-down hierarchy with different granularity, so low-level nodes seem to be a refinement and explanation of top-level nodes. As one of the main motivations of the article, I hope the author can explain why introducing refined information will hurt performance for some problems.
3. During the construction of the summary graph, the authors iteratively aggregate lower-level nodes by batching them and inputting them into the large language model (LLM) to generate higher-level nodes. However, the details of the iterative batching mechanism require further elaboration.

4. The authors argue that the information points (IPs) focus on “a single event or very few events”. It seems that the authors achieve this with just several instructions in the prompt. Is this approach sufficient to ensure the achievement of the intended objectives?

5. The authors average the token-level attentions to obtain the weights between information chunks (IPs). However, since these chunks represent higher-level, text-based content, is averaging token-level attentions an appropriate method for establishing relationships between these information chunks?

Comments, Suggestions And Typos:
1. In Section 4 Experiments, it is recommended to highlight the metrics that perform well in the table by bolding or underlining them.

questions:
Please refer to weakness, thanks.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730488563901

thread_type:
official_review

<thread_object>
creator: reviewer_cbqx

<content>
summary:
The paper presents GARLIC, a retrieval method that uses Hierarchical Weighted Directed Acyclic Graphs to improve long-document question-answering (QA) tasks. Unlike traditional retrieval-augmented generation (RAG) and tree-based models, GARLIC combines a unique two-stage process - Summary Graph Construction and Dynamic Graph Search.

strengths:
By using dynamic stopping and attention-weighted paths, GARLIC avoids unnecessary computation, which is common in exhaustive retrieval methods.

Outperforms benchmarks like Llama 3.1 and recent methods on NarrativeQA, Qasper, HotpotQA, and MuSiQue.

Compatible with long-context LLMs (e.g., Llama 3.1), making it feasible for single GPU execution.

weaknesses:
The attention normalization approach may limit scalability to larger graphs and complex attention patterns.

While the retrieval stage is efficient, graph construction is relatively resource-intensive, especially for single-query documents.

Embedding similarity, although beneficial, introduces some redundancy when compared with pure attention-based retrieval.

questions:
How does the system handle differences in event granularity? Specifically, do Information Points (IPs) for shorter events lead to inconsistencies in information distribution across the graph?

How does GARLIC scale when handling complex attention dependencies or queries that span multiple, disparate sections of a document? Is there a threshold at which the attention-guided search might encounter limitations?

Has dynamically adjusting the stop patience based on query complexity or node connectivity been considered? Could this approach optimize retrieval efficiency within larger graphs?

How does the efficiency of graph search vary in contexts with mixed single- and multi-query documents, particularly in cases with highly fragmented narratives, such as those in NarrativeQA?

GARLIC appears to extend ideas from both RAPTOR and MemWalker, borrowing sub-graph or informational-node stacking from RAPTOR and summarization from MemWalker. Could you clarify the main design distinctions and advantages of GARLIC compared to these methods (apart from using greedy search)?

Could you explain the choice to exclude LongT5 XL (Guo et al., 2022) and CoLT5 XL (Ainslie et al., 2023) as baselines (or any other baseline you feel may have given better performance similar to the base Llama3.1 on the benchmarked datasets), given their performance as open-source models? While ChatGPT’s closed-source nature makes its exclusion understandable, a rationale for omitting these alternatives would help clarify comparisons. Also, could you discuss the reported GARLIC performance alongside Table 5 in [1]?

From Table 1, it appears that a significant portion of GARLIC's performance boost is coming from the Llama-3.1 base model, as it already outperforms other baselines. How might results compare if Llama-3.1 were used with RAPTOR instead, considering RAPTOR's higher efficiency (0.5:1 on 1 datasets, and always below 1 on all remaining datasets)?

[1] Sarthi, Parth, et al. "Raptor: Recursive abstractive processing for tree-organized retrieval." arXiv preprint arXiv:2401.18059 (2024)."
</content>
</thread_object>

</thread>
<thread>
creation date:
1730545193557

thread_type:
official_review

<thread_object>
creator: reviewer_kpav

<content>
summary:
This work introduces a retrieval method, "GARLIC" (LLM-Guided Dynamic Progress Control with Hierarchical Weighted Graph), aimed at improving long document question answering. GARLIC operates through a multi-step process. First, it constructs a Hierarchical Weighted Directed Acyclic Graph (HWDAG) where each node represents a focused "Information Point" (IP) generated through LLM-based summarization. Second, GARLIC dynamically retrieves nodes from the graph, leveraging attention weights to assess relevance and terminate the search once sufficient information is collected. Third, it employs a Greedy Best-First Search to explore multiple graph paths, enhancing flexibility by allowing the search to stop at various levels based on the query's needs. This approach effectively balances retrieval precision and computational efficiency, outperforming existing methods in single and multi-document QA tasks.

strengths:
S1. The proposed method employs a hierarchical weighted directed acyclic graph instead of a tree structure, utilizing multi-path dynamic retrieval and hierarchical summary nodes.
S2. It is an interesting idea to assign weights to the edges based on attention, which allows GARLIC to adjust the retrieval depth and information volume flexibly.
S3. Decent performance compared to other existing approaches for retrieval.

weaknesses:
W1. An explanation of the edge weights in the directed acyclic graph needs further clarification: specifically, how the weights are calculated and how they function during the search process. The current presentation lacks intuitiveness.
W2. Detailed explanation on how KV caching is applied in the dynamic progress control is needed.
W3. The code should be made publicly available.
W4. Some baseline methods mentions in the article search down to the leaf nodes during retrieval, in other words, gather more information. However, why do they perform worse than the method presented in this paper, even though the proposed method may terminate the search early? Further analysis would be beneficial.

questions:
See weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1732565622079

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank the reviewers for their thoughtful feedback and the time they dedicated to evaluating our work.

We added the Top-X results for RAPTOR. We applied the Top-X setting to the RAPTOR Collapsed Tree variant, extracting Top-20, Top-42, Top-12, and Top-22 nodes for NarrativeQA, Qasper, HotpotQA, and MuSiQue, respectively, to match the TFLOPs of our method, consistent with other Top-X settings. The Top-X setting is to adjust the retrieved nodes to match the TFLOPs of baselines and our methods. All changes have been incorporated into the revised version and are highlighted in blue.

In the Top-X setting, we use our method to determine the nodes required for baselines, while in practice, baselines have to treat the number of extracted nodes as a hyperparameter. In contrast, our method automatically determines the number of nodes in each run using Dynamic Progress Control.

To emphasize the Top-X results and better illustrate the findings, we reordered Table 1 to list all Top-X results together.

| NarrativeQA | F1 | ROUGE-L | BLEU-4 | TFLOPs | Ratio |
|---|---|---|---|---|---|
|Llama3.1 | 53.7 | 52.6 | 10.4 | 3361.9 | 108.45x |
|MeMWalker | 11.2 | 9.8 | 2.6 | 353.8 | 11.41x |
|BM25 Top-X | 53.7 | 52.9 | 14.0 | 37.5 | 1.21x |
|SBERT Top-X | 39.5 | 38.8 | 7.3 | 37.5 | 1.21x |
|Dragon Top-X | 55.1 | 54.2 | 13.6 | 37.5 | 1.21x |
|RAPTOR Top-X | 52.0 | 51.2 | 11.8 | 35.1 | 1.13x |
|GARLIC | 61.1 | 60.2 | 18.6 | 31.0 | 1.00x |

| Qasper | F1 | ROUGE-L | BLEU-4 | TFLOPs | Ratio |
|---|---|---|---|---|---|
|Llama3.1 | 49.4 | 47.6 | 26.9 | 92.5 | 1.38x |
|MeMWalker | 39.0 | 36.8 | 17.4 | 123.9 | 1.85x |
|BM25 Top-X | 47.0 | 45.1 | 22.8 | 69.3 | 1.04x |
|SBERT Top-X | 46.6 | 44.5 | 23.3 | 68.9 | 1.03x |
|Dragon Top-X | 46.9 | 44.8 | 22.1 | 67.0 | 1.00x |
|RAPTOR Top-X | 46.9 | 44.7 | 20.8 | 67.3 | 1.01x |
|GARLIC | 49.7 | 47.9 | 27.0 | 66.9 | 1.00x |

| HotpotQA | F1 | ROUGE-L | BLEU-4 | TFLOPs | Ratio |
|---|---|---|---|---|---|
|Llama3.1 | 41.3 | 41.2 | 6.3 | 23.7 | 1.48x |
|MeMWalker | 39.7 | 38.9 | 13.9 | 93.4 | 5.84x |
|BM25 Top-X | 40.7 | 40.8 | 7.7 | 20.0 | 1.25x |
|SBERT Top-X | 40.8 | 40.7 | 7.5 | 19.6 | 1.23x |
|Dragon Top-X | 39.2 | 39.1 | 6.7 | 20.6 | 1.29x |
|RAPTOR Top-X | 40.7 | 40.7 | 7.2 | 17.9 | 1.12x |
|GARLIC | 43.5 | 43.5 | 7.2 | 16.0 | 1.00x |

| MuSiQue | F1 | ROUGE-L | BLEU-4 | TFLOPs | Ratio |
|---|---|---|---|---|---|
|Llama3.1 | 35.8 | 35.7 | 5.6 | 40.6 | 1.31x |
|MeMWalker | 24.0 | 23.5 | 9.9 | 175.7 | 5.69x |
|BM25 Top-X | 31.8 | 31.7 | 5.6 | 35.6 | 1.15x |
|SBERT Top-X | 32.5 | 32.5 | 6.4 | 35.6 | 1.15x |
|Dragon Top-X | 30.2 | 30.1 | 6.0 | 38.0 | 1.23x |
|RAPTOR Top-X | 35.4 | 35.2 | 7.2 | 32.2 | 1.04x |
|GARLIC | 36.9 | 36.8 | 5.7 | 30.9 | 1.00x |

After reordering Table 1 to list all Top-X results, it becomes clearer that our method outperforms all baselines with similar or even lower computational costs. For summary-based methods, MeMWalker, RAPTOR, and our approach, the computational costs for summarization are similar. However, our method still achieves superior performance compared to other summary-based methods at similar computational costs.

Our method introduces Dynamic Progress Control and a new attention-based retrieval paradigm leveraging Graph Search that does not rely on embeddings. Even with the same average TFLOPs, Dynamic Progress Control allows our method to better distribute and allocate computational resources across different queries and documents. Furthermore, as shown in Figure 4, our method allows stable adjustment of the trade-off between effectiveness and efficiency. These innovations are fundamentally different from existing RAG methods and are validated by our experimental results.

Among all baselines, our method is the only RAG approach that outperforms the LLM itself. As LLMs grow stronger and support longer input lengths, many RAG methods struggle to match the performance of LLMs, resulting in a widening performance gap. By deeply integrating the LLM into the retrieval process, our method achieves superior results, outperforming all baselines, including the LLM.

When compared to Llama 3.1, our method also mitigates scaling issues. For example, for a single-query document from NarrativeQA, Llama 3.1 requires 3361.9 TFLOPs, whereas our method requires only 2073.8 TFLOPs, encompassing both the summary and inference stages. Additionally, for multi-query documents, our method is significantly more efficient than Llama 3.1, as the summary graph can be reused across queries.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**Summary:**

This paper introduces GARLIC, a retrieval method for long document QA that effectively balances computational efficiency and accuracy. The core innovation lies in constructing a Hierarchical Weighted Directed Acyclic Graph (HWDAG), where text is summarized into fine-grained Information Points (IPs), each capturing single or few events. The graph edges are derived from LLM attention weights, enabling dynamic and flexible traversal across hierarchical levels.

Key contributions include:

* Dynamic Progress Control, which allows retrieval to stop when sufficient information is gathered.
* Attention-Based Retrieval, leveraging attention weights for relevance instead of embedding similarity.

**Strength:**

* Recursive use of a large language model to summarize long texts into information structures and assign attention-based edge weights introduces a novel information representation.
* GARLIC combines LLM-guided retrieval and computational efficiency, offering a valuable reference for other researchers.
* The method shows decent performance compared to existing retrieval approaches and outperforms Llama 3.1 while retaining RAG-like computational efficiency.

**Weakness:**

* The major weakness all reviewers pointed out is the lack of clarity and detailed explanation of the key components (e.g., edge weights by reviewer kpAv and LAnf; attention normalization by cbqx)
* Graph construction is resource-intensive since it needs multiple rounds of summarization using LLMs
* Lack of comparative analysis with other methods
* Further analysis is needed to explain why early termination in GARLIC performs better.
* Although embedding similarity improves performance, it introduces redundancy when compared to a purely attention-based retrieval method.