analiza aiqbench
This study introduces RamseyGadgets, a dataset of 70 underexplored graph construction problems designed specifically to evaluate the reasoning capabilities of large language models in mathematical contexts. By using SAT solvers for verification and focusing on tasks difficult to memorize from training data, the research reveals that current open-source LLMs struggle significantly, achieving only about 38% accuracy on hard-tier problems despite their growing utility in mathematics. The findings highlight a critical gap between generative AI's ability to recall known solutions and its capacity for genuine novel reasoning within formal logic domains.
RamseyGadgets: A Graph Construction Dataset for LLMs
arXiv:2608.14999v1 Announce Type: new 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.
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.
Computation and Language (cs.CL); Artificial Intelligence (cs.AI)
arXiv:2608.14999 [cs.CL]
(or arXiv:2608.14999v1 [cs.CL] for this version)
https://doi.org/10.48550/arXiv.2608.14999 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 340 cuvinte
Subiecte conexe
Are Large Language Models Effective Knowledge Graph Constructors?
arXiv · 28 aug. 2026
Three perspectives on corrigibility - shards, simulators, singular learning
LessWrong · 16 oct. 2026
Relation-Aware Graph Foundation Model
arXiv · 30 sept. 2026
From Lab to Reality: A Practical Evaluation of Deep Learning Models and LLMs for Vulnerability Detection
arXiv · 19 aug. 2026