# Self-Guiding Exploration for Combinatorial Problems

arXiv: https://arxiv.org/abs/2405.17950 · HTML: https://mlsanity.com/paper/2405.17950/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 28 May 2024.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [LaMDA: Language Models for Dialog Applications](https://mlsanity.com/paper/2201.08239/) (2022)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Automatic Chain of Thought Prompting in Large Language Models](https://mlsanity.com/paper/2210.03493/) (2022)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Decomposed Prompting: A Modular Approach for Solving Complex Tasks](https://mlsanity.com/paper/2210.02406/) (2022)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Applying Deep Learning to the Newsvendor Problem](https://mlsanity.com/paper/1607.02177/) (2016)
- [Exploring Combinatorial Problem Solving with Large Language Models: A Case Study on the Travelling Salesman Problem Using GPT-3.5 Turbo](https://mlsanity.com/paper/2405.01997/) (2024)

## Built on by (most cited first, 22 of 22)

- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges](https://mlsanity.com/paper/2506.15196/) (2025)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Generalizable Heuristic Generation Through LLMs with Meta-Optimization](https://mlsanity.com/paper/2505.20881/) (2025)
- [Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimization](https://mlsanity.com/paper/2408.12214/) (2024)
- [ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization](https://mlsanity.com/paper/2602.22465/) (2026)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems](https://mlsanity.com/paper/2510.16701/) (2025)
- [Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation](https://mlsanity.com/paper/2511.10233/) (2025)
- [DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization](https://mlsanity.com/paper/2601.06502/) (2026)
- [Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization](https://mlsanity.com/paper/2602.01090/) (2026)
- [SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problem](https://mlsanity.com/paper/2505.21887/) (2025)
- [ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention](https://mlsanity.com/paper/2506.11052/) (2025)
- [OptiHive: Ensemble Selection for LLM-Based Optimization via Statistical Modeling](https://mlsanity.com/paper/2508.02503/) (2025)
- [Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2603.27169/) (2026)
- [General Intelligence-based Fragmentation (GIF): A framework for peak-labeled spectra simulation](https://mlsanity.com/paper/2511.09571/) (2025)
- [Large Language Models as Amortized Pareto-Front Generators for Constrained Bi-Objective Convex Optimization](https://mlsanity.com/paper/2605.12106/) (2026)
- [Large Language Models as Optimizers: A Survey of Direct vs. Tool-Augmented Approaches and Their Performance Frontiers](https://mlsanity.com/paper/2606.15577/) (2026)
- [Privacy from Symmetry: Orthogonally Equivariant Transformers for LLM Inference](https://mlsanity.com/paper/2606.16461/) (2026)
- [From Hand-Crafted to LLM-Based Variation Operators in Metaheuristics: A Tutorial](https://mlsanity.com/paper/2609.31649/) (2026)
- [VLM Fine-Tuning for End-to-End Combinatorial Optimization](https://mlsanity.com/paper/2609.37175/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have become pivotal in addressing reasoning tasks across diverse domains, including arithmetic, commonsense, and symbolic reasoning. They utilize prompting techniques such as Exploration-of-Thought, Decomposition, and Refinement to effectively navigate and solve intricate tasks. Despite these advancements, the application of LLMs to Combinatorial Problems (CPs), known for their NP-hardness and critical roles in logistics and resource management remains underexplored. To address this gap, we introduce a novel prompting strategy: Self-Guiding Exploration (SGE), designed to enhance the performance of solving CPs. SGE operates autonomously, generating multiple thought trajectories for each CP task. It then breaks these trajectories down into actionable subtasks, executes them sequentially, and refines the results to ensure optimal outcomes. We present our research as the first to apply LLMs to a broad range of CPs and demonstrate that SGE outperforms existing prompting strategies by over 27.84% in CP optimization performance. Additionally, SGE achieves a 2.46% higher accuracy over the best existing results in other reasoning tasks (arithmetic, commonsense, and symbolic).