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 14 papers

Explore similar work

CardsList
Apr 23, 2026

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

Ramsey-good graphs are graphs that contain neither a clique of size ss nor an independent set of size tt. We study doubly saturated Ramsey-good graphs, defined as Ramsey-good graphs in which the addition or removal of any edge necessarily creates an ss-clique or a tt-independent set. We present a method combining SAT solving with bespoke LLM-generated code to discover infinite families of such graphs, answering a question of Grinstead and Roberts from 1982. In addition, we use LLMs to generate and formalize correctness proofs in Lean. This case study highlights the potential of integrating automated reasoning, large language models, and formal verification to accelerate mathematical discovery. We argue that such tool-driven workflows will play an increasingly central role in experimental mathematics.

Benjamin Przybocki, John Mackey, Marijn J. H. Heule +1

Carnegie Mellon University, Pittsburgh, USA

Large Language Model-Guided Scientific Discovery
AskPDF
May 2, 2026

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

With the rapidly improving reasoning abilities of Large Language Models (LLMs), there is also a rising demand to use them in a wide variety of domains. This brings about the need to carefully evaluate the limits of the capabilities of these models with various tests and benchmarks. Graph structures are ubiquitous in real-world data, and are often used to represent and analyze relationship patterns within data. Many benchmarks have already been proposed in the graph literature to test the reasoning ability of LLMs to follow and execute graph algorithms. However, due to the limited context length of LLMs, these benchmarks consist of very small graphs. In real-world data, the size of graphs can be significantly larger, and in many cases, not fully accessible. In this paper, we examine a class of problems that arises with very large graphs having limited accessibility. We propose a large graph benchmark dataset, EstGraph, and introduce four distinct tasks designed to estimate large graph properties. We evaluate the reasoning abilities of LLMs on these tasks using a wide variety of graph datasets. In addition, we provide task-specific prompt constructions based on random walk sampling of large graphs (up to millions of nodes) that effectively convey sufficient information to LLMs within the limits of context length.

Sunil Kumar Maurya, Xin Liu

University of Tokyo Tokyo, Japan · AIST Tokyo, Japan

LLM EvaluationLLM Reasoning with GraphsGraph ReasoningLLM Reasoning
AskPDF
Sep 10, 2026

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

Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasoning over the graph itself, or to fix a single input format. We introduce Graph Theory Bench (GT Bench), a benchmark covering 24 classical graph problems in 44 task-structure settings, with over 100,000 examples across four representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation, that the best representation shifts with graph density, size, and topology as well as with the model, and that this sensitivity persists, attenuated, in the strongest reasoning models. Building on these observations, we propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA lifts Phi-4 from 53.5% to 69.1% on the benchmark's easy split and from 33.0% to 41.5% on its hard split, outperforming eight prompting and agent baselines, and transfers without retraining to GraCoRe and NLGraph. Code for benchmark generation and evaluation: https://github.com/xzx34/GTA. The project homepage is available at https://xzx34.github.io/gta/.

Zixiang Xu, Yanbo Wang, Chenxi Wang +6

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

LLM Reasoning with GraphsLLM AgentsGraph ReasoningAlgorithmic Reasoning
AskPDF