A new benchmark says today's large language models still can't reliably build even small mathematical graphs.
Researchers introduced RamseyGadgets, a dataset of 70 graph construction problems drawn from Ramsey theory, built so solutions are small enough (at most 10 vertices) to be checked automatically with SAT solvers. The problems are deliberately obscure spins on Ramsey-good graphs - constructions that avoid specific monochromatic subgraphs - chosen precisely because they are underexplored, so models can't just recall a textbook answer. The team tested five open-source LLMs and found none topped 37.70% accuracy on the hardest tier of problems. The dataset is designed to expand easily, since swapping which subgraphs are banned generates a fresh set of problems.
Math benchmarks for LLMs are increasingly compromised by models that have memorized known constructions from training data rather than reasoning them out. By digging into underexplored corners of Ramsey theory, RamseyGadgets tries to isolate genuine problem-solving from recall - a distinction that matters as labs tout reasoning gains on benchmarks like GSM8K or MATH that are now thoroughly picked over. A sub-40% success rate on a purpose-built benchmark suggests graph construction reasoning remains a real weak spot, even for models that do well on competition math.
The researchers also tested giving models hints, which is a quiet admission that without help, these systems are still closer to guessing than proving.