Can Graph Descriptive Order Affect Solving Graph Problems with LLMs? (2025.acl-long)
Copied to clipboard
| Challenge: | Large language models (LLMs) have achieved significant success in reasoning tasks, including mathematical reasoning and logical deduction. |
| Approach: | They conduct the first comprehensive analysis of how the order of graph descriptions impacts LLM performance. |
| Outcome: | The results show that graph descriptions significantly improve LLMs’ comprehension of graph structures, and the robustness of LLM models to graph description order varies across different tasks. |
Similar Papers
Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation (2026.findings-acl)
Copied to clipboard
| Challenge: | Recent studies focus on performance benchmarks without fully comparing LLMs to graph learning models. |
| Approach: | They evaluate off-the-shelf and instruction-tuned graph learning models across a variety of scenarios. |
| Outcome: | The proposed models outperform traditional graph learning models in few-shot settings, the authors show . their models out perform models with instruction tuning, and they show excellent generalization and robustness. |
GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understanding (2025.acl-long)
Copied to clipboard
| Challenge: | Large language models struggle with comprehending graphical structure information through prompts of graph description sequences, especially as the graph size increases. |
| Approach: | They propose a framework to improve LLMs’ comprehension of both macro- and micro-level graphical information by placing critical graphical data in positions where LLM's exhibit stronger memory performance. |
| Outcome: | The proposed framework outperforms all other graph description methods in understanding graph structures of varying sizes. |
GraphICL: Unlocking Graph Learning Potential in LLMs through Structured Prompt Design (2025.findings-naacl)
Copied to clipboard
| Challenge: | Text-Attributed Graphs (TAGs) are a powerful tool for understanding complex systems and relationships. |
| Approach: | They propose a benchmark to evaluate large language models for graph-structured data using prompts. |
| Outcome: | The proposed benchmark outperforms state-of-the-art graph LLMs and graph neural networks on graph learning tasks without training. |
Mapping the Minds of LLMs: A Graph-Based Analysis of Reasoning LLMs (2025.emnlp-main)
Copied to clipboard
| Challenge: | Large Reasoning Models (LRMs) often display unstable behaviors, e.g., hallucinating unsupported premises, overthinking simple tasks, and displaying higher sensitivity to prompt variations. |
| Approach: | They propose a graph-based analytical framework that clusters long, verbose CoT outputs into semantically coherent reasoning steps, then constructs directed reasoning graphs to capture contextual and logical dependencies among these steps. |
| Outcome: | The proposed framework enables quantitative evaluation of internal reasoning structure and quality beyond conventional metrics and provides practical insights for prompt engineering and cognitive analysis of LLMs. |
Graph-Assisted Large Language Models: A Perspective on Mitigating Intrinsic Limitations (2026.findings-acl)
Copied to clipboard
Haitong Luo, Fali Wang, Weiyao Zhang, Xianren Zhang, Zhiwei Zhang, Tianxiang Zhao, Minhua Lin, Jiahao Zhang, Hui Liu, Xianfeng Tang, Qi He, Suhang Wang, Xuying Meng, Yujun Zhang
| Challenge: | Large language models exhibit intrinsic limitations such as knowledge cutoff, single-threaded reasoning that hinders finer-grained branch and aggregation, and rigid collaboration mechanisms that struggle to coordinate specialized capabilities. |
| Approach: | They propose a taxonomy spanning *Graph-Assisted Knowledge Augmentation*, *Graph Assisted Reasoning and Planning*, and *Graphed LLM Collaboration*. |
| Outcome: | The proposed models show that graphs can augment and correct LLMs and support dynamic coordination among experts and agents in collaborative settings. |
Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks (2026.acl-long)
Copied to clipboard
| Challenge: | Large Language Models (LLMs) have improved reasoning abilities but are limited due to limited context length. |
| Approach: | They propose a large graph benchmark dataset and propose four tasks to evaluate LLMs' reasoning abilities. |
| Outcome: | The proposed tasks evaluate the reasoning abilities of LLMs on a large graph benchmark dataset. |
The Curse of Verbalization: How Presentation Order Constrains LLM Reasoning (2026.findings-eacl)
Copied to clipboard
| Challenge: | Xu et al., 2025) found that LLMs struggle when programs execute in an unaligned order. |
| Approach: | They propose to use esoteric programming languages to evaluate LLMs' reasoning abilities. |
| Outcome: | The proposed model improves reasoning performance across state-of-the-art models by restructuring problems to align the presentation order with the order of utilization. |
Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models (2026.findings-acl)
Copied to clipboard
| Challenge: | Graph problems require reasoning over explicit structure, permutation invariance, and computationally complex relationships, creating a mismatch with the representations of text-based models. |
| Approach: | They propose a human-interpretable structural encoding strategy that injects graph structure directly into natural language prompts. |
| Outcome: | The proposed method improves performance on synthetic and real-world datasets. |
Are LLMs Truly Graph-Savvy? A Comprehensive Evaluation of Graph Generation (2025.acl-srw)
Copied to clipboard
| Challenge: | Large language models have demonstrated impressive capabilities across diverse tasks . however, their ability to generate valid graph structures remains underexplored . |
| Approach: | They evaluate large language models on five specialized graph generation tasks . they also test the models using 3 different prompt types: direct, iterative feedback, and program-augmented. |
| Outcome: | The proposed models solve twice as many tasks as general-purpose models, compared to their general-usage peers. |
GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets (2025.findings-naacl)
Copied to clipboard
| Challenge: | Large language models (LLMs) have demonstrated significant capabilities in processing and understanding text data. |
| Approach: | They propose a structure-based instruction-based method to enhance LLM performance on complex graph tasks. |
| Outcome: | The proposed framework outperforms open-source models on graph problem-solving, but the gap is narrowing. |