GraphThought: Graph Combinatorial Optimization with Thought Generation
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning
GraphScout trains LLMs to autonomously synthesize structured training data from knowledge graphs via flexible exploration tools, enabling a 4B model to outperform larger LLMs by 16.7% on average with fewer inference t...
-
Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization
NLCO benchmark shows LLMs achieve reasonable feasibility on small natural-language CO tasks but degrade on larger instances, with set-based problems easier than graph-structured or bottleneck-objective ones.
-
An Agentic AI Framework with Large Language Models and Chain-of-Thought for UAV-Assisted Logistics Scheduling with Mobile Edge Computing
An agentic AI framework with LLMs generates formulations for coupled UAV product collection and MEC task scheduling, solved by hierarchical PPO that reaches 99.6% collection success and 100% deadline compliance in sim...
-
Are Large Language Models Suitable for Graph Computation? Progress and Prospects
A survey of LLMs for graph computation introduces a role-based taxonomy of executors versus planners and concludes that current models suit simple small-scale tasks but remain unreliable for large-scale exact computation.
-
Large Language Models for Operations Research: A Comprehensive Survey
A survey compiling roles, applications, benchmarks, challenges, and future directions for large language models in operations research.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.