Re-ranking Reasoning Context with Tree Search Makes Large Vision-Language Models Stronger

Thanks for your constructive reviews and address your concerns as follows.

Q1: From the Table 2, it is not clear why for InternVL-2, the Vanilla-Rag performs worse than the Zero-shot. Is that because of the quantization method for models over 7B?
A1: Thank you for pointing out this issue. Actually, we initially had similar concerns and conducted multiple experiments, obtaining consistent results. Here are some possible reasons we analyzed:

1. This issue may not be caused by model quantization, since we use the same quantized models for all experiments. The performance degradation is consistent across all methods.
2. Since InternVL-2 has been trained on ScienceQA and MathQA datasets, this might be because ICL alters the distribution of the model's outputs, resulting in failed predictions.
3. Compared to Qwen2-VL, we observe that Qwen2-VL has better performance in multiple rounds of interaction capabilities, while our RCTS implemented ICL through multi-turn conversations. This may be the reason why vanilla-RAG is inferior to zero-shot in InternVL-2.
4. As for why RCTS did not encounter this issue, this might be attributed to the fact that MCTS-HR incorporates heuristic rewards, which helps to validate the predicted results and can therefore mitigate the impact of ICL on the model distribution to a certain extent.

Q2: It is important to show the database building cost, retrieving cost, and the reranking cost to help the readers better understand.
A2: Regarding the cost issues of our model, all cost experiments are evaluated on an A800 GPU, using vllm 0.6.4, with Qwen2-VL-7B-GPTQ-Int4. Additionally, we randomly select 100 samples from ScienceQA and MathV datasets for cost comparison, and repeat tests 5 times to mitigate hardware fluctuations.

1. KB Construction Cost. The time required to construct the KB is positively correlated with the difficulty of the problems. This is because once the Score (L202) reaches the maximum value, the current reasoning context is returned as the optimal reasoning path. The cost-time is shown below: |Cost-Time (seconds)|ScienceQA|MathV| |-|-|-| |KB Construction (per)|0.94±0.06|4.28±0.22|

2. Hybrid Retrieval Cost. As mentioned in Q4 by Reviewer wbuQ, we employ Bert-Base + ViT-L (422M parameters) to extract text and image embeddings. Besides, we pre-store the features from KB using Faiss for fast retrieval. The average retrieval time per sample ranges from 5–30 ms, which is significantly shorter than the inference time required for MCTS we discuss below.

3. MCTS Inference Cost. MCTS inherently requires more simulations due to its rollout mechanism, thus consuming more cost. To enable faster responses for simpler questions, we introduced an early-stopping strategy based on answer consistency (L642–645), i.e., if the initial branch and the greedy retrieval branch yield the same answer, the result is returned, bypassing MCTS’s multi-round simulations. Therefore, our inference cost also varies depending on the difficulty of the problem. The cost time of MCTS-Reranking is shown as below: |Cost-Time (seconds)|ScienceQA|MathV| |-|-|-| |MCTS-Reranking (per)|29.55±4.5|62.32±8.6|

Q3: One thing not clear is about the retrieving key of the method.
A3: Thank you for pointing this out. Actually, we have observed this issue in L60 under the "challenge ii)". Specifically, our hybrid retrieval method computes text embeddings using the user's question and the KB questions, without including the long reasoning contexts and corresponding answers (L187-191, L211-213). This design ensures efficient retrieval of the most similar image-text pairs from the KB that align with the user’s query.
However, relying solely on feature similarity is insufficient, as the information in the KB which is not similar to the query might be an important thinking step to respond to the query. For this issue, we propose a tree search approach with Heuristic Rewards, termed MCTS-HR, which dynamically re-ranks and selects the most related samples rather than similar samples. By evaluating candidate samples through heuristic rewards, MCTS-HR identifies the most pertinent samples (i.e., those beneficial for addressing the user's question) from the candidate feature-similar samples (L209-211).

Q4: The discussion of the option of N in the experiments.
A4: Thank you for pointing this out. We take more ablation studies on N with Qwen2VL-7B, conducted on ScienceQA and MathV dataset.
It can be observed that a smaller N degrades performance, since the reduction in candidate similarity samples narrows the action space of MCTS, limiting its ability for re-ranking. On the other hand, selecting an excessive number of N introduces more noise into the MCTS action space, i.e., samples that are neither similar nor particularly helpful. Taking these into account, we set N to 20.

We thank you for your insightful and valuable reviews and address your concerns as follows.

Q1: What dataset is Vanilla RAG retrieving from? Is the info coming from the same KB but without MCTS reranking? And I think the setup for the Vanilla-RAG is not clear. It's later improved by Fig. 6 but this information comes too late.
A1: Thank you for pointing this out. Yes, the retrieved examples come from the same knowledge base, excluding the reasoning context, as shown in Table 1. Besides, Vanilla-RAG uses the same hybrid retrieval module, which is the same as our RCTS. The difference is that it only relies on the feature similarity without MCTS reranking. And we will revise this explanation earlier about Vanilla-RAG in Section 3.1 and Section 4.2.

Q2: L200-201: what is the score being used here? Why do you need SC if you have ground-truth answers?
A2: As shown in Fig. 3(b), the score is defined as the ratio of correctly predicted answers to the total number of predicted answers, computed as: $\text{Score} = \frac{N_{\text{correct}}}{N_{\text{total}}}$, where $N_{\text{correct}}$ = number of correct responses and $N_{\text{total}}$ = total number of responses.
For subsequent question, SC serves to build a VQA knowledge base with reasoning contexts. While we possess both questiones and ground-truth answers from the knowledge base, the associated reasoning contexts are unavailable. Additionally, since the model-generated reasoning paths are not entirely reliable, we use the ground-truth to verify and score these reasoning contexts. Table 6 further demonstrates the reliability of our reasoning contexts.

Q3: The purpose of rewards (especially the mutual consistency reward) should be made clear earlier on.
A3: Thank you for pointing this out. We conduct more discussions about the purpose of rewards in Reviewer eQW2 Q3. And we will add this explantion earlier on Introduction (L88).

Q4: How are you embedding images and text? Which model is used?
A4: Following Lin et al. [1], we employ the Bert-base model (110M parameters) as our text encoder for generating text embeddings. For extracting image embeddings, we utilize a ViT-L coupled with a 2-layer MLP, totaling 312M parameters. We will add this in Section 4.2.

Q5: Which model is used to construct the KB?
A5: Thank you for pointing this out. We use Qwen2-VL (7B) to construct the KB. We will add this in L290.

Q6: L262, does this mean that you are treating selecting a QA pair is an action? And it's not clear what the action space is or why this needs to be a sequential problem. In this case, the authors are selecting a set of ICL examples. It doesn't seem to me like order matters here, i.e. does selecting a different example first makes a difference?
A6: As illustrated in Eq. 5, our action space comprises multiple retrieved QA pairs, where each QA pair represents a distinct action. Besides, this can be treated as a sequential problem because ICL performance depends critically not only on the quality of the retrieved samples but also on the their orders. Accordingly, our RCTS treats different example orders as sequential decision-making problems within a set of actions (L236). Furthermore, through comprehensive ablation studies, we systematically investigate and demonstrate the importance of example orders in Reviewer x7Ua Q1.

Q7: Computational cost is mentioned in the limitations, it would be good to have a number to put to this.
A7: We discuss the computational cost at Reviewer yd6M Q2.

Q8: Essential references should be discussed.
A8: Thank you for pointing these important references, we will cite them and add discussions in the revised version. We summarize the differences as follows:

1. LLM-R [2] introduces an iterative training framework to retrieve high-quality in-context examples for large language models. In contrast, our method employs a training-free MCTS-based reranking approach, offering greater generalization compared to trained methods.
2. RATP [3] leverages MCTS + RAG to enhance the self-reflection and self-critique capabilities across numerous private healthcare documents. While sharing a similar MCTS + RAG concept, there are differences in design details, such as the setup of proxy rewards and our heuristic rewards, as well as variations in the action space design. Additionally, RATP’s knowledge base consists of document-style data, whereas our method focuses on example pairs with reasoning contexts.

Q9: A few small quibbles and typos about the language in the paper.
A9: Thank you again for pointing this out, we will fix them in our revision.

Reference

[1] Lin et al., 2024, PreFLMR: Scaling up fine-grained late-interaction multi-modal retrievers

[2] Wang et al., 2023, Learning to Retrieve In-Context Examples for Large Language Models

[3] Pouplin et al., 2024, Retrieval Augmented Thought Process for Private Data Handling in Healthcare

We thank you for your constructive reviews and address your concerns as follows.

Q1: One major concern is the assumption of this paper. Unlike other KB-VQA that mostly focuses on an external knowledge base, the knowledge base in this paper is a large number of QA pairs for each question.
A1: In RCTS, we propose a novel paradigm with reasoning VQA samples serves as the knowledge base, different from traditional RAG that relies on external sources (e.g., Wikipedia or Online Search), as detailed in L34-40.Specifically, our approach leverages reasoning QA pairs to explicitly model ICL, enhancing the model's ability to solve complex problems.
To address potential concerns about the source of KB, we leverage multiple open-source VQA datasets (e.g., ScienceQA, OK-VQA, VizWiz) and further employ an automated reasoning construction framework to build a high-quality reasoning KB.
In addition, regarding concerns about the assumptions in this scenario, RCTS aims to transition VLMs’ responses from merely known to better understood (know-how reasoning) by prepending it with retrieved reasoning examples, extensive experiments (Section 4.3) demonstrate the effectiveness of our approach, achieving a significant improvement on complex reasoning benchmarks compared to Vanilla-RAG baselines.

Q2: It is not quite reasonable to me to not do some fine-tuning, given the large number of examples for each task, while merely using them as candidates for in-context learning. I would expect the authors to provide more explanations on the motivation.
A2: Thank you for raising this important concern. Actually, the core innovation of our paper lies in exploring a method that leverages massive reasoning QA pairs as a knowledge base for performance improvement without requiring training. We will provide more explanations motivated by three key considerations:

1. Generalization Capability
   Although fine-tuning methods (SFT/PEFT) are effective, the debate between SFT and ICL hinges on a trade-off between specialization and generalization. While SFT offers more tailored and often higher performing models for specific tasks, it can lead to loss of the model’s generalization abilities, as discussed by Chen et al.[1]
2. Flexible Knowledge Base Construction
   Compared to fine-tuning, our framework is training-free and can be adaptively extended to multiple domains by simply expanding the knowledge base, as mentioned in L161-164, offering greater universality. Additionally, we have added this explanation in our Introduction to further emphasize our motivation.
3. Experiment Validation
   We follow the suggestions and explicitly compared RCTS vs. fine-tuning variants. Specifically, we take VQA pairs from the knowledge base corresponding to MathV as training samples and use Llama-Factory[2] for SFT on Qwen2-VL-2B. As shown below, the results showed that while fine-tuning improved accuracy on our test set, it caused a significant drop on out-of-domain benchmarks, validating our design choice. We believe this trade-off favors applications requiring broad adaptability.

Q3: Expect the authors to provide more explanations on the choices of the two heuristics rewards. For self-consistency rewards, it promotes the selection of QA pairs that the answer matches the generated answer. But what is the rationale behind this heuristics?
A3: Regarding the self-consistency reward, we primarily leverage the self-consistency property of VLM models (Wang et al.[3]), i.e., 'Self-consistency leverages the intuition that a complex problem typically admits multiple different ways of reasoning path leading to its unique answer.' Thus, the essence of selecting generated answers $\{A_i^{(n)}\}$ (L265) that match the predicted answers $\tilde{A}_i$ (L266) lies in choosing responses where the predicted answers and the predicted reasoning paths remain consistent.
For the mutual heuristic reward, we posit that if the answer to one question is correct, it will positively contribute to reasoning for other related questions, and vice versa (L277-280). Specifically, the reward is based on whether the reasoning context generated by MCTS-HR can generalize effectively to other questions (from KB), thereby selecting robust and transferable response.
Besides, we comprehensively take into account the two aforementioned rewards and conducted thorough ablation experiments to verify their effectiveness as shown in table 5.

Reference

[1] Chen et al., 2020, ACL, Recall and Learn: Fine-tuning Deep Pretrained Language Models with Less Forgetting

[2] Zheng et al., 2024, ACL, LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models

[3] Wang et al., 2023, ICLR, Self-Consistency Improves Chain of Thought Reasoning in Language Models

We thank you for your constructive reviews and address your concerns as follows.

Q1: Why in-context example retrieval needs such a complex tree-based search strategy? Does the order of retrieved examples matter?
A1: As demonstrated by Tan et al.[1] and Liu et al.[2], the order of retrieved in-context examples has an important effect on the generative model's response due to path dependency properties, i.e. different example orders implicitly guide the model's attention toward distinct reasoning patterns. Recognizing both the importance of example order and the combinatorial complexity in identifying optimal order, we employ a tree-based search strategy for re-ranking. This approach effectively balances exploration of potential orders with exploitation of high-performing orders through its hierarchical search structure. Besides, we further conduct experiments with shuffle/ordered examples on ScienceQA dataset to empirically validate the impact of order, with the results shown below:

Where, 'Retrieval-Order' refers to the top-3 samples sorted by similarity (i.e., Vanilla-RAG), 'Retrieval-Shuffle' denotes randomly reordered top-3 retrieval samples. 'RCTS-Shuffle' represents the shuffled orders of our RCTS re-ranking. The results demonstrate that different orders exert influence on model's performance.

Q2: The complexity of the framework, especially the application of MCTS. And the inspiration behind the application of MCTS.
A2: We justify our adoption of MCTS from the following aspects:

1. As mentioned in Q1, the order of the examples is important, which motivates us to optimize the example order. Similar to path planning (Eiffert et al.[3]), this problem can be modeled as a sequential searching problem, which is very suitable to be solved using MCTS.
2. MCTS effectively balances exploration of potential orders with exploitation of high-performing orders through its hierarchical search structure, making it more efficient than brute-force-search‌‌. Besides, our approach produce substantial performance gains, clearly justifying the computational investment in MCTS.

Therefore, we adopt MCTS over conventional retrieval methods to transition from exploiting "similar examples" to "relevant examples" (L28).

Q3: Are there any observations on the chain structure, like how the model selects the examples in such orders?
A3: Through observation of some examples of our RCTS in supplementary materials , we summarize some patterns below:

1. In the initial expansion of RCTS, RCTS prioritizes expanding from the most similar examples. When the reward value Q is high, RCTS assigns higher priority (Fig. 15). However, if the similar example face significant degradation (i.e., have very low reward values), RCTS will exclude it (Fig. 14).
2. During the expansion process of RCTS, as shown in Fig. 11 and Fig. 12, valuable examples (i.e., those with higher reward values) are repeatedly explored and utilized, even if they appear in different orders. In contrast, examples with low reward values are only used once and are not revisited afterward.
3. After RCTS reaches the maximum number of simulation rounds, it selects the branch with the highest cumulative reward value Q as the final result, even though other branches may also contain correct answers.
   Note: For all examples in the supplementary materials, the branch expansion follows a left-to-right sequence.

Q4: The time computation cost.
A4: We discuss this concern at Reviewer yd6M Q2.

Q5: The novelty and differences of reasoning knowledge base and hybrid embeddings compared to the references.
A5: 1. For reasoning knowledge base, while both our approach and AutoCoT[4] automate the generation of reasoning chains, our key novelty lies in proposing self-consistency strategy to verify the correctness of the reasoning context, making it suitable for RAG applications. We elaborate on this motivation in L185–190. 2. For hybrid embeddings, we directly adopt the retrieval module (frozen) from PreFLMR[5] in L211. The core contributions of this work lie in making them suitable with reasoning knowledge base and an innovative tree-based search strategy for re-ranking examples.

Reference

[1] Tan et al., 2023, TACL, Lost in the Middle: How Language Models Use Long Contexts

[2] Liu et al., 2024, Order Matters: Exploring Order Sensitivity in Multimodal Large Language Models

[3] Eiffert et al., 2020, ICRA, Path Planning in Dynamic Environments using Generative RNNs and Monte Carlo Tree Search

[4] Zhang et al., 2023, ICLR, Automatic chain of thought prompting in large language models

[5] Lin et al., 2024, ACL, PreFLMR: Scaling up fine-grained late-interaction multi-modal retrievers