Tree-Structured Synergy of Large Language Models and Bayesian Optimization for Efficient CASH

Technical Summary: Tree-Structured Synergy of Large Language Models and Bayesian Optimization for Efficient CASH

Problem Statement
The paper addresses the Combined Algorithm Selection and Hyperparameter Optimization (CASH) problem, which aims to jointly identify the optimal machine learning algorithm and its hyperparameters to maximize validation performance. While Bayesian Optimization (BO) is the dominant approach for CASH, it struggles with cold-start issues and high-dimensional, structured search spaces because it treats configurations as abstract numeric vectors, failing to incorporate prior knowledge. Conversely, Large Language Models (LLMs) offer semantic priors and reasoning capabilities but suffer from poor generalization in high-dimensional, structured spaces, lack uncertainty quantification, and often rely on unstructured, noisy optimization histories that lead to inefficient context utilization and premature convergence. Existing hybrid methods often fail to effectively synergize LLMs and BO in the CASH setting due to a lack of a structured state that models hierarchical optimization trajectories.

Methodology: LB-MCTS
The authors propose LB-MCTS, a trajectory-structured optimization framework that integrates LLMs and BO using a Monte Carlo Tree Search (MCTS) tree as a shared state. The method reformulates CASH as a sequential decision-making process over a tree structure with three node types: a root CASH node, algorithm (Algo) nodes, and hyperparameter (HP) nodes.

Key components include:

1. Tree-Structured Search: The MCTS tree organizes the search space hierarchically. Actions include algorithm selection, initialization (generating a starting configuration), and optimization (refining a configuration). The tree captures the full optimization trajectory, allowing for root-level algorithm selection and subtree-level exploration-exploitation within specific algorithm subspaces.
2. BO–LLM Proposer Synergy: The framework employs two complementary proposers:
   • BO Proposer: Uses a per-algorithm Gaussian Process (GP) surrogate model to perform quantitative search. It generates candidates via random or local sampling and selects the best candidate using Expected Improvement (EI).
   • LLM Proposer: Uses In-Context Learning (ICL) to generate semantic proposals. It extends the PUCT selection process to choose a base node and then queries the LLM to propose a new configuration based on a structured prompt.
3. Selective Tuning Memory (STM): To address the challenge of efficient context utilization, STM retrieves algorithm-specific and trajectory-relevant trials from the shared tree state. It combines Global Memory (Pareto-optimal historical attempts based on similarity and performance) and Local Memory (the ancestral path from the algorithm root to the current node). This isolates histories from different algorithms to prevent cross-algorithm noise and provides the LLM with focused, low-noise context.
4. Dynamic Proposer Selection: A reliability-aware policy adaptively shifts between LLM and BO proposers. Initially, the LLM is favored for warm-starting with semantic priors. As the BO surrogate model matures (quantified via cross-validation rank correlation), the probability of selecting the BO proposer increases, ensuring a smooth transition from semantic exploration to quantitative exploitation.
5. Reflection Mechanism: Following the evaluation of a proposed configuration, the LLM (or a heuristic rule for BO) generates a reflection summarizing what worked or failed. This verbal feedback is stored in the tree node, bridging the gap between numerical rewards and semantic reasoning for future iterations.

Key Contributions

• Tree-Structured Formulation: The paper formulates CASH as a tree-structured search over optimization trajectories, enabling principled algorithm selection and hierarchical exploration-exploitation balance.
• Unified Synergy: It unifies BO and LLM optimization trajectories in a shared tree state, allowing for dynamic proposer selection that outperforms either component alone.
• Selective Tuning Memory: The introduction of STM allows the LLM to reason from focused, algorithm-specific, and trajectory-relevant contexts, mitigating the noise associated with mixing histories across different algorithms.
• Empirical Validation: Extensive experiments on 104 datasets from the AutoML Benchmark (AMLB) demonstrate the method's effectiveness.

Results
Experiments on 104 AMLB datasets (covering classification and regression tasks) show that LB-MCTS consistently outperforms state-of-the-art baselines, including pure BO methods (SMAC, OptDivBO, Rising Bandit, MOSAIC), pure LLM optimizers (OPRO, LLAMBO), and existing hybrid approaches (BOPRO, BORA).

• Performance: LB-MCTS achieves the best average validation rank of 2.16, significantly outperforming the second-best baseline, Rising Bandit (RB), which ranked 3.49.
• Test Set Performance: On the test set, LB-MCTS maintains a leading average rank of 3.05, statistically significantly superior to all baselines.
• Efficiency: The method achieves these gains with an economical API cost of approximately $0.127 per task and demonstrates robust performance across diverse task types, sample sizes, and feature dimensions.
• Ablation Studies: Analyses confirm that the tree-structured search, the dual directive strategy (Exploration/Exploitation), the STM mechanism, and the dynamic proposer selection are all critical to the method's success.

Significance and Claims
The paper claims that LB-MCTS effectively lowers the expertise barrier in AutoML by addressing the specific challenges of the CASH problem: efficient context utilization, the exploration-exploitation trade-off in structured spaces, and the effective synergy between LLMs and BO. By using the MCTS tree as a shared state, the method overcomes the limitations of existing hybrids that rely on flat, unstructured history exchanges. The authors assert that LB-MCTS provides a robust, sample-efficient solution for high-dimensional, structured optimization problems, achieving superior performance without prohibitive computational costs. The work also includes a theoretical analysis proving global convergence almost surely as the number of iterations approaches infinity, provided the BO-selection probability is lower-bounded.