KnowledgeBerg: Evaluating Systematic Knowledge Coverage and Compositional Reasoning in Large Language Models

Abstract

Many real-world questions appear deceptively simple yet implicitly demand two capabilities: (i) systematic coverage of a bounded knowledge universe and (ii) compositional set-based reasoning over that universe, a phenomenon we term "the tip of the iceberg."We formalize this challenge through two orthogonal dimensions: knowledge width, the cardinality of the required universe, and reasoning depth, the number of compositional set operations.We introduce KNOWLEDGEBERG, a benchmark of 4,800 multiple-choice questions derived from 1,183 enumeration seeds spanning 10 domains and 17 languages, with universes grounded in authoritative sources to ensure reproducibility.Representative open-source LLMs demonstrate severe limitations, achieving only 5.26-36.88F1 on universe enumeration and 16.00-44.19accuracy on knowledge-grounded reasoning.Diagnostic analyses reveal three stages of failure: completeness, or missing knowledge; awareness, or failure to identify requirements; and application, or incorrect reasoning execution.This pattern persists across languages and model scales.Although testtime compute and retrieval augmentation yield measurable gains-up to 4.35 and 3.78 points, respectively-substantial gaps remain, exposing limitations in how current LLMs organize structured knowledge and execute compositional reasoning over bounded domains.The dataset is available at https://huggingface. co/datasets/2npc/KnowledgeBerg.When looking at all constellations, which type of theme appears most often?

Authors 5

1. Xiao Zhang

   University of Groningen

   Affiliation as printed

   University of Groningen

2. Qianru Meng Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University

3. Yongjian Chen

   University of Groningen

   Affiliation as printed

   University of Groningen

4. Yumeng Wang Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University

5. Johan Bos

   University of Groningen

   Affiliation as printed

   University of Groningen