TEMPERA: Test-Time Prompting via Reinforcement Learning

1 INTRODUCTION

• Prompting can deliver zero-shot and few-shot NLU performance, but prompts often require careful task-specific tuning for consistent results.Discrete prompt optimization targets meaningful instructions, exemplars, and verbalizers, while prior query-dependent discrete-prompt search is described as inefficient.Source: §1 · p. 1
• TEMPERA constructs query-dependent discrete prompts through test-time editing, formulating the editing process as a reinforcement-learning problem.The method is intended to make efficient search for query-dependent prompts feasible.Source: §1 · p. 1
• A manually chosen initial prompt lets users incorporate prior knowledge, while the editing tools usually preserve sentence meaning and make the final prompt more interpretable.The editing approach aims to balance flexible transformations with a more feasible search space than direct generation.Source: §1 · pp. 1–2
• Its action space edits instructions, in-context exemplars, and verbalizers; the method uses consecutive-prompt score differences as rewards and an attention-based policy over choices.The authors also use techniques such as reward normalization to improve training.Source: §1 · p. 2
• On average across SST2, AG News, RTE, and MR, TEMPERA achieves comparable performance using 4x fewer examples than standard fine-tuning.Figure 1 compares data efficiency in a few-shot setting.Source: Figure 1 · p. 2, §1 · p. 2
• TEMPERA achieves SoTA performance across multiple tasks, including 1.8% better in SST-2 and 3.9% better in CR than few-shot finetuning, prompt tuning, and discrete prompt optimization.The authors also report 4x greater data efficiency than traditional finetuning across four tasks.Source: §1 · p. 2

• Prompt performance can vary with exemplar order, prompt format, and training-example choice, as reported by Lu et al. (2022) and Zhao et al. (2021).Source: §2 · p. 2
• In continuous space, Lester et al. (2021) add tunable task tokens during fine-tuning; Zhong et al. (2021) optimize input-embedding prompts for factual probing, and Wu et al. (2022) report instance-independent prompt tuning boosts performance.Source: §2 · p. 2
• Discrete methods generate templates, identify label words, or search prompt tokens; AutoPrompt's best prompts are usually not human-interpretable (Shin et al., 2020a).Other methods mine or paraphrase prompts for factual knowledge probing.Source: §2 · p. 2
• Deng et al. (2022) use RL to generate prompts directly, whereas TEMPERA uses RL for efficient search in a test-time editing space.Source: §2 · pp. 2–3
• Prior exemplar methods retrieve semantically similar examples or train a dense retriever; TEMPERA uses attention-based selection over the embedding space within RL.The cited retrieval approaches are Liu et al. (2022) and Rubin et al. (2022).Source: §2 · p. 3

3.1 BACKGROUND

• The few-shot classification setup assumes a pretrained language model, K labeled training samples per class, and a separate hold-out test dataset for evaluation.Source: §3.1 · p. 3
• Discrete prompt optimization searches over text prompts rather than latent-space vectors, retaining interpretability and enabling natural-language-tool-based search.Source: §3.1 · p. 3
• The paper distinguishes three discrete-prompt components: task instructions, in-context demonstrations with labels, and verbalization choices such as label words.Source: §3.1 · p. 3

3.2 TEST-TIME EDITING

• Query-agnostic prompts omit query information, while directly generating a prompt for each query is challenging to combine with human prior knowledge or feedback.Exemplar reordering and nearest-neighbor selection are cited as evidence motivating query-dependent prompts.Source: §3.2 · p. 3
• At test time, the editing function maps an initial prompt, query, and pool of examples or verbalizers to a final prompt by changing parts such as verbalizers or examples.Source: §3.2 · p. 3
• Figure 2 depicts an attention-based policy editing instructions, in-context exemplars, and verbalizers for T rounds after training to optimize downstream-task performance.Source: Figure 2 · p. 4
• Algorithm 1 trains the policy through N episodes of T editing steps, stores state-action transitions, updates with PPO loss, and evaluates on a held-out set.Source: §3.2 · p. 4
• The editing function is trained on a fixed training dataset and deployed at test time without additional training, ground-truth labels, or a surrogate objective.Source: §3.2 · p. 4

4 TEST-TIME EDITING VIA REINFORCEMENT LEARNING

• Test-time editing is an MDP in which the initial prompt and query form the state, editing actions deterministically transition prompts, and a horizon or termination rule ends the process.The objective is to maximize expected discounted reward.Source: §4 · p. 4
• The state representation is the pretrained language model’s last hidden states for the prompt and query, which are fed to the policy network.Source: §4 · p. 5
• Actions can swap, add, or delete instruction phrases, swap in-context exemplars, and choose verbalizers for each exemplar or query.Instruction phrases are tokenized before editing; exemplars are selected from a pool initialized with examples in the prompt.Source: §4 · p. 5
• Immediate reward is the score difference between successive edits, aligning accumulated reward with the final-versus-initial prompt score when discounting is ignored.The score uses the language model’s log probability for the correct output label.Source: §4 · p. 5
• An attention-based policy attends over candidate choices and can emphasize examples that are more semantically similar to the test instance.Source: §4 · p. 5
• Sample-wise reward normalization addresses differing reward scales across training samples, while conditioning on action history mitigates loops between prompt states.The authors also report that normalizing language-model observations boosts performance.Source: §4 · p. 6

5.3 DATA EFFICIENCY FOR TEMPERA

• On various GLUE and SuperGLUE tasks, TEMPERA achieves the same performance as fine-tuning with 5.33x less data; Figure 3 reports 4x–8x data-efficiency gains, including almost 8x fewer examples on SST-2 and about 4x on Yelp.Source: §5 · p. 6, Figure 3 · p. 8, §5.3 · p. 8

5.1 FEW-SHOT TEXT CLASSIFICATION

• 1.8% absolute gain over RLPrompt on SST-2 and 3.9% gain on CR; TEMPERA outperforms most tested baselines overall.The comparison includes fine-tuning, prompt tuning, and discrete prompt optimization.Source: Table 2 · p. 7, §5.1 · p. 7

5.2 IMPORTANCE OF TEST-TIME PROMPT EDITING

• 0.8% improvement on MR and 3.0% on AG News with test-time editing; its effect was not significant on SST-2.The comparison is against TEMPERA without test-time editing; the paper reports larger gains on harder tasks.Source: Table 3 · p. 8, §5.2 · p. 8

5.5 ABLATION: DIFFERENT EDITING TECHNIQUES

• Adding verbalizer edits helps across tasks, especially MR and AG News; instruction edits marginally help SST-2 and MR, with verbalizers changing AG News performance by 1.2%.The results characterize the effects of adding or removing editing techniques.Source: Table 4 · p. 8, §5.5 · p. 9

5.4 QUALITATIVE ANALYSIS OF THE EDITS

• The learned policy combines example selection, verbalizer swapping, and phrase-level instruction edits, producing different interpretable prompts for different queries.Table 5 contrasts the readable edited prompts with prior methods that often produce non-readable prompts; red marks original text and blue marks changes.Source: §5.4 · p. 8, Table 5 · p. 9

5.6 ABLATION: NUMBER OF SHOTS

• Increasing exemplars from 2 to 4 to 8 generally improves performance, but gains are limited and AG News declines from 4 to 8 because inputs exceed RoBERTa’s 512-token limit and are truncated.The decline is reported for AG News, whose input length is longer than 512 tokens.Source: Table 6 · p. 9, §5.6 · p. 9

5.7 ABLATION: SIZE OF THE PROMPT POOL

• A larger prompt pool offers more choice of in-context demonstrations and slightly improves final performance, while results remain relatively stable across pool sizes.The number of exemplars is held at four in this comparison.Source: Table 7 · p. 9, §5.7 · p. 9

6 CONCLUSION

• TEMPERA applies reinforcement learning to edit prompts at test time for large language models.The method requires little high-level search-space guidance and can incorporate human knowledge.Source: §6 · p. 9
• The authors report that test-time editing can greatly improve pretrained language models’ downstream-task performance.Source: §6 · p. 9
• TEMPERA achieves state-of-the-art performance on multiple benchmarks, including GLUE.The conclusion also suggests this NLP–RL research intersection may inspire future work on test-time editing algorithms.Source: §6 · p. 10

A TRAINING DETAIL

• Training uses online PPO with GAE for policy optimization.The experiments use the same number of parallel environments as the few-shot setting, such as 32 in few-shot experiments.Source: A TRAINING DETAIL · p. 13
• Additional observation and reward normalization are used, and the authors report that a large parallel environment helps boost performance.Source: A TRAINING DETAIL · p. 13
• Hyperparameters used for TEMPERA across all tasks are listed in a table.Source: Table 8 · p. 13

B NETWORK ARCHITECTURE

• The policy and baseline networks share an attention-based encoder with flat attention over all candidate examples.Source: B NETWORK ARCHITECTURE · p. 13
• The encoder has 3 layers, 3 heads, and a latent dimension of 48.Source: B NETWORK ARCHITECTURE · p. 13
• Separate 2-layer MLP heads serve as the policy and baseline heads, and the policy-learning component uses no dropout.The authors report that not using dropout boosted performance.Source: B NETWORK ARCHITECTURE · p. 13

C ADDITIONAL EXPERIMENTS

• Across RTE, QNLI, SNLI, MNLI, and MRPC, TEMPERA is consistently better than most discrete prompt optimization and continuous prompt tuning methods.On several tasks, it is also better than full-model fine-tuning.Source: C ADDITIONAL EXPERIMENTS · p. 13

D NATURAL INSTRUCTIONS AND PROMPTSOURCE

• The appendix provides examples of the instructions used in experiments, with the full instruction set referenced on GitHub.Source: D NATURAL INSTRUCTIONS AND PROMPTSOURCE · p. 13
• The appendix provides examples of the verbalizers used, with the full verbalization referenced on GitHub.Source: D NATURAL INSTRUCTIONS AND PROMPTSOURCE · p. 13

E DATASET DETAIL

• The fine-tuning baseline uses Hugging Face RoBERTa for 100 epochs, a learning rate of 0.0003, and Adam.Source: E DATASET DETAIL · p. 13
• TEMPERA surpasses baselines including fine-tuning, prompt tuning, and discrete prompt search in the few-shot classification results.The table reports standard deviations in brackets.Source: Table 9 · p. 14
• TEMPERA often achieves better few-shot performance across eight tested tasks, with MRPC and QNLI as exceptions.Source: Figure 4 · p. 14

F COMPARISON OF DIFFERENT METHOD

• The comparison section is intended to clarify properties of different prompting algorithms.Source: F COMPARISON OF DIFFERENT METHOD · p. 14
• Tables 10 and 11 list the natural instructions and verbalizers used for TEMPERA across tasks.Source: Table 10 · p. 15, Table 11 · p. 15
• With 512 training examples per class, TEMPERA scales and achieves better results than fine-tuning.Source: Table 12 · p. 16
• The dataset-details table reports dataset type and training, evaluation, and test sizes; all listed sizes are few-shot.Source: Table 13 · p. 16
• TEMPERA is gradient-free and produces interpretable, query-dependent prompts.Source: Figure 5 · p. 16