TL;DR
Large Language Models (LLMs) are sensitive to the order of examples provided in their prompts for in-context learning (ICL). This paper introduces OptiSeq, a novel method that efficiently determines the optimal example order at inference time, significantly improving LLM accuracy across various tasks and models without requiring additional training data.
What Problem Does This Paper Address?
In-context learning (ICL) is a powerful technique that allows LLMs to perform tasks without explicit fine-tuning, by providing examples within the prompt. However, ICL is known to be fragile, with performance heavily influenced by the quality, quantity, and crucially, the order of these examples. Prior work has focused on selecting high-quality examples or determining the optimal number of examples. This paper addresses the challenge of example ordering at inference time. The authors demonstrate that even with the same set of examples, different orderings can lead to vastly different LLM outputs and performance, as illustrated by an API sequence generation task where only one of six possible orderings yielded the correct answer. This sensitivity makes it difficult to achieve consistent performance in real-world applications, especially when dynamic ordering decisions are needed without access to training or validation data.
Methods
The core of OptiSeq lies in its ability to leverage the LLM's own internal confidence scores to determine the best example order. The process involves:
- Generate Outputs for All Permutations: For a given task instruction and a set of in-context examples, OptiSeq constructs prompts for every possible permutation of these examples. These prompts are then fed to the LLM to generate candidate outputs.
- Eliminate In-Context Examples: For each generated output, the in-context examples are removed from the prompt, leaving only the original task instruction.
- Compute Log Probabilities: The LLM is then used again to compute the sum of log probabilities of the output tokens, but this time conditioned only on the task instruction (without the examples). This step aims to measure the inherent likelihood of the output sequence, independent of the specific example ordering.
- Select the Optimal Ordering: The example order that results in the highest sum of log probabilities is chosen as the optimal ordering.
A variant, EOptiSeq, is also proposed to prune the search space by first using sentence embeddings to rank examples by similarity to the test instance and anchoring the most similar example first, reducing the number of permutations to evaluate from $|E|!$ to $(E-1)!$.
Datasets
The authors evaluate their methods on a variety of datasets across two main tasks:
- API Sequence Generation:
- ToolBench (Qin et al., 2023)
- RestGPT (Song et al., 2023)
- Text Classification:
- AG News (Zhang et al., 2015)
- SST-5 (Socher et al., 2013)
- TREC (Hovy et al., 2000)
Key Insights and Ideas
- Order Matters More Than You Think: The paper provides strong empirical evidence that the order of in-context examples can significantly impact LLM performance, sometimes more than the specific examples themselves. This highlights a critical, often overlooked, aspect of prompt engineering.
- LLM Confidence as a Signal: OptiSeq cleverly uses the LLM's own log probabilities to gauge the "correctness" of an output, independent of the ordering that produced it. This is a powerful way to leverage the model's internal reasoning without needing external labels or validation sets.
- Inference-Time Optimization is Key: The proposed methods are designed to work at inference time, meaning they can adapt to new tasks and data without requiring costly retraining or pre-computation. This is crucial for dynamic, real-world applications.
- Smaller, Smarter Sets Can Outperform Larger, Random Ones: The results suggest that strategically ordering a few examples can be more effective than using a larger set of examples in a random or less optimal order, especially considering context length limitations.
Key Results
OptiSeq consistently improves accuracy across multiple LLMs (from 8B to 70B parameters) and datasets:
- API Sequence Generation: OptiSeq achieves an average improvement of 10.5 percentage points over random selection, 9.05% points over Top-K selection, and 5.5 percentage points over recent baselines.
- Text Classification: OptiSeq demonstrates an approximate improvement of 6% points compared to random selection and Top-K, and 4% over recent baselines.
- EOptiSeq, while slightly less performant than OptiSeq, still shows improvements over random and Top-K selection.
- The paper also shows that OptiSeq can improve performance even when using out-of-distribution (OOD) examples, outperforming Top-K with in-distribution (ID) examples.
Limitations and Future Work
- Computational Cost: OptiSeq requires evaluating all $|E|!$ permutations of examples, which can become computationally expensive for a large number of in-context examples (many-shot settings). EOptiSeq attempts to mitigate this by reducing the search space.
- Instance-Specific vs. Generalization: The current approach optimizes ordering for individual instances. The authors suggest future work could explore meta-learning or domain adaptation to learn transferable ordering strategies that generalize across instances and models.
- LLM Platform Support: The reliance on token-level log probability computation might be a limitation if not all LLM platforms or APIs fully support this feature. However, the authors anticipate this will improve as LLM technology evolves.
Summary updated