We appreciate the reviewer for pointing out the potential weaknesses of our paper, and we will address these concerns by answering the questions.

---

Question 1: How robust is the approach to NLI degradation? If the NLI model used for contradiction detection underperforms—e.g., on non-English or technical content—how significantly does this affect the reliability of the MIS defense?

Response to question 1:

We thank the reviewer for pointing out this potential issue. To address your concern, we have done the following additional experiments to demonstrate that the performance of our framework degrades gracefully with NLI degradation. In particular, we repeat our experiments on RealtimeQA and Mistral-7B with prompt injection attack, but impose some error probability on NLI checks. In particular, for each contradiction edge, we invert it with probability $\epsilon$ and test the performance of our framework under different values of $\epsilon$’s. The accuracy results of these additional experiments are as follows:

With $k = 10$ retrieved documents:

With $k = 50$ retrieved documents:

We can see that, even with 0.5 error probability (i.e. we invert each edge with 50% probability), our methods still demonstrate superior robustness. Note that for $k = 50$, the accuracies are almost unaffected when the attack is on position 25 or 50 because the malicious document is very unlikely to get sampled to begin with. We can thus conclude that our methods are quite robust against NLI degradation.

In addition, we would like to note that the possibility of NLI degradation is precisely why, on top of the empirical results, we have focused on providing theoretical analyses parameterized by the properties of the NLI performance. Furthermore, we have worked out and will provide new and tighter theoretical results and empirical simulations that augment this argument in later versions of our paper. Recognizing that malicious / low-quality documents might degrade the performance of NLI models, we provide a new version of Theorem 1 in which we permit larger error probability between benign documents and malicious documents compared with the current version of the paper. In particular, we show that even if the NLI model makes errors with ~0.3 probability between benign and malicious documents, our method is still $(1 - e^{O(k)})$-robust under certain natural conditions, where $k$ is the number of documents. We also conducted new simulations on the contradiction graph generation process (similar to Appendix B.1.1), and found that: even with ~0.4 NLI error probability between benign and malicious documents, the probability that any MIS includes any malicious document stays near zero until the number of malicious documents $k’$ becomes substantial relative to the total number of documents $k$. For example, robustness holds up to $k’ = 3$ for $k = 10$ and up to $k’ = 7$ for $k = 20$. Note that all of the above analysis assumes the worst case where any pair of malicious documents are non-contradictory to each other.

Ultimately, we would like to mention that we are not relying on NLI model accuracy in isolation – our defence framework adopts the philosophy of defence-in-depth. The NLI signal is used in conjunction with the ranking signal, and both are inputs to the MIS algorithm; so in order for adversaries to succeed, they need to exploit weaknesses in the NLI model and conduct adversarial search engine optimization, and do so in a way that subverts the protections provided by applying the MIS that uses both types of signals. Thus, although our approach works best when NLI is accurate, its defence-in-depth nature allows for gracefully handling of inaccuracies in NLI in the face of realistic adversaries.

---

Question 2: Could the sampling parameters be learned or adapted? Is it feasible to tune the sampling distribution or context size in a data-driven manner, rather than fixing γ, T, and m heuristically?

Response to question 2:

We thank the reviewer for pointing out this question. This is a very promising direction for future work that generally falls into the learning-augmented algorithms paradigm, and we think is feasible. In our paper, we have also provided detailed ablation studies that could guide the choice of parameters in a data-driven and compute-aware manner:

1. For $\gamma$: In our experiments, we are using exponentially decaying weights with decay factor $\gamma$ as a proxy for reliability scores of documents. This is because we are using google retriever to retrieve relevant documents and that doesn’t come with an explicit reliability score. In real deployments of our system, we would expect retrieved documents to come with some reliability score / some meta-data that can offer a nice estimate for a reliability score, then one can just use these scores in place of the exponentially decaying weights in the paper.

2. For the number of sampling rounds $T$: As we have shown in Appendix C.6, the performance of our algorithm basically monotonically increases with $T$. In other words, increasing $T$ trades off compute for enhanced robustness. Thus, in real deployment, one can just decide on an appropriate value of $T$ by considering how much compute is available. One can find an appropriate $T$ with, say, binary search, to find the maximum acceptable $T$ with a given amount of compute. $T = 20$ turns out to be a good choice that nicely balances compute and performance in our experiments.

3. For the context size $m$: As we have shown in Appendix C.6, the performance generally decreases as $m$ increases, because a larger $m$ increases the likelihood of sampling malicious documents. Thus, if one expects there to be many potentially malicious / misleading documents, one might take a smaller $m$, e.g. $m = 2$ as in our experiments. If documents being malicious / misleading is unlikely, then one can take a larger $m$ as that avoids the algorithm from potentially missing relevant and useful documents.

---

Question 3: Can the MIS selection be integrated with document reranking? For example, would combining MIS with re-ranking via learned relevance scores further enhance robustness or utility?

Response to question 3:

Yes, definitely. For example, if each document comes with a relevance / trustworthiness score, then we can construct a weighted contradiction graph where the weight of each document is its relevance / trustworthiness score. Then, we can find a weighted MIS instead of an unweighted one. Of course, the robustness / performance of this method depends on the quality of the relevance / trustworthiness score. If high-quality documents indeed have high scores, then the weighted MIS algorithm described above will more likely include them in the MIS, thus leading to enhanced robustness or utility. This is a very promising direction for future work, but out of the scope for the first paper in this space, as we wanted to demonstrate the promise of our method in the simplest conceptually possible scenario. Contradiction-based graph-theoretic methods should be a widely applicable technique that can see interesting applications in many different forms / domains.

---

Question 4: What happens when no consistent majority exists? In cases where most retrieved documents are noisy, off-topic, or benignly contradictory, how does the system avoid excessive pruning or failure?

Response to question 4:

We appreciate the reviewer for pointing out this question, which points to a major motivation for why we would want to take reliability / rank information into account. We first note that completely noisy, off-topic documents are usually useless / could even have adverse effects for answering the question correctly and the best way to deal with them is to prune them out, regardless how our system works (e.g. [1] explicitly lists “context filtering” as a canonical sub‑module of RAG pipelines, alongside retrieval and generation).

If no consistent majority exists among the relevant documents (after filtering out noisy, off-topic ones), then even humans may not effectively identify the correct answer from them. Our algorithm deals with this case gracefully though, as we explicitly prioritize higher-ranked documents. For example, say there are $k = 10$ documents and each document points to a different answer to the question. However, as long as the top-ranked document contains the correct answer, our algorithm can find it. In short, by explicitly utilizing rank / reliability information, our algorithm is still likely to find a decent answer even if a consistent majority is hasty.

---

References:

[1]. Sharma et al, Retrieval-Augmented Generation: A Comprehensive Survey of Architectures, Enhancements, and Robustness Frontiers

Dear Reviewer Xjz6,

The authors have already submitted their response to your review, and we are approaching the deadline for author-reviewer discussions (August 8, 11:59 PM AoE).

Could you please share your feedback with the authors regarding whether their response sufficiently addresses the concerns raised in your review, and if any issues remain that require further clarification or elaboration?

As a key reminder, active engagement in the discussion process is critical at this stage. Reviewers must participate in discussions with authors (e.g., by posting follow-up feedback in the discussion thread), and then submit a Mandatory Acknowledgement to confirm your participation.

Best regards,

AC

Weakness 1: Robustness hinges on NLI model accuracy; vulnerable to adversarial contradictions.

Response to weakness 1:

We thank the reviewer for pointing out this potential issue. To address your concern, we have done the following additional experiments to demonstrate that the performance of our framework degrades gracefully with NLI degradation. In particular, we repeat our experiments on RealtimeQA and Mistral-7B with prompt injection attack, but impose some error probability on NLI checks. In particular, for each contradiction edge, we invert it with probability $\epsilon$ and test the performance of our framework under different values of $\epsilon$’s. The accuracy results of these additional experiments are as follows:

With $k = 10$ retrieved documents:

With $k = 50$ retrieved documents:

We can see that, even with 0.5 error probability (i.e. we invert each edge with 50% probability), our methods still demonstrate superior robustness. Note that for $k = 50$, the accuracies are almost unaffected when the attack is on position 25 or 50 because those documents are very unlikely to get sampled to begin with. We can thus conclude that our methods are quite robust against NLI degradation.

In addition, we would like to note that the possibility of NLI degradation is precisely why, on top of the empirical results, we have focused on providing theoretical analyses parameterized by the properties of the NLI performance. Furthermore, we have worked out and will provide new and tighter theoretical results and empirical simulations that augment this argument in later versions of our paper. Recognizing that malicious / low-quality documents might degrade the performance of NLI models, we provide a new version of Theorem 1 in which we permit larger error probability between benign documents and malicious documents compared with the current version of the paper. In particular, we show that even if the NLI model makes errors with ~0.3 probability between benign and malicious documents, our method is still $(1 - e^{O(k)})$-robust under certain natural conditions, where $k$ is the number of documents. We also conducted new simulations on the contradiction graph generation process (similar to Appendix B.1.1), and found that: even with ~0.4 NLI error probability between benign and malicious documents, the probability that any MIS includes any malicious document stays near zero until the number of malicious documents $k’$ becomes substantial relative to the total number of documents $k$. For example, robustness holds up to $k’ = 3$ for $k = 10$ and up to $k’ = 7$ for $k = 20$. Note that all of the above analysis assumes the worst case where any pair of malicious documents are non-contradictory to each other.

Ultimately, we would like to mention that we are not relying on NLI model accuracy in isolation – our defence framework adopts the philosophy of defence-in-depth. The NLI signal is used in conjunction with the ranking signal, and both are inputs to the MIS algorithm; so in order for adversaries to succeed, they need to exploit weaknesses in the NLI model and conduct adversarial search engine optimization, and do so in a way that subverts the protections provided by applying the MIS that uses both types of signals. Thus, although our approach works best when NLI is accurate, its defence-in-depth nature allows for gracefully handling of inaccuracies in NLI in the face of realistic adversaries.

---

Weakness 2: MIS and NLI checks add overhead , limiting real-time use.

Response to weakness 2:

We thank the reviewer for pointing out this potential issue, and we will provide more detailed discussions in the response to your Question 1. For here, we would like to clarify that we did provide detailed discussions of the overhead of our framework in Appendix D.2. In particular, even with our current setup (which is not very optimized in terms of running time), NLI checks induce nearly negligible overhead (< 0.05s for even $k = 50$ retrieved documents). The “isolated answering” stage and MIS construction contributes to a major part of the overhead, but is still far from limiting real-time use (only around 0.2 ~ 0.4s).

---

Weakness 3: No validation for scenarios where reliability signals (ranks/weights) are miscalibrated or manipulated.

Response to weakness 3:

We thank the reviewer for pointing out this potential issue. We first note that these scenarios are somewhat out of the scope of our current work, because one major novelty of our methods is that the ranks are difficult to compromise in the search context (e.g. in google retrievers).

In addition, we would like to note that our methods could offer decent solutions even in the case where reliability signals are compromised.

In MIS, we are essentially taking a majority vote over the documents, so even if the reliability signal of a few documents are manipulated, as long as benign ones still form a majority, our algorithm will return the correct answer. If the benign ones are not the majority to begin with and, furthermore, malicious documents manage to climb up in the rank, then even humans can find it hard to effectively identify the correct answer.

In Sampling + MIS, one might control the decay factor $\gamma$ to decide how much to trust higher-ranked documents compared to lower-ranked documents. In scenarios where reliability signals can be easily compromised or are known to be of low quality, one might place more uniform weights across the documents to avoid overly trusting the higher-ranked ones.

---

Question 1: Can you measure the time overhead of actually using the framework and whether it will significantly affect the user experience?

Response to question 1:

We would like to clarify that we did provide a detailed discussion of overhead issues and potential strategies to mitigate this in Appendix D.2. In that section, we show that the running time of our entire framework is ~0.61s for $k = 10$ retrieved documents + Mistral-7B, ~0.41s for $k = 10$ retrieved documents and Llama-3B, ~1.32s for $k = 50$ retrieved documents + Mistral-7B, and ~0.92s for $k = 50$ retrieved documents + Llama-3B, with vLLM and simple parallelism like batch query. Moreover, this is just based on our prototype academic setup and can be, of course, accelerated even further with more proper parallelization and tighter system integration.

To potentially reduce the latency overhead even more, one can perform the “isolated answering” stage using a smaller, faster language model instead of the LLM for the RAG query. Such a model could rapidly assess documents for basic contradictions or irrelevance. This is likely sufficient for detecting rudimentary issues such as simple prompt injections or factual poisoning, but more targeted and nuanced attacks may bypass the filter, requiring careful consideration based on the specific threat model and application context.

Even with the current latency with our preliminary setup which induces a sub-1s latency, it will not significantly affect the user experience. Users interacting with sophisticated RAG systems often experience multi-second or even minute latencies, which can stem not only from retrieval and basic generation but also from extensive downstream processing, such as reasoning or other test-time scaling techniques applied for enhanced analysis and answer quality. Again, we would like to note that our current setup is not very optimized in terms of time overhead, as the major goal of our paper is to show the value of our contradiction-based graph-theoretic approach.

Weakness 1: At least 2 decimal points and CI / Significance would be helpful in presenting convincing evidence in the main results, generally tests have been applied sporadically.

Response to weakness 1:

We thank the reviewer for the suggestion, and we apologize that we were not able to repeat the experiments for multiple times for all experiments in our paper due to budget constraints (as we were using GPT-4o-as-a-judge to judge correctness of answers for high-quality judgement, which was quite expensive for large-scale experiments). We note that we did provide results with error bars in Appendix C.4 for $k = 50$ documents, Mistral-7B on all datasets. As presented in Figure 4 and 5, the error bars are very narrow, and our method consistently performs better than all the other baselines. We appreciate the reviewer for pointing this out, and we will provide more discussions about the statistical significance of our results.

---

Weakness 2: The motivation (L 62-63)...

Response to weakness 2:

We thank the reviewer for pointing this out, and we will revise Line 62-63 to make this distinction clear.

---

Weakness 3: The approach could be contrasted with more naive signals, given the motivation in a commercial setting why not apply naive lexical matching and observe if any attack can even succeed?

Response to weakness 3:

We thank the reviewer for raising this question. We have two interpretations for what the reviewer might have had in mind by contrasting with applying naive lexical matching. One interpretation is that it means checking how well each document lexically matches the prompt and selecting the document that matches the most. Such approaches are known to be vulnerable to adversarial attacks, and prior works show attacks with documents that are lexically / semantically close to the prompt (e.g., [3]); thus lexical matching may be a useful, but not sufficient signal. Our second interpretation is that the reviewer suggests replacing the NLI with using lexical matching to detect contradictions / non-contradictions. This is, of course, possible, and can be viewed as a simplified version of our approach. We are not sure whether we misinterpreted the suggestion, and we would appreciate it if the reviewer could clarify the approach they suggest they suggest we contrast with so that we can provide additional experimental results for it.

---

Weakness 4: The lack of human annotation (solely llm-as-a-judge) prevents evidence from being particularly compelling, simply using an openQA dataset which uses for example multiple-choice answers such that llm-as-a-judge is unneeded would be sufficient to strengthen evidence.

Response to weakness 4:

We thank the reviewer for pointing out this potential complication. We first note that llm-as-a-judge and limited datasets are a function of the cost of running such experiments, and a commercial lab less limited by costs could do it. In addition, using llm-as-a-judge (in particular, GPT-4o-as-a-judge) is already much more rigorous than many existing works with QA-dataset evaluations, such as [1] which uses direct string comparisons. In addition, using llm-as-a-judge is a widely adopted method for judging correctness of answers for QA datasets, e.g. by OpenAI ([2]). Furthermore, we human-evaluated 100 llm-judged answers on the RealtimeQA dataset, and found that all the judgments are correct.

Finally, to better address your concern, we also conduct additional experiments by constructing a multiple-choice dataset using our RealtimeQA dataset and test the performance of our methods compared against baseline methods (with Mistral-7B and prompt injection attack, using the same setup of experiments as presented in our paper):

With $k = 10$ retrieved documents:

With $k = 50$ retrieved documents:

We can see that our methods perform similarly well compared with other baseline methods in this multiple-choice setting, which offers additional evidence for the strength of our methods. We appreciate the reviewer for pointing out the value of showing this, and we will add these results and relevant discussions into later versions of our paper.

---

Weakness 5: The latency experiments without explicit weakness discussion are not convincing but with clearer discussion and acknowledgement that 4x RAG is not satisfactory in most settings, this may be considered a minor point.

Response to weakness 5:

We acknowledge that our method is inducing additional latency, but we would also like to clarify that this is just based on our prototype setup and can be accelerated more with proper parallelization and tighter system integration. To potentially reduce the latency overhead even more, one can perform the “isolated answering” stage using a smaller, faster language model instead of the LLM for the RAG query.

We note that even with the current latency of our preliminary setup which induces a sub-1s latency, it will not significantly affect the user experience. Users interacting with sophisticated RAG systems often experience multi-second or even minute latencies, which can stem not only from retrieval and basic generation but also from extensive downstream processing, such as reasoning or other test-time scaling techniques applied for enhanced analysis and answer quality.

---

Response to the Note:

We appreciate the reviewer for pointing out this relation, which is an interesting direction of future work. We would also like to clarify that, as presented in Appendix D.2, the pairwise NLI checks induce nearly negligible (instead of massive) overhead (< 0.05s for even $k = 50$ retrieved documents)

---

Question 1: You make no assumption when both documents are malicious. In practice, how often did your attacks produce malicious pairs that the NLI judged “non-contradictory,” and does this undermine robustness?

Response to question 1:

We clarify that in our theoretical analysis (Theorem 1), we assume the worst-case scenario where all malicious pairs are judged as non-contradictory, as adversarial behaviors can induce outcomes that can be arbitrarily bad. Even under this pessimistic assumption, our method shows nice theoretical guarantees. In reality, (1) In single-position attacks, there’s only one malicious document so there are no malicious pairs here. (2) In multi-position attacks, all malicious documents are constructed in such a way that they point to the same malicious answer, so any pair of malicious documents are non-contradictory, i.e., we consider the worst-case scenario in our design of experiments as well. As presented in Appendix C.5, our methods show excellent robustness against multi-position attacks, even when all pairs of malicious documents are non-contradictory. To summarize, the potential issue of malicious pairs being non-contradictory is studied and addressed both theoretically and experimentally in our paper. We apologize if our current presentation is unclear regarding this point, and we will make this clearer in later versions of our paper.

---

Question 2: Did you perform sensitivity analysis on beta, and is there a principled way to adapt it per query or domain?

Response to question 2:

Yes, we did experiment with different values of $\beta$, from 0.2 to 0.8. One observation is that the output of the NLI model (contradiction probability) is usually almost binary (very close to 0 or 1), so our results are not very sensitive to the choice of $\beta$. Since 0.5 is a natural and previously adopted choice (e.g., in [1]), we present $\beta = 0.5$ in the paper. As per our observation in experiments (which ranges many different domains and queries), there is no need for specific adaptation per query or domain. We thank the reviewer for pointing out the value of sensitivity analysis here, and we will add them into later versions of our paper.

---

Question 3: More broadly for parameters please clarify choices made for beta as mentioned, m, t etc.

Response to question 3:

We appreciate the reviewer for pointing out the importance of clarifying design choices made, and we will add more discussions regarding them. We presented extensive ablation studies regarding the choice of parameters in Appendix C.6 and discussions of their impacts, including (1). The impact of varying context size $m$; (2). The impact of varying the number of sampling rounds $T$; (3). The impact of varying the decaying factor $\gamma$; (4). The impact of weight decaying schemes.

---

References:

[1] Xiang et al, Certifiably Robust RAG against Retrieval Corruption

[2] OpenAI, openai/simple-evals Github Repository

[3] Zou et al, PoisonedRAG: Knowledge Corruption Attacks to Retrieval-Augmented Generation of Large Language Models

Weakness 1: Did the authors try applying different NLI models (I'm not sure if there are more NLI options available), and did they do sensitivity analysis on the contradiction threshold β? I'd like to see more ablation results.

Response to weakness 1:

Did the authors try applying different NLI models - Yes, we did experiment with other NLI models like deberta-v3-large-mnli, and that yields similarly good results. In particular, on RealtimeQA, with Mistral-7B and under prompt injection attack, the accuracy results for our techniques are as follows:

In general, we expect (and our theoretical results support this) most NLI models with decent performance to yield similarly good results.

Did they do sensitivity analysis on $\beta$ - Yes, we did experiment with different values of $\beta$, from 0.2 to 0.8. One observation is that the output of the NLI model (contradiction probability) is usually almost binary (very close to 0 or 1), so our results are not very sensitive to the choice of $\beta$. Since 0.5 is a natural and previously adopted choice (e.g., in [1]), we present $\beta = 0.5$ in the paper.

We thank the reviewer for pointing out the value of more ablation studies, and we will add them into later versions of our paper.

---

Weakness 2: The analysis of multi-position attacks could be more in-depth. Section 5.4 only shows partial results - I suggest providing more analysis in the main text about system behavior when attackers simultaneously corrupt documents at multiple different ranking positions. This would help understand the limits of the defense mechanism.

Response to weakness 2:

We appreciate this suggestion, and we sincerely apologize that we were not able to put more results about multi-position attacks in the main body of the paper due to limited space. More comprehensive analysis and discussions are presented in Appendix C.5, where we experimented with different corruption sizes (0, 1, 2, 3, 4 for $k = 10$ retrieved documents and 0, 5, 10, 15, 20 for $k = 50$ retrieved documents) on all the datasets. Our MIS / Sampling + MIS almost consistently perform significantly better than RobustRAG (Keyword), and show excellent robustness even when almost half of the documents are malicious.

We thank the reviewer for pointing out the importance of this part, and we will add more discussions about multi-position attacks in the main body in later versions of our paper.

---

Weakness 3.1: Some detail issues: The isolated answering step in Algorithm 1 incurs additional LLM call overhead - can this be reduced through caching or other optimizations?

Response to weakness 3.1:

Can overhead be reduced through caching or other optimizations - Yes, definitely. We did provide a detailed discussion of overhead issues and potential strategies to mitigate this in Appendix D.2. In that section, we show that the overhead of the “isolated answering” step is ~0.27s for $k = 10$ retrieved documents + Mistral-7B, ~0.16s for $k = 10$ retrieved documents and Llama-3B, ~0.38s for $k = 50$ retrieved documents + Mistral-7B, and ~0.20s for $k = 50$ retrieved documents + Llama-3B, with vLLM and simple parallelism like batch query. Moreover, this is just based on our prototype setup and can be accelerated even more with more proper parallelization and tighter system integration.

---

Weakness 3.2: Some discussion and insights would be helpful. In Figure 2's caption, "attacked documents" should clearly specify that it's a continuous suffix attack pattern.

Response to weakness 3.2:

We thank the reviewer for the suggestion, and we will change Figure 2’s caption to make it clear that we are considering a continuous suffix attack. We sincerely apologize that we were not able to provide more discussion and insights in the main body of the paper due to limited space; we placed more discussions (including more experiments, extensive ablation studies, and adaptive attack) in Appendix C. We will add more discussions and insights in later versions of our paper and in the main text.

---

Weakness 3.3: From a paper formatting perspective, I suggest the authors not use paragraph breaks in the abstract and make it more concise (the current abstract is too long).

Response to weakness 3.3:

We thank the reviewer for the suggestion, and we will prune and reformat the abstract in later versions of our paper.

---

Weakness 3.4: Similarly, I hope the authors carefully polish the introduction section. While I understand that using bold text and hard paragraph breaks can more clearly express related work, for a research paper, I'd prefer the introduction to have better overall coherence and narrative flow.

Response to weakness 3.4:

We thank the reviewer for the suggestion. We will refine the introduction section in later versions of our paper to make it more coherent and narrative.

---

References:

[1]. Shuster et al, Stretching Sentence-pair NLI Models to Reason over Long Documents and Clusters