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

CombEval introduces a dynamic benchmark framework designed to rigorously evaluate the combinatorial counting capabilities of large language models (LLMs). This framework addresses a critical gap in existing benchmarks by synthesizing complex, structured counting problems from a formal specification rather than relying on static question banks. By enabling systematic variation across object types, entity scales, and constraint counts, CombEval allows researchers to control the structural complexity of problems. This controlled environment is crucial for diagnosing precisely when and why LLMs fail at combinatorial reasoning—such as issues with ordered objects or nested dependencies—providing a diagnostic testbed for studying model limitations in this domain.

Formalization via Cofola

The core of CombEval is the use of Cofola, a typed declarative language and solver specifically designed for combinatorial counting. Each problem is formalized as a triple P = ⟨D, O, C⟩, where D is the finite entity domain, O is the set of combinatorial objects defined over D (e.g., sets or sequences), and C is the set of constraints over these objects. This formal structure allows for precise definition of object types (such as sets, bags, tuples, sequences) and constraints (like subset membership or relative order patterns). The Cofola solver compiles this formal specification into weighted first-order model counting (WFOMC) instances, which are solved efficiently to provide an exact answer verification for a wide range of combinatorial problems.

Dynamic Problem Generation Pipeline

CombEval generates problem instances through a typed object-DAG pipeline. This process involves several controlled steps:

1. Initializing a finite entity domain with 'n' entities and sampling initial set or bag objects.

2. Constructing a Cofola object DAG by repeatedly sampling type-compatible operators (like 'choose', 'sequence', or 'composition') to define combinatorial operations, controlled by maximum dependency depth 'd'.

3. Sampling a set of constraints ('k' constraints) whose types match the selected objects, covering structural and cardinality constraints.

4. Using a template-based method to convert the generated CO problem into natural language using templates associated with each Cofola object type, ensuring that every instance is grounded in a formal program and solved exactly before evaluation.

Systematic Evaluation of LLMs

CombEval is used to conduct systematic evaluations of 11 mainstream LLMs, including both open-source models (e.g., Qwen, DeepSeek) and closed-source models (e.g., GPT-5.5). The evaluation protocol is designed to test reasoning under two paradigms: standard natural language reasoning (zero-shot) and code-augmented reasoning, where models are prompted to return executable Python code for computation. Key observations from the experiments include that Model scale and advanced reasoning techniques lead to improved overall accuracy, but all models still show clear degradation on typed objects that require indistinguishable elements, ordered structures, or multi-step dependencies.

Controllability of Difficulty

A primary research question addressed by CombEval is the controllability of problem difficulty. The framework allows for fine-grained control over difficulty by systematically tuning structural variables:

1. Increasing entity size ('n') expands the combinatorial search space.

2. Increasing constraint count ('k') introduces more complex restrictions, which can predictably lower model accuracy.

3. Increasing reasoning depth ('d') tests chain-structured reasoning, where performance degradation is monotonic as depth increases, demonstrating how deeper nesting exacerbates the risk of reasoning drift and error accumulation.

Robustness to Prompt Variations

The framework also investigates the impact of prompt templates on LLM performance. By comparing original problem formulations with solver-verified natural-language rewrites that preserve the exact Cofola structure (a closed-loop verification pipeline), researchers can isolate surface wording effects from underlying reasoning ability. The results indicate that surface template variations can cause some performance fluctuations, especially for less capable (but still strong) models, but stronger models, such as gpt-5.5, show greater robustness to these variations.

Solver-Backed Verification and Error Analysis

The benchmark relies on the Cofola solver for exact answer verification, filtering out instances with solver failures, unsupported features, or unstable answers. Furthermore, manual error analysis of incorrect answers reveals common failure modes that span both semantic gaps (e.g., misinterpreting together constraints) and classical combinatorial slips (e.g., missing factorial quotients for multiset circles). This diagnostic capability allows the framework to identify specific logical errors in LLMs' reasoning processes.

Limitations and Future Directions

While powerful, CombEval has limitations, including support only for English, computational constraints on solver runtime limiting the complexity of generated instances, and reliance on a subset of human validation. Future work plans include scaling the suites to additional object types (like graph objects) and exploring agentic techniques to enhance combinatorial reasoning performance. The code and generated benchmark suites are publicly available at the provided GitHub repository.

Here are specific improvements for AI systems based on the CombEval framework:

1. Improve Combinatorial Reasoning Benchmarks: Develop and deploy a dynamic benchmark generator (CombEval) that creates complex, structured combinatorial counting problems from formal specifications (Cofola). This moves beyond static datasets by allowing systematic variation of entity scale, constraint count, object type (sets, sequences, tuples), and reasoning depth.

2. Enhance Model Robustness to Structural Complexity: Train models to maintain high accuracy on combinatorial tasks even when faced with specific structural challenges identified in the error analysis:

3. Address Specific Reasoning Weaknesses: Explicitly train or fine-tune models on types of failures identified by CombEval, such as:

4. Handling Ordered and Positional Constraints (e.g., adjacency, relative ordering) in sequences and tuples without catastrophic failure, especially with indistinguishable elements (Error 1).

5. Managing Nested Object Dependencies: Improve the ability of models to reason through complex object dependencies where one combinatorial structure is defined based on the result of another (depth-2 and deeper nesting failures).

6. Mastering Constraint Interpretation: Enhance models' ability to correctly interpret and apply complex, multi-faceted constraints (e.g., simultaneously handling membership, cardinality, absolute position, and relative order) without logical errors (Error 5).

7. Improving Code-Augmented Reasoning for CO: Fine-tune models specifically on the ability to generate correct Python code for combinatorial counting problems. This involves training them to decompose complex combinatorial logic into executable algorithmic steps rather than relying solely on pattern matching (RQ1, RQ2).

8. Developing Prompt Robustness Strategies: Implement a closed-loop verification pipeline (Style Transfer -> Formal Back-translation -> Solver Verification) during model development/fine-tuning to ensure that models learn the underlying combinatorial structure rather than memorizing superficial prompt templates or linguistic variations (RQ3). This ensures reasoning is decoupled from surface wording.

9. Creating Difficulty Control Mechanisms: Use the framework's parameterization (entity size, constraint count, depth) to create adaptive training regimes where models are progressively exposed to increasing structural complexity, ensuring they learn scalable counting principles rather than just solving small, simple instances.

This improved AI system will be significantly better at tackling real-world constraint-driven decision optimization problems in finance, logistics, and healthcare by accurately performing combinatorial enumeration and reasoning.