Research map / Large language models / Retrieval and knowledge
KITAB: Evaluating LLMs on Constraint Satisfaction for Information Retrieval
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces KITAB, a dataset and dynamic collection pipeline of about 13k author-book constraint-satisfaction queries, and evaluates GPT-4 and GPT-3.5 on irrelevance, satisfaction, completeness, and all-correctness under no-context, self-context, and with-context prompts.
Problem
LLMs are increasingly used to answer constraint-satisfaction information retrieval queries (lists of items satisfying several constraints), but existing factual benchmarks are saturated, contaminated, or only test single-answer facts, so their reliability on long, constrained lists is poorly underst
Approach
Build a book-domain benchmark from Open Library and Wikidata with controllable lexical, temporal, and named-entity constraints, plus a re-runnable collection and verification workflow for new author samples, and decouple failure modes via prompt conditions (no-context, self-context, with-context) and author popularity and constrainedness bins.
Key results
- GPT-4 with no context: about 26% of returned books are irrelevant (not from the author) on average across single-constraint queries, with 0.24 unsatisfied clusters.
- All-correct rates are low: GPT-4 reaches 0.08 in no-context and 0.31 with full context on single-constraint queries; both models stay below 35%.
- Providing the complete author book list (with-context) reduces irrelevance to near zero (0.00 for GPT-4 and GPT-3.5) but does not fix constraint satisfaction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Provide complete author-book context instead of no context | GPT4 · KITAB, one book constraint | irrelevant information: 0.26 -> 0.00 | Helped |
| Provide complete author-book context instead of no context | GPT4 · KITAB, one book constraint | satisfied information: 0.51 -> 0.78 | Helped |
| Provide complete author-book context instead of no context | GPT4 · KITAB, one book constraint | all correct: 0.08 -> 0.31 | Helped |
| Use self-context retrieval instead of no context | GPT4 · KITAB, one book constraint | irrelevant information: 0.26 -> 0.33 | Hurt |
| Use self-context retrieval instead of no context | GPT3.5 · KITAB, one book constraint | irrelevant information: 0.20 -> 0.44 | Hurt |
| Provide complete author-book context instead of no context | GPT4 · KITAB, two book constraints | satisfied information: 0.34 -> 0.54 | Helped |
| Provide complete author-book context instead of no context | GPT4 · KITAB, two book constraints | completeness: 0.13 -> 0.52 | Helped |
| Increase from one to two book constraints | GPT4 · KITAB, no-context | satisfied information | Hurt |
| Use GPT4 rather than GPT3.5 | KITAB evaluation · KITAB, one book constraint | all correct: 0.07 -> 0.08 | Helped |
Surprising findings
- Providing the complete author book list drives irrelevant information to near zero but barely improves constraint satisfaction, and GPT-4 is only modestly better than GPT-3.5.
- Self-retrieval (self-context) increases irrelevant books relative to no-context for GPT-4 (0.33 vs 0.26 on single-constraint queries).
Limitations
- Ground truth is built from Open Library and Wikidata, so some valid books missing from these sources are marked irrelevant (about 5-6% of queries affected by manual check).
- Evaluated only on GPT-4 and GPT-3.5 and only in the literature domain.
- Evaluation is lenient (fuzzy and subset matching, word-count tolerance), and temperature 0 only.
Experimental setup
Datasets: Open Library Wikidata Geonames Azure Cognitive Services Language API
Benchmarks: KITAB
Metrics: irrelevant information rate satisfied rate unsatisfied rate completeness all correct
Baselines: GPT-3.5
Builds on: chain-of-thought retrieval-augmented generation constrainedness
Closest papers by meaning
- Attention Satisfies: A Constraint-Satisfaction Lens on Factual Errors of Language Models (ICLR 2024 · similarity 0.88)
- Sufficient Context: A New Lens on Retrieval Augmented Generation Systems (ICLR 2025 · similarity 0.87)
- BABILong: Testing the Limits of LLMs with Long Context Reasoning-in-a-Haystack (NeurIPS 2024 · similarity 0.87)
- KScope: A Framework for Characterizing the Knowledge Status of Language Models (NeurIPS 2025 · similarity 0.86)
- WikiContradict: A Benchmark for Evaluating LLMs on Real-World Knowledge Conflicts from Wikipedia (NeurIPS 2024 · similarity 0.86)
- ClashEval: Quantifying the tug-of-war between an LLM’s internal prior and external evidence (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.