Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.11607 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908405438873600 |
|---|---|
| author | Huang, Zixiao Guo, Lifeng Li, Wenhao Sheng, Junjie Shen, Chuyun Chen, Haosheng Jin, Bo Lu, Changhong Wang, Xiangfeng |
| author_facet | Huang, Zixiao Guo, Lifeng Li, Wenhao Sheng, Junjie Shen, Chuyun Chen, Haosheng Jin, Bo Lu, Changhong Wang, Xiangfeng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11607 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | GraphThought: Graph Combinatorial Optimization with Thought Generation Huang, Zixiao Guo, Lifeng Li, Wenhao Sheng, Junjie Shen, Chuyun Chen, Haosheng Jin, Bo Lu, Changhong Wang, Xiangfeng Machine Learning 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. |
| title | GraphThought: Graph Combinatorial Optimization with Thought Generation |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.11607 |