Paper deep dive
RamseyGadgets: A Graph Construction Dataset for LLMs
Zohair Raza Hassan, Deepak Pandita
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/18/2026, 5:07:43 AM
Summary
The paper introduces RamseyGadgets, a dataset of 70 underexplored graph construction problems designed to evaluate the reasoning capabilities of Large Language Models (LLMs). The problems involve finding Ramsey-good graphs with specific properties (gadgets) that are small enough (<=10 vertices) to be verified by SAT solvers. The authors evaluate five open-source LLMs, finding that Gemma-4-31B performs best with 37.70% accuracy on hard-tier problems, highlighting significant challenges for LLMs in complex graph construction tasks.
Entities (14)
Relation Signals (8)
RamseyGadgets → contains → 70 graph construction problems
confidence 100% · RamseyGadgets consists of 70 similarly formatted graph construction problems
Gemma-4 31B → achievedhighestaccuracy → RamseyGadgets
confidence 95% · with Gemma-4-31B achieving the highest performance out of the five.
RamseyGadgets → evaluates → LLM reasoning
confidence 90% · RamseyGadgets: A Graph Construction Dataset for LLMs... test whether LLMs are able to construct graphs... using their reasoning capabilities.
LLaMA-3.1-8B → hasloweraccuracy → Gemma-4 31B
confidence 90% · Gemma-4-31B is the best-performing model... while Llama 3.1-8B is the worst-performing one.
Sender Gadget → istypeof → RamseyGadget
confidence 90% · we use 13 distinct pairs (F,H) and three types of gadgets... Sender Gadgets.
Hardness Gadget → istypeof → RamseyGadget
confidence 90% · we use 13 distinct pairs (F,H) and three types of gadgets... Hardness Gadgets.
Determiner Gadget → istypeof → RamseyGadget
confidence 90% · we use 13 distinct pairs (F,H) and three types of gadgets... Determiner Gadgets... Sender Gadgets... Hardness Gadgets.
RamseyGadgets → uses → SAT Solver
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 \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.
Tags
Links
- Source: https://arxiv.org/abs/2608.14999v1
- Canonical: https://arxiv.org/abs/2608.14999v1
Trouble viewing inline? Open PDF directly →
Full Text
40,022 characters extracted from source content.
Expand or collapse full text
RamseyGadgets: A Graph Construction Dataset for LLMsThanks: Supported in part by NSF grant CCF-2421977 and DUE-2439323. Zohair Raza Hassan Deepak Pandita 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. Introduction Constructing graphs with special properties is a task frequently faced by researchers in mathematics and computer science. Popular examples include constructing extremal graphs in Ramsey theory (27), expander graphs for derandomization (2), and graph gadgets for NP-hardness proofs (10). Constructing special graphs is an especially laborious and creative exercise; such graphs are typically found after the careful inspection of several graphs, through which researchers eventually discover a pattern that they can exploit to obtain a graph with the desired properties. Constructions that are the product of human ingenuity can have lasting effects that generalize to other problems. For example, despite their age, the celebrated graphs of Petersen (26) and Schläfli (29) and their generalizations are still used to solve problems today (19; 11). As we move towards our new age of AI-assisted mathematics, it is natural to want to use Large Language Models (LLMs) for these arduous yet frequently encountered and fruitful tasks. 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. Evaluating and training LLMs for this endeavor requires a high-quality dataset. While datasets for general mathematical and algorithmic problems exist (see Section Related Work for an overview), one specific to graph construction does not. Datasets specific to a type of math problem would not only provide more insight into an LLM’s limitations for said type of problem, but also allow us to ask new questions. We expand on this concept later. Several challenges arise when attempting to build such a specialized dataset. To avoid recollection from training data, we need problems that have received little attention in the literature. Many natural graph construction problems, such as those within Ramsey theory, have been explored extensively, and most open cases require large constructions (27) that would be difficult to work with within a reasonable context length or verify efficiently. Another important factor is scalability: as the performance of LLMs improves, datasets become saturated (4) and new problems are needed to evaluate LLM performance. In this work, we introduce RamseyGadgets, a novel dataset of 70 graph construction problems that addresses all of these challenges. The dataset is based on finding graphs with special Ramsey-good colorings (i.e., edge colorings avoiding forbidden monochromatic subgraphs—see Preliminaries for a formal definition). These problems are: • Less examined. Our problems are based on graphs with special Ramsey-good colorings for cases which only have a handful of relevant papers. • Reasonably sized. All of the problems are witnessed by solution graphs with at most 10 vertices. • Easily verifiable. Checking whether a given graph satisfies the properties specified by the problem is verifiable via a simple script using a SAT solver. • Scalable. Ramsey-good colorings are based on avoiding specified forbidden subgraphs. The dataset can be easily expanded by varying these forbidden subgraphs. An example is provided in Figure 1. We provide results on the performance of five open-source LLMs on RamseyGadgets, where we also showcase how our specialized dataset allows us to ask and analyze domain-specific research questions, such as: • RQ1. Does providing a domain-specific hint help LLMs perform better at the task? • RQ2. Does performance decrease as minimal solution size grows? • RQ3. Are LLMs able to perform better when given access to tools specialized for the task? Even with access to a special tool, the best accuracy achieved by an LLM is 51.83% on our dataset, with 37.70% accuracy on the hard-tier problems. Our dataset is publicly available at https://github.com/deepakpandita57/RamseyGadgets . Our contributions are summarized as follows: • We introduce RamseyGadgets, a novel dataset to evaluate LLM reasoning on graph construction problems. • We evaluate the performance of five popular open-source LLMs on RamseyGadgets, showcasing its difficulty. • We demonstrate how our specialized dataset allows us to ask domain-specific research questions about LLMs’ reasoning ability. Related Work There has been an increased interest in studying the abilities of LLMs for graph-based applications (20). 33 explore how LLMs can enhance graph machine learning methods and how graphs can be adopted to improve the performance of LLMs. With the improving reasoning abilities of LLMs, recent work has utilized computational complexity for more accurate and reliable assessment (9). 9 introduce NPHardEval, a dynamic reasoning benchmark built around the framework of computational complexity. The benchmark comprises algorithmic questions scaled across different computational complexity classes, including NP-Hard problems, and the problems are procedurally refreshed monthly to ensure models are constantly evaluated on unseen data instances. 8 introduced a dataset of Everyday Hard Optimization Problems (EHOP) that translate standard NP-hard algorithmic problems (such as graph coloring or the knapsack problem) into natural language to identify gaps in LLM performance and found large performance disparities relative to the well-documented textbook form. 16 utilized the 3-SAT — the prototypical NP-complete problem — to evaluate LLMs, specifically leveraging the 3-SAT “phase transition” phenomenon to dynamically control problem hardness. 17 introduced a dataset of graph k-coloring problems across varying complexities: 4 to 8 vertices and 2 to 4 colors (e.g., 4v2c up to 8v4c) to investigate the systematic reasoning capabilities of LLMs. MathConstruct (4) is a benchmark of 127 challenging problems sourced from various mathematics competitions, which targets constructive proofs. Instead of finding a single numerical answer, the task requires the LLM to construct a specific mathematical object such as a set, matrix, or graph that satisfies a given set of properties. These generated objects can be automatically verified using custom evaluators. They found that the models were able to achieve an accuracy of only 53% on their benchmark. BeyondBench (31) uses algorithmic problem generation to create mathematically grounded problems on the fly, ensuring contamination resistance. Contamination resistance is guaranteed through the vast problem space, strict mathematical verification, and isomorphic transformations that create syntactically new but semantically identical problems. The hard suite in BeyondBench also contains 10 variations of graph coloring problems. RamseyGadgets is close to MathConstruct in that our work also requires the construction of mathematical objects, but we are specifically focused on graph construction. Our dataset is based on finding graphs with special Ramsey-good colorings (i.e., edge colorings avoiding forbidden monochromatic subgraphs). These graphs are underexplored, reasonably sized, easily verifiable, and scalable. We note that constructing special graphs computationally is a popular approach (27; 15), but this often requires specialized algorithms based on intricate knowledge of the underlying problem to effectively prune the search-space of the desired graph. While LLMs have successfully been used to prune the search-space for genetic algorithms (24; 25; 5; 30), this tells us little about their reasoning abilities on problems of this type. RamseyGadgets bridges this gap by allowing us to ask and analyze domain-specific research questions for graph construction problems. Figure 2: All graphs used as F or H in our dataset. Preliminaries The notion of Ramsey-goodness concerns coloring the edges of a graph while avoiding specific (not necessarily induced) monochromatic subgraphs. Formally, a (F,H)(F,H)-good coloring of a graph is a red/blue edge-coloring containing no red F and no blue H, and a graph is called (F,H)(F,H)-good if it has at least one such coloring. For example, the coloring of the graph shown in Figure 1 is a (P3,K3)(P_3,K_3)-good coloring. The path, cycle, and complete graphs on n vertices are denoted as PnP_n, CnC_n, and KnK_n. The star graph on n+1n+1 vertices is denoted as K1,nK_1,n. Note that P3=K1,2P_3=K_1,2. The graphs used for F and H in our work are illustrated in Figure 2. As is standard, we assume that F and H are connected and have at least three vertices (if F=P2F=P_2 (resp., H=P2H=P_2), any (F,H)(F,H)-good coloring cannot contain any red (resp., blue) edge). Note that a graph is (F,H)(F,H)-good if and only if it is (H,F)(H,F)-good. Since colors can be interchanged without loss of generality, problems on (F,H)(F,H)-good graphs and problems on (H,F)(H,F)-good graphs are equivalent. RamseyGadgets Consider the following graph construction problem: Example Problem. Construct a (P3,K3)-good (P_3,K_3)-good graph G with an edge e such that e is red in every (P3,K3)(P_3,K_3)-good coloring of G. The problem is asking for a graph adhering to two constraints: (1) the Ramsey-goodness constraint enclosed in ⋯ ·s, and (2) the underlined “gadget” constraint. RamseyGadgets consists of 70 similarly formatted graph construction problems that were obtained by varying these constraints. In our dataset, we use 13 distinct pairs (F,H)(F,H) and three types of gadgets. We discuss the details of these below. Gadget Types The typical goal within Ramsey theory is to find the smallest complete graphs for which no (F,H)(F,H)-good coloring exists. Less popular, but still important, is the search for special graphs (hereafter referred to as gadgets) with restricted colorings known as “determiner gadgets,” “sender gadgets,” and ”hardness gadgets,” which are used for constructing families of minimal extremal graphs (6) and for proving NP-hardness (7; 28; 15). Since these gadget types are less examined in the literature, they make for good candidates for our dataset. Determiner Gadgets. These gadgets are based on forcing an edge to always be a specific color (28). For a pair (F,H)(F,H), a (F,H)(F,H)-red-determiner is a graph G with an edge e such that e is red in every (F,H)(F,H)-good coloring of G. (F,H)(F,H)-blue-determiners are defined similarly. Sender Gadgets. These gadgets are based on “sending signals” across two edges (see (6)). For a pair (F,H)(F,H), a (F,H)(F,H)-positive-sender is a graph G with distinct edges e and f such that e and f are the same color in every (F,H)(F,H)-good coloring of G. Moreover, there must exist a good coloring where e is red and a good coloring where e is blue11 1 Note that without this restriction we could simply take the disjoint union of two determiner gadgets to construct a “sender.”. (F,H)(F,H)-negative-senders are defined similarly, but e and f must always be opposite colorings. Hardness Gadgets. These gadgets were introduced to simulate clauses and variables in SAT formulas (28; 14; 15). In (15), these are defined explicitly for F=P3F=P_3, and it is noted that the definitions can be extended to any F that is a tree. We provide the definitions for F=K1,kF=K_1,k, since that is the only case for F considered in our work (see the preceding section for more details). • In a (K1,k,H)(K_1,k,H)-good coloring, an enforced vertex is a vertex incident to no red edges. A (K1,k,H)(K_1,k,H)-clause-gadget is a (K1,k,H)(K_1,k,H)-good graph with three vertices i1i_1, i2i_2, and i3i_3, such that: (1) G does not have a (K1,k,H)(K_1,k,H)-good coloring where i1i_1, i2i_2, and i3i_3 are all simultaneously enforced, and (2) G does have (K1,k,H)(K_1,k,H)-good colorings for all other 7 combinations of enforcement for i1i_1, i2i_2, and i3i_3. • In a (K1,k,H)(K_1,k,H)-good coloring, an enforcer vertex is a vertex incident to k−1k-1 red edges. A (K1,k,H)(K_1,k,H)-variable-gadget is a graph with vertices u1u_1, u2u_2, and n1n_1 such that: 1. In every (K1,k,H)(K_1,k,H)-good coloring of G, if u1u_1 or u2u_2 is not an enforcer vertex, then n1n_1 must be an enforcer vertex. 2. In every (K1,k,H)(K_1,k,H)-good coloring of G, if n1n_1 is not an enforcer vertex then u1u_1 and u2u_2 must be enforcer vertices. 3. There exists a (K1,k,H)(K_1,k,H)-good coloring of G where u1u_1 and u2u_2 are not enforcer vertices. 4. There exists a (K1,k,H)(K_1,k,H)-good coloring of G where n1n_1 is not an enforcer vertex. (,) (F,H) pairs After a careful exploration of viable candidates for F and H, we chose all pairs (F,H)(F,H) with the following properties: • F is star on three or four vertices (K1,2=P3CLOSE(K_1,2=P_3, and OPENK1,3)K_1,3) • H is a connected graph on three or four vertices (P3,K3,K1,3,P4,TK3,C4,K4−eCLOSE(P_3,K_3,K_1,3,P_4,TK_3,C_4,K_4-e, and OPENK4)K_4) • F≠HF =H These pairs were chosen because: • they allow for diverse gadget types; for example, determiners only exist when F≠HF =H, and the hardness gadgets are only well-defined for the case where F is a tree. • they allow for solutions that are reasonably sized; using the methodology described in (15), we computed the minimal size solutions for each of our problems and found that the largest graph has 10 vertices. • they are underexplored in the literature; while the case where F is a star and H is an arbitrary graph has been explored in the context of extremal graphs (27), in the context of our gadget types it was explored only very recently (14; 15) and that too only for hardness gadgets. Verification of results Any (F,H)(F,H)-good coloring of G corresponds to a true assignment of the following formula over the variables re|e∈E(G)\r_e~|~e∈ E(G)\, where rer_e is true if and only if e is red: ψG= _G= ⋀e1,…,ek∈E(G) form F(re1¯∨re2¯∨⋯∨rek¯)∧ _e_1,…,e_k∈ E(G) form F( r_e_1 r_e_2 ·s r_e_k)~~~ ⋀e1,…,ek∈E(G) form H(re1∨re2∨⋯∨rek) _e_1,…,e_k∈ E(G) form H(r_e_1 r_e_2 ·s r_e_k) Note how the clauses at the top force every copy of F to have at least one blue edge, and the clauses at the bottom force every copy of H to have at least one red edge. The correspondence between satisfying assignments of ϕG _G and (F,H)(F,H)-good colorings of G allows us to easily verify (F,H)(F,H)-goodness and gadget properties. For example, given G and e∈E(G)e∈ E(G), one can verify that G is a (F,H)(F,H)-red-determiner by checking if ϕG _G is satisfiable (i.e., G is (F,H)(F,H)-good) and checking if ϕG∧(re¯) _G ( r_e) is unsatisfiable (i.e., there is no good coloring when e is blue). Verification scripts for all gadgets follow a similar structure, except for hardness gadgets where it was easier to first compute all (F,H)(F,H)-good colorings (i.e., all satisfying assignments) and then check properties for each vertex. These scripts are available with our dataset. Notes on our Dataset Difficulty Tiers. Note that determiner gadgets only require a constraint on a single edge, whereas other gadget types require constraints on multiple edges/vertices. For the pairs (F,H)(F,H) in our dataset, determiners can often be constructed by saturating an edge with many copies of F and H. As such, we categorize the 26 problems involving determiners as “easy” and the other 44 problems in our dataset as “hard.” Exclusion of some Problems. In our dataset, we do not include the construction problems where we are asked to construct hardness gadgets for (F,H)(F,H) pairs where computing (F,H)(F,H)-goodness is solvable in polynomial-time, since the existence of both of these gadgets would imply P == NP. There are four such cases22 2 These cases are (P3,K3)(P_3,K_3), (P3,K1,3)(P_3,K_1,3), (P3,P4)(P_3,P_4), and (P3,TK3)(P_3,TK_3)., giving our dataset a total of 13×6+9×4=7013× 6+9× 4=70 problems. Minimal Examples. For each problem in our dataset, we used the methodology and code provided in (15) to compute the smallest solutions (fewest number of nodes). This involves iteratively generating (F,H)(F,H)-good graphs up to 10 vertices, removing redundant edges (i.e., edges belonging to neither F nor H) when appropriate, and searching for gadgets within this generated set. We provide these minimal examples alongside our dataset. We show the distribution of the sizes of these minimal solutions in Figure 3. Figure 3: Distribution of minimal solution size. Experiments and Results We evaluate the performance of five state-of-the-art open-source models with varying sizes: Llama 3.1-8B (23), Gemma 4-31B (32), GPT-OSS-120B (1), Qwen3-235B (34), and DeepSeek-R1 (12) on RamseyGadgets. All models except Llama 3.1-8B have thinking/reasoning capabilities. We include Llama 3.1-8B in our evaluation because it is comparatively a small and very popular model. We evaluate these models under three settings: zero-shot, zero-shot with hints, and multiround with access to a graph colorer. We elaborate on each setting and discuss the results below. Implementation Details. Our experiments were run on a cluster of 12 nodes where each node had access to one GH200 GPU, 144 Neoverse-V2 CPUs, and 550GB memory. Our code makes use of the following software: vLLM (21), PySAT’s (18) implementation of the Glucose SAT solver (3), NetworkX (13), and Grand-Iso (22). The hyperparameters for each model and the prompts used in our experiments are provided in the appendix. Experimental Settings Model Accuracy (%) Pass@5 (%) Tokens Zero-shot Llama-3.1-8B-it 1.71 ± 1.86 5.71 1,175.4 gemma-4-31B-it 36.00 ± 2.35 51.43 18,118.0 gpt-oss-120b 21.14 ± 1.86 38.57 13,513.8 Qwen3-235B-A22B 26.16 ± 3.90 45.07 36,607.1 DeepSeek-R1 10.29 ± 1.20 21.43 21,537.2 Zero-shot + Structural Hint Llama-3.1-8B-it 3.43 ± 0.78 5.71 1,488.7 gemma-4-31B-it 38.57 ± 5.25 54.29 18,231.5 gpt-oss-120b 18.86 ± 1.86 37.14 11,697.6 Qwen3-235B-A22B 24.40 ± 6.34 42.25 36,676.1 DeepSeek-R1 10.00 ± 2.26 18.57 21,798.6 Zero-shot + Size Hint Llama-3.1-8B-it 2.86 ± 1.01 8.57 1,155.0 gemma-4-31B-it 40.00 ± 2.86 55.71 18,209.7 gpt-oss-120b 25.71 ± 5.05 48.57 13,362.1 Qwen3-235B-A22B 27.71 ± 2.96 44.29 31,337.4 DeepSeek-R1 11.43 ± 3.19 21.43 19,266.4 Multiround Llama-3.1-8B-it 1.69 ± 1.18 8.45 13,807.3 gemma-4-31B-it 51.83 ± 3.05 66.20 56,124.9 gpt-oss-120b 25.07 ± 5.02 42.25 38,167.1 Qwen3-235B-A22B 28.45 ± 10.13 54.93 69,706.5 DeepSeek-R1 11.92 ± 2.32 25.35 49,755.2 Table 1: Model performance (mean accuracy ± standard deviation %, Pass@5 %) and average total tokens across evaluation settings. Zero-shot. In this setting, the model is given all required definitions and asked to generate a graph adhering to the given constraints. The model has one round to provide an answer after reasoning. Zero-shot with Hints. This setting is similar to the zero-shot setting, but we also provide the model a hint relevant to its task. We use three different hints: • Structural. In this setting, we tell the model that in any (F,H)(F,H)-good coloring of a graph G, any edge that does not belong to H can always be colored blue. This fact, albeit simple, is used to prune the search space for computational approaches (15). • Size. In this setting, we tell the model that the desired graph is known to exist on n vertices, where n is the size of the minimal example we computed. This setting mimics the scenario when we know an object exists due to a nonconstructive proof but don’t know exactly what the object is. • Relevant Example. In this setting, we give the model an example of a similar problem whose solution could be generalized to the target problem. Particularly, for prompts concerning (K1,3,H)(K_1,3,H)-goodness problems, we give the model an example of a similar gadget for the (P3,H)(P_3,H)-goodness setting if it exists. This gives us a total of 30 problems. This setting is inspired by the fact that constructions involving similar F or H can often be generalized, as seen in (14) and (15). Multiround with Access to Coloring Tool. In this setting, we provide the model access to a graph colorer that returns all (F,H)(F,H)-good colorings of a given graph for the relevant problem. The model has a total of three rounds to complete the task: two rounds for exploration, and one round to aggregate its findings and provide an answer. Results We repeat each experiment five times and report: (1) the average accuracy and standard deviation over each run, (2) the Pass@5 percentage (i.e., the percentage of problems that were solved correctly at least once across the five runs), and (3) the average number of tokens used. Our results (Table 1) show that Gemma-4-31B is the best-performing model across all settings based on mean accuracy and Pass@5, followed by Qwen-235B, gpt-oss-120b, and DeepSeek-R1, while Llama-3.1-8B is the worst-performing one. The low performance of Llama-3.1-8B is expected as it is not a thinking model. Gemma-4-31B achieves a mean accuracy of 36.00 ± 2.35% and Pass@5 of 51.43% in the Zero-shot setting. The best results are achieved by Gemma-31B in the Multiround setting, where it has access to a graph colorer: it achieves a mean accuracy of 51.83 ± 3.05% and Pass@5 of 66.20%. We observe in our analysis that a majority of this success comes from the “easy” difficulty tier of our dataset. Our results demonstrate that these popular LLMs struggle to achieve high performance on RamseyGadgets. Figure 4: Accuracy vs. Token Cost Trade-off across Models & Settings Computational Cost. Table 1 also shows the average total tokens consumed by the models. The Qwen-235B model turns out to be the most expensive in terms of token consumption while achieving the second-best performance. Figure 4 shows the mean accuracy versus average total token cost trade-off across all models and settings. Gemma-4-31B turns out to offer the best trade-off between computational cost and performance. Impact of Structural and Size Hints. Table 1 shows that our structural hint typically had a negative effect, with most models showing a slight decrease in performance as compared to the zero-shot setting. The only exception to this is Gemma-4-31B, where the accuracy and Pass@5 improve. On the other hand, the size hint generally improves the performance of all models, making a substantial (10%) impact on the results for gpt-oss-120b. Model Accuracy (%) Pass@5 (%) Tokens Zero-shot Llama-3.1-8B-it 1.33 ± 1.83 1.33 1,181.3 gemma-4-31B-it 20.00 ± 2.36 20.00 19,343.0 gpt-oss-120b 10.00 ± 4.08 10.00 11,772.5 Qwen3-235B-A22B 13.67 ± 4.15 13.57 41,503.3 DeepSeek-R1 6.67 ± 2.36 6.67 22,363.3 Zero-shot + Example Hint Llama-3.1-8B-it 3.33 ± 0.00 3.33 2,299.3 gemma-4-31B-it 25.33 ± 3.80 36.67 18,768.9 gpt-oss-120b 11.33 ± 3.80 20.00 14,407.5 Qwen3-235B-A22B 14.19 ± 1.44 19.35 38,195.0 DeepSeek-R1 4.67 ± 1.83 6.67 22,133.1 Table 2: Model performance (mean accuracy ± standard deviation %, Pass@5 %) and average total tokens for the cases considered in the Zero-shot + Example Hint setting. Impact of Example Hint. Table 2 shows the comparative performance of the models in the Zero-shot setting against the Zero-shot + Example Hint setting. Note that in this case, we are only evaluating over the 30 problems to which this setting applies. We observe that providing an example substantially improves the performance of all models, with the exception of DeepSeek-R1. (a) Zero-shot (b) Zero-shot + Structural Hint (c) Zero-shot + Size Hint (d) Multiround Figure 5: Mean Accuracy vs. minimal solution size. Impact of Coloring Tool. Having access to a coloring tool in the multiround setting substantially improves the performance of all models. Notably, this setting sees the best results on the dataset; Gemma-4-31B achieves a mean accuracy and Pass@5 of 51.83% ± 3.05 and 66.20%. However, we also observe that token usage increases substantially, with an average of 2.5x more tokens across all models when compared to the Zero-shot setting. Impact of Minimal Solution Size. Figure 5 shows the graphs for mean accuracy against the minimal solution size across all models and settings. We notice that the performance degrades as the number of vertices in the minimal solution increases. This demonstrates a very interesting pattern highlighting the increasing difficulty of the problems based on a minimal solution. We note that our dataset only has 8 problems that have minimal solutions with at least 8 vertices (see Figure 3), making it difficult to assert this trend. However, this trend holds even across problems with minimal solution sizes 4 to 7, which are well-represented in our dataset. We also note that the problems requiring a solution on at least 10 vertices solved by the models are part of the easy difficulty tier of our dataset; these are (K1,3,K4)(K_1,3,K_4)-red- and (K1,3,K4)(K_1,3,K_4)-blue-determiners. Results across Difficulty Tiers. Figure 6 shows the performance of all models across settings based on the difficulty tier (“easy” and “hard”) of the problems. We note that the models struggle on the hard problems in our dataset, with the highest mean accuracy being 37.7% for Gemma4-31B. (a) Zero-shot (b) Zero-shot + Structural Hint (c) Zero-shot + Size Hint (d) Multiround Figure 6: Model Accuracy by difficulty. Discussion In this section, we discuss our results in the context of the research questions posed in the introduction. • RQ1. Does providing a domain-specific hint help LLMs perform better at the task? Our results demonstrate that hints can improve the performance of LLMs if the hint is strong enough. Conversely, the performance can also be stymied if the hint is too general. As observed in our results, providing a general structural hint can negatively impact performance, while the more specific size and example hints almost always improved performance. • RQ2. Does performance decrease as minimal solution size grows? Our results show that the performance substantially decreases as minimal solution size grows, even when going from 4 vertices to 7 vertices. • RQ3. Are LLMs able to perform better when given access to tools specialized for the task? Our results show a substantial performance improvement when models are given a tool that computes (F,H)(F,H)-good colorings. Conclusion In this work we presented RamseyGadgets, a novel specialized dataset of 70 graph construction problems that are less examined and have reasonably sized and easily verifiable solutions. These problems are based on finding Ramsey-good graphs with special colorings. To avoid saturation, RamseyGadgets can easily be expanded to include more problems; each problem in the dataset is based on generating (F,H)(F,H)-good graphs, and simply varying F and H will give us new problems. The limitation of this approach is that as F and H grow larger, it becomes increasingly difficult to compute minimal solutions. However, this limitation only affects the scenario where one wants to provide this solution or its size as a hint. Other ways of obtaining new problems include avoiding multiple subgraphs in both colors and using more than two colors. Our evaluation of five popular LLMs on RamseyGadgets shows that these models struggle to reliably solve graph construction problems, despite that fact that the largest minimal solution size to a problem is 10 vertices. We demonstrated how our specialized dataset allows us to ask and analyze research questions about LLMs specific to graph construction, such as the impact of hints and tools. We see our work as an important first step towards improving the performance of LLMs on graph construction problems, allowing researchers to delegate these arduous yet frequently-encountered tasks to these models. References Agarwal et al. (2025) S. Agarwal, L. Ahmad, J. Ai, S. Altman, A. Applebaum, E. Arbus, R. K. Arora, Y. Bai, B. Baker, H. Bao, et al. Gpt-oss-120b & gpt-oss-20b model card. CoRR abs/2508.10925. Cited by: Experiments and Results. Arora and Barak (2009) S. Arora and B. Barak Computational complexity - A modern approach. Cambridge University Press. Cited by: Introduction. Audemard and Simon (2018) G. Audemard and L. Simon On the glucose SAT solver. Int. J. Artif. Intell. Tools 27 (1), p. 1840001:1–1840001:25. External Links: Link, Document Cited by: Implementation Details.. Balunovic et al. (2025) M. Balunovic, J. Dekoninck, N. Jovanovic, I. Petrov, and M. T. Vechev MathConstruct: challenging LLM reasoning with constructive proofs. In Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025, A. Singh, M. Fazel, D. Hsu, S. Lacoste-Julien, F. Berkenkamp, T. Maharaj, K. Wagstaff, and J. Zhu (Eds.), Proceedings of Machine Learning Research, Vol. 267. External Links: Link Cited by: Introduction, Related Work. Bhan et al. (2026) J. Bhan, N. Nobili, and P. Langer New bounds for zarankiewicz numbers via reinforced LLM evolutionary search. CoRR abs/2605.01120. External Links: Link, Document, 2605.01120 Cited by: Related Work. Burr et al. (1976) S. A. Burr, P. Erdős, and L. Lovász On Graphs of Ramsey Type. Ars Combinatoria 1 (1), p. 167–190. Cited by: Sender Gadgets., Gadget Types. Burr (1990) S. A. Burr On the Computational Complexity of Ramsey-Type Problems. Mathematics of Ramsey Theory 5, p. 46–52. Cited by: Gadget Types. Duchnowski et al. (2025) A. Duchnowski, E. Pavlick, and A. Koller A knapsack by any other name: presentation impacts LLM performance on NP-hard problems. In Findings of the Association for Computational Linguistics: EMNLP 2025, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, p. 6628–6651. External Links: Link, Document Cited by: Related Work. Fan et al. (2024) L. Fan, W. Hua, L. Li, H. Ling, and Y. Zhang NPHardEval: dynamic benchmark on reasoning ability of large language models via complexity classes. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), L. Ku, A. Martins, and V. Srikumar (Eds.), Bangkok, Thailand, p. 4092–4114. External Links: Link, Document Cited by: Related Work. Garey and Johnson (1979) M. R. Garey and D. S. Johnson Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman. External Links: ISBN 0-7167-1044-7 Cited by: Introduction. Goedgebeur and Van Overberghe (2022) J. Goedgebeur and S. Van Overberghe New bounds for Ramsey numbers R(Kk−e,Kl−e)R(K_k-e,K_l-e). Discrete Applied Mathematics 307, p. 212–221. Cited by: Introduction. Guo et al. (2025) D. Guo, D. Yang, H. Zhang, J. Song, P. Wang, Q. Zhu, R. Xu, R. Zhang, S. Ma, X. Bi, et al. Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. CoRR abs/2501.12948. Cited by: Experiments and Results. Hagberg et al. (2008) A. A. Hagberg, D. A. Schult, and P. J. Swart Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, G. Varoquaux, T. Vaught, and J. Millman (Eds.), Pasadena, CA USA, p. 11 – 15. Cited by: Implementation Details.. Hassan (2024) Z. R. Hassan The complexity of (P3,H)(P_3,H)-arrowing and beyond. In 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, Bratislava, Slovakia, August 26-30, 2024, R. Královic and A. Kucera (Eds.), LIPIcs, Vol. 306, p. 59:1–59:16. External Links: Link, Document Cited by: 3rd item, Hardness Gadgets., 3rd item. Hassan (2026) Z. R. Hassan The complexity of ramsey arrowing: A computational approach for hardness proofs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2026, Kortrijk, Belgium, June 2-4, 2026, J. Goedgebeur and P. Rzazewski (Eds.), LIPIcs, Vol. 376, p. 25:1–25:20. External Links: Link, Document Cited by: Related Work, 2nd item, 3rd item, Hardness Gadgets., Gadget Types, Minimal Examples., 1st item, 3rd item. Hazra et al. (2025) R. Hazra, G. Venturato, P. Z. Dos Martires, and L. De Raedt Have large language models learned to reason? a characterization via 3-sat. In Second Conference on Language Modeling, Cited by: Related Work. Heyman and Zylberberg (2025) A. Heyman and J. Zylberberg Evaluating the systematic reasoning abilities of large language models through graph coloring. CoRR abs/2502.07087. Cited by: Related Work. Ignatiev et al. (2024) A. Ignatiev, Z. L. Tan, and C. Karamanos Towards universally accessible SAT technology. In 27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024, Pune, India, August 21-24, 2024, S. Chakraborty and J. R. Jiang (Eds.), LIPIcs, Vol. 305, p. 16:1–16:11. External Links: Link, Document Cited by: Implementation Details.. Inoue et al. (2026) Y. Inoue, K. Kawarabayashi, A. Miyashita, B. Mohar, and T. Sonobe Three-edge-coloring (tait coloring) cubic graphs and nowhere-zero 4-flow for graphs on the torus. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, K. G. Larsen and B. Saha (Eds.), p. 6133–6165. External Links: Link, Document Cited by: Introduction. Jin et al. (2024) B. Jin, G. Liu, C. Han, M. Jiang, H. Ji, and J. Han Large language models on graphs: a comprehensive survey. IEEE Transactions on Knowledge and Data Engineering 36 (12), p. 8622–8642. Cited by: Related Work. Kwon et al. (2023) W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023, J. Flinn, M. I. Seltzer, P. Druschel, A. Kaufmann, and J. Mace (Eds.), p. 611–626. External Links: Link, Document Cited by: Implementation Details.. Matelsky et al. (2021) J. K. Matelsky, E. P. Reilly, E. C. Johnson, J. Stiso, D. S. Bassett, B. A. Wester, and W. Gray-Roncal DotMotif: an open-source tool for connectome subgraph isomorphism search and graph queries. Scientific Reports 11 (1). Cited by: Implementation Details.. Meta (2024) Meta Meta-llama/llama-3.1-8b. Hugging Face. Note: https://huggingface.co/meta-llama/Llama-3.1-8BAccessed: 2026-07-28 Cited by: Experiments and Results. Nagda et al. (2026) A. Nagda, P. Raghavan, and A. Thakurta Reinforced generation of combinatorial structures: ramsey numbers. CoRR abs/2603.09172. Cited by: Related Work. Novikov et al. (2025) A. Novikov, N., M. Eisenberger, E. Dupont, et al. AlphaEvolve: A coding agent for scientific and algorithmic discovery. CoRR abs/2506.13131. External Links: Link, Document, 2506.13131 Cited by: Related Work. Petersen (1898) J. Petersen Sur le théorème de tait. L’Intermédiaire des Mathématiciens 5, p. 225–227. Cited by: Introduction. Radziszowski (2026) S. Radziszowski Small Ramsey Numbers. Electronic Journal of Combinatorics DS1, p. 1–149. External Links: Link Cited by: Introduction, Introduction, Related Work, 3rd item. Schaefer (2001) M. Schaefer Graph ramsey theory and the polynomial hierarchy. Journal of Computer and System Sciences 62 (2), p. 290–322. External Links: Link, Document Cited by: Determiner Gadgets., Hardness Gadgets., Gadget Types. Schläfli (1858) L. Schläfli An attempt to determine the twenty-seven lines upon a surface of the third order and to divide such surfaces into species in reference to the reality of the lines upon the surface. The Quarterly Journal of Pure and Applied Mathematics 2, p. 110–120. Cited by: Introduction. Sharma (2025) A. Sharma OpenEvolve: an open-source evolutionary coding agent. GitHub. External Links: Link Cited by: Related Work. Srivastava et al. (2026) G. Srivastava, A. S. Hussain, Z. Bi, S. Roy, P. Pitre, M. Lu, M. Ziyadi, and X. Wang BeyondBench: contamination-resistant evaluation of reasoning in language models. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Related Work. Team et al. (2026) G. Team, S. E. Abd, V. Aggarwal, R. Algayres, A. Andreev, O. Bachem, I. Ballantyne, C. Brick, V. Cărbune, M. Casbon, et al. Gemma 4 technical report. CoRR abs/2607.02770. Cited by: Experiments and Results. Wang et al. (2025) S. Wang, J. Huang, Z. Chen, Y. Song, W. Tang, H. Mao, W. Fan, H. Liu, X. Liu, D. Yin, et al. Graph machine learning in the era of large language models (llms). ACM Transactions on Intelligent Systems and Technology 16 (5), p. 1–40. Cited by: Related Work. Yang et al. (2025) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. Qwen3 technical report. CoRR abs/2505.09388. Cited by: Experiments and Results. Appendix A Appendix Hyperparameters The “max_tokens” for each model was set to 32K. Each model was run using its recommended settings including, hyperparameters, system prompt usage, and other quirks: • Llama-3.1-8B-it – Temperature: 0.6 – Top_p: 0.9 – System prompt: yes • Gemma-4-31B-it – Temperature: – Top_p: 1 – Top_k: 0.95 – System prompt: yes. As recommended, a “<|think|>” tag was added to the system prompt. • gpt-oss-120b – Temperature: 1 – Top_p: 1 – Top_k: 0 – System prompt: yes. As recommended, “reasoning_effort = high” was added to the system prompt. • Qwen3-235B-A22B – Temperature: 0.7 – Top_p: 0.8 – Top_k: 20 – Repetition-penalty 1.05 – System prompt: yes • DeepSeek-R1 – Temperature: 0.6 – Top-p: 0.95 – System prompt: no – As recommended, the model was forced to start its response with “<think>” to force reasoning. Appendix B Prompts System prompts were used to describe the role, output instructions, and necessary definitions. Main prompts were used to provide the task. If a model did not support/recommend system prompts, the system and main prompts would be merged and marked as “Instructions” and “Task,” respectively. The prompts can be found under “/ramseygadgetspackage/zero_shot_prompts.py”, “/ramseygadgetspackage/hint_prompts.py”, and “/ramseygadgetspackage/multi_round_prompts.py” in the provided code.