New Benchmark Reveals LLM Weaknesses in Graph Reasoning

Evaluating the true reasoning capabilities of large language models (LLMs) is challenging due to the risk of data contamination in fixed test sets. This paper introduces ClosureBench, a new benchmark designed to overcome this by generating unique test instances on demand. Each task's correct answer is verified by executing a program in the Ein tensor-logic language, ensuring objective ground truth. ClosureBench covers 26 task categories across three compositional levels and allows control over difficulty through graph size, edge density, and query depth. The researchers tested various models, from 1.5B open-source models to frontier systems like GPT-4.1 and Gemini 2.5. Key findings include a significant performance gap between seen and fresh instances for models fine-tuned on fixed sets, highlighting memorization over true reasoning. Accuracy consistently drops as graph size and query depth increase, even for the strongest models, which often misinterpret natural language graph descriptions before reasoning. Interestingly, a 4B model fine-tuned to emit executable programs rather than direct answers performed significantly better, maintaining accuracy across compositional levels and approaching frontier model performance at a fraction of the token cost. This suggests program synthesis is a promising avenue for robust compositional reasoning.