Reproduce “Re-evaluating LLM-based Heuristic Search: A Case Study on the 3D Packing Problem” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Guorui Quan, Mingfei Sun, Manuel López-Ibáñez
A re-evaluation of LLM-based heuristic search for the 3D Packing Problem reveals that while LLMs excel at optimizing scoring functions within established frameworks, they struggle to invent novel algorithmic structures from scratch, especially for constrained problems. Implementing constraint scaffolding and iterative self-correction significantly improved the success rate of generated heuristics from 10% to 85%, and an LLM-designed scoring function, when integrated into a human-designed metaheuristic, achieved performance competitive with state-of-the-art solvers on the base problem.
Key insights
- LLMs, despite a vast search space, predominantly focus on refining mathematical scoring functions within greedy frameworks, rather than inventing novel, high-level algorithmic structures like 'wall-building'.
- Current LLMs exhibit significant fragility in complex logical and geometric reasoning, necessitating engineering interventions like constraint scaffolding and iterative self-correction to ensure the generation of correct, valid, and efficient code.
- While LLM-generated scoring functions can be powerful as component optimizers, their full potential is realized only when integrated into robust, human-designed algorithmic architectures.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.