Decoding Intelligence: A Framework for Certifying Knowledge Comprehension in LLMs

Authors: Isha Chaudhary, Vedaant V Jain, Gagandeep Singh
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords: Large Language Models, Reasoning, Information Extraction, Certification

Abstract:
Knowledge comprehension capability is an important aspect of human intelligence. As Large Language Models (LLMs) are being envisioned as superhuman
agents, it is crucial for them to be proficient at knowledge comprehension. However, existing benchmarking studies do not provide consistent, generalizable, and
formal guarantees on the knowledge comprehension capabilities of LLMs. In
this work, we propose the first framework to certify knowledge comprehension in
LLMs with formal probabilistic guarantees. Our certificates are quantitative -
they consist of high-confidence, tight bounds on the probability that a target LLM
gives the correct answer on any knowledge comprehension prompt sampled from
a distribution. We design and certify novel specifications that precisely represent
distributions of knowledge comprehension prompts leveraging knowledge graphs.
We certify SOTA LLMs for specifications over the Wikidata5m knowledge graph.
We find that knowledge comprehension improves with increasing model size.

Decision: reject
Reviewer scores: 3, 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1730325010014

thread_type:
official_review

<thread_object>
creator: reviewer_msm5

<content>
summary:
The paper introduces QuaCer-C, a protocol to assess the knowledge comprehension abilities of LLMs, i.e. their ability to extract information from reference inputs and reason over it to answer questions. To this end, the authors introduce an evaluation protocol that constructs multi-step reasoning queries together with multiple-choice answers and gathers reference information based on traversing a knowledge graph. By sampling many paths starting from the same root node, the authors are able to estimate confidence intervals for whether an LLM will answer knowledge comprehension queries based on that root node correctly. The paper uses this approach to quantitatively and qualitatively evaluate the knowledge comprehension abilities of several popular open-weight as well as closed models. The results show that closed models significantly outperform closed ones, and sheds lights on the failure modes of knowledge comprehension.

strengths:
1. Overall, the paper is well-written and easy to follow.
2. I believe that the introduced knowledge comprehension test can serve as a useful benchmark for evaluating the ability of LLMs to retrieve information from prompts, reason about that information and use it to answer complex questions.
3. The paper provides a comprehensive assessment of the knowledge comprehension abilities of many of the currently most popular LLMs.

weaknesses:
1. I am not sure in which situations the correctness certificates derived by QuaCer-C would be useful. The certificates hold for prompts sampled from the same distribution as the 250 sample prompts. But that means that certificates can only be obtained for cases where a corresponding knowledge graph exist and the relevant queries can be expressed as graph traversals. But in such cases, it would be much simpler to query the knowledge graph directly, rather than using an LLM to extract information from and reason over it. The cases where LLM-based knowledge comprehension is actually required are typically much less structured documents without a corresponding knowledge graph, but in those cases QuaCer-C cannot compute certificates. I still think the prompt construction and evaluation approach can serve as a useful benchmark for the knowledge comprehension abilities of LLMs, but I don't see a scenario where the derived certificates would be useful.
2. The approach might incorrectly mark answers as wrong in case of 1 - n or m - n relationships. E.g. in Figure 4, first row, in the example "Batman Begins: ... -> (characters) -> (artist) -> (nomination received) -> ?" there could be multiple characters (1 - n relationship) whose artists might have received different nominations. The model might pick a different but valid character than intended and then reason correctly, potentially using its parametric knowledge, and arrive at a different than expected, but still correct answer.
3. The paper claims that larger models are better at knowledge comprehension. While Table 1 provides some evidence in this direction, I believe that it is insufficient to confidently claim a size-dependent relationship, because of a number of potential confounders: 1) The smaller models in the table are all open source ones, while the larger ones are closed, and their size is not (officially) known. 2) Except for (Phi-3-3B, Phi-3-14B) and (Gemini-1.5-Flash, Gemini-1.5-Pro) (whose size difference and other potential differences are unknown), all models belong to different families, so other than size they might also differ in training data mixtures, training strategies and architecture. The only really comparable datapoint here is (Phi-3-3B, Phi-3-14B), and those two models show 1% or less difference. To make claims about model size effects more reliable, comparisons of several (open) models within the same family would be needed.
4. Minor clarity issue: It was not clear to me how the few-shot examples are constructed until I came across Appendix B.5. Please reference the appendix in the main paper and provide some minimal information about the few-shot examples, e.g. that the same fixed set of examples is used for all prompts.

questions:
### Questions
1. Does the approach also work without few-shot examples? Or are they needed to convey the answer format?
2. How long is the context (per node) and does it contain information beyond the Wikipedia page's abstract? The authors mention that only one distractor is included due to context size limitations. However, all the studied models support, or have versions that support, context lengths of at least 32k. At least if Llama-3.1-8B was used, rather than Llama-3-8B, which I'm not sure about.
3. Do the authors think that techniques like chain-of-thought prompting would change the results? The paper investigates problems that inherently require multi-step reasoning, whereas the evaluation expects models to produce the answer almost as the first token. Allowing for additional reasoning steps might significantly improve accuracy.

### Suggestions
1. It would be helpful to include the appendix into the main paper's PDF, not as a separate file.
2. It might be helpful to name the certified property, i.e. "our overall property", line 228.
3. Currently, prompts are constructed by sampling graph trajectories starting from a specific root node. Another interesting approach might be to sample trajectories whose edges all have the same relationship type, e.g. which are all of the form "... -> (appeared in movie) -> (directed by) -> ?", irrespective of the nodes that appear in them. Such an approach might be able to assess/certify how well a model can comprehend knowledge about a particular multi-step relationship, irrespective of what the exact entities are, e.g. how well the model can comprehend which directors an actor worked with.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730676396799

thread_type:
official_review

<thread_object>
creator: reviewer_w1nm

<content>
summary:
This paper aims to develop a formal certification framework for evaluating knowledge comprehension in LLMs. The authors propose an approach that frames knowledge comprehension as a formal specification using a knowledge graph. The accuracy of LLM responses is assessed by the probability of generating correct answers to knowledge comprehension prompts sampled from a distribution based on the knowledge graph. However, this approach, in my opinion, closely resembles a basic KBQA evaluation process for LLMs and lacks difference compared to existing work. Furthermore, current proprietary models, such as Gemini-Pro and GPT-4o, have already demonstrated impressive accuracy in knowledge utilization, as shown in Figure 3, with performance scores between 0.7 and 0.8, which raises questions about the significance of this task and the motivation of this work.

strengths:
1. This paper provides a detailed description of the approach, including the formalization, theoretical framework, and algorithmic implementation.
2. Models of varying sizes and employing different pretraining techniques are evaluated.

weaknesses:
This paper provides an extensive and complex introduction and description of the approach for formalizing knowledge comprehension evaluation using a knowledge graph. The knowledge comprehension capability of LLMs is assessed by measuring the accuracy of their responses to prompts sampled from paths within the knowledge graph. However, (1) there is no rigorous theoretical proof to guarantee the approach, and (2) it appears to be a very basic, standard KBQA evaluation process using LLMs nowadays, lacking distinction from existing work. I find the motivation, novelty, and differentiation of this work unclear. Some related work is omitted like [1,2]

[1] Zha, Hanwen, Zhiyu Chen, and Xifeng Yan. "Inductive relation prediction by BERT." Proceedings of the AAAI conference on artificial intelligence. Vol. 36. No. 5. 2022.
[2] He, Xiaoxin, et al. "G-retriever: Retrieval-augmented generation for textual graph understanding and question answering." arXiv preprint arXiv:2402.07630 (2024).

questions:
1. Is the evaluation process merely a standard method of sampling questions from a knowledge graph to assess LLMs? If so, why not utilize existing KBQA/GraphQA datasets?
2. Is there any theoretical guarantee for the bounds introduced?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730706983381

thread_type:
official_review

<thread_object>
creator: reviewer_9uch

<content>
summary:
The authors introduce QuaCer-C, a framework designed to assess knowledge comprehension in LLMs by sampling paths of lengths 1 to 5 from the WikiData5m knowledge graph and constructing context + distraction + query sets as tasks for the models to complete. Since responses are evaluated on a success/fail binary basis, Clopper-Pearson confidence intervals are used to establish upper and lower bounds for the resulting metrics. Experiments on major closed-source and open-source LLMs indicate that larger models perform better, while shuffled contexts and added distractors degrade performance.

strengths:
1. Provides a robust quantitative probabilistic framework for evaluation.
2. Overall, the presentation is clear and the structure flows well.
3. Accompanied by code for reproducibility.

weaknesses:
1. The findings are somewhat predictable and could benefit from deeper insights.
2. Some redundant content in the main text could be replaced by key details currently in the Appendix, such as the process for generating queries and context.
3. There’s ambiguity as to whether the LLM’s responses are derived from embedded knowledge or the provided context, thus raising questions about true comprehension. The prompt itself does not restrict the LLM to answer based solely on the given context. For example, in a hypothetical question like “Matthew Perry→(character_acted_by)→(birth date)→?”, the LLM could respond from its internal knowledge base rather than relying solely on the provided context.

questions:
1. Given that the framework already uses a probabilistic approach, why not leverage the fact that an LLM can act as an implicit conditional probabilistic model? For instance, adjusting the output threshold or re-querying could yield probabilities that reflect comprehension more accurately.
2. Relating to weakness 3: Why are aliases for entities and relations randomly sampled? This approach may inadvertently query the LLM’s embedded knowledge (e.g., recognizing that alias A corresponds to B), which might not be present in the provided context.
3. Regarding sampling: How does the chosen sample of n=250 compare in ratio to the full knowledge graph? Additionally, how do we justify that this sample is unbiased, given that only the top 2000 nodes and edges are selected?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730789528401

thread_type:
official_review

<thread_object>
creator: reviewer_nuwn

<content>
summary:
This paper proposes to provide formal guarantees of model knowledge, as elicited by prompts derived from Wikidata. The object of the formal guarantee is the correctness of an answer to a question representing an arbitrary k-hop question stemming from some pivot node in the Wikidata knowledge graph. The means of formal guarantee is a binomial proportion confidence interval. To the best of my understanding, what this means is that the method guarantees model correctness with high confidence over a subgraph of Wikidata. The reason this requires a probabilistic guarantee, and cannot be done exhaustively, is that the combination of contexts for the questions, distractor text to provide alongside context, and few-shot examples for prompting the method creates a large prompt space that would be infeasible to exhaustively search. Experiments demonstrate that the authors can often bound model accuracy over a subgraph of Wikidata within about +/- .05 points.

strengths:
- Important: I like the spirit of trying to give formal guarantees to model correctness for LLMs, which are difficult to handle analytically. The approach of using binomial proportion confidence intervals is a simple but appropriate one.
- Important: Experiments are carefully designed to demonstrate the main claims of the paper. A wide variety of models are tested.

weaknesses:
- Important: While the main result in this paper is interesting, I also find it hard to say that it is especially impactful. The basic approach is to use a binomial proportion confidence interval to  estimate a model accuracy over a data distribution. The only way that this setting differs from any typical ML benchmark is that the authors define a data distribution over a subnetwork of Wikidata. As the authors note in L.242, longer paths in k-hop questions can result in somewhat surprising or meaningless queries. So I ask, what is really the point of certifying knowledge over such a subgraph? As in the qualitative example, we are not certifying knowledge about a movie. Rather, we are certifying knowledge about a movie, as well as a surprisingly diverse set of entities that are related to the movie. And, even if we were certifying knowledge about a movie, the next question is if the method in this paper merits publication if it primarily just makes use of an existing analytical binomial proportion confidence interval.
- Of some importance: While I believe the central point that we cannot exhaustively test deep learning models over input spaces is well-received, the paper has to introduce some complexity in order to make this difficulty appear in the first place in their setting. Specifically, aliases, contexts, distractors, and few-shot examples are randomly ordered in order to make the input space too large to exhaustively search. I believe it would also be possible to fix a basic set of instructions for strong models like Gemini and do these questions zero-shot. In that setting, there would not be a large combinatorial space to explore. Or, it might be more appropriate to generate model-based paraphrases of the input question, which may be more naturally representative of knowledge query diversity than the chosen approach.

questions:
- L.65: strictly speaking, it’s not just the high number of parameters, right? Also nonlinearities?
- What makes R in L.274 a random variable? Is the any(.) operator effectively a uniform distribution? How is it defined? Later, when the paper says “we equally prioritize the different possible path lengths”, does this mean that the any(.) operator appropriately reflects this choice, or is there any bias in the estimator?
- Why use a multiple-choice format? Is the task too difficult otherwise?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732217876893

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response (2) - Novelty

comment:
> [nuWN,w1nm] Comparison with benchmarks

Following are the main points of difference of our framework over traditional KBQA benchmarks [4-6].
1. Avoiding test set leakage: Unlike benchmarking with standard KBQA datasets, the distribution-driven analysis of QuaCer-C provides more consistent and reliable assessment of knowledge comprehension. This is because, analysis with distributions avoids test set leakage, where models are trained on the test set. Prior works [1-3] have shown inconsistent benchmark analyses, which could be due to test set leakage. Distributions, however, are not fixed datasets that models can memorize during training. We sample from them by running probabilistic programs (Algorithm 1). Hence, if an LLM performs well in our setting, then it is less likely due to memorization.
3. Generalizability: QuaCer-C's high confidence bounds generalize over prohibitively large distributions. Conventional benchmarks can not scale to such distributions, due to their enumerative analysis. 
4. Holistic analysis with varying challenges: Typical KBQA datasets capture only limited kinds of potentially adversarial corruptions of prompts, such as using different aliases [4], distractors [5], and information ordering [6]. Extending them to include more challenges requires significant manual effort. However, our distributions are generalizations of various kinds of corruptions and enable a holistic study of knowledge comprehension.
5. Insights on worst and best-case performance: We provide a new baseline on benchmarking with a static dataset, in the "new experiments" section of the general response. We see that the baseline is an optimistic view of knowledge comprehension in LLMs, missing out on several failure cases of the models. Certification with QuaCer-C can, however, indicate the worst and best-case performance of the models with certification bounds, constituting a robust assessment. The average certification bounds can be used as measures of robust knowledge comprehension alongside benchmarking results, like prior works on certifying neural networks [7,8].

>[nuWN] Novelty

As reviewer nuWN points out, we design novel distributions and their samplers over related problems to specify correct knowledge comprehension by target LLMs. As we believe and prior works [9,10] discuss, designing sampleable input distributions is important to establish desirable properties over given ML models and crucial for probabilistic certification [11,12]. For specialized properties, like correct knowledge comprehension, we need specific prompt distributions, which can capture natural, challenging prompts requiring the property and from which we can efficiently obtain independent and identically distributed (iid) samples. Our distributions are the first prompt distributions for knowledge comprehension, to the best of our knowledge. They capture realistic but challenging prompts with long, unstructured context by incorporating entity aliases (from Wikipedia pages), information shuffling, and distractor information. Moreover, their sampler (Algorithm 1, lines 1-5), can efficiently generate iid samples.

We do not claim novelty in the statistical estimation method used, but rather in enabling its use for certifying knowledge comprehension with novel distributions. Binomial proportion confidence intervals require iid samples from distributions over which estimation is done. While we find them suitable for certifying LLMs (nuWN also agrees to their suitability), leveraging them directly without distributions of prompts for knowledge comprehension is not possible. This is because standard datasets do not guarantee that their elements are sampled iid. We strongly believe that identifying and enabling an existing statistical estimation algorithm to provide the first formal guarantees for the important property of knowledge comprehension in LLMs can be a valuable contribution towards trustworthy LLMs. Prior works, such as [7,11] which have also used existing statistical methods for trustworthy AI have been well-received by ICML and ICLR and have been very impactful.
## References
1. Larger language models do in-context learning differently
2. In-context learning and induction heads
3. Why larger language models do in-context learning differently
4. Large language models can be easily distracted by irrelevant context
5. Constructing Datasets for Multi-hop Reading Comprehension Across Documents
6. KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation
7. Certified Adversarial Robustness via Randomized Smoothing
8. Property-Driven Evaluation of RL-Controllers in Self-Driving Datacenters
9. Adversarial Distributional Training for Robust Deep Learning
9. NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks
9. A Statistical Approach to Assessing Neural Network Robustness
9. Probabilistic Verification of Fairness Properties via Concentration
</content>
</thread_object>

</thread>
<thread>
creation date:
1732217938168

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
Dear Area Chair and Reviewers, 

We thank the reviewers for their time and positive feedback. We are encouraged by the reviewers finding our work to be well-formulated and extensively evaluated.

For the Area Chair: As per the reviewers' suggestions, we have included additional experiments (shown below) and have updated our paper with the details. We are happy to conduct more experiments and provide further clarifications, if needed. The revised paper now contains the Appendix attached to the main paper (instead of supplementary material). The text added to the revised paper is highlighted in red color.

## Updates to paper
1. New baseline results added to Section 4 and Table 1.
2. More details on query and context construction added to Section 4 of main paper from the Appendix.
3. Appendix A.4 added with new chain-of-thought experiments.

## New experiments
> [9uCh] Benchmarking baseline 

We include a new benchmarking baseline in Table 1 (Section 4) of the revised paper. The baseline results give the accuracy of LLMs on a static dataset formed with randomly-selected paths in the subgraphs of Wikidata5m which we also use in our certification results in Table 1. The baseline setup is described further in Section 4, Lines 338-342 of the revised paper. Comparison with benchmarking baseline reveals important discrepancies. Firstly, the baseline shows an optimistic view of LLM performance for knowledge comprehension, with high numbers. It fails to capture many vulnerabilities of LLMs due to evaluation on a fixed dataset with limited challenges. Certification, however, explores various vulnerabilities of the models by evaluating with multiple prompts with varying difficulties. Moreover, baseline testing shows Mistral-7B outperforming Phi3-3B, as well as scores that exceed the certification upper bounds. Additionally, Phi3-14B's 8-bit quantized version shows large performance drops when compared with the fp16 model in baseline testing. These results suggest that standard benchmarking methods may present only a limited picture of the performance of LLMs for knowledge comprehension, sensitive to the particular details of constructing the prompts and the static datasets.

> [mSM5] Additional models with varying size from same family

We certify Llama-3.2-Instruct 1B, 3B, and 11B models to substantiate our claim on the improvement in knowledge comprehension with model size, within the same model family. Unfortunately, we do not have the resources to certify much larger open-source models. The performance show clear improvement from the 1B to 3B to 11B models with average certification bounds - (0.24, 0.35); (0.30, 0.41); (0.34, 0.46) respectively, demonstrating that increasing model size leads to better performance.

> [mSM5] Use Chain of Thought (COT)

We apply COT to Phi-3 (3B) in the vanilla (no information shuffling/distractors) setting. We provide details of our experimental setup and results in Appendix A.4. As anticipated, performance improved, yielding a new range of (0.44, 0.56) - a *10% increase* in both average lower and upper bounds. This highlights the broader applicability of our framework, which is compatible with various prompting techniques and models. While we acknowledge the potential benefits of COT, earlier experiments were limited due to the significantly increased computational cost of COT (generating 5-8 times more tokens), particularly with closed-source models as output tokens are expensive.

> [mSM5] Certification of specifications with constant path relations

The suggested specification can be certified with a trivial extension of our framework. We show 2 example certificates next. We certify Phi-3 (3B) over queries formed from paths of the kind - "...$\rightarrow$(appeared in movie)$\rightarrow$(directed by)$\rightarrow$?" (suggested by mSM5) and "...(host country)$\rightarrow$(flag description)$\rightarrow$?" (very common path in Wikidata5m). Specifically, we (uniformly) randomly select paths having the above structure but varying entities that are related by the aforementioned relations. We form queries from these paths by selecting (uniformly) random aliases of the path entities. We generate the Clopper-Pearson confidence intervals with $250$ prompt samples from the distribution over such paths and obtain the certification bounds - (0.74, 0.84) and (0.68, 0.80), respectively. We hypothesize that the bound values are high because the paths are simple and common ones in the knowledge graph, involving just $2$ reasoning steps. Paths with higher number of reasoning steps, agnostic of the individual entities, are less common in the knowledge graph. We are happy to provide more example certificates of similar properties, if the reviewer suggests. However we are unable to put these certification results in the paper, as it would not be compatible with the current writing of the theoretical sections.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces QuaCer-C, a framework for certifying knowledge comprehension in LLMs using knowledge graphs. While the approach attempts to provide statistical confidence in model responses to knowledge comprehension prompts, reviewers highlighted several weaknesses. Key concerns included the limited practical utility of the certification process due to its dependence on structured datasets like knowledge graphs, lack of novelty compared to existing KBQA methods, and unclear theoretical justifications. I recommend rejection.