Tree Prompting: Efficient Task Adaptation without Fine-Tuning (2023)

Abstract: Prompting language models (LMs) is the main interface for applying them to new tasks. However, for smaller LMs, prompting provides low accuracy compared to gradient-based fine-tuning. Tree Prompting is an approach to prompting which builds a decision tree of prompts, linking multiple prompt-LM calls together to solve a task. At inference time, each call to the LM is determined by efficiently routing the outcome of the previous call using the tree. Experiments on classification datasets show that Tree Prompting improves accuracy over competing methods and is competitive with fine-tuning. We also show that variants of Tree Prompting allow inspection of a model’s decision-making process.

## introduction pretrained language models (lms) have made remarkable progress in recent years @xcite @xcite , but their large size makes them difficult to fine-tune with gradients for specific downstream tasks. as such, prompting has become the main interface for applying pretrained language models (lms), where task-specific instructions are provided to guide an lm's behavior. the most common way to adapt lms is to use few-shot in-context examples, where input-output pairs are shown to the model. yet, few-shot prompting has a clear downside. prompt expressiveness is limited by the context length of the language model. this constraint prevents using more than a handful of examples for few-shot in-context learning, particularly in memory-constrained environments. if there is additional supervised data available for a task, users need to either ensemble together many prompts or back off to alternative lm fine-tuning approaches. tree prompting offers several advantages over existing prompting approaches. it allows users to easily incorporate large supervised training datasets without requiring larger contexts. it also allows experts to examine the decision-making process underlying a prediction in detail, which can be improved by combining with prompt generation methods. finally, tree prompting can be adapted to be compatible with many existing lms that are only accessible to the public via api calls. we demonstrate these advantages in experiments on multi-class classification benchmarks. ## background: decision trees decision trees are a classic model for classification and regression. they provide a graphical, intuitive model of decision-making, based on a cascading series of binary decisions foot_0 . at each node in the tree, a decision is made based on a single feature of the input, which leads to the next node, and ultimately to a leaf node representing a prediction. learning decision trees are constructed greedily in a top-down manner, starting from the root node, where all training data (x, y) and features ϕ(x) ∈ {0, 1} d are available. at each node, a feature that best splits the dataset into two subsets is chosen. the "best split" is determined by a criterion that measures the quality of a split. a commonly used criterion is the gini impurity from the cart algorithm @xcite . the selected feature creates two child nodes, each containing the subset of data that satisfies the respective split condition. this process is repeated recursively for each child node with the corresponding subset of the data until a stopping condition is met foot_1 . each leaf node in the final decision tree represents a decision (such as a class label prediction), determined by the majority class of the instances in the leaf. inference a decision tree makes predictions on unseen data by traversing the tree from the root node to a leaf node. starting from the root, the feature value of the example corresponding to the split feature at the current node is used to determine whether the left child or the right child node is visited next. this process is repeated until a leaf node is reached. the class label associated with this leaf node is then used as the prediction. ## tree prompting tree prompting utilizes decision trees as a method of adapting lms to specific tasks without finetuning the model. assuming access to a set of textlabel pairs (x, y), the goal is to determine a tree to best classify this data. the algorithm then proceeds in a top-down manner, where at each node, it selects the best prompt based on the chosen method for finding prompt candidates and constructing split features. however, unlike standard decision trees, we do not have access to a predetermined set of features ϕ(x). tree prompting instead constructs this feature function dynamically by constructing prompts. the value of a feature ϕ i (x) is determined by running a prompt through the lm and mapping its response to a binary value. a major benefit of utilizing decision trees in this setting is their efficiency at inference time. constructing the tree lets us compactly represent a large amount of task-specific training examples. if each ϕ i requires running one prompt, there are 2 d features. at inference time, we only need d prompt calls to classify a single datapoint. our primary approach to find prompts for features ϕ i (x) is to select random few-shot examples drawn from the training data, as shown in figure 1 . we take inspiration from bagging approaches @xcite that combine random training samples to produce complementary parallel models. by sampling random x, y pairs from the task training data and passing them to an lm, we are effectively bagging small training splits. each prompt is constructed by alternating classes with their corresponding labels in a templated form. once a prompt is constructed, the feature value is set using a pre-defined verbalizer to transform the lm's output @xcite . a verbalizer is a function that maps the lm's output probabilities into a discrete decision. a simple implementation of a verbalizer is to determine whether the predicted probability for the token yes/no is higher. in this work, we experiment with two different verbalizers: the first maps the logits to class labels (such as positive/negative for binary sentiment classification), and the second more generic verbalizer maps the logits to yes/no. when the output logits of the lm are inaccessible 4 , we can discretize the lm's outputs into "yes" "no" figure 2 : extension to the tree prompting approach using instruction prompts on the emotion dataset. each path represents a decision sequence, and colors correspond to different emotions (classes). the line width indicates the number of instances within a particular class. as the decision process advances down the tree, the classes get separated. ## experimental setup datasets we evaluate tree prompting on 13 text classification datasets. among them are binary classification datasets sst2 @xcite , subj @xcite , mpqa @xcite , cr @xcite , mr @xcite , rte @xcite , imdb @xcite , and multi-class classification datasets agnews @xcite , cb @xcite , db-pedia @xcite , trec @xcite , fpb @xcite , and emotion @xcite . appendix a.1 provides dataset statistics in model settings for the lm, we run experiments using five pretrained models: gpt-2 small (117m parameters), gpt-2 medium (355m parameters), gpt-2 large (774m parameters), gpt-2 xl (1.5b parameters) @xcite , and gpt-j (wang and komatsuzaki, 2021) (6b parameters). baselines we compare our approach tree prompting, treeprompt, to standard fine-tuning. in addition, we also compare against a conventional prompting baseline fsprompting, which directly uses few-shot example demonstrations as the prompt. we also compare the performance of our ensembling approach, treeprompt ens foot_3 , with two baseline ensembling strategies: greedy, which adds prompts to an ensemble in order of their crossvalidation accuracy), and boosting, which adds prompts to an ensemble using adaboost @xcite @xcite . ## conclusions and future work we introduce the tree prompting approach, a use of decision trees for task adaptation. experiments demonstrate that tree prompting can offer improved performance across various text classification tasks while still remaining efficient during inference. on many tasks, the model is competitive with gradient fine-tuning. additionally, the approach can be used with dynamic prompt creation to yield interpretable models. our results suggest a future direction of exploring a flexible and modularized assembly of models. one exciting direction is to extend tree prompting to generalize to tasks beyond text classification, using previous outputs to guide subsequent prompts and lms. further exploration could involve extending tree prompting to jump across nodes in the tree ( similar to long (2023) ) or introduce cycles in the tree (similar to @xcite ), and ultimately developing a program of prompts by navigating various nodes in a decision tree as though calling different functions. another direction could explore incorporating different criteria into the tree-building algorithm, e.g. fairness @xcite , sparsity @xcite , or smoothness @xcite .