Prefix-Tuning for Arbitrary Output Sequences on Pretrained Transformers

AI summary

Overview

Research area: Natural Language Processing — specifically parameter-efficient fine-tuning (PEFT) and the theoretical expressiveness of prefix-tuning for large language models.

Technical level: Advanced. The paper is a theorem-and-proof paper in the style of mathematical machine learning, with attention formulas, linear-algebraic constructions, and a training-free algorithm derived from the theory.

Scope: The paper proves necessary and sufficient conditions under which a prefix exists that forces a fixed, pretrained autoregressive Transformer to generate an arbitrary target output sequence, and it derives and empirically tests a training-free algorithm for computing that prefix.

What This Paper Is About

Prefix-tuning adapts a pretrained language model by prepending a small set of learned continuous vectors (a "prefix") to the model's hidden states while keeping all original weights frozen. It works in practice, but nobody had established whether prefixes are expressive enough to induce any desired output from any input. This paper answers that open question — called Problem 1 / Problem 2 in the paper — for a Transformer that is fixed in advance, showing that a prefix exists precisely when the target output lies in the model's range, and giving an explicit way to compute it.

Key Contributions

1. A complete resolution of the prefix expressiveness question. The authors prove (Theorem 2.1) that for a pretrained autoregressive Transformer, given a target output y that lies in the model's range (i.e., reachable by autoregressive generation from some source input x'), a (generalized) prefix exists that makes the model produce y from any user input x. They also show the assumption is necessary, so the result is stated to be best possible.

2. An explicit, constructive, training-free algorithm. The prefix is computed by solving a fixed, small number of linear systems, rather than by gradient-based optimization. The construction is based on a framework the authors call attention matching.

3. Full characterization including architectural caveats. For Transformers with residual connections and positional encodings, the theorem additionally requires p = n (source input length equals user input length) and x_n = x'_p (the last user token equals the last source token). The paper argues both conditions are mild in practice, and shows counterexamples exist if they are dropped.

4. A best-possible result on dataset size. Theorem 2.2 constructs a fine-tuning dataset of two elements that cannot be realized even under full fine-tuning, showing the single-pair formulation of Theorem 2.1 cannot be trivially extended to larger datasets.

5. The first empirical validation of such a theoretical result on modern LLMs. The authors report experiments on GPT-2 (multi-head attention, residual connections, positional encodings) and Qwen3-4B (which uses grouped-query attention, GQA), describing a high success rate in fully controlling output sequences.

Main Findings

• Sufficiency (Theorem 2.1): A generalized prefix satisfying the control condition exists if (a) there is a source input x' producing y, and (b) condition (10) holds at every attention head — namely, that there exists a vector s such that E_h(x_n, s), E_h(y_1, s), …, E_h(y_{k-1}, s) are all distinct.

• Necessity: The source-input assumption cannot be removed — if y is not in the range of T, no such prefix may exist. Likewise, when residual connections and positional encodings are present, counterexamples exist when p = n and x_n = x'_p are removed.

• Condition (10) is never violated in experiments, even when there are repeated tokens in y or x_n — attributed to positional encodings giving identical tokens slightly different embeddings.

• The linear-system formulation is tractable: the problem reduces to p + k - 1 linear systems, each with m variables and k equations, all sharing the same k × m coefficient matrix. Dimensionality scales linearly with sequence length rather than embedding dimension. The prefix length must satisfy m ≥ k.

• Attention logits can be very large, defeating naive overriding. Figure 1 plots the maximum (across heads) pre-softmax scaled dot-product attention logit across layers and decoding steps in GPT-2, using the prompt "To be, or not to be, that is the question" and generating 5 tokens; for certain layer–step pairs the maximum exceeds 20. Since exp(20) overwhelms smaller contributions, the authors add an explicit override constraint and a minimal-norm construction for prefix vectors (Equation 12).

• Best-possible with respect to dataset size (Theorem 2.2): a two-element fine-tuning dataset exists that cannot be realized even for full fine-tuning. The authors argue such datasets are contradictory rather than representative of realistic fine-tuning.

• Experimental results are stated qualitatively in the available text: the abstract and introduction report "extensive experiments" on GPT-2 and Qwen3-4B with a "high success rate" in completely controlling output sequences. The paper content provided here is truncated mid-Section 5, so specific success rates, dataset sizes, and benchmark numbers are not reported in the available material.

Methodology in Plain English

The core obstacle is that forcing a specific output out of a language model looks like an enormous system of nonlinear equations with no guarantee of a solution. The authors sidestep this by changing what they try to match.

Instead of trying to match the model's final probabilities, they match the attention outputs produced at each layer as the model generates. The reasoning: if the internal attention outputs during generation from the user input (with prefix) are identical to those during generation from a source input that is known to produce the target output, then every downstream layer and the final next-token prediction will also be identical, so the same tokens get generated.

Their construction works like this:

1. Run the model on a known source input that produces the target output, and record the attention behavior.
2. Allow prefix vectors to be split into separate "key" and "value" parts, and make them head-specific. This decoupling turns the nonlinear matching problem into a linear one.
3. Also apply an "override" trick: repeat each prefix vector r times so that its contribution dominates the sums in the attention formula.
4. Each prefix vector's value part is written as a linear combination of the source input embeddings and previously generated output embeddings, introducing m(p+k-1) unknowns. Matching coefficients gives p + k - 1 linear systems sharing one coefficient matrix, solved with standard linear algebra.
5. To guarantee the coefficient matrix has full rank, construct the key-side prefix vectors to point along (W_K^h)^T W_Q^h y'_t with a scale chosen so that the attention logit hits a threshold attn_lim — this simultaneously satisfies the override requirement and keeps the vector's norm minimal.

The entire procedure is training-free and runs with minimal hardware: no gradients, no backpropagation through the model, and no modification of the pretrained weights. The authors note a related attention-matching framework was independently developed by Zweiger et al. (2026) for KV cache compaction, with differences discussed in Appendix H.

Why This Matters

Impact on research. The paper closes a stated open problem in PEFT theory and, unlike prior expressiveness work, does so for a fixed pretrained model rather than a hand-crafted one, and in the autoregressive generation setting rather than one-shot sequence-to-sequence mapping. The authors identify three limitations of prior analyses — model mismatch, generation mismatch, and impractical scaling assumptions on width, depth, or prefix length — and position their result as removing all three. They also report this as the first empirical demonstration of a prefix expressiveness theorem on a modern LLM.

Real-world applications (as motivated in the paper):

• Domain adaptation where full fine-tuning is too expensive to update or store all parameters, e.g., specialized terminology in legal, healthcare, finance, or education settings.
• Steering model behavior in deployment without touching the base weights — the prefix can be implemented as a KV cache, so memory and inference-speed costs are low.
• Chatbot-style systems, where the paper notes the required x_n = x'_p condition is nearly automatic because user inputs typically end with a system-inserted end-of-conversation token.
• Studying and auditing model capabilities, since the result confirms that prefix-tuned models cannot exhibit behaviors absent from the original model.

Industry relevance. The paper comes from Huawei Technologies Canada Co., Ltd., and the algorithm's selling point is operational: exact-ish output control obtained by solving linear systems, with no training loop. It is validated on Qwen3-4B, a model with grouped-query attention, indicating the construction extends beyond GPT-2-era architectures.

Future Directions

• Extending to larger, consistent datasets. Theorem 2.2 shows the single-pair guarantee does not generalize to arbitrary datasets. The authors explicitly call for formalizing a notion of "consistency" in a fine-tuning dataset and extending the results to larger consistent datasets, calling this of independent interest.
• Removing the p = n length requirement. The paper states this condition exists mainly to mitigate positional encodings, that positional encodings induce only small perturbations, and that Appendix C provides an experiment supporting the claim that it is not essential in real applications — leaving a formal relaxation open.
• Understanding the limits of the override strategy numerically. The theoretical construction for full rank "performs poorly numerically," and the practical construction is justified empirically rather than provably; the gap between the provable and the numerically reliable construction is not closed.
• Quantifying the approximation error from repeated prefix vectors. The override argument only satisfies the matching condition "up to an arbitrarily small error," relying on continuity of the Transformer; how that error propagates to output-token control is not characterized in the available text.

Target Audience

Researchers and graduate students working on parameter-efficient fine-tuning, mechanistic interpretability of Transformers, or the theory of in-context and prompt-based control. It is also relevant to practitioners who need deterministic, low-cost control over LLM outputs and are comfortable with the linear-algebraic construction, and to theorists interested in expressiveness results for fixed pretrained models under autoregressive decoding. Readers wanting experimental detail should note that the results sections are truncated in the material summarized here, so concrete success rates and dataset statistics are not available from this content.

Authors’ abstract

Prefix-tuning is a parameter-efficient fine-tuning method for large language models (LLMs) that steers model outputs by prepending task-specific prefix representations to the input sequence. Despite its practical success, the theoretical understanding of the expressiveness of prefixes remains incomplete. In particular, the following question remains open: Given a pretrained autoregressive Transformer, for any input-output sequence pair $(\mathtt{x},\mathtt{y})$, does there always exist a prefix $\mathcal{S}$ such that prepending $\mathcal{S}$ to $\mathtt{x}$ induces the model to generate the target output $\mathtt{y}$? In this work, we prove that under the assumption that $\mathtt{y}$ is in the range of the pretrained Transformer, such a prefix $\mathcal{S}$ exists and can be explicitly computed by solving multiple linear systems. We further show that this assumption is necessary, in the sense that such a prefix may not exist when the assumption fails, thereby providing a complete answer to the above question. Our analysis is constructive and the obtained theoretical results hold under fairly general assumptions on model architecture. Extensive experiments on GPT-2 and Qwen3-4B demonstrate that our algorithm produces prefixes with strong control over model outputs.