Generative Exploration via Stochastic Inference in Monte Carlo Tree Search for Automatic Heuristic Design

Large language models (LLMs) enable automatic heuristic design (AHD) without manually specified program grammars, but their generated heuristics and evaluation outcomes are highly variable. Existing search methods often treat these noisy observations as deterministic fitness values, which encourages premature exploitation of fragile candidates. We introduce GENESIS, an uncertainty-aware Monte Carlo Tree Search framework for LLM-based AHD. GENESIS represents concrete heuristics and generation operators in a shared search tree, maintains Normal--Inverse--Gamma posterior beliefs over their performance, and uses hierarchical Thompson sampling to select both promising heuristics and useful transformation operators. It further applies Assumption-Guided Reflective Expansion (AGRE), a structured reflection process that identifies brittle assumptions, constructs counterfactual failures, and produces assumption-conditioned refinements. Experiments across multiple combinatorial optimization settings evaluate the effects of uncertainty-aware search and structured reflection on automatic heuristic discovery.