ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

• URL: http://arxiv.org/abs/2608.18242v1
• Date: Tue, 18 Aug 2026 18:36:21 GMT
• Title: ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning
• Abstract summary: ClosureBench is a constructive benchmark for graph-relational reasoning with.<n> verified ground truth.<n>We evaluate models from 1.5B open weights to frontier systems.
• Score: 1.827510863075184
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We introduce ClosureBench, a constructive benchmark for compositional graph-relational reasoning with programmatically verified ground truth. Unlike fixed-test-set benchmarks vulnerable to data contamination, ClosureBench generates instances on demand: each task's reference answer is computed by executing a program in the Ein tensor-logic language, ensuring machine-verified correctness. The benchmark spans 26 task categories at three compositional levels (L1-L3), with difficulty controlled along three independent axes: graph size, edge density, and query depth. We evaluate models from 1.5B open weights to frontier systems (o3, GPT-4.1, Gemini 2.5, Claude Sonnet 4) and report three findings. First, because the benchmark can always supply fresh instances, it measures memorisation directly: a model fine-tuned on a fixed test set shows a 19.3 percentage-point gap between its accuracy on seen and on fresh instances, which a static test set cannot reveal. We scope this to supervised fine-tuning on answer pairs, not pretraining contamination. Second, accuracy falls as graph size and query depth increase, and the two interact: models misread the graph from its natural-language description and then reason correctly over the wrong graph, so even the strongest frontier model degrades from atomic to compositional queries. This bottleneck is a property of the reasoning rather than the input format: it persists when the graph is given as a JSON edge list or an adjacency matrix instead of prose. Third, a 4B model fine-tuned to emit executable programs rather than answers stays nearly flat across compositional levels and approaches frontier accuracy (94.3% on held-out instances) at a fraction of the token cost. This holds for two program targets, Ein and Python+NetworkX, so it is a property of verified program synthesis rather than of one language.

Related papers

• Can We Do Interpretable NLI with Graphs Based on Atomic Propositions? [2.6043470516146225]
  This paper explores whether Natural Language Inference can be performed using only interpretable, graph-based representations of evidence.<n>We introduce a fully graph-based pipeline where the classifier never directly processes the input text.<n>On the SNLI dataset, our pipeline achieves 89.7% accuracy, just 1.9 points below an identically trained text-based model.
  arXiv  Detail & Related papers  (2026-09-15T08:20:20Z)
• GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs [50.68372832207766]
  Graph Theory Bench (GT Bench) is a benchmark covering 24 classical graph problems in 44 task-structure settings.<n>GT Bench shows that accuracy is strongly tied to the input representation.<n>We propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding.
  arXiv  Detail & Related papers  (2026-09-10T22:50:10Z)
• Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMs [23.31472184486587]
  Graph-augmented large language models often assume that graph evidence produced by external computation can be used by the native decoder.<n>We show that providing graph evidence is not the same as making it usable.<n>We present S$2$GE as an instance showing that diagnosis-driven interface design can improve native decoder usability.
  arXiv  Detail & Related papers  (2026-08-31T08:27:01Z)
• More Accurate or More Efficient? Evaluating Locally Deployed Compact Open-Weight Language Models for Mathematical Reasoning [0.0]
  This paper presents a controlled, documented procedure for evaluating locally hosted LLMs on mathematical reasoning.<n>It combines fixed inference settings, hierarchical answer extraction and verification, explicit failure-mode classification, and per-question resource measurement.<n>Preliminary findings indicate that accuracy alone is an insufficient basis for selecting a local model.
  arXiv  Detail & Related papers  (2026-08-22T17:24:28Z)
• Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models [26.262278539931632]
  Graph reasoning provides a promising testbed for evaluating the reasoning ability of large language models (LLMs)<n>Existing graph reasoning benchmarks have limited coverage of data complexity and rely heavily on manual construction.<n>We propose a five-stage framework for constructing complex graph reasoning benchmarks.
  arXiv  Detail & Related papers  (2026-08-02T22:02:04Z)
• SDR: Set-Distance Rewards for Radiology Report Generation [2.2462804525190427]
  We propose set-to-set distances between generated and reference embeddings as continuous, permutation-invariant rewards.<n>Across two datasets and three vision--language models, post-training with set-to-set distance based rewards via GRPO consistently outperforms supervised fine-tuning.<n>The same set distances also enable test-time best-of-$N$ selection.
  arXiv  Detail & Related papers  (2026-05-30T00:10:51Z)
• ChartVerse: Scaling Chart Reasoning via Reliable Programmatic Synthesis from Scratch [57.01439313241121]
  We introduce Rollout Posterior Entropy (RPE), a novel metric that quantifies chart complexity.<n>We also develop truth-anchored inverse QA synthesis to guarantee reasoning rigor.<n>To further elevate difficulty and reasoning depth, we filter samples based on model fail-rate and distill high-quality Chain-of-Thought (CoT) reasoning.
  arXiv  Detail & Related papers  (2026-01-20T05:11:44Z)
• Detect Anything via Next Point Prediction [51.55967987350882]
  Rex- Omni is a 3B-scale MLLM that achieves state-of-the-art object perception performance.<n>On benchmarks like COCO and LVIS, Rex- Omni attains performance comparable to or exceeding regression-based models.
  arXiv  Detail & Related papers  (2025-10-14T17:59:54Z)
• Losing the Plot: How VLM responses degrade on imperfect charts [11.071294641688496]
  Vision language models (VLMs) show strong results on chart understanding, yet existing benchmarks assume clean figures and fact based queries.<n>We evaluate ChatGPT 4o, Claude Sonnet 4, and Gemini 2.5 Pro, finding sharp performance drops under corruption or occlusion.<n>A key innovation is prompt reverse inconsistency, where models contradict themselves when asked to confirm versus deny the same statement.
  arXiv  Detail & Related papers  (2025-09-22T21:12:20Z)
• Practical and Accurate Local Edge Differentially Private Graph Algorithms [11.49857418691547]
  We introduce novel LDP algorithms for two fundamental graph statistics: k-core decomposition and triangle counting.<n>Our approach leverages input-dependent private graph properties, specifically the degeneracy and maximum degree of the graph, to improve theoretical utility.<n>Our k-core decomposition achieves errors within 3x of exact values, far outperforming the 131x error in the baseline of Dhulipala et al.
  arXiv  Detail & Related papers  (2025-06-25T20:54:07Z)
• Does It Run and Is That Enough? Revisiting Text-to-Chart Generation with a Multi-Agent Approach [7.613758211231583]
  Large language models can translate natural-language chart descriptions into runnable code, yet approximately 15% of the generated scripts still fail to execute.<n>We propose a lightweight multi-agent pipeline that separates drafting, execution, repair, and judgment, using only an off-the-shelf GPT-4o-mini model.
  arXiv  Detail & Related papers  (2025-06-06T15:39:17Z)
• Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
  We propose the one-shot-subgraph link prediction to achieve efficient and adaptive prediction.<n>Design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps.<n>We achieve promoted efficiency and leading performances on five large-scale benchmarks.
  arXiv  Detail & Related papers  (2024-03-15T12:00:12Z)
• Enhancing Self-Consistency and Performance of Pre-Trained Language Models through Natural Language Inference [72.61732440246954]
  Large pre-trained language models often lack logical consistency across test inputs. We propose a framework, ConCoRD, for boosting the consistency and accuracy of pre-trained NLP models. We show that ConCoRD consistently boosts accuracy and consistency of off-the-shelf closed-book QA and VQA models.
  arXiv  Detail & Related papers  (2022-11-21T21:58:30Z)
• Heuristic Semi-Supervised Learning for Graph Generation Inspired by Electoral College [80.67842220664231]
  We propose a novel pre-processing technique, namely ELectoral COllege (ELCO), which automatically expands new nodes and edges to refine the label similarity within a dense subgraph. In all setups tested, our method boosts the average score of base models by a large margin of 4.7 points, as well as consistently outperforms the state-of-the-art.
  arXiv  Detail & Related papers  (2020-06-10T14:48:48Z)

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.