GraphIC: A Graph-Based In-Context Example Retrieval Model for Multi-Step Reasoning

Authors: Jiale Fu, Yaqing Wang, SIMENG HAN, Jiaming Fan, Chen Si, Xu Yang
Primary area: foundation or frontier models, including LLMs
Keywords: In-context learning, multi-step reasoning, thought graphs, large language model

Abstract:
In-context learning (ICL) enables large language models (LLMs) to generalize to new tasks by incorporating a few in-context examples (ICEs) directly in the input, without updating parameters. However, the effectiveness of ICL heavily relies on the selection of ICEs, and conventional text-based embedding methods are often inadequate for tasks that require multi-step reasoning, such as mathematical and logical problem solving. This is due to the bias introduced by shallow semantic similarities that fail to capture the deeper reasoning structures required for these tasks. We present GraphIC, a novel approach that leverages graph-based representations of reasoning processes, coupled with Bayesian Networks (BNs) to select ICEs. Graph structures inherently filter out shallow semantics while preserving the core reasoning structure. Importantly, BNs capture the dependency of a node’s attributes on its parent nodes, closely mirroring the hierarchical nature of human cognition—where each thought is shaped by preceding ones. This makes BNs particularly well-suited for multi-step reasoning tasks, aligning the process more closely with human-like reasoning. Extensive experiments across three types of reasoning tasks (mathematical reasoning, code generation, and logical reasoning) demonstrate that GraphIC outperforms both training-free and training-based models in selecting ICEs, excelling in terms of both effectiveness and efficiency. We show that GraphIC enhances ICL’s performance and interpretability, significantly advancing ICE selection for multi-step reasoning tasks.

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

Reviews and discussion:
<thread>
creation date:
1730080343556

thread_type:
official_review

<thread_object>
creator: reviewer_uqot

<content>
summary:
This paper studied in-context example selection for ICL, and proposed a novel GraphIC method to capture reasoning processes for ICL in multi-step reasoning. GraphIC first generated thought graphs for candidate examples and query with LLM to encode the reasoning steps, and then employed a BN with PPR mechanism to studied the associated parameters reflecting the underlying reasoning structure. Finally, GraphIC selected the candidate examples with the parameter maximizing the probability of thought graph for the query in ICL. The authors conducted extensive experiments, and the results demonstrated that GraphIC outperformed both training-free and training-based baselines across various multi-step reasoning tasks.

strengths:
1. The idea of selecting ICE with reasoning structure rather than semantics is novel and inspiring, and the human cognition-inspired methodology of capturing the underlying reasoning process with thought graph and BN is interesting.
2. The inference of the proposed method is solid, which makes the method more reasonable.
3. The authors conducted extensive experiments and deeper analysis to demonstrate the effectiveness of the proposed method and its components.

weaknesses:
1. There are some concerns on the method design.
- According to the prompts in the Appendix, the proposed method seems to exploit the answer to generate the thought graph for both examples and the query. So where does the answer come from? If the answer is fetched from the annotations, it seems to lead to label leakage. If the answer is generated by the LLM, how to ensure its consistency to real solution?
- As the authors have mentioned in section 3, BN works on the DAG. However, there exist loops in thought graphs for codes which violate the DAG assumption as shown in Figure 3.
2. The presentation of the manuscript could be further improved especially for the confusing and unclear contents.
- The authors should explain the formal definition of the thought graph more clearly. Maybe one example could help. For example, what does one vertex and edge mean in the thought graph (does one vertex mean one step), how can it capture the reasoning processes, and how is the corresponding text attribute got. If the text is that in Figure 3, I do not think it contains much useful information. Besides, it would be better to explain the vertex, edge and random variable of BN in section 3 more clearly.
- Related works on BN should be cited properly.
- The insights behind the parameter W should be explained more clearly. Why the parameter can reflect the reasoning structure, and why the probability computed with parameter of the example and graph of the query can reflect their similarity on reasoning?
- The insights of the matrix B in PPR is confusing. What does the matrix mean and why can the matrix realize the retracing. Perhaps the authors could provide one example.
- The author mentioned that the asymmetry of the proposed method, so I wonder the advantages of the asymmetry compared with symmetry.
3. Some concerns on the experiments.
- The authors could add the LLM without ICL as one baseline to demonstrate the improvements more clearly.
- It would be better to add experiments to compare the computation time of the proposed method and other ICE selection baselines.
- In Figure 4, it seems that the proposed method does not work very well with 1-4 shot. It would be better to make clearer explanation.
- It would be better to add studies on the effects of lambda.

questions:
See the Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730225013879

thread_type:
official_review

<thread_object>
creator: reviewer_eg3j

<content>
summary:
This paper studies how to retrieve demonstration examples more effectively in in-context learning to improve the performance of in-context learning. Specifically, the paper proposes a method named GraphIC, which establishes thought graphs and models them as Bayesian networks, then retrieves demonstration examples that make the probability density of queries' bayesian networks maximum. Experiments show the effectiveness of the proposed method.

strengths:
* The motive of the paper is reasonable and the method proposed is novel.
* Writing of this paper is good, with reasonable structure.
* The experiments are relatively abundant, and the experimental results can prove the conclusion of the paper.

weaknesses:
* Some parts of the method section of the paper lack some details, there are many assumptions but no conditions, refer to questions.
* Method relies on LLM to construct a thought graph, which may be difficult or inaccurate to decompose key steps for complex problems.
* The lack of experiments on the thought graph, in my opinion, is an important part of the method and has a big impact on method performance, refer to questions.

questions:
* In the 'Estimation of Model Parameters' paragraph, the rank of W is set to 1, there is no theoretical basis for this hypothesis, and how much precision loss is caused?
* As mentioned in weakness, LLM is probably hard to construct thought graph, do you try more complex datasets, such as widely used mathematical MATH dataset [1]?
* How accurate is the LLM at generating a thought graph? 
* Multiple generations of the LLM may produce different thought graphs, how much will this affect the results?

[1] https://github.com/hendrycks/math/
</content>
</thread_object>

</thread>
<thread>
creation date:
1730656305445

thread_type:
official_review

<thread_object>
creator: reviewer_1szm

<content>
summary:
This paper proposes GraphIC, a graph-based method for in-context example retrieval aimed to multi-step reasoning tasks. GraphIC models CoTs as "tought graphs, and uses Bayesian networks and personalised pagerank for selecting in-context examples with similar underlying graph structures. Empirical results show marginal improvements or competitive results on a wide array of reasoning tasks (GSM8K, AQUA, MBPP, ProofWriter).

Bayesian Networks (BNs) are a common way to represent complex joint distributions over sets of variables; however, this work never formalises which joint distribution the BNs in this work aim to represent. Furthermore, in Eq. 2, it is not really true that "commonly, in BNs, $p(x_i | pa(v_i)) = g(dist(x_i, \hat{x}_i))$" -- BNs aim at representing dependence distributions between variables, like "rainy weather" and "risk of aqua planning", and it's not really clear what a distance function between those variables should represent.

Furthermore, the paper is based on the construction of "thought graphs", but it's not really clear what these are -- are they task dependent? How do they look like? Given a taks, how does someone create a "thought graph"? The paper also says that "to facilitate computation, we further represent the vertex attribures as the BERT embedding of corresponding text" -- what is going on exactly?

Then, my understanding is that the BN defines a distribution over "thoguht graphs", and that the distribution over $\hat{x}_i$; what does $\hat{x}_i$ represent? (E.g. in Eq. 8)

Results seem to be marginally better than the baselines in most cases, but it's really hard to understand what's going on in the proposed method.

strengths:
The proposed method seems to produce marginally better results than the baselines in most cases.

weaknesses:
It is very hard to understand what's going on in the proposed method -- for example, the method uses Bayesian networks but the paper never explicitly states which join distribution the Bayesian network aims to represent.

questions:
Can you please explicitly state, e.g., what joint the BN is representing? What exactly is a "graph of thought"? Can you please provide a brief, clear, and self-contained description of the proposed method?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730661233899

thread_type:
official_review

<thread_object>
creator: reviewer_gzw4

<content>
summary:
This paper focuses on improving the selection of the in-context examples. It proposes GraphIC, which leverages the graph-structure and Bayesian Network to select in-context examples for complex reasoning tasks. Experiments on three types of reasoning tasks (math, code, and logical reasoning) demonstrate GraphIC outperforms the other ICE selection methods.

strengths:
1. This paper uses a formalized reasoning representation to construct a thought graph for complex reasoning problems. Based on that, it can better model the underlying reasoning process than the semantic representation of natural language.  
2. It enhances the graph embedding by the personalized PageRank and establishes a probabilistic model for the thought graph. GraphIC retrieves in-context examples by selecting top-k candidate examples that can maximize the probability of generating the correct thought graph. The probabilistic method can better capture the examples that can enhance the reasoning of the new query.  
3. The paper verifies the proposed method on diverse reasoning benchmarks with multiple training-free and training-based retrieval baselines, and the results demonstrate its effectiveness.   
4. It further conducts a comprehensive ablation study on each component and investigates the symmetry of different retrieval methods.

weaknesses:
1. GraphIC relies on the thought graph, which is generated by formalized reasoning representation from LLMs. How to ensure the correctness of the thought graph of candidate examples? Will it be multiple possible thought graphs for the same query? Will these factors affect the robustness of GraphIC?  
2. For a test query q, GraphIC first creates the thought graph G^q without the ground-truth answer and retrieve in-context examples to maximize the probability density p_i(X^q). This also assumes that the thought graph G^q is correct. What if the thought graph has an incorrect reasoning process? Will it mislead the retrieval and thus affect the performance?

questions:
1. Can you estimate the extra inference and time cost for GraphIC? For other retrieval baselines, they do not need to create the thought graph.  
2. In Figure 4, the performance keeps increasing with more in-context examples. Do you think it will benefit from more than even more examples? For example, on MBPP, can 16-shot outperform the CEIL baseline?
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary: The paper presents GraphIC, an approach for selecting examples for in-context learning (ICL) that focuses on capturing reasoning structure rather than just semantic similarity. The proposed method leverages graph-based representations called "thought graphs", something inspired by Bayesian Networks (BNs) and personalized PageRank to improve relevance scoring. Empirical studies conducted show better results for GraphIC on 4 tasks (spanning mathematical reasoning, code generation, and logical reasoning) against chosen training-free and training-based baselines.

Strengths:
- Important problem of example selection for ICL
- Good direction of using graph representation (but details are confusing as mentioned in weakness)
- Comparison with both training-free and training-based baselines (but gains are somewhat marginal currently, should show on more complex tasks where thought graphs have potential to shine brighter)
- Provides ablation for different components and robustness to incorrect thought graphs

Weakness:
- The submission received a lukewarm response from the reviewers and several concerns were raised.
- Lack of clarity in explaining key concepts like thought graphs and their construction
- Ambiguity in the proposed probabilistic framework as the joint probability distribution modelled by BNs was unclear
- Applicability to complex tasks where thought graph is motivated to shine most is not clear as there is limited evaluation on more complex datasets
- Concerns about the consistency and correctness of LLM-generated thought graphs
- Presentation issues making technical details hard to follow
- Additional inference time compute needed due to thought graph construction for marginal improvements.

Decision:
While the work shows promise and addresses an important problem, unfortunately, the paper can't be accepted in its current form and addressing all the concerns would warrant another round of reviewing.