Why Do Pretrained Language Models Help in Downstream Tasks? An Analysis of Head and Prompt Tuning
Authors: Colin Wei
Sang Michael Xie
Tengyu Ma
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: theory
representation learning theory
self-supervised learning theory
pretrained language models
natural language processing

Abstract: Pretrained language models have achieved state-of-the-art performance when adapted to a downstream NLP task. However, theoretical analysis of these models is scarce and challenging since the pretraining and downstream tasks can be very different. We propose an analysis framework that links the pretraining and downstream tasks with an underlying latent variable generative model of text -- the downstream classifier must recover a function of the posterior distribution over the latent variables. We analyze head tuning (learning a classifier on top of the frozen pretrained model) and prompt tuning in this setting. The generative model in our analysis is either a Hidden Markov Model (HMM) or an HMM augmented with a latent memory component, motivated by long-term dependencies in natural language. We show that 1) under certain non-degeneracy conditions on the HMM, simple classification heads can solve the downstream task, 2) prompt tuning obtains downstream guarantees with weaker non-degeneracy conditions, and 3) our recovery guarantees for the memory-augmented HMM are stronger than for the vanilla HMM because task-relevant information is easier to recover from the long-term memory. Experiments on synthetically generated data from HMMs back our theoretical findings.


Why Do Pretrained Language Models Help in Downstream Tasks? An Analysis of Head and Prompt Tuning
Colin Wei
Sang Michael Xie
Tengyu Ma
Department of Computer Science Stanford University
{colinwei, xie, tengyuma) stanford. edu
Abstract
Pretrained language models have achieved state-of-the-art performance when adapted to a downstream NLP task. However, theoretical analysis of these mod- els scarce and challenging since the pretraining and downstream tasks can be very different. We propose an analysis framework that links the pretraining and downstream tasks with an underlying latent variable generative model of text the downstream classifier must recover a function of the posterior distribution over the latent variables. We analyze head tuning (learning classifier on top the frozen pretrained model) and prompt tuning in this setting. The generative model in our analysis either Hidden Markov Model (HMM) or an HMM augmented with latent memory component, motivated by long-term dependencies in nat- ural language. We show that 1) under certain non-degeneracy conditions on the HMM, simple classification heads solve the downstream task. 2) prompt tuning obtains downstream guarantees with weaker non-degeneracy conditions, and 3) recovery guarantees for the the vanilla HMM because task-relevant information is easier to recover from the long-term memory. Experiments synthetically generated data from HMMs back our theoretical findings.
HMM are stronger than for
Introduction
Natural language processing (NLP) has been revolutionized by large-scale pretrained language models such as BERT 4 and GPT (25), which are adapted to a variety of downstream NLP tasks. Although large body of empirical work seeks to understand the effectiveness of pretrained models 5 12 35 34 27 [5], theoretical understanding is searce. Theoretically analyzing the relationship between the pretraining and downstream tasks is challenging because pretraining and downstream settings can greatly differ.
The key starting point for our analysis is to link the pretraining and downstream settings through an underlying generative model of the data. We model the data distribution as latent variable model and the downstream task as function of the latent variables. Assuming that pretraining on large corpus allows us to learn the generative model, the conditional token probabilities predicted by the pretrained model carry information about the hidden variables. In downstream adaptation, we aim to recover this information to solve the downstream task.
Though full finetuning is the de facto empirical standard, analyzing it is challenging because it requires characterizing the weights of the pretrained model. In this paper, we focus head tuning
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and prompt tuning, which both freeze all pretrained parameters and allow us to treat the pretrained model as a black box. Head tuning 22 trains task-specific heads on top of the pretrained model outputs. Prompt tuning [31 19 9 21 optimizes a task-specific "prompt" that is concatenated to the model input. Studying prompt tuning is particularly interesting since it can match the performance of full finetuning with less computation time [19 9 21.
Our work contrasts with prior theoretical work (28] which assumes that downstream labels are recoverable via a linear head applied to the conditional token probabilities, and analyze how errors in pretraining or model misspecification propagate downstream. We consider specific generative distributions for which we can prove these assumptions, showing that head and prompt tuning can recover the downstream labels.
Our analysis considers two data- data-generating distributions with increasing realism. First, we consider data generated from Hidden Markov Model (HMM), where the downstream task is to learn linear classifier on the posterior distribution over the hidden states (Section 3) We prove that, under strong non-degeneracy conditions on token emission probabilities, a linear head applied
pretrained model G which outputs exact conditional token probabilities (G) = P[x; x==I) can recover the downstream label (Theorem 3.3). Furthermore, we can prove better recovery guarantees with relaxed non-degeneracy assumptions (Assumption 3.T) by using continuous prompt tuning (Theorem (3.6). reflecting the strong empirical performance of prompt tuning [9 9 21). Intuitively, prompt tuning conditions the latent variables so that nonessential information for the downstream task can be ignored during the tuning phase, making task-essential information easier to recover.
Second, we also strengthen our analysis by leveraging additional structure in the data. Motivated by long-range dependences in natural language, analyze HMM variants with additional latent "memory" variables that can store long-term information more easily than vanilla HMMs (Section 4 Here, the downstream task is to learn a linear classifier on the posterior distribution of the memory variables. We show that, under weaker non-degeneracy conditions than the first setting, an attention- based classification head can recover ground-truth downstream labels from pretrained model outputs (Theorem 4.3) Intuitively, our recovery guarantees improve because the classification head can focus on the persistent, task-essential information in the memory while ignoring other transient and nonessential aspects of the latent variables. As with the vanilla HMM, we analyze prompt tuning for relaxing the non-degeneracy conditions even further (Theorem 4.6)
In summary, we relate the pretraining and downstream tasks by assuming that the downstream task is to learn classifier the posterior distributions of the latent variables defined by an underlying generative model of text. Our theoretical contributions are: 1) in this setting we analyze an HMM generative model show that simple classification heads can recover the true downstream labels under certain non-degeneracy assumptions, 2) we prove that soft prompt tuning can relax the non-degeneracy assumptions needed for downstream recovery making easier to extract task-specific information, and 3) our recovery guarantees are stronger for geemory-augmente HMMs in comparison to the vanilla HMM when tuning an attention-buan based classfication head.
We empirically evaluate our theoretical results with language models pretrained on synthetically generated data from HMMs. We find that prompt tuning obtains good downstream performance when our non-degeneracy conditions are relaxed, whereas head tuning performs poorly. Furthermore, we show that head tuning obtains better downstream performance when data is generated from memory-augmented HMM, compared to a vanilla HMM, as is predicted by our theory.
1.1
Related works
The black box nature of BERT and related models has inspired a variety of empirical works which seek to understand them. Probing papers study whether a pretrained model computes various types of structured information (c.g., syntactic [35]
[T] by evaluating the performance of simple classifiers, or
probes, on the representations 77 12 34
27
[5] Other papers ablate various aspects of pretraining,
such as changing the masking scheme 14
20
40
or permuting the word order [32].
In comparison, theoretical analysis of pretrained language models is limited. Besides (28). which we discussed in Section [ Zhang and Hashimoto (40) analyze using a linear classifier to approxi- mately recover the latent variable in Gaussian graphical model with sparse dependencies between observed variables. However, their analysis and setting are focused towards understanding syntactic dependencies between tokens, whereas we directly model and analyze downstream performance.

---

Prompt-based tuning [3 19 21 13 6, 41 23 which has improved empirical downstream performance for lightweight adaptation methods beyond head tuning approach full finetuning, is an important focus of our theoretical analysis. Shin et al. [31 employ task-specific prompts that are optimized over the díscrete token space. Schick and Schütze [29]
30) reformulate natural language
tasks as cloze-style phrases to enable few-shot learning. Subsequent methods
[19 [ 21] optimize
"soft" prompts, or continuous embedding vectors. Lester et al. [19] employ soft prompts on pretrained large-scale T5 [26] models and show that as the model size increases, prompt tuning performance can eventually match finetuning, Hambardzumyan et al. [9] applies a variant soft prompt tuning to MLM models. Li and Liang (21 propose prefix tuning, which prepends trainable prefix embedding sequence to all layers of the transformer.
More broadly, Lee et al. [18 analyze reconstruction- sanebbrrcctio- self supervueeee learning methods in general setting and show that under certain conditional independence assumptions, predicting one observed variable from another allows recovery of the latent with a linear head, Other theoretical works analyzing self-supervised or constrastive learning include 1 directly relate to particular setting.
36 38
but they do not
Formulations and notations
We analyze models pretrained on masked language modeling (MLM) objectives. Let X' denote finite vocabulary of input tokens, X² the set of variable-length sequences of tokens, and X (X1...., Xr) E X random sequence of T tokens. Let A |X] denote the space of probability distributions over tokens.
Pretraining and downstream task. Let G(z) (z), G2(z)....)) denote the masked language model which predicts a probability vector for each timestep in the input æ. Our theoretical abstraction is that G2 perfectly computes the distribution of X,, the i-th token, conditioned on all other tokens:
Gz(z) P[X;] X-; = x x=i]. Here P[X; X_; = x= E A XI is a probability vector. In particular, Gz(z)) does not depend on zi.- The downstream task involves labeled examples (ar, FF(x)) X ), where F x - y provides ground-trut downstream labels and y is a discrete set of labels for classification.
Head and prompt tuning. Head tuning trains a classification head f on top of fixed model outputs, resulting in the classifier Fzx) ((f(G(z)) > 0). We expect to be simple function such as a linear or one layer attention model. We also analyze variants where ff also takes the tokens x embeddings of input, which provides additional information. Soft prompt tuning requires viewing the pretrained model G as a function of the token embeddings; we refer to this model by G. Letting e(x) = e(xx),.... e.....,,...,, exxt) denote the token embeddings, we have G(e(z)) = G(z). Soft prompt tuning concatenates trainable prompt so that the model output is G (1,, e(x)). We consider simultaneously training the prompt parameter u and a classification head to fit the downstream task.
Notations. Let A denote the space of d-dimensional probability vectors, We work with discrete random variables V taking values in finite set V. We use P[V] APP to denote the distribution of V and P[U| V = v] E IR ( the conditional distribution of U given V U. Pr(V v) [o, 1] will denote the probability that V takes values v. We also let P(U
V] R denote the vector with entries Pr(U u V v). P e RUx) will describe the matrix with entries PLU Vm,. = Pr(U = u V V v).
For sequence v (VI...., vz), we use the notation Usy for i & j to denote (G,, (Ii,..., R.), and u.; to denote (U15-1, 1.) We let 1 denote the indicator function. For set V. we let y* = V2 u 1 u.... denote variable-length sequences of elements of V. Let O denote elementwise product. Let 1 Og denote the d-dimensional all- is and all-O's vector. We omit the subscript if the dimension is clear from context. For two vectors a, E IRd, we let a/b denote their element-wise division. We use supp(a) to denote the set of indices where vector a is non-zero.
Analysis for Hidden Markoy Models
Defining a relation between pretraining and downstream tasks the foremost challenge for analysis. We propose to link the two via latent variable generative assumptions the input distribution. We
3

---

X1 X2,
t-1 Xt embedding
Ho
H1
Hr
u, 1 e2, soft prompt, = fake token 2
e Ct pretrained model G
Task: predict
HT OTHoHHl
X1
X
1[
-[x+|x-113)
downstream task head
Figure 1: Left: Illustration of HMM graphical model. Right: Overview of the formulation and analysis setting for prompt (and head) tuning. To abstractify soft prompt tuning, we note that every token has natural embedding, the corresponding row of the emission probability matrix. We view prompt tuning as adding a fake token E to the vocabulary, assigning a row u in the emission matrix, and prepending it to the input embedding sequence. More details are provided in Section 3.1
model the downstream task as a function of the posterior distribution of the latent variables. Towards first result, this section studies the case where imputs are generated by HMMs (see Figure T (left)). which have been well-studied in the context of language and speech processing (see e.g. [24] 17.
Data distribution. Let H denote the hidden state space of the HMM. We (Ho, H,...., Hy) E 7t* to denote the sequence of hidden states. For all timesteps > 0, the transition probabilities are time-invariant, i.e. P[H; H;-1] A for A E IR [R|[||H]] For each timestep i 1, tokens X; are emitted following some time-invariant probability: P[X, H.] W for W | The joint probability of X, H
H
Pr T Pr(Ho ho) I Pr(Hl, h2 - I, H4 hz). 1=1
Downstream tasks. We assume that Ho has the meaningful information for the downstream task, which is binary classification task where the ground-truth labeling F* is assumed be linear classifier on the posterior P[H X1.T = æ]::
(x) 1 144 P[Ho X x 0)
(3.1)
for μ R HH] Our results are easily extended to the multiclass setting. We consider tuning linear head for the downstream classifier, which formally computes 1(b Gi (a) > 0) for b e IR X1, The following non-degeneracy condition is crucial for our recovery result in this setting.
Assumption 3.1 (Non-degeneracy, vanilla HMM). The token emission probability matrix W has linearly independent columns.
We also require the following regularity conditions on Hy and the state transitions. Assumption 3.2 (Regularity). The Markov chain Hu, H1.... ergodic, and P[Hu] has full support.
We show that if W has linearly independent columns, a linear head fits downstream labels.
Theorem 3.3. Assume that non-degeneracy (Assumption)) 3.1 and regularity (Assumption 3.2) hold. Then any downstream task F (x) of the form (3.1) can be computed by linear head on G applied to shifted sequence. That is, there exists linear head weights b RR [ such that for all supp(P[[X)..
(x) = 1 1(
where x' = (Ø, I1. is the concatenation of special token with r:
The key for the proof is to leverage the following general statement about random variables U, V, Z such that U 1 V Z, which decomposes the expression for PUU VJ.
We note that (zx) does not depend on o{ and therefore > can be any token.

---

Proposition& 3.4. Let U, V, Z be random variables such that U 1 V Z. Then for any v, P(U V =
w] PLU| 2] P[Z| V = v]. Thus, if P(U 7 has a left inverse (P[U ZJ),, then P(Z V
w] = P 2 PLU| V = =]]
By the conditional independence structure of the HMM, Proposition 3.4 immediately implies
G1(z') = WPP(H| = =x]
P[H1|X2:T+] x]] W Gx(')
where Wt is the left inverse for W, guaranteed exist by Assumption 3.1 This lets us recover
P[ X2.++1 x by applying linear function to G1 (z'). Additional linear functions will be
sufficient to obtain j P[Ha] X = x] from P[H1 ([Hi|X2:TH+ X2:++1 = xd.. We provide the full proof in
Section B
Proposition 3.4 reminiscent of the arguments of [18) which leverages the independence structure in the same way. Subsequent sections will require more complicated analyses and recovery procedures.
A drawback of Theorem 3.3 is that it relies heavily on assuming W has full column rank, which implies the necessary condition that [H|] < |. Without this assumption, it is unclear how to recover P[Hol X1.7- = xr from (zx) alone. However, in realistic settings we would expect [7]] > |xX), as increasing the size of the hidden state space improves language modeling capabilities of HMMs [3
3.1 Relaxed non-degeneracy assumptions via prompt tuning
In this section, we study applying soft, or continuous, prompt tuning [19 9 to the setting above. We show that by using soft prompt tuning, we can recover F using a linear head on G for HMMs where the non-degeneracy assumptions on W are relaxed. Our analysis provides insight into the empirical successes of prompt-tuning intuitively, prompt tuning enables better recovery of the downstream task by conditioning the output of G' to only contain task-specific information.
Soft prompt tuning trains task apecifpci embedding vectors, but analyzing how the model processes embedding vectors is challenging because it requires opening up the black box of the pretrained model. Thus, we require additional abstractions about how the pretrained model processes the embedding vectors. We will extend the mask language model to model G that maps a sequence of embeddings e Et to conditional probabilities ........ G2 (z) follows. We observe that each token z in the vocabulary X' naturally corresponds to a dimeeninal vector: the z-th row of the emission probability matrix W, or equivalently, P[X;
H.]. We denote this embedding by e(2) and call the family of embeddings (e(z) : = X3 proper embeddings. A fundamental property of HMMs is that the conditional probability P[X; X-; = x=i] only depends on Ii,..... Tt through their embeddings e(x) = (e(x1)...... e(zx)). In other words, there exists function G, such that
(Z ..) (e(())))....
In particular, we let T. compute the standard message passing algorithm 16 that computes the conditional probability of HMMs. This ensures that G. is well defined on all sequences of nonnegative vectors in [0. 1]1H1, beyond sequences of proper embeddings. We assume that pretraining produces this G. which we treat as a blackbox for prompt tuning.
In particular, for prompt tuning we can consider the case where we pass an arbitrary nonnegative vector u E [0, || to G in the first argument and proper embeddings at positions >> 1. We can interpret the embedding of fake token C. Concretely, consider adding new token 2 to the vocabulary X, and changing the emission probability at position to satisfy P[X, = ž| H1] = u and for all 2 * 2, P[X, = 2| H, [x] u) O e()). Then Gi(u, e(x1), .... e(xx)) precisely computes the conditional probability P[X, X- = (ž, (2, T1..... 21)-i] under the modified HMM. We refer the readers to Section C for the formal definition of G. and formal proofs of the interpretation above.
We consider a downstream training algorithm which trains the prompt tuning parameter described above and a linear classification head. Letting u denote the trainable prompt parameter and b | the trainable linear head weights, the model uses the embedding sequence
ē(x) + (u, e(0), e(x11.................)) (2))).....(()),,, c(xx))
(3.2)
and outputs the prediction F(x) 10 ((((x) > 0). We can provide recovery guarantees for this
model if the ground-truth classifier weights μ (defined in (3.T) and columns of the HMM transition matrix A satisfy the following relaxation of the requirement in Theorem 3.3 that W is nondegenerate.
5

---

Assumption 3.5 (Relaxed non-degeneracy condition). There exists set of essential hidden states H H. so that the columns of W corresponding H2' [W. are linearly independent. Furthermore, Ht covers all meaningful information for the downstream tasks: supp(μ) = HH"
In addition, last technical requirement on H' is as follows: there exists set B = H such that H = J Bsuppp(( In other words, 't' must be the set of all states reachable by starting from some state in B and transitioning one step in the hidden Markov chain.
Compared to Assumption 3.1] which required that all columns of W are linearly independent, Assumption 3n5 requires linear independence on a subset H of essential states. In the setting where [H| [2 the condition for Theorem 3.3 can never hold. On the other hand, Assumption 3.5 could still hold, for example,
[supp(u)] < T and the set of columns of W corresponding to hidden states in supp(μ) is linearly independent. The last technical requirement in Assumption [.5 is
also required, which could be satisfied if columns of A are sparse. The following theorem shows that when Assumption (.5tgtioonn333.ll holds, we can recover F using soft prompt tuning with linear head.
Theorem 3.6. In the above setting, assume that Assumptions 3.2 and 3.5 hold. Then F can be computed using soft prompt tuning with a linear head on G. Concretely, there is a continuous prompt parameter u. E RIHl and weight vector E RIx, such that for all E supp(P[X]]
F*(x) 1(b G2(ā(=) & 0)
where é prepends to the input embedding sequence, defined in
3.2
Theorem 3.6 provides a stronger recovery result than Theorem 3.3 which only used a linear head. This is also reflected in our synthetic experiments (Section 5 and prior work which shows that variants of prompt tuning can perform much hetter than only training the last few layers of the model [21] Our theory suggests that prompt tuning could help by conditioning the hidden variables to remove nonessential information for the task from the output of G. This makes task-essential information easier to recover.
The key proof intuition that although recovering P[Ho| XI.T = x] is impossible without strong non-degeneracy conditions (Assumption 3.1. we aim recover P[H, X1.1- z] the subset of essential states H" defined in Assumption 3.5 which suffices for computing P[Ho X x]. since Ht 2 supp(u). To recover P X æ1 on H', we observe in Lemma C.2 that prepending the prompt u is equivalent to introducing a modified random sequence X and fake token I which influences the posterior of H2 as follows:
Cz(ā(z)) r WDP(H, X = 21 O P[Ho XIT = =x)
(3.3)
for invertible diagonal matrix D and positive scalar Tz. We choose so P[H2 1 2] O
P[Hol X1.T æ] is supported only on H. As corresponding columns of W are linearly in- dependent (Assumption 3.5). we recover Pr( Ho h| X1.T x) for h E 7" via linear function of (z(ā())). This suffices for computing μ." P[Hol X = .r.. For more details, see Section C
4 Analysis for memory-augmented Hidden Markov Models
We study a memory-augmented HMM which explicitly disentangles the evolution of hidden states from a persistent "memory" variable. Inspired by natural sentences, this model is intended to better capture the distinction between syntax, which constantly evolves, and semantics, which changes less. This additional structure in the generative model allows us to strengthen our results by relaxing the non-degeneracy conditions W. the token emission probabilities. Thus. both head and prompt tuning are more powerful in this setting compared to Section 3 and can recover the downstream label with weaker non-degeneracy assumptions on W. In Section 4.2 we show that soft prompt tuning also provides an advantage over head tuning alone.
Data distribution. The memory- augmented HMM, depicted in Figure 2 can be viewed as generative variant of memory networks 39 33 and is closely related to Hidden Topic Markov HMM: a Markov chain
Models [ There are two sets of latent variables in the memory-augmentt on hidden states Ho, H1,..., meant to model the evolution of syntax, and a persistent "memory" M = (M,...., M with N total cells, where each M; takes values in a finite set M. The full joint

---

Jo
11
Jr
Ho
H
H
So
S
S
M₁
X
M1
Mr
Task: predict μ² PM xx1:)
MN
X
X
Task: predict μ PM x1:c)
Figure 2: Left: Memory-augmented HMM with single memory cell. The memory M and hidden state H, determine the emission probabilities for each state X, Right: Memory-augmentee with multiple memories Mi....y My. The hidden state H; consists of a cell index Jj and syntax state S, To sample X,, we first look up the J:-th memory cell MJ., The token emission probability then determined by the tuple (M,,, St)
HMM
probability is as follows:
Pr(X, H, M x. hr ml m 1) =
Pr(M m))r((H Ho ho) | Pr(HH h4 H
= = m, H, h₂)
The hidden state is modified to explicitly consist of disentangled cell index J E [N] and syntax state S E S, such that H₁ = (Jz, St) and H= [N] x S. To sample the token at timestep given the hidden state H, = S3),
first Jj to index the memory M, obtaining the random variable MJ.- X, is then sampled according to some time-invarinn invariant probability depending on J,, Sy:
P[X, M m, H, (j. $)] P[X, M,, my. H, [j,s)] W (im
Here W E R M|||1|] stores the emission probabilities for each choice memory cell value and hidden state. Note that in particular, the conditional probabilities for X; only depend a single memory cell for each timestep. We also note that nemory-auggmett vanilla HMMs with structured transitions because (Ho, M). (H1 M), can be viewed a Markov chain where the memory component does not change.
HMMs can be viewed as
Example 4.1 (Generating natural sentence with memory-augmentt model may generate the sentence "The cow the pasture rolled on the grass' happily." M, could store the subject ("cow"), ),, Ma the location ( ("pasture"), )) M3 the sentiment (" ("huppily"), ), and S could determine part-of-speech. For timesteps where "cow" and "rolled" are emitted J, = because we emit information related to the sentence subject. Timesteps for "pasture" " and "grass" have J, =
HMM). We consider how this
Downstream tasks. We consider downstream tasks where ground-truth labels are obtained via a linear classifier on the posterior distribution of particular memory cell j" E [N]: F* (n P[M |X = x] T 0), where μ E RIMI Intuitively, this formulation models downstream tasks which depend particular aspect of the semantics but not syntax (e.g. in the setting of Example 4.1 if j 3, the task is sentiment analysis).
4.1 Tuning attention head for recovering ground- -trth downstream labels
To recover the downstream labeling, we require an attention-based classification head, which is a function of both the input embeddings and outputs of G. Formally, let E [R|H||1 denote query parameter and 31, 3...... 3: E R| denote trainable position embeddings. Given pretrained model outputs (z) and trainable token embeddings e(x:), the attention head Attn(-) applies key and value functions K, V to compute the output as follows:
I arg maxly (K(G,(>)) + 8.)3
(4.1)
Atn((G((wo)ee(::))))
V(C.(z),e(z..))
(4.2)
T
ET

---

where arg max refers to the set of indices achieving the maximum in 4.1.. We note that standard attention heads in practice rely on the softmax function, but the expression based on arg max above captures the limiting behavior as 1 OD. We consider linear key functions given by (x)) =
(()) (z)) The value function V R X RIMIH - R uses parameters @ E IR ||]] and e [ M| and computes e()()))))(s)))))))))))))))))))))
6J ((O(V)G,(x)) e(())).
Because our generative model disentangles H and M, we relax the non-degeneracy assumption on the token emission probabilittes W, compared to Theorem [.3 The relaxed assumption only requires the columns ( (m,.h) M. to be linearly independent in subset H of "recoverable" hidden states, whereas Assumption 3.1 required all columns to be linearly independent.
Assumption 4.2 (Existence of "recoverable" hidden states). There exists a set of recoverable hidden states H { x S such that the collection of token emission probabilities from M x H." {W (W.,m,))) (ee..t)) is a linearly independent set of vectors.
Furthermore, the span of these vectors must be disjoint from the span of token emission probabiliries from M x (Hi)H"): span( (m..))
((m..)))mm.MM.ee M,,,, n span Span([W..ona (mm..())) ( Me {0px)² }-
Note that the non-degeneracy condition of Theorem 3.3 would require {W (m,)). me M. to be linearly independent, whereas Assumption 4.2 only requires linear independence for h E 7" The second condition states that Hn and HHH are distinguishable by the token emission probabilities.
We explain Assumption 1.2 the setting of Example For natural language, there might be choices of h (j,, s,) for which the set {W ImMM M of token emission probabilities is fundamentally not very diverse, and therefore not linearly independent. For example, if the syntax s; indicates "article", i.e. words such as "a", "an", and "the", the token emission probabilities would carry little information about Mj. because the choice of article does not depend much on semantics, so columns corresponding to 8; "article" would not be linearly independent, violating Assumption 3.1 However, Assumption 4.2 allows us to avoid this issue by placing such h in H' HH" a set of hidden states which we can ignore, and only including hidden states which earry a lot of information about M in Ht" In 1..1 when Jj = 2 (location), S. = "noun", the position i should convey lot about the location (in this case, "pasture"), it is more reasonable assume that (W (m, MEM is linearly independent for this hidden state.
Thus, our aim is to focus recovering information for the downstream task from positions i where H; E H. Formally, we define the following set of input sequences containing positions where the posterior of H, given x- concentrates on H(*
R + { ( x²)= E supp : with supp( |X, X-, = S H"}
(4.3)
The following theorem shows that under Assumption 4.2 we can recover F* using the attention head described above, if E R nonempty. Note that R. is nonempty the posterior of H; concentrates on Ht for some i. For natural language, it is realistic to assume this can occur because syntactic aspects of a sentence are typically low-entropy when the full sentence is observed.
Theorem 4.3. Assume that non non-degeneracy (Assumption 4.2 and regularity (Assumption hold. Define R as in (4.)). Then there exist an attention head on G(x) and token embeddings el e(;) such that the following holds for any R.
(x) = 1( (Attm((G(())
where the function Attn is in the form described in
The idea is to use the attention mechanism to attend to positions where supp(P[H, | = x=+)) c
H. The intuition of Assumption 4.2 is that such positions are more informative for recovering the latent posteriors; indeed, from the outputs (z(z) at such i, the value function in the attention will be able to recover P[M,- X1.r 2]. A full proof is provided in Section D.1
4.2 Guarantees for prompt-tuning
Though the generative modeling assumptions in this section already allowed relaxed non-degeneracy assumptions, applying soft prompt tuning allows us to relax them even further. For simplicity, we consider the setting where there a single memory cell, so M E M, and the downstream task is linear classifier on the posterior of the memory: (x) 1(p P[M]XLT
x] > 0). This
8

---

simplified setting doesn't 't require the explicit disentanglement between Jj and S; in H,, We analyze continuous prompt-wning in a setting where the pretrained model G follows the same abstraction as in Section 3.1 We modify the model to take |M dimensioonll vectors, so the proper embedding for token 2 is given by e(2) P[X; 2 M, H;] WT.- In Section D.3 we describe the formal construction and interpretation of in the more general setting with more memories.
Letting e R |MMl denote the trainable prompt parameter, we define the input embeddings ?(x:) (u, ((z.)........ e(z)))
(4.4)
The downstream model applies an attention head the output of G: F(x) 1 (((()) assumption on P[Ho] will simplify the recovery procedure (though it can be removed).
2 0), where Attn is defined in (4.2). An additional stationarity
Assumption 4.4 (Stationarity). Assumption 3.2 holds on the Markov chain Ho, H1,... Furthermore, P[H]] is the stationary distribution: Hol AP(Ho), where A is the transition matrix.
As before, we assume sparsity of μ and some non-degeneracy of W, though the assumption is more relaxed and easier to state compared to the vanilla HMM setting.
Assumption 4.5 (Relaxed version of Assumption 4.2 Let M = supp(u) denote the set of non-zero coordinates in p.. There exists a set of recoverable hidden states H., such that the collection of token emission probabilities from M x H", (W.,m,.) ME MeEt, MeH."
linearly independent.
Furthermore, the span of these vectors must be disjoint from the span of token emission probabilities from M (H+HH"): Aopan[[W..or ,,(m.))) m. me.M., en span( 33
AEH. {0
We note that Assumption 4.3 and Assumption D.5 for multiple memories, are relaxations of Assump- tion 4.2, they only consider memory values in supp(u), whereas Assumption 4.2 considers all m E M. An additional advantage of the eeemory-augmentne
HMM is that Assumption 4.2 is simpler
than Assumption 3.1 and does not require any conditions on the transition matrix A. We now state our result for recovering F* with soft prompt tuning and an attention head.
Theorem 4.6. In the setting above, suppose that non-degeneracy Assumption 4.5 and stationarity
Assumption 4.4 hold. Then there exists a prompt u and attention head on G(e(a) and the token embeddings which can compute the ground truth (x)) for any Z E R, defined in (4.3).
F (a)
1 (AAtt((G, (((()))))((())))))))
(())) 0)
where è is the embedding in 4.4 and Attn is defined in
4.2
The intuition for this proof is similar to Theorem 3.6 the soft prompt conditions the memory M to
concentrate on supp(n). As result, all irrelevant information the task is removed from (((z))) making it easier to recover the task-specifie information about the posterior of M. A more general theorem statement for the multiple memories setting, and the full proof, is provided in Section D.3
5 Simulations
We empirically evaluate our theoretical results by pretraining a BERT-like masked language model (MLM) [4] on synthetic data generated by an HMM. Our goal is to verify key implications of our theory in more realistic setting where some assumptions, such as that G outputs exact conditional probabilities, may not hold. First, we compare head and prompt tuning and show that prompt tuning improves downstream performance, especially when the recovery problem is degenerate. Second, we compare the effect of changing the data distribution from vanilla HMMs to memory- aegmore-augmented HMMs on head tuning with an attention layer. We find that the downstream performance improves when the data has a long-term memory component. These observations support our theory.
Pretraining data and downstream task. We generate pretraining data from an HMM with randomly generated transition matrix, emission probabilities, and start distributions. In all experiments, the HMMs have 10 vocabulary symbols, while the hidden state size varies. The downstream task uses input sequences XI:T of length 129, where the first token X, = [MASK]. We consider binary classifcation where labels are generated using linear functions of the analyticalty-compueed posteriors in the HMMs. In all experiments, the ground truth linear weight sparse with 6 nonzero entries at uniformly random locations with Gaussian values. More details are in Appendix
9

---

100
Prompt Tuning Head Tuning
100
Accuracy
90
Vocab size
Test Test Accuracy
90
Vanilla HMM + linear
Memory HMM attention
Vecab
80
80-
70
60
60
15 20
30
10
15
20
25
of hidden states
hidden states
HMM data, with varying hidden state sizes. Prompt tuning improves downstream accuracy especially when the problem is degenerate (HH) (. Right: Downstream accuracy of head tuning on data from vanilla HMM vs. memory-augmented HMM, across varying values of [M] Long-term dependencies in the meeoryy-aggentte HMM data improve downstream recovery with attention. We average over 20 trials (left) and 5 trials (right) of pretraining and finetuning, with 95% intervals shown.
Figure 3: Left: Head vs. prompt tuning with linear head synthetically-genenee
Head vs. prompt tuning. We compare head and prompt tuning the hidden state size of the HMM varies. The downstream label is computed via μ P[Ht1 X_=1 x_1J,, where is a random ground-truth linear weight. Head tuning learns linear head on top of the softmax probabilities predicted by the pretrained model for filling in the first [MASK] token. Prompt tuning uses the same setup but also optimizes a length 20 continuous embedding prepended to the input sequence.
Figure 3 (left) shows that prompt tuning improves downstream performance substantially across all hidden state sizes (44,8,10,15.4 10,15,25,30)) Prompt tuning improves especially when the hidden state size increases beyond the vocabulary size, which makes the recovery problem degenerate. Thus, as suggested by Theorem 3.6 prompt tuning helps relax the non-degeneracy conditions.
Memory-augmented HMMs. We investigate the effect augmenting the data-generating HMM with long-term memory. We consider the single memory case with | 4 and varying memory sizes |M| E 3, 5, 7}. The downstream label is generated by computing μ P[M X_11 x-1l. where denotes the ground-truth weights. Viewing component on M never changes, we can compare against the vanilla HMMs from the previous setting. For the memory- memory-augmented HMM, we use head tuning with a single-cell attention layer on the entire sequence of softmax probability outputs. For the vanilla HMM in the comparison, use linear head on the output at the first position, as an attention head would perform worse since the downstream task depends only on Hi, and not any other timesteps.
memory HMM as a HMM where
Figure 3 (right) verifies that head tuning recovers the downstream task better when there more structure in the data, as predicted by Theorem 4.3 Head tuning achieves near 100% downstream accuracy on all hidden state sizes.
6 Conclusion
We analyze how pretraining on generic language modeling tasks can improve performance on diverse downstream tasks. In our analysis framework, the downstream task requires predicting properties of the posterior distribution over latent variables in an underlying generative model. When the generative model is a standard HMM, downstream recovery is possible with simple classification head under strong non-degeneracy assumptions. We also show that we can relax the non-degeneracy conditions by changing the generative model to memory-augmented HMM or using prompt tuning. The distributions studied here are meant to provide first-cut result we also expect similar theorems to hold for other generative models, which we leave as interesting direction for future work.
Acknowledgements
We thank Percy Liang, Tianyi Zhang, and Nelson Liu for helpful discussions.
10

---

Funding statement
CW was supported by NSF Graduate Research Fellowship. SMX was supported by a NDSEG Fellowship. TM acknowiedges support of Google Faculty Award, NSF IIS 2045685, and JD.com. Additional revenue: CW received an honorarium for talk at G-eeserrch
References
[1] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. In International Conference on Machine Learning, 2019.
[2] Xiang Chen, Xin Xie, Ningyu Zhang, Jiahuan Yan, Shumin Deng, Chuanqi Tan, Fei Huang, Luo Si, and Huajun Chen. Adaprompt: Adaptive prompt-based finetuning for relation extraction. arXiv preprini arXiv:2104.07666 2021.
[3] Justin Chiu and Alexander M Rush. Scaling hidden markov language models. arXiv preprint 1rXiv:2011.046/4 2020.
[4] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.0480, 2018.
[5] Kawin Ethayarajh. How contextual are contextualized word representations? comparing the geometry of bert, elmo, and gpt-2 embeddings. arXiv preprint arXiv: 1990002,,,,0011,, 2019.
[6] Tianyu Gao, Adam Fisch, and Danqi Chen. Making pre-trained language models better few-shot learners. arXiv preprint 2rXiv:2012.15723: 2020.
[7] Mario Giulianelli. Jack Harding, Florian Mohnert, Dicuwke Hupkes, and Willem Zuidema. Under the hood: Using diagnostic classifiers to investigate and improve how language models track agreement information. arXiv preprint arXiv:/808.00800 2018.
[8] Amit Gruber, Yair Weiss, and Michal Rosen-Zvi. Hidden topic markov models. Artificial intelligence and statistics, pages 163-170. PMLR, 2007.
[9] Karen Hambardzumyan, Hrant Khachatrian, and Jonathan May. Warp: Word-level adversarial reprogramming, arXiv preprint arXiv:2101.0012 2021.
[10] Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss, 2021.
[11] John Hewitt and Christopher D Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages 4138, 2019.
[12] Ganesh Jawahar, Benoît Sagot, and Djamé Seddah. What does bert learn about the structure of language? In ACI. 2019-57th Annual Meeting of the Association for Computational Linguistics, 2019.
[13] Zhengbao Jiang, Frank F Xu, Jun Araki, and Graham Neubig. How can we know what language models know? Transactions of the Association for Computational Linguistics, 8:423-438, 2020.
[14] Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S Weld, Luke Zettlemoyer, and Omer Levy. Spanbert: Improving pre- pre-training by representing and predicting spans. Transactions of the Association for Computational Linguisties, 8:64-77, 2020.
[15] Taeuk Kim, Jihun Choi, Daniel Edmiston, and Sang-goo Lee. Are pre-trained language models aware of phrases? simple but strong baselines for grammar induction. arXiv preprint axXiv:2002.00737.0 2020.

---

[16] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[17] Julian Kupiec. Robust part-of-speech tagging using a hidden markov model. language, 6(3):225-242, 1992.
Computer speech
[18] Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable supe-supe learning. arXiv preprint OrXiv:2008.01066 2020.
[19] Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efffiient prompt tuning. arXiv preprint (cdi::2104008622 2021.
[20] Yoav Levine, Barak Lenz, Opher Lieber, Omri Abend, Kevin Leyton-Brown, Moshe Tennen- holtz, and Yoav Shoham. Pmi-masking: Principled masking of correlated spans. arXiv preprint arXiv:2010.0/825 2020.
[21] Xiang Lisa Li and Percy Liang, Prefix-tuning: Optimizing continuous prompts for generation. arXiv, 2021.
[22] Matthew E Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Ken- ton Lee, and Luke Zettlemoyer. Deep contextualized word representations. arXiv preprint arXiv: 2018.
[23] Guanghui Qin and Jason Eisner. prompts. arXiv preprint arXiv:2104.06599 2021.
Learning how to ask: Querying Ims with mixtures of soft
[24] Lawrence Rabiner and Bünghhwan Juang. An introduction to hidden markov models. ieee assp magazine, 3(1):4-16, 1986.
[25] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. 2018.
[26] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. arXiv preprint arXiv: 10683, 2019.
[27] Anna Rogers, Olga Kovaleva, and Anna Rumshisky. A primer in bertology: What we know about how bert works. Transactions of the Association for Computational Linguistics, 8: 842 866,66666660 2020.
[28] Nikunj Saunshi, Sadhika Malladi, and Sanjeev Arora. A mathematical exploration of why language models help solve downstream tasks. arXiv preprint NXXi:20010003644 2020.
[29] Timo Schick and Hinrich Schüitze. Exploiting cloze questions for few shot text classification and natural language inference. arXiv preprint arXiv:2001.07677 2020.
[30] Timo Schick and Hinrich Schütze. It's not just size that matters: Small language models are also few-shot learners. arXiv preprint wxXiv22009.07//8 2020.
[31] Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. Auto- prompt: Eliciting knowledge from language models with automatically generated prompts. arXiv preprini arXiv:2010. / 15980, 2020.
[32] Koustuv Sinha, Robin Jia, Dieuwke Hupkes, Joelle Pineau, Adina Williams, and Douwe Kiela. Masked language modeling and the distributional hypothesis: Order word matters pre-training for little. arXiv preprint arXiv:2104. 100.006444 2021.
[33] Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. arXiv preprint arXiv: 1503.0003308800 00095.. 2015.
[34] Ian Tenney, Dipanjan Das, and Ellie Pavlick. Bert rediscovers the classical nlp pipeline, arXiv preprint 17Xiv:1905.059550 2019.
12

---

[35] Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang. Adam Poliak, R Thomas McCoy, Najoung Kim, Benjamin Van Durme, Samuel R Bowman, Dipanjan Das, al. What do you learn from context? probing for sentence structure in contextualized word representations. arXiv preprint (90506390 2019.
[36] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv:2003. 0.22244 2020.
[37] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pages 1179-1206. PMLR,
2021.
[38] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data, 2020. URL htR.itttps///oeeeevvvv....e http://wwwwww//w/mm//mm
rC8sJ416kail
[39] Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks. arXiv preprint arXiv:1410.3916, 2014.
[40] Tianyi Zhang and Tatsunori Hashimoto. On the inductive bias of masked language modeling: From statistical to syntactic dependencies. arXiv preprint arXiv:2104.05694 2021.
[41] Zexuan Zhong, Dan Friedman, and Danqi Chen. Factual probing is [mask]: Learning vs.
learning to recall, arXiv preprint urXiv:2104.0522 2021.
13


Reviews:
[{"review_id": "o48-9-222K", "reviewer": "Reviewer_9BBf", "summary": "The paper studies the question why head and prompt tuning work for pre-trained LM. Analyzing complicated neural networks is a daunting task. The paper offers an analysis framework based on the Hidden Markov Model (HMM) and memory augmented HMM. Under this framework, the paper makes a connection with masked LM (BERT) that at time step i, the output of BERT(`[mask]_i`) represents the marginal P(X_i) of the HMM. The framework further allows for analysis of a binary classification task using head tuning or prompt tuning via the posterior distribution of a HMM. To this end, the paper runs a simulation study with data generated from HMM and memory augmented HMM. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- While pretrained models have been used intensively in NLP, much of the analysis on pretrained models is often carried out without considering down-stream tasks. This paper provides one of the first analyses on why pretrained LM does well in fine-tuning and prompt tuning for downstream tasks via a lens of generative models (HMM). While it poses some simplified assumptions (i.e., data generated from HMM), I think it is a valuable first step in this direction.\n\n- The paper studies both head tuning and prompt tuning for both vanilla HMM and a more complex one, namely memory augmented HMM. Under each model, it shows that the downstream label can be recovered (i.e., predicted) using a linear layer on the conditional probability vector of the head.  While the analysis relied on some strict assumptions ( |H| << |V|), I think the paper presented quite a thorough analysis within its scope.\n\n- Given that the paper focuses on MLM, which currently dominates the field of NLP, I think the simulation could be a bit more realistic. For example, one can train a large neural HMM [1] to generate language data. A MLM can be trained to verify if it can predict the marginal p(x_i) at position i.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "FuVglL8sFGI", "reviewer": "Reviewer_Dxbb", "summary": "This paper proposes an analysis framework to link the pre-training and downstream tasks. In this framework, the downstream task needs to predict the properties of the posterior distribution over latent variables in an underlying generative model. And When the generative model is a standard HMM, the downstream recovery is possible with a simple classification head under strong non-degeneracy assumptions. It further shows that changing the generative model to a memory-augmented HMM or using prompt tuning can relax the non-degeneracy conditions.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThis paper provides a theoretical analysis towards the relationship between the pre-training and downstream tasks. It proves that under strong non-degeneracy conditions on token emission probabilities, a linear layer can recover the labels in the downstream task. Also, it further proves recovery guarantees with relaxed non-degeneracy assumptions by using continuous prompt tuning, which explains the effectiveness of prompt tuning.\n\nWeaknesses:\nThe data used in the experimental part are all synthetic and the pre-trained model is also trained based on synthetic data. How well can this theoretical analysis be fitted into the real data? How can the application side benefits from this theoretical analysis?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "   ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "6EvI7UxC_kp", "reviewer": "Reviewer_xxSu", "summary": "This work puts forward a theoretical analysis of pre-trained language models and head and prompt tuning on downstream tasks. In particular it studies the assumptions on the distribution of language and downstream tasks under which the downstream label can be recovered from a pretrained LM by using head or prompt tuning, by considering a generative model of language that can be represented as a HMM. The key components of the analysis include:\n1. The data distribution is generated from a HMM (or a memory augmented HMM).\n2. The initial state of the HMM, $H_0$, contains all the information necessary to recover the downstream label for the sequence.\n\nUnder this setup, for head tuning, the downstream labels are recoverable under the condition that the token emission probability matrix $W$ has linearly independent columns (implying that the dimensionality of the HMM hidden states is smaller than the vocabulary size of the data generating distribution). On the other hand, prompt tuning requires only a relaxed version of this condition, only the columns corresponding to the support of the downstream task need to be independent, eliminating the condition on the hidden state dimensionality.\n\nUnder memory augmented HMMs, for downstream tasks that can be represented as a linear function of the memory (with a fixed number of cells, $N$), the non-degeneracy condition can be relaxed even for head tuning. For prompt tuning, the independence assumption can be further relaxed to hold only for the set of memory cells that the downstream task depends on.\n\nThe authors further perform simulation experiments to validate the findings on different settings of the data generating distribution. Simulation results agree with the findings:\n1. Prompt tuning outperforms head tuning in the setting where hidden state size is significantly larger than the token vocabulary size.\n2. When the data is generated using memory-augmented HMMs, and the downstream task information can be recovered entirely from the memory, even head tuning gets close to perfect performance for all hidden state sizes.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. Novel approach to analyze the effectiveness of pre-trained models on downstream tasks by modeling the generative distribution of language with a HMM.\n2. Theoretically validates why the ongoing work on prompt tuning might be empirically more successful than head tuning.\n\nLimitations:\n1. The significance of the degeneracy conditions on the data-generating distribution and downstream tasks is not clearly discussed at points. Adding a short discussion on their practical implications could go a long way towards improving the impact of the work.\n\nOther minor questions / comments:\n1. Are there any significant differences in the distributions that can be modeled by a memory-augmented HMM as against a HMM, or is it fair to say that this is more of a limitation on the types of downstream tasks that can be recovered (those that can be expressed as a function of only the memory in the case of memory-augmented HMMs)?\n2. Line 254: grasp -> grass", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "5ijrR31h0M", "reviewer": "Reviewer_33Yr", "summary": "[UPDATE: Thanks to the authors for engaging with the comments in the review.  I hope to see them fully addressed in the revision and look forward to seeing the next version of the paper!]\n\nThe paper investigates how pretrained representations might be expected to help prediction on a downstream task.\n\nIn some sense, they should \"obviously\" help: the downstream predictor can learn to exploit any mutual information between its target output and the pretrained representations.  That's the standard motivation for multitask learning.\n\nHowever, the paper exhibits specific settings in which the target output can be *exactly* predicted from the pretrained representations, using only a *simple* probe such as a linear classifier.  \n\nThe paper is primarily theoretical, although a few experiments are included by way of illustration.  It is not clear what the experiments are intended to verify.\n\nTo make the analysis possible, the pretrained representations in the paper are not underlying representations such as word embeddings.  Rather, they are identifiable given the pretraining data, which makes it clear what \"successful pretraining\" means.  For example, the representation of word x_i in a sentence is the conditional distribution of x_i given all other words in the sentence, as predicted by a pretrained cloze language model.  The analysis assumes (though the experiments do not check) that the predicted conditional distribution actually matches the true conditional distribution.  This should be the case in the limit of infinite training data, provided that the cloze language model has adequate capacity and can be trained to a global optimum of log-loss.\n\nIt is shown that if the vocabulary is large enough, or under other assumptions, then this representation of x_1 is enough to recover the posterior distributions over h_1 and h_0, which are assumed to be sufficient for the downstream task.\n\nCaveat: In the analysis, the observed sentences are assumed to be generated by a latent-variable model.  One would then expect the downstream task target output to be predictable from the actual latent variables.  However, the paper assumes more strongly that the target is a function of the *posterior distribution* of the latent variables given the observed sentences.  In other words, the goal of the downstream task is not to recover what the speaker *actually* meant, but only to recover what a hearer who knows the true generating distribution *thinks* it meant (given only the sentence and no other context).\n\nTwo structures are considered for the latent-variable model and its relationship to the downstream task.  For the more complex version, the predictor is also more complex, requiring argmax attention over all positions i.\n\nIn both cases, the paper considers allowing the predictor to prepend an arbitrary word embedding x_1 to the input.  This soft prompt can serve to shift the posterior predictions of x_i so as to be more informative for the downstream task.  \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I appreciate the style of work, as it goes beyond the usual \"close your eyes and hope for the best\" approach to neural networks.  It thinks carefully about what's going on with particular architectures.\n\nIt may be that the paper is answering a question that no one has asked.  As I noted in the summary, it seems obvious that pretrained features should help; in fact, it's known that even random features help!\n\nHowever, I do think that this paper has some helpful insights.  Primarily about what can be extracted with a linear classifier for a downstream task, and why learned prompts and attention might also be useful.  The artificial setup is well chosen to make the pedagogical point.\n\nThe paper is precisely written, but was a slow read.  Although I'm very familiar in principle with all these topics, it was sometimes hard to connect the presentation to my usual concerns.  Since the primary goal of the paper is to aid understanding, I fear that the difficulty in skimming it will limit its impact.\n\nI'm concerned that the graphs in the experiments may be comparing apples and oranges.  Are the points on each curve related at all, or is each point representing a single random HMM (with the error region showing different datasets generated from that HMM)?  If the 10-state HMM has nothing to do with the 15-state HMM, they probably shouldn't be on the same graph as if they're being compared -- the particular HMMs you chose may be unrepresentative.  You want to show mean and variance over many 10-state HMMs.  Similarly, is the right graph comparing some random memory HMM with some random vanilla HMM?  Again, that's just anecdotal, not systematic.  Also I'm not sure it's an interesting comparison since the tasks are different; I would have expected you to fix the setup to a memory HMM with its corresponding downstream task, and see what benefit was given by the attention architecture vs. the look-at-X_1 architecture from section 3.\n\n---------------------------\n\nSUGGESTIONS\n\nTo increase citations, I suggest including more high-level discussion of what is and isn't being shown.  I also suggest drawing more careful connections between the artificial settings in this paper and familiar real-world pretraining settings.  This hand-holding should probably be at the level of the comments I wrote in the paper summary.\n\nThe hardest thing to get my head around was the fact that you are (unusually) looking for exact recovery.  Just before section 3.1, I kept wondering why degeneracy was a problem.  After all, Bayes' Theorem still applies: it should *help* to be able to predict (in effect) X_0 even if X_0 doesn't have enough information to recover H_0 perfectly.  But for some reason, you want to be able to perfectly recover H_0 from *only* the prediction of X_0, which requires that prediction to preserve all of the relevant information from X_1, ..., X_n.\n\nYou are particularly interested in using a linear classifier for the downstream task.  Why this restriction?  You could say that the downstream task often has relatively little training data.  But that is a motivation for a low-parameter classifier, not a linear one.  In fact, you should admit that your classifier parameter \\mu is high-dimensional if the vocabulary is large.\n\nYou rely heavily on the linearity of HMM inference.  You might want to defend why HMMs are plausible distributions for natural language.  The argument is presumably that with a large enough state space, it is possible to summarize an entire string prefix into a state.  A couple of papers relevant to this are https://arxiv.org/abs/2011.04640 and https://arxiv.org/pdf/1804.10747.pdf.  The paragraph at line 255 is also helpful.\n\nCan you say anything about factorial HMMs?  The memory HMMs are only a simple case of factorial HMMs (2 factors, one being constant).\n\nA little more hand-holding around proposition 3.4 would be helpful.  Your point is that predicting X_0 from X_{1:T} helps you predict H0 from X_{1:T}.  The reason for the complicated setup here is that X_0 is never actually observed (in fact you left it out of the model), but there are some stationarity invariants in the data -- and thus hopefully in the pretrained model -- that allow you to predict it anyway.\n\nWhen using a prompt u as X_1, I think you want observing u to change the true posterior and hence the predicted posterior over X_2 (mediated by latent variables H_1 and H_2).  It would probably be helpful to say that explicitly.\n\nYour construction with prompts assumes that the pretrained word embeddings are actually rows of the true emission matrix.  But how does that fit with the BERT pretraining that you do in your experiments?  Also, even if BERT pretraining works on real sentences, will it continue to get the \"correct\" cloze predictions when you prepend an embedding corresponding to a word never seen in training data?\n\nI'm not clear on what the experiments are showing.  What do they add that was not present in the theoretical analysis?  I might have expected you to verify that BERT is in fact computing the correct word posteriors, and that the hidden state posteriors can be reconstructed from the word posteriors, so that you can predict downstream results for *any* mu, not just a particular random mu.\n\nThe assumption 3.5 is quite strong: it basically ensures that reconstructing one\n   word is enough for the downstream task.  Maybe ok, but should be discussed more in\n   the context of actual tasks, e.g., trying to get out some info and not other info.  (This assumption is relaxed in section 4.)\n\nIt might also be helpful to point out more explicitly that the cloze language model doesn't necessarily have to have the same structure as the true generating distribution.  Indeed in the experiments, it doesn't.  In the experiments, the data are generated by an HMM, but the cloze language model adopts a BERT architecture rather than doing something like spectral learning of the HMM.  It is implicitly assumed that BERT will be able to match the true posterior of the HMM, but this is not evaluated.\n\nRegarding the caveat in my summary above: At line 138, it's a bit odd to think that the ground truth should be a linear function of the *posterior distribution* over H_0.  Ordinarily we would think that it would be determined by the *true value* of H_0, or at least, that it has high mutual information with H_0. However, if \\mu_h = p(Answer=1 | H_0=h_0) - 0.5, then (3.1) is a good decision rule because it says to return 1 iff p(Answer=1 | X=x) >= 0.5, or equivalently, to return argmax_i p(Answer=i | X=x).  So perhaps you can argue that the ground truth is being labeled by a human who is using this decision rule to make their best guess given X=x, without privileged access to H_0.\n\n---------------------------\n\nMINOR REMARKS\n\nThe name \"head tuning\" seems misleading to me as it makes me think of attention heads in a Transformer, which is not the intention here.\n\nOn soft prompts, other work has recently appeared, including https://arxiv.org/abs/2104.06599, https://arxiv.org/pdf/2104.08691.pdf, https://arxiv.org/abs/2012.15723.\n\nIn section 4.1, the use of argmax with the attention head is nonstandard (section 4.1), although it's equivalent in the limit of scaling up key magnitude.  Should point this out.\nThe computation of the value functions is also nonstandard.\n\nAt line 114, I think you want to say more specifically that G(x) = \\bar{G}(u,e(x)).\nYou say something like that later at 178.\n\nAt line 120, probably clearer to define P[U|V] first and then say that P[U|V=v] and P[U=u|V] select columns and rows from that matrix.\n\nLine 188: shouldn't u be \\tilde{z} here?\n\nAt line 283, by \"article,\" do you mean words like \"the\" and \"every\"?\nIf so, I suggest using the word \"determiner,\" which is more common in linguistics and NLP; \nat first I thought you were talking about a news article, or perhaps just a\nphysical object (as in \"article of clothing\").\n\nIn Fig 3 (left), the \"prompt tuning\" line tunes the head AND the prompt, right?  Clear in the text but the figure legend and caption seem to say otherwise.\n\nline 358: \"ground-truth linear weight\": do you mean that it's randomly generated just like the params at line 350?  If so, please use similar language in both places.  (What distributions are used?  I don't think you say, even in the appendices.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a theoretical analysis of pretrained language models, linking the pretraining and downstream tasks with an underlying latent variable generative model of text. It analyzes head and prompt tuning in this setting, using a memory augmented HMM as the generative model in the analysis. The main findings are that under certain non-degeneracy conditions heads and prompt tuning can solve the downstream task with certain recovery guarantees. The theoretical findings are illustrated with experiments on synthetic data.

All reviewers agree that the theoretical analysis is novel and insightful, and a good first step in understanding the effectiveness of fine-tuning and prompt tuning. They pointed out as weaknesses lack of discussion on the practical implications, which the authors promised to address in the final version. While the use of synthetic data and lack of experimentation on more realistic tasks is a limitation, I believe the theoretical findings are useful and may foster future research considering more realistic scenarios.  I urge the authors to take into account the detailed comments made by the reviewers when preparing the final version.
Decision: Accept (Spotlight)