📊 statistics

Why is prompting hard? Understanding prompts on binary sequence predictors

This paper investigates the challenges of prompting by framing it as finding optimal conditioning sequences on sequence predictors, revealing through controlled experiments and frontier model analysis that optimal prompts are often unintuitive, difficult to identify even with exhaustive search, and frequently suboptimal when using standard demonstration-based methods.

Original authors: Li Kevin Wenliang, Anian Ruoss, Jordi Grau-Moya, Marcus Hutter, Tim Genewein

Published 2026-05-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Li Kevin Wenliang, Anian Ruoss, Jordi Grau-Moya, Marcus Hutter, Tim Genewein

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a super-smart, highly trained parrot. This parrot has read millions of books, watched countless movies, and listened to every radio show ever made. It knows how to predict the next word in a sentence better than anyone else. This is your AI model.

Now, you want this parrot to do a specific trick: tell a joke, write a sad poem, or solve a math problem. You do this by giving it a prompt—a few words of instruction or an example to get it started.

This paper asks a simple but deep question: Why is it so hard to find the perfect words to give the parrot? Sometimes, the instructions that work best look completely weird, nonsensical, or even "wrong" to a human. Why does a prompt that looks like gibberish work better than a clear, logical instruction?

The authors decided to stop guessing and start testing. They built a tiny, controlled world to understand what's really happening inside the parrot's brain.

The Experiment: The Coin Flip Parrot

Instead of using a real, complex AI, they created a simple "parrot" that only understands Heads and Tails (like a coin flip).

The Training: They taught this parrot by showing it thousands of coin flips. But here's the catch: they didn't just show it fair coins. They showed it coins that were biased in different ways. Some coins landed on Heads 20% of the time, others 90%, and some were a mix of both. The parrot learned to guess the next flip based on the pattern it saw in its training.
The Task: Now, they wanted the parrot to act like a specific coin that lands on Heads 70% of the time. They asked: "What is the best sequence of Heads and Tails to show the parrot so it starts guessing 70% Heads?"

The Big Surprise: "Wrong" Prompts Work Best

You might think the best way to teach the parrot to guess 70% Heads is to show it a long list of 70% Heads and 30% Tails. That seems logical, right?

The paper found that this is often wrong.

In many cases, the optimal prompt (the one that actually works best) was a sequence that looked nothing like the task.

The Analogy: Imagine you want to teach a student who is used to studying in a quiet library to study in a noisy cafeteria. You might think showing them a recording of a noisy cafeteria is the best way to prepare them. But the paper found that sometimes, the best way to get them ready is to show them a sequence of silence that subtly tricks their brain into expecting noise.
The Reality: The "best" prompt depends entirely on how the parrot was trained (its pretraining distribution). If the parrot was trained on a specific mix of coin biases, the "magic words" to get it to behave a certain way might be a sequence of all Heads, or a weird mix of 10 Heads and 2 Tails. To a human looking at the task alone, this looks like a mistake. But to the parrot, it's a perfect key that unlocks the right behavior.

Why Is This So Hard to Figure Out?

The paper highlights three main reasons why finding these "magic words" is a nightmare:

1. The "Hidden Recipe" Problem
The parrot's behavior is shaped by a secret "recipe" (the pretraining distribution) that we usually don't know.

Analogy: Imagine you are trying to tune a radio to a specific station. You don't know what the station sounds like, and you don't know how the radio was built. You just turn the dial. Sometimes, turning it to the "obvious" spot gives you static. You have to turn it to a weird, random spot to get clear sound. Without knowing the radio's internal wiring, you can't explain why that weird spot works.

2. The "Flat Landscape" Problem
The authors visualized the search for the best prompt like walking on a hilly landscape.

Analogy: You are looking for the highest peak (the best prompt). In a perfect world, there is one sharp mountain peak, and it's easy to find. But in this paper's experiments, the "landscape" is often a flat plateau. There are hundreds of different prompts that are almost equally good.
The Consequence: If you try to find the best prompt using a small amount of data (like a small test batch), you might accidentally pick a "good enough" prompt that is actually different from the true best one. If you run the test again with a slightly different batch, you might pick a different "good enough" prompt. This makes the results unreliable and hard to interpret.

3. The "Expert Demo" Trap
A popular way to teach AI is to show it examples of an expert doing the task (e.g., "Here is how a chess grandmaster plays").

The Finding: The paper showed that showing expert examples is often less effective than using a weird, optimized prompt.
Analogy: Imagine you want a robot to play chess perfectly. You could show it 100 games played by a Grandmaster. Or, you could give it a weird, short code that forces its brain into "Grandmaster mode." The paper found that the weird code often works better than the 100 games. The expert examples are too "typical" and don't account for the robot's specific training biases.

What About Real AI (Like Chatbots)?

The authors tested these ideas on real Large Language Models (like GPT-2 and Gemma) using movie reviews.

They found the same patterns: The best prompts to generate a "positive" review weren't always positive-sounding words. Sometimes, they were short, weird, or even negative-sounding words that somehow triggered the right response.
They also found that to reliably find the best prompt, you need a huge amount of data (thousands of examples), not just the small batches (around 200) that people usually use. With small batches, you are just guessing.

The Takeaway

The paper concludes that prompting is hard because we are trying to steer a machine without knowing its full history.

The "Best" Prompt is Relative: There is no universal "best" prompt. The best prompt depends on the specific, hidden biases of the AI's training data.
Intuition Fails: What looks logical to a human (showing the AI what you want) often fails because it doesn't account for the AI's internal "math."
Reliability is Low: Unless you search exhaustively and use massive datasets, the prompts you find might be lucky guesses that don't work consistently.

In short, the paper suggests that the "magic" of prompting isn't just about writing good instructions; it's about hacking the hidden statistical biases of the AI in ways that often look completely counter-intuitive to us.

Technical Summary: Understanding Prompts on Binary Sequence Predictors

Problem Statement

Frontier models, such as Large Language Models (LLMs), can be conditioned via prompts to perform diverse tasks. However, finding effective prompts is difficult, and even when high-performing prompts are found, they are often unintuitive or "eccentric." The core problem addressed is the lack of fundamental understanding regarding why optimal prompts behave counter-intuitively, why they are hard to identify reliably, and why common heuristics (like using expert demonstrations) often fail.

The paper posits that prompting is fundamentally a problem of finding the best conditioning sequence on a near-optimal sequence predictor. The difficulty arises because the optimal prompt depends heavily on the pretraining distribution (the meta-distribution of the data the model was trained on), which is typically unknown to the user. Consequently, prompts that are optimal for a specific task may appear atypical or suboptimal when viewed solely through the lens of the task distribution.

Methodology

The authors propose a rigorous, controlled empirical framework to study prompting from a Bayesian meta-learning perspective.

Synthetic Data Generators (DGs): Instead of relying on complex natural language data where ground truth is elusive, the authors design synthetic binary sequence data generators. These include:
- Conditionally Independent Bernoulli DGs (CIB-DGs): Models where sequences are generated based on a latent bias $\tau$ drawn from a prior distribution $p_\tau$ .
- Complex DGs: Including switching processes, hierarchical models, and topic models to simulate non-i.i.d. structures.
- Bandit Decision-Maker: A two-armed Bernoulli bandit task where the goal is to induce a specific "skill level" ( $\tau$ ) in an agent to maximize returns.
Predictors: The framework evaluates two types of predictors:
- Bayes Predictors: Theoretically optimal predictors derived analytically for the synthetic DGs.
- Neural Predictors: Autoregressive models (RNNs, LSTMs, Transformers) trained via meta-learning on samples from the pretraining DGs to approximate the Bayes predictor.
Prompt Search:
- Theoretical Optimal Prompts ( $s^*$ ): Found via exhaustive search over the prompt space to minimize the expected log-loss under the task distribution $q$ . This provides a numerically guaranteed ground truth.
- Empirical Optimal Prompts ( $\hat{s}$ ): Found by optimizing prompts on finite datasets drawn from $q$ , simulating real-world prompt engineering constraints.
Metrics: The study analyzes the "proportion correct" (reliability of finding $s^*$ ), the "loss landscape" (flatness around the optimum), and the interpretability of prompts relative to the task and pretraining distributions.

Key Contributions

Rigorous Framework: Established a formal framework for analyzing optimal conditioning sequences, encompassing definitions of optimality, experimental designs, and visualization techniques.
Exhaustive Search Results: Collected over 250,000 numerically guaranteed optimal prompts. The study reveals that optimal prompts are often atypical for the task; they may not resemble samples from the task distribution but are instead tailored to exploit biases in the unknown pretraining distribution.
Reliability Analysis: Demonstrated that identifying optimal prompts is unreliable even with finite datasets. Increasing the dataset size ( $N$ ) does not always improve reliability; in some cases, it leads to inconsistent results due to flat loss landscapes where many suboptimal prompts have similar performance.
In-Context Learning vs. Optimal Prompts: Showed that prompting via expert demonstrations (a common in-context learning strategy) is often suboptimal compared to theoretically optimal prompts. In a bandit task, expert demonstrations yielded lower returns than prompts that induced specific latent skill levels through counter-intuitive reward patterns.
LLM Validation: Adapted the framework to real LLMs (GPT-2, Gemma-3, Gemini 2.5 Pro) using IMDB movie reviews. The findings on binary sequences (e.g., the difficulty of identifying optimal prompts with small batch sizes and the prevalence of short, non-intuitive prompts) were consistent with results on real models.

Key Results

Atypicality of Optimal Prompts: In a scenario where a model is pretrained on a mixture of coin biases and tasked with generating 70% heads, the optimal prompt was not a sequence of 70% heads. Instead, it was often a sequence of all ones (or other extreme counts) that most rapidly concentrated the posterior belief on the target bias, given the specific pretraining mixture.
Length and Search Space: Contrary to the intuition that longer prompts are always better, the study found that optimal prompt length does not monotonically increase with task sequence length. Shorter prompts often appear optimal because the search space for longer prompts is vast, and exhaustive search is rarely performed in practice.
The Role of Pretraining Distribution: The interpretability of a prompt is contingent on knowing the pretraining distribution. Without this knowledge, optimal prompts appear as "gibberish" or eccentric sequences.
Expert Demonstrations are Suboptimal: In the bandit experiment, prompts derived from expert demonstrations (Thompson sampling) performed worse than optimal prompts. The optimal prompts utilized specific reward patterns (e.g., a single failure followed by a streak of successes) to signal high skill levels more effectively than typical expert trajectories.
Reliability and Batch Size: Empirical optimization is highly sensitive to dataset size. Small batch sizes (e.g., $N=200$ , common in literature) yield unreliable prompts. A much larger $N$ (e.g., $N \approx 1700$ for LLMs) is required to achieve a 50% chance of identifying the optimal prompt.

Significance and Claims

The paper claims to take an initial step towards understanding optimal prompts from a statistical and empirical perspective. It argues that the unintuitive nature of prompting is not merely a flaw of current architectures but a fundamental consequence of Bayesian meta-learning on unknown pretraining distributions.

Fundamental Insight: The difficulty in prompting arises because the optimal prompt must "hack" the pretraining priors to steer the model, rather than simply mimicking the task distribution.
Limitations: The authors are modest about their claims, noting that binary tokens are drastic simplifications of natural language. While the findings offer foundational insights, they do not definitively predict the exact behaviors of full-scale frontier models. The study focuses on the pretraining phase and does not fully account for post-training effects (e.g., RLHF) or specific architectural nuances.
Implication: The work suggests that current heuristic approaches to prompt engineering (relying on intuition or small-scale search) are likely missing the true optimal solutions, which are often hidden in the complex interplay between the task and the hidden pretraining distribution.

In summary, the paper provides a theoretical and empirical basis for why "good" prompts are hard to find and why they often look strange, attributing these phenomena to the statistical necessity of aligning with an unknown pretraining meta-distribution.