RamseyGadgets: A Graph Construction Dataset for LLMs

# A Graph Construction Dataset for LLMs
Source: [https://arxiv.org/html/2608.14999](https://arxiv.org/html/2608.14999)
## RamseyGadgets: A Graph Construction Dataset for LLMsThanks:Supported in part by NSF grant CCF\-2421977 and DUE\-2439323\.

###### 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 introduceRamseyGadgets, 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](https://arxiv.org/html/2608.14999#bib.bib2)\), expander graphs for derandomization\([2](https://arxiv.org/html/2608.14999#bib.bib1)\), and graph gadgets for NP\-hardness proofs\([10](https://arxiv.org/html/2608.14999#bib.bib3)\)\. 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](https://arxiv.org/html/2608.14999#bib.bib7)\)and Schläfli\([29](https://arxiv.org/html/2608.14999#bib.bib8)\)and their generalizations are still used to solve problems today\([19](https://arxiv.org/html/2608.14999#bib.bib10);[11](https://arxiv.org/html/2608.14999#bib.bib9)\)\. 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\.

![Refer to caption](https://arxiv.org/html/2608.14999v1/Figures/fig1.jpg)Figure 1:Left:an example of a problem inRamseyGadgets\.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](https://arxiv.org/html/2608.14999#Sx2)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](https://arxiv.org/html/2608.14999#bib.bib2)\)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](https://arxiv.org/html/2608.14999#bib.bib11)\)and new problems are needed to evaluate LLM performance\.

In this work, we introduceRamseyGadgets, 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](https://arxiv.org/html/2608.14999#Sx1.F1)\. We provide results on the performance of five open\-source LLMs onRamseyGadgets, 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 is51\.83%on our dataset, with37\.70%accuracy on the hard\-tier problems\. Our dataset is publicly available athttps://github\.com/deepakpandita57/RamseyGadgets\. Our contributions are summarized as follows:

- •We introduceRamseyGadgets, a novel dataset to evaluate LLM reasoning on graph construction problems\.
- •We evaluate the performance of five popular open\-source LLMs onRamseyGadgets, 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](https://arxiv.org/html/2608.14999#bib.bib21)\)\.[33](https://arxiv.org/html/2608.14999#bib.bib22)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](https://arxiv.org/html/2608.14999#bib.bib23)\)\.[9](https://arxiv.org/html/2608.14999#bib.bib23)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](https://arxiv.org/html/2608.14999#bib.bib24)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](https://arxiv.org/html/2608.14999#bib.bib26)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](https://arxiv.org/html/2608.14999#bib.bib25)introduced a dataset of graphkk\-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](https://arxiv.org/html/2608.14999#bib.bib11)\)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](https://arxiv.org/html/2608.14999#bib.bib27)\)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\.

RamseyGadgetsis 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](https://arxiv.org/html/2608.14999#bib.bib2);[15](https://arxiv.org/html/2608.14999#bib.bib4)\), 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](https://arxiv.org/html/2608.14999#bib.bib5);[25](https://arxiv.org/html/2608.14999#bib.bib6);[5](https://arxiv.org/html/2608.14999#bib.bib33);[30](https://arxiv.org/html/2608.14999#bib.bib34)\), this tells us little about their reasoning abilities on problems of this type\.RamseyGadgetsbridges this gap by allowing us to ask and analyze domain\-specific research questions for graph construction problems\.

![Refer to caption](https://arxiv.org/html/2608.14999v1/Figures/fig2.jpg)Figure 2:All graphs used asFForHHin 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 redFFand no blueHH, 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](https://arxiv.org/html/2608.14999#Sx1.F1)is a\(P3,K3\)\(P\_\{3\},K\_\{3\}\)\-good coloring\. The path, cycle, and complete graphs onnnvertices are denoted asPnP\_\{n\},CnC\_\{n\}, andKnK\_\{n\}\. The star graph onn\+1n\+1vertices is denoted asK1,nK\_\{1,n\}\. Note thatP3=K1,2P\_\{3\}=K\_\{1,2\}\.

The graphs used forFFandHHin our work are illustrated in Figure[2](https://arxiv.org/html/2608.14999#Sx2.F2)\. As is standard, we assume thatFFandHHare connected and have at least three vertices \(ifF=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\\boxed\{\(P\_\{3\},K\_\{3\}\)\\text\{\-good\}\}graphGGwith anedgeeesuch thateeis red in every\(P3,K3\)\(P\_\{3\},K\_\{3\}\)\-good coloring ofGG\.

The problem is asking for a graph adhering to two constraints: \(1\) the Ramsey\-goodness constraint enclosed in⋯\\boxed\{\\cdots\}, and \(2\) the underlined “gadget” constraint\.RamseyGadgetsconsists 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](https://arxiv.org/html/2608.14999#bib.bib13)\)and for proving NP\-hardness\([7](https://arxiv.org/html/2608.14999#bib.bib14);[28](https://arxiv.org/html/2608.14999#bib.bib12);[15](https://arxiv.org/html/2608.14999#bib.bib4)\)\. 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](https://arxiv.org/html/2608.14999#bib.bib12)\)\. For a pair\(F,H\)\(F,H\), a\(F,H\)\(F,H\)\-red\-determineris a graphGGwith an edgeeesuch thateeis red in every\(F,H\)\(F,H\)\-good coloring ofGG\.\(F,H\)\(F,H\)\-blue\-determinersare defined similarly\.

##### Sender Gadgets\.

These gadgets are based on “sending signals” across two edges \(see\([6](https://arxiv.org/html/2608.14999#bib.bib13)\)\)\. For a pair\(F,H\)\(F,H\), a\(F,H\)\(F,H\)\-positive\-senderis a graphGGwith distinct edgeseeandffsuch thateeandffare the same color in every\(F,H\)\(F,H\)\-good coloring ofGG\. Moreover, there must exist a good coloring whereeeis red and a good coloring whereeeis blue111Note that without this restriction we could simply take the disjoint union of two determiner gadgets to construct a “sender\.”\.\(F,H\)\(F,H\)\-negative\-sendersare defined similarly, buteeandffmust always be opposite colorings\.

##### Hardness Gadgets\.

These gadgets were introduced to simulate clauses and variables in SAT formulas\([28](https://arxiv.org/html/2608.14999#bib.bib12);[14](https://arxiv.org/html/2608.14999#bib.bib15);[15](https://arxiv.org/html/2608.14999#bib.bib4)\)\. In\([15](https://arxiv.org/html/2608.14999#bib.bib4)\), these are defined explicitly forF=P3F=P\_\{3\}, and it is noted that the definitions can be extended to anyFFthat is a tree\. We provide the definitions forF=K1,kF=K\_\{1,k\}, since that is the only case forFFconsidered 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\-gadgetis a\(K1,k,H\)\(K\_\{1,k\},H\)\-good graph with three verticesi1i\_\{1\},i2i\_\{2\}, andi3i\_\{3\}, such that: \(1\)GGdoes not have a\(K1,k,H\)\(K\_\{1,k\},H\)\-good coloring wherei1i\_\{1\},i2i\_\{2\}, andi3i\_\{3\}are all simultaneously enforced, and \(2\)GGdoes have\(K1,k,H\)\(K\_\{1,k\},H\)\-good colorings for all other 7 combinations of enforcement fori1i\_\{1\},i2i\_\{2\}, andi3i\_\{3\}\.
- •In a\(K1,k,H\)\(K\_\{1,k\},H\)\-good coloring, an enforcer vertex is a vertex incident tok−1k\-1red edges\. A\(K1,k,H\)\(K\_\{1,k\},H\)\-variable\-gadgetis a graph with verticesu1u\_\{1\},u2u\_\{2\}, andn1n\_\{1\}such that: 1. 1\.In every\(K1,k,H\)\(K\_\{1,k\},H\)\-good coloring ofGG, ifu1u\_\{1\}oru2u\_\{2\}is not an enforcer vertex, thenn1n\_\{1\}must be an enforcer vertex\. 2. 2\.In every\(K1,k,H\)\(K\_\{1,k\},H\)\-good coloring ofGG, ifn1n\_\{1\}is not an enforcer vertex thenu1u\_\{1\}andu2u\_\{2\}must be enforcer vertices\. 3. 3\.There exists a\(K1,k,H\)\(K\_\{1,k\},H\)\-good coloring ofGGwhereu1u\_\{1\}andu2u\_\{2\}are not enforcer vertices\. 4. 4\.There exists a\(K1,k,H\)\(K\_\{1,k\},H\)\-good coloring of G wheren1n\_\{1\}is not an enforcer vertex\.

### \(𝑭,𝑯\)\\boldsymbol\{\(F,H\)\}pairs

After a careful exploration of viable candidates forFFandHH, we chose all pairs\(F,H\)\(F,H\)with the following properties:

- •FFis star on three or four vertices\(K1,2=P3CLOSE\(K\_\{1,2\}=P\_\{3\}, andOPENK1,3\)K\_\{1,3\}\)
- •HHis a connected graph on three or four vertices\(P3,K3,K1,3,P4,T​K3,C4,K4−eCLOSE\(P\_\{3\},K\_\{3\},K\_\{1,3\},P\_\{4\},TK\_\{3\},C\_\{4\},K\_\{4\}\-e, andOPENK4\)K\_\{4\}\)
- •F≠HF\\not=H

These pairs were chosen because:

- •they allow for diverse gadget types; for example, determiners only exist whenF≠HF\\not=H, and the hardness gadgets are only well\-defined for the case whereFFis a tree\.
- •they allow for solutions that are reasonably sized; using the methodology described in\([15](https://arxiv.org/html/2608.14999#bib.bib4)\), 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 whereFFis a star andHHis an arbitrary graph has been explored in the context of extremal graphs\([27](https://arxiv.org/html/2608.14999#bib.bib2)\), in the context of our gadget types it was explored only very recently\([14](https://arxiv.org/html/2608.14999#bib.bib15);[15](https://arxiv.org/html/2608.14999#bib.bib4)\)and that too only for hardness gadgets\.

### Verification of results

Any\(F,H\)\(F,H\)\-good coloring ofGGcorresponds to a true assignment of the following formula over the variables\{re\|e∈E⁡\(G\)\}\\\{r\_\{e\}~\|~e\\in E\(G\)\\\}, whererer\_\{e\}is true if and only ifeeis red:

ψG=\\displaystyle\\psi\_\{G\}=⋀e1,…,ek∈E⁡\(G\)​form​F\(re1¯∨re2¯∨⋯∨rek¯\)∧\\displaystyle\\bigwedge\_\{e\_\{1\},\\ldots,e\_\{k\}\\in E\(G\)\\text\{ form \}F\}\(\\overline\{r\_\{e\_\{1\}\}\}\\lor\\overline\{r\_\{e\_\{2\}\}\}\\lor\\cdots\\lor\\overline\{r\_\{e\_\{k\}\}\}\)~~~\\land⋀e1,…,ek∈E⁡\(G\)​form​H\(re1∨re2∨⋯∨rek\)\\displaystyle\\bigwedge\_\{e\_\{1\},\\ldots,e\_\{k\}\\in E\(G\)\\text\{ form \}H\}\(r\_\{e\_\{1\}\}\\lor r\_\{e\_\{2\}\}\\lor\\cdots\\lor r\_\{e\_\{k\}\}\)
Note how the clauses at the top force every copy ofFFto have at least one blue edge, and the clauses at the bottom force every copy ofHHto have at least one red edge\.

The correspondence between satisfying assignments ofϕG\\phi\_\{G\}and\(F,H\)\(F,H\)\-good colorings ofGGallows us to easily verify\(F,H\)\(F,H\)\-goodness and gadget properties\. For example, givenGGande∈E⁡\(G\)e\\in E\(G\), one can verify thatGGis a\(F,H\)\(F,H\)\-red\-determiner by checking ifϕG\\phi\_\{G\}is satisfiable \(i\.e\.,GGis\(F,H\)\(F,H\)\-good\) and checking ifϕG∧\(re¯\)\\phi\_\{G\}\\land\(\\overline\{r\_\{e\}\}\)is unsatisfiable \(i\.e\., there is no good coloring wheneeis 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 ofFFandHH\. 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 cases222These cases are\(P3,K3\)\(P\_\{3\},K\_\{3\}\),\(P3,K1,3\)\(P\_\{3\},K\_\{1,3\}\),\(P3,P4\)\(P\_\{3\},P\_\{4\}\), and\(P3,T​K3\)\(P\_\{3\},TK\_\{3\}\)\., giving our dataset a total of13×6\+9×4=7013\\times 6\+9\\times 4=70problems\.

##### Minimal Examples\.

For each problem in our dataset, we used the methodology and code provided in\([15](https://arxiv.org/html/2608.14999#bib.bib4)\)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 neitherFFnorHH\) 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](https://arxiv.org/html/2608.14999#Sx4.F3)\.

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](https://arxiv.org/html/2608.14999#bib.bib28)\), Gemma 4\-31B\([32](https://arxiv.org/html/2608.14999#bib.bib29)\), GPT\-OSS\-120B\([1](https://arxiv.org/html/2608.14999#bib.bib30)\), Qwen3\-235B\([34](https://arxiv.org/html/2608.14999#bib.bib31)\), and DeepSeek\-R1\([12](https://arxiv.org/html/2608.14999#bib.bib32)\)onRamseyGadgets\. 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](https://arxiv.org/html/2608.14999#bib.bib20)\), PySAT’s\([18](https://arxiv.org/html/2608.14999#bib.bib16)\)implementation of the Glucose SAT solver\([3](https://arxiv.org/html/2608.14999#bib.bib17)\), NetworkX\([13](https://arxiv.org/html/2608.14999#bib.bib18)\), and Grand\-Iso\([22](https://arxiv.org/html/2608.14999#bib.bib19)\)\. The hyperparameters for each model and the prompts used in our experiments are provided in the appendix\.

### Experimental Settings

Table 1:Model performance \(mean accuracy±\\pmstandard 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 graphGG, any edge that does not belong toHHcan always be colored blue\. This fact, albeit simple, is used to prune the search space for computational approaches\([15](https://arxiv.org/html/2608.14999#bib.bib4)\)\.
- •Size\.In this setting, we tell the model that the desired graph is known to exist onnnvertices, wherennis 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 similarFForHHcan often be generalized, as seen in\([14](https://arxiv.org/html/2608.14999#bib.bib15)\)and\([15](https://arxiv.org/html/2608.14999#bib.bib4)\)\.

#### 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](https://arxiv.org/html/2608.14999#Sx5.T1)\) 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±\\pm2\.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±\\pm3\.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 onRamseyGadgets\.

Figure 4:Accuracy vs\. Token Cost Trade\-off across Models & Settings#### Computational Cost\.

Table[1](https://arxiv.org/html/2608.14999#Sx5.T1)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](https://arxiv.org/html/2608.14999#Sx5.F4)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](https://arxiv.org/html/2608.14999#Sx5.T1)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\.

Table 2:Model performance \(mean accuracy±\\pmstandard deviation %, Pass@5 %\) and average total tokens for the cases considered in the Zero\-shot \+ Example Hint setting\.
#### Impact of Example Hint\.

Table[2](https://arxiv.org/html/2608.14999#Sx5.T2)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%±\\pm3\.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](https://arxiv.org/html/2608.14999#Sx5.F5)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](https://arxiv.org/html/2608.14999#Sx4.F3)\), 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](https://arxiv.org/html/2608.14999#Sx5.F6)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 presentedRamseyGadgets, 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,RamseyGadgetscan easily be expanded to include more problems; each problem in the dataset is based on generating\(F,H\)\(F,H\)\-good graphs, and simply varyingFFandHHwill give us new problems\. The limitation of this approach is that asFFandHHgrow 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 onRamseyGadgetsshows 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

- Agarwalet 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\.CoRRabs/2508\.10925\.Cited by:[Experiments and Results](https://arxiv.org/html/2608.14999#Sx5.p1.1)\.
- Arora and Barak \(2009\)S\. Arora and B\. BarakComputational complexity \- A modern approach\.Cambridge University Press\.Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p1.1)\.
- Audemard and Simon \(2018\)G\. Audemard and L\. SimonOn the glucose SAT solver\.Int\. J\. Artif\. Intell\. Tools27\(1\),pp\. 1840001:1–1840001:25\.External Links:[Link](https://doi.org/10.1142/S0218213018400018),[Document](https://dx.doi.org/10.1142/S0218213018400018)Cited by:[Implementation Details\.](https://arxiv.org/html/2608.14999#Sx5.SSx4.SSS0.Px1.p1.1)\.
- Balunovicet al\.\(2025\)M\. Balunovic, J\. Dekoninck, N\. Jovanovic, I\. Petrov, and M\. T\. VechevMathConstruct: challenging LLM reasoning with constructive proofs\.InForty\-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](https://proceedings.mlr.press/v267/balunovic25a.html)Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p2.1),[Related Work](https://arxiv.org/html/2608.14999#Sx2.p2.1)\.
- Bhanet al\.\(2026\)J\. Bhan, N\. Nobili, and P\. LangerNew bounds for zarankiewicz numbers via reinforced LLM evolutionary search\.CoRRabs/2605\.01120\.External Links:[Link](https://doi.org/10.48550/arXiv.2605.01120),[Document](https://dx.doi.org/10.48550/ARXIV.2605.01120),2605\.01120Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p4.1)\.
- Burret al\.\(1976\)S\. A\. Burr, P\. Erdős, and L\. LovászOn Graphs of Ramsey Type\.Ars Combinatoria1\(1\),pp\. 167–190\.Cited by:[Sender Gadgets\.](https://arxiv.org/html/2608.14999#Sx4.SSx1.SSS0.Px2.p1.1),[Gadget Types](https://arxiv.org/html/2608.14999#Sx4.SSx1.p1.1)\.
- Burr \(1990\)S\. A\. BurrOn the Computational Complexity of Ramsey\-Type Problems\.Mathematics of Ramsey Theory5,pp\. 46–52\.Cited by:[Gadget Types](https://arxiv.org/html/2608.14999#Sx4.SSx1.p1.1)\.
- Duchnowskiet al\.\(2025\)A\. Duchnowski, E\. Pavlick, and A\. KollerA knapsack by any other name: presentation impacts LLM performance on NP\-hard problems\.InFindings of the Association for Computational Linguistics: EMNLP 2025,C\. Christodoulopoulos, T\. Chakraborty, C\. Rose, and V\. Peng \(Eds\.\),Suzhou, China,pp\. 6628–6651\.External Links:[Link](https://aclanthology.org/2025.findings-emnlp.352/),[Document](https://dx.doi.org/10.18653/v1/2025.findings-emnlp.352)Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p1.1)\.
- Fanet al\.\(2024\)L\. Fan, W\. Hua, L\. Li, H\. Ling, and Y\. ZhangNPHardEval: dynamic benchmark on reasoning ability of large language models via complexity classes\.InProceedings 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,pp\. 4092–4114\.External Links:[Link](https://aclanthology.org/2024.acl-long.225/),[Document](https://dx.doi.org/10.18653/v1/2024.acl-long.225)Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p1.1)\.
- Garey and Johnson \(1979\)M\. R\. Garey and D\. S\. JohnsonComputers and intractability: A guide to the theory of NP\-completeness\.W\. H\. Freeman\.External Links:ISBN 0\-7167\-1044\-7Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p1.1)\.
- Goedgebeur and Van Overberghe \(2022\)J\. Goedgebeur and S\. Van OverbergheNew bounds for Ramsey numbersR⁡\(Kk−e,Kl−e\)R\(K\_\{k\}\-e,K\_\{l\}\-e\)\.Discrete Applied Mathematics307,pp\. 212–221\.Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p1.1)\.
- Guoet 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\.CoRRabs/2501\.12948\.Cited by:[Experiments and Results](https://arxiv.org/html/2608.14999#Sx5.p1.1)\.
- Hagberget al\.\(2008\)A\. A\. Hagberg, D\. A\. Schult, and P\. J\. SwartExploring network structure, dynamics, and function using networkx\.InProceedings of the 7th Python in Science Conference,G\. Varoquaux, T\. Vaught, and J\. Millman \(Eds\.\),Pasadena, CA USA,pp\. 11 – 15\.Cited by:[Implementation Details\.](https://arxiv.org/html/2608.14999#Sx5.SSx4.SSS0.Px1.p1.1)\.
- Hassan \(2024\)Z\. R\. HassanThe complexity of\(P3,H\)\(P\_\{3\},H\)\-arrowing and beyond\.In49th 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,pp\. 59:1–59:16\.External Links:[Link](https://doi.org/10.4230/LIPIcs.MFCS.2024.59),[Document](https://dx.doi.org/10.4230/LIPICS.MFCS.2024.59)Cited by:[3rd item](https://arxiv.org/html/2608.14999#Sx4.I6.i3.p1.1),[Hardness Gadgets\.](https://arxiv.org/html/2608.14999#Sx4.SSx1.SSS0.Px3.p1.1),[3rd item](https://arxiv.org/html/2608.14999#Sx5.I7.i3.p1.1)\.
- Hassan \(2026\)Z\. R\. HassanThe complexity of ramsey arrowing: A computational approach for hardness proofs\.In52nd 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,pp\. 25:1–25:20\.External Links:[Link](https://doi.org/10.4230/LIPIcs.WG.2026.25),[Document](https://dx.doi.org/10.4230/LIPICS.WG.2026.25)Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p4.1),[2nd item](https://arxiv.org/html/2608.14999#Sx4.I6.i2.p1.1),[3rd item](https://arxiv.org/html/2608.14999#Sx4.I6.i3.p1.1),[Hardness Gadgets\.](https://arxiv.org/html/2608.14999#Sx4.SSx1.SSS0.Px3.p1.1),[Gadget Types](https://arxiv.org/html/2608.14999#Sx4.SSx1.p1.1),[Minimal Examples\.](https://arxiv.org/html/2608.14999#Sx4.SSx4.SSS0.Px3.p1.1),[1st item](https://arxiv.org/html/2608.14999#Sx5.I7.i1.p1.1),[3rd item](https://arxiv.org/html/2608.14999#Sx5.I7.i3.p1.1)\.
- Hazraet al\.\(2025\)R\. Hazra, G\. Venturato, P\. Z\. Dos Martires, and L\. De RaedtHave large language models learned to reason? a characterization via 3\-sat\.InSecond Conference on Language Modeling,Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p1.1)\.
- Heyman and Zylberberg \(2025\)A\. Heyman and J\. ZylberbergEvaluating the systematic reasoning abilities of large language models through graph coloring\.CoRRabs/2502\.07087\.Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p2.1)\.
- Ignatievet al\.\(2024\)A\. Ignatiev, Z\. L\. Tan, and C\. KaramanosTowards universally accessible SAT technology\.In27th 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,pp\. 16:1–16:11\.External Links:[Link](https://doi.org/10.4230/LIPIcs.SAT.2024.16),[Document](https://dx.doi.org/10.4230/LIPICS.SAT.2024.16)Cited by:[Implementation Details\.](https://arxiv.org/html/2608.14999#Sx5.SSx4.SSS0.Px1.p1.1)\.
- Inoueet al\.\(2026\)Y\. Inoue, K\. Kawarabayashi, A\. Miyashita, B\. Mohar, and T\. SonobeThree\-edge\-coloring \(tait coloring\) cubic graphs and nowhere\-zero 4\-flow for graphs on the torus\.InProceedings 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\.\),pp\. 6133–6165\.External Links:[Link](https://doi.org/10.1137/1.9781611978971.218),[Document](https://dx.doi.org/10.1137/1.9781611978971.218)Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p1.1)\.
- Jinet al\.\(2024\)B\. Jin, G\. Liu, C\. Han, M\. Jiang, H\. Ji, and J\. HanLarge language models on graphs: a comprehensive survey\.IEEE Transactions on Knowledge and Data Engineering36\(12\),pp\. 8622–8642\.Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p1.1)\.
- Kwonet al\.\(2023\)W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. Gonzalez, H\. Zhang, and I\. StoicaEfficient memory management for large language model serving with pagedattention\.InProceedings 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\.\),pp\. 611–626\.External Links:[Link](https://doi.org/10.1145/3600006.3613165),[Document](https://dx.doi.org/10.1145/3600006.3613165)Cited by:[Implementation Details\.](https://arxiv.org/html/2608.14999#Sx5.SSx4.SSS0.Px1.p1.1)\.
- Matelskyet al\.\(2021\)J\. K\. Matelsky, E\. P\. Reilly, E\. C\. Johnson, J\. Stiso, D\. S\. Bassett, B\. A\. Wester, and W\. Gray\-RoncalDotMotif: an open\-source tool for connectome subgraph isomorphism search and graph queries\.Scientific Reports11\(1\)\.Cited by:[Implementation Details\.](https://arxiv.org/html/2608.14999#Sx5.SSx4.SSS0.Px1.p1.1)\.
- Meta \(2024\)MetaMeta\-llama/llama\-3\.1\-8b\.Hugging Face\.Note:https://huggingface\.co/meta\-llama/Llama\-3\.1\-8BAccessed: 2026\-07\-28Cited by:[Experiments and Results](https://arxiv.org/html/2608.14999#Sx5.p1.1)\.
- Nagdaet al\.\(2026\)A\. Nagda, P\. Raghavan, and A\. ThakurtaReinforced generation of combinatorial structures: ramsey numbers\.CoRRabs/2603\.09172\.Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p4.1)\.
- Novikovet al\.\(2025\)A\. Novikov, N\., M\. Eisenberger, E\. Dupont,et al\.AlphaEvolve: A coding agent for scientific and algorithmic discovery\.CoRRabs/2506\.13131\.External Links:[Link](https://doi.org/10.48550/arXiv.2506.13131),[Document](https://dx.doi.org/10.48550/ARXIV.2506.13131),2506\.13131Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p4.1)\.
- Petersen \(1898\)J\. PetersenSur le théorème de tait\.L’Intermédiaire des Mathématiciens5,pp\. 225–227\.Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p1.1)\.
- Radziszowski \(2026\)S\. RadziszowskiSmall Ramsey Numbers\.Electronic Journal of CombinatoricsDS1,pp\. 1–149\.External Links:[Link](https://www.combinatorics.org/)Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p1.1),[Introduction](https://arxiv.org/html/2608.14999#Sx1.p2.1),[Related Work](https://arxiv.org/html/2608.14999#Sx2.p4.1),[3rd item](https://arxiv.org/html/2608.14999#Sx4.I6.i3.p1.1)\.
- Schaefer \(2001\)M\. SchaeferGraph ramsey theory and the polynomial hierarchy\.Journal of Computer and System Sciences62\(2\),pp\. 290–322\.External Links:[Link](https://doi.org/10.1006/jcss.2000.1729),[Document](https://dx.doi.org/10.1006/JCSS.2000.1729)Cited by:[Determiner Gadgets\.](https://arxiv.org/html/2608.14999#Sx4.SSx1.SSS0.Px1.p1.1),[Hardness Gadgets\.](https://arxiv.org/html/2608.14999#Sx4.SSx1.SSS0.Px3.p1.1),[Gadget Types](https://arxiv.org/html/2608.14999#Sx4.SSx1.p1.1)\.
- Schläfli \(1858\)L\. SchläfliAn 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 Mathematics2,pp\. 110–120\.Cited by:[Introduction](https://arxiv.org/html/2608.14999#Sx1.p1.1)\.
- Sharma \(2025\)A\. SharmaOpenEvolve: an open\-source evolutionary coding agent\.GitHub\.External Links:[Link](https://github.com/algorithmicsuperintelligence/openevolve)Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p4.1)\.
- Srivastavaet al\.\(2026\)G\. Srivastava, A\. S\. Hussain, Z\. Bi, S\. Roy, P\. Pitre, M\. Lu, M\. Ziyadi, and X\. WangBeyondBench: contamination\-resistant evaluation of reasoning in language models\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=mIKqVWGjwI)Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p2.1)\.
- Teamet 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\.CoRRabs/2607\.02770\.Cited by:[Experiments and Results](https://arxiv.org/html/2608.14999#Sx5.p1.1)\.
- Wanget 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 Technology16\(5\),pp\. 1–40\.Cited by:[Related Work](https://arxiv.org/html/2608.14999#Sx2.p1.1)\.
- Yanget 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\.CoRRabs/2505\.09388\.Cited by:[Experiments and Results](https://arxiv.org/html/2608.14999#Sx5.p1.1)\.

## Appendix AAppendix

### 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 BPrompts

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