KITAB: Evaluating LLMs on Constraint Satisfaction for Information Retrieval

[part 1 of 2]

We thank the reviewers for their detailed feedback and for finding our work to be a valuable worthwhile contribution. Next, we respond to each of the comments and questions. We’d also be happy to follow up with further clarifications.

For the open datasets (Open Library and WikiData), is there some precautions taken to "snapshot" these to a specific point in time for reproducibility purposes? - Indeed, for the sake of reproducibility, we follow two key precautions:

• Inclusion of Raw Data and Metadata: In our published dataset, in addition to our clean processed book data associated with each query, we have included the raw snapshot pulled from OpenLibrary. We have also included the metadata (birth year and popularity metric) associated with each author. This is integrated alongside the main KITAB dataset.
• Provision of Code Scripts: We provide code scripts not only for the evaluation of KITAB, but also for every step of the construction of the dataset itself, allowing users to refresh and rebuild the dataset as needed and also generate a different version with a different set of authors if necessary.

The procedures uses a few proprietary tools to develop the dataset: Azure Cognitive Services NER and Language API, Geonames in the dataset preparation. - We experimented with a few options to identify an effective and inclusive entity recognition tool and found that Azure Cognitive Services provided the most reliable and comprehensive results for our dataset. However, if users would like to replicate or update KITAB, and would like to adhere to non-proprietary tools, they can easily adapt our published code scripts to replace Azure's API with any open-source NER software they see fit. Additionally, we used Geonames, which is already an open-source tool, making it readily accessible for those who wish to use or adapt our methodology. For reference, you can check out Geonames - All Cities with a population > 1000 — Opendatasoft.

Likewise for GPT-3.5 and -4: are all the queries and responses captured somehow for reproducibility of the experiments and analysis? Some of these reproducibility concerns potentially undercut the usefulness and extensibility of the framework. - This feedback is very insightful; we have opted not to release our model responses along with KITAB, primarily due to the dynamic nature of LLMs, especially GPT models and the inconsistencies that can arise from different endpoints, leading to potential confusion. However, we have thoroughly documented all of our experiments, capturing both the raw and processed outputs from the models. To facilitate research and extend the utility of our work, we plan to include a note in our published dataset, encouraging researchers to contact the authors directly if they wish to access these detailed records. This approach is intended to maintain the integrity and reproducibility of our research while acknowledging the evolving landscape of LLMs.

[part 2 of 2]

Some of the constraints seem a little artificial: authors born in a specific year. Some of the constraint questions are out of scope of the design of current LLM's tokenization, "Book title starts with the letter v". These constraints don't accurately reflect user interaction with a LLM, I feel. - Your observation about certain constraints seeming artificial, like specifying authors' birth years and questions about book titles starting with a specific letter, is indeed insightful. The reasoning we’ve arrived at behind these constraints, however, comes from a practical standpoint. As multiple authors could share the same name, we have chosen to add the birth year in our prompts to help in distinguishing them. This approach is aimed at reducing confusion and improving the accuracy of responses, especially in cases where authors might be less well-known or have common names. We indeed saw this issue happening in practice and merely wanted to add more information to help the model and provide a better chance for it to be correct as it did in fact help for several examples that we investigated manually. Regarding constraints such as book titles starting with a specific letter, while it is indeed valid that these type of tokenization-dependent tasks might be out of scope for the LLM's architecture, we have decided to include them to assess the model's performance under various scenarios, keeping in mind that average users may not be aware of the technical limitations of language models and might still trust or expect accurate responses from the model in such cases. Another consideration is that currently users are building applications and multi-agent systems on top of existing LLMs and they are using them for tasks that traditionally we had not anticipated them for, even searching with a given string (or letter). While current LLMs do not perform well on such tasks, even if they are out-of-scope for their design, it is probably still a good idea to quantify and increase awareness as results remain unreliable.

Can you enumerate all the constraints? It's not clear from the text what exactly the single and double constraints general architecture is - Certainly, we used two main types of constraints in our study:

• Author Constraints: This specifies the author's name and their birth year. For example, "books by Gabriel García Márquez (born 1927)".
• Book Constraints: These are of six different types (mentioned in Table 2) to test for lexical, entity-based, and temporal aspects. An example is "Book contains a human name in its title". Please refer to Table 2 for details on the distribution of book constraints of different types across KITAB queries containing one and two book constraints (in addition to an author constraint), as well as Figures 5 and 6 for a visualization of the latter across author popularity and constrainedness.

In our experiments, for every query, we use one author constraint and a varied number of book constraints from zero to two. We then evaluate how well the models met all these constraints per query through a variety of metrics described in detail in section 4.1.

[part 1 of 2]

We thank the reviewers for their elaborate feedback and for finding our work to be well-constructed and a good fit. Next, we respond to each of the comments and questions. We’d also be happy to follow up with further clarifications.

The dataset is somewhat limited, being about books, years and authors. I would prefer if the dataset included a wider portfolio of constraint tasks, perhaps around geography or movies. - As mentioned in the general response, we chose the book domain as a domain that has sufficient public data to work with, but we believe that the problem of LLMs having difficulties in answering such queries is more ubiquitous. Based on research and usage evidence, similar issues have been observed when models are required to answer queries of the same nature in the scientific research domain or encyclopedia-like questions by models fabricating titles of papers that do not exist on a given topic (e.g. https://twitter.com/IttefaqM/status/1715392338535563594?s=20). Most prominently, even the earlier hallucination observed in Bard (see https://www.theverge.com/2023/2/8/23590864/google-ai-chatbot-bard-mistake-error-exoplanet-demo) was related to a similar query that also contained constraints which were not satisfied by the model (i.e., “What new discoveries from the James Webb Space Telescope can I tell my 9 year old about?” with the model including a discovery that did not actually involve the James Webb Space Telescope). While we hope that more datasets of a similar nature evolve in the community covering other domains, we hope that KITAB opens the path for such work and shows the value of being able to collect and leverage clean and complete data for similar evaluations. Note that one of the main challenges with constructing datasets in a similar vein is related to data cleaning and completeness. Even for domains around movies, geography, celebrities etc., well-known repositories are far from clean and require the integration of several data sources and robust cleaning approaches as we further discuss in the paper and supplementary material. In addition, we also wanted to provide future users with a way to create more evaluation data dynamically by using public APIs, given rising concerns around data contamination.

It would also be nice if at least one opensource LLM was used in evaluation (i.e. LLAMA or LLAMA 2) - This is a very important point and we very much agree with the reviewer’s observation. Unfortunately, at the time of investigation models in the llama family (including chat versions) did not perform well in terms of following formatting instructions, which resulted in challenges with reliable and scalable evaluation. More recently, and in particular the official deployments by Meta, are more receptive to formatting instructions, which we hope will enable us and future studies to overcome the challenges that we faced initially. At the same time, even with the most recent deployments and releases, we still notice that for this particular task model quality is so low that it is not clear whether it is possible to extract useful quantitative or qualitative insights, in particular when it comes to comparing many different open source models or performance on different constraint types. This concern was valid even for the most popular authors in the dataset, but for the mid-range and less popular authors anecdotally we see that model output may not even have a single satisfactory item. We will include a discussion on this very important topic in the paper and hope to do more of these tasks in the future for either more simplified versions of our dataset or for future open source model releases that perhaps show stronger emerging capabilities.

We thank the reviewer for finding our study timely, comprehensive, and well presented! Next, we respond to each of the comments and questions. We’d also be happy to follow up with further clarifications.

Venue fit. Concerns of the submission being out-of-scope. - It would be great if the reviewer could further clarify their concerns on scope. If the concern is related to the fact that the dataset focuses on factual IR queries rather than learning problems, it is worth noting that even though IR queries traditionally have not been considered in the ML scope, given the increasing abilities and most importantly usage of LLMs to answer these queries, it is important to share these results and artifacts with the ML community through this ICLR track focused on benchmarks and datasets. Indeed, pure LLM or LLM-based solutions are currently being used worldwide to answer exactly these types of queries, even more so in the retrieval augmented generation setting (BingChat and ChatGPT more recently), which we simulate in one of our experimental conditions.

Limited Scope. … The scope of the proposed dataset is fundamentally narrow, being confined to the domain of books. - As mentioned in the general response, we chose the book domain as a domain that has sufficient public data to work with, but we believe that the problem of LLMs having difficulties in answering such queries is more ubiquitous. Based on research and usage evidence, similar issues have been observed when models are required to answer queries of the same nature in the scientific research domain or encyclopedia-like questions by models fabricating titles of papers that do not exist on a given topic (e.g. https://twitter.com/IttefaqM/status/1715392338535563594?s=20). Most prominently, even the earlier hallucination observed in Bard (see https://www.theverge.com/2023/2/8/23590864/google-ai-chatbot-bard-mistake-error-exoplanet-demo) was related to a similar query that also contained constraints which were not satisfied by the model (i.e., “What new discoveries from the James Webb Space Telescope can I tell my 9 year old about?” with the model including a discovery that did not actually involve the James Webb Space Telescope). While we hope that more datasets of a similar nature evolve in the community, we hope that KITAB paves the path for such work and shows the value of being able to collect and leverage clean and complete data for similar evaluations. Note that one of the main challenges with constructing datasets in a similar vein is related to data cleaning and completeness. Even for domains like movies, celebrities etc., well-known repositories are far from clean and require the integration of several data sources and robust cleaning approaches as we further discuss in the paper and supplementary material. In addition, we also wanted to provide future users with a way to create more evaluation data dynamically by using public APIs, given rising concerns around data contamination.

Inclusion of Open Source Models - This is a very important point and we very much agree with the reviewer’s observation. Unfortunately, at the time of investigation models in the llama family (including chat versions) did not perform well in terms of following formatting instructions, which resulted in challenges with reliable and scalable evaluation. More recently, and in particular the official deployments by Meta, are more receptive to formatting instructions, which we hope will enable us and future studies to overcome the challenges that we faced initially. At the same time, even with the most recent deployments and releases, we still notice that for this particular task model quality is so low that it is not clear whether it is possible to extract useful quantitative or qualitative insights, in particular when it comes to comparing many different open source models or performance on different constraint types. This concern was valid even for the most popular authors in the dataset, but for the mid-range and less popular authors anecdotally we see that model output may not even have a single satisfactory item. We will include a discussion on this very important topic in the paper and hope to do more of these tasks in the future for either more simplified versions of our dataset or for future open source model releases that perhaps show stronger emerging capabilities.

We thank the reviewer for their feedback and for appreciating our contributions! Next, we respond to each of the comments and questions. We’d also be happy to follow up with further clarifications.

Generality of the dataset. Can the presented constraint types really test the ability of LLMs to satisfy constraints? - We consider 6 different constraint types to test for lexical, entity-based, and temporal constraints. Indeed, the pretrained models are not directly trained to satisfy these constraints, but that is the case for many emergent abilities of interest. Yet, we’d like to understand and measure model performance on these abilities given that current models do show non-trivial (albeit non satisfactory) performance in such tasks.

Even amongst the constraint types we consider, models may have received direct or indirect training signals. For example, entity recognition (human/city name) is a task that has been largely studied in NLP and may therefore have more explicit training data used for pretraining, while the model’s ability to apply string operations is less studied and perhaps requires different skills. This is why we disaggregate our analysis and show how performance varies across different constraints. While it is true that some of these constraints can be easily satisfied through SQL, our goal here is to test the model’s direct linguistic abilities as at the application-level not all user queries are or can be rewritten as SQL queries. Some of the constraint types we consider, can actually be mapped to concrete librarian tasks such as retrieving an author’s work (List all books by an author), indexing or searching by a given constraint (List all books by an author whose title starts with a letter), finding characters mentioned in the title (or content in more advanced versions) etc. While our goal isn’t to completely solve the library domain, we use this domain as an illustration of a much larger problem in factual inaccuracy when models are not able to follow constraints.

Evaluation procedure. While the ground truth is determined correctly, there may be some problem in the measure of irrelevance and completeness, as some fuzzy matches are allowed. - Thanks for raising this concern, it is indeed important for the measurement to be realistic. We view performance on KITAB as an “upper bound” on the LLM’s actual ability for these types of simple information retrieval tasks. Our main qualitative result is that existing LLMs already struggle to obtain good performance on KITAB, and therefore, this casts doubt on their ability to perform these sorts of constraint satisfaction tasks in general settings. This is why we are willing to overestimate model performance; indeed, our main result demonstrates that even with all of these relaxations, state-of-the art LLMs still struggle immensely with this elementary (but important) task.

In addition, relaxing the evaluation process is crucial for testing constraint satisfaction abilities in the language domain in a realistic manner without undermining model capabilities. For example, the evaluation should not over penalize the model if the model is asked to output a title that starts with the letter “c” and includes the title “The Citadel” in its results. Indeed, librarian practices do include such titles as this categorization is most useful for users. Similarly, if the model outputs the following title “Gödel, Escher, Bach” as a book by Douglas R. Hofstadter but does not mention its full title (“Gödel, Escher, Bach: An Eternal Golden Braid”) this should be considered a correct answer as the book is known with both titles. Similar reasoning goes to accounting for potential typos in the model’s answer or in our data by using fuzzy matching. In fact, we consider the evaluation process together with the appropriate implemented relaxation process as a practical contribution of the paper and will open source the artifacts to support reproducibility to this end.

As mentioned in the paper (Section 3.1 - Book collection) and supplementary material (C.1), we also run a manual annotation to separately evaluate how irrelevance and completeness is impacted by perhaps books that we were not able to retrieve with the sources used (OpenLibrary and WikiData) and find that only 5% of the GPT4 answers contain at least one book that exists on the internet from the same author but is not captured from KITAB. The impact of this on actual irrelevance and completeness is a lot lower because the number of non-found books per query is usually less than 2 while the satisfactory set is larger.

Do you also apply a threshold on the percentage of the substring, or a substring of any length is accepted? - Let’s take the example of 2 possible titles for the same book t1= “Gödel, Escher, Bach: An Eternal Golden Braid” and t2= “Gödel, Escher, Bach”. We would consider this a match if t2 \in t1 or if t1 \in t2. Therefore, we only consider full substrings as a match.