mlsanityData to 7 Oct 2026

Self-Guiding Exploration for Combinatorial Problems

arXiv 2405.17950 ↗First posted 28 May 2024cs.AIcited by 21

On the map: LLM reasoning → Mathematical reasoning

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).

Key facts. Cited by 21 papers in the map (data through 7 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.

Builds on

25 of 45 references.

References · 25

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2022Training language models to follow instructions with human feedbackcited by 15,712
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  5. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  6. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  7. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  8. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,317
  9. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  10. 2022Emergent Abilities of Large Language Modelscited by 2,483
  11. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Themcited by 1,767
  12. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
13 more
  1. 2022LaMDA: Language Models for Dialog Applicationscited by 1,218
  2. 2015Pointer Networkscited by 882
  3. 2022Automatic Chain of Thought Prompting in Large Language Modelscited by 684
  4. 2018Attention, Learn to Solve Routing Problems!cited by 646
  5. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  6. 2022Decomposed Prompting: A Modular Approach for Solving Complex Taskscited by 554
  7. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  8. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 266
  9. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  10. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  11. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 133
  12. 2016Applying Deep Learning to the Newsvendor Problemcited by 24
  13. 2024Exploring Combinatorial Problem Solving with Large Language Models: A Case Study on the Travelling Salesman Problem Using GPT-3.5 Turbocited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 12; 2026: 8.

21 papers.

Sort:

By area:

  1. 2025Large Language Models as End-to-end Combinatorial Optimization Solverscited by 27
  2. 2025HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimizationcited by 19
  3. 2025HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challengescited by 19
  4. 2025GraphThought: Graph Combinatorial Optimization with Thought Generationcited by 9
  5. 2024Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimizationcited by 8
  6. 2025Generalizable Heuristic Generation Through LLMs with Meta-Optimizationcited by 7
  7. 2026ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimizationcited by 6
  8. 2025An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problemscited by 5
  9. 2025Large Language Models in Operations Research: Methods, Applications, and Challengescited by 4
  10. 2025Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptationcited by 3
  11. 2026DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimizationcited by 3
  12. 2026Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimizationcited by 3
9 more
  1. 2025SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problemcited by 2
  2. 2025ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attentioncited by 1
  3. 2025OptiHive: Ensemble Selection for LLM-Based Optimization via Statistical Modelingcited by 1
  4. 2026Aligning LLMs with Graph Neural Solvers for Combinatorial Optimizationcited by 1
  5. 2025General Intelligence-based Fragmentation (GIF): A framework for peak-labeled spectra simulationcited by 0
  6. 2026Large Language Models as Amortized Pareto-Front Generators for Constrained Bi-Objective Convex Optimizationcited by 0
  7. 2026Large Language Models as Optimizers: A Survey of Direct vs. Tool-Augmented Approaches and Their Performance Frontierscited by 0
  8. 2026Privacy from Symmetry: Orthogonally Equivariant Transformers for LLM Inferencecited by 0
  9. 2026VLM Fine-Tuning for End-to-End Combinatorial Optimizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Combinatorial Reasoning: Selecting Reasons in Generative AI Pipelines via Combinatorial Optimization
  2. 2026Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization
  3. 2024Self-Explore: Enhancing Mathematical Reasoning in Language Models with Fine-grained Rewards
  4. 2024Expanding Search Space with Diverse Prompting Agents: An Efficient Sampling Approach for LLM Mathematical Reasoning
  5. 2025LLM-First Search: Self-Guided Exploration of the Solution Space
  6. 2025Advancing Multi-Step Mathematical Reasoning in Large Language Models through Multi-Layered Self-Reflection with Auto-Prompting
  7. 2025MARGE: Improving Math Reasoning for LLMs with Guided Exploration
  8. 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks