RetICL: Sequential Retrieval of In-Context Examples with Reinforcement Learning

Alexander Scarlatos, Andrew S. Lan

Abstract

Many recent developments in large language models focus on prompting them to perform specific tasks. One effective prompting method is in-context learning, where the model performs a (possibly new) generation/prediction task given one (or more) examples. Past work has shown that the choice of examples can make a large impact on task performance. However, finding good examples is not straightforward since the definition of a representative group of examples can vary greatly depending on the task. While there are many existing methods for selecting in-context examples, they generally score examples independently, ignoring the dependency between them and the order in which they are provided to the large language model. In this work, we propose Retrieval for In-Context Learning (RetICL), a learnable method for modeling and optimally selecting examples sequentially for in-context learning. We frame the problem of sequential example selection as a Markov decision process, design an example retriever model using an LSTM, and train it using proximal policy optimization (PPO). We validate RetICL on math problem solving datasets and show that it outperforms both heuristic and learnable baselines, and achieves state-of-the-art accuracy on the TabMWP dataset. We also use case studies to show that RetICL implicitly learns representations of math problem solving strategies.

Introduction

In-context learning (ICL) has emerged as a powerful paradigm, allowing Large Language Models (LLMs) to solve complex tasks by observing a few demonstrations within the prompt. However, LLM performance is highly sensitive to the choice and ordering of these examples. Traditional retrieval methods, such as k-Nearest Neighbors (kNN), often select examples independently based on semantic similarity to the query. This approach fails to account for synergy—where a combination of examples provides more clarity than the sum of their parts—and order effects, such as the recency bias where LLMs prioritize the final example in a prompt.

The RetICL Framework

To address these limitations, we propose RetICL (Retrieval for In-Context Learning). We frame example selection as a Markov Decision Process (MDP), where a retriever agent sequentially selects examples from a corpus to construct an optimal prompt.

Figure 1: The RetICL architecture uses an LSTM to maintain state and selects examples sequentially via bilinear transformation, optimized through PPO.

The core of RetICL is an LSTM-based retriever. The initial hidden state is seeded with the query embedding. At each step, the model selects an example based on a bilinear transformation between the current hidden state and candidate embeddings. The chosen example's embedding then updates the LSTM state, allowing the model to "remember" what has already been prompted and account for inter-example dependencies.

The model is trained using Proximal Policy Optimization (PPO) with a dual reward system:

  1. Goal Reward ($R^G$): A binary signal indicating whether the LLM produced the correct final answer.
  2. Confidence Reward ($R^C$): Calculated using the inverse perplexity of the LLM's output. This encourages the retriever to find examples that lead to high-confidence reasoning paths, helping the model distinguish between a lucky guess and solid logic.

Experimental Results

We evaluated RetICL against several baselines, including random selection, kNN, and prior RL-based methods like PromptPG, across three benchmarks: TabMWP (tabular math), GSM8K (grade-school math), and QASC (science QA).

Figure 3: Performance comparison of RetICL against various baselines across three benchmark datasets.

As shown in the results, RetICL significantly outperforms standard kNN on reasoning-heavy datasets like GSM8K (66.11% vs 59.74%) and QASC (76.13% vs 61.99%). On TabMWP, it achieves competitive performance (88.58%), nearly matching kNN. The success on GSM8K is particularly noteworthy as it suggests RetICL learns to prioritize structural similarity (mathematical logic) over mere semantic similarity (topic overlap).

Analysis and Insights

A key finding is RetICL's robustness to limited data. Even when the candidate pool is reduced to 0.1% of its original size, RetICL maintains high relative accuracy, whereas similarity-based methods degrade rapidly. Qualitative analysis further reveals that RetICL often employs a "context-then-execution" strategy, picking a general first example followed by a second example that closely mirrors the query's specific logic.

Ablation studies confirmed that both the sequential LSTM architecture and the Confidence Reward are critical components. Removing either leads to a significant drop in performance, validating the importance of modeling inter-example dependencies and LLM certainty.

Conclusion and Future Work

RetICL demonstrates that treating in-context example retrieval as a sequential decision-making problem yields superior results for complex reasoning tasks. While the training process is computationally intensive and requires access to LLM log-probabilities, the gains in accuracy and robustness are substantial. Future work will explore dynamic prompt lengths and scaling the RL training to accommodate larger sets of examples.

Summary updated

Abstract

Many recent developments in large language models focus on prompting them to perform specific tasks. One effective prompting method is in-context learning, where the model performs a (possibly new) generation/prediction task given one (or more) examples. Past work has shown that the choice of examples can make a large impact on task performance. However, finding good examples is not straightforward since the definition of a representative group of examples can vary greatly depending on the task. While there are many existing methods for selecting in-context examples, they generally score examples independently, ignoring the dependency between them and the order in which they are provided to the large language model. In this work, we propose Retrieval for In-Context Learning (RetICL), a learnable method for modeling and optimally selecting examples sequentially for in-context learning. We frame the problem of sequential example selection as a Markov decision process, design an example retriever model using an LSTM, and train it using proximal policy optimization (PPO). We validate RetICL on math problem solving datasets and show that it outperforms both heuristic and learnable baselines, and achieves state-of-the-art accuracy on the TabMWP dataset. We also use case studies to show that RetICL implicitly learns representations of math problem solving strategies.
BibTeX
@misc{scarlatos2023reticl,
  author = {Alexander Scarlatos and Andrew S. Lan},
  title = {{RetICL: Sequential Retrieval of In-Context Examples with Reinforcement Learning}},
  year = {2023},
  eprint = {2305.14502},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.14502},
}
Figure