cs.CLAug 15, 2026

RamseyGadgets: A Graph Construction Dataset for LLMs

Authors: Zohair Raza Hassan, Deepak Pandita

Organizations: Rochester Institute of Technology, NY, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Constructing special graphs is an important task within graph theory and computer science. Many popular graph constructions are the result of a comprehensive exploration of relevant graphs and human ingenuity. Given the rise of generative AI usage in mathematics, it is natural to test whether LLMs are able to construct graphs with specified properties using their reasoning capabilities. Unfortunately, many natural graph construction problems, such as finding extremal Ramsey-good graphs (i.e., avoiding specific monochromatic subgraphs), have been explored extensively in the literature, making it difficult to ascertain whether a construction is the product of an LLM's reasoning capabilities or its recollection from training data. In this work, we introduce RamseyGadgets, a novel dataset of 70 underexplored graph construction problems that require finding Ramsey-good graphs with special properties (e.g., containing an edge with a fixed color). These problems have reasonably sized solutions (at most 10 vertices) that can be verified by SAT solvers, making them suitable for automatic evaluation. Our dataset is easily expandable, as one can simply change the monochromatic subgraphs being avoided to obtain a new set of problems. We evaluate the performance of five open-source LLMs on our dataset and report the results. Our findings show that LLMs achieve only 37.70% accuracy on the hard-tier problems in our dataset, with Gemma-4-31B achieving the highest performance out of the five. We also showcase how our dataset allows us to ascertain what kind of hints help LLMs perform better at this task.

Figures & tables

Figure 1: Left: an example of a problem in RamseyGadgets . Right: a solution to the problem and a coloring adhering to the constraints described in the problem.
Figure 2: All graphs used as FF or HH in our dataset.
Figure 3: Distribution of minimal solution size.
ModelAccuracy (%)Pass@5 (%)Tokens
Zero-shot
Llama-3.1-8B-it1.71 ±\pm 1.865.711,175.4
gemma-4-31B-it36.00 ±\pm 2.3551.4318,118.0
gpt-oss-120b21.14 ±\pm 1.8638.5713,513.8
Qwen3-235B-A22B26.16 ±\pm 3.9045.0736,607.1
DeepSeek-R110.29 ±\pm 1.2021.4321,537.2
Table 1: Model performance (mean accuracy ±\pm standard deviation %, Pass@5 %) and average total tokens across evaluation settings.
Figure 4: Accuracy vs. Token Cost Trade-off across Models & Settings
ModelAccuracy (%)Pass@5 (%)Tokens
Zero-shot
Llama-3.1-8B-it1.33 ±\pm 1.831.331,181.3
gemma-4-31B-it20.00 ±\pm 2.3620.0019,343.0
gpt-oss-120b10.00 ±\pm 4.0810.0011,772.5
Qwen3-235B-A22B13.67 ±\pm 4.1513.5741,503.3
DeepSeek-R16.67 ±\pm 2.366.6722,363.3
Table 2: Model performance (mean accuracy ±\pm standard deviation %, Pass@5 %) and average total tokens for the cases considered in the Zero-shot + Example Hint setting.
Figure 5: Mean Accuracy vs. minimal solution size.
Figure 6: Model Accuracy by difficulty.
More in this topic

Graph Construction

See all 15 papers

Explore similar work

CardsList

  1. Doubly Saturated Ramsey Graphs: A Case Study in Computer-Assisted Mathematical Discovery

    Apr 23, 2026Benjamin Przybocki, John Mackey, Marijn J. H. Heule +1Large Language Model-Guided Scientific Discovery

    Carnegie Mellon University, Pittsburgh, USA

  2. Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks

    May 2, 2026Sunil Kumar Maurya, Xin LiuLLM EvaluationLLM Reasoning with Graphs

    University of Tokyo Tokyo, Japan · AIST Tokyo, Japan

  3. GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

    Sep 10, 2026Zixiang Xu, Yanbo Wang, Chenxi Wang +6LLM Reasoning with GraphsLLM Agents

    University of Southern California · University of California, Los Angeles · Mohamed bin Zayed University of Artificial Intelligence +2