Research map / Large language models / Retrieval and knowledge
Can Language Models Solve Graph Problems in Natural Language?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Build-a-Graph instruction to CoT | text-davinci-003 · Cycle | accuracy: 66.75 -> 72.44 | Helped |
| Add algorithm description to CoT | text-davinci-003 · Cycle | accuracy: 66.75 -> 71.78 | Helped |
| Add Build-a-Graph instruction to CoT | text-davinci-003 · Shortest Path | accuracy: 51.51 -> 55.76 | Helped |
| Add algorithm description to CoT | text-davinci-003 · Shortest Path | accuracy: 51.51 -> 51.66 | No clear effect |
| Add Build-a-Graph instruction to CoT | text-davinci-003 · Hamilton Path | accuracy: 24.00 -> 22.34 | Hurt |
| Add algorithm description to CoT | text-davinci-003 · Hamilton Path | accuracy: 24.00 -> 22.09 | Hurt |
| Use few-shot exemplars instead of zero-shot prompting | text-davinci-003 · Hamilton Path and Bipartite Graph Matching | accuracy: 1.00% to 10.48% | Hurt |
| Increase the number of in-context exemplars | text-davinci-003 · Hamilton Path | accuracy | Hurt |
| Use CoT or CoT+SC instead of simpler prompting on complex graph tasks | text-davinci-003 · Topological Sort and Maximum Flow | accuracy | Hurt |
| Use CoT instead of zero-shot prompting | text-davinci-003 · GNN simulation | partial credit: 13.61 -> 64.55 | Helped |
| Apply ordinary connectivity prompting to chain-structured queries | text-davinci-003 · Connectivity chain subset | average accuracy: 78.40 -> 54.83 | Hurt |
| Apply ordinary connectivity prompting to clique queries | text-davinci-003 · Connectivity clique subset | average accuracy: 78.40 -> 71.00 | Hurt |
Closest papers by meaning
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.91)
- GraphArena: Evaluating and Exploring Large Language Models on Graph Computation (ICLR 2025 · similarity 0.90)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.90)
- $\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- Can Graph Learning Improve Planning in LLM-based Agents? (NeurIPS 2024 · similarity 0.89)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.