mlsanityData to 14 Oct 2026

GraphThought: Graph Combinatorial Optimization with Thought Generation

arXiv 2502.11607 ↗First posted 17 Feb 2025cs.LGcited by 9

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Graph combinatorial optimization (GCO) problems are central to domains like logistics and bioinformatics. While traditional solvers dominate, large language models (LLMs) offer new possibilities for structured reasoning, yet struggle with complex GCO tasks requiring rigorous combinatorial analysis and multi-step deduction, often producing hallucinated steps. We first formalize the Optimal Thoughts Design (OTD) problem, which provides a structured guidance for producing high-quality intermediate reasoning steps. Building on this formulation, we introduce GraphThought, a novel framework that generates effective reasoning sequences through either heuristic-guided forward search or solver-aligned backward reasoning. By fine-tuning LLMs on these structured thought sequences, we develop Llama-GT, an 8B-parameter model that achieves state-of-the-art performance on the GraphArena benchmark, outperforming significantly larger models like DeepSeek-V3. Our results demonstrate that when scaffolded with structured reasoning priors, principled thought generation can significantly enhance LLM performance on GCO tasks without requiring increased model scale.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 50 of its 89 references that are in the map. First posted on arXiv 17 Feb 2025.

Builds on

50 of 89 references.

Closest ancestors · 7

Same direction, newest first

  1. 2024Thinking LLMs: General Instruction Following with Thought Generation14 Oct
  2. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithms28 May
  3. 2024Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping21 Feb
  4. 2024Demystifying Chains, Trees, and Graphs of Thoughts25 Jan
  5. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Models18 Aug
  6. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Models21 Mar
  7. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 43

  1. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  2. 2022Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agentscited by 1,035
  3. 2023Large Language Models Cannot Self-Correct Reasoning Yetcited by 1,017
  4. 2022STaR: Bootstrapping Reasoning With Reasoningcited by 940
  5. 2022Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoningcited by 334
  6. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 274
  7. 2023Can Language Models Solve Graph Problems in Natural Language?cited by 252
  8. 2023GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarkingcited by 210
  9. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 192
  10. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 176
  11. 2022Language Models of Code are Few-Shot Commonsense Learnerscited by 160
  12. 2024Stream of Search (SoS): Learning to Search in Languagecited by 145
31 more
  1. 2022Language Models as Agent Modelscited by 132
  2. 2024Let Your Graph Do the Talking: Encoding Structured Data for LLMscited by 118
  3. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Modelcited by 107
  4. 2024A Survey of Large Language Models for Graphscited by 72
  5. 2019WIQA: A dataset for "What if..." reasoning over procedural textcited by 71
  6. 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capabilitycited by 58
  7. 2020Learning Dynamic Belief Graphs to Generalize on Text-Based Gamescited by 49
  8. 2024GraphArena: Evaluating and Exploring Large Language Models on Graph Computationcited by 49
  9. 2024Can LLM Graph Reasoning Generalize beyond Pattern Memorization?cited by 47
  10. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 42
  11. 2023LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?cited by 40
  12. 2024GLBench: A Comprehensive Benchmark for Graph with Large Language Modelscited by 36
  13. 2023Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysiscited by 35
  14. 2024GITA: Graph to Visual and Textual Integration for Vision-Language Graph Reasoningcited by 33
  15. 2021Learning Knowledge Graph-based World Models of Textual Environmentscited by 31
  16. 2024ProG: A Graph Prompt Learning Benchmarkcited by 29
  17. 2024Self-Guiding Exploration for Combinatorial Problemscited by 22
  18. 2024Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challengescited by 21
  19. 2024Scalable and Accurate Graph Reasoning with LLM-based Multi-Agentscited by 21
  20. 2024GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understandingcited by 18
  21. 2024Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Modelscited by 17
  22. 2024GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Modelscited by 13
  23. 2024GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaborationcited by 12
  24. 2024Beyond Graphs: Can Large Language Models Comprehend Hypergraphs?cited by 11
  25. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Pathcited by 10
  26. 2024Can LLMs perform structured graph reasoning?cited by 9
  27. 2024Eyeballing Combinatorial Problems: A Case Study of Using Multimodal Large Language Models to Solve Traveling Salesman Problemscited by 8
  28. 2024Lost-in-Distance: Impact of Contextual Proximity on LLM Performance in Graph Taskscited by 8
  29. 2024Graph Reasoning with Large Language Models via Pseudo-code Promptingcited by 6
  30. 2024GUNDAM: Aligning Large Language Models with Graph Understandingcited by 5
  31. 2024Exploring Graph Structure Comprehension Ability of Multimodal Large Language Models: Case Studiescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 6.

9 papers.

  1. 2025Large Language Models as End-to-end Combinatorial Optimization Solverscited by 28
  2. 2026Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimizationcited by 9
  3. 2025Large Language Models in Operations Research: Methods, Applications, and Challengescited by 6
  4. 2025NPG-Muse: Scaling Long Chain-of-Thought Reasoning with NP-Hard Graph Problemscited by 5
  5. 2026GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoningcited by 2
  6. 2026An Agentic AI Framework with Large Language Models and Chain-of-Thought for UAV-Assisted Logistics Scheduling with Mobile Edge Computingcited by 1
  7. 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospectscited by 0
  8. 2026GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMscited by 0
  9. 2026GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubricscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures
  2. 2025Improving LLMs' Generalized Reasoning Abilities by Graph Problems
  3. 2026RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning
  4. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought
  5. 2025Multi-chain Graph Refinement and Selection for Reliable Reasoning in Large Language Models
  6. 2025ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention
  7. 2026Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization
  8. 2025Rethinking and Benchmarking Large Language Models for Graph Reasoning