# KITAB: Evaluating LLMs on Constraint Satisfaction for Information Retrieval

arXiv: https://arxiv.org/abs/2310.15511 · HTML: https://mlsanity.com/paper/2310.15511/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 24 Oct 2023.

## Builds on (most cited first, 26 of 26)

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Know What You Don't Know: Unanswerable Questions for SQuAD](https://mlsanity.com/paper/1806.03822/) (2018)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Siren's Song in the AI Ocean: A Survey on Hallucination in Large Language Models](https://mlsanity.com/paper/2309.01219/) (2023)
- [Capabilities of GPT-4 on Medical Challenge Problems](https://mlsanity.com/paper/2303.13375/) (2023)
- [Dissecting Recall of Factual Associations in Auto-Regressive Language Models](https://mlsanity.com/paper/2304.14767/) (2023)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [DoLa: Decoding by Contrasting Layers Improves Factuality in Large Language Models](https://mlsanity.com/paper/2309.03883/) (2023)
- [Measuring and Improving Consistency in Pretrained Language Models](https://mlsanity.com/paper/2102.01017/) (2021)
- [Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agents](https://mlsanity.com/paper/2304.09542/) (2023)
- [Head-to-Tail: How Knowledgeable are Large Language Models (LLMs)? A.K.A. Will LLMs Replace Knowledge Graphs?](https://mlsanity.com/paper/2308.10168/) (2023)
- [Emergent and Predictable Memorization in Large Language Models](https://mlsanity.com/paper/2304.11158/) (2023)
- [Controlled Text Generation with Natural Language Instructions](https://mlsanity.com/paper/2304.14293/) (2023)
- [Attention Satisfies: A Constraint-Satisfaction Lens on Factual Errors of Language Models](https://mlsanity.com/paper/2309.15098/) (2023)
- [Toward Unified Controllable Text Generation via Regular Expression Instruction](https://mlsanity.com/paper/2309.10447/) (2023)

## Built on by (most cited first, 11 of 11)

- [TextGrad: Automatic "Differentiation" via Text](https://mlsanity.com/paper/2406.07496/) (2024)
- [Phi-4-reasoning Technical Report](https://mlsanity.com/paper/2504.21318/) (2025)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [Chain of Thoughtlessness? An Analysis of CoT in Planning](https://mlsanity.com/paper/2405.04776/) (2024)
- [Eureka: Evaluating and Understanding Large Foundation Models](https://mlsanity.com/paper/2409.10566/) (2024)
- [BenchAgents: Multi-Agent Systems for Structured Benchmark Creation](https://mlsanity.com/paper/2410.22584/) (2024)
- [From Instructions to Constraints: Language Model Alignment with Automatic Constraint Verification](https://mlsanity.com/paper/2403.06326/) (2024)
- [Recursive Decomposition of Logical Thoughts: Framework for Superior Reasoning and Knowledge Propagation in Large Language Models](https://mlsanity.com/paper/2501.02026/) (2025)
- [The Ability of Large Language Models to Evaluate Constraint-satisfaction in Agent Responses to Open-ended Requests](https://mlsanity.com/paper/2409.14371/) (2024)
- [Music Recommendation with Large Language Models: Challenges, Opportunities, and Evaluation](https://mlsanity.com/paper/2511.16478/) (2025)
- [FASHION-RQ: Mining Hierarchical Semantic Structure for Automated Evaluation of Fashion Retrieval](https://mlsanity.com/paper/2610.17841/) (2026)

## Abstract (arXiv)

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 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 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.