Efficient Test-time Inference for Generative Planning Models with OCL Search

Generative models have emerged as a powerful paradigm for AI planning, yet their performance remains constrained by the training data distribution. One approach is to improve generated solutions during inference by scaling test-time compute. A more efficient alternative is to optimize the inference process itself. In this paper, we show that a modified version of a classical Open-Closed List (OCL) search provides just such an efficient inference procedure. Our algorithm synergizes two learned components: a generative model that performs fast rollouts from intermediate states and a heuristic model that prioritizes among candidate reasoning paths. Key contributions include novel exploration control mechanisms and integration of learned models within the OCL framework. Across multiple combinatorial planning domains, our approach outperforms both neurosymbolic search baselines and classical solvers in computational efficiency and solution quality.

When an AI solves planning puzzles — like rearranging blocks or navigating a maze — its quality is limited by its training data. One fix is to generate many candidate solutions and pick the best, but this is computationally expensive. We introduce OCLGen, which makes the search process itself smarter instead. It combines two learned components: a generative model that quickly sketches candidate plans, and a second model that judges which partial plans are worth exploring further. The key idea is to systematically revisit plans at all stages of completion, rather than over-committing to one promising-looking path. Tested on four challenging planning domains, OCLGen finds shorter, higher-quality plans faster than competing methods. When its own solutions become new training data in a self-improvement loop, it achieves optimal plans on 100% of Blocksworld problems and 94.7% of Sokoban problems.