Decoding Intelligence: A Framework for Certifying Knowledge Comprehension in LLMs

We thank the reviewer for their time and constructive feedback. We address their concerns below. We hope our response mitigates their concerns and they consider increasing their support for our paper.

Utility of certificates

The reviewer correctly identifies that certification guarantees generalize only over the distribution given in the specification. Certification is generally useful as:

• Certificates from traditional neural network certification methods [1,2] are used to quantify model robustness as number of specifications that could be certified (deterministic certification) for them. We envisage similar utility for QuaCer-C as well. Average certification bounds can be used to assess and compare the general knowledge comprehension capabilities across LLMs.
• Even with knowledge graphs, language models (LMs) are needed to effectively parse natural language prompts, extract entities/relations involved in queries, and respond in desired output format. LMs enable doing this seemlessly, without significant manual efforts. Hence, they may be preferable in natural language question answering settings, even when knowledge graphs are available.
• As mentioned in our future work, for domains with documented knowledge but no knowledge graph, existing knowledge graph construction methods [3] can be integrated with QuaCer-C to certify LLMs for knowledge comprehension. Our work, being the first step in this direction, provides one component of such a pipeline.

Instances with multiple correct answers

We acknowledge this possibility and hence we prompt with multiple-choice questions (MCQs), where only 1 answer is correct and we evaluate model's answer with the known correct answer. Generalizing beyond MCQs requires evaluators that can check for any possible correct answer (and their aliases) in LLM's response. Developing such evaluators is complementary to our research and our framework can easily incorporate them. As we are not aware of any reliable evaluators with low false evaluation rates, we conduct experiments with MCQs. Our theoretical framework, however, generalizes beyond MCQs, to free-form QA with multiple possible answers (similar to aliases).

Certifying more models with varying sizes in same family

We thank the reviewer for the suggested experiment. We show results in the "new experiments" section of the general response. We understand the importance of other factors such as training data in LLM performance, and acknowledge them alongside model size in Section 4.3.

Constructing few-shot examples

We have updated the main paper with a reference to Appendix B.5 on few-shot examples. We use the same few shot examples across all prompts and have updated this detail in line 323.

Need for few-shot examples

QuaCer-C theoretically does not require few shot examples in prompts. It can work, given an evaluator for LLM responses that can extract the correct answer from unstructured text. However, such evaluators tend to be quite inaccurate in our experience and also observed by prior works [4]. Hence in practice, as correctly identified by the reviewer, we need few shot examples to convey the structure of the query and expected response to LLMs. This enables using string matching to automatically and accurately extract the LLM's response from the generated text and evaluate it.

Length, contents of context per node?

Context per node contains ~300 tokens consisting of only the abstracts of Wikipedia pages of the node's entity.

Limitation in number of distractors due to context length.

We certify several models, some of which have small context windows. These include Llama-3-8B (not 3.1) and Mistral-7B with 8k tokens each. As we want to compare the performance of different models on the same standards, we restrict to only 1 distractor in our experiments. We also want to maintain a low proportion of distracting information, relative to useful information. As the certification also uses samples with shorter path length, e.g., 3 nodes, restricting to 1 distractor ensures that the prompt has reasonable complexity. Note, however, our framework is flexible to allow multiple distractors as well, as required by the use case.

Use of Chain-of-Thought (COT)

We agree with the reviewer that COT may affect LLM performance. Please check our "new experiments" section in the general response for our certification results with COT (also in Appendix A.4).

Certification with edges with same relations.

We thank the reviewer for their suggestion. We show certificates for the suggested specifications in "new experiments" in the general response.

References

1. AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation, Gehr et al., 2018
2. Certified Adversarial Robustness via Randomized Smoothing, Cohen et al., 2019
3. A Comprehensive Survey on Automatic Knowledge Graph Construction, Zhong et al., 2023
4. Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena, Zheng et al, 2023

I would like to thank the authors for their detailed response, for providing clarifying information, and for conducting additional experiments addressing my concerns and questions.

Utility of certificates

Being able to specify knowledge comprehension queries over knowledge graphs in natural language (NLQs) and using LLMs to interpret them seems useful. However, if accurate responses are important, the more reasonable approach seems to be to use LLMs to translate the NLQs into a formal query language, execute them using some form of graph algorithm, and then process the results using LLMs again. This would be analogous to using LLMs as a translation layer to SQL for databases, rather than letting LLMs interpret table data directly. If accuracy is not critical, then certificates would probably not be required. Therefore, it is still not clear to me in which scenarios the derived certificates would be useful.

Additional results

The additional results are interesting and reassuring. The statements about the effects of model size are more convincing to me now. Seeing such a large effect from CoT prompting is also striking.

I find the results on paths with fixed sequences of relations to be promising as well, since I find measuring and potentially certifying knowledge comprehension abilities over these composite relations potentially more useful than for relation chains starting from the same node. I believe that a future version of the paper could benefit from a stronger focus on these types of relations.

I also think the results on data with random labels (suggested by reviewer 9uCh) are valuable, since they disentangle the models' knowledge comprehension abilities from confounding parametric knowledge.

While I believe that the new results are valuable, I think that the paper needs another iteration to incorporate them properly. My main concern about the utility of the certificates also remains.

Therefore, I will maintain my score.

We thank the reviewer for their feedback and appreciation of our additional results. We are constantly endeavoring to improve our work and are grateful for the enhancements suggested by the reviewer. We want to clarify our position on the utility of the certificates in this response.

We think that the alternative way of using LLMs with knowledge graphs suggested by the reviewer is interesting. However, our setting of using LLMs for end-to-end question-answering is conventionally popular among works on reading comprehension [1-3]. Moreover, our framework can be trivially extended to certify LLM systems (like the one proposed by the reviewer comprising of the LLM as a parser and a knowledge graph querying engine), as we just assume query access to the question answering system. Traditionally, benchmarking datasets to study knowledge comprehension [3-7] have also been developed with knowledge graphs, similar to our use of knowledge graphs for specifying correct knowledge comprehension. Hence, we believe that this setting is important and certificates for it are useful evaluations of knowledge comprehension by LLMs or LLM systems.

If accuracy is not critical, then certificates would probably not be required.

We respectfully contradict the reviewer. Accuracy is important for knowledge comprehension, as otherwise the task is pointless. LLMs have been conventionally compared based on their knowledge comprehension accuracy and leaderboards have been designed for the same [8,9]. Hence, accuracy is critical and certification is a reliable way to assess knowledge comprehension performance of LLM-based question answering systems.

References

1. HOTPOTQA: A Dataset for Diverse, Explainable Multi-hop Question Answering, Yang et al., 2018.
2. A Survey on Machine Reading Comprehension: Tasks, Evaluation Metrics and Benchmark Datasets, Zeng et al., 2020.
3. Constructing Datasets for Multi-hop Reading Comprehension Across Documents, Welbl et al., 2018.
4. KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation, Wang et al., 2021.
5. Multimodal Analogical Reasoning over Knowledge Graphs, Zhang et al., 2022.
6. Variational Reasoning for Question Answering with Knowledge Graph, Zhang et al., 2017.
7. OpenDialKG: Explainable Conversational Reasoning with Attention-based Walks over Knowledge Graphs, Moon et al., 2019.
8. https://crfm.stanford.edu/helm/classic/latest/#/groups/natural_qa_openbook_longans
9. https://paperswithcode.com/task/reading-comprehension

We thank the reviewer for their time and constructive feedback. We address their concerns below. We hope our response mitigates their concerns and they consider increasing their support for our paper.

Differences from existing works on KBQA and why we can't use standard benchmarks.

Please refer to general response.

Significance of task and motivation of work.

Knowledge comprehension is an important evaluation task for human learners. As LLMs attempt to achieve human-level intelligence, they should be capable to excel at knowledge comprehension, i.e., attain high performance scores (approaching 100%). Even if we consider the proprietary models such as Gemini-Pro and GPT-4o which achieve high performance, they exhibit several instances of failed knowledge extraction and/or reasoning. For example, Figure 4 shows an example of failed reasoning in GPT-4o. Table 1 shows the reduction in the knowledge comprehension performance of Gemini-Pro and GPT-4o, when the information is shuffled and distractors are included in the prompt (Shuffle Distractor setting), thus indicating that these models are not effectively able to remove additional, distracting information and navigate through shuffled pieces of information, which can be generally done by humans. Hence, knowledge comprehension is not a solved problem and we need reliable assessment and enhancement of this capability in LLMs. Prior works [1,2] have also extensively benchmarked LLMs on knowledge comprehension. However, our work differs from them by providing a reliable certification method for this property.

Adding suggested references

We thank the reviewer for the references. We have included them in our updated related works section.

Theoretical guarantees on bounds.

The certification bounds are such that the true probability of correct response for any prompt in a given distribution (e.g., distribution in lines 1-5 of Algorithm 1) $p^*$ is within the bounds with high-confidence. That is, for bounds $[l,u]$, $Pr[p^*\in[l,u]]\geq 1-\delta$, where $\delta>0$ is a small, user-specified constant. This is a property of the Clopper-Pearson confidence intervals [3], which we use as certification bounds. We provide these details in Section 3.2 of the paper. Benchmarking over static datasets, on the other hand, does not give any guarantees on the generalization of the results.

References

1. Large Language Models' Expert-level Global History Knowledge Benchmark (HiST-LLM), Hauser et al., 2024.
2. DOCBENCH: A Benchmark for Evaluating LLM-based Document Reading Systems, Zou et al., 2024.
3. The Use Of Confidence Or Fiducial Limits Illustrated In The Case Of The Binomial, Clopper and Pearson, 1934.

We thank the reviewer for their time and constructive feedback. We address their concerns below. We hope our response mitigates their concerns and they consider increasing their support for our paper.

Deeper insights

We would like to respectfully contradict the reviewer's view of our findings being predictable. The quantitative nature of our certificates enables deeper and novel insights, both model-specific and across models, some of which we mention next and also describe in the paper.

1. We find that the Phi3-3B model can do reasoning comparable to models with > 10B parameters, contradicting prior works [1,2].
2. We observe that quantization can deteriorate knowledge comprehension (e.g., 16% relative difference between performances of fp16 and 4-bit quantizations of Llama-3 8B in Table 1), contradicting prior works [3] which say that quantization preserves such capabilities.
3. We have added a new benchmarking baseline in Table 1 to compare with certification and highlight the latter's advantages. Details are in "new experiments" section of the general response.

More details of queries/context in main paper.

Please check updated Section 4.

Parametric knowledge vs knowledge in context

We agree with the reviewer that some queries can be answered by the LLM using its parametric knowledge and knowledge provided in the context may be redundant. However, even using parametric knowledge will require LLMs to comprehend the query and refer to relevant parametric knowledge to give the final correct answer. To the best of our knowledge, there is no way to definitely tell which knowledge source was used by the LLM. However, the knowledge provided in the context ensures that the LLM has sufficient information to answer the query correctly.

Random sampling of aliases and whether LLMs can link the aliases with the original entities.

We randomly select entity and relation aliases from a set of aliases derived from Wikipedia pages. Random sampling ensures that we certify with respect to all the possible aliases, which can be realistically used by users in their prompts, with equal weightage. We agree that the LLMs might be unable to connect the aliases with the entities and relations based on just their embedded knowledge and hence provide information on that upfront in the context. We have updated the paper (Appendix B.3) with this detail.

Using LLM's generated conditional probability distribution

We agree with the reviewer that evaluating the LLM responses with their generated probability distributions could be an interesting extension of our work. However, we chose to certify over the LLM's generated text for the following reasons. (1) Given that several SOTA LLMs showing good knowledge comprehension performance are closed-source, and thus do not provide the generated probabilities, the extension to using probability distributions can inhibit the applicability of the certification framework. (2) In line with most approaches for Question-Answering [4-6], we do greedy decoding for the LLM responses. Thus, the use of probability distributions would not add much to the analysis. Given that our method is based on several independent and identically distributed samples, which are sampled with replacement, we do not need to re-query the LLMs on the same prompt explicitly [7].

Clarification on 250 samples for certification

We would like to clarify that n=250 samples are used for 1 certification for a property defined on a given subgraph of a knowledge graph. The certification guarantees are for prompts in the distribution defined over the subgraph, rather than the whole knowledge graph. Hence, the comparison between the samples in 1 certificate with the full knowledge graph is not well-defined, in our opinion. For our experiments, we extracted subgraphs from the Wikidata knowledge graph by performing bounded breadth-first searches with a maximum path length of $\rho$, starting from randomly selected pivot nodes. These pivots were drawn from two populations: the top 2000 nodes by out-degree in the global graph, and nodes whose subgraph within radius $\rho$ contains at least 2000 vertices (mentioned on line 301-305). Note, however, that these subgraphs were selected only for illustration purposes and our framework is not restricted to subgraphs having specific properties about them.

References

1. Emergent abilities of large language models, Wei et al., 2022.
2. Tool learning with foundation models, Qin et al., 2024.
3. A comprehensive evaluation of quantization strategies for large language models, Jin et al., 2024.
4. Gemini: A Family of Highly Capable Multimodal Models, Gemini Team Google, 2024.
5. GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models, Mirzedeh et al., 2024.
6. TinyGSM: achieving > 80% on GSM8k with small language models, Liu et al., 2023.
7. Scalable Quantitative Verification For Deep Neural Networks, Baluta et al., 2021.

We thank the reviewer for their time and constructive feedback. We address their concerns below. We hope our response mitigates their concerns and they consider increasing their support for our paper.

Novelty and comparison with benchmarks

Please refer to general response.

Certifying over subgraphs

The idea behind certifying over subgraphs is not just to certify LLMs for answering queries related to the pivot node ("movie" from reviewer's example). It is to check whether the LLM can extract and reason over various pieces of information, starting at a pivot node to answer questions related to the pivot node. This is with various realistic corruptions of prompts, such as information shuffling, aliases, and distractor information. LLMs, which are extensively used in QA tasks, should, even under corruptions, be able to robustly provide correct answers. While we desire this accuracy over all possible QA tasks, we specify this as separate properties over local subgraphs, in line with majority works in neural network certification [1,2], to make the certification tractable. Note that, as we illustrate that longer paths can become meaningless, we restrict the maximum path lengths starting from pivot node in subgraphs over which we certify, to 5 (mentioned in Section 4.1). We observe that queries over paths longer than 5 become quite distinct from the pivot node. Our framework is not restricted to just subgraphs, however, and we show additional certification results for specifications over paths having same relations but varying entities, in "new experiments" in general response.

Intractable input space

Aliases, unstructured context, and distractors are realistic corruptions that can occur in practical user prompts and standard datasets [3,4] also contain instances of these. This necessitates accounting for random variations of aliases, information ordering, and distractor texts when certifying for knowledge comprehension. Restricting to specific prompt structures will give us limited understanding of knowledge comprehension by models (e.g., Gemini), and guarantees over the small input spaces will not be about practical user prompts. Just to clarify, we do not vary few shot examples across prompts.

Model-based paraphrases for certification

Model-specific paraphrasing could be an alternative to get knowledge comprehension prompts for LLMs. As our specification (Algorithm 1) is agnostic to distributions D over aliases, model-specific distributions are special cases that can be used to certify. That may also yield an intractable input space for realistic D. We do not make D model-specific to compare different models for knowledge comprehension on a common standard for fair evaluation. Moreover, as common users are not expected to deliberately apply model-specific corruptions to their prompts but rather introduce random corruptions inadvertently, we use the same input prompt spaces for all models.

Clarification of $\mathcal{R}$

R is a function of randomly sampled prompt P (Algorithm 1, lines 1-5), and hence a random variable. It denotes whether LLM L can output any alias of the tail node of path $\Pi$ underlying P, when prompted with P. any(.) is a deterministic primitive of our specification language. We have updated our usage of any(.) in the specification (Algorithm 1) to be more understandable. It denotes that L's output for P matches any alias of the tail node $\Pi[-1]$ of $\Pi$, as all the aliases are correct answers. We have clarified any(.) in line 234 as well. We equally prioritize different path lengths when sampling P. any(.) simply checks whether L's answer for given P matches with the correct answer for corresponding path $\Pi$. As any(.) permits L to give any correct alias as answer, we do not see any bias in the certifier due to it.

Multiple-choice format?

Our prompts contain multiple-choice questions (MCQs) similar to prior works on question-answering [5,6], which consider MCQ QA as an important task. The main challenge of free-form responses is accurate evaluation. Specifically, we need to check whether response mentions any of 100s of possible aliases of the correct answer as final answer. We observe several false evaluations, even by LLM-as-a-judge, for free-form responses. Hence, we evaluate with MCQ prompts. However, this is just an implementation detail and our theoretical framework generalizes to free-form responses too.

Including non-linearities

We agree with the reviewer on the complexity added by non-linearities for LLM certification and have added this in line 64.

References

1. Formal Specification for Deep Neural Networks
2. Fast and Precise Certification of Transformers
3. KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation
4. Large language models can be easily distracted by irrelevant context
5. Measuring massive multitask language understanding
6. Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge

These results suggest that standard benchmarking methods may present only a limited picture of the performance of LLMs for knowledge comprehension

It sounds like the main claim here is that the proposed random prompts are more accurate measurements than the baseline benchmarks, due to e.g. having prompts of varying difficulty. This feels a little orthogonal to the point of knowledge certification. While it is good to have benchmarks vary prompts by varying entity aliases, including distractor information, and shuffling information order, this has more to do with making benchmarks representative of settings that we care about, and less to do with certifying performance.

Certification of specifications with constant path relations

I think this addition to the paper is nice. It could help show that models understand a certain kind of (multi-hop) relationship between entities in the world.

If an LLM performs well in our setting, then it is less likely due to memorization.

Actually, are answers always clearly derivable from the contexts? I agree with the idea that varying the surface form realization of some underlying question can help mitigate test set leakage for LLMs. Just to keep the terminology clear, doing well on wikidata-based tasks should be pretty correlated with a model having "memorized" Wikipedia, in the sense that the model has memorized factual information from Wikipedia, even when it's not the case that the exact test-set prompts were seen in the training data.

main points of difference of our framework over traditional KBQA benchmarks

Overall, I think these points do not fully convince me that this certification framework is a better way of benchmarking model knowledge, reading comprehension, or k-hop QA ability. I like the certification idea at its core, but I feel like this point might be better illustrated by showing something like: (1) researcher 1 benchmarks an LLM on some typical knowledge benchmarks, and (2) researcher 2 tries to replicate the benchmark results with prompts that differ in reasonable ways, using some of the transformations described in this paper. A certificate from researcher 1 could help researcher 2 understand whether their results are surprising or not, if they highly over/underperform numbers from researcher 1. I understand this is basically a different paper from the one here, focused on off-the-shelf knowledge benchmarks and not k-hop QA based on wikidata. Since the authors bring up the importance of the "corruptions" multiple times in the rebuttal, while maintaining that the certificates are useful but not strictly novel, I am trying to imagine an application of both of these directions that could produce a more compelling or widely useful final result than certifying k-hop performance over wikidata.

We conduct the following experiment to distinguish between the use of parametric knowledge versus in-context knowledge by the models. We mask all entities in the Wikidata5m knowledge graph with random strings consisting of 10 characters, with a combination of upper-case, lower-case letters and digits. We certify the 50 subgraphs with the masked entities, similar to our original method. As we have masked entities, we cannot use their original contexts, as that can reveal information about the original entity. Hence, we form a new context for each entity, consisting of descriptions of all relations it has with other entities. Such context is structured as "{masked entity A} is related to {masked entity B} by relation {relation}", where relation {relation} exists between entities A and B. We asked a query with masked source node from the model and give it options consisting of masked entities, one of which is the correct answer. We certify Gemini-1.5-Flash model with QuaCer-C for the Wikidata5m knowledge graph with masked entities and obtain [0.74,0.85] as our average lower and upper bounds over 50 certificates, for the Vanilla setting (no information shuffling or distractors). These bounds are significantly higher than the corresponding average bounds in our original setting [0.46, 0.58] (from Table 1), suggesting the difficulty of unstructured and long context for the model. The improvement in the new results over the original ones suggests that the model may not have been using parametric knowledge to answer the queries, because if that was the case then the original bounds should have been higher, irrespective of the challenges posed by the context. We can show more certification results in the new setting with entity masking, if the reviewers suggest.