CombEval: A Framework for Evaluating Combinatorial Counting in Large Language Models

Overview

CombEval is a dynamic evaluation framework designed to assess the combinatorial counting (CO) capabilities of Large Language Models (LLMs). Unlike static benchmarks that are prone to data contamination and memorization, CombEval generates problems on-the-fly using a formal specification language called Cofola. This allows researchers to systematically vary problem parameters—such as entity scale, constraint count, and reasoning depth—to create a diagnostic testbed that verifies whether models are truly reasoning about combinatorial structures or merely matching surface-level patterns.

Each problem in CombEval is represented as a triple consisting of an entity domain, a set of combinatorial objects, and a set of constraints. The framework uses a typed object-directed acyclic graph (DAG) to generate these problems, which are then translated into natural language via templates. Crucially, every generated problem is solved by the Cofola backend using weighted first-order model counting (WFOMC) to provide an exact, verifiable ground truth. This approach enables a fine-grained analysis of model performance across different object types, such as sequences, partitions, and tuples, and allows for testing models in both direct natural language and code-augmented settings.

Key Findings

Evaluations of 11 mainstream LLMs reveal a clear performance hierarchy where larger, reasoning-enhanced models consistently outperform smaller ones. However, the study identifies significant brittleness across all tested models. Specifically, LLMs frequently fail when tasks involve ordered objects, indistinguishable elements, or nested dependencies. While code-augmented reasoning improves performance for stronger models, the models often struggle to interpret constraints correctly or apply fundamental counting principles, suggesting that their reasoning capabilities are still limited in the face of complex, multi-step combinatorial logic.

Combinatorial counting is a cornerstone of probability and decision optimization. As LLMs are increasingly deployed for complex reasoning tasks, understanding their limitations in structured mathematical domains is critical. CombEval provides a scalable, contamination-resistant method for researchers to pinpoint exactly where and why models fail, moving beyond aggregate scores to a deeper understanding of the structural reasoning boundaries of current AI systems.