Research map / Large language models / Agents, code and math
Self-Guiding Exploration for Combinatorial Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Self-Guiding Exploration (SGE), an autonomous general-purpose prompting strategy that explores multiple heuristic trajectories, decomposes them into subtasks, executes and refines them, and integrates them, applied to combinatorial problems and reasoning benchmarks.
Problem
LLMs have been little studied on NP-hard combinatorial problems (assignment, knapsack, bin packing, TSP, VRP, job scheduling), where direct prompting and existing prompting strategies give poor solutions as problem size grows.
Approach
A single general-purpose, task-agnostic prompting loop that combines exploration-of-thought, decomposition, and self-refinement, with recursive sub-calls for complex subtasks, so the model autonomously selects heuristics per CP without task-specific exemplars.
Key results
- On CP tasks with GPT-4, SGE achieves 41.33% (assignment) to 75.33% (JSP) cost improvement over IO, outperforming Decomposition by a margin of 7.53% to 37.13%.
- On eight reasoning datasets with GPT-4 plus code interpreter, SGE averages 89.60% accuracy vs 86.43% for Decomposition prompting.
- SGE uses 87.89% more function calls than Decomposition while achieving 27.84% better CP performance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SGE instead of Decomposition | GPT-4 on Assignment Problem · Assignment Problem | performance improvement vs IO (%): 33.80 -> 41.33 | Helped |
| Use SGE instead of Decomposition | GPT-4 on Knapsack · Knapsack | performance improvement vs IO (%): 51.95 -> 70.39 | Helped |
| Use SGE instead of Decomposition | GPT-4 on Bin Packing · Bin Packing | performance improvement vs IO (%): 39.57 -> 74.72 | Helped |
| Use SGE instead of Decomposition | GPT-4 on TSP · TSP | performance improvement vs IO (%): 38.49 -> 72.10 | Helped |
| Use SGE instead of Decomposition | GPT-4 on VRP · VRP | performance improvement vs IO (%): 36.73 -> 71.92 | Helped |
| Use SGE instead of Decomposition | GPT-4 on Job Scheduling · Job Scheduling | performance improvement vs IO (%): 38.20 -> 75.33 | Helped |
| Use SGE instead of Decomposition | GPT-4 on reasoning tasks · Reasoning tasks average | accuracy: 86.43 -> 89.60 | Helped |
| Increase problem size from 5 to 20 nodes | SGE with GPT-4 · Assignment Problem | performance improvement vs IO (%): 44.05 -> 40.24 | Hurt |
| Increase problem size from 5 to 20 nodes | SGE with GPT-4 · Knapsack | performance improvement vs IO (%): 75.94 -> 67.21 | Hurt |
| Increase problem size from 5 to 20 nodes | SGE with GPT-4 · Bin Packing | performance improvement vs IO (%): 90.92 -> 69.78 | Hurt |
| Increase problem size from 5 to 20 nodes | SGE with GPT-4 · TSP | performance improvement vs IO (%): 76.77 -> 67.14 | Hurt |
| Increase problem size from 5 to 20 nodes | SGE with GPT-4 · VRP | performance improvement vs IO (%): 80.47 -> 65.19 | Hurt |
Surprising findings
- Llama-2 70B and 7B perform similarly on CPs, suggesting model size alone does not improve combinatorial performance.
- Bigger problem sizes generally reduce SGE's improvement over IO, indicating diminishing gains with scale.
Limitations
- Performance depends on the choice of underlying LLM; only models with code interpreters perform well.
- Higher operational cost, with 87.89% more function calls than Decomposition.
- Performance gains shrink as problem size grows.
Experimental setup
Datasets: AQUA GSM8K SVAMP ASDiv StrategyQA CSQA ARC LastLetter
Benchmarks: AQUA GSM8K SVAMP ASDiv StrategyQA CSQA ARC LastLetter six combinatorial problem tasks (assignment, knapsack, bin packing, TSP, VRP, JSP)
Metrics: percentage cost improvement vs IO optimality gap vs OR-Tools optimum accuracy function call count
Baselines: IO prompting Chain-of-Thought Self-Refine Decomposition prompting
Builds on: Chain-of-Thought Self-Refine Decomposition prompting Tree-of-Thoughts
Closest papers by meaning
- MARGE: Improving Math Reasoning with Guided Exploration (ICML 2025 · similarity 0.89)
- On the self-verification limitations of large language models on reasoning and planning tasks (ICLR 2025 · similarity 0.89)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.88)
- Boosting of Thoughts: Trial-and-Error Problem Solving with Large Language Models (ICLR 2024 · similarity 0.88)
- Chain of Thoughtlessness? An Analysis of CoT in Planning (NeurIPS 2024 · similarity 0.88)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.