ConceptSearch: Towards Efficient Program Search Using LLMs for Abstraction and Reasoning Corpus (ARC) (Student Abstract)

Kartik Singhal, Gautam ShroffAAAI 2025 · DOI

TL;DR

This paper tackles the challenging Abstraction and Reasoning Corpus (ARC) by introducing ConceptSearch, a novel program search algorithm that leverages Large Language Models (LLMs). By employing concept-based scoring functions, ConceptSearch significantly improves efficiency and accuracy compared to direct LLM prompting and simpler scoring methods, demonstrating a more intelligent approach to program synthesis for complex reasoning tasks.

What Problem Does This Paper Address?

The Abstraction and Reasoning Corpus (ARC) is a benchmark designed to test an AI's ability to generalize and learn from a few examples, mimicking human-like reasoning. It presents tasks where an AI must infer a transformation rule from a set of input-output grid pairs and then apply that rule to new inputs. Current deep learning methods, including LLMs, struggle with ARC due to its demand for broad generalization and few-shot learning. While LLMs are good at program synthesis, directly applying them to ARC yields limited success. Existing program synthesis approaches often require complex, hand-crafted Domain-Specific Languages (DSLs) and struggle with the combinatorial explosion of possibilities. This paper aims to bridge this gap by developing a more efficient and effective LLM-based program search strategy for ARC.

Methods

The core of ConceptSearch is an LLM-guided function search algorithm. It builds upon the FunSearch framework, which iteratively samples and ranks programs using an LLM. The novelty lies in the concept-based scoring functions used to guide this search. Instead of relying solely on pixel-level similarity (like Hamming distance), ConceptSearch uses two main scoring approaches:

  • CNN-Based Scoring: A neural network is trained to capture the "concept" of a transformation by learning representations of input-output pairs. The similarity score is then calculated based on the distance between the representations of the true transformation and the program's inferred transformation. This network is trained using a dual loss approach (cross-entropy and contrastive loss) on the Concept-ARC dataset.
  • LLM-Based Natural Language Scoring: This method leverages natural language descriptions of tasks. An LLM generates a "goal" hypothesis (a natural language description of the transformation) for a given task. Another LLM generates natural language descriptions for candidate programs. A SentenceTransformer model then embeds these natural language descriptions, and the similarity score is the distance between the embeddings of the goal hypothesis and the program's hypothesis.

When a program correctly generates outputs for all demonstration examples, it's evaluated on test examples. The algorithm iterates, refining programs based on their scores until a solution is found or a maximum number of attempts is reached.

Datasets

  • Abstraction and Reasoning Corpus (ARC): Used for evaluating the performance of the proposed ConceptSearch algorithm.
  • Concept-ARC dataset: Used for training the CNN-based scoring function. This dataset categorizes ARC tasks into 16 distinct concept classes.
  • LARC dataset: Consists of natural language descriptions for ARC tasks, used for training the LLM-based natural language scoring function.

Key Insights and Ideas

  • Beyond Pixel-Level Similarity: The most crucial insight is that superficial similarity (like matching pixels) is insufficient for solving complex reasoning tasks like ARC. Capturing the underlying "concept" or logic of a transformation is paramount.
  • LLMs as Reasoning Engines: LLMs can be effectively leveraged not just for generating programs but also for guiding a search process through sophisticated scoring mechanisms.
  • Concept Representation is Key: Both the CNN and LLM-based scoring functions aim to create meaningful representations of transformations, allowing for a more robust evaluation of program correctness.
  • Efficiency Gains: Concept-based scoring significantly reduces the number of iterations needed to find a solution compared to simpler methods, making the search process more efficient.

Key Results

ConceptSearch, particularly with its LLM-based natural language scoring, achieved the highest accuracy (29/50 tasks solved) among the evaluated methods on a subset of 50 ARC training tasks. It also demonstrated the most efficient search, requiring an average of 2.05 iterations per solved task.

  • Accuracy:
    • Ours - LLM-based: 29/50
    • Ours - CNN-based: 25/50
    • Ours - Hamming distance: 25/50
    • Direct Prompting (Xu et al. 2024) - GPT-4: 13/50
  • Mean Iterations (for solved tasks):
    • Ours - LLM-based: 2.05
    • Ours - CNN-based: 2.80
    • Ours - Hamming distance: 3.70

The LLM-based scoring function showed a significant efficiency gain (29.3%) over the CNN-based scoring function and a substantial gain (70.7%) over the Hamming distance for tasks solved by both methods.

Limitations and Future Work

  • Computational Cost: While more efficient than direct prompting, LLM-based methods can still be computationally intensive. The paper mentions using Gemini 1.5 Pro and Flash, indicating reliance on powerful, potentially costly models.
  • Reliance on Pre-trained Models: The performance of the LLM-based scoring is dependent on the quality of the pre-trained LLM and SentenceTransformer.
  • Future Work: The authors suggest that the quality of programs provided in context directly influences search efficiency. Future work could explore better initialization strategies for the program database and further refine the concept-based scoring functions. The paper also implies that exploring object-based representations, as mentioned in related work, could be a promising direction.

Summary updated

BibTeX
@inproceedings{singhal2025conceptsearch,
  author = {Kartik Singhal and Gautam Shroff},
  title = {{ConceptSearch: Towards Efficient Program Search Using LLMs for Abstraction and Reasoning Corpus (ARC) (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i28.35300},
}
Figure