What's the Magic Word? A Control Theory of LLM Prompting

Aman Bhargava, Cameron Witkowski, Manav Shah, Matt ThomsonSubmission to ICLR 2024 · Rejected

TL;DR

This paper reframes prompt engineering through classical control theory, treating an autoregressive large language model (LLM) as a discrete dynamical system and prompts as control inputs. By analyzing the "reachable set" of token outputs, the authors prove mathematical conditions under which an output is unreachable in self-attention and empirically demonstrate that prompts of 10 tokens or fewer can steer open-source LLMs to output the "ground-truth" next token over 97% of the time.

What Problem Does This Paper Address?

Prompt engineering is ubiquitous for eliciting desired behavior from pre-trained language models, yet it remains largely empirical, heuristic-driven, and poorly understood from a mathematical standpoint. Standard metrics like cross-entropy loss tell us what a model likely generates by default, but they fail to answer fundamental questions about steerability:

  • Can any desired output token sequence be forced simply by prepending an optimal sequence of prompt tokens (a "magic word")?
  • If not, what outputs are fundamentally reachable, and what is the minimum control cost (prompt length) required to elicit them?

The authors bridge this gap by establishing a formal control-theoretic foundation for prompt optimization.

Methods

The authors introduce a rigorous mathematical framework modeling LLM generation as a discrete-time, shift-and-grow dynamical system where the prompt $u$ acts as an external control signal:

  • Theoretical Reachability Analysis: The authors prove a necessary condition (Theorem 1) for an output representation to be excluded from the reachable set of a self-attention head. This analytic upper bound depends on the number of prompt tokens $k$, the bounds on token representation norms, and the maximum singular values of the projection weight matrices ($W_q, W_k, W_v$). Intuitively, control tokens steer the output by reallocating attention away from the initial input state $x_0$, but their ability to overpower $x_0$ is fundamentally constrained by parameter magnitudes and prompt length.
  • Empirical Reachability via Prompt Optimization: To establish empirical lower bounds on the reachable output set, the authors deploy a hybrid search procedure called Back-off Prompt:
  • Greedy Back-Generation (novel): For very short prompt constraints ($k \le 3$), they iteratively evaluate all possible single-token extensions prepended to the input by running $|V|$ parallel evaluations.
  • Greedy Coordinate Gradient (GCG): For longer prompts ($k \in [4, 6, 8, 10]$), they utilize first-order gradient approximations at the token embedding layer (Zou et al., 2023) to iteratively swap prompt tokens.

Datasets

The authors evaluated controllability across three foundation models—Falcon-7b, Llama-7b, and Falcon-40b—using:

  1. Wikitext Benchmark (Merity et al., 2016): 5,000 sample sequences with context lengths $|x_0| \in [8, 32]$ tokens, testing whether the true next Wikitext token $y^*$ is reachable.
  2. Top-75 Model Likelihood Dataset: A synthetic set of 25 Wikitext contexts paired with the top 75 most probable next tokens under the model's base distribution $P_{LM}(y|x_0)$.
  3. Uniform Rank Synthetic Dataset: A dataset pairing contexts with tokens sampled uniformly across the model's entire vocabulary distribution (from rank 1 down to the least probable token).

Key Insights and Ideas

  • LLMs as Controlled Dynamical Systems: Prompting fits cleanly into systems theory, enabling formal definitions of output reachability, state growth, and $k - \epsilon$ controllability (the proportion $1 - \epsilon$ of targets achievable within prompt length $k$).
  • Prior Probability Doesn't Preclude Reachability: A low prior probability or high base cross-entropy loss does not imply an output is unreachable. In fact, prompts as short as $k \le 4$ tokens could steer the model to output tokens that originally had near-zero base probability.
  • Log-Linear Controllability Scaling: Across prompt length $k$, the unreachability fraction $\log(\epsilon)$ decreases roughly linearly with $k$ for a given context length.
  • Attention Decomposition: The proof of Theorem 1 highlights that self-attention can be algebraically decomposed into separate components driven by prompt tokens versus context tokens, linked primarily via normalization scalar cross-terms.

Key Results

  • Ground Truth Reachability: With a prompt length constraint of $k \le 10$, the correct ground-truth next token from Wikitext is reachable over 97% of the time across the evaluated models (e.g., 97.16% on Falcon-7b).
  • Top-75 Reachability: The top 75 most likely next tokens are reachable at least 85% of the time (and over 89% for Falcon-7b) with $k \le 10$.
  • Steering to Arbitrary Tokens: When targeting tokens sampled uniformly across the entire vocabulary, 46.43% were reached within $k \le 10$. Notably, the required prompt length did not correlate strongly with prior token rank—even the least likely tokens in the vocabulary could frequently be reached with modest prompt lengths.

Limitations and Future Work

  • Single-Token Horizon: Experiments focus on immediate, single-step next-token prediction ($|y^*| = 1$). Extending controllability analysis to multi-token outputs and multi-step dynamics (e.g., iterative autoregressive decoding, tool-use, chain-of-thought) remains open.
  • Architectural Scope of Proof: Theorem 1 analyzes an isolated self-attention head; extending reachability bounds to full transformer blocks (with layer normalization, MLPs, and residual connections) is left for future work.
  • Cross-Model Comparability: Direct metric comparisons across different LLM families remain difficult due to varying tokenizer vocabularies (e.g., 32k for LLaMA vs. ~65k for Falcon).
  • Future Directions: Exploring distributional control (steering to target probability distributions rather than argmax outputs), multi-agent LLM control (LLMs learning to control other LLMs), and composable control architectures.

Summary updated

Abstract

Prompt engineering is effective and important in the deployment of LLMs but is poorly understood mathematically. Here, we formalize prompt engineering as an optimal control problem on LLMs -- where the prompt is considered a control variable for modulating the output distribution of the LLM. Within this framework, we ask a simple question: given a sequence of tokens, does there always exist a prompt we can prepend that will steer the LLM toward accurately predicting the final token? We call such an optimal prompt the magic word since prepending the prompt causes the LLM to output the correct answer. If magic words exist, can we find them? If so, what are their properties? We offer analytic analysis on the controllability of a self-attention head where we prove a bound on controllability as a function of the singular values of its weight matrices. We take inspiration from control theory to propose a metric called $k - \epsilon$ controllability to characterize LLM steerability. We compute the $k-\epsilon$ controllability of a panel of large language models, including Falcon-7b, Llama-7b, and Falcon-40b on 5000 WikiText causal language modeling tasks. Remarkably, we find that magic words of 10 tokens or less exist for over 97\% of WikiText instances surveyed for each model.
BibTeX
@misc{bhargava2023what,
  author = {Aman Bhargava and Cameron Witkowski and Manav Shah and Matt Thomson},
  title = {{What's the Magic Word? A Control Theory of LLM Prompting}},
  year = {2023},
  eprint = {2310.04444},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.04444},
}
Figure