Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery

The evolution of large language models (LLMs) such as GPT-4 and PaLM has revolutionized natural language processing and program synthesis. Early efforts like FunSearch and AlphaEvolve integrated LLMs into evolutionary algorithms for program generation, achieving notable success in mathematical and combinatorial problems. However, these approaches largely relied on black-box fitness signals, limiting their efficiency and interpretability. Recent research emphasizes the importance of structuring the search space, leveraging semantic representations, and incorporating contrastive learning to better exploit LLM internal knowledge. Despite progress, fully harnessing the potential of LLMs for algorithm discovery remains an open challenge, especially in complex, poorly understood problem domains.

Current algorithm discovery methods predominantly depend on fitness-based selection within unstructured program spaces, which hampers efficiency and scalability. The lack of explicit semantic or hierarchical organization prevents the search from effectively navigating the vast, irregular space of programs. As a result, the discovery process is often slow, opaque, and prone to getting stuck in local optima. Developing a method that explicitly models the semantic structure of algorithms could significantly improve search guidance, interpretability, and the ability to generalize across tasks.

The primary innovation is the integration of hierarchical semantic concepts into the search process via a contrastive learning framework. This involves constructing a dynamic concept tree, where each node encodes a semantic idea, and learning which concepts are associated with high performance. The method employs likelihood ratios derived from probabilistic models to bias parent node selection, effectively guiding the search toward promising regions. Additionally, the approach introduces exploration mechanisms to discover new concepts and avoid premature convergence. These innovations collectively enable a more structured, interpretable, and efficient search process compared to existing black-box methods.

• �� Extract hierarchical concepts from generated programs using LLM prompts, organizing them into a dynamic tree structure.
• �� Use an external evaluator to assign performance scores to candidate programs.
• �� Fit probabilistic models (via cross-entropy updates) to high- and low-performing subsets of programs based on their concept features.
• �� Calculate likelihood ratios to reweight parent node selection, favoring concepts linked to better performance.
• �� Incorporate exploration strategies to introduce and emphasize underexplored or novel concepts during search.
• �� Combine multiple parent selection strategies (uniform, greedy, k-elites, CCTS) to balance exploration and exploitation.
• �� Generate new candidate programs conditioned on selected parent nodes and biased concept directives, iterating this process to improve solutions.

Experiments focus on Erdős-style combinatorial problems, including circle packing and Heilbronn’s triangle problem. The framework compares CCTS with baseline methods like greedy, uniform, and k-elites, measuring average scores, convergence speed, and interpretability of concept trees. Multiple runs assess robustness. Synthetic environments simulate ground-truth concept structures, validating the model’s ability to recover and utilize meaningful semantic features. Hyperparameters such as iteration count, exploration probability, and concept model complexity are tuned for optimal performance. Results show CCTS consistently outperforms baselines across tasks, demonstrating faster convergence and higher-quality solutions.

CCTS achieves over 15% higher average scores within the same iteration budget across multiple tasks, with a 20% reduction in convergence time compared to baselines. The learned concept trees are interpretable, capturing meaningful problem-specific structures. Synthetic experiments confirm the model’s ability to recover ground-truth concept utilities, emphasizing the importance of learning which concepts to avoid. Ablation studies reveal that the contrastive reweighting mechanism is critical for performance gains, and exploration strategies help discover novel concepts, further improving search outcomes.

This approach can be applied to automated algorithm design, mathematical problem solving, and scientific discovery, especially in domains where explicit semantic understanding is beneficial. It enables AI systems to generate interpretable, high-quality algorithms efficiently, reducing reliance on human expertise. The framework is adaptable to various problem types, including symbolic reasoning, combinatorics, and optimization tasks, and can be integrated into existing program synthesis pipelines for enhanced performance.

Dependence on accurate concept extraction limits effectiveness if semantic definitions are noisy or incomplete. Computational overhead increases with larger hierarchies and more complex models. The approach may struggle with tasks where the semantic structure is not well-defined or too sparse. Scalability to very large program spaces remains a challenge, requiring further optimization. Future work should focus on improving concept extraction robustness and reducing computational costs.