One-sentence Summary

Researchers from Microsoft Research, University of Illinois Urbana-Champaign, and Stanford University propose KITAB, a dataset of $13{,}000$13,000 book-related queries across $600+$600+ authors, to evaluate LLMs on constraint satisfaction for information retrieval, showing that context availability mitigates irrelevant information but fails to address fundamental barriers, as $\text{GPT4}$GPT4 and $\text{GPT3.5}$GPT3.5 exhibit severe limitations—including factual errors and incompleteness—that worsen with lower information popularity.

Key Contributions

• The paper introduces KITAB, a new dataset for measuring constraint satisfaction in language models, comprising 13,000 book-related queries spanning more than 600 authors, along with a dynamic data collection and constraint verification approach for generating comparable test data across other authors.

• The dataset offers control over constraint type and complexity in queries expecting longer list outputs, and includes metadata on constrainedness and information popularity to support fine-grained analysis of model behavior.

• Extended experiments on GPT4 and GPT3.5 characterize and decouple failure modes across information popularity, constraint types, and context availability, finding that context availability reduces irrelevant information but does not improve constraint satisfaction, highlighting fundamental barriers that persist even with complete relevant context provided.

Introduction

Large language models (LLMs) now power conversational search engines, but evaluating their factual accuracy remains difficult due to benchmark saturation, training data contamination, and the challenge of assessing open-ended outputs. The authors study constraint satisfaction in LLMs, where queries specify conditions the output must meet, such as "A list of research papers authored by {author} published after {year}." This perspective generalizes keyword, boolean, and faceted search, and is central to scenarios where users need precise, structured information rather than creative text. Prior benchmarks focus on simple single-constraint queries with one answer and have largely saturated, leaving open how models handle multi-constraint queries that generate longer outputs.

The authors introduce KITAB, a dataset of literature queries that fix an author constraint while varying lexical, temporal, and named entity constraints. They evaluate GPT4 and GPT3.5 under four controlled settings: baseline retrieval of all books by an author, queries answered from parametric knowledge only, queries answered with complete context provided, and a self-context setup where the model constructs its own context first. Findings show that even state-of-the-art models fabricate irrelevant books in 12% to 41% of cases when relying only on parametric knowledge, with higher error rates for less popular authors. Providing complete context reduces irrelevance but does not fix constraint satisfaction failures, while self-retrieval prompts increase hallucinations as models invent titles to meet constraints. GPT4 improves over GPT3.5, but the gap is modest, and perfect match accuracy stays below 35% across conditions. KITAB also includes a dynamic data collection and cleaning process on disjoint author lists, which helps counter benchmark leakage and saturation for independent testing.

Dataset

Introducing KITAB: A New Benchmark for Constraint Satisfaction

The authors introduce KITAB, a new dataset designed to evaluate the constraint satisfaction capabilities of large language models (LLMs) in the literature domain. It provides a framework with 12,989 queries, each paired with a set of constraints an LLM must satisfy when generating a book title.

1. Dataset Composition and Sources The dataset construction is a multi-stage process, beginning with author sampling from WikiData and cross-referencing with the Open Library repository.

• Author Sampling: The authors sampled 20,000 authors from WikiData, then filtered out those born before 1850 and those with fewer than 10 or more than 300 works, leaving 1,505.
• Final Author Set: These authors were cross-referenced with Open Library, keeping only those with at least five works there. This resulted in 599 authors. A control set of 12 handpicked, well-known authors from five continents was added for quality checks, bringing the final total to 611 authors.
• Popularity Proxy: The authors use the number of site links in WikiData for each author as a proxy for information popularity, a factor known to influence factual errors.

2. Book Collection and Processing For each author, the authors collected all books from Open Library tagged as English or with an empty language field. An additional language detection check using Azure Cognitive Services ensured only the earliest English edition was kept. The cleaning process included:

• Deduplication and cross-checking authorship and publication year across Open Library and WikiData.
• Title Variants: Keeping variants of the same title (e.g., "Gödel, Escher, Bach" vs. "Gödel, Escher, Bach: An Eternal Golden Braid") to facilitate evaluation.
• Quality Checks: Manual annotation revealed that less than 5% of GPT4 and 6% of GPT3.5 queries might be affected by missing book titles, a minor impact on model comparison.

3. Book Metadata and Constraint Construction To enable verification, KITAB includes rich metadata for each book:

• Provided Metadata: Publication year and lists of human or city names in the title.
• Entity Recognition: Human names were detected using both Azure Cognitive Services and GPT4 to be culturally complementary, while city names were detected using Azure Cognitive Services and the Geonames database.

All queries follow a fixed form: the first constraint is always the author, followed by variable constraints of different types:

• Lexical: Title starts/ends with a letter or has a specific word count.
• Temporal: Published between specific years.
• Named Entity: A city or human name is present or not present in the title.
• Subsampling: Queries were subsampled to ensure a balanced representation of constraint types and varied constrainedness.

4. Dataset Statistics and Usage The final dataset contains 8,239 single-constraint queries and 4,750 double-constraint queries.

• Double Constraints: All are individually satisfiable, and only 0.76% are jointly unsatisfiable. Unsatisfiable constraints, which match no book titles, constitute 7.99% of the queries.
• Usage: KITAB is used for offline model evaluation. It provides verification functions and a complete mapping of all books that satisfy each of the 12,989 queries, allowing for direct evaluation of LLM-generated output. This workflow design is intended to be adaptable to other domains like movies, restaurants, or research papers.

Method

The authors propose a comprehensive framework to evaluate Large Language Models (LLMs) on constrained queries, centered around the construction of the KITAB dataset and a set of specific experimental conditions. The primary objective is to dissect model performance regarding constraint satisfaction and identify bottlenecks in information retrieval tasks.

Data Collection and Dataset Construction

The methodology begins with a rigorous data collection pipeline to ensure data quality and diversity. The authors sample authors from WikiData, applying strict filters to exclude outliers and inaccurate data: authors born before 1850 are removed, and only those with between 10 and 300 linked works are retained. These candidates are cross-referenced with the Open Library repository to ensure a sufficient number of English-language publications (at least five works). This process results in a curated sample of 611 authors.

The distribution of these authors is characterized by varying levels of popularity, measured by the number of sitelinks in WikiData. As illustrated in the figure above, the dataset covers a wide range of popularity tiers, with queries distributed across different constraint types such as "starts-with," "ends-with," "word-count," and temporal or named entity constraints. This diversity allows for an analysis of how model performance correlates with content popularity and constrainedness.

Following author selection, the system collects book metadata from Open Library. The pipeline includes language detection using Azure Cognitive Services to filter for English editions, deduplication, and cross-checking authorship and publication years against WikiData. To facilitate constraint verification, the dataset includes extracted metadata such as publication years and named entities (human and city names) identified via Azure Cognitive Services and Geonames.

Constraint and Query Generation

Queries are generated by combining fixed author constraints with variable book constraints. The constraints are categorized into three types:

1. Lexical: Title starts or ends with a specific letter, or specific word count.
2. Temporal: Published within a specific year range.
3. Named Entity: Presence or absence of city or human names in the title.

The dataset comprises 8239 queries with a single book constraint and 4750 queries with two book constraints. The generation process ensures a balanced representation of constraint types and a mix of satisfiable and unsatisfiable queries (approximately 8% unsatisfiable).

Experimental Conditions

To answer the research questions, the authors design five distinct experimental conditions using specific prompt templates. These conditions isolate different aspects of model capability:

• ALL-BOOKS (Template 1): The model is asked to list all books by the author. This serves as an upper bound for retrieval performance, independent of constraint satisfaction.
• NO-CONTEXT (Template 2a): The model must satisfy constraints using only its parametric knowledge, without external context.
• WITH-CONTEXT (Template 2b): This condition simulates a retrieval-augmented generation (RAG) setup. The model is provided with the full list of the author's books as context and asked to filter them based on the constraints. This isolates the model's ability to verify constraints given complete information.
• SELF-CONTEXT (Template 3): A chain-of-thought approach where the model first retrieves the list of books and then applies constraints to that self-generated list.
• SINGLE-ITEM (Template 4): The model evaluates constraints on a single book title to decouple single-item verification from list processing.

This experimental design allows for a granular analysis of where failures occur, whether in retrieval, constraint understanding, or the combination of both.

Experiment

The experiments evaluate GPT-4 and GPT-3.5 on the KITAB dataset, using prompt variants including no-context, self-context, retrieved context, and single-item conditions to isolate failures in verifying book constraints. Even with lenient fuzzy-match metrics, both models perform poorly, with GPT-4 all-correctness below 35% across all conditions; chain-of-thought helps but is insufficient, and providing full context reduces irrelevant output but does not improve constraint satisfaction or completeness. Performance varies by constraint type, with ends-with being harder than starts-with and negation easier, and while author popularity sharply reduces irrelevant information beyond a low threshold, it does not yield gains in correctness, highlighting that scaling and retrieval alone do not solve constraint verification.

Both GPT4 and GPT3.5 show high rates of irrelevant information and poor constraint satisfaction across all prompting conditions. Providing full context reduces irrelevant information but does not meaningfully improve constraint satisfaction or full correctness, which remains very low overall. The models perform similarly, with GPT4 slightly ahead but still far from reliable. Irrelevant information rates drop substantially when context is provided, but constraint satisfaction remains low. Full correctness is strikingly low across all conditions, though WITH-CONTEXT shows visible improvement. GPT4 outperforms GPT3.5 only marginally, suggesting scaling alone does not resolve constraint satisfaction.

The table compares constraint types across one book and two book queries, showing how constrainedness varies by type and query complexity. These patterns are used to examine model performance on constrained fact retrieval tasks. Starts-with and ends-with constraints are more constrained than word-count or no-human-name constraints. Two book queries generally increase constrainedness compared to one book queries, except for city-name which decreases. While higher constrainedness usually lowers performance, ends-with and city-name constraints show the opposite trend.

GPT4 shows poor overall performance on the KITAB benchmark, with notable variation across constraint types. Ends-with queries are substantially harder than starts-with, while negation and entity constraints are relatively easier. Adding context reduces irrelevant book mentions but does not improve constraint satisfaction or completeness, and self-generated chain-of-thought actually increases irrelevant outputs. Ends-with constraints are much harder for the model than starts-with, likely due to the need for forward planning. Providing context nearly eliminates irrelevant books, yet satisfaction and completeness remain low. Higher popularity reduces irrelevant information but shows no clear benefit for satisfaction, completeness, or all-correctness rates.

Across experiments, providing full context consistently reduced irrelevant information but did not meaningfully improve constraint satisfaction or overall correctness, which remained low for both GPT-3.5 and GPT-4. Constraint types and query complexity influenced performance, with ends-with constraints being substantially harder than starts-with, while negation and entity constraints were relatively easier. Adding context nearly eliminated irrelevant book mentions but left satisfaction and completeness largely unchanged, and self-generated chain-of-thought even increased irrelevant outputs. Higher popularity reduced irrelevant information without clear gains in satisfaction or correctness, suggesting that scaling and context alone are insufficient to address constrained fact retrieval challenges.