Large Language Models are Interpretable Learners
Authors: Ruochen Wang
Si Si
Felix Yu
Dorothea Wiesmann Rothuizen
Cho-Jui Hsieh
Inderjit S Dhillon
Venue: ICLR 2025 Poster (2025)
Keywords: Interpretability
Explainable AI
LLMs
VLMs
MLLMs
Symbolic Learning
Prompting
Primary area: interpretability and explainable AI

Abstract: The trade-off between expressiveness and interpretability remains a core challenge when building human-centric models for classification and decision-making. While symbolic rules offer interpretability, they often lack expressiveness, whereas neural networks excel in performance but are known for being black boxes. This paper shows a combination of Large Language Models (LLMs) and symbolic programs can bridge this gap. In the proposed LLM-based Symbolic Programs (LSPs), the pretrained LLM with natural language prompts provides a massive set of interpretable modules that can transform raw input into natural language concepts. Symbolic programs then integrate these modules into interpretable decision rules. To train LSPs, we develop a divide-and-conquer approach to incrementally build the program from scratch, where the learning process of each step is guided by LLMs. To evaluate the effectiveness of LSPs in extracting interpretable and accurate knowledge from data, we introduce IL-Bench, a collection of diverse tasks, including both synthetic and real-world scenarios across different modalities. Empirical results demonstrate LSP's superior performance compared to traditional neurosymbolic programs and vanilla automatic prompt tuning methods. Moreover, as the knowledge learned by LSP is a combination of natural language descriptions and symbolic rules, it is easily transferable to humans (interpretable), and other LLMs, and generalizes well to out-of-distribution samples. Our code and benchmark will be released for future research.

Published as a conference paper at ICLR 2025
LARGE LANGUAGE MODELS ARE INTERPRETABLE LEARNERS
Ruochen Wang" UCLA
Si Si Google
Felix Yu Google
Dorothea Wiesmann Google
Cho-Jui Hsieh Google, UCLA
Inderjit Dhillon
Google
ABSTRACT
The trade-off between expressiveness and interpretability remains a core challenge when building human-centric models for classification and decision-making. While symbolic rules offer interpretability, they often lack expressiveness, whereas neu- ral networks excel in performance but are known for being black boxes. This paper shows combination of Large Language Models (LLMs) and symbolic programs can bridge this gap. In the proposed LLM-based Symbolic Programs (LSPs), the pretrained LLM with natural language prompts provides a massive set of interpretable modules that can transform raw input into natural language con- cepts. Symbolic programs then integrate these modules into interpretable decision rules. To train LSPs, we develop divide-and-conque approach to incrementally build the program from scratch, where the learning process of each step is guided by LLMs. To evaluate the effectiveness of LSPs in extracting interpretable and accurate knowledge from data, we introduce IL-Bench, a collection of diverse tasks, including both synthetic and real-world scenarios across different modalities. Empirical results demonstrate LSP's superior performance compared traditional neurosymbolic programs and vanilla automatic prompt tuning methods. Moreover, as the knowledge learned by LSP tions and symbolic rules, it is easily transferable to humans (interpretable), and other LLMs,, and generalizes well to -ut-of-distribution samples. Our code and benchmark will be released for future research.
combination of natural language descrip-
INTRODUCTION
Learning interpretable predictive models from annotated data remains key challenge in human- centric AL. Given input-output pairs ((T;, vi)}, the objective is to learn a function f x - y that not only fits the data accurately but is also interpretable. means that human with no prior domain knowledge can understand and apply the decision rules demonstrated by f. facilitating the transfer of knowledge from Al humans. This is crucial not only for enbancing the transparency of Al systems but also for enabling humans to learn from these models, empowering various comman-n--the-lone applications such as scientific discovery, material synthesis, and automatic data annotation (Chaudhuri et al., 2021).
this context, a strong form of "interprettalee
Definition 1.1 A predictive model is considered interpretable if its decision rules can be understood and applied by a human judger without prior domain knowledge.
Consider an exemplar task of classifying species in Palworld (Pair, 2024) - a newly released Pokemon- style game based on few image-label pairs, as illustrated in Figure 1. The ultimate goal is that even humans unfamiliar with Palworld can replicate AI's decisions by following the same predictive rules after examining the model trained on the data. This task effectively represents the challenge of extracting interpretable knowledge, such species characteristics. from data. The algorithm propose in this paper learns a model following the decision rule illustrated in Figure 1, which is designed to be easily understood and reproduced by humans. In essence, this problem be viewed as discovering interpretable knowledge (e.g., the properties of a species in Palworld) from the data.
Work completed during internship Google.

---

Published as a conference paper at ICLR 2025
Despite extensive research, the problem of developing fully interpretable predictive model has not been fully addressed. Traditional methods often face trade-off between expressiveness and interpretability: Deep neural networks, for instance, are powerful yet operate as "black boxes". Although post-hoc explanation methods attempt to make these models more transparent by identifying influential features (Zintgraf et al., 2017; Petsiuk et al., 2018; Dabkowski & Gal, 2017; Shrikumar al. 2017; Sundararajan at, 2017; Ancona et al., 2017), they do not not clarify the underlying decision- making processes and have no control over the learning process. Directly learning interpretable models like (locally) linear (Ribeiro et al., 2016), tree-based (Lundberg, 2017) often falls short in expressiveness, especially with complex inputs like images.
To address this challenge, Neurosymbolic Programs (NSPs) (Chaudhuri et al., 2021; Shah et al., 2020; Cui & Zhu, 2021; Nauta et al., 2021b) offer a promising solution by modeling the decision rule program incorporating both symbolic operations and neural network modules. Despite this, the inherent trade-off between expressiveness and interpretability persists. While the integration of neural modules enhances expressiveness, it also compromises the program's 's overall interpretability. Additionally, designing effective symbolic operators requires significant expertise and is critical for the performance of the resulting program, necessitating careful customization for each specific dataset (Chaudhuri et al., 2021; Shah et al., 2020; Cui & Zhu, 2021).
Is it possible to harness the power of neural networks within Neurosymbolic Programs without compromising interpretability? This paper presents an affirmative answer. Our key insight that (Multimodal) LLMs encompass variety of powerful, conditional probabilistic sub-models. These models share unified parametric architecture with the unconditional parent LLM (Super Model), yet distinctive defined by their respective prompts. Therefore, crafting prompts (by either Human or meta- LLMs) for LLM is equivalent searching over the hypothesis space spanned by these submodels. This yields an infinite set of neural network-based operations that are inherently interpretable and can serve as fundamental "learnable" building blocks within Neurosymbolic Programs.
Building on this insight, we introduce a novel framework termed LLM-Symbolic Programs (LSPs), defined and Iearned through LLMs. Our approach leverages minimal Domain-Specific Language (DSL) set with only two operators: prompted-LLN, and conditional branching, yielding a classic decision-making process structured as trees. We then propose learning algorithm to incrementally learn the tree using LLMs with prompt optimization. To thoroughly evaluate the efficacy of LSPs, we construct the enterpretable-Lernine Lee--eaan-----nchaartt Benchmark of diverse predictive tasks, containing both synthetic and real-world data across vision and text modalities. Our empirical findings show that LSPs surpass the accuracy of both traditional XAI methods and LLMs prompted with automatically learned instructions, all while maintaining human interpretability. These results highlight the potential of LSPs to significantly enhance the performance and utility of Multimodal LLMs in various applications.
BACKGROUND AND RELATED WORK
Taxonomy Interpretable learning (IL. is central aspect of Explainable AI (XAI). The taxonomy closely follows that of discriminative tasks: for a given dataset (I. v), the objective is to construct a model that not only predicts accurately but also provides insight into its predictions. Here, the knowledge required for making accurate predictions is not inherent to the model; rather, it must be distilled from the data into compact, interpretable rules. In this work, we use strong form of "interpretability" defined as follows:
Traditional IL methods The pursuit of interpretable model predictions divides into two primary methodologies: post-hoc and intrinsic. Post-hoc methods explain the behavior of pre-trained models by identifying salient features, yet they fall short of fully recovering the neural secision-making process. In contrast, intrinsic methods, such Neuro-Symbolic Programming (NSP) (Chaudhuri et al., 2021; Shah et al., 2020; Cui & Zhu, 2021; Nauta et al., 2021b), integrate interpretability directly into the model architecture. However, NSP faces a fundamental trade-off between expressiveness (requiring more neural network modules) and interpretability (favoring symbolic modules). Addition- ally, training NSP models is often computationally expensive due to the need for co-optimizing both program architecture and neural network parameters (Shah et al., 2020; Cui & Zhu, 2021).
Interpretable Learning in the era of (M)LLMs web-scale pretraining of (M)LLMs has empowered (M)LLMs with remarkable zero-shot capabilities
The vast corpus of knowledge encoded during the
2

---

Published as a conference paper at ICLR 2025
across diverse tasks, including math, coding, creative writing, etc. However, IL tasks pose unique challenge for these models, as they are inherently not zero-shot solvable (Table 1). Specifically, LLMs must utilize knowledge acquired from labeled examples rather than relying solely on input data and its prior knowledge (including external knowledge retrieved via RAG).
(1), Can existing prompting methods apply to II tasks? Most LLM prompting methods, such as Tree- of-Thoughts (Yao et al., 2024) or augmenting LLMs with various tools (calculator, symbolic solver, etc) (Dong et al., 2023; Fang et al., 2024; Yang et al., 2023b), do not involve any learning and are thus incompatible with IL tasks. Generie Prompt Optimization (PO) methods, which aim to automatically configure instructions for LLMs, could be applied to any task, including IL in principle (Zhou et al., 2022; Pryzant al., 2023; Yang et al., 2023a; Singh al., 2023; Wang et al., 2023). However, PO methods are predominantly designed for instruction induction task - inferring optimal task descriptions rather than extracting concrete predictive rules from data (Zhou et al., 2022; Zhang al., 2023). Consequently, most PO approaches focus on rewriting prompts to enhance performance (Pryzant et al., 2023; Hsich et al., 2023), which is insufficient for deriving interpretable knowledge from data. Additionally, while recent developments have introduced capabilities for correcting prompts using error examples (Pryzant et al., 2023; Wang et al., 2023), they remain inadequate for extracting complex decision rules, such as conditional branching required for classification. These rules, often applicable to only subset of samples, are challenging to recover when considering the entire training set. Our experiments show that directly applying existing methods fails to effectively address these complex decision rules. These limitations motivate the proposed LSP framework, which integrates prompt optimization with symbolic programs to overcome these challenges.
(2). Can existing benchmarks measure (M)LLM's IL ability? Despite the extensive study of IL in the pre-LLM era, there lacks of benchmarks suitable for evaluating such methods on modern (M)LLMs. Traditional XAI Datasets are often image-centric and inadequate for evaluating the text capabilities of LLMs. Furthermore, the inclusion of popular vision datasets like CUB within MLLM training corpuses leads to data contamination, making it difficult to determine if performance improvements due to enhanced rule learning mere retrieval of prior knowledge. LLM Benchmarks, such Big- Bench (Suzgun ct al., 2022). SuperNatural Instructions (Wang et al., 2022). and Math datasets (Cobbe et al., 2021; Tricu& & Luong. 2024; Wei et al., 2024), measures various language ability of the model, ranging from prompt optimization, reasoning tasks, to summarization. However, all these tasks are all zero-shot solvable, allowing LLMs to make predictions without additional rule learning. Therefore, these benchmarks are unsuitable for evaluating IL tasks.
A Comprehensive literature review on the previous XAI methods, Neuro-Symbolic Programming, and Prompt Optimization methods can be found in Appendix A.1.
Interpretable Learning
Common LLM
Zero shot solvable?
solving the task requires extracting rules from labeled training data.
LLKs con in principle solvas these tasks without seen any labeled examples.
Representative lasks
Palword clasaiiication; Symbolic claastff f on tasks
sig-Rench-Hard, Abstract Keascning,
Math, coding, Agant, summarization, SAG.
Example data
Imput: you return the starting point? Take a steps. Turn around. Take 8 ateps.
Input which creature in the Falworid-dex this? output: creature_"
Output: Yes
Table 1: Comparison between the taxonomy of Interpretable Learning and common LLM tasks.
3 IL-BENCH: 1ST INTERPRETABBLE-LEARRRE
BENCHMARK FOR (M)LLMS
To address the lack of suitable benchmarks for evaluating the interpretable learning capabilities of (M)LLMs, we introduce the Interpretable- Learning Benchmark (IL-Bench). This new benchmark comprises a series of challenging tasks that are not solvable through zero-shot methods by even the most advanced (M)LLMs, such as GPT-4 and Gemini- IL-Bench includes 16 new symbolic and real-context tasks unseen to the current model lineup. These tasks range across vision and language modalities, providing a comprehensive and extensible evaluation framework. Below, we provide high-level summary of the key data curation methods; Concrete examples, data curation, statistics, and how extend this benchmark can be found in the Appendix A.2 (Table 8).
3

---

Published as a conference paper at ICLR 2025
Symbo-y Programming (NSP)
Das fecarr mraill dualgingg spenters
Jesardiin interpenabllle
Calneetnn cb: predict Xirae))
Bis QHILA prodic
LLMI Symbolic Programming (LSP)
Gemini
Thr cesttre los roneg Iuey laaiie "aaeee
By esamining function I betieve hour distinguishh botueen thage species
S
Roddy
The C'aature voca lepi, torra and Haarp Clasi "Arace"
Rocto
Illustration of LLM-Symboolic vs. Neuro-Symbolic Program on interpretable learning task. The goal is to develop model that allows humans with prior knowledge to replicate Al's decisions by following the rules as the model. While NSP (Top right) offers certain level of interpretability. it heavily relies on manually designing operators, and the inclusion of neural operators often reduces interpretability, In contrast, LSP (Bottom right) generates fully interpretable programs with the help of versatile LLM modules.
Figure 1:
Symbolic tasks Drawing inspiration from language-independent IQ tests, we generate set of synthetic datasets to evaluate the interpretable learning capabilities of the models. These datasets utilize symbols to denote input variables and their values; The input values are randomly assigned, and mapped to their labels based on predefined set of rules (See Figure 8 for a concrete example). We also vary the number of variables, values, and labels to generate datasets of increasing complexity. These symbolic tasks enjoy several key benefits: (1). Known oracle rules, enabling precise evaluation of learning ability. (2). Context independence, forcing the models to depend solely on learned rules, without relying on external context. (3). Scalability, allowing for the automated creation of an unlimited number of tasks with arbitrary difficulty levels.
Textual classification tasks: converting vision dataset text inputs To evaluate model pro- ficiency in intricate real-world scenarios, we utilize Fine-Grained Visual Classification (FGVC) datasets (Maji al., 2013; Wah al., 2011; Kramberger & Potočník, 2020; Nilsback Zisserman, 2008; Van Horn et al., 2015), such as CUB commonly used in XAI research. These datasets comprise of objects within narrowly-defined, visually-similar categories that are partieularly challenging for the model to distinguish. To adapt these visual datasets for textual evaluation, we convert them into text-based datasets using a captioning model. In order for the task to be well-defined, the generated caption must cover all visual features required for classification, which are usually very subtle for FGVC datasets (e.g. the particular shape of bird's beak). To ensure the captions capture all essential visual features, we also provide contrastive examples to the captioner (details in Appendix). The class names (e.g, Sca_Albaue Sea__Abbtrosss model from using label names to "shortcut" the prediction process. Empirical results indicate that the performance of existing text-based L.MMs approximates that of random guessing in zero-shot setting.
also anonymized by symbols (e.g.. class_ to prevent the
Visual classification Tasks: distinguishing novel visual concepts Due to the extensive coverage of (M)LLM training data, evaluating models in a multi-modal setting presents a unique challenge. Despite our best efforts, all existing image classification datasets we tested were already seen by least one (M)LLM, which can predict labels in zero-shot manner. To address this, we curate seven new datasets using screenshots from "Palworld," a recently released regional game featuring various creature species similar to Pokémon (examples in Table 8). As this game was released after the knowledge cut-off dates of the tested (M)LLMs, the models lack prior information about these creatures, requiring them rely solely on the knowledge extracted from the dataset for predictions.
4 INTERPRETABLE LEARNING WITH LLM-SYMBOLIC PROGRAMMING
This section explains our proposed framework: LLM-SSmbolic Programs. Section 4. 1 reviews Neurosymbolic Learning method. Section 4.2 discusses utilizing LLM to implement interpretable programs, including a connection between prompted- LLM and interpretable unit (Section 4.2. the Domain Specific Language (Section 4.2.2) and learning algorithm (Section 4.2.3).
4

---

Published as a conference paper at ICLR 2025
4.1 PRELIMINARIES ON CLASSICAL NEUROSYMBOLIC LEARNING
NeuroSymbolic Programming (NSP) (Chaudhuri et al., 2021; Shah et al., 2020; Cui & Zhu, 2021; Frosst Hinton, 2017) represents an innovative method for combining classical symbolic learning with contemporary neural networks, with the goal of building expressive and interpretable models. NSP often consists of two main components: (1) a Domain Specific Language (DSL. that specifies available operations of the program (akin to a "search space") and (2) learning algorithm for finding the best program. The resulting programs are structured, neuro-symbolic terms that follow the syntax specified by the DSL.
Domain-Specifte Language (DSL) DSL in NSPs comprises manually defined operators, including interpretable symbolic (e.g. if ff-then- else) and expressive neural components (e.g. cnn (x, 8)) ). These operators can be chained to construct various structree programs, a.k.a. computation graphs. equation presents an example DSL used to construct the program for predicting the creature species in Figure 1. Here, and represents inputs and constants, and denotes sub-progran proogrm:: | Add(an, .2) Mul(an,
If (x) Then 02 Else 0z cnn(2r, 0) Dist(ai, 02), (1)
Co-optimization of program structure and learnable parameters In NSPs, the construction of program involves solving combinatorial optimization problem for both the program structure and the parameters of its learnable operators (e.g. neural components). As the number of DSL operators increases, the complexity of this task grows exponentially. To make the search process more tractable, existing research employs various approximation techniques to efficiently identify viable candidates, including greedy tree search (Shah et al., 2020), continuous relaxation (Cui & Zhu, 2021), distillation (Frosst & Hinton, 2017) and meta-learning (Chaudhuri et al., 2021).
Limitations While the integration of symbolic and neural components in NSPs represents promis- ing innovation, the incorporating of neural modules inevitably introduces black-box components and makes the program non non-interpretable. Researchers have attempted to address this issue through two primary approaches: restricting the DSL to only interpretable operators (Shah et al., 2020; Cui & Zhu, 2021), or employing prototype learning to derive relatively interpretable neural modules (Nauta et al., 2021b; Ming al., 2019; Nauta et al., 2021a). However, the DSL. approach is not automatic, heavily relies on domain expertise, and potentially overlooking crucial information not identified by experts; Conversely, prototype learning aims represent the concept of each neural module by set of representative samples, which is not guaranteed to success.
4.2 LLM-SYMBOLLC PROGRAMS
This section explores how LLMs can effectively be utilized implement NSPs' modules that expressive, interpretable, and straightforward to learn with LLMs.
4.2.1
PROMPTED-LLM AS AN INTERPRETABLE UNIT
The trade-off between interpretability and expressiveness presents a fundamental limitation in machine learning. Machines perceive images and text as raw binary signals, and transforming these into interpretable concepts; this inevitably requires complex and non-interpretable components, such as neural networks. Even human perception remains non-interpretable, as we lack complete understanding of how the brain processes signals. However, the following analysis suggests that pretrained LLM offer potential avenue to bridge this gap: shows that powerful LLM can be used to define a wide range of interpretable functions via prompting.
Connection between interpretable learning and prompting LLMs pretrained on the next-token prediction task model the following joint distribution of a sequence of tokens (w))
II
T - P(w, Wt-1, 2 1) fo(w; W1, W2..... Wt-1),
P(W1, Wy. WT)
where the conditional probabilities are parameterized by an auto-regressive model f(: (e.g. Transformer) and each word w, is predicted given all the preceding tokens. The pretraining objective minimizes the following negative log-likelihood:
min L()) = Σ t=1 log fo(wr W,-ln...,, w1).
(2)
8
5

---

Published as a conference paper at ICLR 2025
SMM-Spbbsic Pto.Smmbii-Frrrmmnnng Programing (.SP)
The crastar Noxtor
Lifka
"Scchere" Ohinniee
Structure Search
Rakle 11
<Éompias for Seamer LUb
sdictractto actise Loireer LLB the above soaesies bass Thin provice high-
lnels these evsugle tasnt the
Pacchalddr
desoeras from Leamer
Plochooder
Node withi lrggrtt poneetaa Improwe
Raddy 2n Sceclite asime withest mane.
Uhe creature was groy nane, tean
Figure 2: Learning Algorithm for LSPs. The learning algorithm for LSPs contains two parts: (1) program structure search (Left): This process is akin to constructing a traditional decision tree. Starting from the root, the algorithm traverses down the tree, iteratively splitting the training dataset based on the current node's s predictions and expanding the leaf node with the highest prediction errors. (2) LLM module optimization (Right): Here, a learner L.M is instructed to summarize rules based on the observed data at its node.
key observation from Eq. equation 2 is that the training process optimizes a "'SupeNNet" of conditional probabilistic models (CPM), each defined by an instruction s: fz = fy xr s). where x the input and s is the instruction for a particular task. Therefore, with fixed LLM, the set of natural language prompts, denoted as S, provides a massive set of interpretable neural network modules for the task. For given dataset {(x 31) H=) finding the best prompt minimize the empirical loss, min > L((fs, (() z;))), can be viewed as form of learning, and the resulting model inherently interpretable, as the prompt s is expressed in natural language.
This connection reveals that prompt within the natural language space offers a form of interpretable learning that simultaneously achieves both expressiveness and interpretability. The key bridging this gap lies in leveraging LLMs to handle the non-interpretable processing of raw signals into high-level concepts, much like how neurons in the human brain transform signals into information. This allows learning to occur within an interpretable space.
4.2.2 DPMAIN-SPECIHIC LANGUAGE OF LSPS
Traditional NSPs require manually designing a comprehensive DSL. However, with LLM's ability to represent wide range of functions via different prompts, we significantly streamline the grammar required to build expressive and interpretable models. Specifically, for predictive models, we can build powerful LSPs from a minimalist DSL with only three components: the input, conditional branching, and LLM module:
(3) Here, input represents the input data (text, image, etc); the conditional branching swi tch (13 ai)/ forms the backbone of the program structure. Each switch can be viewed decision tree tree with & branches. It will branch to a; the sub-program a predicts yı. The LLM
a ::= x
//sstwccchff | = ys as)) LLM(M, s).
node in
Module LLM(,, s) serves the inference engines. It means to prompting LLM to make a prediction on input x under the instruction s.
Figure (Bottom Right) shows an example program generated from above DSL. During inference time, given a test query, we traverse the trce-structured program in top-down manner, assigning data to specific child node based on the parent node's 's predictions, until the leaf node is reached and the final response is returned.
4.2.3 LEARNING ALGORITIIM
After defining the search space for program construction, we proceed to describe the algorithm used to identify the optimal program. Similar to Neuro-Symbolic Programming (NSP), our approach involves optimizing two key components:
LLM module optimization: Generating the rules from data for each LLM module. Program structure search: Determining how to expand the program tree.
Figure illustrates the entire search process. The following sections will describe these two compo- nents respectively.

---

Published as a conference paper at ICLR 2025
LLM modules optimization via summarizing predictive rules In Large Symbolic Programs (LSPs), each LLM module is responsible for making decisions on its designated data subset. While traditional NSPs optimize neural modules through empirical risk minimization, LSPs can derive predictive rules directly from observed data, method we termed RuleSum. To achieve this, we leverage the LLM's powerful summarization capabilities (Adams et al., 2023; Goyal et al., 2022; Zhang et al., 2024; & Demberg, 2023), and instruct a learner LLM to observe patterns from the data samples and summarize them into concrete rules. The process is visualized in Figure 2 (right).
Program Structure Search LSP produces a tree-structured program where each path represents a complete decision-making process. To discover the optimal program, we employ top-down tree traversal approach to expand the tree from scratch. Starting from the root node of an empty program with the entire training dataset:
Step 1: Add an LLM (x, s) module to the root node.
Step 2: Optimize LLM (x, s) using the RuleSum algorithm.
Step 3: Create child nodes for the root by adding switch operator the program.
Step 4: Assign training data to child nodes based on LLM (x, s) 's predictions.
Step 5: Move to the highest-scoring child node, and repeat Steps 1-4 until max_ite iter is reached.
In essence, this search algorithm uses a divide-and -ondd-e strategy: it progressively partitions the training dataset into sub- bebbrrcchhss based the parent node's 's predictions, enabling the child LLM modules to further refine the prediction. This approach simplifies the learning process for each LLM module and makes the overall system more error-tolerant: the RuleSum algorithm only needs to derive rules for a subset of the data, and any inaccuracies can be corrected by subsequent child nodes.
Node scoring function for node selection During program structure search, prioritize the expansion of the node with the highest potential for program improvement. Since nodes with a higher frequency of errors have greater room for enhancement, we use error count as the scoring function. This metric, which considers both the error rate and the size of the data subset handled by each node, offers straightforward yet empirically effective approach. Section 6 provides empirical evidence demonstrating the efficacy and robustness this metric against alternatives.
Complete Algorithm The above outline the learning process of single program (visualized in Figure 2). To enhance the full search pipeline, we integrate beam search (Pryzant et al., 2023) to avoid getting trapped in local minima. Specifically, each iteration of the learning algorithm maintains and expands trees, where represents the beam size. Algorithm 2 in Appendix A.7 summarizes the entire process.
EXPERIMENTAL RESULTS
We adopt a comprehensive approach to extensively evaluate the effectiveness of LSPs against various baselines under different settings. Our empirical study is designed to validate the benefits of LSPs over alternative methods by addressing the following research questions:
Ql: How does LSP compare against traditional NSPs in expressiveness and interpretability? We assess this through both quantitative and qualitative evaluations (human studies). (Section 5.2)
Q2: Does LSP generalize better than traditional NSPs under domain shifts? This question is explored in detail in (Section 5.2).
Q3: Is the incorporation of explicil structures beneficial to LSPs? We compare the structured LSP with vanilla prompt optimization, which exemplifies special case of LSP with a single LLM module. (Section 5.3)
Q4: How effective are different LLMS in implementing ISP? We conduct cross-model experiments to evaluate the performance of various LLMs as the computational backbone for learning and inference in LSP. (Section A.5.1)
5.1 GENERAL SETTINGS
Evaluation For language tasks, we test popular LLMs, including GPT-3.5 (turbo-1104) (Ouyang et al., 2022), GPT-4 (1106-preview) (Achiam et al., 2023), and Gemini-M (1 C-pro) (Team et al., 2023). For vision tasks, GPT-4V (1106vvis) on-preview) and Gemini-Vision (1.5-flam are utilized, All experiments are repeated with seeds.
7

---

Published as a conference paper at ICLR 2025
Table 2: Classification accuracy comparison with XAI methods on IL--Bench- Vision. Here, numbers for LSP are obtained with Gemini- Vision as the learner and inference I.M., except for LSP (GPT-4V) which uses the larger GPT-4V as the learner; Decision Tree, operating directly on pixel data, lacks human interpretability. Key findings include: (1) Our method outperforms XAI baselines with an average accuracy of 95.67%, which is over 10% higher than the nearest competitor. (2) The program generated by LSP also demonstrates superior transferability human raters, as they able reproduce the predictions following rules learned by LSP.
IL-Benck- Viiien
Palvord
MILM
Methal
More
Fno-1
Fro-
Rogiel
Bogin-2
Waize
Decison Thee (Ches & Guestis, 2016]
68.20
91.11 & 12.57
32,00
9.50
68.33 s 10.27
48.33 2. 20:95
$2.67 a 5.50
65.33 4: 13
65.67 =: 5.50
ProveTeee UNtata 20210)
54.33
0.00
62.67
98.33
4.06
0.00
61.07
Genini M
LSP
9633
92.33 0.00
92.00 9.00
100.0 0.00
100.00 0,08
100,00 2: 0,00
95.00 5:00
97.50 17.50::239 2.50
(CPL-V))
96.77
96.57
6.00
50.00
10.00
97.50
2.50
100000 0.00
98.00 1
97.50
Human Roe
ProuoToee DNam 2001
72.44
75.0
$7.5
LSP (CPT-4M)
90.36
J0LI8
0,00
TILM0 2: 10,00
100,0
0.00
87.5 12.5
10000 2 0J0
100,00 :: 0.00
75.00 2500
Implementation details of LSP Our default model of choice is GPT-3.5 for language tasks and Gemini- Vision for vision tasks for cost efficiency, but also examine cross- Cross-(M)LLM performance in Appendix. All LLM modules are initialized with empty instruction "none". More detailed hyperparameters can found Appendix A.8, which is kept fixed throughout the experiments.
5.2 COMPARISON WITH TRADITIONAL INTERPRETABLE LEARNING METHODS
We compare LSP with two established models Pro- toTree (Nauta al., 202 and Decision Tree (Chen & Guestrin, 2016) both organize prediction process in tree-structured formats. Among existing NSP methods, the closest to ours is ProtoTree highly interpretable NSP that learns discrete binary tree end-to-end, where each node stores an image patch ("prototype") and the edges determine whether the prototype exists within the query image. Note that Proto Tree does not rely on an explicit DSL we could not compare with meth- ods based on explicit DSL since they require domain experts to design those operation, while our goal is to automate the whole process. Since ProtoTres only im- plements image tasks, this comparison also focus the vision tasks in Ie.BBecc.
DT
ProtoTree
LSP
LSP-GPT4
0.4
0.6
0.8
1.0
Percantage of Accuracy Pertained
Figure 3: Accuracy retention rate on Out- Of-Distribution variants of (L-Bench-Vision We compute the ratio of test accuracy evaluated on OOD datasets to the original test accuracy. LSP shows strong transferability to OOD data. Notably, LSP with GPT-4V as the learner retains 90-100% of the original test accuracy.
Expressiveness The expressiveness of the learned programs evaluated in Table 2. LSP (GPT4) outperforms ProtoTree with an average accuracy of 95.67% over 10% gain. Considering that GPT/Gemini has never observed the images in our datasets before (curated after their knowledge cutoff), this result suggests LSP is capable of formulating effective predictive rules from previously unseen examples.
Interpretahility We measure the interpretability of LSPs and NSPs by having human raters make predictions based on visualizations of the learned programs (See Appendix for evaluation protocols). This process essentially "transfers" knowledge from models back to human. Notably, many XAI methods fall short of achieving this level of interpretability, with ProtoTree being a rare exception. As summarized in Table 2, the program generated by LSP also demonstrates stronger transferability to human raters, as they are able to largely reproduce the predictions following rules learned by LSP.
In contrast to traditional NSP models that rely parametric memory, L.SP utilizes language instructions to encode knowledge. This strategy significantly enhances robustness against variations in visual attributes (domain shifts). To verify this advantage, we examine the transferability of the learned programs to Outtof--istributtion (OOD) data, constructed using GPT-4V (See Appendix for details) As shown in Figure 3, LSP demonstrates exceptional resilience domain shifts, compared with ProtoTree.
Generalization under Domain Shift
5.3 COMPARISON WITH PROMPT OPTIMIZATION METHODS
Since there exists a variety of PO method that primarily differ in the search algorithm, we select one most representative method from each major category: Monte Carlo sampling (APE) (Zhou et al.,
8

---

Published as a conference paper at ICLR 2025
Table Classification accuracy comparison with Prompt Optimization methods on LL-Beuc--Language Key findings: (1) LSP achieves ~ 6% accuracy gain over the second best method, PromptAgent, with comparable search and inference costs. (2) Across synthetic Decision Tree datasets categorized by increasing complexity of oracle decision rules (Easy, Medium, Hard), LSP consistently outperforms other methods in maintaining high accuracy levels. demonstrating its superior ability to reverse-engined complex rules from observed data.
Tex Beckkaak
Syrankk
Cattie
Mabal
Seadk
DT-Holan
DT-lles
Waceeg
Srulan
0.43
15:48
251364
0.44
5009
1/6
701T 176
3033 330
2722 4276
57.22
4037 4.6
2.3
25.344 1/
1253
21033
180.00 039
1660 471
78.5 11.00
96.11 438
41.11446
1600 350
24.7
58.3 2.53:10
Dogt 2129
12.0
210956
9:18
LSe (Danl
1833
2534
0.b
1936 895
96300 1228
66,0
441
oLI 141
:6755:444
60.00 6442
Thahhsep a pao er opintnics rndedd We sky rnted LiNG Sox Appondix oorass deads
Table 4: Classification accuracy comparison with Prompt Optimization methods on IL--Becc-- Vision. LSP achieves an average accuracy of 96,83% which is ~ 20% higher than the 2nd best method (APO).
Vision Renchmark
Palwceld
Methed
Monn
Fine-I
Fine-2
Drgon-1
Daion-2
Flectrio-1
Flectric-2
Water-
APE (Zhos et al., 2022)
47.45
60.00
0.00
38.00 +: 18.00
43,33 +: 3.33
42,50 :: 7,50
53.33 4: 0.00
25.00 + 15,00
70.00 15,00
OPRO (Yang at 2023g)
28.09
13.33
0.00
20.00
0.00
30.00 10,00
25.00 1 0.00
53.33 1. 20,00
25.00 0.00
30,00 0,00
APO (Pryaat et 2023)
76.38
70.00
16.67
58.00
96.67
77.50 2.50
90.00
10.00
67.50
75.00
(Singh all, 2023)
67:20
60.00
0.00
50,00
2.50
$3.33 0.00
65.00
PromptAgest
2023)
66.33
40,00
56,00
4.00
20,00
(Oars)
96.83
93.33 0.00
92.00 0.00
0.00
100.00
0.00
100.00
95.00 5,00
97,50 2,50
2022), evolutionary search (ORPO) (Yang et al., 2023a), beam search (APO) (Pryzant et al., 2023), and tree search (PromptAgent) (Wang et al., 2023). We also adapt TreePrompt (Singh et al., 2023) a Pre-LLM method that fits classic decision tree to a set of pre-defined prompts to LLMs. Since the main bottleneck for PO methods is the candidate evaluation, we follow existing works and set the same maximum number of candidate proposals for all methods (100 candidates).
The empirical results indicate that incorporating explicit structures significantly enhances performance of the programs on predictive tasks: LSP consistently outperforms all vanilla prompt optimization methods, with considerable margin of 20. 20.09% and 4.89% over the 2nd best methods on vision and language tasks respectively. The advantages of integrating structured learning are twofold: (1) It simplifies the learning process: LSP benefits from divide-and-conquer approach where each M-M-mld node focuses solely on extracting predictive rules for a specific subset of the data. (2) It streamlines the inference process: We observe that LLMs tend to exhibit hallucination as the complexity of the instructions increases (c.g., multiple conditional clauses. In contrast, LSP mitigates this issue by ensuring that each LLM module contains simpler, more manageable instructions.
Results
Search cost analysis A key advantage of the structured prediction approach in LSP that theo- retically, it can reduce inference costs when executing oracle decision rules. This efficiency arises because, during prediction, only small subset of branches is executed for a given test input, and the prompt on each branch is also much simpler due to divide-and divide-and-conee and-conquer. Consequently, we observe empirically that LSP's search and inference costs are comparable to those of various prompt optimization baselines (Table 3). For more detailed analysis, please refer to Appendix A.4.
ABLATION STUDY
Convergence of LLM-Symbolic Program LSP LSP organizes instructions into a tree-based structure. Such wwride-and-conque strategy simplifies the learning process. To verify this, we also plot the training trajectories for LSP across various tasks. The training trajectory indicates the how fast model fits the observed examples. As Figure 5 demonstrates, LSP not only converges faster but also achieves higher final accuracy compared to models that use unstructured prompting techniques.
Different node scoring functions Table 5 summarizes the performance of LSP using three different node scoring functions: (1). Error count. (2). Prediction accuracy. (3). Random scoring. The results suggest that error count performs more consistently across different tasks.

---

Published as a conference paper at ICLR 2025
100
150
80
40
0.5
Ted
0.2
20
C21T-3.5
Gamre-V GPT-4V
GPT-4
01-Mfadd
Wanning Waterttrah
0.2
0.3
0.4
0.5
(a) Language Tasks
(b) Vision Tasks
(c) Program Depth
(d) Program Sparsity
Figure 4: (a, b): Stronger LLMs better LSP learners. these experiments. we keep the inference LLM fixed (GPT-3.5 for text and Gemini-V for images) while swapping the learner LIM with GPT-4. With its larger parameter count, GPT-4 consistently achieves better performance in learning LSPs. (c, d): Statistics of discovered programs. Averaged from the Language tasks, the resulting I.Pss are generally shallow and sparse, indicating that the final prediction can be reached within only few steps.
LSP (Qurs)
LSP (Curs)
LSP (Ours)
LSP JOurs]
0.50
APC
0.80
APD
APD
0.8
APO
0.75
0.75
Accuncy
0.70
6.6
3.70
0.65
2.55
0.60
0.75
0.4
0.60
0.55
0.70
0.2
Round
Round
Round
(a) COBCCCB-WWiii
Waxwing
(b) CUB-CUUBBNTNN JUB-atttrhh
(c) -UB-Blackbird
(d) DT-Hard
Figure 5: Convergence of different algorithms across time. We plot the trajectory of training accuracy against the number of optimization rounds. The API model is GPT-3.5. (1). LSP converges substantially faster than vanilla prompting: (2). The search process does not introduce extra variances.
Robustness to meta-prompts LLM's behavior is highly sensitive to prompt formulation, where even minor variations in prompts might lead to significantly different outcomes. To assess the robustness of LSP's performance against variations in the meta-prompt the prompt used by the learner LLM generate rules
conducted experiments with three alternative prompts. These prompts were paraphrased versions generated by distinct LLMs (visualized in Appendix A.5). The results, presented in Table 5, indicate that LSP's performance remains consistent across all meta- prompt variants, demonstrating robustness to prompt formulation.
Complexity of discovered programs We found that the complexity of programs devel- oped by LSP is fairly manageable: Most pro- grams can reach a final prediction within just three steps, illustrated in Figure 4c, and the tree structures tend be sparse, shown in Figure 4d. These observations confirm that although theoretical maximum tree expansion could grow exponentially with depth, in prac- tice, LSPs operate effectively without requiring overly complex structures.
Table 5: Comparison of Different Node Scoring Functions three tasks from IL- (L-Bench-Lee Language De- spite its simplicity, error count achieves performance compared to alternative metries.
consistent
Node Scoctnn
DTillard
Warwing
Waterthuuh
Ransum
70,50 11:11
62.22 + 438
51.77 + 1.36 $4.44 4 0.70
Accuracy
80.33 e: 18.37
66.11 7.56
Emmor Count (LSP)
96.35 à 0.55
0535 2 417
62.50 1 0,33
Meta Prompt
DT--ard
Waxwing
Waterthrush
Pangturase11
97.50 +: 2.12
65.00 = 4.91
66.11 3.14
Panghrase-2
98 98.50 0.7.1
61.67
2.36
62
1.03
Panghrrans33
90.33
0.62
62.78
2.83
63.80 0.799
Original (LSP))
96.83 + 0.8
66.83
4.17
62.50 0.85
CONCLUSION
This work aims revitalizing the concept of Neuro- Sauoolyymoolic Programming in the era of Large Language Models. We demonstrate that pretrained LLMs can implement powerful symbolic programs that are expressive, interpretable, and easy to train. Additionally, we introduce the Instruction Learning Benchmark (IL- (LL-Benchmark,, which consists of suite of vision and language datasets designed to evaluate instruction learning algorithms. We hope that our proposed framework will inspire new developments in interpretable learning methods during the LLM era. We regard our study as an initial step in the research on I.LM-Symbllic Programs. Accordingly, acknowledge the limitations of the current method in Appendix Section A.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
This work is partially supported by NSF 2048280 and 2331966.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Griffin Adams, Alexander Fabbri, Faisal Ladhak, Eric Lehman, and Noémie Elhadad. From sparse to dense: Gpt-4 summarization with chain of density prompting. arXiv preprint arXiv:2309.04269) 2023.
Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross. Towards better understanding of gradient- based attribution methods for deep neural networks. arXiv preprint 1.Xix:1711.06000 2017.
Andrew Bai, Chih-Kual Yeh, Pradeep Ravikumar, Neil YC Lin, and Cho-Jui Jui Hsieh. Concept gradient: Concept-based interpretation without linear assumption. In ICLR, 2023.
Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, Yisong Yue, al. Neurosymbolic programming. Foundations and Trends@ in Programming Languages, 7(3):158- 583, 2021.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd aem sigkdd international conference knowledge discovery and data mining, pp. 785-794, 2016.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jenry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 14168, 2021.
Guofeng Cui and He Zhu. Differentiable synthesis of program architectures. Advances in Neural Information Processing Systems, 34:1 11:11122-11133 2021.
Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers. In Advances in Neural Information Processing Systems, pp. 6967-6976. N
Mingkai Deng, Jianyu Wang, Cheng-Ping Hsich, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing. and Zhiting Hu. Riprompt: Optimizing discrete text prompts with reinforcement learning. arXiv preprint arXiv:2205. 12548, 2022.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems, pp. 592 603. NeurIPS, 2018.
Yijiang River Dong, Lara Martin, and Chris Callison-Buree Burch.. Corruus Code-based structured prompt- ing for neurosymbolic story understanding. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 13152-13168, 2023.
Meng Fang, Shilong Deng, Yudi Zhang, Zijing Shi. Ling Chen, Mykola Pechenizkiy, and Jun Wang. Large language models are neurosymbolic reasoners. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38. pp. 17985-17993. 2024.
Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rock- täschel. Promptbreeder: Self-referential self-improvement via prompt evolution. arXiv preprint arX1v:2309.16797,, 2023.
Nicholas Frosst and Geoffrey Hinton. Distilling neural network into soft decision tree. arXiv preprint 1 109784, 2017.
Tanya Goyal, Junyi Jessy Li, and Greg Durrett. News summarization and evaluation in the era of gpt-3. arXiv preprint arXiv:2209. 12356, 2022.

---

Published as a conference paper at ICLR 2025
Yash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh, and Stefan Lee. Counterfactual visual explanations. In International Conference on Machine Learning, pp. 2376-2384. ICML, 2019.
Qingyan Guo, Rui Wang. Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint arXiv:2309.0855 085322 2023.
Trevor Hastie and Robert Tibshirani. Generalized additive models. Chapman and Hall/CRC, 1990.
Lisa Anne Hendricks, Ronghang Hu, Trevor Darrell, and Zeynep Akata. Grounding visual explana- tions. In ECCV. ECCV, 2018.
Cheng- Yu Hsieh, Chan Yeh, Xuanqing Liu, Pradeep Kumar Ravikumar, Seungyeon Kim, Sanjiv Kumar, and Cho-Jui Hsieh. Evaluations and methods for explanation through robustmess analysis. In International Conference on Learning Representations. ICLR, 2021. URL https: //openreview net/ wftrrooorrieeeeeeeeeeeeo 4xxpdxx
Cho-Jui Hsieh, Si Si, Felix X Yu, and Inderjit S Dhillon. Automatic engineering of long prompts. arXiv preprint arXiv:2311.1011 2023.
Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, al. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav). In International Conference on Machine Learning, pp. 2673-2682. ICML, 2018
Pang Wei Koh, Thao Nguyen, Yew Siang Tang. Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International conference on machine learning, pp. 5338 5348. PMLR. 2020.
Tin Kramberger and Božidar Potočnik. Lsun- Stan--tanffrd car dataset:
enhancing large-scale image datasets using deep learning for usage in gan training. Applied Sciences, 10(14):49) 2020.
Max Losch, Mario Fritz, and Bernt Schiele. Interpretability beyond classification output: Semantic bottleneck networks. arXiv preprint 1rXiv:1907.10882, 2019.
Scott Lundberg. A unified approach to interpreting model predictions. 2017.
arXiv preprint
Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi. Fine-grained visual classification of aircraft. arXiv preprint 13xiv:1306.5155. 2013.
Yao Ming, Panpan Xu, Huamin Qu, and Liu Ren. Interpretable and steerable sequence learning via prototypes. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 903 913, 2019.
Meike Nauta, Annemarie Jutte, Jesper Provoost, and Christin Seifert. This looks like that, because... explaining prototypes for interpretable image recognition. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 456. Springer, 2021a.
Meike Nauta, Ron Van Bree, and Christin Seifert. Neural prototype trees for interpretable fine-grained image recognition. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 14933-14943 2021b.
Maria-Elena Nilsback and Andrew Zisserman. Automated flower classification over a large number of classes. In 2008 Sixth Indian conference on computer vision, graphics & image processing, pp. 722-729 IEEE, 2008.
Tuomas Oikarinen, Subhro Das, Lam M Nguyen, and Tsui-Wei Weng. Label-free concept bottleneck models. arXiv preprint 2rXiv:2304.06129, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances neural information processing systems, 35:27730- 27744, 2022.
Pocket Pair. Palworld, 2024. URL https: //o::///nn.. wik. http:/ppd........iiiie/pe world.
12

---

Published as a conference paper at ICLR 2025
Vitali Petsiuk, Abir Das, and Kate Saenko. Rise: Randomized input sampling for explanation of black-box models. arXiv preprint arXiv:1806.07421, 2018.
Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with" gradient descent" and beam search. arXiv preprint 0334933 2023.
Dongqi Pu and Vera Demberg. Chatgpt vs human-authored text: Insights into controllable text summarization and sentence style transfer. arXiv preprint arXiv:2306.07799 2023.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135 1144. ACM, 2016.
Ameesh Shah, Eric Zhan, Jennifer Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri. Learn- ing differentiable programs with admissible neural heuristics. Advances in neural information processing systems, 33:4940-4952, 2020.
Taylor Shin, Yasaman Razeghi, Robert Logan IV, Eric Wallace, and Sameer Singh. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprint arXiv:2010.1 15980, 2020.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. International Conference on Machine Learning, 2017.
Chandan Singh, John Morris, Alexander M Rush, Jianfeng Gao, and Yuntian Deng. Tree prompting: Efficient task adaptation without fine-tuning. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 6253-6267, 2023.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328. PMLR, 2017.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc Le. Ed H Chi, Denny Zhou, et al. Challenging big-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.0926: 2022.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, dean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: family of highly capable multimodal models. arXiv preprint 2r 1180, 2023.
Trieu and Thang Luong. Alphageometry: An olympiad levell ai system for geometry, 2024.
Jasper van der Waa, Marcel Robeer, Jurriaan van Diggelen, Matthieu Brinkhuis, and Mark Neerincx. Contrastive Explanations with Local Foil Trees. In 2018 Workshop on Human Interpretability in Machine Learning (WHI). WHI, 2018.
Grant Van Horn, Steve Branson, Ryan Farrell, Scott Haber, Jessie Barry, Panos Ipeirotis, Pietro Perona, and Serge Belongie. Building bird recognition app and large scale dataset with citizen scientists: The fine print fine-grained dataset collection. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 595-604, 2015.
C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie The caltech-uesd birds-200-2011 dataset. Technical Report CNS-TR TR-2011-000001 California Institute Technology, 2011.
Ruochen Wang, Sohyun An, Minhao Cheng, Tianyi Zhou, Sung Ju Hwang, and Cho-Jui Hsieh. One prompt is not enough: Automated construction of a mixture-of-expert prompts. In International Conference on Machine Learning, 2024a.
Ruochen Wang, Ting Liu, Cho-Jui Hsieh, and Boqing Gong. On discrete prompt optimization for diffusion models. In International Conference on Machine Learning, 2024b.
Xinyuan Wang, Chenxi Li, Zhen Wang, Fan Bai, Haotian Luo, Jiayou Zhang, Nebojsa Jojic, Eric P Xing, and Zhiting Hu. Promptagent: Strategic planning with language models enables expert-level prompt optimization. arXiv preprint 2Xiv:2310.16444 2023.
13

---

Published as a conference paper at ICLR 2025
Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganch Kordi, Amirreza Mirzaei, Anjana Arunkumar, Arjun Ashok, Arut Selvan Dhanasekaran, Atharva Naik, David Stap, et al. Supper-naturalinsttuciiosss Generalization via declarative instructions on 1600+ nlp tasks. arXiv preprint arXiv:2204.07705, 2022.
Chenrui Wei, Mengzhou Sun, and Wei Wang. Proving olympiad algebraic inequalities without human demonstrations. arXiv preprint 24XXv:24006.42299 2024.
Hanwei Xu, Yujun Chen, Yulun Du, Nan Shao, Yanggang Wang, Haiyu Li, and Zhilin Yang. Gps: Genetic prompt search for efficient few-shot learning. arXiv preprint arXiv:22 2tt.22200.1704.. 2022.
Chengrun Yang. Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoe Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. arXiv preprint arXiv2230.004409, 2023a.
Sen Yang, Xin Li, Leyang Cui, Lidong Bing, and Wai Lam. Neuro-symbolic integration brings causal and reliable reasoning proofs. arXiv preprint arXiv:2311 1.09802, 2023b.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan.
Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Mert Yuksckgonul, Maggie Wang, and James Zou. Post-hoc concept bottleneck models. arXiv preprint arXiv:2205, 15480, 2022.
Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schuurmans, and Joseph E Gonzalez. Tempera: Test-time prompting via reinforcement learning. arXiv preprint arXiv:221 18800 2022.
Tianyi Zhang, Faisal Ladhak, Esin Durmus, Percy Liang, Kathleen McKeown, and Tatsunori B Hashimoto. Benchmarking large language models for news summarization. Transactions of the Association for Computational Linguistics, 12:39-57, 2024.
Zhihan Zhang, Shuohang Wang, Wenhao Yu, Yichong Xu, Dan Iter, Qingkai Zeng, Yang Liu, Chenguang Zhu, and Meng Jiang. Auto-instruct: Automatic instruction generation and ranking for black-box language models. arXiv preprint arXiv:2310.13127, 2023.
Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. arXiv preprint M.Xiv:2211.01911 2022.
Luisa M Zintgraf, Taco S Cohen, Tameem Adel, and Max Welling. Visualizing deep neural network decisions: Prediction difference analysis. arXiv preprint arXiv: 1wX:::1:22000. 702.04595 2017.
14

---

Published as a conference paper at ICLR 2025
A SUPPLEMENTAL MATERIAL
Organization
The appendix file is organized as follows:
A.1 More details on related work.
A.2 More details on II-BBecc.
A.3 Qualitative analysis of discovered programs.
A.4 Analysis on the inference efficiency advantage LSP.
A.5 Additional ablation study cross model performance.
.
A.7
Complete learning algorithm used in LSP.
A.8
Implementation details.
A.9
Construction of
data for Palworld datasets.
A.10 Human evaluation protocols.
A.11 Known limitations of LSP.
A.12
Social impact statement.
A.13
License statement.
Table 8 Overview of all tasks in II.-Bench.
A.1 MORE DETAILS ON RELATED WORK
Interpretable machine learning Although neural networks are immensely expressive, they provide no insights into its internal decision making mechanism. In the quest of making model predictions interpretable, research has broadly categorized methods into two main types: post-hoc and intrinsic. Post-hoe methods provide insights into how pretrained model behaves, usually by highlighting important features used for decision making (Zintgraf et al., 2017; Petsiuk et al., 2018; Dabkowski & Gal, 2017; Shrikumar et al., 2017; Sundararajan et al., 2017; Ancona et al., 2017) or provide counterfactual explanations (Dhurandhar et al., 2018; Hendricks et al., 2018; van der Waa et al., 2018; Goyal et al., 2019; Hsieh et al., 2021). Beyond attribution in the feature space, some methods can also be generalized to the space of higher level concepts (Kim al., 2018: Bai al., 2023). However, all these methods aim to highlight important features while not being able to recover the entire decision making process of neural networks.
On the other hand, intrinsic methods integrate interpretability directly into the model's architecture, making them naturally interpretable by design. Traditional Methods include Decision Trees (Chen & Guestrin, 2016) and Generalized Additive Models (GAMs) (Hastie & Tibshirani, 1990) offer strong interpretability, yet often not expressive enough. Concept bottleneck model adds hidden layer in neural network, where neurons represent some predefined concepts to gain interpretability (Koh et al., 2020; Losch et al., 2019; Yuksekgonul et al., 2022; Oikarinen al., 2023). While this approach facilitates attribution of concepts, it does not provide a comprehensive decision rule, and the concepts need to be predefined by human experts. In contrast, LSP directly learns all interpretable modules (LLM prompts) from data without relying on human prior knowledge. Furthermore, LSP fully reveals its decision process through learned prompts and program structure, while concept-based methods only partially expose the decision process. Neurosymbolic Programming (NSP) (Chaudhuri et al., 2021; Shah et al., 2020; Cui & Zhu, 2021; ; Nauta et al., 2021b) represents an innovative blend, combining deep learning's 's data handling capabilities with symbolic reasoning to foster both performance and transparency. Despite early promises, NSP suffers from an inherit trade-off between expressiveness (more NN modules) and interpretability (more symbolic modules). Moreover, they are often expensive to train due to co-optimization of program architecture and parameters of the NN modules (Shah al., 2020; Cui & Zhu, 2021).
Prompt Optimization prompts. Recent advancements have aimed to automate this process, reducing the need for human effort through prompt optimization (Shin et al., 2020; Zhou et al., 2022). While pioneering efforts mainly directed towards various discrete optimization algorithms (Shin al., 2020; Deng et al., 2022; Zhang et al., 2022; Wang et al., 2024b), it has been noted that advanced LLMs can revise prompts similarly to human engineers (Zhou et al., 2022; Pryzant et al., 2023; Wang al., 2024a).
The essence of utilizing generative language model lies in crafting effective
15

---

Published as a conference paper at ICLR 2025
Since these initial efforts, significant body of research has emerged, exploring various search algorithms including Monte Carlo Sampling (Zhou et al., 2022), beam search (Pryzant et al., 2023), evolutionary search (Yang et al., 2023a; Fernando et al., 2023; Xu et al., 2022; Guo et al., 2023; Hsieh et al., 2023), and tree search (Wang et al., 2023). However, existing methods often treat the prompt as single entity without explicit structure. From this perspective, prompt optimization methods can be seen as simplified instances of L.PPs, where the program consists solely of one LLM module. While this simplification has shown promising results, as task complexity increases, the explicit structuring within LSPs allows them to encode knowledge from data. This provides substantial advantages over conventional prompt optimization methods. The only exception is TreePrompt (Singh et al., 2023), developed before the LLM era. TreePrompt first pre-generates a set of prompts as attributes and fits decision tree on top of them. On the other hand, LSP aims at establishing a principled hybrid between LLMs and NeuroSymbolic Programming, which substantially differs from traditional decision tree algorithms in program structure search, module definition, module learning method, and extendability, Concretely, LSP uses progressive tree search algorithm to search for program structures; Moreover, all LLM modules are fully optimized by LLMs using the proposed rule learning prompting method; The LLM module each node trained to fit subset of data assigned to it instead of capturing the full data distribution, making the learning task much simpler. Similar to NSP, LSP framework also enjoys great extendability, allowing to seamlessly incorporate extra modules (either learned or manually defined) to the search space to include more complex and tailored programs for new tasks. Empirical results also suggest that LSP achieves substantial gain over previous prompt optimization method.
Augmenting LLMs with Neural-Symbon Solvers Symbolic Al encompasses diverse set of methods and tools suitable for various applications. Although prior work has explored combining symbolic approaches with LLMs, these efforts target distinct tasks compared to LSP (Dong et al., 2023; Fang et al., 2024; Yang et al., 2023b). For instance, Dong et al. (2023) focuses on enhancing LLMs' story comprehension ability by converting storylines into code, while Fang et al. (2024); Yang et al. (2023b) augment LLMs with external symbolic solvers improve accuracy. These approaches are not applicable to the Intepretable Learning task that our work addresses.
A.2 MORE DETAILS ON IL-BENCE
A.2.1 DATA CURATION AND STATISTICS
Symbolic tasks
For symbolic tasks, we use ش to represent input variables, with values denoted by Aj. Bj. Cy.... The label for each data point takes values from 0, .., N - 1. Inspired by the natural alignment of many decision-makiin trees to generate labels for each data point.
processes with tree structures, we use synthetic decision
Each level of the decision tree processes one variable, and leaf nodes are assigned so that labels are evenly distributed. The dataset is generated by randomly sampling a value for each variable and then passing the resulting example through the decision tree. The parameters M and N are predefined to control task difficulty: more variables increase the complexity of the underlying rules, making the task more challenging for the model. This setup allows for automatic generation of symbolic tasks that can be extended to arbitrarily high levels of difficulty.
Language tasks For the initial version of IL- et al., 2011) to construct text classification tasks, though the curation method presented here can be readily applied to convert any visual classification dataset (c.g., Stanford Cars, Dog Breeds, Food Items (Maji et al., 2013)), which we plan to add in future relcases. CUB is a fine-grained visual classification dataset comprising visually similar bird subspecies, making it widely used in Pre-LLM-era interpretability research.
primarily use the CUB dataset (Wah
To convert this dataset into text classification tasks, we use GPT-4 as the captioner. Since an image contains far richer information compared to a text modality, captioning images individually risks missing fine- ane-grained details that are crucial for distinguishing between bird subspecies, which could render the task ill-defined. To address this, we generate contrastive captions: for each target image, we sample images from other classes as contrastive examples. This contrastive approach is applied for every class, and all resulting captions are concatenated to form the input for the new text classification dataset. To avoid information leakage through label names, class names (e.g.. North_ Ame r can Waterthrush) replaced with symbols (e.g., class_1).
16

---

Published as a conference paper at ICLR 2025
Empirically, we confirmed that the curated datasets are not solvable in zero-shot setting: all tested LLMs in our experiments could not outperform random guessing without learning the underlying rules.
Vision tasks To curate images that are unfamiliar to the MLLMs, we use a regional Pokémon-style video game called "Palworld," " which contains approximately 150 creatures ("Pals") of different types (e.g., water, fire, electric). To make the task challenging, we group visually similar Pals into the same dataset. Since these visually similar Pals often belong to the same type, we name each dataset according to the type (e.g.. fire fire_1). All images are collected via screenshots of publicly available in gaga footage on YouTube. Similar to the language tasks, Pal names are replaced with symbols to prevent information leakage.
A.2.2 TASK DESCRIPTIONS AND EXAMPLES
Table 8 provides overview of each task in IL-Bench, including task name, input modality, descrip- tions, and example data points.
A.3
QUALITATIVE ANALYSIS OF DISCOVERD PROGRAMS
If x1
B1, and x3 B2,
then label is bar.
If x1 A2, x2 B1, and x3 C2, then the label is han. Otherwise, none of the above conditions met, the lebel foo.
foo
x3 foo.
labe
If x2 B2 and x3 CZ, then the label
is han.
If x1 Al and x3 CI, then the label
Kelpsea
sin
If x1 A1, x2 B2, and C2, then the label is han. Otherwise, if any of these conditions are not met, the label is foo.
If x2 B2 and x3 C1, then the label
Figure 6: Example program discovered by LSP on DT-Harr task.
In this section, we provide qualitative analysis of the discovered programs. We use programs discovered from DT-Hard task as illustrating example, as knowing the oracle rules for this task allows us precisely identify the reasons for both success and failure.
The data for the DT-Hard task are generated using the following rules:
Label foo when x1=Al, x2=B1, x3=C1 x1=A2, x2=B2, x3=C1
Label bar when x1=A1, x2=B1,
x3=C2 or x1=A2, x2=B2, x3=C2
Label sin when x1=A1, x2-B2,
x3=C1 x1-A2, x2-B1, x3=C1
Label han when x1-A1, x2-B2, x3-C2 or x1-A2, x2-B1,
x3=C2
Figure 6 visualizes an example program discovered by LSP, which achieves 96% test accuracy. Here, nodes are LLM modules with rules, and edges denote the prediction from the parent node. the rule on specific node cannot cover a test query, it will simply return its parent's prediction. By examining the program, we can observe that it learns to londde-andcooquue
test query: Take the rules at the root node as an example, it first summarizes few rules for label sin, bar and han, but decide classify every other situations foo; This is clearly not accurate, so its child node further refines the rules. Let us use the data point *x1=A1, x2=B2, x3=C1 as an example. At the root node, the nule states " "Otherwia se, the label is feo", which sends this example
17

---

Published as a conference paper at ICLR 2025
to the child node. At this child node, the rule becomes "if x1=A1 and x3=C1, label sin", which sends this example to the left child node, At this leaf node, the rule is "if x2=B2, x3=C1, the the label is sin" ", resulting in the final prediction of sin, which is correct.
From this representative example, the following observations can be made:
The root node initially misclassifies the example as "sin", demonstrating that current LLMs can still make errors when generating predictive rules.
However, this error is corrected by the child node, resulting in an accurate final prediction.
The rules at each node need not be complete, as child nodes are responsible for correctly predicting the subset of data assigned to them.
There exists redundancy between the rules different nodes, this suggests that the learned program could be further simplified using post-hoc algorithms.
A.4 DETAILED COMPLEXITY ANALYSIS OF LSP
LSP follows multi-step decision-makinn process, akin to decision tree. While this might initially suggest an increase inference time, in-depth complexity analysis demonstrates that LSP actually improves inference efficiency.
Inference cost depends on total token count, not number of prompts Assuming network speed is not a bottleneck, the inference cost is primarily determined by the total token count rather than the number of prompts. Although LSP necessitates multiple LLM calls for a final prediction, the individual prompts are significantly simpler and shorter, due to the divide-and-comquer strategy. While LSP requires multiple LLM calls to reach final prediction, each prompt is significantly simpler and shorter due to LSP's divide-and-comquue strategy.
Tree structure of LSP reduces theoretical inference cost Consider an oracle rule represented with N tokens. If represented in a traditional prompt, the inference LLM must process ((N) tokens. By contrast, using LSP's complete binary tree structure, the LLM processes only ONN/ / log D) tokens per test query, where represents the program depth (with some minor template overhead in practice). This is because only one path in the LSP tree are executed for given test input, thereby substantially reduces the inference cost of oracle rules.
Oracle rules are naturally complex and lengthy The oracle rules underlying many datasets, particularly those from IL.BBench, tend to be inherently complex. Such rules are often composed of simpler sub-rules, resulting in longer token sequences. As the complexity of an oracle rule increases, the minimal description length (measured by token count) also grows, naturally raising the inference cost. Importantly, no token limit was imposed on any the baselines, allowing them to introduce more rules if beneficial. However, unstructured learning methods often produce relatively simple prompts that perform worse. In practice, LSP only uses comparable or slightly more tokens than previous SOTA, while is substantially more accurate in captures the complex oracle decision rules.
A.5 ADDITIONAL ABLATION EXPERIMENTS
A.5.1 USING DIFFERENT LLMS TO IMPLEMENT LSPS
The role of LLMs in LSPs is twofold: they serve both as the inference and learning engine of the LLM-modules in the grammar. The learning engine is responsible for summarizing and organizing patterns from observed data samples into clear predictive rules, whereas the inference engine follows the learned program to make predictions on test examples. Natural questions arise: (1). how effective are different LLMs at optimizing LSPs? (2). Is the learned programs interpretable to different LLMs?
LLM as LSP learner We replace the learning engine used in optimizing LSP with various LLMs GPT-3.5, Gemini, and GPT-4 while keeping all other settings consistent with the main experiment. As shown in Figure 4, GPT-4 consistently outperforms other LLMS on both text and vision tasks, while Gemini and GPT-3.5 show similar performance with each other. This reflects their respective capabilities. For specific examples of instructions generated by different LLM optimizers, please see the Appendix.
18

---

Published as a conference paper at ICLR 2025
Table 6: Transferring LSPs learned from one LLM to another. The learned LSPs are generally interpretable across various M. However, larger L.MMs (c.g.. GPT-4) demonstrate a slightly higher consistency in understanding LSPs learned by other LLMs.
Source Model
Task
GPT3.5
Gemini-M
GPT4
DT-Hard
89.75 2 1.25
72.67 = 6.91
87.50 = 1.22
GPT3.5
Waxwing
65.83 + 4.17
52.22
1.57
36.67 = 3,60
Waterthuush
62.30
0.83
64.44
0.79
59.44 1. 3.93
DT-llard
75.50 2.04
80.83 1 1.03
79.17 11.45
Gemini-M
Waxwing
52.78 1: 3.42
58.33 1: 4.91
61.11
10.57
Waterthrush
4.16
54.44 5.50
52.22 0.79
DT--Hard
74.50 9.35
57.67 + 3.01
99.50 + 0.00
GPT4
Waxwing
99.44+55.115
62,22 + 7.49
63.33 4.91
Waterthrush
66.67 1 6.80
68.33 = 2.72
62.78 = 9.06
LLM as LSP interpreter We then test if LSPs created by one LLM could be interpreted by other L.Mss. Table 6 summarizes the performance. The results suggest that LSPs are interpretable across a diverse range of inference models; I. Larger and stronger L.LMs (e.g. GPT-4) demonstrates slight more consistent ability in interpreting LSPs, which aligns their superior instruction-follovinn capacities.
A.6 DIFFERENT PARAPHRASING OF THE META-PROMPT
Here, we visualize the different paraphrased version of the meta-prompt used in Table 5.
Version
Prompt
Paraphrasing-1
Begin by outlining the patterns visible in these exemples; Next, formulate well defined rule that successfully predicts the labels for these examples using these patterns.
Paraphrasing-2 Start by iden and explainiag the patterna found in these examples; Then, propose robust rule that can accurately prediet labels based on the identified patterns.
Paraphrasing-3
Start by iden:ifying the patterns in these examples; then, develop clear rule that acourately forecasts the labela for these examples based on these patterns.
Original
First explain patterna you observe from the exarples; provide 1 high quality zule that can correctly predict the labels of those examples based on those patterns.
Table 7: Different variants of the meta-prompt used by the learner LLM when building LSP. The variants are produced by asking different LLMs to paraphrase the original meta-prompt.
A.7 LEARNING ALGORITHM FOR LSP
The complete pipeline for constructing LSPP summarized in Algorithm and Algorithm 2.
Remarks
Although initially, the complexity of the program expansion might seem exponential the tree depth, a closer examination reveals otherwise: (1). In practice, the trees are typically sparse, meaning that expanding only few branches is often sufficient achieve good performance (Figure 4d). (2). The divide-and-conquer approach ensures that each tree level processes the same amount of data making the evaluation complexity lincar to tree depth.
The above arrangement of the search process does not compromise generality of LSP: For more sophisticated DSL designs, program structure search can be conducted similarly to traditional NSPs, using top-down tree traversal Chaudhuri et al. (2021); Cui Zhu (2021).
19

---

Published as a conference paper at ICLR 2025
Algorithm llaarn :aln__ooule: Learning LLM Module by summarizing predictive rules
1: Input: Proposal size data sample B, learner LLM Mr
2: Initialize an empty list of LLM modules
3: for to do
4: Randomly sample b B
5: Onew summarizazz ze M,
6: + <- {fnew]
7: end for
8: return
Algorithm 2 Complete pipeline of optimizing LSPs
1: Input: Dataset D, beam size d, number of iterations T, inference L.M Mi, learner L.M M₁, expand ratio K, proposal size
2: Initialize Po as an empty program
3: Initialize candidate program set P {po}
4: for = 1 to T do
5: for each program p in P do
6: BBtch evaluation
7: Sample batch B ~ 'D
8:
Evaluate p on B using M;
9:
>
Selecting the most promising node n to expand Assign B the leaf nodes of
11:
Identify the most error-prone leaf node n with assigned subset B,
12:
Extend program p to K new programs by adding top-K LLM modules node 4- learn_ liph__mm_mma_ 1 en,, Bi,
13:
14:
Ptop evaluate and retain top-K $ on B,
15:
Pnew <- extend by assigning each @ E Ptop to node n on program p.
16:
T-PUPnes
17: end for
18: Evaluate and retain the top-d programs from P on D
19:
end for
20:
return The best program from P
20

---

Published as a conference paper at ICLR 2025
Table 8: Overview of Interpretable-Leariins Benchmark. We provide task names, types, sum- maries, number of labels, and one example data point for each task.
Yink
Type
Summary
Laleds
Exampll
Diiltayy
Symbolic
Product labels based on symbollc in- pare. Roles genreseed by small decison uce
"Inpor: "24412:244111 "omppt": "bor"
Symbblii
Predict lubels based symbolic
"Taput; "51=A5,x2-82", "ostput": "baa"
pas. Ruios grncrted malium docieum lecz
Ha
Syndholiz
Predect based
"Inpor: "41=A1:x-+B1:x4411 "oopurt
puss, Rules genersted large
Waxwing
Coption
Clasity Warwing species deserittonn
"Thn brows heed upper body, black mankkrross lighter undorpans, bright socondary wing feathers, smill black Nill yellow sail" "cutpu"" Coodr Wassing"
"Tppot"
Waterheask
Caption
Classity Watertrosh spocics bused description
"Tagut" gay coos,, white axeecillann, dark eyeatape estendias eyc, undorpens long, Watcnteaes"
wings wingten, onane logs" "ougus"
whbtivelly
Jaeger
Caption
Clasiity Jaeger species based on its text description.
"aapot" "Light gresish brows plrmage on the underside, distict sanow white band acmos the tape, kings with duped panten whene speead, tail slightly focked but mostl striight acres" suppst "Long ustld Jaeger
Albaton
Caption
Clasiff Albaros apocios bsaed test descripiion
Dark beows upperpari and puier beown underpats, clongsted and sanow wiag with where traling edge and dusinct tngreiite tps. booked beok with pate bose, light-ollond head with a dark eye pasch and bill winge hold sniggtt in gliding fight. glidin ahome water corvian Unffeen dark brown planage long dender vings, disinct white patem on undersings. white band nea the tips of the underwings, pale or white lead, dark ese patcl." "ouppt"" "Bick footed Albutioss
"ugut"
Blackhinl
Caption
Clasify Blackbind upocios head nen description.
"Bright yellow head. blak botly stamp couica book parchal noal-il like vogctatioo. Hright yellow head, ysllow chez, sold black body escluding head and chest, perched or this bearch Black body. bright yellow beat, stunty bill porched or reed" "ourur": "Yellow bracket Ilackhied
"sppal"
Swallow
Caption
Classity Swulkow douription.
"ipptt
pale throat
pointed sheet till,
Light brown host upper hody white undopatts win: backgmand dhon beok, slack buly stape. Brows and white plunags penthal wine, steud boaly, short dhick nock, cralim-knnhh sill with sinight elge, compad size, unmorted lighter underpart, darker wings and apperparts" "corpar" 'Bank Swilloo
whic inderpero, sitting
Fire1
Detingsish vissally similar fire- oype pols Palwordd
"Inport:
"oopur"" "Asso""
Fire-2
Vision
Ditinguish visudly-simila fire- typ pole from Palwordi
"taput:
"ouputt" "Pyti"
Dragon- Blze-1
Vision
Detingrish visually coloced dragon-cype pals from
"Inpor::
"oopur"" "Elphidron Aqua"
Bragon-
visustly-inn
"ingeet
"ooppr"" "Arragon"
coleed diagon-cype oype from
Electic-1
Distiggiist visualy sinile elecsic- type Falwordd
"Inpott:
"oupput" "Gizzbell"
Elestrie22
Vision
Divingsisk simually curilr electric type pols from Palwordd
Tirput:
"supur" "Uniool"
Watzi
Distiguish vissally sinilar typo polk from Palwerld
"Input::
"oupptt" "Celary"
A.8 IMPLEMENTATION DETAILS
Throughout our main experiment, we use an expansion ratio of 4, batch size of 64, a maximum number of four iterations, and a maximum of 8 candidate (LLM module) proposals for each iteration. The settings for beam search follows that of APO, which uses a beam size of 4 and deploys UCBBan- dits algorithm with sample size of 32 to speedup the candidate ranking Pryzant et al. (2023). The only exception is that for vision tasks, we use a batch size of 4 for cost reduction. The temperature for all API models are set their default (0.7).
LSP
Baselines For all prompt optimization baselines, we set the maximum budget (measured by the number of candidate proposals) to the same number.
For Decision Tree, we use XGBoost library's standard implementation, which operates on raw pixels.
21

---

Published as a conference paper at ICLR 2025
For PretoTree, directly the original implementation, but reduce the maximum depth from 9 to 5, as is faster to train yet achieves better performance on our datasets.
For TreePrompt, we swap the GPT-2 model used in its implementation with the more capable gpt-3.5-turbo for fair comparison with other more recent baselines.
We align the evaluation our baselines.
A.9 CONSTRUCTING
DATASET FOR 1I-BENCI--ISSOO TASKS
(a) Beakon Original
(b) Celaray Original
(c) Incineram Original
(d) Jolthog Original
(c) Beakon Generated
(I) Celaray Generated
(g) Incineram Generated
(h) Jolthog Generated
Figure 7: Comparison between original images (top row) and Out-Or-Distribution images
(botton row) generated by GPT-4V. All images are resized to an unified resolution of 128.
Our OOD dataset is constructed by feeding the original image from the training set to GPT-4 (web version), and ask GPT to generate variant of the input image. The prompt used is shown below. Figure 7 shows a comparison of some example OOD images generated by GPT-4 with original image.
Generate image variant containing the creature in the provided image. keep the key features of this creature unmodified You must show the full body view of this creature.
A. HUMAN EVALUATION PROTOCOL
We conduct user study to access the interpretability of our method and ProtoTree. For both methods, we send (1) the original image datasets and (2) visualizations of the discovered programs to the human raters, and as the human rater to make predictions based on those programs. We then compute the accuracy of their predictions, and report the mean and standard deviations. We select the group of human raters so that they have no background in machine learning research.
A.11 LIMITATIONS
We acknowledge the following limitations, which merit further exploration in future studies. It is important to note that these limitations pertain to the specific, simplified instantiation of the algorithms used in this preliminary study, rather than to the LSP framework itself:
22

---

Published as a conference paper at ICLR 2025
(a) Celaray
(b) Gobfin
(c) Kelpsea
(d) Penking
(c) Prec
the creature the image has white cration light
squetic flying creaturs, label us humanold precominently color with white detalls, and a fin on hnaa,, label
Calenay
the creature has two dongatee blue wings, underbellyy, then label "Celeney" thee the creature has yollow abe "Ceippes.
the character has blue body, pointy and the forehead, label it "Gobiin: If the character has pengui-- beard, lubel "Panicing"
If the creature two main body yellow and primarily cuadrusedal stance, lobel as "Kalpoe."" If the without yallow and primarly lepodaa or has wings, label it "Cdoraa..
LSP
Figure 8: Example programs discovered by LSP (bottom) and ProtoTree (middle). While ProtoTree offers some interpretability by displaying prototype image patches the user, it can be misleading as there is no guarantee that the prototypes are meaningful (e.g. many patches miss the key regions, and there also exists entire branches that overfit the background). In contrast, the programs discovered by LSP accurately capture the characteristics of the creatures and guide the decision-making process step by step.
23

---

Published as a conference paper at ICLR 2025
Domain-Specifie Language Design: A common practice in NSp is to design DSLs suitable for specific tasks. This work presents only a basic example of DSL designed for predictive tasks. Investigating a variety of DSL designs could enable LSPs to excel across broader range of applications.
Program Complexity: Our search algorithm prioritizes accuracy without considering the complex- ity of the resulting programs, potentially leading to redundancies. The complexity of the learned programs could be reduced either through post-processing (akin to code cleaning) or by integrating complexity regularization during the search process.
A.12 SOCIETAL IMPACT
The development and deployment of interpretable predictive models using Large Language Models (LLMs)) have significant societal implications. By enhancing the transparency and interpretability of AI systems, our approach addresses critical concerns related to trust, accountability, and fairness of the decision making process. These improvements are particularly valuable in high-stakes domains such as healthcare, finance, and legal decision-making, where understanding the rationale behind AI decisions is crucial for gaining user trust and ensuring ethical outcomes.
However, as with any AI technology, careful consideration must given to the potential risks of misuse unintended consequences. It is essential continue developing comprehensive guidelines and regulatory frameworks to ensure that the deployment these models aligns with societal values and ethical standards. By promoting transparency and interpretability. approach paves the way for more responsible and beneficial integration of Al into society.
A.13 LICENSE
The open-source code from GitHub used in this paper adheres various licenses like MIT, Apache 2.0, and GPL, ensuring the code's free use, modification, and distribution under specific conditions. The ChatGPT API from OpenAl and the Gemini API from Google are used in compliance with their respective terms of service, which include usage restrictions, attribution requirements, and provisions for commercial use. By following these licenses and terms, we maintain ethical and legal standards utilizing both open-source code and proprietary APIs in our research.
24


Reviews:
[{"review_id": "4aIzaA1rek", "reviewer": "Reviewer_44Us", "summary": "The paper proposes a new framwork, named LSP, for LLM-Symbolic Program combining LLMs with Neurosymbolic programs (NSPs). The main idea of the paper is to consider a prompted LLM as an interpretable unit, enabling the use of NSPs with a minimal domain specific language and thus narrowing this important bottleneck of NSPs. The approach is demonstrated on a proposed Interpretable-Learning benchmark. It includes a comparison with SOTA NSPs as well as some ablation study on the components of the approach. It also include an human evaluation protocol to access the interpretability of the approach.", "questions": "Some questions are in the Weaknesses section.\nOther questions :\n+ Could the following claim could be discussed : the resulting model is inherently interpretable as the prompt s is expressed in natural language ? \n+ How this idea of using LLMs to transforms signals into high-level concepts, how the approach compared to concept induction approach ? To  Concept-based Explanations for LLMs ? \n+ In the following approach, is the decision making process limited to conditional branching and tree-based models ? Is it a strong limitation ? \n+ Can hallucinations can occur for RuleSum ?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strengths of the paper are :\n+ **Clarity** : the paper is well written with a clear and well motivated idea. The paper provides nice illustration that enable a clear understanding of the proposed approach. The addressed research question are also very clear.  Moreover, a thorough description of the proposed framework, including ablation studies and code for reproducibility is provided.\n+ **Originality** : the main originality of the paper is to use prompting and the ability of summarization of LLMs, a method named RuleSum, to obtain concrete rules and to prevent from manually designing operators, one of the bottleneck of NSPs. It is a simple approach but opening the way for LLM-based symbolic programs. The IL-bench is also an interesting contribution of the paper.\n+ **Quality** : The paper is of sufficient quality for the ICLR conference standard.\n+ **Significance** : the paper propose a new approach for interpretable learning, i.e. interpretable and comprehensible decision making process which an important area for XAI and trust in AI.", "weaknesses": "While the core idea is interesting, the paper has several limitations:\n+ a first small concerns is about the title of the paper which is for me not really aligned on the content. The authors use LLMs as learnable building blocks for NSPs but are not interpretable as their own. The title of the paper should be slightly changed to better reflect the true claims of the paper.\n+ **lack of clear definition of the notion of interpretability and of the underlying assumptions** : as the authors tackle the trade-off between expressiveness and interpretability, a clear definition of them should be given. For instance for me, using a minimalist DSL means less expressivity since there are only two operators. The assumption that relying on natural language brings interpretability should also be discussed. The interpretability seems to be linked to the interpretability of the prompts.\n+ a better positioning to recent approach on XAI, in particular concept-based XAI, mentioned in appendix A.1 and Mechanistic Interpretability.\n+ **Generality of the findings**  : the IL-Bench should be more motivated. It is not clear for me what a symbolic task is exactly. Moreover, a large part of the task are classification tasks. What about other tasks regarding the proposed approach ?\n+ What is $Dist$ in equation 1 ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J5va5xxjHU", "reviewer": "Reviewer_fKng", "summary": "The authors in this paper introduce LLM-based Symbolic Programs (LSPs), combining Large Language Models with symbolic programming to create predictive models that balance expressiveness and interpretability. LSPs use LLMs to generate interpretable modules from raw data. With a step-by-step program generation algorithm, the proposed method could generate the symbolic programs. Besides, the authors propose a new benchmark, called IL-Bench, for evaluating interpretable learning tasks. In their evaluation, LSPs outperform traditional methods, offering interpretable, transferable, and generalizable results.", "questions": "Referring to W1, the author may run an additional evaluation of the proposed method with specific open-source LLMs (e.g. LlaMA3.1-8B, LlaMA3.2) that can be run locally. No matter the results, the authors could discuss some potential limitations to making LSP work with locally deployed LLMs.\n\nThe authors claim that the existing LLM benchmark could measure (M)LLM’s IL ability: \"all these tasks are all zero-shot solvable, allowing LLMs to make predictions without additional rule learning. Therefore, these benchmarks are unsuitable for evaluating IL tasks.\"\nMy other questions are:\n\n1. Are datasets from AIPS or/and AlphaGeometry, which contains IMO level mathematical problems, able to be IL benchmark? \nThe authors may discuss the difference between the proposed dataset and the datasets like AIPS or AlphaGeometry in terms of measuring interpretable learning ability.\n\nFYI, AIPS aims to address inequality math problems, and AlphaGeometry aims to address geometrical math problems. Both papers propose a dataset and a problem-solving algorithm. From my point of view, the algorithm is a neural-symbolic method and is similar to LSP, which uses LLM as a module to generate a one-step decision, add a construct for geometry problems, and transform an inequality. Then, designing a high-level search problem to solve the complex problem.\n\n2. Instead of constructing LSP, does SFT or some RL could be applied to LLM to improve the LLM's IL ability?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A new benchmark for interpretable learning tasks, for both vision and text scenarios.\n2. Design a LLM-symbolic program generation algorithm (called LSP by authors) by a program structure search procedure.\n3. Evaluation shows that the LSP significantly outperforms the baselines in the authors' evaluation settings.", "weaknesses": "1. As the authors say, LLM's responsibility is to make decisions in each LLM module in their llm-symbolic programs. Thus, generating a correct LSP relies on the LLM's ability. I am curious whether the proposed method could correspond with other open-source LLMs that could be deployed locally.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p7CfA3QzA7", "reviewer": "Reviewer_ZPkh", "summary": "This paper tackles the challenge of balancing expressiveness and interpretability in predictive models for classification and decision-making. The authors propose LLM-based Symbolic Programs (LSPs) that combine Large Language Models with symbolic programs to bridge this gap. LLMs generate interpretable modules that transform raw inputs into natural language concepts, which are then integrated into decision rules by symbolic programs.\nMoreover, the paper proposes IL-Bench, a new benchmark for the interpretable learning capabilities of LLMs. In experiments, it is demonstrated that LSPs outperform traditional neurosymbolic programs and prompt tuning methods on the proposed benchmark.", "questions": "I was not fully following the reasoning in line 268 -- 286.\nCould you elaborate the following two arguments?\n> Therefore, with a fixed LLM, the set of natural language prompts, ... provides a massive set of interpretable neural network modules for the task.\n\nWhy the prompts can be trivially seen as interpretable neural modules?\n\n> ... the resulting model is inherently interpretable, as the prompt s is expressed in natural language.\n\nWhy the resulting model can be seen inherently interpretable?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The approach to integrating LLMs into DSL-based neuro-symbolic programming approaches is interesting, although the idea itself may be straightforward. \nBy combining Large Language Models (LLMs) with symbolic programs, the authors effectively leverage the strengths of both methods: LLMs for creating interpretable natural language concepts and symbolic programs for incorporating these into decision rules. This hybrid approach not only enhances model interpretability without sacrificing performance but also makes the knowledge easily transferable to humans and adaptable for other LLMs.\nLimitations are discussed in an explicit section.\nIn experiments, the proposed approach outperformed established baselines in multiple aspects, e.g., on OOD examples, expressiveness, and interpretability (transferability).", "weaknesses": "I found the manuscript somewhat challenging to follow due to the absence of consistent examples within the main text. Currently, major examples are relegated to the supplementary materials. To enhance clarity, I recommend incorporating one or two examples directly into the main manuscript and referencing them throughout.\n\nMoreover, a clear problem statement would significantly improve comprehension. Specifically, outlining the input and output parameters before discussing the methodology would be beneficial.\n\nApart from these presentation issues, the experiments appear to demonstrate the efficacy of the proposed approach. However, as I feel I lack sufficient expertise in the baselines, I will defer to other reviewers for a critical assessment of the significance of these results.\n\nMinor Points:\n\nThe structure of the document feels somewhat convoluted. There is an overuse of emphasized text formats (bold, italic, etc.), particularly noticeable on Page 3, which detracts from the core ideas being presented. I recommend retaining emphasis only on the most critical sections and reducing the use of bold and italic text.\n\nEquation 3 could be better explained with a figure that includes a concrete example and details like $\\alpha$ and $y_i$.\n\nThe text size in Figure 8 (f) makes it difficult to interpret. Consider increasing the text size for better readability.\n\nFurthermore, the code is not submitted, making it challenging to assess reproducibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)