Technical Summary: Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery

Problem Statement

Large Language Model (LLM)-assisted algorithm discovery operates as an iterative, black-box optimization process where an LLM proposes candidate programs, and an external evaluator provides task feedback. While recent paradigms (e.g., FunSearch, AlphaEvolve) have successfully rediscovered or improved solutions to combinatorial problems (such as Erdős-style problems), they largely rely on fitness-driven evolutionary updates. In these existing systems, parent selection is determined by the raw performance (fitness) of programs, and the search proceeds as a walk over the lineage of programs ordered by performance.

A critical limitation of this approach is that the program space remains weakly structured. Even when constrained by an LLM, generated algorithms often lack clear notions of locality, smooth variation, or compositional structure that can be exploited by search algorithms. Consequently, guidance is derived primarily from raw fitness signals and the LLM's implicit prior, rather than an explicit, learned understanding of which semantic components of the algorithms are actually useful. This paper addresses the open question of how to maximally exploit the LLM's internal representation of the program space to improve search efficiency and interpretability.

Methodology: Contrastive Concept-Tree Search (CCTS)

The authors introduce Contrastive Concept-Tree Search (CCTS), a framework that shifts the search guidance from raw fitness to a learned, hierarchical semantic concept space. The core hypothesis is that algorithms can be described by an underlying semantic concept space organized as a hierarchy, where nodes represent concepts and edges encode refinement or specialization.

1. Concept Representation and Tree Construction

• Feature Extraction: Each candidate program $x$ is mapped to a semantic feature representation $b = \Phi(x)$, extracted by prompting the LLM to generate a list of relevant concepts.
• Hierarchical Structure: These concepts are organized into a rooted concept tree. A concept vector $b$ is an indicator vector where activations are ancestor-closed (activating a child concept implies activating all its ancestors). The tree is dynamic, growing as new concepts are discovered during the search.

2. Contrastive Learning of Concept Utility

Instead of selecting parents based solely on their fitness score, CCTS learns which concepts are empirically associated with high performance through a contrastive approach:

• Partitioning: The archive of evaluated programs is partitioned into "good" ($y_i \ge \tau_t$) and "bad" ($y_i < \tau_t$) subsets based on a performance threshold.
• Model Fitting: Two probabilistic models, $\hat{p}_{\eta^+}(b)$ and $\hat{p}_{\eta^-}(b)$, are fitted to the feature distributions of the good and bad subsets, respectively. The authors utilize a Tree-structured Parzen Estimator (TPE)-style approach with a factorized hierarchical Bernoulli model. This model assumes conditional independence of features given their parent in the hierarchy.
• Likelihood Ratio Scoring: A likelihood-ratio score (log-concept utility) is computed for each program:
  $$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$$
  This score quantifies how strongly a specific set of concepts distinguishes high-performing solutions from low-performing ones.

3. Parent Selection and Search Dynamics

• Biased Sampling: Parents are selected from the archive with a probability proportional to their likelihood-ratio score. This biases the search toward programs containing concept combinations empirically associated with improvement.
• Exploration Mechanism: To prevent premature convergence and encourage the discovery of new concepts, CCTS incorporates a lightweight exploration mechanism. This includes:
  • Beta Priors: Smoothing counts to ensure newly discovered concepts never have zero probability.
  • Novelty Bias: Downweighting concepts that have been frequently tried, favoring underexplored regions of the concept tree.
  • Mixture Strategy: A mixture of exploitation (based on the learned contrastive model) and exploration (based on novelty) guides the selection of concepts to inject into the LLM's prompt for child generation.

Key Contributions

1. Explicit Semantic Structure: The paper proposes making the latent structure of the algorithm space explicit by learning a hierarchical concept tree, moving beyond the unstructured program space used in standard evolutionary algorithms.
2. Contrastive Guidance: It introduces a contrastive statistical framework that learns to identify which concepts to prioritize and, crucially, which concepts to avoid, rather than just tracking which programs perform best.
3. Interpretability: The method produces interpretable, task-specific concept trees that reveal the semantic structure explored during the search, offering insights into the algorithmic strategies being discovered.
4. Synthetic Validation: The authors construct a controlled synthetic environment with a "teacher" concept tree and ground-truth utilities. This allows them to validate that CCTS recovers the underlying semantic structure and that the observed search dynamics are driven by the learning of concept utilities rather than specific LLM artifacts.

Experimental Results

The authors evaluated CCTS on a benchmark of open Erdős-type combinatorics problems, including circle packing, the Arithmetic Kakeya conjecture, Heilbronn's triangle problem, and the squares-in-square problem.

• Performance Gains: CCTS consistently achieved higher scores and faster improvement compared to baseline strategies (Uniform, Greedy, and $k$-elite selection) across multiple tasks.
• Mechanism of Improvement: Analysis revealed that the performance gains are driven largely by learning which concepts to avoid. Successful runs identified a similar set of high-utility concepts as unsuccessful runs but demonstrated a significantly better ability to suppress low-utility (harmful) concepts. This suggests CCTS stabilizes search by reducing unproductive exploration caused by misleading correlations in the LLM's initial prior.
• Synthetic Validation: In the synthetic environment, the learned concept utilities showed strong correlation ($r=0.94$) with the ground-truth teacher utilities, confirming that the method effectively recovers meaningful semantic representations.
• Structure Dependence: The optimal balance between exploration and exploitation was found to depend on the structure of the underlying concept tree (e.g., branching ratio), suggesting that search strategies should be adapted to the specific topology of the problem space.

Significance and Claims

The paper claims that CCTS addresses a fundamental mismatch in current LLM-assisted algorithm discovery: high-scoring algorithms do not necessarily generate strong descendants because fitness is a poor proxy for evolvability in a weakly structured space. By shifting selection from raw fitness to semantic evidence of improvement, CCTS allows the search to operate in a concept space where distance, recombination, and search direction are meaningful.

The authors position this work as a methodological advance toward more reliable and scalable algorithm discovery. They emphasize that while the current results demonstrate relative improvements over baselines on specific benchmarks, the primary contribution is the demonstration of how explicit, human-compatible semantic concept structures can make automated discovery more transparent, controllable, and efficient. The work suggests that future systems should focus on learning and exploiting these latent semantic hierarchies rather than relying solely on black-box fitness signals.