# Large Language Models are Interpretable Learners

Ruochen Wang
UCLA
&Si Si
Google Research
&Felix Yu
Google Research
&Dorothea Wiesmann
Google Research
&Cho-Jui Hsieh
Google Research
&Inderjit Dhillon
Google Research Work completed during internship at Google.

###### Abstract

The trade-off between expressiveness and interpretability remains a core
challenge when building human-centric predictive 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. In this paper, we show 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 an interpretable decision rule. 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.

https://github.com/ruocwang/llm-symbolic-program

##  1 Introduction

Learning interpretable predictive models from annotated data remains a key
challenge in human-centric AI. Given input-output pairs $\\{(x_{i},y_{i})\\}$,
the objective is to learn a function $f:x\rightarrow y$ that not only fits the
data accurately but is also interpretable. tIn this context, a strong form of
"interpretable" means that individuals with no prior domain knowledge can
understand and apply the decision rules demonstrated by $f$, facilitating the
transfer of knowledge from AI to humans. This is crucial not only for
enhancing the transparency of AI systems but also for enabling humans to learn
from these models, empowering various human-in-the-loop applications such as
scientific discovery, material synthesis, and automatic data annotation
(Chaudhuri et al., 2021).

Consider an exemplar task of classifying species in Palworld (Pair, 2024) \- a
newly released Pokemon-style game - based on a 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 as
species characteristics, from data. The algorithm we 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 can be viewed as discovering interpretable knowledge (e.g., the
properties of a species in Palworld) from the data.

Despite extensive research, the problem of developing a fully interpretable
predictive model has not been fully addressed. Traditional methods often face
a 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 (Ribeiro et al., 2016), they do not clarify
the underlying decision-making processes and have no control over the learning
process. Directly learning interpretable models like (locally) linear, tree-
based 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 and Zhu, 2021; Nauta et al., 2021b) offer a
promising solution by modeling the decision rule as a 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 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 and 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 is that (Multimodal) LLMs encompass a
variety of powerful, conditional probabilistic sub-models. These models share
a 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 to
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 learned through LLMs. Our approach leverages a
minimal Domain-Specific Language (DSL) set with only two operators: prompted-
LLM and conditional branching, yielding a classic decision-making process
structured as trees. We then propose a learning algorithm to incrementally
learn the tree using LLMs with prompt optimization. To thoroughly evaluate the
efficacy of LSPs, we construct the Interpretable-Learning-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.

##  2 LLM-Symbolic Programs

Figure 1:  Illustration of LLM-Symbolic vs. Neuro-Symbolic Program on
interpretable learning task. The goal is to develop a model that allows humans
with no prior knowledge to replicate AI’s decisions by following the same
rules as the model. While NSP (Top right) offers a 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.

This section explains our proposed framework: LLM-Symbolic Programs. Section
2.1 reviews Neurosymbolic Learning method. Section 2.2 discusses utilizing LLM
to implement interpretable programs, including a connection between prompted-
LLM and interpretable unit (Section 2.2.1), the Domain Specific Language
(Section 2.2.2) and learning algorithm (Section 2.2.3).

###  2.1 Preliminaries on Neurosymbolic Learning

NeuroSymbolic Programmings (NSPs) (Chaudhuri et al., 2021; Shah et al., 2020;
Cui and Zhu, 2021; Frosst and Hinton, 2017) seek to couple classical symbolic
methods with contemporary neural networks to build expressive and
interpretable models. The learning method for NSPs is often characterized by
(1) a Domain Specific Language (DSL) that specifies available operations of
the program and (2) a learning algorithm for finding the best instance. The
resulting programs are structured, neuro-symbolic terms that follow the syntax
specified by the DSL.

##### Domain-Specific Language (DSL)

DSL in NSPs comprises manually defined operators, including interpretable
symbolic (e.g. if-then-else) and expressive neural components (e.g. cnn(x,
$\theta$)). These operators can be chained to construct various tree-
structured programs, a.k.a. computation graphs. Eq (1) presents an example DSL
used to construct the program for predicting the creature species in Figure 1.
Here, $x$ and $c$ represents inputs and constants, and $\alpha$ denotes a sub-
program:

$\displaystyle\alpha::=x\mid
c\mid\texttt{Add}(\alpha_{1},\alpha_{2})\mid\texttt{Mul}(\alpha_{1},\alpha_{2})\mid\text{If
}\alpha_{1}\text{ Then }\alpha_{2}\text{ Else
}\alpha_{3}\mid\texttt{cnn}(x,\theta)\mid\texttt{Dist}(\alpha_{1},\alpha_{2}).$
(1)

##### Co-optimization of program structure and learnable parameters

In NSPs, the construction of a program involves solving a 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 and Zhu, 2021),
distillation (Frosst and Hinton, 2017) and meta-learning (Chaudhuri et al.,
2021).

##### Limitations

While the integration of symbolic and neural components in NSPs represents a
promising innovation, the incorporating of neural modules inevitably
introduces black-box components and makes the program 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 and Zhu, 2021), or employing prototype learning to derive relatively
interpretable neural modules (Nauta et al., 2021b; Ming et 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 to represent the
concept of each neural module by a set of representative samples, which is not
guaranteed to success.

###  2.2 LLM-Symbolic Programs

This section explores how LLMs can effectively be utilized to implement NSPs’
modules that are expressive, interpretable, and straightforward to learn with
LLMs.

####  2.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
inevitably requires complex and non-interpretable components, such as neural
networks. Even human perception remains non-interpretable, as we lack a
complete understanding of how the brain processes signals. However, The
following analysis suggests that pretrained LLM offer a potential avenue to
bridge this gap.

##### 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_{t}\\}_{t=1}^{T}$

$\displaystyle P(w_{1},w_{2},\ldots,w_{T})=\prod\nolimits_{t=1}^{T}P(w_{t}\mid
w_{t-1},w_{t-2},\dots,1)=f_{\theta}(w_{t}\mid w_{1},w_{2},\ldots,w_{t-1}),$

where the conditional probabilities are parameterized by an auto-regressive
model $f(\cdot;\theta)$ (e.g. Transformer) and each word $w_{t}$ is predicted
given all the preceding tokens. The pretraining objective minimizes the
following negative log-likelihood:

$\displaystyle\min_{\theta}\mathcal{L}(\theta)=-\sum\nolimits_{t=1}^{T}\log
f_{\theta}(w_{t}\mid w_{t-1},\dots,w_{1}).$ (2)

A key observation from Eq. (2) is that the training process optimizes a
“SuperNet" of conditional probabilistic models (CPM), each defined by an
instruction $s$: $f_{s,\theta}(y|x)=f_{\theta}(y\mid x,s)$, where $x$ is the
input and $s$ is the instruction for a particular task. Therefore, with a
fixed LLM, the set of natural language prompts, denoted as $\cal{S}$, provides
a massive set of interpretable neural network modules for the task. For a
given dataset $\\{(x_{i},y_{i})\\}_{i=1}^{n}$, finding the best prompt to
minimize the empirical loss, $\min_{s\in{\cal S}}\sum_{i=1}^{n}{\cal
L}((f_{s,\theta}(y_{i}\mid x_{i})))$, can be viewed as a form of learning, and
the resulting model is inherently interpretable, as the prompt $s$ is
expressed in natural language.

This connection reveals that prompt optimization within the natural language
space offers a form of interpretable learning that simultaneously achieves
both expressiveness and interpretability. The key to 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.

##### Limitation of (discrete) prompt optimization

However, existing prompt optimization algorithms are insufficient for
interpretable learning for several reasons: firstly most methods focus on
“rewriting” prompts to enhance performance (Pryzant et al., 2023; Hsieh et
al., 2023), which might not help in extracting interpretable knowledge from
data. Additionally, while recent developments show some capabilities in
correcting prompts using error examples (Pryzant et al., 2023; Wang et al.,
2023), they still struggle with complex decision rules, such as conditional
branching for classification tasks. These rules, often applicable to only a
subset of samples, are difficult to recover when considering the whole
training set. Our experiments indicate that direct application of current
methods fails to effectively address complex decision rules. These challenges
motivate the proposed LSP framework that combines prompt optimization with
symbolic programs.

####  2.2.2 Domain-Specific Language of LSPs

Compared with traditional NSPs that require manually designing a comprehensive
DSL, LLM’s ability to represent a wide range of functions via different
prompting, we can 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:in

$\displaystyle\alpha$
$\displaystyle::=x\mid\texttt{switch}(\\{\alpha==y_{i}:\alpha_{i}\\}_{i=1}^{k})\mid\texttt{LLM}(x,s).$
(3)

Here, input $x$ represents the input data (text, image, etc); the conditional
branching $\texttt{switch}(\\{y_{i}:\alpha_{i}\\}_{i=1}^{k})$ forms the
backbone of the program structure. Each switch can be viewed as a node in a
decision tree tree with $k$ branches. It will branch to $\alpha_{i}$ if the
sub-program $\alpha$ predicts $y_{i}$. The LLM Module $\texttt{LLM}(x,s)$
serves as the inference engines. It means to prompting LLM to make a
prediction on input $x$ under the instruction $s$.

Figure 1 shows an example LSP generated from above DSL. Given a test query, we
traverse the tree-structured program in a top-down manner, assigning data to
specific child node based on the parent node’s predictions, until the leaf
node is reached and the final response is returned.

####  2.2.3 Learning algorithm

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 predictions and expanding the leaf node with the
highest prediction errors. (2) LLM module optimization (Right): Here, a
learner LLM is instructed to summarize rules based on the observed data at its
node.

##### Overview

The tree search framework commonly used in NSPs also applies to LSPs
(Chaudhuri et al., 2021; Shah et al., 2020). Moreover, the simplicity of our
DSL allows the search process to be further arranged in a highly intuitive
manner akin to constructing decision trees. As illustrated in Figure 2, the
process begins at the root node with an empty program and the entire training
set. A switch operator combined with an LLM(x, s) module is then added. This
combination essentially directs the program’s flow based on the module’s
predictions. Once the LLM module is trained, we expand its child nodes and
repeat the whole process. This divide-and-conquer strategy benefits the search
process by simplifying each LLM module’s task to fitting only a subset of the
data.

##### Learning LLM-modules by summarizing predictive rules

In LSPs, each LLM module is responsible for decision-making on its designated
data subset. For traditional NSPs, the neural modules are optimized using
empirical risk minimization; For LSPs, training LLM modules essentially
transforms into deriving rules from observed data, as established in Section
2.2.1. While this can be achieved via generic prompt optimization techniques,
we adopt a more direct approach utilizing the LLM’s robust summarization
capabilities (Adams et al., 2023; Goyal et al., 2022; Zhang et al., 2024; Pu
and Demberg, 2023), asking the model to summarize rules from observed data
patterns. Note that LLM serves as both the inference engine and the learner,
as depicted in Figure 2 (Right).

##### Node selection

Top-down tree search algorithms generally use a node scoring function to
determine the next node to expand, ideally prioritizing nodes with the
greatest potential for program improvement. Given that nodes with more
frequent errors likely have more room for improvement, we use error count as
our scoring function. This metric, accounting for both the error rate and the
size of the data subset each node handles, provides a simple yet empirically
effective approach. Section 6 presents empirical evidence supporting the
efficacy and robustness of this metric.

##### Complete algorithm

The above outlines the learning process for expanding a single program. In the
full search pipeline, we further incorporate beam search (Pryzant et al.,
2023) and batch sampling to prevent the search from getting stuck in local
minima, as summarized in Algorithm 2 (Appendix).

##  3 IL-Bench Interpretable-Learning Benchmark

The goal for interpretable learning is for the model to acquire knowledge
transferable to humans for classification tasks that are NOT zero-shot
solvable. A task is zero-shot solvable if the LLM can predict accurately based
solely on the class name (e.g. basic dog-cat classification). To evaluate
interpretable learning methods, we need classification tasks with classes
unseen during LLM pretraining, requiring the model to learn additional
knowledge for successful classification. This is challenging given the
extensive pretraining on Internet data. Therefore, we introduce Interpretable-
Learning Bench, a novel benchmark comprising multiple challenging tasks, and
even advanced LLMs like GPT need to learn substantial additional knowledge to
solve these tasks. This benchmark provides a valuable resource for evaluating
future interpretable learning and autoprompting methods. We will explain the
construction of IL-Bench next, and leave the detailed summaries to Appendix
Table 7.

##### Synthetic Tasks

Prior work in symbolic learning often uses synthetic datasets to evaluate
methodologies due to known oracle rules, making it easy to observe model
performance. Inspired by this, we develop synthetic datasets with known
predictive rules in our benchmark. These datasets employ symbols to represent
variables and values, making them context-agnostic and requiring the model to
rely on abstract reasoning. Our tasks include decisions generated by decision
trees of varying complexity, allowing us to assess model behavior as rule
complexity increases.

##### Textual Classification Tasks: from image to text dataset

To evaluate the model’s proficiency in complex scenarios, Fine-Grained Visual
Classification (FGVC) tasks (Maji et al., 2013; Wah et al., 2011; Kramberger
and Potočnik, 2020; Nilsback and Zisserman, 2008; Van Horn et al., 2015) serve
as an excellent testbed. FGVC focuses on distinguishing objects within
narrowly defined categories, where the differences between examples from each
class are often subtle. We selected specific image subsets from FGVC
databases, covering area of various bird species (Wah et al., 2011). For
evaluating pure-text LLMs, we convert them to text datasets via captioning. To
ensure the captions cover the intricate differences between objects, we
introduce the Concatenated Contrastive Captioning (C3) technique, which
generates detailed captions by contrasting a target image with reference
images from different classes, merging them into a comprehensive description
for text-only LLM evaluation.

##### Visual classification Tasks: distinguishing novel visual concepts

We also collect a new suit of datasets from Palworld, a Pokemon-style game
containing various species of creatures (Examples in Table 7). Since the game
is released after most existing LLM’s knowledge cut-off date, the model will
need to rely solely on the knowledge extracted from the dataset to perform the
prediction.

##  4 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-hoc methods provide insights into how
a pretrained model behaves, usually by highlighting important features used
for decision making (Zintgraf et al., 2017; Petsiuk et al., 2018; Dabkowski
and 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 et al., 2018; Bai et
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 and Guestrin, 2016) and
Generalized Additive Models (GAMs) (Hastie and Tibshirani, 1990) offer strong
interpretability, yet often not expressive enough. Concept bottleneck model
adds a 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 et al., 2023). While this approach
facilitates attribution of concepts, it does not provide a comprehensive
decision rule. Neurosymbolic Programming (NSP) (Chaudhuri et al., 2021; Shah
et al., 2020; Cui and Zhu, 2021; Nauta et al., 2021b) represents an innovative
blend, combining deep learning’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 et al., 2020; Cui and Zhu, 2021).

##### Prompt Optimization

The essence of utilizing a generative language model lies in crafting
effective 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 were mainly directed
towards various discrete optimization algorithms (Shin et al., 2020; Deng et
al., 2022; Zhang et al., 2022), it has been noted that advanced LLMs can
revise prompts similarly to human engineers (Zhou et al., 2022; Pryzant et
al., 2023). Since these initial efforts, a 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., 2023; 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 a single entity without explicit structure.
From this perspective, prompt optimization methods can be seen as simplified
instances of LSPs, 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.

##  5 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:

  * •

Q1: 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 explicit structures beneficial to LSPs? We compare
the structured LSP with vanilla prompt optimization, which exemplifies a
special case of LSP with a single LLM module. (Section 5.3)

  * •

Q4: How effective are different LLMs in implementing LSP? We conduct cross-
model experiments to evaluate the performance of various LLMs as the
computational backbone for learning and inference in LSP. (Section 8.1.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.0-pro) (Team et al., 2023). For vision tasks, GPT-4V
(gpt-4-1106-vision-preview) and Gemini-Vision (1.0-pro-vision) are utilized.
All experiments are repeated with 3 seeds.

##### Implementation details of LSP

Our default model of choice is GPT-3.5 for language tasks and Gemini-Vision
for vision tasks, but also examine cross-(M)LLM performance in Appendix. All
LLM modules are initialized with an empty instruction “none”. More detailed
hyperparameters can be found in Appendix, which is kept fixed throughout the
experiments.

###  5.2 Comparison with traditional interpretable learning methods

Table 1: Classification accuracy comparison with XAI methods on IL-Bench-
Vision. Here, all numbers for LSP are obtained with Gemini-Vision as the
learner and inference LLM, 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 to human raters, as they are able to reproduce the
predictions following rules learned by LSP.

IL-Bench-Vision |  | Palworld
---|---|---
MLLM | Method | Mean | Fire-1 | Fire-2 | Dragon-1 | Dragon-2 | Electric-1 | Electric-2 | Water-1
Gemini-M | Decision Tree (Chen and Guestrin, 2016) | 68.20 | 91.11 $\pm$ 12.57 | 32.00 $\pm$ 9.80 | 68.33 $\pm$ 10.27 | 48.33 $\pm$ 20.95 | 82.67 $\pm$ 6.80 | 65.33 $\pm$ 13.60 | 66.67 $\pm$ 8.50
ProtoTree (Nauta et al., 2021b) | 84.33 | 100.00 $\pm$ 0.00 | 62.67 $\pm$ 12.36 | 98.33 $\pm$ 2.36 | 85.00 $\pm$ 4.08 | 100.00 $\pm$ 0.00 | 82.67 $\pm$ 9.98 | 61.67 $\pm$ 25.93
LSP | 84.76 | 93.33 $\pm$ 6.67 | 76.00 $\pm$ 4.00 | 85.00 $\pm$ 0.00 | 97.50 $\pm$ 2.50 | 86.00 $\pm$ 10.00 | 68.00 $\pm$ 4.00 | 87.50 $\pm$ 2.50
LSP (GPT-4V) | 95.67 | 96.67 $\pm$ 3.33 | 90.00 $\pm$ 6.00 | 90.00 $\pm$ 10.00 | 97.50 $\pm$ 2.50 | 100.00 $\pm$ 0.00 | 98.00 $\pm$ 2.00 | 97.50 $\pm$ 2.50
Human Rater | ProtoTree (Nauta et al., 2021b) | 72.74 | 83.33 $\pm$ 16.67 | 50.0 $\pm$ 10.0 | 100.0 $\pm$ 0.0 | 75.0 $\pm$ 0.0 | 83.33 $\pm$ 16.67 | 80.0 $\pm$ 0.0 | 37.5 $\pm$ 12.5
LSP (GPT-4V) | 90.36 | 100.00 $\pm$ 0.00 | 70.00 $\pm$ 10.00 | 100.00 $\pm$ 0.00 | 87.5 $\pm$ 12.5 | 100.00 $\pm$ 0.00 | 100.00 $\pm$ 0.00 | 75.00 $\pm$ 25.00

Figure 3:  Accuracy retention rate on Out-Of-Distribution variants of IL-
Bench-Vision testsets. We compute the ratio of test accuracy evaluated on OOD
datasets to the original test accuracy. LSP shows strong transferability to
OOD data. Notably, the version using GPT-4V as the learner retains 90-100% of
the original test accuracy.

We compare LSP with two established models - ProtoTree (Nauta et al., 2021b)
and Decision Tree (Chen and Guestrin, 2016) \- both organize prediction
process in tree-structured formats. Among existing NSP methods, the closest to
ours is ProtoTree - a highly interpretable NSP that learns a 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
ProtoTree does not rely on an explicit DSL - we could not compare with methods
based on explicit DSL since they require domain experts to design those
operation, while our goal is to automate the whole process. Since ProtoTree
only implements image tasks, this comparison also focus on the vision tasks in
IL-Bench.

##### Expressiveness

The expressiveness of the learned programs is evaluated in Table 1. LSP
(GPT4V) outperforms ProtoTree with an average accuracy of 95.67%, which is
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.

##### Interpretability

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 1, 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.

##### Generalization under Domain Shift

In contrast to traditional NSP models that rely on parametric memory, LSP
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 Out-of-Distribution (OOD) data, constructed using
GPT-4V (See Appendix for details) As shown in Figure 3, LSP demonstrates
exceptional resilience to domain shifts, compared with ProtoTree.

###  5.3 Comparison with prompt optimization

Table 2: Classification accuracy comparison with Prompt Optimization methods
on IL-Bench-Language. Key findings include: (1) LSP achieves $\sim 5\%$
accuracy gain over PromptAgent, the previous state-of-the-art. (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-engineer complex rules from observed data.

Text Benchmark |  | Synthetic | Caption |
---|---|---|---|---
LLM | Method | Mean | DT-Easy | DT-Medium | DT-Hard | Waxwing | Waterthrush | Jaeger | Albatross | Blackbird | Swallow
GPT-3.5 | APE (Zhou et al., 2022) | 67.62 | 99.67 $\pm$ 0.47 | 86.67 $\pm$ 12.47 | 87.00 $\pm$ 8.57 | 46.11 $\pm$ 4.37 | 43.89 $\pm$ 3.14 | 65.56 $\pm$ 2.83 | 47.41 $\pm$ 2.28 | 78.06 $\pm$ 1.04 | 54.17 $\pm$ 1.18
OPRO (Yang et al., 2023) | 55.48 | 50.00 $\pm$ 1.08 | 50.17 $\pm$ 3.06 | 30.33 $\pm$ 2.62 | 57.22 $\pm$ 2.08 | 57.22 $\pm$ 4.16 | 76.67 $\pm$ 4.71 | 40.37 $\pm$ 3.43 | 78.06 $\pm$ 2.83 | 55.28 $\pm$ 1.04
APO (Pryzant et al., 2023) | 70.67 | 100.00 $\pm$ 0.00 | 96.67 $\pm$ 4.71 | 77.83 $\pm$ 11.90 | 56.11 $\pm$ 4.78 | 48.89 $\pm$ 4.16 | 70.00 $\pm$ 5.93 | 54.07 $\pm$ 9.70 | 74.17 $\pm$ 2.97 | 58.33 $\pm$ 1.36
PromptAgent (Wang et al., 2023) | 72.40 | 97.67 $\pm$ 3.30 | 88.50 $\pm$ 8.44 | 64.33 $\pm$ 20.27 | 60.56 $\pm$ 4.78 | 56.67 $\pm$ 6.24 | 75.00 $\pm$ 3.60 | 74.44 $\pm$ 6.54 | 74.17 $\pm$ 1.36 | 57.22 $\pm$ 0.79
LSP (Ours) | 77.29 | 99.25 $\pm$ 0.75 | 98.50 $\pm$ 0.00 | 89.75 $\pm$ 1.25 | 65.83 $\pm$ 4.17 | 62.50 $\pm$ 0.83 | 80.00 $\pm$ 1.67 | 61.11 $\pm$ 1.11 | 78.75 $\pm$ 0.42 | 62.92 $\pm$ 0.42

Table 3: Classification accuracy comparison with Prompt Optimization methods
on IL-Bench-Vision. LSP achieves an average accuracy of 84.47%, which is $\sim
20\%$ higher than the 2nd best method (APE).

Vision Benchmark |  | Palworld |
---|---|---|---
MLLM | Method | Mean | Fire-1 | Fire-2 | Dragon-1 | Dragon-2 | Electric-1 | Electric-2 | Water-1
Gemini-M | APE (Zhou et al., 2022) | 64.38 | 76.67 $\pm$ 3.33 | 56.00 $\pm$ 0.00 | 59.17 $\pm$ 5.83 | 35.00 $\pm$ 5.00 | 57.33 $\pm$ 10.67 | 82.00 $\pm$ 2.00 | 82.50 $\pm$ 12.50
OPRO (Yang et al., 2023) | 49.26 | 86.67 $\pm$ 0.00 | 32.00 $\pm$ 4.00 | 56.67 $\pm$ 3.33 | 50.00 $\pm$ 5.00 | 48.00 $\pm$ 28.00 | 49.00 $\pm$ 19.00 | 27.50 $\pm$ 2.50
APO (Pryzant et al., 2023) | 58.45 | 76.67 $\pm$ 23.33 | 42.00 $\pm$ 14.00 | 59.17 $\pm$ 5.83 | 70.00 $\pm$ 5.00 | 39.33 $\pm$ 7.33 | 67.50 $\pm$ 12.50 | 52.50 $\pm$ 17.50
PromptAgent (Wang et al., 2023) | 54.74 | 66.67 $\pm$ 6.67 | 44.00 $\pm$ 0.00 | 49.17 $\pm$ 15.83 | 52.50 $\pm$ 2.50 | 55.33 $\pm$ 8.67 | 42.50 $\pm$ 2.50 | 70.00 $\pm$ 0.00
LSP (Ours) | 84.47 | 93.33 $\pm$ 6.67 | 76.00 $\pm$ 4.00 | 85.00 $\pm$ 0.00 | 97.50 $\pm$ 2.50 | 86.00 $\pm$ 10.00 | 68.00 $\pm$ 4.00 | 87.50 $\pm$ 2.50

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., 2022), evolutionary search (ORPO)
(Yang et al., 2023), beam search (APO) (Pryzant et al., 2023), and tree search
(PromptAgent) (Wang et al., 2023). 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).

##### Results

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 a
considerable margin of $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 a divide-and-conquer approach where each LLM-module 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 (e.g., multiple
conditional clauses. In contrast, LSP mitigates this issue by ensuring that
each LLM module contains simpler, more manageable instructions.

(a) Language Tasks

(b) Vision Tasks

(c) Program Depth

(d) Program Sparsity

Figure 4:  (a, b): Stronger LLMs as better LSP learners. In these experiments,
we keep the inference LLM fixed (GPT-3.5 for text and Gemini-V for images)
while swapping the learner LLM 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 IL-Bench-Language tasks,
the resulting LSPs are generally shallow and sparse, indicating that the final
prediction can be reached within only a few steps.

##  6 Ablation Study

##### Convergence of LLM-Symbolic Program LSP

(a) CUB-Waxwing

(b) CUB-Waterthrush

(c) CUB-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.  Table
4: Search and inference runtime Ccmparison. Despite the multi-step decision-
making process of LSP’s tree structure, our method incurs comparable search
and inference costs to various prompt optimization baselines.

Method | Search (s) | Inference (s)
---|---|---
APE | 270.60 | 0.11
OPRO | 257.86 | 0.14
APO | 270.85 | 0.08
PromptAgent | 220.95 | 0.11
LSP | 232.54 | 0.13

LSP organizes instructions into a tree-based structure. Such divide-and-
conquer 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 a 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.

Table 5: Comparison of Different Node Scoring Functions on three tasks from
IL-Bench-Language. Despite its simplicity, error count achieves more
consistent performance compared to alternative metrics.

Node Scoring | DT-Hard | Waxwing | Waterthrush
---|---|---|---
Random | 70.50 $\pm$ 11.01 | 62.22 $\pm$ 4.78 | 61.67 $\pm$ 1.36
Accuracy | 80.33 $\pm$ 18.27 | 66.11 $\pm$ 7.86 | 54.44 $\pm$ 0.70
Error Count (LSP) | 89.75 $\pm$ 1.25 | 65.83 $\pm$ 4.17 | 62.50 $\pm$ 0.83

##### Search cost analysis

We also report the actual runtime of search and inference process for
different methods in Table 4. We found that LSP incurs comparable search and
inference costs to various prompt optimization baselines.

##### 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 achieves substantially better and more
consistent outcomes across different tasks.

##### Complexity of Learned LSP

Our analysis of the statistics of learned programs indicates that the
complexity of programs developed by LSP is quite manageable: Most programs can
reach a final prediction within just three steps, as illustrated in Figure
4(c), and the tree structures tend to be sparse, as shown in Figure 4(d).
These observations confirm that although theoretical maximum tree expansion
could grow exponentially with depth, in practice, LSPs operate effectively
without requiring overly complex structures. This further explain why LSP
exhibits the reasonable search and inference costs documented in Table 4.

##  7 Conclusion

This work aims at revitalizing the concept of Neuro-Symbolic 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-Benchmark), which consists of a 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 LLM-Symbolic Programs. Accordingly, we acknowledge the limitations
of the current method in Appendix Section 8.4.

## References

  * Achiam et al. [2023] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ , 2023.
  * Adams et al. [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.
  * Ancona et al. [2017] Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross.  Towards better understanding of gradient-based attribution methods for deep neural networks.  _arXiv preprint arXiv:1711.06104_ , 2017.
  * Bai et al. [2023] Andrew Bai, Chih-Kuan Yeh, Pradeep Ravikumar, Neil YC Lin, and Cho-Jui Hsieh.  Concept gradient: Concept-based interpretation without linear assumption.  In _ICLR_ , 2023.
  * Chaudhuri et al. [2021] Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, Yisong Yue, et al.  Neurosymbolic programming.  _Foundations and Trends® in Programming Languages_ , 7(3):158–243, 2021.
  * Chen and Guestrin [2016] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In _Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining_ , pages 785–794, 2016.
  * Cui and Zhu [2021] Guofeng Cui and He Zhu.  Differentiable synthesis of program architectures.  _Advances in Neural Information Processing Systems_ , 34:11123–11135, 2021.
  * Dabkowski and Gal [2017] Piotr Dabkowski and Yarin Gal.  Real time image saliency for black box classifiers.  In _Advances in Neural Information Processing Systems_ , pages 6967–6976. NeurIPS, 2017.
  * Deng et al. [2022] Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu.  Rlprompt: Optimizing discrete text prompts with reinforcement learning.  _arXiv preprint arXiv:2205.12548_ , 2022.
  * Dhurandhar et al. [2018] 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_ , pages 592–603. NeurIPS, 2018.
  * Fernando et al. [2023] Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel.  Promptbreeder: Self-referential self-improvement via prompt evolution.  _arXiv preprint arXiv:2309.16797_ , 2023.
  * Frosst and Hinton [2017] Nicholas Frosst and Geoffrey Hinton.  Distilling a neural network into a soft decision tree.  _arXiv preprint arXiv:1711.09784_ , 2017.
  * Goyal et al. [2022] Tanya Goyal, Junyi Jessy Li, and Greg Durrett.  News summarization and evaluation in the era of gpt-3.  _arXiv preprint arXiv:2209.12356_ , 2022.
  * Goyal et al. [2019] Yash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh, and Stefan Lee.  Counterfactual visual explanations.  In _International Conference on Machine Learning_ , pages 2376–2384. ICML, 2019.
  * Guo et al. [2023] 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.08532_ , 2023.
  * Hastie and Tibshirani [1990] Trevor Hastie and Robert Tibshirani.  _Generalized additive models_.  Chapman and Hall/CRC, 1990.
  * Hendricks et al. [2018] Lisa Anne Hendricks, Ronghang Hu, Trevor Darrell, and Zeynep Akata.  Grounding visual explanations.  In _ECCV_. ECCV, 2018.
  * Hsieh et al. [2021] Cheng-Yu Hsieh, Chih-Kuan Yeh, Xuanqing Liu, Pradeep Kumar Ravikumar, Seungyeon Kim, Sanjiv Kumar, and Cho-Jui Hsieh.  Evaluations and methods for explanation through robustness analysis.  In _International Conference on Learning Representations_. ICLR, 2021.  URL https://openreview.net/forum?id=4dXmpCDGNp7.
  * Hsieh et al. [2023] Cho-Jui Hsieh, Si Si, Felix X Yu, and Inderjit S Dhillon.  Automatic engineering of long prompts.  _arXiv preprint arXiv:2311.10117_ , 2023.
  * Kim et al. [2018] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al.  Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav).  In _International Conference on Machine Learning_ , pages 2673–2682. ICML, 2018.
  * Koh et al. [2020] 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_ , pages 5338–5348. PMLR, 2020.
  * Kramberger and Potočnik [2020] Tin Kramberger and Božidar Potočnik.  Lsun-stanford car dataset: enhancing large-scale car image datasets using deep learning for usage in gan training.  _Applied Sciences_ , 10(14):4913, 2020.
  * Losch et al. [2019] Max Losch, Mario Fritz, and Bernt Schiele.  Interpretability beyond classification output: Semantic bottleneck networks.  _arXiv preprint arXiv:1907.10882_ , 2019.
  * Maji et al. [2013] Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi.  Fine-grained visual classification of aircraft.  _arXiv preprint arXiv:1306.5151_ , 2013.
  * Ming et al. [2019] 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_, pages 903–913, 2019.
  * Nauta et al. [2021a] Meike Nauta, Annemarie Jutte, Jesper Provoost, and Christin Seifert.  This looks like that, because… explaining prototypes for interpretable image recognition.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 441–456. Springer, 2021a.
  * Nauta et al. [2021b] Meike Nauta, Ron Van Bree, and Christin Seifert.  Neural prototype trees for interpretable fine-grained image recognition.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 14933–14943, 2021b.
  * Nilsback and Zisserman [2008] 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_, pages 722–729. IEEE, 2008.
  * Oikarinen et al. [2023] Tuomas Oikarinen, Subhro Das, Lam M Nguyen, and Tsui-Wei Weng.  Label-free concept bottleneck models.  _arXiv preprint arXiv:2304.06129_ , 2023.
  * Ouyang et al. [2022] 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 in neural information processing systems_ , 35:27730–27744, 2022.
  * Pair [2024] Pocket Pair.  Palworld, 2024.  URL https://en.wikipedia.org/wiki/Palworld.
  * Petsiuk et al. [2018] Vitali Petsiuk, Abir Das, and Kate Saenko.  Rise: Randomized input sampling for explanation of black-box models.  _arXiv preprint arXiv:1806.07421_ , 2018.
  * Pryzant et al. [2023] 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 arXiv:2305.03495_ , 2023.
  * Pu and Demberg [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.
  * Ribeiro et al. [2016] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Why should i trust you?: Explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1135–1144. ACM, 2016.
  * Shah et al. [2020] Ameesh Shah, Eric Zhan, Jennifer Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri.  Learning differentiable programs with admissible neural heuristics.  _Advances in neural information processing systems_ , 33:4940–4952, 2020.
  * Shin et al. [2020] Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh.  Autoprompt: Eliciting knowledge from language models with automatically generated prompts.  _arXiv preprint arXiv:2010.15980_ , 2020.
  * Shrikumar et al. [2017] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje.  Learning important features through propagating activation differences.  _International Conference on Machine Learning_ , 2017.
  * Sundararajan et al. [2017] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In _International Conference on Machine Learning_ , pages 3319–3328. PMLR, 2017.
  * Team et al. [2023] Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al.  Gemini: a family of highly capable multimodal models.  _arXiv preprint arXiv:2312.11805_ , 2023.
  * van der Waa et al. [2018] 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.
  * Van Horn et al. [2015] Grant Van Horn, Steve Branson, Ryan Farrell, Scott Haber, Jessie Barry, Panos Ipeirotis, Pietro Perona, and Serge Belongie.  Building a bird recognition app and large scale dataset with citizen scientists: The fine print in fine-grained dataset collection.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 595–604, 2015.
  * Wah et al. [2011] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie.  The caltech-ucsd birds-200-2011 dataset.  Technical Report CNS-TR-2011-001, California Institute of Technology, 2011.
  * Wang et al. [2023] 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 arXiv:2310.16427_ , 2023.
  * Xu et al. [2022] 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:2210.17041_ , 2022.
  * Yang et al. [2023] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen.  Large language models as optimizers.  _arXiv preprint arXiv:2309.03409_ , 2023.
  * Yuksekgonul et al. [2022] Mert Yuksekgonul, Maggie Wang, and James Zou.  Post-hoc concept bottleneck models.  _arXiv preprint arXiv:2205.15480_ , 2022.
  * Zhang et al. [2022] Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schuurmans, and Joseph E Gonzalez.  Tempera: Test-time prompting via reinforcement learning.  _arXiv preprint arXiv:2211.11890_ , 2022.
  * Zhang et al. [2024] 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.
  * Zhou et al. [2022] 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 arXiv:2211.01910_ , 2022.
  * Zintgraf et al. [2017] Luisa M Zintgraf, Taco S Cohen, Tameem Adel, and Max Welling.  Visualizing deep neural network decisions: Prediction difference analysis.  _arXiv preprint arXiv:1702.04595_ , 2017.

##  8 Supplemental Material

###  8.1 Additional ablation experiments

####  8.1.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.

##### LLM as LSP interpreter

Table 6: Transferring LSPs learned from one LLM to another. The learned LSPs
are generally interpretable across various LLMs. However, larger LLMs (e.g.,
GPT-4) demonstrate a slightly higher consistency in understanding LSPs learned
by other LLMs.

Source Model | Task | Evaluator
---|---|---
GPT3.5 | Gemini-M | GPT4 |
GPT3.5 | DT-Hard | 89.75 $\pm$ 1.25 | 72.67 $\pm$ 6.91 | 87.50 $\pm$ 1.22 |
Waxwing | 65.83 $\pm$ 4.17 | 52.22 $\pm$ 1.57 | 56.67 $\pm$ 3.60 |
Waterthrush | 62.50 $\pm$ 0.83 | 64.44 $\pm$ 0.79 | 59.44 $\pm$ 3.93 |
Gemini-M | DT-Hard | 75.50 $\pm$ 2.04 | 80.83 $\pm$ 1.03 | 79.17 $\pm$ 11.45 |
Waxwing | 52.78 $\pm$ 3.42 | 58.33 $\pm$ 4.91 | 61.11 $\pm$ 10.57 |
Waterthrush | 50.56 $\pm$ 4.16 | 54.44 $\pm$ 5.50 | 52.22 $\pm$ 0.79 |
GPT4 | DT-Hard | 74.50 $\pm$ 9.35 | 57.67 $\pm$ 3.01 | 99.50 $\pm$ 0.00 |
Waxwing | 59.44 $\pm$ 5.15 | 62.22 $\pm$ 7.49 | 63.33 $\pm$ 4.91 |
Waterthrush | 66.67 $\pm$ 6.80 | 68.33 $\pm$ 2.72 | 62.78 $\pm$ 9.06 |

We then test if LSPs created by one LLM could be interpreted by other LLMs.
Table 6 summarizes the performance. The results suggest that LSPs are
interpretable across a diverse range of inference models; Larger and stronger
LLMs (e.g. GPT-4) demonstrates a slight more consistent ability in
interpreting LSPs, which aligns their superior instruction-following
capacities.

###  8.2 Learning algorithm for LSP

The complete pipeline for constructing LSP is summarized in Algorithm 1 and
Algorithm 2.

##### Remarks

  * •

Although initially, the complexity of the program expansion might seem
exponential to the tree depth, a closer examination reveals otherwise: (1). In
practice, the trees are typically sparse, meaning that expanding only a few
branches is often sufficient to achieve good performance (Figure 4(d)). (2).
The divide-and-conquer approach ensures that each tree level processes the
same amount of data making the evaluation complexity linear 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 (cite).

Algorithm 1 learn_llm_module: Learning LLM Module by summarizing predictive
rules

1: Input: Proposal size $m$, data sample $\mathcal{B}$, learner LLM
$\mathcal{M}_{l}$

2: Initialize an empty list of LLM modules $\Phi$

3: for $i=1$ to $m$ do

4: Randomly sample $b\sim\mathcal{B}$

5: $\phi_{new}\leftarrow\texttt{summarize}(M_{l},b)$

6: $\Phi\leftarrow\Phi\cup\\{\phi_{new}\\}$

7: end for

8: return $\Phi$

Algorithm 2 Complete pipeline of optimizing LSPs

1: Input: Dataset $\mathcal{D}$, beam size $d$, number of iterations $T$,
inference LLM $\mathcal{M}_{i}$, learner LLM $\mathcal{M}_{l}$, expand ratio
$K$, proposal size $m$

2: Initialize $p_{0}$ as an empty program

3: Initialize candidate program set $P=\\{p_{0}\\}$

4: for $t=1$ to $T$ do

5: for each program $p$ in $P$ do

6: $\triangleright$ Batch evaluation

7: Sample a batch $\mathcal{B}\sim\mathcal{D}$

8: Evaluate $p$ on $\mathcal{B}$ using $\mathcal{M}_{i}$

9: $\triangleright$ Selecting the most promising node $n$ to expand

10: Assign $\mathcal{B}$ to the leaf nodes of $p$

11: Identify the most error-prone leaf node $n$ with assigned subset
$\mathcal{B}_{n}$

12: $\triangleright$ Extend program $p$ to $K$ new programs by adding top-$K$
LLM modules to node $n$

13:
$\Phi\leftarrow\texttt{learn\\_llm\\_module}(n,\mathcal{B}_{n},\mathcal{M}_{l},m)$

14: $\Phi_{topK}\leftarrow$ evaluate and retain top-$K$ $\Phi$ on
$\mathcal{B}_{n}$

15: $\mathcal{P}_{new}\leftarrow$ extend $p$ by assigning each
$\phi\in\Phi_{topK}$ to node $n$ on program $p$.

16: $\mathcal{P}\leftarrow\mathcal{P}\cup\mathcal{P}_{new}$

17: end for

18: Evaluate and retain the top-$d$ programs from $\mathcal{P}$ on
$\mathcal{D}$

19: end for

20: return The best program from $P$

Table 7: Overview of Interpretable-Learning Benchmark. We provide task names,
types, summaries, number of labels, and one example data point for each task.

Task |  Type |  Summary |  Labels |  Example
---|---|---|---|---
DT-Easy |  Synthetic |  Predict labels based on symbolic inputs. Rules generated by a small decision tree |  2 |  "input": "x1=A2; x2=B1", "output": "bar"
DT-Medium |  Synthetic |  Predict labels based on symbolic inputs. Rules generated by a medium decision tree |  2 |  "input": "x1=A3; x2=B2", "output": "bar"
DT-Hard |  Synthetic |  Predict labels based on symbolic inputs. Rules generated by a large decision tree |  4 |  "input": "x1=A1; x2=B1; x3=C1", "output": "foo"
Waxwing |  Caption |  Classify Waxwing species based on its text description. |  2 |  "input": "Tan to light brown head and upper body, black m̈askäcross eyes, lighter cream underparts, bright red tips on secondary wing feathers, small black bill, yellow band on tail.", "output": "Cedar Waxwing"
Waterthrush |  Caption |  Classify Waterthrush species based on its text description. |  2 |  "input": "Light gray crown, white supercilium, dark eyestripe extending behind eye, olive-brown wings with faint wingbars, white throat, pale underparts, long, slender bill, relatively short tail, orange legs.", "output": "Louisiana Waterthrush"
Jaeger |  Caption |  Classify Jaeger species based on its text description. |  2 |  "input": "Light greyish-brown plumage on the underside, distinct narrow white band across the nape, wings with a M-shaped pattern when spread, tail slightly forked but mostly straight across.", "output": "Long tailed Jaeger"
Albatross |  Caption |  Classify Albatross species based on its text description. |  3 |  "input": "Dark brown upperparts and paler brown underparts, elongated and narrow wings with a white trailing edge and distinct finger-like tips, hooked beak with a pale base, light-colored head with a dark eye patch and bill, wings held straight in gliding flight, gliding above water surface. Uniform dark brown plumage, long slender wings, distinct white pattern on underwings, white band near the tips of the underwings, pale or white head, dark eye patch.", "output": "Black footed Albatross"
Blackbird |  Caption |  Classify Blackbird species based on its text description. |  4 |  "input": "Bright yellow head, black body, sharp conical beak, perched on reed-like vegetation. Bright yellow head, yellow chest, solid black body excluding head and chest, perched on a thin branch. Black body, bright yellow head, sturdy bill, perched on a reed.", "output": "Yellow headed Blackbird"
Swallow |  Caption |  Classify Swallow species based on its text description. |  4 |  "input": "Light brown head, pale throat, light brown upperparts, long pointed wings, short tail, white underparts, sitting on wire. Light brown head and upper body, white underparts, sitting on a wire, sky background, short beak, sleek body shape. Brown and white plumage, perched on a wire, stout body, short and thick neck, medium-length tail with a straight edge, compact size, unmarked lighter underparts, darker wings and upperparts.", "output": "Bank Swallow"
Fire-1 |  Vision |  Distinguish visually-similar fire-type pals from Palworld. |  3 |  "input": , "output:" "Arsox"
Fire-2 |  Vision |  Distinguish visually-similar fire-type pals from Palworld. |  5 |  "input": , "output:" "Pyrin"
Dragon-Blue-1 |  Vision |  Distinguish visually-similar blue-colored dragon-type pals from Palworld. |  3 |  "input": , "output:" "Elphidran Aqua"
Dragon-Blue-2 |  Vision |  Distinguish visually-similar blue-colored dragon-type pals from Palworld. |  4 |  "input": , "output:" "Jetragon"
Electric-1 |  Vision |  Distinguish visually-similar electric-type pals from Palworld. |  3 |  "input": , "output:" "Grizzbolt"
Electric-2 |  Vision |  Distinguish visually-similar electric-type pals from Palworld. |  4 |  "input": , "output:" "Univolt"
Water-1 |  Vision |  Distinguish visually-similar water-type pals from Palworld. |  4 |  "input": , "output:" "Celaray"

###  8.3 More details on empirical evaluation

Here we provide more details on the empirical evaluation.

####  8.3.1 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 UCBBandits algorithm with
a 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 to their default (0.7).

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.
For ProtoTree, we directly run the original implementation, but reduce the
maximum depth from 9 to 5, as it is faster to train yet achieves better
performance on our datasets. We align the evaluation our baselines

####  8.3.2 Constructing Out-Of-Distribution dataset for IL-Bench-Vision tasks

(a) Beakon Original

(b) Celaray Original

(c) Incineram Original

(d) Jolthog Original

(e) Beakon Generated

(f) Celaray Generated

(g) Incineram Generated

(h) Jolthog Generated

Figure 6: Comparison between original images (top row) and Out-Of-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 a variant of the input
image. The prompt we used is shown below. Figure 6 shows a comparison of some
example OOD images generated by GPT-4 with original image.

> Generate an 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.

####  8.3.3 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) Celaray

(b) Gobfin

(c) Kelpsea

(d) Penking

(e) Caption for the second image

(f) Example

Figure 7: Example programs discovered by LSP (bottom) and ProtoTree (middle).
While ProtoTree offers some interpretability by displaying prototype image
patches to 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 to 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.

###  8.4 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:

  * •

Domain-Specific Language Design: A common practice in NSp is to design DSLs
suitable for specific tasks. This work presents only a basic example of a DSL
designed for predictive tasks. Investigating a variety of DSL designs could
enable LSPs to excel across a broader range of applications.

  * •

Program Complexity: Our search algorithm prioritizes accuracy without
considering the complexity 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.

###  8.5 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 be given to the
potential risks of misuse or unintended consequences. It is essential to
continue developing comprehensive guidelines and regulatory frameworks to
ensure that the deployment of these models aligns with societal values and
ethical standards. By promoting transparency and interpretability, our
approach paves the way for more responsible and beneficial integration of AI
into society.

###  8.6 License

The open-source code from GitHub used in this paper adheres to 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
OpenAI 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 in utilizing both open-
source code and proprietary APIs in our research.


††thanks<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Observation of quantum spin Hall states in Ta2Pd3Te5

Xuguang Wang  Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China  These authors contributed equally to this
work.  Daiyu Geng  Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China  These authors contributed equally to this
work.  Dayu Yan  Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China  These authors contributed equally to this
work.  Wenqi Hu  Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China  These authors contributed equally to this
work.  Hexu Zhang  Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China  Shaosheng Yue  Institute of Physics, Chinese
Academy of Sciences, Beijing 100190, China  School of Physical Sciences,
University of Chinese Academy of Sciences, Beijing 100049, China  Zhenyu Sun
Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
School of Physical Sciences, University of Chinese Academy of Sciences,
Beijing 100049, China  Shiv Kumar  Hiroshima Synchrotron Radiation Center,
Hiroshima University, 2-313 Kagamiyama, Higashi-Hiroshima 739-0046, Japan
Kenya Shimada  Hiroshima Synchrotron Radiation Center, Hiroshima University,
2-313 Kagamiyama, Higashi-Hiroshima 739-0046, Japan  Peng Cheng  Institute of
Physics, Chinese Academy of Sciences, Beijing 100190, China  School of
Physical Sciences, University of Chinese Academy of Sciences, Beijing 100049,
China  Lan Chen  Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China  Songshan Lake Materials Laboratory, Dongguan,
Guangdong 523808, China  Simin Nie  Department of Materials Science and
Engineering, Stanford University, Stanford, California 94305, USA  Zhijun Wang
Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
School of Physical Sciences, University of Chinese Academy of Sciences,
Beijing 100049, China  Youguo Shi  Institute of Physics, Chinese Academy of
Sciences, Beijing 100190, China  School of Physical Sciences, University of
Chinese Academy of Sciences, Beijing 100049, China  Center of Materials
Science and Optoelectronics Engineering, University of Chinese Academy of
Sciences, Beijing 100049, China  Songshan Lake Materials Laboratory, Dongguan,
Guangdong 523808, China  Yi-Qi Zhang  Institute of Physics, Chinese Academy of
Sciences, Beijing 100190, China  School of Physical Sciences, University of
Chinese Academy of Sciences, Beijing 100049, China  Kehui Wu  Institute of
Physics, Chinese Academy of Sciences, Beijing 100190, China  School of
Physical Sciences, University of Chinese Academy of Sciences, Beijing 100049,
China  Songshan Lake Materials Laboratory, Dongguan, Guangdong 523808, China
Baojie Feng  Institute of Physics, Chinese Academy of Sciences, Beijing
100190, China  School of Physical Sciences, University of Chinese Academy of
Sciences, Beijing 100049, China

###### Abstract

Two-dimensional topological insulators (2DTIs), which host the quantum spin
Hall (QSH) effect, are one of the key materials in next-generation spintronic
devices. To date, experimental evidence of the QSH effect has only been
observed in a few materials, and thus, the search for new 2DTIs is at the
forefront of physical and materials science. Here, we report experimental
evidence of a 2DTI in the van der Waals material Ta2Pd3Te5. First-principles
calculations show that each monolayer of Ta2Pd3Te5 is a 2DTI with weak
interlayer interactions. Combined transport, angle-resolved photoemission
spectroscopy, and scanning tunneling microscopy measurements confirm the
existence of a band gap at the Fermi level and topological edge states inside
the gap. These results demonstrate that Ta2Pd3Te5 is a promising material for
fabricating spintronic devices based on the QSH effect.

Two-dimensional topological insulators (2DTIs), also known as quantum spin
Hall (QSH) insulators, feature a bulk band gap and helical in-gap states at
the material boundaries HasanMZ2010 ; QiXL2011 ; AndoY2013 . The edge states
of a 2DTI can serve as one-dimensional conducting channels in which
backscattering is forbidden by time-reversal symmetry. Therefore, 2DTIs
provide an ideal platform to fabricate low-dissipation spintronic devices. To
date, 2DTIs have only been realized in two types of materials. The first type
is quantum well systems, including HgTe/CdHgTe KonigM2007  and InAs/GaSb
LiuC2008 ; KnezI2011 ; DuL2015 . However, the material synthesis of these
quantum wells is extremely challenging, and experimental signatures of the QSH
effect have only been observed by a few research groups. The second type of
2DTI has been reported in several two-dimensional (2D) materials, such as
bilayer Bi YangF2012 ; DrozdovIK2014 , monolayer 1T′ WTe2 TangS2017 ; JiaZ2017
; PengL2017 , and graphene-like honeycomb lattices ZhuF2015 ; ReisF2017 ;
DengJ2018 ; XuC2018 ; ZhuSY2019 . However, despite the large number of 2D
materials as candidate 2DTIs, transport evidence of the QSH effect has only
been reported in monolayer 1T′ WTe2 FeiZ2017 ; WuS2018 ; ShiY2019 .

Realizing QSH states in van der Waals materials, such as WTe2, offers great
opportunities to fabricate quantum transport devices, as monolayer or few-
layer materials for realizing the QSH effect are very easy to obtain. However,
as a prototypical van der Waals material, 1T′ WTe2 was confirmed to be a 2DTI
only in the monolayer limit WuS2018 . In bulk form, WTe2 becomes a metal with
zero energy gap AliMN2014 ; SoluyanovAA2015 . As a result, QSH states
disappear in multilayer WTe2 because of the hybridization of the bulk and edge
states. Therefore, QSH devices based on WTe2 suffer from easy degradation of
monolayer samples under ambient conditions. Since multilayer materials are
typically more inert and have higher tunability via the thickness or twist
angles, realizing QSH states in multilayer materials is highly desirable. This
requires a semiconducting van der Waals material that hosts a similar inverted
gap as the monolayer.

Figure 1: Structure and characterization of Ta2Pd3Te5 single crystals. (a)
Schematic drawing of the atomic structure of Ta2Pd3Te5. (b) Schematic drawing
of the Brillouin zones and high-symmetry points of monolayer Ta2Pd3Te5. (c)
X-ray diffraction spectrum on a flat surface of Ta2Pd3Te5. The inset shows a
photograph of typical Ta2Pd3Te5 single crystals. (d) Large-scale STM
topographic image of the Ta2Pd3Te5 surface ($V\rm_{B}$=1 V; $I$=0.05 nA). (e)
Zoomed-in STM image showing atomic resolution ($V\rm_{B}$=50 mV; $I$=0.05 nA).
The atomic structure of the surface Te atoms (red balls) is superimposed on
the left part of the image. (f) Fast Fourier transformed STM image, which
shows a rectangular reciprocal lattice. Red arrows indicate the reciprocal
lattice vectors. (g) In-plane resistivity of Ta2Pd3Te5 single crystals as a
function of temperature. The red line is the fitting result obtained using the
Arrhenius formula.

In this work, we report the observation of QSH states in the van der Waals
material Ta2Pd3Te5 NieS2020 , which hosts a band gap in both the bulk and
monolayer forms. We synthesize Ta2Pd3Te5 single crystals and investigate their
electronic structures by combined first-principles calculations, transport,
angle-resolved photoemission spectroscopy (ARPES), and scanning tunneling
microscopy/spectroscopy (STM/STS) measurements. We prove that Ta2Pd3Te5 hosts
a band gap at the Fermi level. Because of the weak interlayer coupling, the
topmost layer of Ta2Pd3Te5 can be viewed as a monolayer material placed on a
single-crystal substrate. As expected, we directly observe topological edge
states using STS. These results provide strong evidence for QSH states in
Ta2Pd3Te5. The discovery of QSH states in van der Waals materials with a
significant band gap could pave the way to realizing practical QSH devices.

Ta2Pd3Te5 single crystals were synthesized by the self-flux method. The
starting materials of Ta (99.999%), Pd (99.9999%), and Te (99.9999%) were
mixed in an Ar-filled glove box at a molar ratio of Ta:Pd:Te=2:4.5:7.5. The
mixture was placed in an alumina crucible and sealed in an evacuated quartz
tube. The tube was heated to 950 ∘C over 10 h and maintained at this
temperature for 2 days. Then, the tube was slowly cooled to 800 ∘C at a rate
of 0.5 ∘C/h. Finally, the extra flux was removed by centrifugation at 800 ∘C.
After centrifugation, single crystals of Ta2Pd3Te5 could be selected from the
remnants in the crucible. To investigate the crystalline structure, single-
crystal X-ray diffraction (XRD) was carried out at 273 K using Mo
$\emph{K}\alpha$ radiation ($\lambda$ = 0.71073 Å). The crystalline structure
was refined by the full-matrix least-squares method on _F 2_ by using the
SHELXL-2018/3 program. Electrical resistivity (_$\rho$_) measurements were
carried out on a physical property measurement system (PPMS, Quantum Design
Inc.) using a standard dc four-probe technique.

ARPES experiments were performed at beamline BL-1 of the Hiroshima synchrotron
radiation center IwasawaH2017 . The clean surfaces required for the ARPES
measurements were obtained by cleaving the samples in an ultrahigh vacuum
chamber with a base pressure of 1.0$\times$10-9 Pa. Both the cleavage process
and ARPES measurements were performed at 30 K. The energy resolution of the
ARPES measurements was approximately 15 meV. STM/STS experiments were carried
out in a home-built low-temperature ($\sim$5 K) STM system with a base
pressure of 2$\times$10-8 Pa. The clean surfaces for STM/STS measurements were
also obtained by cleaving the samples in situ at low temperature.

First-principles calculations were performed within the framework of the
projector augmented wave (PAW) method Blochl1994 ; Kresse1999  implemented in
the Vienna ab initio simulation (VASP) package KresseG1996 ; KresseG1996prb .
The Perdew-Burke-Ernzerhof (PBE) generalized gradient approximation (GGA)
exchange-correlation functional PerdewJP1996  was implemented in the
calculations. The cutoff energy for plane wave expansion was 500 eV. Spin-
orbit coupling was self-consistently taken into account within the second
variational method. A 4-unit-cell slab structure (with 20 Å vacuum) was built
to simulate the surface spectrum.

Ta2Pd3Te5 crystallizes in an orthorhombic structure with the space group
_Pnma_ (No. 62). Schematic drawings of the atomic structure and Brillouin
zones (BZs) of Ta2Pd3Te5 are shown in Figs. 1(a) and 1(b), respectively. Each
unit cell contains two Ta2Pd3Te5 monolayers, which are stacked along the $a$
direction via weak van der Waals interactions. Each monolayer contains a Ta-Pd
mixed layer sandwiched between two Te layers. Figure 1(c) shows the XRD
spectrum on a flat surface of Ta2Pd3Te5, whereby only $(h00)$ peaks are
observed. A photograph of a typical Ta2Pd3Te5 crystal is displayed in the
inset of Fig. 1(c). The picture shows that the crystal is as large as 1 mm and
has shiny surfaces, indicating the high crystallinity of our samples. The
lattice parameters of Ta2Pd3Te5 determined from the XRD data are _a_ =
13.9531(6) Å, _b_ = 3.7038(2) Å, and _c_ = 18.5991(8) Å. Figure 1(d) shows a
large-scale STM image of Ta2Pd3Te5 (the _bc_ plane). The surface is slightly
corrugated, forming periodic stripes along the _b_ direction. A zoomed-in STM
image with atomic resolution is displayed in Fig. 1(e). Each bright protrusion
corresponds to a Te atom, which well matches the structure model of Ta2Pd3Te5.
From the STM image, the rectangular structure of the _bc_ plane of Ta2Pd3Te5
can also be identified in the fast Fourier transformed image in Fig. 1(e). The
lattice constants determined from our STM results are $\sim$3.6 Å and
$\sim$18.7 Å, respectively, which agree well with the lattice constants along
the $b$ and $c$ directions.

The temperature dependence of the electrical resistivity of Ta2Pd3Te5 is
displayed in Fig. 1(g). When the temperature is decreased from 300 K to 2 K,
the resistivity increases monotonically, indicating semiconductor behavior.
The temperature-dependent resistivity can be fitted with the Arrhenius model
$\rho$ $\sim$ exp($\epsilon_{act}$/$k_{B}$$T$), where $k_{B}$ and
$\epsilon_{act}$ are the Boltzmann constant and thermal activation energy,
respectively. The fitting results are shown by the red line in Fig. 1(g). The
fitted $\epsilon_{act}$ is approximately 14 meV. Therefore, bulk Ta2Pd3Te5 is
a narrow-gap semiconductor with a global band gap of $\sim$14 meV.

Figure 2: Topological band structure of Ta2Pd3Te5. (a) Calculated band
structure of monolayer Ta2Pd3Te5. (b) Magnified view of the blue-shaded area
in (a), showing the existence of a band gap. The calculated gap is
approximately 5 meV. (c) and (d) ARPES intensity plots at the Fermi level and
EB=0.35 eV, respectively. The blue lines indicate the surface BZs of
Ta2Pd3Te5. (e) ARPES intensity plot of the band structure along the
$\bar{\Gamma}$–$\rm\bar{Y}$ direction. (f) Slab calculation results of the
band structure along the $\bar{\Gamma}$–$\rm\bar{Y}$ direction.

Before showing further experimental results of Ta2Pd3Te5, we briefly discuss
the topological properties based on our first-principles calculation results.
For bulk Ta2Pd3Te5, the symmetry indicators
($\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times\mathbb{Z}_{4}$)
are 0. However, it has a nontrivial mirror Chern number in the $k_{y}=0$ plane
due to the band inversion at the $\Gamma$ point NieS2020 , which indicates the
topological nature of bulk Ta2Pd3Te5. In the monolayer limit, Ta2Pd3Te5
becomes a 2DTI NieS2020  with a similar band inversion. Its nontrivial
topology has also been confirmed by the one-dimensional Wilson loop method.
Figure 2(a) shows the band structure of monolayer Ta2Pd3Te5, where an inverted
band gap near the Fermi level can be identified. The calculated gap along the
$\Gamma$–Z direction is approximately 5 meV. Notably, the gap fitted based on
our transport measurements ($\sim$14 meV) on bulk samples is larger than the
calculated value. We will later show that our STS measurements also indicate a
significantly larger gap compared to the calculation results. This
inconsistency probably originates from the fact that density functional theory
(DFT) calculations may underestimate the band gap of materials.

To study the electronic structure of Ta2Pd3Te5, we performed ARPES
measurements on a freshly cleaved surface. An ARPES intensity map of the Fermi
surface is displayed in Fig. 2(c), which shows a weak spectral weight along
the $\bar{\Gamma}$–$\rm\bar{Y}$ direction. Because of the large lattice
constant along the _c_ direction, we observed four BZs along
$\bar{\Gamma}$–$\rm\bar{Z}$. With increasing binding energy, an oval-like
pocket appears at the $\bar{\Gamma}$ point, as shown in Fig. 2(d). The band
structure along the $\bar{\Gamma}$–$\rm\bar{Y}$ direction is shown in Fig.
2(e), which agrees well with our slab calculation results (see Fig. 2(f)).
These ARPES results, combined with the DFT calculations, provide strong
evidence of the topological band structure of Ta2Pd3Te5.

Figure 3: STM characterization of the topological edge states in Ta2Pd3Te5.
(a) STM topographic image containing a step edge. Dashed black lines indicate
the position of the step edge. (b) Line profile along the solid black line in
(a). (c) dI/dV curves taken on the flat terrace (blue) and near the step edge
(black). (d) Series of dI/dV spectra taken along the red arrow in (a). The red
dashed line indicates the emergence of in-gap states near the step edge. (e)
dI/dV maps taken in the same area as (a). The bias voltage is indicated on the
left side of each map. Pronounced edge states appear when the bias voltage is
in the range of -40 to 20 meV, as indicated by the black dashed lines. (f)
Averaged dI/dV map at four different bias voltages: -40, -20, 0, and 20 mV.

Now that we have shown the existence of a topological band structure and a
band gap in Ta2Pd3Te5, we proceed to studying the topological edge states,
which are a key signature of the QSH state in monolayer Ta2Pd3Te5. Because of
the weak interlayer coupling, topological edge states are expected to exist at
the periphery of the topmost layers. An ideal technique to study the edge
states is STS because the tunneling conductance is proportional to the local
density of states (LDOS). Figure 3(a) shows an STM image that contains a step
edge. From the line profile in Fig. 3(b), the step height is 1.4 nm, which
corresponds to the lattice constant along the $a$ direction. Figure 3(c) shows
the dI/dV curves taken on the flat terrace and near the step edge. On the flat
terrace, we observe a band gap at the Fermi level, in agreement with the
semiconductor behavior of Ta2Pd3Te5. The estimated gap size is approximately
43 meV, with the valence band top and conduction band bottom at -33 meV and 10
meV, respectively. The band gap shows negligible variation across the flat
terrace, despite the height variation of the Te chains, as shown in
Supplementary Fig. S1. This indicates the high spatial homogeneity of the
surface, which provides further evidence for the global nature of the band
gap. Notably, the gap estimated from our STS data is larger than that fitted
based on the transport measurements. This may originate from the surface
sensitivity of the STS technique, which indicates a larger band gap in
monolayer Ta2Pd3Te5 than in the bulk material. Near the step edge, however,
the LDOS is dramatically enhanced, featuring a V-shape in the energy range
between -40 and 40 meV. This indicates the existence of edge states inside the
band gap. To better visualize the evolution of the edge states, we present a
series of dI/dV curves across the step edge in Fig. 3(d). When the tip
approaches the step edge, the tunneling conductance inside the gap gradually
increases, as indicated by the red dashed line in Fig. 3(d).

To confirm the spatial distribution of the edge states, we performed real
space dI/dV mapping, as shown in Fig. 3(e). When the bias voltage is set to be
within the band gap (e.g., 0 and -20 mV), the tunneling conductance is
dramatically enhanced near the step edge. The enhancement of the tunneling
conductance vanishes at bias voltages outside the band gap, resulting in a
uniform LDOS over the entire surface (e.g., at $\pm$80 mV). Figure 3(f) shows
an averaged dI/dV map at several bias voltages that span the band gap, where
the enhancement of the LDOS near the step edge can be clearly seen. The fact
that these edge states are located inside the gap agrees well with their
topological nature. Notably, the step edge is not straight and contains
several different terminations. Nevertheless, edge states always exist,
despite the slight variation in the details of the STS spectra. This provides
strong evidence for the robustness of the edge states, which is also
consistent with their topological nature NieS2020 . Similar topological edge
states have been reported in several other topological materials, such as
ZrTe5 WuR2016  and TaIrTe4 DongX2019 .

In summary, our results support the existence of significant inverted gap and
topological edge states in the van der Waals material Ta2Pd3Te5, thus
providing strong evidence for QSH states in Ta2Pd3Te5. In stark contrast to
WTe2, multilayer and even bulk Ta2Pd3Te5 hosts a similar inverted gap at the
Fermi level. This is beneficial for device applications because multilayer
samples are typically more inert and have higher tunability. Therefore, we
expect that Ta2Pd3Te5 will become a promising material for fabricating QSH
devices.

## Acknowledgments

This work was supported by the Ministry of Science and Technology of China
(Grants No. 2018YFE0202700, No. 2017YFA0302901, No. 2016YFA0300604, and No.
2016YFA0300904), the National Natural Science Foundation of China (Grants No.
11974391, No. 11974395, No. U2032204, No. 11774399, No. 11825405, and No.
1192780039), the Beijing Natural Science Foundation (Grants No. Z180007 and
No. Z180008), the Strategic Priority Research Program of the Chinese Academy
of Sciences (Grants No. XDB33030100 and No. XDB30000000), and the K. C. Wong
Education Foundation (GJTD-2018-01). ARPES measurements were performed under
the Proposal No. 19BG007. We thank the N-BARD, Hiroshima University for
supplying liquid He.

## References

  * (1) M. Z. Hasan and C. L. Kane, Colloquium: topological insulators. Rev. Mod. Phys. 82, 3045-3067 (2010).
  * (2) X.-L. Qi and S.-C. Zhang, Topological insulators and superconductors. Rev. Mod. Phys. 83, 1057-1110 (2011).
  * (3) Y. Ando, Topological insulator materials. J. Phys. Soc. Jpn. 82, 102001 (2013).
  * (4) M. König, S. Wiedmann, C. Brüne, A. Roth, H. Buhmann, L. W. Molenkamp, X. L. Qi, and S. C. Zhang, Quantum spin Hall insulator state in HgTe quantum wells. Science 318, 766-770 (2007).
  * (5) C. Liu, T. L. Hughes, X.-L. Qi, K. Wang, and S.-C. Zhang, Quantum spin Hall effect in inverted type-II semiconductors. Phys. Rev. Lett. 100, 236601 (2008).
  * (6) I. Knez, R.-R. Du, and G. Sullivan, Evidence for helical edge modes in inverted InAs/GaSb quantum wells. Phys. Rev. Lett. 107, 136603 (2008).
  * (7) L. Du, I. Knez, G. Sullivan, and R.-R. Du, Robust helical edge transport in gated InAs/GaSb bilayers. Phys. Rev. Lett. 114, 096802 (2015).
  * (8) F. Yang, L. Miao, Z. F. Wang, M.-Y. Yao, F. Zhu, Y. R. Song, M.-X. Wang, J.-P. Xu, A. V. Fedorov, Z. Sun, G. B. Zhang, C. Liu, F. Liu, D. Qian, C. L. Gao, and J.-F. Jia, Spatial and energy distribution of topological edge states in single Bi(111) bilayer. Phys. Rev. Lett. 109, 016801 (2012).
  * (9) I. K. Drozdov, A. Alexandradinata, S. Jeon, S. Nadj-Perge, H. Ji, R. J. Cava, B. Andrei Bernevig, and A. Yazdani, One-dimensional topological edge states of bismuth bilayers. Nat. Phys. 10, 664-669 (2014).
  * (10) S. Tang, C. Zhang, D. Wong, et al. Quantum spin Hall state in monolayer 1T′-WTe2. Nat. Phys. 13, 683-687 (2017).
  * (11) Z. Jia, Y.-H. Song, X.-B. Li, K. Ran, P. Lu, H.-J. Zheng, X.-Y. Zhu, Z.-Q. Shi, J. Sun, J. Wen, D. Xing, and S.-C. Li, Direct visualization of a two-dimensional topological insulator in the single-layer 1T′-WTe2. Phys. Rev. B 96, 041108(R) (2017).
  * (12) L. Peng, Y. Yuan, G. Li, X. Yang, J.-J. Xian, C.-J. Yi, Y.-G. Shi, and Y.-S. Fu, Observation of topological states residing at step edges of WTe2. Nat. Commun. 8, 65 (2017).
  * (13) F.-f. Zhu, W.-j. Chen, Y. Xu, C.-l. Gao, D.-d. Guan, C.-h. Liu, D. Qian, S.-C. Zhang, and J.-f. Jia, Epitaxial growth of two-dimensional stanene. Nat. Mater. 14, 1020-1025 (2015).
  * (14) F. Reis, G. Li, L. Dudy, M. Bauernfeind, S. Glass, W. Hanke, R. Thomale, J. Schäfer, R. Claessen, Bismuthene on a SiC substrate: A candidate for a high-temperature quantum spin Hall material. Science 357, 287-290 (2017).
  * (15) S. Y. Zhu, Y. Shao, E. Wang, L. Cao, X.-Y. Li, Z.-L. Liu, C. Liu, L.-W. Liu, J.-O. Wang, K. Ibrahim, J.-T. Sun, Y.-L. Wang, S. Du, and H.-J. Gao, Evidence of topological edge states in buckled antimonene monolayers. Nano Lett. 19 6323-6329 (2019).
  * (16) J. Deng, B. Xia, X. Ma, H. Chen, H. Shan, X. Zhai, B. Li, A. Zhao, Y. Xu, W. Duan, S.-C. Zhang, B. Wang, and J. G. Hou, Epitaxial growth of ultraflat stanene with topological band inversion. Nat. Mater. 17, 1081-1086 (2018).
  * (17) C.-Z. Xu, Y.-H. Chan, P. Chen, X. Wang, D. Flötotto, J. A. Hlevyack, G. Bian, S.-K. Mo, M.-Y. Chou, and T.-C. Chiang, Gapped electronic structure of epitaxial stanene on InSb(111). Phys. Rev. B 97, 035122 (2018).
  * (18) Z. Fei, T. Palomaki, S. Wu, W. Zhao, X. Cai, B. Sun, P. Nguyen, J. Finney, X. Xu, and D. H. Cobden, Edge conduction in monolayer WTe2. Nat. Phys. 13, 677-682 (2017).
  * (19) S. Wu, V. Fatemi, Q. D. Gibson, K. Watanabe, T. Taniguchi, R. J. Cava, and P. Jarillo-Herrero, Observation of the quantum spin Hall effect up to 100 kelvin in a monolayer crystal. Science 359, 76-79 (2018).
  * (20) Y. Shi, J. Kahn, B. Niu, Z. Fei, B. Sun, X. Cai, B. A. Francisco, D. Wu, Z.-X. Shen, X. Xu, D. H. Cobden, and Y.-T. Cui, Imaging quantum spin Hall edges in monolayer WTe2. Sci. Adv. 5, eaat8799 (2019).
  * (21) M. N. Ali, J. Xiong, S. Flynn, J. Tao, Q. D. Gibson, L. M. Schoop, T. Liang, N. Haldolaarachchige, M. Hirschberger, N. P. Ong, and R. J. Cava, Large, non-saturating magnetoresistance in WTe2. Nature 514, 205-208 (2014).
  * (22) A. A. Soluyanov, D. Gresch, Z. Wang, Q. Wu, M. Troyer, X. Dai, and B. A. Bernevig, Type-II Weyl semimetals. Nature 527, 495-498 (2015).
  * (23) Z. Guo, D. Yan, H. Sheng, S. Nie, Y. Shi, and Z. Wang, Quantum spin Hall effect in monolayer Ta2M3Te5 (M=Pd, Ni). arXiv: 2012.05917 (2020).
  * (24) R. Wu, J.-Z. Ma, S.-M. Nie, L.-X. Zhao, X. Huang, J.-X. Yin, B.-B. Fu, P. Richard, G.-F. Chen, Z. Fang, X. Dai, H.-M. Weng, T. Qian, H. Ding, and S. H. Pan, Evidence for topological edge states in a large energy gap near the step edges on the surface of ZrTe5. Phys. Rev. X 6, 021017 (2016).
  * (25) X. Dong, M. Wang, D. Yan, X. Peng, J. Li, W. Xiao, Q. Wang, J. Han, J. Ma, Y. Shi, and Y. Yao, Observation of topological edge states at the step edges on the surface of Type-II Weyl semimetal TaIrTe4. ACS Nano 13, 9571-9577 (2018).
  * (26) H. Iwasawa, K. Shimada, E. F. Schwier, M. Zheng, Y. Kojima, H. Hayashi, J. Jiang, M. Higashiguchi, Y. Aiura, H. Namatame, and M. Taniguchi, Rotatable high-resolution ARPES system for tunable linear-polarization geometry. J. Synchrotron Radiat. 24, 836-841 (2017).
  * (27) P. E. Blöchl, Projector augmented-wave method. Phys. Rev. B 50, 17953-17979 (1994).
  * (28) G. Kresse and D. Joubert, From ultrasoft pseudopotentials to the projector augmented-wave method. Phys. Rev. B 59, 1758-1775 (1999).
  * (29) G. Kresse, and J. Furthmüller, Efficiency of ab-initio total energy calculations for metals and semiconductors using a plane-wave basis set. Comput. Mater. Sci. 6, 15-50 (1996).
  * (30) G. Kresse and J. Furthmüller, Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set. Phys. Rev. B 54, 11169-11186 (1996).
  * (31) J. P. Perdew, K. Burke, and M. Ernzerhof, Phys. Rev. Lett. 77, 3865-3868 (1996).