KITAB: Evaluating LLMs on Constraint Satisfaction for Information Retrieval
Authors: Marah I Abdin
Suriya Gunasekar
Varun Chandrasekaran
Jerry Li
Mert Yuksekgonul
Rahee Ghosh Peshawaria
Ranjita Naik
Besmira Nushi
Venue: ICLR 2024 poster (2024)
Keywords: language model evaluation
benchmark
constraint satisfaction
information retrieval
retrieval-augmented architecture
Primary area: datasets and benchmarks
TL;DR: State-of-the-art LLMs struggle with answering constraint satisfaction queries for finding information. We contribute a dataset and an evaluation study to support progress in this emerging ability.

Abstract: We study the ability of state-of-the art models to answer constraint satisfaction queries for information retrieval (e.g., “a list of ice cream shops in San Diego”). In the past, such queries were considered as tasks that could only be solved via web-search or knowledge bases. More recently, large language models (LLMs) have demonstrated initial emergent abilities in this task. However, many current retrieval benchmarks are either saturated or do not measure constraint satisfaction. Motivated by rising concerns around factual incorrectness and hallucinations of LLMs, we present KITAB, a new dataset for measuring constraint satisfaction abilities of language models. KITAB consists of book-related data across more than 600 authors and 13,000 queries, and also offers an associated dynamic data collection and constraint verification approach for acquiring similar test data for other authors. Our extended experiments on GPT4 and GPT3.5 characterize and decouple common failure modes across dimensions such as information popularity, constraint types, and context availability. Results show that in the absence of context, models exhibit severe limitations as measured by irrelevant information, factual errors, and incompleteness, many of which exacerbate as information popularity decreases. While context availability mitigates irrelevant information, it is not helpful for satisfying constraints, identifying fundamental barriers to constraint satisfaction. We open source our contributions to foster further research on improving constraint satisfaction abilities of future models.

Published as a conference paper at ICLR 2024
KITAB: EVALUATING LLMs ON CONSTRAINT SATISFACTION FOR INFORMATION RETRIEVAL
Marah I AAbdin
Suriya Gunasekar' Varun Chandrasekaran" Jerry Li
Mert Yuksekgonul Rabee Ghosh Peshawaria' 1
Ranjita Naik'
Besmira Nushi'
Microsoft Research, University of Illinois Urbana-Champaign, Stanford University
ABSTRACT
We study the ability of state-of-the art models to answer constraint satisfac- tion queries for information retrieval ge.g.. "a list of ice cream shops in San Diego"). In the past, such queries were considered to be tasks that could only be solved via web-search or knowledge bases. More recently, large language models (LLMs) have demonstrated initial emergent abilities in this task. However, many current retrieval benchmarks are either saturated or do not measure constraint sat- isfaction. Motivated by rising concerns around factual incorrectness and hallu- cinations of LLMs, we present KITAB, a new dataset for measuring constraint satisfaction abilities of language models. KITAB consists of book-related data across more than 600 authors and 13,000 queries, and also offers an associated dynamic data collection and constraint verification approach for acquiring simi- lar test data for other authors. Our extended experiments on GPT4 and GPT3.5 characterize and decouple common failure modes across dimensions such as in- formation popularity, constraint types, and context availability. Results show that the absence of context, models exhibit severe limitations as measured by irrele- vant information, factual errors, and incompleteness, many of which exacerbate information popularity decreases. While context availability mitigates irrelevant information, it is not helpful for satisfying constraints, identifying fundamental barriers to constraint satisfaction. We open source our contributions to foster fur- ther research on improving constraint satisfaction abilities of future models. [
INTRODUCTION
Answering factual queries is one of the many emerging abilities of large language models (LLMs) (OpenAT 2023) Touvron et al.) 2023) Chowdhery et al., (022). This has reinvented the way search engines operate by involving conversational L.MSs directly as part of the user experience (e.g., BingChat). As with many emerging abilities, rigorous evaluation remains a challenge due to continuous lack of appropriate benchmarks, benchmark saturation, training data contamination, and difficulties in evaluating open-ended generated output from LLMs (Chang et al.) [023 Liang et al.)
2022). At the same time, several concerns have arisen over repeated occurrences of LLMs fabricat- ing talse information or providing irrelevant content (informally termed as hallucinations) (Bender
al. 2021 Bommasani et al. 2 Zhang et al. 2023 Sun al. 2023a).
This work studies and evaluates constraint satisfaction capabilities of LLMS in the context of in- formation retrieval (IR). Similarly traditional constrained search problems (Meseguer) 1989), constraint satisfaction queries in IR are queries that include a set of constraints to be satisfied by the generated output. The framework has been recently proposed for studying and detecting factual errors of LLMs by Yuksekgonul et al.] (2023) as a useful perspective which also connects informa- tion popularity and constraint feasibility to the LLM's 's ability to satisfy such constraints. Here, we employ the same framework to guide LLM evaluation and experimental design. Queries with con- straints can also be considered as the more general form of keyword, boolean, or pattern-matchinn queries (Baeza- Yates et al. 1999) and faceted web search (Tunkelang) 2009 Hahn et al. 2010)
https:: httpss://ugggnggee waceffcc...om www.aaee..coo....aooooooooooe.oe htt.aa/..oo.ttttteeeetrrooooooee Correspondence ma rah abdi www.iiooooof...mm con and besmi rushi @mi croso ft. com.

---

Published as a conference paper at ICLR 2024
Relevant information
Irrelevant information
(Books from the author)
Completeness f
All Correct t
Satistied f
Unsatisfied
GPT4
0.26
0.33
0.00
0.51
0.49
0.78
0.24
0.19
0.21
0.24
0.26
0.70
0.08
0.08 0.31 0.15
GPT3.5
0.20
0.44
0.00
0.44
0.26
0.68
0.36
0.30
0.32
0.16
0.16
0.47
0.07
0.02
Table 1: Aggregated model performance KITAB for 3 prompts NO-CONTEXT SELF- CONTEXT WITH- CONTEXT (see definitions in $ B3.)) for queries requesting list of books from a given author satisfying one additional book constraint. Both models have high rates irrelevant information and poor constraint satisfac- tion across the board. Context availability mitigates irrelevant information rate, but constraint satisfaction still remains low. Full correctness (i.c., perfect match of the post-proeessed model output and the ground truth) is strikingly low across all conditions and models but there is visible improvement for WITH-CONTEXT. Similar results for queries with two book constraints are shown in Appendix, Table
where constraints are expressed in natural language. For example, the query "A list of research pa- pers authored by (author) published after {year)" naturally specifies at least two constraints the required output. While the variety of constraint types across user requests in an L..M-poeree search engine can be large and some constraints may be more difficult to parse and verify, funda- mentally, many user interactions fall under this definition, particularly in scenarios where users seek specific and precise information rather than open open-ended, creative text.
While several benchmarks and reports exist for evaluating factual correctness on simple, single con- straints queries that expect a single-output item (e.g., "Which city the capital of Ukraine") (Lin) et al. 2 Flazar et al. 2021: K Kwiatkowski et al. 2019 Zellers et al.) 2019). many of them have saturated. Little is understood about the performance of LLMs on more complex queries with sev- eral constraint types and that generate longer outputs. Staying consistent with constraints on longer text generations important to study as this is a major differentiator between previous and newer ar- chitectures (Chang al.) 2023), which exhibit better self-consistency. Surprisingly, as will show in this analysis, staying consistent with external constraints remains challenging even for state-of- the-art LLMs (GPT4 and GPT3.5) trained on internetsscale data (see Table To better understand how and when these inconsistencies occur, we contribute KITAB, a dataset and dynamic data col- lection approach focused literature queries, from efficient retrieval and has sufficient public information potentially also used during training (e.g., on Wikipedia). KITAB queries are of the form: "A list of all books from Toni Morri son published between 197C - 1980?", where the first constraint is fixed to an author and the following can vary among lexical, temporal, and named entity constraints.
classical example of a domain that can benefit
We use KITAB to test LLMs across different controlled conditions, specifically, their: i) baseline ability to retrieve all books from an author (ALL-BOOKS), ii) performance on queries that have both an author constraint and book constraints using only the parametric knowledge (NO-CONTEXT), iii) performance when they have access to "complete"" context with all books from the author, to differentiate between parametric and retrieval -agmeetel settings iv) performance for standard chain-of- of-thought prompts and prompts that require the LLM to first construct its own context with all books from the author, does not use other systems (ELF-CCNNEETT) These conditions enable us to carefully characterize and decouple failure modes for the task, and draw insights follows:
and finally
self-sufficient retrieval approach that
Using only their parametric knowledge, state-of-the art LLMs have a high rate of presenting ir- relevant (potentially hallucinated) books not written from the given author, varying between 12% and 41%. Irrelevant information increases abruptly for authors with lower popularity.
Complete context availability addresses irrelevance, but constraint satisfaction failures remain a major obstacle across both L.LMs and different constraint types, even with complete context.
Self-retrieval approaches significantly increase the rate of irrelevant (potentially hallucinated) in- formation and fabricated titles that are not from the author, for the sake of satisfying constraints. While GPT4 improves all scores when compared to GPT3.5, the difference between the two LLMs is not as dramatic showing that scale alone may not address the filtering with constraints problem. All correctness (i.e., perfect match with the ground truth) remains notably lower than 35%.
Besides the dataset and a detailed report on GPT4 and GPT3.5, the work also contributes an approach for collecting and cleaning other versions of KITAB using the same process but disjoint author list. The process can be of significant importance to confront benchmark saturation or leakage and to support independent testing in situations when the initial dataset may be used in training.
2

---

Published as a conference paper at ICLR 2024
2 BACKGROUND & RELATED WORK
Factual Queries: Most prior work focuses on locating specific facts in the LLM's parameters (Meng
et al.) 2022, Geva al. 2023 Mallen et al. 2022). understanding how the LLM's performance in these tasks can be improved (Chuang et al. 2023 While these works indirectly benchmark the LLM's ability correctly respond to factual queries, they primarily focus short responses, using datasets that are saturated (i.c.. with reasonably high or SOTA performance already), or worse- contaminated. For example, [Noi al. (2023) note that GPT4 is able reproduce questions from SQuAD 2.0 (Rajpurkar et al. (018) verbatim, while OpenAT (2023) notes contamination for MMLU (Hendrycks et al.] (2020]. and [Sun et al. (2023b) highlight how GPT4 achieves SOTA results for BEIR (Thakur et al.) (002)).
A promising solution fact-finding failures and hallucinations to combine generation with re- trieval mechanisms as done in retrieval augmented generation (RAG) (Nakano et al. [202T] Lewis) al. 2020)). As we discuss in $ [3.2 we simulate this setting by providing the desired complete information in-context and then evaluate the LLM in its ability to respond to factual queries. In prac- tice, (pre-)retrieval RAG can introduce new challenges across many domains, especially when the retrieval engine is unreliable or expensive.
Constraint Satisfaction: As discussed by Yuksekgonul et al. (202)), many queries (and tasks) can be viewed through the lens of constraint satisfaction. Using this same lens provides us with a natural framework for generating queries with varying notions of complexity i.c. by altering the constraints. The main distinction between this study and work by Yukkekgonul et al. (2023) is that we contribute a dataset (and functional evaluation) that is challenging even for large proprietary models like GPT4; Yuksekgonul al. (2023) propose an attention-based method for mechanistic understanding and detecting failures of open-source models using model internals. More broadly, other tasks that can be viewed as constraint satisfaction problems include planning (Valmeekam et al. 2022), instruction tuning (Zhou et al. (023).. and controlled generation (Zheng et al. (023).
Constraint and Query Complexity: One way of measuring query complexity is using the notion of constrainedness (Meseguer) 1989; Gent et al. 1996). which views this as a function of the num- ber of solutions for given constraint. In similar spirit, we measure the complement of the ratio between the number of solutions S that satisfy the constraint and the total number of items in the domain (higher constrainedness, more complex), i.e., K = =I seen as the opposite of query selectivity in database systems (Getoor et al.) (200)), i.e., the percent- age of records that satisfy the query. Constraint popularity measures the popularity of entities within specific constraints (more popular, less complex). Ideally, popularity would directly measure infor- mation frequency in training data. In absence of such information, we use the number of sitelinks in the author's WikilDat page. In many open-world problems, it is not possible directly compute popularity or constrainedness, which is why we make this information available in KITAB.
Constrainedness can also be
METHOD
Research Questions. Whether users may be looking up general knowledge facts (e.g., "Which vac- cines are due at four years old?") or using LLMs to research and collect information on a topic (c.g., "A list of all authors from Africa who have won the Nobel Prize?") ?"),, failure to sat- isfy the given constraints and factual errors may lead to lack of trust, frustration, and safety concerns (e.g., in settings such soliciting healthcare advice). Our goal is to dissect model performance and create transparency around when and how current LLMs fail on constraint satisfaction queries. To guide dataset and experimental design, we focus on the following research questions:
RQI: How does model performance vary depending on the type of constraint?
RQ2: How does model performance change if complete information is made available in-context?
RQ3: How does model performance vary depending on content popularity and constrainedness?
RQ4: What the main bottlenecks in constraint satisfaction queries in IR for current LLMs?
To answer these questions, we designed the KITAB dataset. KITAB contains queries with high diversity in the (i) type of constraints, (ii) number of candidate solutions (i.e., constrainedness), and
3

---

Published as a conference paper at ICLR 2024
5k
One book constraints
Two book constraints
starts-With
number of queries
ends-with
Constraint Type
queries constrainedness
# queries constrainedness
4k
word-ccunt
starts-with
598
0.90
2163
0.92
publishingggeer
ends-with
482
0.89
1782
0.91
3k
cit-naam
no-dity name
word-count
1672
0.53
1630
0.81
2k
human--nmme
0.77
292
0.89
no-luumnn-nmme
no-human-name
611
0.23
801
0.78
1k
city-name
611
0,92
197
0.81
no-city-name
611
0.08
831
0.77
0
20
40
60
80 100
publishing-year
3043
0.80
1804
0.89
Popularity
Summary
8239
0.67
4750
0.87
Figure I: Author popularity for one book constraints.
Table 2: KITAB statistics on constraint frequency and average constrained- ness. Two book constraint queries have more than one constraint type.
(iii) author popularity (i.e., a proxy for frequency in the dataset). Figure D and Table summarize main data statistics. More detailed information is also available in Appendix, Figure and 6
3.1 KITAB DATA COLLECTION
Author sampling. To seed the data collection, first sample 20,000 authors (i.e., entities marked as writers) randomly from WikiData, as a public data source that has been potentially used for the training of several models (Gao et al. 2020). To avoid potentially inaccurate data and extreme out- liers, we filter out authors that were born before 1850 and those that have less than 10 or more than 300 works linked to their profile, which results to 1505 authors. Next, we rross-reference these au- thors with the Open Library repository using the author name and year of birth, keeping only those that have at least five works in Open Library (after book cleaning and deduplication), resulting in 599 authors. These filtering choices ensure that the final sample contains both useful and natural distribution of author popularity for which it is possible to construct satisfiable queries. We focus on popularity since previous works (Carlini et al. 2022, Biderman al. 2023 Yuksekgonul et al.
2023
Mallen et al.] 2022) identified popularity as key factor for factual errors. While Mallen et al.
2022 measure popularity through the number of page visits, [hhkoouhi (2011) demonstrated that
page visits are seasonal and might paint false picture of popularity. Henceforth, similar to Yuk- sekgonul et al. (2023), we use the number of website links in WikiData
proxy to information popularity. Figure ! shows the distribution of the number of site-links in WikiData (as a proxy for popularity) across the whole sample, which includes an additional control set of 12 handpicked well-known authors from the five continents. The control set was used for repeated quality checks on the data cleaning workflow described next. The final sample contains 61 authors.
Book collection. Using the name of the author and their year of birth, we cross referrnffe the Open Library corpus and collect all books from the author that are tagged to be in English by the API, or where the language field is empty. Then, we make an additional check using the Azure Cognitive Services Language API for language detection such that we keep only the earliest English edition ti- tles, given that our prompts are also in English. Further, the data cleaning process involves number of quality and consistency checks, namely on deduplication and cross-checking the authorship and publication year of the book both the Open Library and WikiData. We also keep variants of the same title to facilitate model evaluation when the same book may be known with slightly different ti- tles and bylines (e.g.. "Gödel, Escher, Bach" vs. "Gödel, Escher, Bach: An Eternal Golden Braid")). Despite our best efforts in collecting complete and accurate set of books, we also faced a variety of challenges in retrieval and cleaning, which we further describe in Appendix C.I To estimate the extent of which potential data cleaning issues may impact the data quality of KITAB and fur- ther evaluation, we also undertook manual data annotation exercise during which we searched the web for titles provided by GPT4 and GPT3.5 but that were marked as "not from the author" in our dataset. summary, we find that based on a manual annotation of a subsample of queries, less than 5% of the queries to GPT4 and less than 6% of the queries to GPT3.5 may potentially be affected by cases where the model finds a book title that is not in KITAB (and that will consequentially be marked as not from the author during our evaluation). While this can be remediated by using further data sources, the impact of missing information on our evaluation is minor.
Together with books, KITAB also provides variety of book metadata to enable verification func- tions for constraint satisfaction, including: publication year, list of human or city names in the title (if any). Entity recognition for human names was done using both Azure Cognitive Services and
4

---

Published as a conference paper at ICLR 2024
GPT4 (Template 4 in Appendix D. found the two approaches to be complementary for de- lecting names from different cultures. For city names, we use Azure Cognitive Services along with Geonames, database of cities with more than 1000 inhabitants (Opendatasoff 2023).
Constraints and queries. All queries in KITAB have the following form:
List all books written by Toni Morrison (born in 1931). that
author constrains.
were first published between 1970-1980.
book constraint
In each query, the first constraint is always fixed to an author and the following can vary among lexical (title starts or ends with a letter, word count in title), temporal (published between start and end year), and named entity (city or human name present not present in title) book constraints to test for different constraint satisfaction capabilities. Since there exists a large number constraint instances depending on their cardinality, we subsample from the large set of queries in way that ensures i) a balanced representation across constraint types, and ii) a variety of constraints that have different constrainedness. We also add "unsatisfiable" constraints, which do not match any book titles in our data-this constitutes 7.99% of the queries.
The final dataset contains 8239 queries with book constraint and 4750 queries with two book constraints. Table 2 shows how these queries are distributed across different constraint types. For most double-constraint queries, both constraints are individually satisfiable and generated by com- bining our single constraint data. Only 0.76% of the queries are jointly unsatisfiable across both constraints. Further details on the constraint sampling process are presented in Appendix $
To enable offline model evaluation, KITAB includes a mapping of all books that satisfy each of the 12,989 queries. Altogether, this provides a convenient tool also for the evaluation of L.M generated output, which we detail in $ 4. While for this work we focus on the literature domain, the workflow design can prove useful for other domains as well (e.g., movies, restaurants, research papers etc.).
3.2 EXPERIMENTAL CONDITIONS
To answer the presented research questions, we lay out the following experimental conditions that map to specific prompt templates, which are detailed in Appendix(D] All templates in this list (except Template 1) ask the model to provide a (prior) brief reason to why book in the output list satisfies a given constraint, as a standard chain-of-thought approach.
ALL-BOOKS (Template 1): List all books from the author. This condition enables us to estimate an upper bound of model performance in retrieving relevant information for all queries, regardless of other constraints. In experimental results, we will use the notion of the ratio of books that are not from the author as the rate of irrelevant information since these items are irrelevant to the query, regardless of whether the other constraints how information irrelevance changes between queries that have none, one, or two adittional book constraints, for settings that use only the model's parametric knowledge.
satisfied. This condition then helps in decoupling
NO-CONTEXT (Template 2a): List all books from the author that also satisfy other book constraints. The same template used for testing two book constraints. This condition will measure model per- formance in satisfying different types of constraints, using only the model's 's parametric knowledge.
WITH-CONTEXT (Template 2b): First, provide full list of books from the author as input context to the model. Then, ask the model to list all books from the author that also satisfy another book constraint. The same template used for testing two book constraints. This condition intends to simulate aurieval-augmentee settings Nakano et al. (202T): Lewis et al. (2020) where the retrieval part of the system can provide complete context to the model and the model's 's task is then to just run and verify the constraints. While retrieved context may often also be incomplete in practice, here we provide the list of all books from the author known to KITAB to isolate potential failures to only model shortcomings for verifying constraints. Note that some of the constraints (but not all) could also be solved through declarative languages (i.e., SQL) if the input context is structured or could even require the model to write code for constraint verification. However, given the broader nature of our queries and the fact that relevant input context is usually not structured, here are interested in testing the native abilities of the model to verify basic constraints.
5

---

Published as a conference paper at ICLR 2024
SELF-CONTEXT (Template 3): Ask the model to first self-retrieve all books from the author, and then use that list to find those that also satisfy book constraints. This tests whether the model can simulate a self-sufficien retrieval setting,
more advanced chain-of-thon tfttouhh approach.
SINGLE-ITEM (Template 4): Ask the model to apply a constraint on a single book title to decouple the performance of the model in applying constraints a single item from applying constraints to a whole list. Here, we sample 400 queries using a single book as described in Appendix $ C222
4 EXPERIMENTS
We evaluate the performance of GPT4 and GPT3.5 our dataset, with prompt templates and max- imum token length as defined in Section 3.2
All experiments were done with temperature 0.
4.1 METRICS AND EVALUATION
The guiding principle for the design of metrics used in this evaluation was to be as lenient as possible to the model while still being able measure important positive and negative trends. In early evaluations we found that model answers may vary slightly from the ground truth answer, e.g., by omitting a byline in the title, outputting variations of the title, or repeating a title. To ensure these factors do not artificially decrease model performance, we design our metrics to accommodate for such partial and/or fuzzy matches. For counting constraints, we also consider titles that have one word more or less than the specified constraint as satisfied, to add more tolerance to the evaluation. Surprisingly, even with all of this leeway, SOTA models still perform poorly on KITAB.
Calculating information irrelevance and partial satisfaction. For each query and the answer that the model provides, we calculate the fraction of irrelevant books, as well as the fraction of satisfying and unsatisfying answers, in way which accommodates for repeated titles, partial titles, and fuzzy matches. We do so as follows. First, we process the final list of answers from the model into a set of strings K = (ki,... }. For each k, check if there exists book in the ground truth set of books by that author which is either a string subset match for k, (in both directions), or if any book in the ground truth is at 80% match in Levenshtein distance. If it passes either of these checks, we associate it to that ground truth solution. Otherwise, we mark the book as irrelevant (i.e., not from the author). We then cluster all strings which match the same ground truth into a single cluster. This process yields partition of K into m clusters Cı,-... Cm where each cluster is either a size 1, containing single irrelevant book (i.e., a book that is not written by the author), or cluster where all books are mapped to the same ground truth book. We call the former the set of irrelevant clusters, and the latter the relevant clusters. We then further break down the relevant clusters into two types. We say that a relevant cluster is satisfying cluster if any of the strings in the cluster satisfy the constraint, and otherwise we say it is an unsatisfying cluster. Note that intentionally, we are not naming irrelevant clusters hallucinations because it can be the case that book retrieved by the LLM exists but is not from the author. This is more difficult to check because it requires access to the whole set of books ever written, albeit qualitatively we see several cases with numerous titles that do not even appear on web search and potentially do not exist.
With these definitions, we can now define our metrics. For each query, we report the fraction of irrelevant, satisfying, and unsatisfying clusters. We denote these three quantities by Pirr Psat, and Punsat. respectively. By definition, Pirr + Psat + Punsat
We emphasize that these are very generous terms for the model, and that as result, it is quite possible that we are overestimating the true model performance. However, we believe that this makes our qualitative finding that SOTA models still struggle on this task to be even more interesting.
Calculating completeness and all-correctness. We also wish to evaluate the fraction of correct answers that the model returns, i.e., its completeness. For every query, we define the completeness of the model's s answer as follows. For each book in the ground truth, we check if it is an approximate match to a book by the model, using the same methodology as above (i.e. subset matching and fuzzy matching). We then define the completeness of the model's 's answer, denoted pcomp. to be the fraction of ground truth answers that have such an approximate match. Finally, we say that the model's 's answer is all correct if Psat and Pcomp = 1. This is the strictest evaluation metric that measures whether the model made no factual errors for the query and found all relevant information.

---

Published as a conference paper at ICLR 2024
Relevant information
Single Item
Irrelevant information +
(Books from the author)
Completeness
All Correct
Satisfied +
Unsatisfied
|
starts-with
0.96
0.41
0.36 0.01
0.50 0.57 0.79
0.09 0.07 0.20
0.29
0.31
0.83
0.11
0.17
0.47
ends-with
0.80
0.23
0.38 0.00
0.23
0.28 0.31
0.54 0.34 0.69
0.15
0.17
0.46
0.04
0.05
0.06
word-count
0.58
0.21
0.33 0.00
0.61
0.53
0.63
0.17
0.14
0.37
0.07
0.09
0.39
0.00
0.00
0.02
human
0.70
0.36
0.39 0.01
0.41
0.46 0.84
0.23
00.4
0.15
0.16
0.19
0.61
0.06
0.07
0.23
no-human
0.65
0.32
0.36 0.00
0.57
0.55 0.90
0.10 0.09
0.10
0.25
0.31
0.83
0.00
0.00
0.13
city
0.56
0.12
0.46 0.00
0.77
0.38 0.66
0.11
0.16 0.34
0.33
0.26
0.38
0.31
0.20
0.31
no-city
0.54
0.36
0.34 0.00
0.59
0.61
0.93
0.05
0.05
0.07
0.31
0.32
0.91
0.00
0.00
0.26
pub-year 1.00
0.21
0.27
0.00
0.46
0.47
0.90
0.33
0.26 0.10
0.31
0.34
0.88
0.11
0.12
0.33
Summary
0.80
0.26
0.33 0.00
0.51
0.49| 0.78
0.24 0.19 0.21
0.24
0.26
0.70
0.08
0.08
0.31
Table 3: GPT4 performance on KITAB for NO-CONTEXT SELP-CONTEXT CONTEXT across different con- straint types for queries with one hook constraint. Results for GPT3.5 are shown in Appendix, Table Similar evaluations for queries with two book constraints are presented in Appendix, Table 6nd respectively.
4.2 RESULTS
Overall results. We present the overall statistics averaged over the entire dataset in Table | For each metrie, results are shown for NO-CONTEXT SELF-CONTEXT WITH-CONTEXT conditions in order. Overall, GPT4 performs quite poorly on this dataset, and although it performs better than GPT3.5, the difference not so dramatic, suggesting that improvement on constraint satisfaction tasks may not come simply by scaling up. While thain-of-thoughl helps improve accuracy. it does not seem sufficient by itself, see Appendix F (Example 1), and in fact, advanced chain-of-thought (measured by SELF-CONTEXT) increases the incidence of irrelevant books. We also observe that while the incidence of irrelevant books becomes negligible when the context is provided (WITH- CONTEXT), this does not solve issues with constraint satisfaction, completeness and all correctness, see Appendix [F (Example 2). Model performance remains unreliable even with provided complete context from KITAB, simulating search-assisted settings.
We also break down performance by query type in Table 3 for GPT4 and Appendix, Table for GPT3.5. We find interesting variations between query types. GPT4 struggles much more with ends-with than with starts-with queries. Differently from the starts-with constraint, for the model to satisfy the ends-with ones, it has plan ahead and look into the future of several token generations that may lead to a sequence ending with a letter. For mtidy-bbsed queries, we see that negation queries (e.g., doesn't 't contain) are easier to satisfy and that is reflected in model performance. Yet, even in the best performing types, GPT4 makes a non-negligible fraction of errors.
Popularity. We next consider the correlation between popularity (as measured by WikiData sitelinks) and model performance, in Figure 2 for GPT4, See Appendix, Figure 7b for GPT3.5. Surprisingly, while irrelevant information decreases with higher popularity, we do not see clear positive correlation between popularity and desirable outcomes such as the satisfaction, complete- ness, and all-correctness. Again, this result shows that constraint satisfaction remains a difficult task to solve only with larger data (i.e., higher popularity). One interesting and, to our knowledge, novel observation is that seems there is a relatively sharp "phase transition" " in the incidence of irrelevant books relative popularity. When the number of sitelinks for the author is very small, i.e. between 0-10, irrelevance is quite high. Afterwards, the rate of irrelevant books drops, but quickly flattens out, and does not improve with more sitelinks, with any statistical significance. We conjec- ture that this is because "pragmatic decisions" need to be made during training time; with models devoting memorization resources only after seeing the author a number of times. Of course, this is simplistic view to the observed quick transition in popularity, and the phenomenon warrants future research. Importantly, all correctness remains strikingly low across all conditions and popu- larity bins (< 35%). The finding has important implications to the reliability and completeness of information, if models evaluated in this work were to be used as part of larger automated systems.
Constrainedness. Figure the relationship between constrainedness (as defined in Section and GPT4 model performance. Similar results are shown for GPT3.5 in Appendix, Figure Sb) Here, we see a more nuanced phenomenon when results are aggregated across different constraint types, with model performance resembling an S-curved, almost bimodal distribution, consistent for both models. This is easier to observe in Figure 3 for the WITH-CONTEXT condition, in particular for completeness and all-correctness. To better understand the dynamics, we then disaggregate the same figures but per each constraint type in Appendix, Figures 9 and TO First, we find that while
7

---

Published as a conference paper at ICLR 2024
Bur Unseristed Poeset
0.8
Performnce
0.6
0.4
40-60
63-90
80-100
20-40
40-60
0-20
20-40
40-83
80-100
Author popularity
Author popularity
Author popularity
Pur
0.8
Complstennes
Perforanno
0.6
0.4
20-40
40-60
60-50
80-100
0-20
20-40
60
60-80
80-100
0-20
20-40
40-80
60-80
80-100
Author popularity
Author popularity
Author popularity
Figure 2: GPT-4 performance KITAB comparing NO-CONTEXT(lef), SELF-CONTEEX((iddlgg and WITH- CONTEXT(right) queries various popularity hins. We show trends for irrelevant information, and unsat- isfaction rate top plot; satisfaction, completion and correctness rates in bottom plot.
0.8
Unswisffed Punar
Perforance
0.6
0.4
0.0-2.
0.2.4
0.6-066
0.6-0.5
0.8-1.0
0.0.0.2 0.2.0.4
04-06
066088 0.8-1.0
0.0-0.2
0.2.04
04-06 0.6-0.8 0.0-1.0
Constrainedness
Constrainedness
Constrainedness
Pur
Complehmees Posce
Parfomance
0.6
0.4
0.042
0.2-0.4
04408
0.8-8.8
0.8-10
0.002 0.204 04-08
06-08
0.8-1.
0.0-0.2 0.2-04 04-06 06688 0.8-1.0
Constrainedness
Constranedness
Constrainedness
Figure 3: GPT-4 performance KITAB for queries across various constrainedness bins. Similar to Figure 2 compare (I-CONTEX(((eft)) SELF-CON (midex and WITH-CONTEXT(ight with irrelevant informa- tion and unsatisfaction rates the top; and satisfaction, completeness, and all correctness rates the bottom.
for most constraint types higher constrainedness. is related lower model performance (consistent with findings by Yuksekgonul et al. (203)), for particular constraints like ends with and city- the opposite is true. In addition, for entity constraints (human and city names) the forms (entity exists or does not exist in the title) are placed in two different ends of constrainedness. This can also be seen in Table 2 and Figure 6 where negation queries are placed in the lower end of the graph. Thus, when summed up, the overall dynamics constrainedness on performance. While we do not have a full explanation to why the ends-with and city- -tty-name constraints behave differently, the variation highlights the importance of controlled, large-scale datasets such as KITAB in measuring emergent behavior of LLMs at scale.
resemble almost bimodal effect of
Multiple constraints. 4igure4sshoss shows model performance queries with only author constraint vs. with additional one and two book constraints. Unsurprisingly, model performance consistently decreases for more complex and more constrained queries with two book constraints. As naïve
8

---

Published as a conference paper at ICLR 2024
GPT-4
GPT-3.5
AUTHOR CITHHOR-CONSTRANNTONN
NUTHOR-CONSTRAINT
0.8
SNE-BBOK--ONSTTAAN
0.8
ONE-BOOK-CONSTRAIN
TWO-BOOK-COO CONSSCONNTTA
TWO-BOOK- CONTTCCNNTTANNTT
0.6
0.6
0.4
0.4
0.2
0.2
Inseevant (Port--prr)
Satisfied (Part.FPaa)
Completsness (Port==Pcomp)
Ineeavant (Part=-po)
Satisfled (Part.=Psx))
Completeness (Port.=Pcomp)
Figure 4: Model performance on queries with only an author constraint vs. plus one book constraint, and plus two book constraints. Results for queries with book constraints are based of NO-CONTEXT (Template 2a).
baseline, we also compare with performance on queries with only the author constraint. While completeness and constraint satisfaction decrease in the direction of no book constraints to two book constraints, irrelevant information follows different dynamiis. In particular, models seem to fabricate significantly more irrelevant information when they are asked to list all books from an author. In fact, if one considers the whole set of books by all authors available in the training data as the domain for the ALL-BOOKS queries, the constrainedness of such a query when no other constraints are present quite high. This may demonstrate that estimating the domain cardinality for computing constrainedness is not straightforward and that some leading constraints (i.e., the author in our case) may serve as conditioning handlebars to the domain size used by the model. The finding however warrants future experimentation for studying if and how such conditioning happens. Further detailed results on model performance by constraint type for queries with two book constraints can be found in Tables and for GPT4 and 3.5.
better understand how irrelevant information propagates at dif- ferent stages of our queries, we study the SELF-CONTEXT condition in further detail. We observe that irrelevance for the first part of the chain-of-thought process when the model outputs all books from the author is notably high, 0.42 for GPT4 and 0.47 for GPT3.5. Even though after applying constraints, irrelevance decreases to 0.33 and 0.44, this still remains higher than other conditions as the model is not able to recover from the initial fabricated titles. Qualitatively, observe that sometimes models collect irrelevant books in condition SELF-CONTEXT such that they can satisfy the constraint later on (see Examples and 4 in Appendix FF).
Further decoupling analysis.
Finally, we look at model performance in satisfying constraints for SINGLE-ITEM lists of books. Here, measure the accuracy of the model detecting whether a constraint is satisfied for one title using the same prompt as for WITHICCNTEXT. Model accuracy for SINGLE-ITEM is shown in the first columns of Tables and When comparing these metrics with satisfaction rates from we see that constraint types have two very different behaviors consistent across both models. Constraints like starts-with, ends-with, and publication year are easier to check for individual titles than for lists. Instead, entity constraints become easier for lists of book titles, which resonates with the fact that entity recognition considered a core ability of L.LSs on longer tex
CONCLUSION
We presented KITAB, dataset and dynamic data collection approach for evaluating abilities of large language models to filter information using constraints. The dataset provides convenient flex- ibility for controlling the type and complexity of constraints in queries that expect longer lists of outputs, beyond simple facts. An in-depth analysis of GPT4 and GPT3.5, two state-of-the-art mod- els deployed in the real-world as part of conversational search systems, showed that despite exciting emerging abilities of such models in finding information, important limitations remain when models fabricate irrelevant information when only parametric knowledge is used or when they fail sat- isfy specified constraints even when provided with the most complete and relevant context to filter upon. We hope that the dataset and methodology paves an avenue for future rigorous and large-scale evaluations of emergent abilities in information retrieval problems.
We exclude the word-count constraint from this discussion since our evaluation WITH-CONTEXT tolerates answers that one word longer or shorter than the given constraint.

---

Published as a conference paper at ICLR 2024
REFERENCES
Ricardo Batea-Yates, Berthier Ribeiro-Neto, et al. Modern information retrieval. ACM press New York, 1999.
Emily M Bender, Timnit Gebru, Angelina McMillan Majorr and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In FAceT, pp. 610-623, 2021.
Stella Biderman, USVSN Sai Prashanth, Lintang Sutawika, Hailey Schoelkopf, Quentin Anthony, Shivanshu Purohit, and Edward Raf. Emergent and predictable memorization in large language models. Xiviv preprint arXiv:2304.11150 2023.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportu- nities and risks of foundation models. arXiv preprint arXiv:2 2021.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint 22Xiv:2002.0646.. 2022.
Yupeng Chang, Xu Wang. Jindong Wang. Yuan Wu, Kaijie Zhu, Hao Chen, Linyi Yang, Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, et al. A survey on evaluation of large language models. arXiv preprint arXiv:2307.03109 2023.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.088 023111, 2022.
Yung-Sung Chuang, Yujia Xie, Hongyin Luo, Yoon Kim, James Glass, and Pengcheng He. Dola: Decoding by contrasting layers improves factuality in large language models. arXiv preprint 3XXiv2339.03883 2023.
Xin Luna Dong and Theodoros Rekatsinas. Data integration and machine learning: A natural syn- ergy. In SIGMOD, pp. 1645-1650, 2018.
Yanai Elazar, Nora Kassner, Shauli Ravfogel, Abhilasha Ravichander, Eduard Hovy, Hinrich Schütze, and Yoav Goldberg. Measuring and improving consistency in pretrained language mod- els. Transactions of the Association for Computational Linguistics, 9:1012-100 1021,, 2021.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.0002 2020.
Ian P Gent, Ewan MacIntyre, Patrick Prosser, Toby Walsh, et al. The constrainedness of search. In AAAI/IAA,, Vol. 1, pp. 246-252, 1996.
Lise Getoor, Benjamin Taskar, and Daphne Koller. Selectivity estimation using probabilistic models.
In SIGMOD, 2001.
Mor Geva, Jasmijn Bastings, Katja Filippova, and Amir Globerson. Dissecting recall of factual associations in rugr-segressive language models. arXiv preprint arXiv:2304. 14767, 2023.
Rasmus Hahn, Christian Bizer, Christopher Sahnwaldt, Christian Herta, Scott Robinson, Michaela Bürgle, Holger Düwiger, and Ulrich Scheel. Faceted wikipedia search. In Business Information Systems: 13th International Conference, BIS 2010, Berlin, Germany, May 3-5, 2010. Proceedings 13. pp. 1-11. Springer, 2010.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazcika, Dawn Song, and Jacob Steinhardt. Mcasuring massive multitask language understanding. arXiv preprint arXiv:2009.03300. 2020.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453-466, 2019.
10

---

Published as a conference paper at ICLR 2024
Patrick Lewis, Ethan Perez. Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih. Tim Rocktäschel, et al. eetrieval-augment genera- tion for wwwlledde-intessiv nlp tasks. Advances in Neural Information Processing Systems, 33: 9459-9474, 2020.
Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models. arXiv preprini urXiv:2211.091 10, 2022.
Stephanie Lin, Jacob Hilton, and Owain Evans. Truthfulqa: Measuring how models mimic human falsehoods. arXiv preprint arXiv:2/09.07958, 2021.
Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das. Hannaneh Hajishirzi, and Daniel Khashabi. When not to trust language models: Investigating effectiveness and limitations of parametric and non-parametric memories. arXiv preprint arXiv:2212. 105/1, 2022.
Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov. Locating and editing factual associations in gpt. Advances in Neural Information Processing Systems, 35:17359-17372 2022.
Pedro Meseguer. Constraint satisfaction problems: An overview. Al communicationss 1989.
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:2 12.09332, 2021.
Harsha Nori, Nicholas King, Scott Mayer McKinney, Dean Carignan, and Eric Horvitz. Capabilities of gpt-4 medical challenge problems. arXiv preprint arXiv:2303. /3375, 2023.
OpenAL. Gpt-4 technical report. ArXiv, 2023.
Opendatasoft. Geonames, 2023. URL http://pubblcc..gnnnttttttt wttp://ott...oooe/pppeereee. dataset/geonamer all cities with -opp-aaapppattioo-o--- 1000
Pranav Rajpurkar, Robin Jia, and Percy Liang. Know what you don't know: Unanswerable questions for squad. arXiv preprint arXiv:1806. 1XXx:18806.0322,,, 2018.
Milad Shokouhi. Detecting seasonal queries by time-series analysis. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, pp. 1171-1172, 2011.
Kai Sun, Yifan Ethan Xu, Hanwen Zha, Yue Liu, and Xin Luna Dong. Head-to-tail: How knowl- edgeable are large language models (Im)? aka will Ilms replace knowledge graphs? arXiv preprint ar Xrxiv22308. 10168, 2023a.
Weiwei Sun, Lingyong Yan, Xinyu Ma, Pengjic Ren, Dawei Yin, and Zhaochun Ren. Is chat- gpt good at search? investigating large language models as re-ranking agent. arXiv preprint 1oXiv:230400952 2023b.
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. Beir: A heterogenous benchmark for zero-shot evaluation information retrieval models. arXiv preprint arXiv:2/04.088633 2021.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov. Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.09288 2023.
Daniel Tunkelang. Faceted search, volume 5. Morgan & Claypool Publishers, 2009.
Karthik Valmeckam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large lan- guage models still can't plan (a benchmark for 1lms on planning and reasoning about change). arXiv preprint 22X6v:2206./044 2022.
Mert Yuksekgonul, Varun Chandrasekaran, Erik Jones, Suriya Gunasekar, Ranjita Naik. Hamid Palangi, Ece Kamar, and Besmira Nushi. Attention satisfies: A constraint-satisfactio lens on factual errors of language models. arXiv preprint, 2023.

---

Published as a conference paper at ICLR 2024
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can ma- chine really finish your sentence? arXiv preprint arXiv:195.007830, 2019.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, al. Siren's song the ai ocean: A survey on hallucination in large language models. arXiv preprint urXiv:2309.01219 2023.
Xin Zheng, Hongyu Lin, Xianpei Han, and Le Sun. Toward unified controllable text generation via regular expression instruction. arXiv preprint arXiv:2309. /0447, 2023.
Wangchunshu Zhou, Yuchen Eleanor Jiang, Ethan Wilcox, Ryan Cotterell, and Mrinmaya Sachan. Controlled text generation with natural language instructions. ICML,, 2023.
12

---

Published as a conference paper at ICLR 2024
A
KITAB STATISTICS
One book constraint
Two book constraints
5k
starls-with
number of queries
ends-with
number of queries
4k
publishingyyerr
2k
3k
dly-name
no-oit-name
2k
human-naam
no-human--tame
1k
1
0
20
40
60
80
100
20
40
60
80
100
Popularity
Popularity
Figure 5: Distribution of queries author popularity measured by the number of sitelinks Wikidata, for queries with a single book constraint (left) and two book constraints (right).
One book constraint
Two book constraints
starts-witth
number of queries
2k
number of queries
word-count
publshing-year city-name
2k
no-cityiname
1k
no human-name
1k
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Constrainedness%
Constrainedness%
Figure 6: Distribution of queries across author constraincdness measured by the complement of the ratio between the number of books that satisfy the book constraints and the total number of books from the author. Distribution is shown for queries with a single book constraint (left) and two book constraints (right). Note that most of the distribution in the lower range of constrainedness is dominated by constraints that require no human name city name in the title, which naturally easier satisfy.
B EVALUATION ON QUERIES WITH ONE AND TWO BOOK CONSTRAINTS
Relevant information
Single Item
Irrelevant information |
(Books from the author) Satisfied
Completeness f
All Correct f
Unsatisfied
|
starts-with
0.83
0.33
00.47
0.01
0.36
0.35
0.80
0.32
0.18
0.19
0.13
0.18
0.49
0.04
0.09
0.22
ends-with
0.59
0.18
0.42
0.00
0.15
0.07
0.16
0.67
0.51
0.83
0.12
0.07
0.34
0.03
0.00
0.02
word-count
0.55
0.17
0.43
0.00
0.41
0.22
0.43
0.42
0.34
0.57
0.06
0.04
0.19
0.00
0.00
0.02
human
0.70
0.30
0.46
0.00
0.24
0.28
0.67
0.46
0.26
0.33
0.18
0.14
0.50
0.04
0.01
0.12
no-human
0.60
0.26
0.48
0.00
0.58
0.42
0.86
0.16
0.09
0.14
0.12
0.24
0.71
0.00
0.00
0.04
city
0.56
0.21
0.52
0.00
0.38
0.12
0.58
0.41
0.37
0.42
0.28
0.09
0.38
0.19
0.03
0.29
no-city
0.50
0.23
0.48
0.02
0.72
0.48
0.91
0.06
0.03
0.07
0.26
0.79
0.00
0.00
0.13
pub-year
0.92
0.17
0.41
0.00
0.52
0.23
0.84
0.32
0.35
0.15
0.22
0.22
0.54
0.12
0.03
0.23
Summary
0.69
0.20
0.44
0.00
0.44
0.26
0.68
0.36
0.30
0.32
0.16
0.16
0.47
0.07
0.02
0.15
Table 4: GPT3.5 performance on KITAB for NO-CONTEXT constraint types for queries with book constraint.
SELF-CONTEXT
CONTEXT across different
13

---

Published as a conference paper at ICLR 2024
Relevant information (Books from the author) Satisfied
Irrelevant information
Completeness 1 All Correct f
Unsatisfied
GPT4
0.31
0.00
0.34 0.54
0.35
0.46
0.13
0.52
0.06
0.19
GPT3.5
0.35 0.01
0.15 0.40
0.50
0.60
0.12 0.36
0.00 0.07
Table 5: Aggregated model performance KITAB for NO-CONTEXI constraints.
CONTEXT for queries with two book
Relevant information
Irrelevant information +
(Books from the author) Satisfied
Completeness f
All Correct t
Unsatisfied +
starts-with
0.37 0.00
0.36
0.58
0.27
0.41
0.17
0.63
0.11
0.29
ends-with
0.28
0.00
0.22 0.39
0.50
0.61
0.09
0.46
0.05 0.15
word-count
0.28
0.00
0.41
0.57
0.30
0.43
0.08 0.42
0.04 0.16
human
0.32 0.00
0.29
0.52
0.40
0.48
0.10 0.46
0.05 0.17
no-human
0.26 0.00
0.41 0.62
0.33
0.38
0.11 0.51
0.03 0.16
city
0.57
0.00
0.11 0.42
0.32
0.58
0.02 0.12
0.01 0.09
no-city
0.31
0,00
0,40
0.61
0.29
0.38
0.15 0.58
0.03 0.16
pub-year
0.28
0.00
0.32 0.54
0.40
0.46
0.14
0.58
0.06 0.16
Summary
0.31
0.00
0,34
0.54
0.35
0.46
0.12
0.52
0.06 0.19
Table 6: GPT4 performance KITAB for NO-CONTEXT CONTEXT across different constraint types for queries with two book constraints. The type needs to appear at least once in the query to be grouped under a constraint type. Satisfaction rate is reported jointly for both constraints (i.e., both need to be satisfied).
Relevant information
Irrelevant information +
(Books from the author) Satisfied
Completeness f
All Correct
Unsatisfied |
starts-with
0.42
0.01
0.13 0.49
0.44
0.50
0.13
0.43
0.00 0.12
ends-with
0.29
0.00
0.07
0.22
0.64
0.78
0.08
0.32
0.00 0.05
word-count
0.35
0.01
0.18
0.39
0.47
0.60
0.13 0.28
0.00 0.05
human
0.31
0.00
0.10 0.32
0.59
0.68
0.10 0.35
0.00 0.03
no-human
0.29
0.00
0,25
0.45
0.46
0.55
0.11 0.38
0.00 0.05
city
0.44
0.01
0.05
0.20
0.51
0.79
0.07 0.21
0.00 0.02
no-city
0.31
0.00
0.25
0.48
0.44
0.51
0.10 0.44
0.00 0.05
pub-year
0.38
0.01
0.15
0.45
0.48
0.55
0.16
0.37
0.00 0.07
Summary
0.35
0.01
0.15
0.40
0.50
0.60
0.12
0.36
0.00 0.07
Table 7: GPT3.5 performance on KITAB for NO-CONTEXT CONTEXT across different constraint types for queries with two book constraints. The type needs to appear at least once in the query to be grouped under a constraint type. Satisfaction rate is reported jointly for both constraints (i.e., both need to be satisfied).
C FURTHER DETAILS ON KITAB DATA COLLECTION
C.I DATA CLEANING
Here, we detail all steps involved in the data cleaning of KITAB. These steps are also available in our dynamic data collection for future users of KITAB, who may reproduce the same workflow for other author samples.
Book filtering. We only retrieve books that are tagged be in English by Open Library and those that have no assigned language, since all our prompts are in English and require the model to return only English titles. We keep the books that have no assigned language to improve book collection completeness. However, we still check through the Azure Cognitive Services API whether these titles are in English before adding them to the list. Next, we also remove books that appear to have more than two authors since many of such books will not necessarily appear as books from particular author. In most cases, these are collections of works amongst many authors (e.g., "The Best Short Stories 2022: The O. Henry Prize Winners"). Finally, also found a list of titles in Open Library that were part of an author's collection but not written by the author. To mitigate this, cross checked with Wikidata for the same title and made sure that the author Wikidata
14

---

Published as a conference paper at ICLR 2024
matches the one on OpenLibrary. This step is commonly used during data integration for cleaning purposes (Dong & Rekatsimas 2018) and significantly improved the data quality overall.
Deduplication. To deduplicate potentially redundant book titles, we first lower case and strip all punctuation from title strings and then cluster the books retrieved via Open Library by using i) fuzzy matching with 80% threshold, and ii) subset checks for cases when the book title may appear in a longer or abbreviated form (e.g.. "Gödel, Escher, Bach" vs. "Gödel, Escher, Bach: An Eternal Golden Braid"). We specifically remove the first word of title if the title starts with "The" or "A/An" for deduplication purposes, and apply the same strategy during model evaluation itself so that we do not penalize the model if it did or did not miss a title simply because of these minor details. During deduplication, we keep as publishing year the minimum value of publishing years across all titles in the cluster. Note that the deduplication process also affects the list of ground truth books in KITAB, B, as the same book may appear multiple times on Open Library. To alleviate this, we keep track of redundant titles of the same book during the book collection stage and then employ the redundant titles as well while computing query constrainedness and completeness. For instance, in the example above, both variants of the book title are present in the Open Library ground truth (e.g.. "Gödel, Escher, Bach" vs. "Gödel, Escher, Bach: An Eternal Golden Braid"), the book itself would be merged into one and marked as satisfying both constraints: "title ends with the letter h" and "title ends with the letter d".
Manual checks for quality. The manual checks included looking at two samples of 200 queries for each model and their respective output and inspecting titles that the model had mentioned but we had marked them as irrelevant information (i.e., not from the author). For these titles, we searched on the Web to see if there exists book from that author with the same title. The process identified that 5% and 6% of the queries in the GPT4 and GPT3.5 samples respectively had at least one title in the model output that indeed belongs to the author according to web search but that title is not present on OpenLibrary. Note that the impact of this variance on irrelevant information rates is in fact much lower than 5% because it is measured across queries and not individual books, as an upper bound estimate.
C.2 SAMPLING CONSTRAINTS AND QUERIES
Further, we describe the construction and selection of KITAB's constraint satisfaction queries and ground truth.
Queries with one book constraint. For each author, we generate constraints by associating every title with starting and ending letters, word count, a 5-year publication year range, and whether the title has human or city names. From this large accumulation, we then randomly sample 15% of the constraints for title beginnings or endings and 50% for title word count. We also append unstaistiable constraints of each type, for instance, we randomly select letters that no book title in our set starts with. The set of unsatisfiable queries constitutes 7.99% of the queries. The final set of single book constraints is 8239 queries.
Queries with two book constraints. For all double-constraint queries, both constraints are individ- ually satisfiable and generated by combining our single constraint data. Only 0.76% of the queries are jointly unsatisfiable across both constraints. For a variation in difficulty, we isolate more easily satisfiable constraints that combine title starts with and published in year-range that map to more than one book and sample 25% the latter; of the remaining double constraints, we sample 5% that map to single book and 10% that map more than 2 books. The final set has 4750 queries.
SINGLE-ITEM queries. From KITAB's 's one book constraint data, we randomly select 200 queries, sampling 50 queries each for title starts and ends with constraints, 30 each for published within range and word count in title, and 20 each for the presence of a human or city name in the title. For each query, we randomly select single book item satisifying the constraint from the ground truth and provide it as context. Additionally, for every satisfiable constraint query, we also sample book by the author that is not present in the ground truth a juxtapose context, resulting in a total of 400 single item queries.
15

---

Published as a conference paper at ICLR 2024
D PROMPTING TEMPLATES
(TEMPLATE ALL-BOOKS]; List all books from the author. Maximum token length = 1000
List of all books written by (Sauthor} (born in (Sbirth-yearh) All book
author titles need to be in English. Always finish your response with the following format, do not add additicnal text comments:
Output:
1. Title: <title>
2. Title: <title>
N. Title: <title>
(TEMPLATE 2A NO-CONTEXT]: List all books from the author that satisfy other constraints, no context.
Maximum token length = 400
List of all books written by [Sauthor} (born in (sbirth.yearh) satisfying
Pautaor constraint
all the following criteria. Think step-by-step. Give a 1-2 sentence reason for why the books satisfy the criteria. Criteria: (Sconstraints) Remember that every
Al1 book titles need to be in Rnglish.
book condtracnts
book in the output list needs satisfy all the criteria. Always finish your response with the following format. Do not add any additional text or comments after the output list.
Output:
1. Reason:
<reasen>, Title: <title>
2. Reason:
<reason>. Title: <title>
N. Reason:
<reason>. Title: <title>
[TEMPLATE 2B WITH-CONTEXT]; List books from the author that satisfy other constraints, with context.
Maximum token length = 1000 (200 for the SINGLE-ITEM condition)
The following is a list of books by (Sauthor) (born in (sbirth year))
Sauthor conscraint
with publication dates parenthesis. List: (Sall_books)
Find all books in this list that satisfy all the following criteria. Think step- Give 1-2 sentence reason for why the books satisfy the criteria. Criteria: (Sconstraints) Remember that every
book in the output list needs to satisfy all the criteria. Always finish your response with the following format. Do not add any additional text or comments after the output list. Output:
1. Reason:
<reason>. Title: <title>
2. Reason:
<reason>. Title: <title>
N. Reason:
<reason>. Title: <title>
16

---

Published as a conference paper at ICLR 2024
(TEMPLTE 3 SELF-CONTEXT]; List all books from the author that satisty one other constraint, self-retrieve context.
Maximum token length = 3000
List of all books written by [Sauthor] (born in (Sbirth.year)) satisfying
all the following criteria. All book titles need to be in English. Criteria: (Sconstraints) First, retrieve all books by {Sauthor) (born
book in (sbirthyyear) and list them in the "A11 Books" list. Then, select the subset of books that satisfy Constraint 1 and list them under the "Final Output" list. Think step-py-step. Give 1-2 sentence reason for why the books satisfy the criteria. Remenber that every book in the #inal output 1ist needs to satisty all the criteria. Always finish your response with the following format. Do net add any additiona text or comments after the output list.
All Books:
1. Title: <title>
2. Title: <title>
N. Title: <title>
Final Output:
1. Reason: <reason>, Title: <title>
2. Reason: <reasen>.
Title: <title>
N. Reason:
<reascn>.
Title: <title>
[TEMPLATE 4 NAME-CHECK]: Find all books that contain human name in the title.
The following a list of books. List: (boks
Find all books that centain a human name in the title. Always finish
your response with the following format. Do not add any additional text or comments after the output list.
Output:
1. Reason:
<reason>,
Title: <title>
2. Reason:
<reasen>,
Title: <title>
N. Resson:
<reason>.
Title: <title>
17

---

Published as a conference paper at ICLR 2024
E ADDITIONAL RESULTS ON PERFORMANCE RELATION TO POPULARITY
AND CONSTRAINEDNESS
E. POPULARITY
GPT-4 NO-CONTEXT
GPT-4 SELF-CONTEXT
GPT-, WITH-CONTEXT
1,0
Iralevant Par
0.8
Unsatisfed
0.8
0.4
0.0
0-20
20-40
40-80
60-80
80-100
0-20
20-40
40-60
60-80
80-100
0-20
20-40
40-60
60-80
80-100
Author popularity
Author popularity
Author popularity
Par
0.8
Complitenass
Performance
correct
0.8
0.4
0.0
Author popularily
Author popularily
Author popularily
(a) GPT-4 performance KITAB comparing NO-CONTEXTŪeeI), SELF-CONTEXT and WITH- CONTEXT(right) queries across various popularity bins. show trends irrelevant information, un- satisfaction rate in top plot; and for satisfaction, completion and correctness rates in the bottom plot.
GPT-355 NO-CONTEXT
GPT-3.5, SELF-CONTEXT
GPT-35 WITHCONTEXT
1.0
0.8
Unselliseed Pasar
Performance
0.8
0.4
0.2
60-80 Author popularity
Author popularity
Author popularity
1.0
Saltsfted Pur
0.8
Completeness Peeep
Perforaanc
correct
0.8
0.4
0.2
0.0
0-20
20-40
40-80
60-90
80-100
0.20
20-40
40-60
60-80
80-100
0-20
20-40
40-60
60-80
80-100
Author popularity
Author popularily
Author popularity
(b) GPT-3.5 performance on KITAB comparing NO-CONTEXT((ef), SFLFFCONTEXT((iddll and WITH- (ONTEXT(right) queries across various popularity bins. We show trends for irrelevant information, and un- satisfaction top plot; and for satisfaction, completion and correctness rates in the bottom plot.
Figure 7: GPT4 and GPT-3.5 performance vs. popularity.
18

---

Published as a conference paper at ICLR 2024
E.2 CONSTRAINEDNESS
GPT-4 NO-CONTEXT
GPT-4 SELF-CONTEXT
GPT-, WITH-CONTEXT
1,0
Irelevant
0.8
0.6
0.4
0.2
0.0
0.0.22
0.2.0.4
0.4.6.6
0.6-3.8
0.8-1.0
0.0.0.2
0.2.4.4
0.40.66
0.6-0.8
0.8-1.0
0.0.2.2
0204
0.065
0.6.0.8
0.8-1.3
Constrainedness
Constrainedness
Constrainedness
Par
0.8
Complitenasé
Performance
correct
0.8
0.4
0.0
0.0-0.2
0.2-0.
0,4-0.6
0.6-2.8
0.8-1.0
0.0-0.2
0.2-04 0.4-066 0.8-0.8
0.8-1.0
0.0-0.2
024.44 0.608 0.6-0.8 0.8-1.0
Constrainedness
Constrainedness
Constrainedness
(a) GPT-4 performance KITAB comparing NO-CONTEXT(ee1), SELF-CONTEXT(middle) and WITH- (oigEXT(right) queries across various constrainedness bins. We show trends irrelevant information, and unsatisfaction rate in top plot; and for satisfaction, completion and correctness rates in the bottom plot.
GPT-355, NO-CONTEXT
GPT-355, SELF-CONTEXT
GPT-35 WITH-CONTETT
1,0
0.8
Lnseeliafed Pusor
Performance
0.8
0.4
0.2
Constrainedness
Constrainedness
Constrainedness
1.0
Sallsfied Pat
0.8
Completeness Peoep
Performance
correct
0.8
0.4
0.2
0.0
0.0-0.2
0.404
0.406 066-888
0.8-1.0
0.0-0.2
0.2-44
04-0.8 0.8-0.8 0.8-1.0
00--2 02-44 0406 0.60888 08-1.0
Constrainedness
Constrainedness
Constrainedness
(b) GPT-3.5 performance on KITAB comparing NO-CONTEXT((et), SELF-CONTEXT(middle and WITH- CONTEXT(right) queries across various constrainedness bins. We show trends for irrelevant information, and unsatisfaction rate top plot: and for satisfaction, completion and correctness in the bottom plot.
Figure 8: GPT-4 and GPT-3.5 performance vs, constrainedness.
19

---

Published as a conference paper at ICLR 2024
E.3 BREAKDOWN OF GPT-4 PERFORMANCE BY CONSTRAINT TYPE
GPT-4,
Inolovant Par
Peformance
Unawtadied Pasce
0.5
0.0
GPT-4 NO-CONTEXT (endsrath))
6PT-4, SELF-COMTEXT (endsw(th)
GPT-4, WITH-CCNNEXX (endewwth)
Ie
Peformance
Unaelaaiee
0.0
1.0
GPT-1 NO-CONTEXT (word-count)
GPT- SELF-CONTEXT (wonk-ouur))
GPT-4, WITH--CONTXTT (werd-avuni)
Inelovant
Pelormance
Unsatiafied
1.0
GPT-4, NO-CONTEXT (pbblshingyywr)
GPT-4, A-COMMETT (jublshinggjmm))
GPT-4, WITH-COOTEXT (publshinggyeer)
Inolevint.p..
Peformance
Unsatisfeed Puruet
0.5
GPT-4, CONTEOT
GPT4, SELF-CONTEXT
GPT-4, WITH-COTEETT [human-name)
Peforance
Inrelvant.pp.
Unsodaafied Purae
0.5
(no-humenvreme)
(ne-human-name)
(no-humannsmme)
Inclovant
Peformnnc
Unseliifeed Puss
0.5
0.0
1.0
GPT-4, NO-CONTEXT (olyname))
GPT-4, SELF-CONTEXT (clyname)
GPT-4 WITH-CONTEXT (clyname)
Imelovant
Peformacce
Unsatiifeed
0.0
1.0
GPT4 NO-CONTEXT (no-cilyneme)
GPT-4, FEL--CONT (no-cly-neme)
GPT-4 WITH-CONTEXT (re-ciename)
Inelevant
Peformance
Unsatisfed
h
0.0
0.0.0.2
020.4
0.0.6
0.8.0.8
0.8-1.
0002
0.244
040.8
0.6.0.8
0.8-1.0
0.0.22
0.20444
0.4.86
0.6..88
0.8-100
Constrainedness
Constrainedness
Constrainedness
Figure 9: Constrainedness irrelevance and unsatisfaction for GPT-4 across constraint types.
20

---

Published as a conference paper at ICLR 2024
(atartswwtt))
Satadiel Aur
Peformance
Completoness
0.5
0.0
1.0
GPT NO.CONTEXT (ondswwft))
GPT-4, BELF-CONTEXT (endsw
GP744, CONTEC wonds
Satisfied Aur
Peformance
Completenwss
correct
0.0
1.0
CPT-4 NO-CONTEXT (word-count)
GPT-4 SELF-CONTEXT (wor--count)
GPT4, WITH-COOTEXT Iwerd-oount)
Satisfied Pat
Peformance
cornect
0.0
GPT-4 NO-CONTEXT (ublishingyear)
GPT-4 SELF-CONTEXT (uuttshg--ysa))
GPT-4 WITH-CONTEXT publihingyyyann
Satledee
Pefomancc
Complitanesa Rooe
plewet
0.5
NO-CONTEXT
GPT-4, SELF-CONTEXT
GPT-4, WITH.ONTEET
Pur
Peformance
Commlotoness Pomp
surnect
0.5
(no-tumen-nam))
(nc hame--amnmm
(nohhman--amm)
Satirfed Aur
Peformance
Completoness
0.5
0.0
GPT-4, NO-GONTEXT (obyname)
GPT-4, COL-CCONTEXT (oly-name)
GPT-4, WITHHCONTEXT (abensme)
SalsSfidd Put
Feformance
Completeness
0.0
1.0
GPT-4, NO-CONTEXT [no-cilymteme)
GPT-4, SELF-CONTEXT (no-cly-mmme
GPT-4 WITH-COWIIXT (re-cilenam))
Satisted Pat
Pefermance
Priee
Al connect
0.0-0.2
0.2.0.4
0.4066
0.6-0.8
0.8-1.0
0.0.0.2
0.20..4
0.4.66
0.6.0.8
0.8-1.0
0.0.0.2
0.204
04406
0.0.888
0.8-00
Constrainedness
Constrainedness
Constrainedness
Figure 10: Constrainedness satisfaction, completeness and correctness for GPT-4 constraint types.
21

---

Published as a conference paper at ICLR 2024
F EXAMPLES
[EXAMPLE 1J: High unsatisfaction rate with NO-CONTENT.
Author: Michael Scott
Constraint: Book title contains only 4 words.
KITAB ground truth: "A Celtic odyssey', 'Celtic wisdom for Business', Green and golden tales', 'Irish animal tales.', 'Irish folk and fairy tales', "Irish ghosts and hauntings', 'Irish hero tales', 'Judith and spider', "Magical Irish folk tales', 'The Childrenof Lir', 'The Culai heritage', "The book of Celtic wisdom', 'The last ofthe fianna', 'The quest ofthe sons', The river gods', 'The seven treasures', 'The thirteen hallows]"
KITAB books" "['A Celtic odyssey (1985)', 'Billy the Kid and the vampyres of Vegas (2011)', 'Celtic Wisdom for Business (2001)', "Earthlord (1992)', "Firelord (1994)', 'Gemini game (1993)', 'Green and golden tales (1988)', 'Trish Fairytales (Green and Golden Tales) (1989)', 'Irish animal tales. (1989)', 'Irish folk and fairy tales (1983)', 'Irish ghosts and hauntings (1994)', "Irish hero tales (1989)', 'Judith and spicer (1992)', 'Lottery (1993)', 'Nagical Irish folk tales (1995)', 'Mirror image (2016)', 'October meen (1992)', 'Reflection. (1992)', 'Tales from the land of Erin (1985)', 'The Childrenof Lir (1986)', 'The Culai heritage (2001)', 'The Magician (2008)', 'The alchemyst (2007)', 'The book of Celtic wisdom (2002)', "The enchantress (2012)', 'The last ofthe fianna (1987)', "The necromancer (2010)', 'The quest ofthe sons (1988)', 'The river gods (1991)', "The seven treasures (1992)', 'The thirteen hallows (2011)', "The warlock (2011)', 'Windlord (1991)'
GPT4 books: "['alchemyst the secrets of the immortal nicholas flamel', 'magician the secrets of the immortal nichelas flamel', 'necromancer the secrets of the immortal ni nicholas flamel', 'warlock the secreta of the immortal nicholas flamel', renchantress the secrets of the immortal ni chohas flamel']'
Observation: Although the model managed to generate books that map to KITAB's author book list, no titles satisfy the word-count constraint.
[EXAMPLE 2J: Remaining high unsatisfaction rate with CONTEXT.
Author: Gabriel Gareía Márquez
Constraint: Book title ends with the letter
KITAB ground truth: " Love in the time of cholera', 'The fragrance of guava' )"
KITAB all books (context): '''100 Years of Solitude (1967)', "Armando Morales (2004) Auutumn of the Patriarch (2008)', 'Chronicle of Death Foretold (1981)', 'Clandestine in Chile (1985)', 'Collected Novellas (1990)', 'Conversations with Gapriel Garcia Karquez (2005)', 'For the sake of country within reach of the children (1996)', 'Gabriel Garcia Marquez (2015)', "Granta 31 (1990),, 'Harvard Diss Romance Set (1942)', "I'm Not Here to Give Speech (2014)", 'In evil hour (1962)', 'Innocent Brendira and Other Stories (1979)', 'Leaf storm (1955) 'Living to tell the tale (2002)', 'Lvve in the time of cholera (1985)', 'Memories of My Melancholy Whores (2004)', "News of a kidnapping (1996)', 'No One Writes the Colonel (1961)', 'Of love and other demons (1994) 'One hundred years of solitude (1967)', 'Scandal of the Century (2020) 'Strange Pilgrims (1992)', 'The Handsomest Drowned Man in the World (1968)', The Short story (1987)', 'The fragrance of guava (1982)', "The general in his labyrinth (1989)', ' 'The story of shipwrecked sailor (1970)', "Three Novellas (1991)', 'Tomas Sanchez ()
GPT4 books: v''in evil hour', 'of love and other demons']
Observation: Although the model successfully follows the provided context and all books are in fact hy the author, it fails at extracting books satisfying the constraint.
22

---

Published as a conference paper at ICLR 2024
[EXAMPLE 3]: SELF-CONTEXT leading to higher information irrelevance.
Author:
Russell Humke Fitzgibbon
Constraint: Book title starts with the letter v.
KITAB all books for the author: * directory of Latin American politica parties (1970) 'Assessing democracy in Latin America (1998)', 'Brazil: chronology and fact book, 1488-1973 (1974)', 'Cuba and the United States, 1900-1935 (1935)', 'Global politics (1944)', "Latin America (1946)', "The constitutions of the Americas, as of January 1, 1948.
(1948)', 'Uruguay (1954)', rvisual outline of Latin American history (1938)
GPT4 self-contxx:: "I'vaticar and the kremlin', 'vatican in world politics', 'catholic church and the authoritarian regime in austria', 'catholic church and the totalitarian regime in italy', 'catholic charch and the dictatorship in portugal', catholic church and the fascist regine in spain'
Observation: None of the books in the model output are from the author. The model starts by generating two irrelevant books that do satisfy the constraint but are not from the author. Given that context, it then continues autoregressively generate more of the same books similar topics (religion) hut that are still irrelevant and also do not satisfy the constraint anymore.
[EAAPPL 4J: SELF-CONTEXT leading to higher information irrelevance.
Author:
Johnston McCulley
Constraint: Book contains human name in its title.
KITAB all books for the author: < "('Alias the thunderbelt (1927)' Avenging
Twins Collect (2007)', 'Black Grandee (2019)', 'Brand of silence (2020)', 'Broacway Bab (1919)', BBullet law (1960)', 'Canyon of peril
Jehu (2008)', 'Demon (2007)', "Devil's Doubloons (2019)", 'Don Renegade (2017)', Ghost Phone (2014)', 'Iron Horse Town. (1952)', "Johnston McCulley's Zorro (2000)*. "King of Chaos and Other Adventures (2019)', 'Land of Lost Hope (2016)', 'Man Who Changed Rooms (2008)', 'Searlet Scourge (2007)', 'slave of Mystery and Other Tales of Suspense from the Pulps (2006)', South of the pass (1944)', 'Spider strain (2017)', 'Tales of Thubway Tham (,005)', 'Texas showdown (1953)', "A white man's chance (1927)", The Black Star (1921)', "The Cougar kid (1945)', "The Rollicking rogue (1941)', 'The blocked trail (1932)', 'The caballero. (1947)', The mark of Zorro (1924)', 'The masked woman (1920)', "The range cavalier (1933)', "The rangers' cede (1924)", 'Three Mysteries by Johnston Mcculley (2009)', 'Tragedy Trail (2020) 'Western Megapack (2011)', 'wild Noreen (2007)', "Women's War (2008) ")'r
(1935)', 'Captain Fly-By-Night (2012)', 'Cempanions
sefeneettt "['mark of zorro', 'bold caballero', 'crimson clown', 'crimson clown again', 'crimson clowns apprehension', /crimson clowns return', fcrimson clowns success', 'crimson clowns triumph', 'crimson clowns victory', 'crimson clowns willingness', 'crimson clown yielding', 'crimson clowns zeal', 'erimsen clowns zest', 'crimson clowns zestfulneess' 'crimson clowns zestiness', 'crimson clowns zestlessness' 'crimson clowns xestlessnesseessees""
'crinson clowns 'crimson clowns
cestlessneslesseelesseeee 1 essness' ....]'
zest zestlessness wew.ssssssssseeeeeeeeee sesnnessssssssssseeeeeee
Observation: The first books returned by the model for context are fact by the author (and more or less
satisfying the constraint), however, the model continues to autoregressively generate irrelevant and hallucinated title variations from the 'Crimson Clown' in a continuous problematic pattern.
23


Reviews:
[{"review_id": "mBtigrMBzl", "reviewer": "Reviewer_pbw5", "summary": "This paper proposes a dataset KITAB for testing on how LLMs can satisfy constraints in IR. A set of books are collected. Constraints can be set on authors, titles, dates, etc. and can be combined. The evaluation of the results by GPT-3.5 and GPT-4 are evaluated in terms of irrelevance, completeness, etc. Three test conditions are set using different prompts: no-context, self-context and context, providing (or not) the list of books written by an author.\nThe paper examines how GPT-3.5 and GPT-4 perform on different queries. A wide range of experimental results are reported.", "questions": "For the estimation of irrelevance or partial satisfaction, one case of match is when one is a string subset of another: For each ki, we check if there exists a book in the ground truth set of books by that author which is either a string subset match for ki (in both directions),... Do you also apply a threshold on the percentage of the substring, or a substring of any length is accepted?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem examined - constraint satisfaction - is not a widely studied problem. To some extent, this investigation extends the traditional IR to a special type of IR.\nThe data collection and experimental setting are well described.\nThe results may reveal that GPT models are not able to process this type of queries very well, and in particular, those with some constraints.\nThe authors will release the dataset.", "weaknesses": "The targeted problem is very special. The authors consider it as an IR problem. It resemble more database querying problem. Indeed, once the book references are transformed into structured database, the problem may be much simpler. Howere, as I understand, the intent of the author is not to examine how GPT models can handle such a search problem, but try to use this to test the ability of LLMs to handle queries containing constraints. While I appreciate this effort, I still question on the appropriateness of thFor e task. Instead of expression general constraints in a language, the constraints examined are very specific, and sometimes special. For example, constraints asking a title to end with a letter `v', or titles to be of 4 words, seem very particular. It is expected that a general LLM may not perform the task well because they have not been trained for the task. The main concern about the work is whether the types of constraints used can really test the ability of LLMs to satisfy constraints, or if the tests are on LLMs ability to understand the constraints and to execute filterings of books accordingly in this very special case. Even if LLMs are able to do the job well, would one be able to draw interesting conclusions? The experiments shown in the paper may not allow to draw general conclusions on LLM's ability to satisfy constraints.\nGiven the very special characteristics of the dataset, I question about the value of the KITAB dataset for the purpose of examining LLM's capability of constraint satisfaction in search.\nWhile the ground truth is determined correctly, there may be some problem in the measure of irrelevance and completeness, as some fuzzy matches are allows. As the authors admit, there may be some overestimation of the performance. So the experimental results are only indicative, with some possible rate of errors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TMf6AeI5Iy", "reviewer": "Reviewer_ZHUe", "summary": "The paper proposes KITAB, a dataset for evaluating how large language models perform on information retrieval tasks with constraint satisfaction. The author(s) describe the dataset constructions and settings in detail. Evaluated on the proposed dataset, observations from different perspectives indicate that KITAB is still a challenging task for LLMs.", "questions": "Please refer to \"Weaknesses\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Timely study of LLMs on constraint satisfaction for information retrieval.\n2. The overall paper is well-written and easy to follow.\n3. Detailed descriptions of the data construction are provided.\n4. The author(s) also promise to release the dataset, as well as code to the community.\n5. The author(s) comprehensively analyzed the results to draw several interesting observations.", "weaknesses": "1. Concerns of the submission being out-of-scope. The paper undoubtedly stands out as a great resource that makes contributions through its new dataset and the accompanying empirical studies. It certainly serves as a valuable asset for the research community. However, I'm concerned about its suitability as a full paper for ICLR, given the conference's typical focus.\n\n2. The author(s) have indeed conducted a thorough consideration of multiple facets in constructing the dataset, such as the number of constraints, the variety of constraints, and unsatisfiability. Nevertheless, the scope of the proposed dataset is fundamentally narrow, being confined to the domain of books. This domain-specific focus could limit its applicability to a broader range of IR research. It could be better if data from a variety of domains can be included.\n\n3. The evaluations presented are primarily focused on the LLM services provided by OpenAI. While these are undoubtedly among the leading services in the field, the inclusion of open-source LLMs, such as LLaMA 2 chat, in the evaluation process could provide a more comprehensive view of the landscape.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SaCDhHD8rw", "reviewer": "Reviewer_XGyb", "summary": "This paper introduces a new dataset, KITAB that evaluates how well LLMs  perform in answering constraint satisfaction queries for information retrieval.", "questions": "Can you enumerate all the constraints? It's not clear from the text what exactly the single and double constraints general architecture is.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall I think this new dataset is a well posed and timely work.\n\n* The dataset seems well constructed and reasonable\n* Incorporating constraint satisfaction for LLMs appears to be somewhat understudied, and this dataset will fit nicely into the existing LLM evaluation framework\n* The choice of model evaluation on the data (ChatGPTs) is reasonable\n* The differing frames for the data (with context, without, etc) makes sense\n* The dataset construction is well documented, with design choices explicitly described\n* The metrics and evaluations are well constructed", "weaknesses": "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.\n\nIt would also be nice if at least one opensource LLM was used in evaluation (i.e. LLAMA or LLAMA 2).\n\nSome 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bOaPeX8mkB", "reviewer": "Reviewer_dWav", "summary": "This paper develops a dataset and associated dataset construction framework for the evaluation of LLMs on _constraint satisfaction information retrieval_ tasks (eg, \"celebrities who died in 2022\"). This problem is interesting because many it covers many important and useful factual query tasks, but LLMs have significant accuracy difficulties. The authors experiment against existing LLMs (GPT-3.5 and GPT-4) while varying key dimensions of the task, and conduct performance and error analyses on the results.", "questions": "What does KITAB stand for? I couldn't find a definition. \n\nTable 3: why are some numbers red?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 4, "strengths": "A crisp task definition and associated evaluation dataset can be a high-leverage research contribution that enables and accelerates other work, so this is a worthwhile goal. It's also quite promising that the task seems to be intuitively straightforward yet is still challenging for state-of-the-art proprietary models like GPT-4.\n\nThe citations and engagement with IR research going back to 1989, 1999, 2009, etc is good to see and contextualizes the work well. \n\nThe exploration of problem setting parameters (task settings, author popularity, selectivity) is systematic and illuminating. The research questions are clearly defined and answered. The explanations of the dataset development and scoring are clear and thorough. The \"extensible\" nature of the methodology for dataset construction is useful to \"future proof\" the work.\n\nSome of the detailed error analysis was intriguing and suggestive of mechanisms behind the failure modes which is very exciting for future work:\n* ends-with vs starts-with constraints\n* \"sharp phase transition\" for failure rate vs author popularity\n* fabrication for \"list all books by author\"", "weaknesses": "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? Also, the procedures uses a few proprietary tools to develop the dataset: Azure Cognitive Services NER and Language API, Geonames in the dataset preparation. If the framework code release is open-sourced, future developers could substitute open or more reproducible components in these places, but this means that it would be difficult to create a new version of the dataset \"out of the box\". 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.\n\nFor controlled experimentation purposes it is useful to focus on a single domain such as book  authorship. However, it seems like there is some risk that the findings or behaviors may not transfer to other constrained IR tasks. How easy or difficult would it be to adapt the framework to generate similar dataset-task pairings in other domains as mentioned in the paper (movies, restaurants, etc)? \n\nCan fine-tuned LLMs do well on KITAB? The results and dataset would be more compelling with another FINE-TUNED setting, even if it had to be done with an OSS model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)