GraphARC: A Comprehensive Benchmark for Graph-Based Abstract Reasoning

# GraphARC: A Comprehensive Benchmark for Graph-Based Abstract Reasoning
Source: [https://arxiv.org/html/2605.31031](https://arxiv.org/html/2605.31031)
\(2026\)

###### Abstract\.

Relational reasoning lies at the heart of intelligence, but existing benchmarks are typically confined to formats such as grids or text\. We introduce*GraphARC*, a benchmark for abstract reasoning on graph\-structured data\. GraphARC generalizes the few\-shot transformation learning paradigm of the Abstraction and Reasoning Corpus \(ARC\)\. Each task requires inferring a transformation rule from a few input\-output pairs and applying it to a new test graph, covering local, global, and hierarchical graph transformations\. Unlike grid\-based ARC, GraphARC instances can be generated at scale across diverse graph families and sizes, enabling systematic evaluation of generalization abilities\. We evaluate state\-of\-the\-art language models on GraphARC and observe clear limitations\. Models can answer questions about graph properties but often fail to solve the full graph transformation task, revealing a comprehension\-execution gap\. Performance further degrades on larger instances, exposing scaling barriers\. More broadly, by combining aspects of node classification, link prediction, and graph generation within a single framework, GraphARC provides a promising testbed for future graph foundation models\.

few\-shot, abstract reasoning, graph, scalability, benchmark, ARC, reasoning models, compositional generalization

††journalyear:2026††copyright:cc††conference:Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.2; August 09–13, 2026; Jeju Island, Republic of Korea††booktitle:Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\.2 \(KDD ’26\), August 09–13, 2026, Jeju Island, Republic of Korea††doi:10\.1145/3770855\.3817591††isbn:979\-8\-4007\-2259\-2/2026/08††ccs:Mathematics of computing Graph theory††ccs:Computing methodologies Logical and relational learning††ccs:Computing methodologies Rule learning††ccs:Computing methodologies Natural language processing
Figure 1\.Two examples of GraphARC tasks demonstrating few\-shot abstract reasoning on graphs\. Each task presents two input\-output graph pairs \(top row and middle row\) that illustrate a transformation rule, followed by a test input graph where the learned rule must be applied\. In the example on the left\-hand side, the transformation rule colors the shortest path connecting two colored nodes \(shown in blue\)\. This task is constrained to tree structures to ensure a unique shortest path between any two nodes\. The example on the right\-hand side shows a task where edges between nodes of different colors are removed\.## 1\.Introduction

Relational reasoning—the ability to perceive and reason about relationships between objects—is a core aspect of intelligence\(Hummel and Holyoak,[2003](https://arxiv.org/html/2605.31031#bib.bib24); Halfordet al\.,[2010](https://arxiv.org/html/2605.31031#bib.bib21)\)\. This capacity underlies many forms of higher cognition: we use it to appreciate analogies across different domains\(Holyoak,[2012](https://arxiv.org/html/2605.31031#bib.bib22)\), to understand and learn language\(Pinker,[1998](https://arxiv.org/html/2605.31031#bib.bib25)\), and generally, to apply abstract rules to novel situations\(Smithet al\.,[1992](https://arxiv.org/html/2605.31031#bib.bib23)\)\. Achieving this kind of generalization is a central challenge for artificial intelligence\(Chollet,[2019](https://arxiv.org/html/2605.31031#bib.bib1); Lakeet al\.,[2017](https://arxiv.org/html/2605.31031#bib.bib32)\)\.

The Abstraction and Reasoning Corpus \(ARC\)\(Chollet,[2019](https://arxiv.org/html/2605.31031#bib.bib1)\)is a widely recognized benchmark for evaluating abstract reasoning in AI\. ARC consists of grid\-based visual puzzles that require systems to learn and apply transformation rules based on a few examples\. While ARC puzzles are grid\-based, many of the underlying rules are relational—grouping identical objects, replicating subpatterns, or propagating attributes to neighboring objects\. To capture such a structure more directly, we propose to use graphs as a more general representation that is not tied to a particular spatial layout\.

Inspired by ARC, we introduce*GraphARC*, a benchmark for few\-shot abstract reasoning on graphs\. Each task includes 2\-3 input\-output graph pairs demonstrating a transformation rule, and a test input where the rule should be applied\. See[Figure1](https://arxiv.org/html/2605.31031#S0.F1)for an example\. The transformations are based on fundamental graph primitives: local structure \(degree, neighborhoods, cliques\), reachability \(connected components, isolated nodes\), or hierarchical relations \(closest common ancestor in a tree\)\. The transformations can be color\-based \(changing the color of some nodes\) and structural modifications, adding or removing nodes and edges\. The instances are automatically generated across diverse graph families and sizes, providing a virtually unlimited supply of instances\. This setup allows testing whether models can generalize the same transformation across graphs of varying size and structure\.

GraphARC combines elements of traditional graph learning tasks, including node classification\(Kipf and Welling,[2017](https://arxiv.org/html/2605.31031#bib.bib26)\), graph classification\(Yinget al\.,[2018](https://arxiv.org/html/2605.31031#bib.bib27)\), link prediction\(Zhang and Chen,[2018](https://arxiv.org/html/2605.31031#bib.bib28)\), and graph generation\(Simonovsky and Komodakis,[2018](https://arxiv.org/html/2605.31031#bib.bib29)\)within a single framework\. Given the absence of broadly applicable Graph Foundation Models \(GFMs\)\(Liuet al\.,[2025](https://arxiv.org/html/2605.31031#bib.bib30); Wanget al\.,[2025](https://arxiv.org/html/2605.31031#bib.bib31)\), we focus on evaluating Large Language Models \(LLMs\) that can process textual representations of graphs\. To this end, we systematically test a range of encoding schemes and prompting choices\. We also design two complementary evaluation pipelines for LLMs: one that measures performance on full graph transformation tasks, and another that uses targeted questions about properties of the input and output graph\. This allows us to disentangle a model’s ability to understand the transformation from its ability to execute it\.

Concretely, GraphARC provides

1. \(1\)a scalable task generation framework that produces diverse graph transformation challenges across multiple graph families at arbitrary scales,
2. \(2\)a comprehensive evaluation methodology for LLMs, and
3. \(3\)an extensive analysis of current LLM performance, revealing significant gaps in structural understanding and identifying key failure modes that highlight directions for future research\.

Our code is available on Github\.111[https://github\.com/sakupeltonen/graph\-arc](https://github.com/sakupeltonen/graph-arc)

## 2\.Related work

#### The Abstraction and Reasoning Corpus\.

The ARC challenge, introduced byChollet \([2019](https://arxiv.org/html/2605.31031#bib.bib1)\), established a paradigm for few\-shot abstract reasoning in which systems infer transformation rules from minimal input–output examples and apply them to new cases\. Despite intensive effort, performance hovered near 33% for years before recent breakthroughs: top open\-source entries in the ARC Prize combined neural reasoning with programmatic search to reach roughly 53% accuracy\. At the same time, OpenAI’s o3 attained 75\.7% on ARC\-AGI\-1\(ARC Prize Foundation,[2024a](https://arxiv.org/html/2605.31031#bib.bib35),[b](https://arxiv.org/html/2605.31031#bib.bib9)\)\. However, the release of ARC\-AGI\-2\(Cholletet al\.,[2025](https://arxiv.org/html/2605.31031#bib.bib33)\)in March 2025 largely reset the field, with frontier systems scoring about 16% versus human performance near 60%, underscoring that robust abstract reasoning remains open\. Crucially for our setting, leading ARC solvers are tailored to grid\-based vision puzzles and often rely on specialized pipelines or substantial compute, making direct application to GraphARC’s relational, graph\-structured I/O unnecessary or impractical\. Accordingly, we evaluate general\-purpose LLMs on GraphARC’s textual graph encodings to probe abstract relational reasoning without bespoke ARC\-specific machinery\.

The impact of ARC has led to several extensions exploring different modalities and task formulations\.\(Xuet al\.,[2023](https://arxiv.org/html/2605.31031#bib.bib3)\)created 1D\-ARC tasks specifically for language model evaluation\.Assouelet al\.\([2022](https://arxiv.org/html/2605.31031#bib.bib20)\)developed Arith\-MNIST, containing reasoning tasks where models must infer arithmetic programs applied to colored digits\. In this challenge, the output is a single digit containing the answer, rather than a transformed grid\.

#### Large Language Models and Graph Reasoning\.

Recent work has explored applying LLMs to graph reasoning tasks with mixed results\.Fatemiet al\.\([2024](https://arxiv.org/html/2605.31031#bib.bib4)\)explores various textual representations and their impact on LLM performance across different reasoning tasks\.Wanget al\.\([2023](https://arxiv.org/html/2605.31031#bib.bib5)\)examines whether language models can solve graph problems such as connectivity, cycle existence, and bipartite matching, when graphs are described in text\.

Daiet al\.\([2024](https://arxiv.org/html/2605.31031#bib.bib13)\)evaluate how LLMs understand graph patterns through tasks such as detection, translation, and modification, with patterns specified in natural language or as edge lists\. This work is arguably the most similar to our work, but it focuses on reasoning about predefined motifs, whereas we target few\-shot learning and the application of general graph transformations\. Beyond inputting graphs in text,Zhaoet al\.\([2023](https://arxiv.org/html/2605.31031#bib.bib34)\)introduces GIMLET, using a customized positional encoding to integrate language models with graph\-structured data for molecule property prediction\.Sanfordet al\.\([2024](https://arxiv.org/html/2605.31031#bib.bib41)\)investigates how well transformers can solve graph\-based reasoning problems at various model sizes\. While they do not use natural language to represent the graphs, they do show that transformers can solve graph problems they are trained on\. See\(Jinet al\.,[2024](https://arxiv.org/html/2605.31031#bib.bib10)\)for a comprehensive survey on LLMs for graph problems\.

Chain\-of\-thought prompting \(or test\-time compute\) has emerged as an effective way to improve reasoning abilities in language models\(Weiet al\.,[2022](https://arxiv.org/html/2605.31031#bib.bib18); Snellet al\.,[2025](https://arxiv.org/html/2605.31031#bib.bib43); Mirtaheriet al\.,[2025](https://arxiv.org/html/2605.31031#bib.bib42)\)\. We will investigate this by using closed\- and open\-source models with reasoning abilities, such as OpenAI’s o3\-mini and DeepSeek’s R1\.

#### Graph Foundation Models\.

GFMs are an emerging class of models aimed at general\-purpose graph reasoning\. These approaches seek to combine GNN\-style structural inductive biases with the broad knowledge and few\-shot learning of foundation models\(Liuet al\.,[2023](https://arxiv.org/html/2605.31031#bib.bib6)\)\. Initial efforts have targeted specific domains, such as knowledge graphs\(Galkinet al\.,[2024](https://arxiv.org/html/2605.31031#bib.bib39)\)and molecular graphs\(Méndez\-Lucioet al\.,[2024](https://arxiv.org/html/2605.31031#bib.bib40)\)\. See\(Liuet al\.,[2025](https://arxiv.org/html/2605.31031#bib.bib30)\)for a survey outlining the opportunities and challenges\.

Notably, Google Research has announced a relational GFM that treats databases as graphs and generalizes to unseen tables, reporting up to 40x precision gains on tasks like spam detection\. Despite rapid progress, current GFMs largely target standard supervised objectives \(node/graph classification, link prediction\)\(Liuet al\.,[2023](https://arxiv.org/html/2605.31031#bib.bib6),[2025](https://arxiv.org/html/2605.31031#bib.bib30); Wanget al\.,[2025](https://arxiv.org/html/2605.31031#bib.bib31)\), and cannot be straightforwardly adapted to solve ARC style questions\. Accordingly, we do not benchmark GFMs here; instead, GraphARC serves as a complementary proving ground for future GFMs that claim abstract, few\-shot graph transformation capabilities\.

## 3\.GraphARC

Table 1\.GraphARC transformations\. The tasks are grouped into color\-based transformations and structural transformations\.![Refer to caption](https://arxiv.org/html/2605.31031v1/x1.png)Figure 2\.The GraphARC task generation and evaluation pipeline for LLMs\. A task begins with a formal rule \(e\.g\., “color all degree\-3 nodes blue”\), which is used to generate and textually encode a set of input\-output graph examples\. The pipeline then diverges into two distinct evaluation pathways: 1\) TheFull Output Path \(blue arrows\)requires the model to generate the complete transformed graph, testing both its ability to infer the rule and execute it correctly\. 2\) TheQuestion\-Based Path \(green arrows\)isolates comprehension by asking targeted questions about the input graph and the inferred output properties, disentangling understanding from execution\. Solid arrows represent stages where analysis or transformations occur, while dashed arrows indicate the flow of data without modification\.### 3\.1\.Benchmark Definition

A GraphARC task consists of 2\-3 input\-output graph pairs that demonstrate a transformation rule\. This is followed by a test input graph, where the learned rule must be applied\. See[Figure1](https://arxiv.org/html/2605.31031#S0.F1)for an example task\.

Formally, graphs are represented as a tupleG=\(V,E\)G=\(V,E\)where nodes have unique integer identifiers from0to\|V\|−1\|V\|\-1\. Node IDs remain consistent within each task instance\. Each nodev∈Vv\\in Vcarries a color attribute, with grey as the default color\. We assume the graphs to be undirected\.

GraphARC contains 21 distinct transformations\. A task is an instance of a transformation\. We can generate multiple tasks per transformation by varying transformation parameters, size and family of the graphs, and the number of examples\. Furthermore, by varying the test graph size, we can evaluate how well models generalize transformations to larger instances\. Each transformation is designed to test a specific aspect of graph reasoning, such as local structure \(e\.g\., degree\-based coloring\), reachability \(connected components, paths\), or hierarchical relations \(e\.g\., common ancestors in trees\)\.

#### Transformations\.

See Table[1](https://arxiv.org/html/2605.31031#S3.T1)for the list of transformations\. We organize GraphARC transformations into two main categories: color\-based transformations and structure modification transformations\. Color\-based tasks modify node colors based on structural properties, whereas structure modification tasks alter the graph topology\. A complete task specification includes:

- •Transformation rule:The operation to be performed \(e\.g\., “color all degree\-3 nodes blue”\)\.
- •Required Properties:A list of preconditions the input graph must satisfy for the transformation to be meaningful\. For instance, the “colorDegree3” task requires the input graph to have at least one node of degree 3\. This prevents the generation of trivial examples where the transformation has no effect\.
- •Parameters:Configurable elements of the transformation, such as the target color or degree number\.
- •Pre\-transformation Steps:Initial modifications to the input graph to set up the reasoning problem\. For example, the “colorNeighbors” task first colors a random node orange, and the model must then infer the rule to color all of its neighbors blue\.

#### Graph Generation and Validation

We generate graphs from multiple families, including Erdős\-Rényi, Watts\-Strogatz, trees, star, bipartite, and multi\-component\. This ensures diversity in structural properties, and also allows us to test whether models can learn transformations that generalize across different graph types\.

The number of examples and their size is varied according to size patterns \(see Appendix[A\.2](https://arxiv.org/html/2605.31031#A1.SS2)\)\. In the main dataset, we use small graphs with 5 to 15 nodes in both the examples and the test input\. In the scaling dataset, we fix example graphs at 10 nodes, while testing on larger graphs up to 250 nodes\. This allows us to evaluate how well models can generalize transformations to larger instances\.

To ensure that generated tasks are valid and solvable, we implement a property\-validation system that checks whether the generated graphs satisfy necessary conditions for the transformation to be applied\. It is also important that the combination of input examples should uniquely determine the simplest consistent transformation\. Our system uses a three\-state framework \(True/False/Maybe\) indicating whether a generator guarantees, precludes, or conditionally satisfies the required properties, enabling efficient rejection of invalid instances\. We also set the input graph size to be large enough to make the probability of multiple valid, simple transformations negligible\. Full details appear in Appendix[A](https://arxiv.org/html/2605.31031#A1)\.

### 3\.2\.LLM Evaluation Pipeline

[Figure2](https://arxiv.org/html/2605.31031#S3.F2)illustrates our task generation and evaluation pipeline\. It consists of four parts\. The first part consists of choosing a transformation \(Stage 1\), and generating graphs and validating the examples \(Stage 2\), as detailed above\. These two are independent of the evaluation of LLMs and are used to generate the task instances\. The last two stages are specific to the evaluation of LLMs\.

#### Stage 3: Encoding and Prompt Assembly

We implement two textual encoding schemes for presenting graphs to language models: adjacency list format \(enumerate edges\) and incidence list format \(list of neighbors by node\)\.[Figure2](https://arxiv.org/html/2605.31031#S3.F2)illustrates the adjacency list format and an example incidence list can be found in[AppendixB](https://arxiv.org/html/2605.31031#A2)\.

We also test the effect of different system prompts\. These encourage different approaches to the task, such as a graph analyst studying examples, a graph algorithm developer analyzing patterns, or a mathematics teacher explaining the pattern\. We also include a baseline with no system prompt\. See Appendix[B](https://arxiv.org/html/2605.31031#A2)for a full description of these variations\.

To achieve a fine\-grained analysis of model capabilities, a single set of generated examples is used to create prompts for two complementary evaluation paths\.

#### Stage 4 \(Full Output Path\):

This pathway assesses a model’s ability to infer the transformation rule from the examples and apply it to generate the complete output graph for a new input\. The model’s response is parsed to reconstruct the output graph’s structure and node colors\. This reconstructed graph is then compared to the ground\-truth output graph\. The model’s output must be an exact match, verified via a graph isomorphism check \(this is fast for labeled graphs\)\.

#### Stage 4 \(Question\-Based Path\):

This pathway is designed to disentangle a model’s comprehension of graph properties from its ability to execute a full transformation\. Instead of requesting the full output graph, the prompt poses a targeted question about a specific property\. Crucially, we ask parallel questions about both the visible test input \(e\.g\., How many blue nodes are in the input?”\) and the unseen, to\-be\-inferred output \(e\.g\., How many blue nodes will be in the output?”\)\. The model’s response, typically a numerical or categorical answer, is compared against the ground\-truth value, which is computed from the actual input or output graphs\. This pathway allows for a more granular diagnosis of failures, helping to distinguish between a failure to parse the input, a failure to understand the transformation, or a failure to reason about the output\.

## 4\.Experiments and Results

### 4\.1\.Dataset and Models

We evaluate a range of state\-of\-the\-art AI systems to provide comprehensive coverage of reasoning capabilities, including Qwen3 \(1\.7B to 32B\), DeepSeek R1, OpenAI’s reasoning models o1\-mini, o3\-mini, o4\-mini, and GPT 5 \(all with medium reasoning effort\), and GPT 4\.1\-nano as a direct\-answer baseline\.

There are two regimes in the dataset: \(i\) our*main experiments*, which span a range of tasks under multiple prompts and encoding variations, and \(ii\)*scaling experiments*, which assess performance as graph size increases\. In the main experiments, we use small graphs,n∈\{5,10,15\}n\\in\\\{5,10,15\\\}for both the example and test graphs\. In the scaling experiments, examples are fixed atn=10n=10, while test inputs range up ton=250n=250withn∈\{10,25,50,100,250\}n\\in\\\{10,25,50,100,250\\\}\.

The total number of evaluations per model results from combining different encodings, prompt variants, size patterns, transformations, and question types\. After filtering by task\-generator compatibility, for Qwen3 models and GPT 4\.1\-nano, this gives around 18k evaluations each, while reasoning models—restricted to a single prompt—cover a proportionally smaller set\. The scaling dataset adds 4\.4k evaluations for reasoning models\.

### 4\.2\.Results

![Refer to caption](https://arxiv.org/html/2605.31031v1/Figures/01_combined_model_performance.png)Figure 3\.Overall model performance on GraphARC\. Bars show accuracy for full\-output tasks \(structured graph generation\) and for question\-based tasks, split into questions about the*input*\(visible graph\) and the*output*\(inferred graph\)\. For most models, we observe a comprehension–execution gap \(question\-based\>\>full\-output\) and an input–output asymmetry \(input\>\>output\)\. Reasoning models consistently outperform direct\-answer baselines\.Table 2\.Accuracy on full\-output tasks across a subset of the tested models\. Values are mean accuracies, and bold highlights the best score per row\. Tasks are ordered by increasing average difficulty\. Appendix[C](https://arxiv.org/html/2605.31031#A3)shows results and confidence intervals for all models\.[Figure3](https://arxiv.org/html/2605.31031#S4.F3)reveals a stark performance hierarchy in full graph generation tasks\. The Qwen3 series shows clear scaling with model size \(8\.3% for 1\.7B to 41\.4% for 14B\), while reasoning models achieve substantially higher performance \(57\.5% for o1\-mini to 90\.9% for GPT 5\)\. GPT 4\.1\-nano achieves only 13\.3% accuracy, performing similarly to the smallest Qwen3 model\.

Models are substantially better in question\-answering tasks compared to full graph generation\. This gap is most pronounced in smaller models,Qwen3 1\.7Bachieves 54\.4% on questions but only 8\.3% on full outputs \(6\.55x difference\), whileQwen3 8Bshows 72\.2% vs 30\.5% \(2\.36x difference\)\. Even frontier models exhibit this pattern: o4\-mini achieves 91\.2% on questions versus 86\.5% on full outputs\. Models consistently perform better on questions about input graphs \(which they can see\) than output graphs \(which they must infer\)\. For example,Qwen3 8Bhas an accuracy of 89\.2% on input questions versus 65\.1% on output questions\.

#### Task\-Specific Performance\.

The task\-level performance in[Table2](https://arxiv.org/html/2605.31031#S4.T2)shows a wide range of difficulty across tasks\. Some transformations, such asaddHub,colorDegree1, andcolorNeighbors, are consistently solved with high accuracy\. In contrast, others, includingremoveDegree3,colorEquidistant, andcolorDegree3, remain challenging even for the strongest models\. Global transformations likebipartitionCompletionandmergeAtBlueexemplify the architectural divide between model families\. Only reasoning models achieve meaningful performance \(≥75%\\geq 75\\%\), while all Qwen3 models and GPT 4\.1\-nano fail almost completely\. See Appendix[C](https://arxiv.org/html/2605.31031#A3)for full results across all models\.

#### Scaling Limitations\.

Table 3\.Performance by size pattern \(full output; aggregated across tasks\)\. The first two columns indicate the example and test graph sizes \(in nodes\), and the third column gives the number of evaluated samples\. Values are accuracies, with the best\-performing model for each pattern in bold\. The first two rows correspond to main dataset patterns; the last five rows to scaling patterns\.Table 4\.Task performance by scaling pattern\. Cells are accuracies averaged over selected models \(GPT\-5, o1\-mini, o3\-mini, and o4\-mini\)\. Column headers show the example graph sizes \(before the arrow\) and the test graph size \(after the arrow\)\.Table 5\.Performance by question type \(question\-based; input vs\. output\)\. Values are accuracies; bold indicates the best model per question for input and for output\.[Table3](https://arxiv.org/html/2605.31031#S4.T3)summarizes performance across size patterns\. The results reveal a performance drop as test graph size increases, particularly for o1\-mini and o3\-mini\. For instance, o1\-mini’s accuracy declines from 88% at 10 nodes to just 18% at 250 nodes, suggesting a limit in working memory or attention mechanisms\. In contrast, GPT 5 maintains robust performance, achieving 91% accuracy even at 250 nodes\. The scaling dataset patterns \(last five rows\) were only evaluated on reasoning models, as direct\-answer models struggled even on the smallest graphs\.

Looking across tasks,[Table4](https://arxiv.org/html/2605.31031#S4.T4)shows a consistent decline in accuracy when increasing the test graph size\. The steepest drops are observed in tasks involving degree\-based deletions or colorings\. For example,removeDegree3falls from 96% accuracy at 10 nodes to just 25% at 250 nodes, and similar patterns are seen forcolorDegree2,3\. Surprisingly, some tasks with more global structure, such ascolorPathandcolorComponents, exhibit stronger robustness, remaining near\-perfect up to 100 nodes and only degrading at the largest size\. Some simpler local modifications, such asaddHubandremoveDegree1, also show relatively stable performance compared to their higher\-degree counterparts\. These results highlight that scaling difficulties are not purely a function of locality: global transformations can scale well, while seemingly local ones can collapse under larger graphs, suggesting problems in how the models internalize and apply structural rules\.

#### Performance in Question\-Based Tasks\.

Besides full graph generation, we also test model understanding with targeted questions, which isolate comprehension of graph properties from execution of transformations\. Table[5](https://arxiv.org/html/2605.31031#S4.T5)shows question\-based performance for selected models and question types\. In general, it is easier for models to answer questions about input graphs than output graphs\. The gap between high input accuracy and substantially lower output accuracy highlights that even when models can recognize graph properties, they struggle to learn the transformation or cannot apply it to new graphs reliably\. See Appendix[C](https://arxiv.org/html/2605.31031#A3), Table[7](https://arxiv.org/html/2605.31031#A3.T7)for full results across all models and question types\.

We also observe a systematic bias in reasoning models: when asked about input graphs, they often answer as if the question referred to the output graph instead\. Advanced reasoning models show dramatically higher transfer rates, indicating they apply transformations even when not requested\. The strength of this effect correlates positively with model capability: GPT 5: 55–85%, O4\-mini: 45–75%, O3\-mini: 40–70%, Qwen3 models:<20<20%\. It is most pronounced in tasks with many coloring changes \(bipartitionCompletionandblueSubgraph\), and weakest in structural modifications \(addHubandremoveDegree\)\.

#### Effect of Graph Encoding

Encoding choice has little average impact \(performance ratio near 1\.0 for most models\), though preferences vary by model and task type\. Most differences are minor, but Qwen3\-4b is a clear outlier: for full output tasks, it achieves 31\.7% better performance with incident encoding \(0\.407 vs\. 0\.309\), while for question\-based tasks, it performs 24\.7% better with adjacency encoding \(0\.735 vs\. 0\.589\)\. Overall, encoding effects appear minor on average but can be important for particular model\-task combinations\.

### 4\.3\.Case Study: Failure Modes of GPT 5

We manually analyzed the answers for GPT 5 on full output tasks\. We observe that errors generally fall into the four categories: Output parsing mismatches, Threshold misinterpretation, Concept substitution, and Encoding sensitivity\.

#### \(1\) Output parsing mismatches\.

In some cases the model description of the solution matched the intended subgraph, but the output failed to parse correctly and was marked wrong\.

> “I can’t share step\-by\-step reasoning, but the task is to take the induced subgraph on the colored nodes and list only edges between those colored nodes\.” <answer\>G describes a graph among nodes 4, 11 …</answer\>

*Takeaway:*The semantics were correct, but formatting \(e\.g\. edge listing or section tags\) caused evaluation failure\.

#### \(2\) Threshold misinterpretation\.

Tasks requiring the coloring or removal of nodes of degreexx\(e\.g\. 3\) led to conflicting rules: sometimes interpreted as “degree exactly 3,” and sometimes as “degree at least 3\.” The examples were unambiguous, since in at least one case a node of degree four was present but left untouched, clearly indicating that the rule was “degree exactly 3\.”

> “…removes all nodes with degree 3 or more …” “…remove every node with degree exactly 3 …” “I identify and color the node\(s\) with the highest degree \(most connections\)\.”

*Takeaway:*Even when the examples uniquely determined the threshold, the model occasionally chose a looser interpretation \(“≥3\\geq 3”\) instead of the intended exact one\.

#### \(3\) Concept substitution\.

Sometimes, the model substituted the intended property with a different but superficially related graph concept\. For example:

> “…identified the articulation points \(cut vertices\) …”

*Takeaway:*Instead of following the intended rule, the model sometimes defaulted to alternative structural notions that seemed plausible in one of the examples\.

#### \(4\) Encoding sensitivity\.

Usually the two encoding formats \(adjacency list vs\. incidence list\) yielded similar results\. However, in some cases, particularly tasks involving distance\-based reasoning and paths, the model succeeded under one encoding but failed under the other\.

> “…find the unique shortest path between them\. Color the path’s center node red and also color any neighbors of that center …” “…red if and only if it is equidistant to both blue seeds; ties occur at nodes 11, 10, 9, 8, 5, 7, 4, 6, 3\.”

*Takeaway:*The correct reasoning was present, but the execution depended on encoding format\.

## 5\.Discussion

Our results reveal three insights about graph reasoning in language models\. First, we observe a persistent*comprehension–execution gap*: models can parse structural properties and answer questions about them with high accuracy, but often fail to apply transformations consistently, highlighting that recognition of graph features is easier than generating coherent transformed outputs\. This mirrors findings in other domains where transformers succeed at local operations but fail to compose them into globally consistent solutions\(Dziriet al\.,[2023](https://arxiv.org/html/2605.31031#bib.bib19)\)\.

Secondly, scaling barriers emerge even for strong models\. Mid\-tier reasoning models collapse between 50–100 nodes, while GPT 5 maintains robust performance up to 250 nodes yet still struggles on seemingly local tasks such as degree\-based transformations\. This shows that scaling difficulty is not tied purely to locality but to how reliably models internalize and generalize transformation rules\.

Thirdly, we observe a*paradox of capability*: more advanced models increasingly apply transformations even when not asked, answering questions about the input graphs as if they referred to the output\. This “transformation bias” indicates that instruction following can degrade with capability, creating a failure mode where models over\-apply their reasoning ability\. This phenomenon has been observed in other contexts where highly capable models “overthink” simple tasks\(Weiet al\.,[2022](https://arxiv.org/html/2605.31031#bib.bib18)\)or exhibit “inverse scaling” behaviors\(McKenzieet al\.,[2023](https://arxiv.org/html/2605.31031#bib.bib17)\)\.

### 5\.1\.Comparison with Grid\-Based ARC

GraphARC reveals complementary challenges to the original ARC benchmark:

#### Task Structure\.

While ARC uses fixed small grids with visual patterns, GraphARC tests relational reasoning without spatial constraints\. The absence of visual cues forces models to rely purely on structural understanding\. The graph\-based format allows us to automatically generate a virtually unlimited variety of instances\.

#### Interpretability\.

Our decomposition into question types provides clearer failure analysis than ARC’s binary success/failure\. We can identify specific capabilities \(input understanding, output understanding, and transformation execution\) and trace failure modes to particular reasoning steps\.

#### Scaling\.

While ARC uses fixed small grids, our scalable approach reveals performance degradation patterns with size, exposing architectural limitations that remain hidden in fixed\-size evaluations\. GraphARC’s ability to automatically generate large test cases allows controlled evaluation of scaling behavior and identification of failure thresholds across models\.

#### Human vs\. AI Focus\.

ARC was conceived as a human\-intelligence challenge that is solvable for people but difficult for machines\. Its grid layout provides visual cues that humans naturally exploit\. In contrast, GraphARC is designed as an AI benchmark: the underlying graph structure is presented without spatial layout, since models should not depend on visualization but on reasoning over the graph’s relational properties\. Informal testing confirms that GraphARC tasks \(for example those in[Figure1](https://arxiv.org/html/2605.31031#S0.F1)\) are easily solvable by humans, but this relies on having access to an appropriate graph visualization\.

## 6\.Conclusion and Future Work

GraphARC provides a new benchmark for studying few\-shot abstract reasoning on graphs\. By generating diverse input\-output transformations across graph families and sizes, it exposes systematic limitations of current language models that remain hidden in standard reasoning benchmarks\.

Our evaluation of over 125,000 responses identifies three consistent phenomena: \(1\) a comprehension\-execution gap where models can recognize graph properties but fail to reliably apply transformations, \(2\) scaling barriers that cause mid\-tier models to collapse beyond 50\-100 nodes, and \(3\) a paradoxical failure mode where more capable models over\-apply transformations, even when not requested\.

We see two promising directions for future work\. First, GraphARC can serve as a testbed for models explicitly designed for relational reasoning, including graph neural networks and emerging graph foundation models\. Second, the benchmark invites new training strategies that move toward compositional generalization, such as curriculum design, modular reasoning approaches, or hybrid symbolic\-neural methods\.

By making failure modes transparent and scalable, GraphARC aims to guide the development of systems that can reason robustly over structured data—a necessary step toward broader abstract reasoning capabilities\.

## References

- ARC Prize Foundation \(2024a\)2024 progress on arc\-agi\-pub\.Note:[https://arcprize\.org/blog/2024\-progress\-arc\-agi\-pub](https://arcprize.org/blog/2024-progress-arc-agi-pub)Accessed: 2025\-09\-01Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px1.p1.1)\.
- ARC Prize Foundation \(2024b\)OpenAI o3 breakthrough high score on arc\-agi\-pub\.Note:[https://arcprize\.org/blog/oai\-o3\-pub\-breakthrough](https://arcprize.org/blog/oai-o3-pub-breakthrough)Accessed: 2025\-01\-01Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px1.p1.1)\.
- R\. Assouel, P\. Rodriguez, P\. Taslakian, D\. Vazquez, and Y\. Bengio \(2022\)Object\-centric compositional imagination for visual abstract reasoning\.InICLR2022 Workshop on the Elements of Reasoning: Objects, Structure and Causality,Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px1.p2.1)\.
- F\. Chollet, M\. Knoop, G\. Kamradt, B\. Landers, and H\. Pinkard \(2025\)Arc\-agi\-2: a new challenge for frontier ai reasoning systems\.arXiv preprint arXiv:2505\.11831\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px1.p1.1)\.
- F\. Chollet \(2019\)On the measure of intelligence\.arXiv preprint arXiv:1911\.01547\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p1.1),[§1](https://arxiv.org/html/2605.31031#S1.p2.1),[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px1.p1.1)\.
- X\. Dai, H\. Qu, Y\. Shen, B\. Zhang, Q\. Wen, W\. Fan, D\. Li, J\. Tang, and C\. Shan \(2024\)How do large language models understand graph patterns? a benchmark for graph pattern comprehension\.arXiv preprint arXiv:2410\.05298\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p2.1)\.
- N\. Dziri, X\. Lu, M\. Sclar, X\. L\. Li, L\. Jiang, B\. Y\. Lin, P\. West, C\. Bhagavatula, R\. Le Bras, J\. D\. Hwang, S\. Sanyal, S\. Welleck, X\. Ren, A\. Ettinger, Z\. Harchaoui, and Y\. Choi \(2023\)Faith and fate: limits of transformers on compositionality\.InProceedings of the 37th International Conference on Neural Information Processing Systems,NIPS ’23,Red Hook, NY, USA\.Cited by:[§5](https://arxiv.org/html/2605.31031#S5.p1.1)\.
- B\. Fatemi, J\. Halcrow, and B\. Perozzi \(2024\)Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p1.1)\.
- M\. Galkin, J\. Zhou, B\. Ribeiro, J\. Tang, and Z\. Zhu \(2024\)A foundation model for zero\-shot logical query reasoning\.Advances in Neural Information Processing Systems37,pp\. 54137–54160\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px3.p1.1)\.
- G\. S\. Halford, W\. H\. Wilson, and S\. Phillips \(2010\)Relational knowledge: the foundation of higher cognition\.Trends in cognitive sciences14\(11\),pp\. 497–505\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p1.1)\.
- K\. J\. Holyoak \(2012\)13 analogy and relational reasoning\.The Oxford handbook of thinking and reasoning,pp\. 234\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p1.1)\.
- J\. E\. Hummel and K\. J\. Holyoak \(2003\)A symbolic\-connectionist theory of relational inference and generalization\.\.Psychological review110\(2\),pp\. 220\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p1.1)\.
- B\. Jin, G\. Liu, C\. Han, M\. Jiang, H\. Ji, and J\. Han \(2024\)Large language models on graphs: a comprehensive survey\.IEEE Trans\. on Knowl\. and Data Eng\.36\(12\),pp\. 8622–8642\.External Links:ISSN 1041\-4347,[Link](https://doi.org/10.1109/TKDE.2024.3469578),[Document](https://dx.doi.org/10.1109/TKDE.2024.3469578)Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p2.1)\.
- T\. N\. Kipf and M\. Welling \(2017\)Semi\-supervised classification with graph convolutional networks\.In5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24\-26, 2017, Conference Track Proceedings,External Links:[Link](https://openreview.net/forum?id=SJU4ayYgl)Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p4.1)\.
- B\. M\. Lake, T\. D\. Ullman, J\. B\. Tenenbaum, and S\. J\. Gershman \(2017\)Building machines that learn and think like people\.Behavioral and brain sciences40,pp\. e253\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p1.1)\.
- J\. Liu, C\. Yang, Z\. Lu, J\. Chen, Y\. Li, M\. Zhang, T\. Bai, Y\. Fang, L\. Sun, P\. S\. Yu,et al\.\(2023\)Towards graph foundation models: a survey and beyond\.arXiv preprint arXiv:2310\.11829\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px3.p1.1),[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px3.p2.1)\.
- J\. Liu, C\. Yang, Z\. Lu, J\. Chen, Y\. Li, M\. Zhang, T\. Bai, Y\. Fang, L\. Sun, P\. S\. Yu,et al\.\(2025\)Graph foundation models: concepts, opportunities and challenges\.IEEE Transactions on Pattern Analysis and Machine Intelligence\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p4.1),[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px3.p1.1),[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px3.p2.1)\.
- I\. R\. McKenzie, A\. Lyzhov, M\. Pieler, A\. Parrish, A\. Mueller, A\. Prabhu, E\. McLean, A\. Kirtland, A\. Ross, A\. Liu,et al\.\(2023\)Inverse scaling: when bigger isn’t better\.arXiv preprint arXiv:2306\.09479\.Cited by:[§5](https://arxiv.org/html/2605.31031#S5.p3.1)\.
- O\. Méndez\-Lucio, C\. A\. Nicolaou, and B\. Earnshaw \(2024\)MolE: a foundation model for molecular graphs using disentangled attention\.Nature Communications15\(1\),pp\. 9431\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px3.p1.1)\.
- P\. Mirtaheri, E\. Edelman, S\. Jelassi, E\. Malach, and E\. Boix\-Adsera \(2025\)Let me think\! a long chain\-of\-thought can be worth exponentially many short ones\.arXiv preprint arXiv:2505\.21825\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p3.1)\.
- S\. Pinker \(1998\)Words and rules\.Lingua106\(1\-4\),pp\. 219–242\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p1.1)\.
- C\. Sanford, B\. Fatemi, E\. Hall, A\. Tsitsulin, M\. Kazemi, J\. Halcrow, B\. Perozzi, and V\. Mirrokni \(2024\)Understanding transformer reasoning capabilities via graph algorithms\.Advances in Neural Information Processing Systems37,pp\. 78320–78370\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p2.1)\.
- M\. Simonovsky and N\. Komodakis \(2018\)Graphvae: towards generation of small graphs using variational autoencoders\.InInternational conference on artificial neural networks,pp\. 412–422\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p4.1)\.
- E\. E\. Smith, C\. Langston, and R\. E\. Nisbett \(1992\)The case for rules in reasoning\.Cognitive science16\(1\),pp\. 1–40\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p1.1)\.
- C\. V\. Snell, J\. Lee, K\. Xu, and A\. Kumar \(2025\)Scaling llm test\-time compute optimally can be more effective than scaling parameters for reasoning\.InThe Thirteenth International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p3.1)\.
- H\. Wang, S\. Feng, T\. He, Z\. Tan, X\. Han, and Y\. Tsvetkov \(2023\)Can language models solve graph problems in natural language?\.Advances in Neural Information Processing Systems36,pp\. 30840–30861\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p1.1)\.
- Z\. Wang, Z\. Liu, T\. Ma, J\. Li, Z\. Zhang, X\. Fu, Y\. Li, Z\. Yuan, W\. Song, Y\. Ma,et al\.\(2025\)Graph foundation models: a comprehensive survey\.arXiv preprint arXiv:2505\.15116\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p4.1),[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px3.p2.1)\.
- J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, B\. Ichter, F\. Xia, E\. H\. Chi, Q\. V\. Le, and D\. Zhou \(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.InProceedings of the 36th International Conference on Neural Information Processing Systems,NIPS ’22,Red Hook, NY, USA\.External Links:ISBN 9781713871088Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p3.1),[§5](https://arxiv.org/html/2605.31031#S5.p3.1)\.
- Y\. Xu, W\. Li, P\. Vaezipoor, S\. Sanner, and E\. B\. Khalil \(2023\)Llms and the abstraction and reasoning corpus: successes, failures, and the importance of object\-based representations\.arXiv preprint arXiv:2305\.18354\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px1.p2.1)\.
- Z\. Ying, J\. You, C\. Morris, X\. Ren, W\. Hamilton, and J\. Leskovec \(2018\)Hierarchical graph representation learning with differentiable pooling\.Advances in neural information processing systems31\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p4.1)\.
- M\. Zhang and Y\. Chen \(2018\)Link prediction based on graph neural networks\.Advances in neural information processing systems31\.Cited by:[§1](https://arxiv.org/html/2605.31031#S1.p4.1)\.
- H\. Zhao, S\. Liu, M\. Chang, H\. Xu, J\. Fu, Z\. Deng, L\. Kong, and Q\. Liu \(2023\)Gimlet: a unified graph\-text model for instruction\-based molecule zero\-shot learning\.Advances in neural information processing systems36,pp\. 5850–5887\.Cited by:[§2](https://arxiv.org/html/2605.31031#S2.SS0.SSS0.Px2.p2.1)\.

## Appendix AInstance Generation Framework

### A\.1\.Graph Generators

We employ multiple graph generators to ensure comprehensive coverage of structural patterns:

- •Random: Erdős\-RényiG​\(n,p\)G\(n,p\)model with edge probabilityp=0\.3p=0\.3
- •Connected: Watts\-Strogatz small\-world graphs \(guaranteed connected\)
- •Trees: Generated by extracting a BFS spanning tree from a connected Watts–Strogatz small\-world graph
- •Star: Center node connected ton−1n\-1leaves
- •Bipartite: Two\-partition graphs with random inter\-partition edges
- •Multi\-Component: Exactly 2 disconnected components

### A\.2\.Size Patterns

Size patterns control how few\-shot learning occurs by varyingboth the number of examples and their size\. We design two pattern groups to isolate different learning challenges:

Main Dataset Patterns\(varying number of examples\):

- •scale\_up\_3\[5, 10, 15\]: Test on 15\-node graph after seeing a 5\-node and a 10\-node example
- •scale\_up\_4\[5, 10, 15, 15\]: Test on 15\-node graph after seeing a 5\-node, a 10\-node, and a 15\-node example

Scaling Dataset Patterns\(testing final graph size\):

- •cap10\_3\[10, 10, 10\]: Baseline with all 10\-node graphs
- •cap25\_3\[10, 10, 25\]: Test on 25\-node graph after seeing two 10\-node examples
- •cap50\_3\[10, 10, 50\]: Test on 50\-node graph after 2 10\-node examples
- •cap100\_3\[10, 10, 100\]: Test on 100\-node graph after seeing two 10\-node examples
- •cap250\_3\[10, 10, 250\]: Test on 250\-node graph after seeing two 10\-node examples

### A\.3\.Property validation system

To ensure task validity and meaningful evaluation, we implement a comprehensive property validation system\. Each task declares required graph properties \(e\.g\., connectivity, specific degree distributions\), and our generation pipeline validates that produced graphs satisfy these constraints\.

The validation system uses a three\-state property framework:

- •TRUE: Property is guaranteed by the generator
- •FALSE: Property is incompatible with the generator
- •MAYBE: Property may or may not hold depending on random generation

This framework enables efficient validation by skipping guaranteed properties and immediately rejecting incompatible generator\-transformation combinations\. Additionally, we verify that each transformation produces well\-defined transformations on the example graphs, ensuring that the learning problem is neither trivial nor ill\-posed\.

## Appendix BExperimental Design for LLM Evaluation

This section outlines how we evaluate GraphARC on language models\. We test the models separately on the full output and question\-based pathways\. We also test the effect of graph encoding schemes and system prompts on model performance\.

### B\.1\.Graph Encoding Schemes

Graph structures must be converted to text for language model processing\. We implement two encoding schemes that emphasize different structural properties:

Adjacency List Format: This encoding lists all edges as node pairs\. It may facilitate reasoning about paths and global properties\. An example encoding for a path graph is shown below:

> In an undirected graph, \(i,j\) means that node i and node j are connected with an undirected edge\. G describes a graph among nodes 0, 1, 2, 3, 4\. The edges in G are: \(0,1\) \(1,2\) \(2,3\) \(3,4\)\. The following nodes are colored: 1, 2, 3\.

Incidence List Format: This encoding lists all nodes in the immediate neighborhood for each node\. Degree and local transformation based tasks may benefit from this format\.

> G describes a graph among nodes 0, 1, 2, 3, 4\. In this graph: Node 0 is connected to nodes 1\. Node 1 is connected to nodes 0, 2\. Node 2 is connected to nodes 1, 3\. Node 3 is connected to nodes 2, 4\. Node 4 is connected to nodes 3\. The following nodes are colored: 1, 2, 3\.

### B\.2\.System Prompt Variation

We experiment with 3 different system prompts that frame the task from different professional perspectives, as well as a baseline with no system prompt\.Analystemphasizes systematic analysis,Programmerinvokes algorithmic thinking, andTeacherencourages explanation\. The full prompts are shown below:

System prompts show minimal and inconsistent effects across models\. Most models vary less than 5% between prompts, with no prompt consistently outperforming others\. Qwen3\-4b again shows highest sensitivity \(up to 23\.8% variation\), but the pattern is model\-specific rather than systematic\. Notably, the “none” baseline equals or exceeds role\-based prompts several times, suggesting that explicit role assignment may interfere with models’ natural reasoning strategies for abstract tasks\.

## Appendix CFull results

Table 6\.Accuracy on full\-output tasks across models\. Values are mean accuracies with 95% confidence intervals \(computed usingscipy\.stats\.bootstrapwith percentile method\)\.

Table 7\.Performance on question\-based tasks on the input and output graphs across models\. Values are mean accuracies\.