[Paper Review] StructRAG: Boosting Knowledge Intensive Reasoning of LLMs via Inference-time Hybrid Information Structurization

정보의 최신성을 반영하기 어려운 LLM 의 문제점을 해결하기 위한 방안으로 RAG 시스템이 많은 주목을 받고 있다. 그러나 기본적인 형태의 RAG 시스템은 Knowledge Intensive Reasoning Tasks 에서 한계를 보이는데, 필요한 정보가 분산되어 있거나 chunk 로 나누는 과정에서 생기는 문제(노이즈) 등의 이유로 복잡한 추론 작업에서는 성능이 떨어진다. 그래서 현재는 Naive RAG 형태에서 Advanced RAG, Modular RAG 를 거쳐 최근에는 Graph 기반의 RAG 까지 다양한 방법론이 등장하고 있다. 얼마 전에 공개된 이 논문에서 제안하는 StructRAG 방식은 이전 RAG 시스템과 다르게 추론 과정에서 추가적인 Hybrid Structure Router 를 두어 정보를 구조화하였고, 다른 RAG 방식들과 비교하여 성능이 우수함을 실험적으로 보였다.

• 논문 링크: https://arxiv.org/abs/2410.08815

1. StructRAG via Hybrid Information Structurization

StructRAG framework 의 전반적인 내용은 위 이미지에서 설명이 가능하다.

1.1. Hybrid Structure Router

Hybrid Structure Router 는 StructRAG 시스템의 핵심 모듈로, 주어진 질문 Q 에 대하여 가장 적합한 정보 구조 형식을 선택(라우팅)하는 역할이다. 검색된 문서에서 필요한 정보를 더 효율적으로 이용할 수 있도록 최적의 구조 방식을 결정하는데, 예를 들면 수치나 통계적 정보를 다룰 때는 테이블 형식이 적합하고 복잡한 노드 및 엣지의 관계로 표현되는 데이터에서는 그래프 방식이 적합하기 때문이다. 이 논문에서는 적절한 구조 형식을 5가지로 정의하였는데,

• Table: statistical tasks
• Graph: long-chain tasks
• Algorithm: planning tasks
• Catalogue: summarizing tasks
• Chunk: simple single-hop tasks

Router 의 입력으로 검색된 문서를 그대로 사용하지 않고 core content 가 사용된다. 여기서 core content 는 각 문서의 제목이나 앞 쪽 일부 문장들과 같이 중요한 부분을 의미한다. Router 는 질문 Q 와 core content C 를 바탕으로 가장 적합한 구조형식 t 를 결정한다.
$$t=R(q,C)$$
논문에서는 few-shot 형태의 prompt engineering 을 사용한 것이 아닌 데이터를 구축하여 DPO 방식으로 모델을 직접 학습시켜 Router 로 사용하였다. 사실 이 Router 부분이 가장 핵심 중 하나인데, 별도 학습 없이 prompt 만으로 분류기를 구성하였다면 knowledge intensive 한 tasks 에 대하여 원하는 성능이 나오지는 못했을 것 같다. 결국 이 Router 를 어떻게 구성하는 지가 가장 핵심인 것 같고, 학습을 위한 데이터를 어떻게 구축하였는지 별도로 설명하고 있다.

1.2. Scattered Knowledge Structurizer

Scattered Knowledge Structurizer 는 문서의 산발적인 정보를 선택된 구조 형식으로 변환하는 것이 목적이다. 즉, 원본 문서에서 산발적으로 흩어져있는 필요한 정보들을 이해하는 것도 필요하고, 선택된 구조 형태로 문서를 변환하여 질문에 맞는 정보 형태로 가공하는 것도 필요하다. 논문에서는 LLM 을 이용하여 구조화 과정을 진행하였고, 이 과정을 수식으로 나타내면 아래와 같다.
$$k_t^{(i)}, b_t^{(i)} = S(q, t, d(i))$$
구조화된 결과 $k_t^{(i)}$ 뿐만 아니라 구조화된 결과의 설명(description) 까지 $b_t^{(i)}$ 로 생성하는데, 이는 해당 구조화된 정보가 무엇을 나타내는 지에 대한 설명이다. 그리고 개별 문서에서 추출된 구조화된 지식과 설명은 전체 구조화된 지식 $K_t$ 와 전체 설명 $B_t$ 로 통합된다.

1.3. Structured Knowledge Utilizer

Structured Knowledge Utilizer 는 구조화된 지식을 바탕으로 질문 Q 에 대한 정확한 답변을 생성하는 것이 목적이다. 복잡한 질문의 경우, 이를 하위 질문으로 분해(decomposition)하고 각 하위 질문에 맞는 정보를 추출하여 이를 종합적으로 분석한 뒤에 최종 답을 생성한다. 논문에서는 수식형태로 표현하였으나, 의미적으로만 이해해도 될 것 같다. 다만, Utilizer 는 각 구조화된 정보에 맞게 prompts 를 별도 구성하였는데, 자세한 내용은 논문의 Appendix A.3 에서 확인이 가능하다. 예를 들어, Table 구조의 경우 prompt 는 아래와 같다.

Instruction:
According to the requirements described in the Requirement section, extract the complete relevant tables from the Raw Content.
Note that when constructing the table, you should include the table title and source information, such as which company's report the table comes from.
First, identify the keywords in the Requirement, including entity names and attribute names, and then use these keywords to extract information from the Raw Content. If the Raw
Content does not contain the information required by the Requirement, extract only a small amount of information that is most relevant to the Requirement.
When analyzing the Requirement and extracting from the Raw Content, do not translate; maintain the original language.
Examples:
########
|Broadway Financial Corporation and Subsidiary|\n|---|\n|**Consolidated Statements of Financial Condition**|\n|**In thousands, except share and per share amounts**|\n|**Assets**|\n|Cash and due from banks|$
6,037|\n|Interest-bearing deposits in other banks|$ 61,085|\n|Cash and cash equivalents|$ 67,122|\n|Securities available-for-sale, at fair value|$ 293,243|\n|Loans receivable held for investment, net of allowance of
$7,552 and $7,348|$ 926,497|\n|Accrued interest receivable|$ 5,638|\n|Federal Home Loan Bank (“FHLB”) stock|$ 10,292|\n|Federal Reserve Bank (“FRB”) stock|$ 3,543|\n|Office properties and equipment, net|$
9,731|\n|Bank owned life insurance, net|$ 3,286|\n|Deferred tax assets, net|$ 9,827|\n|Core deposit intangible, net|$ 2,027|\n|Goodwill|$ 25,858|\n|Other assets|$ 13,400|\n|Total assets|$ 1,370,464|
########
Raw Documents:
{documents}
Query:
{query}
Output:

2. Hybrid Structure Router Training

위에서 설명한 3개의 핵심 모듈 중, Hybrid Structure Router 가 어떻게 학습되고, 주어진 질문에 맞춰 최적의 구조 형식을 선택하는 지를 설명한다. Router 는 별도 reward model 이 필요 없는 DPO 알고리즘을 사용하여 학습하는데, 이 방식은 주어진 데이터에서 더 적합한 데이터와 덜 적합한 데이터 선택의 선호도 비교를 통해 모델을 최적화한다. 즉, DPO 알고리즘은 학습을 위해 positive 데이터와 negative 데이터 쌍이 필요하고, 어떻게 positive, negative 데이터를 구성하는 지가 가장 중요하다. (여기서는 chosen structure type, rejected structure type 으로 구분하였다.)

2.1. Data Constructing

위 그림과 같이 데이터를 구축하기 위해 synthesizing-simulating-judging 방식을 사용하였다.

1. seed 에 해당하는 Golden Tasks 를 준비한다.
2. LLM 을 사용하여 1에서 준비한 데이터를 바탕으로 in-context learning 을 통해 new tasks 를 생성한다. (Synthetic Tasks)
3. 각각의 synthetic task 에 대하여, 서로 다른 타입의 구조화된 지식을 사용하는 Simulated Solutions 를 얻는다.
4. LLM-based judge 방식을 통해 해당 task 를 해결하기 위한 simulated solutions 를 비교하고, 그에 맞는 적절한 데이터 pair 를 얻는다. (Preference Judgements) 이 데이터는 Router 가 학습하는 과정에서 각 task 에 맞는 구조 형식을 결정하는 데 사용된다.

각 과정에 대한 prompts 는 아래와 같다.

• Prompts in Synthesizing

Instruction:
In document question-answering tasks, there is a category of questions known as single-hop questions. The optimal strategy for solving this type of question is to split the document into multiple independent
chunks and then select the most suitable chunk based on the query; for chain reasoning questions, such as finding citation and reference relationships among multiple given papers, the optimal strategy is to present
the information in the document in the form of a graph; for statistical questions, such as analyzing and comparing financial data of multiple companies, the optimal strategy is to present the information in the
document in the form of a table; for configuration questions, such as needing to assemble a computer from a large batch of different models and components based on specific user needs, the optimal strategy is to
present the information in the document in the form of an algorithm; for summary questions, such as summarizing a large-scale meeting record into a meeting summary, the optimal strategy is to organize the
meeting records into a catalogue format.
Requirements:
A diversity of content needs to be generated, covering various fields and scenarios.
1.Adhere to the approach indicated in the Examples, that is, when performing question-answering tasks on such document collections, the optimal strategy is to split the documents into multiple independent chunks.
2.Use DOCUMENTS_INFO and QUERY as markers, with ## as a separator between each output.
Examples:
########
DOCUMENTS_INFO:
"Beethoven's Life", "Einstein's Life", "Newton's Life", "Da Vinci's Life", "Galileo's Life", "Voltaire's Life"
QUERY:
In which year was Newton born according to the given document collection?
##
DOCUMENTS_INFO:
2020 Financial Report of Netflix 2020 Financial Report of Alibaba 2020 Financial Report of Tencent
QUERY:
classify the companies in the above documents according to revenue, with more than 100 billion as high-income companies and less than 100 billion as low-income companies.
##
DOCUMENTS_INFO:
RAG: Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks DPR: Dense Passage Retrieval for Open-Domain Question Answering BERT: Pre-training of Deep Bidirectional Transformers for
Language Understanding T5: Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer RoBERTa: A Robustly Optimized BERT Pretraining Approach ALBERT: A Lite BERT for Selfsupervised Learning of Language Representations
QUERY:
decide the reference and citation relationship among the given documents
########
Output:

• Prompts in Simulating

Instruction:
You need to provide multiple possible solutions based on the given problem, with each solution utilizing a different type of knowledge.
Requirements:
1.The types of knowledge include three: chunk, graph, table, algorithm, catalogue
2.Your proposed solutions need to clarify how to construct the document from the current task into the corresponding type of knowledge, and how to use that type of knowledge to answer the questions in the task.
3.Follow the output format in the Examples, with each solution on a separate line, and each solution beginning with the chosen type of knowledge.
Examples:
########
Query:
Based on the documents above, summarize the development trends of this company over the past two years.
Output:
1.Chunk: To build and use chunk-type knowledge, I first need to break these financial reports into multiple independent chunks. Then, based on the query, I will select a few chunks that best reflect the company’s
development trends. Finally, I will summarize the company's development trends over the past two years based on the information from the selected chunks.
2.Graph: To build and use graph-type knowledge, I need to present the information from the documents in the form of a graph, with the company name as the head node, financial metrics as the relationships, and c
orresponding financial data as the tail nodes. Then, I will find the relevant company and subgraph based on the query and summarize the company's development trends over the past two years based on the informa
tion in the subgraph.
3.Table: To build and use table-type knowledge, I need to present the information from the documents in table form, with the company name as the rows and various financial metrics as the columns. The value in e
ach cell will be the corresponding financial data. Finally, I will summarize the company's development trends over the past two years based on the information in the table.
4.Algorithm: To build and use algorithm-type knowledge, I need to use the company’s metrics as judgment criteria, with each decision in the process determining whether to consider the information from that metr
ic. Ultimately, I will summarize the company's development trends based on this process.
5.Catalogue: To build and use catalogue-type knowledge, I need to classify the company’s different financial metrics by importance. Each level of the directory will include specific information about the metric, an
d I will draw conclusions based on all the metric information in this catalogue.
########
Query:
{query}
Output:

• Prompts in Judging

Instruction:
For the given task, there are currently multiple solutions available, each utilizing a different type of knowledge. You need to rank the effectiveness of these solutions and identify the most suitable one. First present
a comparison and analysis of each solution, and then output the final ranking results, using '>', '<', and '=' to indicate the ranking relationships.
Documents Info:
{documents_info}
Query:
{query}
Solutions:
{solutions}
Output:

3. Experiments

실험을 통한 StructRAG 의 전반적인 특징은 다음과 같다.

StructRAG 는 knowledge-intensive reasoning tasks 에 아주 강력하고,
특히 복잡한 작업에 적합하며, 정보가 더 분산된 상황에서는 성능 향상이 더욱 두드러진다.

위의 Table 1 결과를 보면, 실험 메트릭으로 0 ~ 100 까지의 score 를 결정하는 LLM judge 방식의 LLM Score 와 EM(Exact Match) rate 를 사용했고, StructRAG 는 대부분의 tasks 와 문서 길이에서 Long-context, RAG, RQ-RAG, GraphRAG 와 같은 다른 모델들을 능가했다. 이러한 결과는 지식 집약형 추론 작업을 효과적으로 해결할 수 있으며, long-context 가 요구되는 상황에서도 기존의 다양한 RAG 기법들과 비교하여 성능이 크게 향상됨을 보여준다.

또한, long-context 상황에서 다른 모델과의 성능 비교를 살펴보면 context 가 길어질수록 (Set 1 -> Set 4) 성능의 격차 (비율) 이 더 벌어지는 것을 확인할 수 있다. 이는 StructRAG 가 정보가 분산되고 복잡한 상황에서도 우수한 성능을 보임을 알 수 있는데, 그 이유로는 다양한 정보를 효율적으로 구조화하고, 이를 질문에 최적화된 형식으로 효과적으로 결합하여 처리할 수 있기 때문이다. 이는 단순히 문서를 나열하는 기존 RAG 방식 대신, Scattered Knowledge Structurizer 를 통해 필요한 정보를 추출하고 이들을 결합하여 복합적인 추론을 수행하는 것으로 볼 수 있다.

Table 2 에서는 GraphRAG 에서 소개된 query-focused summarization task 인 Podcast Transcripts 데이터셋을 기준으로 StructRAG 와 다른 모델들의 성능을 각각 win rate 로 비교하였는데, 다양한 관점 및 복합적인 성능 측면에서 대체로 우수한 성능을 보였다. 50보다 값이 낮은 경우는 성능이 더 안좋았다는 의미인데, GraphRAG 가 그나마 Empowerment, Directness 측면에서 더 우수하였다.

4. Conclusion

이 논문에서는 지식 집약적 추론 작업에서 기존 RAG 방법의 한계를 인지하고, 인간이 문제를 해결하는 방식에 대한 인지 이론에서 영감을 받아 새로운 프레임워크 StructRAG 를 제안하였다. StructRAG 는 Hybrid Information Structurization 를 통해 구조화된 지식을 최적의 형식으로 구성하고 이를 활용하였고, 주요 3가지 모듈은 아래와 같다.

1. Hybrid Structure Router: 최적의 구조 형식을 선택한다.
2. Scattered Knowledge Structurizer: 원본 문서를 구조화된 지식으로 변환한다.
3. Structured Knowledge Utilizer: 복잡한 질문을 분해하고 구성된 구조화된 지식을 통해 최종 답을 도출한다.

또한, 높은 성능의 Hybrid Structure Router 를 위해 synthesizing-simulating-judging 파이프라인을 구성하여 데이터를 구축하였고, DPO 알고리즘을 이용하여 preference training 을 진행하였다. 이를 바탕으로 StructRAG 는 knowledge-intensive reasoning tasks 에서 SOTA 를 달성하였고, 정보가 분산된 상황에서도 효과가 있음을 실험적으로 보였다.