PaperlayerView exact revision on arXiv

Source-linked AI summary

RamseyGadgets: A Graph Construction Dataset for LLMs

Zohair Raza Hassan, Deepak Pandita

arXiv:2608.14999v1cs.CLcs.AI

TL;DR

LLMs need evaluation on graph-construction problems that are underexplored enough to distinguish reasoning from memorization. RamseyGadgets supplies 70 such Ramsey-good graph tasks and shows that models struggle, achieving only 37.70% accuracy on hard-tier problems.

  • Problem

    Existing graph-construction benchmarks offer limited evidence about LLM reasoning because many natural Ramsey problems are extensively represented in the literature.

  • Method

    The paper introduces 70 underexplored Ramsey-good graph-construction problems with solutions of at most 10 vertices and evaluates five open-source LLMs.

  • Results

    LLMs struggle to reliably solve the tasks, with 37.70% accuracy on hard-tier problems despite minimal solutions containing at most 10 vertices.

  • Takeaways & Limitations

    RamseyGadgets supports targeted analysis of graph-construction reasoning, including how hints, solution size, and specialized tools affect LLM performance.

  • Takeaways & Limitations

    The dataset excludes four hardness-gadget cases because including them would imply P = NP, and larger forbidden graphs make minimal solutions harder to compute.

Abstract

from arXiv · show

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 \textbf{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.

Introduction

RamseyGadgets introduces a 70-problem dataset for evaluating LLM reasoning on underexplored graph constructions with special Ramsey-good colorings. Its small, SAT-verifiable, scalable problems support evaluation of five open-source LLMs and domain-specific questions about their reasoning.

  • Dataset: 70 graph construction problems comprise RamseyGadgets, centered on Ramsey-good edge colorings that avoid specified forbidden monochromatic subgraphs.The problems target cases with only a handful of relevant papers.
  • Dataset: At most 10 vertices witness every problem’s solution graph, keeping the construction tasks reasonably sized.This design supports manageable candidate solutions while preserving graph-construction difficulty.
  • Dataset: SAT solvers provide simple script-based verification, while varying forbidden subgraphs makes the dataset easily expandable.These properties enable automatic checking and scalable generation of related problems.
  • Evaluation: The study evaluates five popular open-source LLMs and uses the dataset to examine hints, solution-size effects, and specialized tools.These correspond to questions about domain-specific assistance, minimal solution size, and task-specialized tool access.
  • Evaluation: 51.83% is the best overall accuracy achieved even with a specialized tool, falling to 37.70% on hard-tier problems.The results indicate that RamseyGadgets is difficult for the evaluated language models.

Related Work

Prior work evaluates LLMs on graph applications, computationally controlled reasoning, graph coloring, and constructive mathematics. RamseyGadgets extends this direction with underexplored, scalable graph-construction problems centered on special Ramsey-good colorings.

  • LLM and graph reasoning: Recent studies examine LLMs for graph-based applications and use computational complexity to assess reasoning more accurately and reliably.NPHardEval translates NP-hard algorithmic problems into natural language, while related work studies graph methods for enhancing LLMs and LLMs for graph machine learning.
  • LLM and graph reasoning: Hazra et al. use 3-SAT phase transitions to dynamically control problem hardness when evaluating LLMs.The benchmark leverages 3-SAT, described as the prototypical NP-complete problem.
  • Construction benchmarks: Existing construction-oriented benchmarks include graph k-coloring across 4–8 vertices and 2–4 colors, and MathConstruct’s 127 competition-sourced constructive problems.The graph-coloring dataset targets systematic reasoning, whereas MathConstruct requires constructing specific mathematical objects rather than giving a single numerical answer.
  • RamseyGadgets positioning: RamseyGadgets resembles MathConstruct but focuses specifically on constructing graphs with special Ramsey-good colorings that avoid forbidden monochromatic subgraphs.Its graphs are characterized as underexplored, reasonably sized, easily verifiable, and scalable.
  • Computational graph construction: Computational construction of special graphs often depends on specialized algorithms and intricate problem knowledge to prune the search space effectively.The passage contrasts this computational approach with prior uses of LLMs to prune genetic-algorithm search spaces, while noting that such uses reveal little about their reasoning capabilities.

Preliminaries

The preliminaries define Ramsey-goodness through red/blue edge-colorings that avoid specified monochromatic subgraphs, and establish notation and symmetry properties used throughout. The framework assumes connected forbidden graphs with at least three vertices, while color interchange makes (F, H) and (H, F) problems equivalent.

  • Definitions: A (F, H)-good coloring is a red/blue edge-coloring with no red F and no blue H, and a graph is (F, H)-good if such a coloring exists.The forbidden subgraphs need not be induced; the paper gives a (P3, K3)-good coloring as an example.
  • Notation: The notation P_n, C_n, and K_n denotes the path, cycle, and complete graph on n vertices, respectively.
  • Assumptions: The forbidden graphs F and H are assumed to be connected and to have at least three vertices.If either forbidden graph is P2, every good coloring excludes an edge of the corresponding color.
  • Symmetry: A graph is (F, H)-good if and only if it is (H, F)-good, because interchanging red and blue preserves the problem.Therefore, problems for the two ordered pairs are equivalent without loss of generality.

RamseyGadgets

RamseyGadgets is a 70-problem dataset of underexplored graph construction tasks spanning 13 (F, H) pairs and three gadget types. Its problems have minimal solutions of at most 10 vertices and are automatically verifiable through SAT encodings.

  • Dataset design: 70 graph construction problems vary Ramsey-goodness and gadget constraints across 13 distinct (F, H) pairs and three gadget types.The dataset uses stars on three or four vertices for F, connected three- or four-vertex graphs for H, and requires F ≠ H.
  • Gadget types: The dataset includes determiner, sender, and hardness gadgets, respectively enforcing one edge’s color, transmitting relations between two edges, or simulating SAT clauses and variables.Determiners force an edge to a specific color; positive and negative senders constrain two edges to match or differ; hardness gadgets encode clause-like restrictions.
  • Minimal solutions: 10 vertices is the largest minimal-solution size, computed by generating (F, H)-good graphs up to 10 vertices, removing redundant edges, and searching for gadgets.Minimal examples are provided with the dataset, together with their size distribution.
  • Verification: SAT verification maps each edge to a red/blue variable, with clauses excluding monochromatic copies of F and H and satisfiability checks confirming goodness and gadget properties.For a red determiner, satisfiability of ϕG establishes goodness, while unsatisfiability of ϕG ∧ (re) rules out a good coloring where the target edge is blue.
  • Difficulty tiers: 26 determiner problems are categorized as easy, while 44 problems requiring constraints on multiple edges or vertices are categorized as hard.Determiners can often be constructed by saturating an edge with copies of F and H.

Experiments and Results · Experimental Settings

The experiments evaluate five open-source language models on RamseyGadgets under zero-shot, hinted, and tool-assisted multiround settings. The setup combines standardized performance reporting with SAT-based graph-coloring infrastructure and specified computational resources.

  • Experiments and Results: Five open-source models of varying sizes are evaluated, including Llama 3.1-8B, Gemma 4-31B, GPT-OSS-120B, Qwen3-235B, and DeepSeek-R1.All models except Llama 3.1-8B have thinking or reasoning capabilities; Llama is included because it is comparatively small and popular.
  • Experimental Settings: The evaluation compares zero-shot, zero-shot-with-hints, and multiround tool-assisted settings.The supplied passage introduces these three settings, while later passages specify the hint and coloring-tool procedures.
  • Experimental Settings: Experiments run on 12 nodes, each equipped with one GH200 GPU, 144 Neoverse-V2 CPUs, and 550GB memory.The implementation uses vLLM, PySAT’s Glucose SAT solver, NetworkX, and Grand-Iso.
  • Zero-shot.: In zero-shot evaluation, models receive the required definitions and constraints, then provide one answer after reasoning.This setting asks the model to generate a graph adhering to the given constraints in a single response round.
  • Experiments and Results: Model performance is reported as mean accuracy ± standard deviation, Pass@5, and average total tokens across evaluation settings.These metrics are summarized in Table 1.
  • Zero-shot with Hints.: The hinted setting adds task-relevant information through structural, size, and computational hints.The structural hint permits blue coloring for edges outside H, while the size hint gives the known minimal example size n.
  • Multiround with Access to Coloring Tool.: The tool-assisted setting gives models a graph colorer and three rounds: two for exploration and one for aggregating findings into an answer.The colorer returns all (F, H)-good colorings of a graph relevant to the problem.

Results

Gemma-4-31B performs best across settings and offers the strongest cost–performance trade-off. Example and coloring-tool hints improve results, whereas structural hints usually hurt performance, and harder problems remain challenging.

  • Overall performance: Gemma-4-31B ranks first in mean accuracy and Pass@5 across settings, followed by Qwen-235B, gpt-oss-120b, DeepSeek-R1, and Llama-3.1-8B.Experiments were repeated five times, reporting mean accuracy, standard deviation, Pass@5, and average token usage.
  • Overall performance: Qwen-235B consumes the most tokens, while Gemma-4-31B provides the best trade-off between computational cost and performance.The cost–performance comparison uses mean accuracy against average total token consumption across models and settings.
  • Hint effects: Structural hints usually reduce performance, whereas size hints generally improve all models and raise gpt-oss-120b results by 10%.Gemma-4-31B is the exception for structural hints, improving in both accuracy and Pass@5.
  • Hint effects: Example hints substantially improve every model except DeepSeek-R1 on the 30 applicable problems.This comparison evaluates Zero-shot against Zero-shot + Example Hint only for the problems covered by that setting.
  • Multiround setting: Coloring tools produce the dataset’s best results: Gemma-4-31B reaches 51.83% ± 3.05 mean accuracy and 66.20% Pass@5.Multiround coloring-tool access also increases average token usage to 2.5x the Zero-shot level across models.
  • Difficulty and solution size: Performance declines as minimal solution size increases, and Gemma-4-31B achieves the highest mean accuracy on hard problems at 37.7%.Problems requiring at least 10 vertices solved by models belong to the easy tier and are the two specified determiners.

Discussion

The discussion finds that domain-specific hints affect LLM performance: sufficiently strong hints help, whereas overly general structural hints can hurt. More specific size and example hints almost always improve performance.

  • RQ1: Sufficiently strong domain-specific hints can improve LLM performance on the graph-construction task.The discussion frames this finding as an answer to RQ1.
  • RQ1: General structural hints may negatively impact LLM performance when they are too broad.The passage contrasts general structural hints with more specific alternatives.
  • RQ1: Specific size and example hints almost always improved LLM performance.These hint types are identified as more effective than general structural guidance.

Conclusion

RamseyGadgets introduces 70 underexplored, verifiable graph-construction problems and shows that five evaluated LLMs struggle to solve them reliably despite small solution sizes. The dataset also supports research on graph-construction-specific factors such as hints and tools.

  • Dataset: RamseyGadgets contains 70 specialized graph-construction problems with reasonably sized, easily verifiable solutions involving Ramsey-good graphs with special colorings.The dataset can be expanded by varying the forbidden graph pair (F, H) used to generate each problem.
  • Evaluation: Five evaluated LLMs struggle to reliably solve RamseyGadgets graph-construction problems, although the largest minimal solution size is 10 vertices.The dataset enables analysis of graph-construction-specific research questions, including the impact of hints and tools.
  • Future direction: RamseyGadgets is presented as an important first step toward improving LLM performance on graph-construction problems.The longer-term aim is to help researchers delegate arduous, frequently encountered graph-construction tasks to these models.

Appendix · Hyperparameters

The appendix reports that all models used a 32K max_tokens limit and their recommended settings, including hyperparameters, system prompts, and model-specific reasoning conventions. The listed configurations vary in sampling parameters and whether reasoning was explicitly induced.

  • Hyperparameters: All models used max_tokens set to 32K and were run with recommended settings, including hyperparameters, system prompt usage, and other quirks.These settings were applied as the implementation configuration for each model.
  • Hyperparameters: Llama-3.1-8B-it used Temperature 0.6, Top_p 0.9, and a system prompt.The model was run with the listed sampling parameters and system-prompt configuration.
  • Hyperparameters: Gemma-4-31B-it used Top_p 1, Top_k 0.95, and a system prompt, with a recommended “<|think|>” tag added to that prompt.The passage does not report a temperature value for this model.
  • Hyperparameters: One model used Temperature 0.7, Top_p 0.8, Top_k 20, Repetition-penalty 1.05, and a system prompt.The passage lists this configuration without naming the model.
  • Hyperparameters: One model used Temperature 0.6, Top-p 0.95, no system prompt, and was forced to start its response with “<think>”.The opening token sequence was used to force reasoning.

Prompts

The study separates system prompts, which define roles, instructions, and definitions, from main prompts, which provide the task; unsupported system prompts are merged into labeled instructions and task sections.

  • Prompt structure: System prompts described the model’s role, output instructions, and necessary definitions, while main prompts supplied the task.When system prompts were unsupported or not recommended, the two prompts were merged and labeled “Instructions” and “Task,” respectively.
  • Prompt templates: Prompt templates were provided for zero-shot, hinted, and multi-round settings in the accompanying code package.The files are zero_shot_prompts.py, hint_prompts.py, and multi_round_prompts.py.
Loading 2608.14999v1…