KITAB: Evaluating LLMs on Constraint Satisfaction for Information Retrieval

1 INTRODUCTION

• The paper situates constrained information retrieval amid concerns about fabricated or irrelevant LLM outputs and challenges in evaluating open-ended generation.It notes that conversational LLMs have become part of search-engine user experiences.Source: §1 · p. 1
• Many factuality benchmarks focus on single-constraint, single-item answers, and many have saturated, leaving longer multi-constraint outputs less understood.The introduction frames consistency with external constraints as a challenge even for state-of-the-art models.Source: §1 · p. 2
• The evaluation separates parametric retrieval, constraint satisfaction with complete context, and self-retrieval before constraint application.It also includes an all-books baseline to characterize retrieval of an author's books.Source: §1 · p. 2
• Even GPT4 and GPT3.5 show high irrelevance and low constraint satisfaction; complete context reduces irrelevance, but perfect-match correctness remains below 35%.The reported findings also say self-retrieval increases irrelevant information and fabricated titles.Source: §1 · p. 2, Table 1 · p. 2
• KITAB contributes book queries across authors and a dynamic collection-and-cleaning approach that can produce versions using disjoint author lists.The approach is proposed as a way to support independent testing if the initial dataset is used in training.Source: §1 · p. 2

2 BACKGROUND & RELATED WORK

• Prior factual-query work often targets short responses and uses benchmarks described as saturated or contaminated, including SQuAD 2.0, MMLU, and BEIR.The cited examples report verbatim reproduction of SQuAD 2.0 questions by GPT4, contamination concerns for MMLU, and state-of-the-art GPT4 results on BEIR.Source: §2 · p. 3
• Retrieval-augmented generation combines generation with retrieval, but pre-retrieval can introduce challenges when retrieval is unreliable or expensive.The paper simulates the setting by supplying complete information in context to isolate constraint verification.Source: §2 · p. 3
• The constraint-satisfaction lens supports queries of varying complexity; KITAB adds a dataset and functional evaluation challenging even for large proprietary models.Yuksekgonul et al. (2023) instead propose an attention-based method for understanding and detecting failures in open-source models using model internals.Source: §2 · p. 3
• The paper measures constrainedness as one minus the fraction of domain items satisfying a constraint, and uses WikiData sitelinks as a proxy for entity popularity.It describes constrainedness as the opposite of database query selectivity and notes that KITAB provides these measures where direct measurement may be difficult.Source: §2 · p. 3

3 METHOD

• KITAB is designed to examine performance by constraint type, context availability, popularity, constrainedness, and bottlenecks in constrained information retrieval.The dataset varies the number of constraints and author popularity, alongside constraint types and candidate-solution counts.Source: §3 · p. 3

3.1 KITAB DATA COLLECTION

• From 20,000 WikiData writers, filtering by birth year (1850 onward) and 10–300 linked works left 1,505; Open Library matching with at least five cleaned, deduplicated works yielded 599 authors.The final sample includes an additional 12 handpicked well-known control authors, for 611 total.Source: §3.1 · p. 4
• Book collection filters and checks English titles, deduplicates records, and cross-checks authorship and publication year using Open Library and WikiData.The workflow keeps title variants; manual checks estimate that fewer than 5% of GPT4-query cases and fewer than 6% of GPT3.5-query cases may be affected by titles missing from KITAB.Source: §3.1 · p. 4
• Queries fix the author constraint and vary book constraints across lexical, temporal, and named-entity types, with 7.99% unsatisfiable constraints.The final dataset has 8,239 one-book-constraint queries and 4,750 two-book-constraint queries; 0.76% of the latter are jointly unsatisfiable.Source: §3.1 · p. 5
• KITAB provides book metadata, constraint-verification functions, and mappings of satisfying books for all 12,989 queries to support offline evaluation.The workflow is presented as potentially useful in domains beyond literature.Source: §3.1 · p. 5

3.2 EXPERIMENTAL CONDITIONS

• ALL-BOOKS measures author-book retrieval without extra constraints, while NO-CONTEXT tests constraint satisfaction using only parametric knowledge.ALL-BOOKS also helps separate irrelevance across queries with no, one, or two additional book constraints.Source: §3.2 · p. 5
• WITH-CONTEXT supplies a complete author-book list, whereas SELF-CONTEXT asks the model to retrieve that list before applying constraints.SINGLE-ITEM isolates constraint application to one title from applying constraints to a whole list; all but Template 1 request a brief reason for each answer.Source: §3.2 · pp. 5–6

4 EXPERIMENTS

• GPT-4 and GPT-3.5 were evaluated on the dataset at temperature 0 with metrics accommodating partial and fuzzy matches; counting constraints treated titles one word above or below specified as satisfied.Source: §4 · p. 6, §4.1 · p. 6

4.1 METRICS AND EVALUATION

• The evaluation leniently matches partial or fuzzy titles, defines completeness by the fraction of ground-truth books matched, and requires full satisfaction and completeness for an all-correct answer.Irrelevant, satisfying, and unsatisfying cluster fractions sum to 1; the authors note this generous scoring may overestimate performance.Source: §4.1 · p. 6

4.2 RESULTS

• Even with complete context, GPT-4 remains unreliable on constraint satisfaction, completeness, and all-correctness; its overall advantage over GPT-3.5 is modest.Chain-of-thought improves accuracy but is insufficient, while SELF-CONTEXT increases irrelevant books.Source: §4.2 · p. 7
• Irrelevant information falls as author popularity rises, but satisfaction, completeness, and all-correctness show no clear positive correlation; all-correctness stays below 35%.Irrelevance is high for authors with 0–10 WikiData sitelinks, then drops and flattens; Figure 2 compares context conditions across popularity bins.Source: §4.2 · p. 7, Figure 2 · p. 8
• Across constraint types, higher constrainedness usually relates to lower performance, but ends-with and city-name constraints reverse this pattern, yielding an almost bimodal aggregate trend.Figure 3 compares context conditions across constrainedness bins; the authors do not fully explain the exceptions.Source: §4.2 · pp. 7–8, Figure 3 · p. 8
• Adding book constraints reduces completeness and constraint satisfaction, while author-only ALL-BOOKS queries elicit significantly more irrelevant information.Figure 4 compares author-only queries with queries adding one or two book constraints; the authors caution that domain cardinality for ALL-BOOKS is difficult to estimate.Source: §4.2 · pp. 8–9, Figure 4 · p. 9
• In SELF-CONTEXT, irrelevant books fall from 0.42 to 0.33 for GPT-4 and from 0.47 to 0.44 for GPT-3.5 after constraints are applied, but remain elevated.The models do not recover from initially fabricated titles.Source: §4.2 · p. 9
• Starts-with, ends-with, and publication-year constraints are easier to check on single titles than lists, whereas entity constraints are easier on lists.Table 3 reports GPT-4 performance across context conditions and constraint types for queries with one book constraint.Source: Table 3 · p. 7, §4.2 · p. 9

5 CONCLUSION

• KITAB combines a dataset with dynamic data collection to evaluate how language models filter information using constraints.The conclusion notes that its queries extend beyond simple facts to longer output lists.Source: §5 · p. 9
• Models using parametric knowledge may include irrelevant books, while constraint failures persist even with complete relevant context.Source: §5 · p. 9

A KITAB STATISTICS

• Figure 5 plots query distributions by Wikidata-sitelink author popularity, separately for single-book and two-book constraints.Source: Figure 5 · p. 13
• Figure 6 plots query distributions by constrainedness for single- and two-book constraints; its lower range is dominated by constraints requiring no human or city name in a title.Source: Figure 6 · p. 13

• Table 4 reports GPT-3.5 performance by constraint type for single-book queries across NO-CONTEXT, SELF-CONTEXT, and CONTEXT.Source: Table 4 · p. 13
• Table 5 reports aggregated model performance on KITAB for NO-CONTEXT and CONTEXT queries with two book constraints.Source: Table 5 · p. 14
• Tables 6 and 7 report GPT-4 and GPT-3.5 performance by constraint type for two-book queries, with satisfaction requiring both constraints.A constraint type is included when it appears at least once in the query.Source: Table 6 · p. 14, Table 7 · p. 14

• The cleaning workflow retains English or language-unspecified books, removes titles with more than two authors, and cross-checks author attribution across Open Library and Wikidata.The cross-check was reported to significantly improve data quality overall.Source: §C.1 · pp. 14–15
• Title deduplication lowercases strings, removes punctuation, and combines fuzzy matching with subset checks, including variants beginning with “The” or “A/An.”Evaluation applies the same title-matching strategy; merged duplicates retain the minimum publication year and can count toward multiple constraints.Source: §C.1 · p. 15
• Web checks found that 5% of sampled GPT-4 queries and 6% of GPT-3.5 queries contained a title absent from Open Library but attributed to the author.These are upper-bound query-level estimates; the effect on irrelevant-information rates is lower.Source: §C.1 · p. 15

C.2 SAMPLING CONSTRAINTS AND QUERIES

• The single-book-constraint set contains 8,239 queries, including 7.99% unsatisfiable queries sampled alongside lexical, temporal, word-count, and title-entity constraints.Source: §C.2 · p. 15
• The two-book-constraint set contains 4,750 queries; both constraints are individually satisfiable, while 0.76% are jointly unsatisfiable.Sampling varies query difficulty by how many books satisfy the combined constraints.Source: §C.2 · p. 15
• The SINGLE-ITEM condition samples 200 single-constraint queries and supplies a satisfying book plus, for satisfiable queries, an additional author book absent from the ground truth, for 400 queries total.Source: §C.2 · p. 15

D PROMPTING TEMPLATES

• The templates cover listing all author books and filtering an author-book list against additional constraints, including prompts with and without supplied context.The templates require list-style outputs and, in some conditions, brief reasons for why books satisfy criteria.Source: D PROMPTING TEMPLATES · p. 16
• Other templates ask models to retrieve an author’s books before filtering them, or to identify titles containing a human name.Source: D PROMPTING TEMPLATES · p. 17

E.1 POPULARITY

• Figure 7 plots GPT-4 and GPT-3.5 performance against popularity.The caption does not report the direction or magnitude of the relationship.Source: Figure 7 · p. 18

E.2 CONSTRAINEDNESS

• Figure 8 plots GPT-4 and GPT-3.5 performance against constrainedness.The caption does not report the direction or magnitude of the relationship.Source: Figure 8 · p. 19

E.3 BREAKDOWN OF GPT-4 PERFORMANCE BY CONSTRAINT TYPE

• Figures 9 and 10 examine GPT-4 outcomes across constraint types, relating constrainedness to irrelevance, unsatisfaction, satisfaction, completeness, and correctness.The captions identify the measures but do not state the plotted outcomes.Source: Figure 9 · p. 20, Figure 10 · p. 21

EXAMPLE 1

• With no context, GPT-4 returns five titles associated with Michael Scott, but none meets the four-word constraint.The example characterizes this as high unsatisfaction despite mapping the titles to the author’s book list.Source: F EXAMPLES · p. 22

EXAMPLE 2

• With context, GPT-4 returns Gabriel García Márquez books, but neither listed title ends with the required letter a.The example says the returned books are by the author, yet fail the title constraint.Source: F EXAMPLES · p. 22

EXAMPLE 3

• For Russell Humke Fitzgibbon, GPT-4’s self-context begins with two irrelevant titles that meet the letter-v constraint, then continues with titles that fail both relevance and constraint.The example describes subsequent autoregressive titles on similar religious topics as still irrelevant and no longer satisfying the constraint.Source: F EXAMPLES · p. 23

EXAMPLE 4

• For Johnston McCulley, self-context starts with three mostly relevant, constraint-satisfying titles, then produces an extended sequence of irrelevant, hallucinated Crimson Clown variations.The example describes the continuation as autoregressive and increasingly problematic.Source: F EXAMPLES · p. 23