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

• URL: http://arxiv.org/abs/2606.19788v1
• Date: Thu, 18 Jun 2026 04:47:49 GMT
• Title: CombEval: A Framework for Evaluating Combinatorial Counting in Large Language Models
• Abstract summary: CombEval represents each problem as a typed Cofola specification over entities, objects, object dependencies, and constraints.<n>Unlike static collections, CombEval supports systematic variation of object type, entity scale, constraint count, and reasoning depth.
• Score: 12.245682714937338
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present CombEval, a dynamic benchmark for evaluating combinatorial counting in large language models. CombEval represents each problem as a typed Cofola specification over entities, combinatorial objects, object dependencies, and constraints, enabling controlled generation of natural-language counting problems with exact solver-verified answers. Unlike static collections, CombEval supports systematic variation of object type, entity scale, constraint count, and reasoning depth. We evaluate 11 LLMs under direct and code-augmented settings and find that models remain brittle on ordered objects, indistinguishable elements, relatively positional constraints, and nested object dependencies. Error analysis further identifies failures in constraint interpretation and counting principles. CombEval provides a diagnostic testbed for studying when and why LLMs fail at combinatorial reasoning. The code and generated benchmark suites are publicly available at \url{https://github.com/YuxuZhou-CN/combination-problem-generation}.

Related papers

• Solving Combinatorial Counting Problems with Weighted First-Order Model Counting [2.2680525506361717]
  We present Cofola (COmbinatorial counting LAnguage with Firstpreserving logic), a typed language that maps every Cofola program to a well-defined counting problem.<n>Cofola produces concise specifications and a uniform solving pipeline that is practical end-to-end.
  arXiv  Detail & Related papers  (2026-05-24T03:29:19Z)
• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• CORG: Generating Answers from Complex, Interrelated Contexts [57.213304718157985]
  In a real-world corpus, knowledge frequently recurs across documents but often contains inconsistencies due to ambiguous naming, outdated information, or errors.<n>Previous research has shown that language models struggle with these complexities, typically focusing on single factors in isolation.<n>We introduce Context Organizer (CORG), a framework that organizes multiple contexts into independently processed groups.
  arXiv  Detail & Related papers  (2025-04-25T02:40:48Z)
• New Dataset and Methods for Fine-Grained Compositional Referring Expression Comprehension via Specialist-MLLM Collaboration [49.180693704510006]
  Referring Expression (REC) is a cross-modal task that evaluates the interplay of language understanding, image comprehension, and language-to-image grounding.<n>It serves as an essential testing ground for Multimodal Large Language Models (MLLMs)
  arXiv  Detail & Related papers  (2025-02-27T13:58:44Z)
• Athanor: Local Search over Abstract Constraint Specifications [2.3383199519492455]
  We focus on general-purpose local search solvers that accept as input a constraint model.<n>The Athanor solver we describe herein differs in that it begins from a specification of a problem in the abstract constraint specification language Essence.
  arXiv  Detail & Related papers  (2024-10-08T11:41:38Z)
• Automatic Feature Learning for Essence: a Case Study on Car Sequencing [1.006631010704608]
  We consider the task of building machine learning models to automatically select the best combination for a problem instance. A critical part of the learning process is to define instance features, which serve as input to the selection model. Our contribution is automatic learning of instance features directly from the high-level representation of a problem instance using a language model.
  arXiv  Detail & Related papers  (2024-09-23T16:06:44Z)
• SHINE: Saliency-aware HIerarchical NEgative Ranking for Compositional Temporal Grounding [52.98133831401225]
  Temporal grounding, also known as video moment retrieval, aims at locating video segments corresponding to a given query sentence. We propose a large language model-driven method for negative query construction, utilizing GPT-3.5-Turbo. We introduce a coarse-to-fine saliency ranking strategy, which encourages the model to learn the multi-granularity semantic relationships between videos and hierarchical negative queries.
  arXiv  Detail & Related papers  (2024-07-06T16:08:17Z)
• Benchmarking Complex Instruction-Following with Multiple Constraints Composition [72.82640456309821]
  How to evaluate the ability of complex instruction-following of large language models (LLMs) has become a critical research problem. Existing benchmarks mainly focus on modeling different types of constraints in human instructions while neglecting the composition of different constraints. We propose ComplexBench, a benchmark for comprehensively evaluating the ability of LLMs to follow complex instructions composed of multiple constraints.
  arXiv  Detail & Related papers  (2024-07-04T14:50:45Z)
• NPHardEval4V: Dynamic Evaluation of Large Vision-Language Models with Effects of Vision [64.83085920775316]
  We introduce NPHardEval4V, a multimodal benchmark suite grounded in four classical NP-hard problems.<n>Each task is presented through a combination of structured visual layouts and textual prompts, designed to assess the ability of LVLMs to perform reasoning under visual-linguistic constraints.<n>Our results show that while these models perform reasonably well on perception-based inputs, they struggle with global optimization, abstraction, and constraint satisfaction.
  arXiv  Detail & Related papers  (2024-03-04T07:10:31Z)
• CodeComplex: Dataset for Worst-Case Time Complexity Prediction [7.974618854858136]
  Code time complexity prediction involves various intricate factors such as the input range of variables and conditional loops.<n>Current benchmarks fall short of providing a rigorous assessment due to limited data, language constraints, and insufficient labeling.<n>We introduce CodeComplex, the first robust and extensive dataset designed to evaluate LLMs' reasoning abilities in predicting code time complexity.
  arXiv  Detail & Related papers  (2024-01-16T06:54:44Z)
• XCSP3: An Integrated Format for Benchmarking Combinatorial Constrained Problems [3.149883354098941]
  The new format is made compact, highly readable, and rather easy to parse. XCSP3 encompasses practically all constraints that can be found in major constraint solvers. The user can make sophisticated queries for selecting instances from very precise criteria.
  arXiv  Detail & Related papers  (2016-11-10T17:00:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.