GRASP: Graph Reasoning via Agentic Solving and Probing of LLMs

Integrating graph knowledge into Large Language Models (LLMs) via passive representation faces critical bottlenecks: limited context windows, unreliable numerical computation, and structural hallucinations. To solve this, we propose GRASP (Graph Reasoning via Agentic Solving and Probing), shifting the paradigm from passive ingestion to proactive agentic exploration. By interleaving Neighbor Retrieval for on-demand probing with Code Interpreter as a deterministic solver, GRASP enables LLMs to autonomously navigate and compute over complex topologies. We employ a staged reinforcement learning strategy (GRPO) that transitions from visible tuning to a structure-blind environment, forcing the agent to develop genuine topological awareness. Evaluated on multi-domain graph reasoning benchmarks, our 4B model achieves a 53.06% average performance boost, surpassing SOTA baselines like DeepSeek-V3.2 and successfully generalizing to unseen tasks, with high potential for tackling sampling on million-node graphs and solving Hard-level LeetCode graph problems. Our implementation is open-sourced at https://github.com/PKU-ML/GRASP, with models hosted on Huggingface collection https://huggingface.co/collections/PKU-ML/grasp.

Large language models often struggle with graph reasoning tasks because they passively read graph information instead of actively exploring graph structures. This can lead to reasoning errors and unreliable calculations on complex graphs. We propose GRASP, a framework that enables language models to actively navigate graphs by retrieving neighboring nodes when needed and using code execution for accurate computation. We further train the model with reinforcement learning to encourage genuine structural understanding. Experiments show that GRASP substantially improves graph reasoning performance, generalizes to unseen tasks, and shows strong potential on large-scale graphs and challenging graph algorithm problems.