Learning Extrapolative Sequence Transformations from Markov Chains
Authors: Sophia Hager
Aleem Khan
Andrew Wang
Nicholas Andrews
Venue: ICML 2025 poster (2025)
Keywords: Large language model
Markov chain Monte Carlo
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: We can distill extrapolative sequence transformations from Markov chains.

Abstract: Most successful applications of deep learning involve similar training and test conditions. However, tasks such as biological sequence design involve searching for sequences that improve desirable properties beyond previously known values, which requires novel hypotheses that \emph{extrapolate} beyond training data. In these settings, extrapolation may be achieved by using random search methods such as Markov chain Monte Carlo (MCMC), which, given an initial state, sample local transformations to approximate a target density that rewards states with the desired properties. However, even with a well-designed proposal, MCMC may struggle to explore large structured state spaces efficiently. Rather than relying on stochastic search, it would be desirable to have a model that greedily optimizes the properties of interest, successfully extrapolating in as few steps as possible. We propose to learn such a model from the Markov chains resulting from MCMC search. Specifically, our approach uses selected states from Markov chains as a source of training data for an autoregressive model, which is then able to efficiently generate novel sequences that extrapolate along the sequence-level properties of interest. The proposed approach is validated on three problems: protein sequence design, text sentiment control, and text anonymization. We find that the autoregressive model can extrapolate as well or better than MCMC, but with the additional benefits of scalability and significantly higher sample efficiency.

Learning Extrapolative Sequence Transformations from Markov Chains
Sophia Hager' Aleem Khan
Andrew Wang'
Nicholas Andrews
Abstract
Example Task: review with rating 1.5
Convert review with rating to a
Most successful applications of deep learning in- volve similar training and test conditions. How- ever, tasks such as biological sequence design involve searching for sequences that improve de- sirable properties beyond previously known val- ues, which requires novel hypotheses that extrap- olate beyond training data. In these settings, ex- trapolation may be achieved by using random search methods such as Markov chain Monte Carlo (MCMC), which, given an initial state, sam- ple local transformations to approximate a target density that rewards states with the desired prop- erties. However, even with a well-des pro- posal, MCMC may struggle to explore large struc- tured state spaces efficiently. Rather than relying stochastic search, it would be desirable to have model that greedily optimizes the properties of interest, successfully extrapolating in as few steps as possible. We propose to learn such a model from the Markov chains resulting from MCMC search. Specifically, our approach uses selected states from Markov chains as source of training data for autoregressive model, which is then able to efficiently generate novel sequences that extrapolate along the sequence-level properties of interest. The proposed approach is validated on three problems: protein sequence design, text sentiment control, and text anonymization. We find that the autoregressive model can extrapolate well or better than MCMC, but with the ad- ditional benefits of scalability and significantly higher sample efficiency.
(State) A
Ratings unseen during training Rotings observed during training
Review Rating
B
c
2
Ratings
during training
Exploration
Achievable
Document State
State A: Service was okay, at best. Mouldn't go there again.
State B: Service was nkeyybblah at bestu-l, wouldn't go there
liskpathetic, best, xouldn't go there again.
State N: Service was pathetic, at best, wouldn't 't go there again!!!
Figure f. The sentiment extrapolation task ($3.2) requires generat- ing reviews with ratings beyond the range observed at training time. The search process is illustrated using toy ID representation the fcatures (x-axis) and rating (y-axis). Monte Carlo exploration can produce reviews that extrapolate, but many steps are required. However, once good state sequences have been discovered, we can sub-sample the transitions that decrease the rating (A + C - N) and use them to learn extrapolative model. The reviews shown to the right for states B, C, and N are actual reviews generated by our method, while A genuine review from the validation data.
For example, automating generation of novel hypotheses is central to mathematical discovery, biological sequence design, molecular optimization, and the creation of new materials TRomera-Paredes, et al., 2024; Fu et al., 2023; Jain et al., 2022: Trabucco et al., 2022; Gao et al., 2022). Extrap- olation also necessary in many creative applications, such writing assistants for creative writing (Swanson al., 2021; Gómez-Rodríguez & Williams, 2023). It is natural to wonder if extrapolation is an emergent ability of large-scale generative models (Schaeffer et al., 2024). However, prior work has found that state-of-the-at foundation models can struggle on tasks requiring extrapolation (Dziri et al., 2023;
1. Introduction
In creative tasks such scientific discovery, key require- ment is the ability to extrapolate beyond existing knowledge.
'epartment of Computer Science, Johns Hopkins University. Correspondence to: Sophia Hager <shager2@@hh.ddu> Nicholas Andrews <noa@ jhu.edu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning Extrapolative Sequence Transformations from Markov Chains
Chakrabarty et al., 2024).
($2), by selecting transitions from the Markov chains, we implicitly learn non-autoregressive model that iteratively transforms an initial sequence (loken-by-token) to improve the score beyond the training range. By further incorpo- rating a sequence-level score at each step of generation- similar to reward-to-go in sequence modeling approaches to reinforcement learning (Janner et al., 2021>-the model can learn to incorporate this feedback.
Instead of increasing the number of model parameters or amount of training data, generative model can simply pro- duce samples repeatedly to find the optimal solution. When guided by a verifier, this process can improve model per- formance substantially (Snell et al., 2025). Notably, Lu et al. (2025) compare reasoning and inference strategies for foundation models, finding that the only strategy that suc- cessfully increases sample diversity is Monte Carlo search. However, while such approaches may offer good results for extrapolation, sampling at inference-time may be too slow in practice.
Summary of contributions We propose framework to extrapolate beyond a given training dataset given an arbitrary scoring function. Our approach leverages existing compo- nents, namely pre-trained language models trained using de- noising objectives, to explore the space of sequence-to- sequence transformations and their impact on the target objective, a process formalized as MCMC. We consider a variety of strategies to select training data from the result- ing Markov chains to fine-tune a model to generate novel sequences. In particular, we propose a multi-step generative process in which, starting from an initial state, the proper- ties of interest are optimized in multiple rounds, similar to non-autoregressive generation. We evaluate our model on three tasks: protein engineering, sentiment style transfer, and anonymization' In some cases, we find that our model, qo, can achieve competitive results with MCMC and other baselines using a significantly smaller number of steps ($3), In other cases, we find that the fine-tuned model extrapolates beyond the best value achieved during sampling.
How can we efficiently extrapolate beyond the training data, taking advantage of performance gains brought by scaling test-time compute without paying the cost at inference? We build on Iterative Controllable Extrapolation (ICE), a recent approach which leverages the de-noising ability of masked language models (MLMs) to extrapolate (Padmakumar et al., 2023). ICE uses random masking and infilling to generate sequence transformations that improve the target objective as evaluated by a trained scorer, and then supplies these transformations as training data for an autoregressive model. The assumption is that at inference time, composing several transformations with this model may lead to effective ex- trapolation. While this method was found to be successful in extrapolating beyond the training region for some tasks, its success is critically dependent on the choice of a number of sensitive
including a threshold on the relative improvement from different transformations and fixed number of iterative decoding steps.
2. Proposed Method
In this paper, we seek to better utilize the implicit knowl- edge of generative models trained using in-filling objec- tives (Bavarian et al., 2022; Tay et al., 2023) for extrapola- tive generation. Rather than employ a heuristic search, we (MH) to generate correlated sam- ples where an MLM is used as a proposal distribution. While MCMC provides theoretical guarantees, it is inefficient in high-dimensional state spaces such as natural language.
The objective of extrapolative generation is to produce sam- ples that optimize properties of interest, such as sentiment in Figure 1, beyond previously observed values. Our ap- proach proceeds in two phases. In the first phase, we use MCMC to sample from a surrogate density that assigns higher probability to samples likely to contain the desired properties. Unlike typical applications of MCMC, our ob- jective is not to approximate the density itself, but to derive training data from the resulting Markov chains. The training data is used to fit a model that iteratively improves the prop- erty of interest, given an initial state. Note that the learned model is not an inference network amortizing the sampling process (Li et al., 2017); the goal is efficient extrapolation.
use Cettropolis-Hastinge
To address this inefficiency, we prune the set of states drawn by the sampler and finetune language models on these pruned states to autoregressively predict the transition from one state the next. Our objective in doing so to generate sequences that achieve scores in the extrapolation range in as few steps as possible. This is illustrated in Fig- ure I for the controlled task of review generation ($3.2). Not all transitions in the Markov chains are equivalently useful as training data, since some transitions may fail to improve the score or result in worse scores. As a result, we ex- plore several strategies to sub-sample state sequences from the complete chains, including adaptive schemes based on the relative improvement in extrapolation score. While the model we fine-tune has autoregressive parametrization
Toy example To illustrate the main idea, we provide a simple example of training an iterative extrapolation model on Markov chains. Consider the space of binary sequences of fixed length L. Given initial sequence 20()) of all zeros, the objective is to search for sequences that maximize a
'Code made available https://github..cm MCM--MMMC-eet SoMMC-exxrrpolaation
s
2

---

Learning Extrapolative Sequence Transformations from Markov Chains
scalar score function sax) = exp Σx' r3 where
generate ratings in the extrapolation range consisting of ratings that are highly negative (1-star) highly positive (5-star). At test time, we generate x' ~ qo and evaluate the true performance of the last sequence, oracle(x') snat)
izs/L L LL
i> L/2
$/
otherwise
which is maximized by placing O's in the first 2 positions followed by I's in the last L/2 positions (for even L). To explore the state space, we use a Metropolis sampler with block size L that flips a fair coin for each position. We consider the space of sequences of length L = 16, which has maximum reward of 314.2. Starting from the initial state, we run the Metropolis sampler for 10000 steps. The sampler had an acceptance rate of 43.7% and the highest achieved reward was 244.7. Next, after removing dupli- cate states, we select all state-to-state transitions that result in improved reward (approximately 2000 transitions). This data is used to train peeueence-t-sequeeee model qo parametrized as a two-layer multi-layer perceptron (MLP) 2
2.1. Generating Markov chains
Surrogate model As a target for MCMC, we use a surro- gate model In p(a)) = s(x) In Z, where s(x; is a sequence- level score that is efficient to evaluate and Z is the partition function. This defines an energy-based model (EBM), and multiple scores may be combined using a product-offexpprts In p(z) = a1 (z) + az)2(2) + .... In Z. weighted with scalar hyperparameter a (Mireshghallah et al., 2022). For example, we can have one score measuring the property of interest, while another measures the prior likelihood of the sequence. Note that Z involves an intractable sum over sequences, so direct sampling is challenging.
Finally, qe was iteratively applied starting at zo five times to produce a sequences of states 2011, (2) x0(5) where 2x(1) = qo (zx!(-1) and predictions from qo are obtained deterministically by decoding all I. positions Our model achieved the following sequence of rewards: 1, 3.3, 15.6, 314.2, 314.2. Thus, in fewer than five steps, the trained model successfully extrapolates beyond the 244.7 state achieved by the MCMC search and achieves the opti- mum value.
Sampler While MCMC is the standard way draw sam- ples from an EBM, the algorithm suffers from the curse of dimensionality. The sample efficiency of MCMC may be improved with a careful choice of proposal distribu- tion, often requiring careful woblem--specifi design. Fortu- nately, language models trained with mask-infilling objec- tives have been shown to serve as effective proposal distribu- tions (Goyal et al., 2021). This allows to obtain effective proposals using pre-trained language models, which exist for natural language as well as other sequence data such as protein sequences. Specifically, we use the Metropolis- Hastings (MH) algorithm which uses a proposal distribution q(a' | x)) to draw candidate states x' given the current state x. These proposals are either accepted, in which case x' is taken as the new state, or rejected, in which case x' x. according to the standard MH acceptance criterion. To im- plement q. we mask random subset of the current state x, and then infill the masked sequence (Devlin et al., 2019; Lewis et al., 2020; Raffel et al., 2020).
parallel.
Oracle scoring To assess the quality of any given sample, we assume access to an oracle function oracle(z) which can assign scalar score to any sample x. In the toy example above, the score s(x) is equivalent to an oracle scorer which can calculate the true reward. However, in general, there may not be an efficient way to score sequences. For example, assessing a novel sequence may require conducting physical experiments or running expensive simulations, as in the pro- tein task described in $3.1). Given candidate sequence x,, we assume that oracle (x:) E y may be consulted to assess x,, but that it is expensive to consult frequently. We instead as- sume access to a guide s(x) that provides a computationally tractable estimate s(x) of oracle(x). For example, s(x) may be a neural network trained to predict properties of x based on database of previous experiments with hypothesized sequences x and measured outcomes or))le(x))
2.2. Training the extrapolative model
Parametrization We imbue the extrapolative model with specific inductive biases to encourage extrapolation beyond the training data. Specifically, we allow generation to pro- ceed via multiple intermediate states æ1, 22, .N- The intuition for this strategy, borne out in our experiments ($3), is that for extrapolation, it is effective to learn conditional transformation that makes incremental changes to state. Unlike transitions in the Markov chains, the model may avail of information from the complete history of previous states I1 Ø2, ......., as well as associated real or predicted scores+ s (x1) s(x2) sTnn-1) when producing the next state
This guide will only be robust within the range of training values, meaning its ability to guide extrapolation may be limited. For instance, in the sentiment task, the guide is only robust in the training range consisting of ratings from 2 to stars. Despite that, in that task our objective is to
"e use hidden dimensions 16 for the embedding matrix and two 128 dimensional layers with rclu activations. The MLP is fit to the selected transitions using multi-label sigmoid cross- entropy loss for 20 epochs using Adam optimizer with 12 learning rate.
"See Wang & Cho (2019) for further context on this approach and Hennigen & Kim (2023) for some analysis and extensions. *We discuss scoring methods further in Appendix
3

---

Learning Extrapolative Sequence Transformations from Markov Chains
Tn- By conditioning on scores, the model has the ability to incorporate these into planning, not unlike the sequence model RL formulations proposed by Janner et al. (2021); Chen et al. (2024).
Uniform thinning If the sampling chain tends mono- tonically improve the energy, the simple strategy of sub- sampling the states at regular intervals can be expected to result in a state sequence with incremental progress towards a local optimum. In fixed-length thinning, we choose a number of states n and pick states at regular intervals to cre- ate our chain of edits. In variablc-length thinning, rather than choosing the number of states n independently of the sequence length i, we choose a thinning factor l and calcu- late n i//k. This dynamically allocates each edit chain a number of states based on the entire edit sequence length.
Autoregressive refinement We create training episodes (21, 81), quences from the complete Markov chains". We discuss several strategies for this in $2.3. The training episodes are encoded as a sequence of tokens:
(IN, sN) by sub-sampling state se-
4o <sequ> 21 <segl> $1 x2 <seq2> ..... Zn 8n <stop>
Above, <seqi> and <stop> are distinguished symbols en- coded either as special vocabulary terms or as strings in pre-trained model, are scalar scores, and I; are token sequences of possibly variable length. Then do is trained using teacher forcing to generate each token of each inter- mediate state 24 (for: > 0) conditioned on all previous states To, Ii,... -;-1- 1- As previously mentioned, the con- crete advantage to formulating inference in this way is that revisions can condition on previously generated sequences and energy scores.
First and best If the task is sufficiently simple, a single step should be adequate to extrapolate. By taking the initial and lowest energy states of the Markov chain, we create single-step training examples."
Changes in energy Ideally, we would like the states cho- sen for training episodes to be governed by properties of states in the chain, such as the relative improvements in energy from state to state. A simple way to incorporate this idea into the selection of training episodes is to identify state transitions that most improve the energy. In fixed-length A energy, we cache the energy for each state while running MCMC, then select the n states that most improve energy training episode.
Inference Since qo has simple autoregressive structure, generating from the model can be done in a variety of ways, including forward sampling and beam search. We note that in principle constrained decoding techniques could be used to enforce adherence to the structure above, but we did not find this necessary in practice. If any intermediate states added to the sequence (i.e. first and best state), after generating each intermediate state Ji the sequence is either scored using s(z;) and the result deterministically appended to the sequence, or go learns to predict the sequence score. 6 When <stop> is generated from the model, the final state nn is taken to be the sample.
from the previous step to construct Rather than selecting states, variable-length A energy selects any states which improve energy by a particular threshold, e.g. 10%..
more than the
3. Experiments
To address whether go has the capacity for sample-efficient extrapolation, we apply our method to two tasks from Pad- makumar et al. (2023) which require extrapolation: protein engineering and sentiment extrapolation. To demonstrate that go retains the capacity to "interpolate" (i.e., generalize well in a non-extrapolative task), we evaluate on a complex task solely requiring interpolation, namely text anonymiza- tion. In all experiments, to demonstrate method efficiency, we show the number of "iterations" each method takes-we consider "iterations" to loosely correspond to the computa- tional work of passing the sequence through the inference model once. Despite our method only requiring one in- ference step, we consider the number of "iterations" to be equivalent to the number of revised states in the training episode, in order scale by number of tokens. In variable- length methods, we report the average number of iterations.
2.3. Creating training episodes
Creating training episodes consisting of the entire Markov chain, which could include hundreds of states, is undesir- able. Ideally, qo is computationally efficient at inference time, generating a small number of states before producing the <stop> symbol. As result, we require relatively short training episodes. Note also that the sampling method might explore high-energy regions of the state space, and it may be sub-optimal to include such exploration in the training episodes; therefore, we idcally want to select state transi- tions from the complete sample that result in decreased energy. We examine several strategies for selecting states.
'In Appendix C we discuss the impact of the number of subsam- pled states, and in Appendix D we discuss the impact of Markov chain length.
3.1. Protein engineering
We replicate the ACE2 stability task from Padmakumar et al. (2023). The goal is to generate mutants of the human
"Another possibility is to consult the oracle at intermediate states of generation, although we do not directly evaluate this version in our experiments, as our setup assumes the necessity of minimizing oracle calls.
"This can be considered special case of uniform thinning where the training episade length is two.
4

---

Learning Extrapolative Sequence Transformations from Markov Chains
angiotensin--coneriing enzyme 2 (ACE2) with higher sta- bility than the wildtype, measured with lower free energy compared to the wildtype (ddG), Lower ddG corresponds to more stable mutants. The protein is represented as a se- quence of 83 amino acids, from a vocabulary of 20 amino acids in total. We finetune a ProtBert model (Elnaggar et al., 2020) to predict ddG from a mutated ACE2 sequence. We use the ACE2 dataset from Chan et al. (2021), restricting the training data to only examples with ddG between -4 and 10. The objective is to generalize to sequences with ddG beyond the training range (i.e. below -4). We describe our experimental procedure in detail in $B.1.
Prior work considers simple version of this task where success is measured only in proportion of sequences in the extrapolation region. We additionally measure the change in fluency after editing, to prevent our models from greedily optimizing only a single metric at the expense of fluency. Details of our procedure can be found in $B.2.
Baselines We report results from Padmakumar et al. (2023), namely the ICE and ICE with scorer methods as well Genhance (Chan et al., 2021). ICE with scorer was previously described in $3.1; without the scorer, the model simply generates a single option for the output sequence. Fi- nally, we report results using FUDGE (Yang & Klein, 2021), an autoregressive classifier-guides method not specifically designed for extrapolation. We describe our implementation of FUDGE in BB.2.
Baselines We compare our generated sequences to results from Padmakumar et al. (2023)"; specifically, we consider their reported scores for masking and infilling, iteratively masking and infilling with ranked outputs (Iterative sam- pling), Genhance by Chan et al. (2021) and Iterative Con- trollable Exurapolation (ICE) by Padmakumar al. (2023). In both cases, we report the better-performing variant with scorer, where at each step the model generates multiple op- tions and chooses the best using the training-time scorer. We also report the scorer-free variant of ICE, which generates a single output at each step, similar to qo-
To evaluate sentiment, we use the oracle scorer as described in (Padmakumar et al., 2023). When editing in the positive direction, we consider a 4-star review or above to be in the training region, and a 5-star review to be the extrapolation region; when editing in the negative direction, we consider 2-star review below to be in the training region, and 1-star review to be in the extrapolation region. We also introduce fluency metric, the median percentage change in perplexity as measured by GPT-2 large (Radford et al., 2019). Editing the sequence should have little impact on the fluency; if a model demonstrates success in extrap- olating only when it significantly reduces the fluency, unlikely be useful in real-world applications.
Metrics
Metries We evaluate the stability of the generated proteins using FoldX (Schymkowitz et al., 2005), which calculates the ddG for each protein. We report the proportion of gen- erated mutants which fall below certain thresholds: -1 and -2.5, which are within the training region, and -5, -6, and -7, which are within the extrapolation region.
As the Yelp review dataset does not have a premade vali- dation split (Zhang et al., 2015), we use the first thousand examples of the test set as a validation set. Padmakumar et al. (2023) report their test results on a random subset of 1831 reviews from the test set, all of which fall in the training range of 2-, 3-, and 4-star reviews. For MCMC and qo, we create three 2000-sentence subsets of the test set and report the average of each of these three runs in our results, finding that there is little variation regardless of the test set. We run FUDGE on one of these 2000-sentence test sets.
Our results with qo trained on training episodes constructed using fixed-length A energy can be found in Table 1. Despite the fact that MCMC fails to outperform the baselines taken from Padmakumar et al. (2023), we find that in the extrapolation range qe significantly outperforms our baselines and MCMC.
Results
3.2. Sentiment extrapolation
Given training dataset of Yelp reviews (Zhang et al., 2015)
We show our results with qe trained on first/best training episodes in Table 2 alongside results from Pad- makumar al. (2023). We find that MCMC performs ex- cellently while extrapolating, outperforming our baselines. Our trained go outperforms our baselines in extrapolative ca- pacity, and outperforms MCMC in efficiency (as measured by number of iterations) and fluency. Example generations can be found in L..L.
Results
with sentiment ranging from 2-stars to 4-stars, the goal is to learn to generate reviews that extrapolate beyond the training region to the highly negative (1-star) or highly positive (5- star) reviews. Following Padmakumar al. (2023), we fit two regression models, training- time scorer and an oracle scorer used for evaluation. The training-time scorer predicts scalar rating from 1 (2-star) to 3 (4-star) using reviews in that range. The oracle scorer uses all of the training data and predicts the complete range of ratings given input text.
3.3. Anonymization
"In a personal communication, the authors report that their procedure exhibits large variance, and indeed we are unable to re- produce published results using the code released by Padmakumar et al. (2023).
Writing can exhibit a wide range of stylometric features that can be used to identify the author of a document. In cases where anonymity is desired, there is a need to au-
5

---

Learning Extrapolative Sequence Transformations from Markov Chains
Model
-1f
-2.51
-51
-61
-7f
Iterations.
Mask/Infill
0.033
0.007
0.000
0.000
0.000
Iterative sampling
0.998
0.954
0.220
0.079
0.001
10
Genhance w/scorer
0.999
0.978
0.159
0.040
0.009
ICE scorer-free
0.945
0.598
0.062
0.017
0.002
10
ICE w/scorer
0.998
0.974
0.361
0.098
0.019
10
MCMC
0.999
0.995
0.270
0.041
0.005
83
q0
0.972
0.938
0.748
0.616
0.464
3
Table Overall ACE2 stability results. Each cell represents the percentage of generated sentences lower than the threshold. Lower ddG more stable; 11 and -2.5 are in the training range, -5 and below in the extrapolation range. While MCMC does not approach the success baseline, variant of ga. trained on training episodes created using fixed-length A energy to select states, significantly outperforms the baseline.
Model
Trainingt
Extrapolation
A Fluency
Iterations.]
Genhance
0.908
0.387
ICE scorer-free
0.947
0.376
10
ICE w/scorer
0.921
0.610
10
FUDGE
0.613
0.237
-0.212%
MCMC
0.960
0.809
0.746%
496
ge
0.925
0.734
0.132%
Table 2. Comparing our methods to the Padmakumar et al. (2023) results on the extrapolative sentiment task. We report the proportion of sentences in beyond the favorable training range (2 stars fewer for negative sentiment, 4 stars more for positive sentiment) and threshold for the extrapolation range (I star for negative sentiment, 5 stars for positive sentiment). MCMC performs well on those metrics, hut notably
flueney while requiring nearly 500 iterations. We compare this go trained using first/hest training episodes. qo decreases fluency less and requires only a single iteration. We provide 95% confidence intervals over three different test sets.
tomatically remove versonally-identilynnn features. Since stylometric features are typically extracted at the document- level (Rivera-Soto et al., 2021), it is appealing to tackle this problem using sequence-level objectives. Similar to previous tasks, we first extract training episodes from an MCMC driven sampler. We adapt the style transfer method proposed by Khan et al. (2024) generate training episodes making one key change: rather than using specific target style, we parameterize the energy function such that any style different from the initial style is desirable. Given some text x, the system results in a series of states y/, -2,..- ...Yn. these episodes are then used to train our anonymization sys- tem. Details on our adaptation of Khan al. (2024) can be found in Appendix G.
16 posts. Given the first 8 original posts from author's his- tory, we attempt to identify the second set of 8 anonymized posts as a match, and all other author posts as negatives. We use a pre-trained author embedding 9 to encode each set of messages into a vector and use cosine similarities between two candidates a score. we successfully avoid detection, expect the EER to rise. We calculate semantic similar- ity using the publically released all-mpnet -mpnet-base--eeeeee-eeee---eaeee v2 checkpoint within the sentence transformers library to en- code original and anonymized documents. A successful system maintains high semantic similarity.
Results We find that baseline systems do a poor job at maintaining semantic similarity, or in the case of Round Trip MT, do so at the cost of not circumventing author verification. While the MCMC sampler performs well under both of these metrics, it is costly to run, with an average of 4498 iterations to yield an anonymized sample. Our system, with go trained on variable-length A energy, returns anonymized sample with comparatively few in-context iterations.
Baselines We consider four baseline anonymization sys- tems: GPT3.5, GPT4 (OpenAI et al., 2024), DIPPER (Kr- ishna al., 2023), and Round Trip Machine Translation (MT). Implementation details for each system are in 1..1.
Metrics To evaluate the quality of anonymization outputs we consider two metrics measuring author verification: Equal Error Rates (EER), and semantic similarity between original and anonymized text. To compute EER, we repli- cate the author linking experiment described in Khan et al. (2021). Our evaluation set consists of 50 authors, each with LUAR-CRUD
6

---

Learning Extrapolative Sequence Transformations from Markov Chains
Model
EER
SBERT
Iterations.
GPT-3.5
0.216
0.777
GPT-4
0.238
0.698
DIPPER (Krishna et al., 2023)
0.206
0.641
Round Trip MT
0.110
0,921
MCMC
0.393
0.835
4498
0.221
0.839
Table Comparing our methods with anonymization baselines. MCMC achieves improved results over baselines, but takes significantly more iterations than any other method: our best variant of trained using variable-length A energy, achieves reasonable performance on both metrics significantly fewer iterations than MCMC.
Model
-11
-2.5t
-51
-61
-71
Iterations
First/Best
0.978
0.932
0.609
0.418
0.242
Thinning (fixed-length)
0.961
0.915
0.715
0.580
0.422
Thinning (variable-length)
0.972
0.929
0.714
0.570
0.420
4.890
A Energy (fixe-lenggh))
0.972
0.938
0.748
0.616
0.464
A Energy (variable-length)
0.964
0.883
0.424
0.252
0.133
3.631
Table Varying training episode creation for the ACE2 stability task. We find that fixed-length A energy outperforms our other training episode creation strategies when extrapolating.
3.4. Analysis of episode creation strategy
wildtype each time, we investigate whether we can achieve similar performance to go by simply running further steps of MCMC. We run the model for ten epochs and report the results Figure We find that further MCMC does not begin to approach the performance of qo. demonstrating that our model may have generalization benefit that cannot be replicated by further MCMC sampling.
Tables 4, 5 and 6 show the effects of different methods of creating training episodes to train do as described in $2.3. In Table 4, we find that selecting states using A energy (fixed-length) outperforms both naive thinning methods by several points. However, A energy (variable-length) under- performs significantly. This weakness is not found in the results for sentiment (Table 5) anonymization (Table 6), where variable-length A energy performs comparatively to fixed-length A energy. In sentiment, it's clear that A energy methods of selecting training episodes have advantages over thinning in the extrapolation range.This pattern is echoed in our interpolation task, amonymization: A energy methods and thinning methods both achieve similar EER, all data within the training range. However, A energy methods preserve more semantic features of the text compared to uniform thinning, similarly to the fluency results in sen- timent. This may indicate that thinning methods tend to change more elements of the text that are irrelevant to the target score. These results suggest that in cases when the model cannot learn a transformation in a single step our "first/best" variant-choosing states using their change in energy is likely result in the best outcome.
Under -5
Under -6
Under -7
Percentage samples under threshold
70
60
40
30
20
10
Epochs
Figure 2. In the protein engineering task, comparing MCMC per- formance (solid line) over ten epnchs, 830 steps, compared the performance of (dotted line) trained on MCMC data gen- erated on one epoch, 83 steps. We find MCMC does not approach the performance of and does not notably improve after even two epochs.
3.5. Approximating qe through further MCMC exploration
In the of the protein engineering task, find that qo significantly outperforms MCMC in the extrapolation range. As the protein synthesis task involves starting from the
1083 steps, the sequence length

---

Learning Extrapolative Sequence Transformations from Markov Chains
Model
Trainingt
Extrapolation f
Fluency.
Iterations
First/Best
0.925 0:000
0.734
0.132 % #0.15
Thinning (fixed-lenghh)
0.883
0.64220..07
0.466%.20014
Thinning (variable-length)
0.854
0.591 4:0012
0.539%
3.997
A Energy (fixed-length)
0.910
0.692.10.116
0.362%:10.00
A Energy (variable-lengthy
0.881 +00004
0.677 0.006
0.396% +0.02s
5.855
Table Applying various training episode creation strategies to the sentiment task. show that these strategies affect the proportion of sentences in the favorable training range and in the extrapolation range. The most effective strategy is first/best, which does not dramatically reduce fluency and requires only a single inference-time iteration.
Model
EER
SBERT
Iterations
First/Best
0.132
0.923
Thinning (fixed-length)
0.209
0,810
4
Thinning (variable-length)
0,202
0,809
12.75
A Energy (fixed-lenghh)
0.192
0,840
4
A Energy (variable-length)
0.221
0.839
12.75
Table Anonymization results with our proposed episode strategies. A energy strategies tend have higher SBERT scores than thinning strategics, with little to no tradcoff on EER.
4. Related Work
Editing models Incremental edits offer models multiple chances to explore the sequence space, increasing the like- lihood that they find more optimal solutions. These edits may be token-level changes (Reid & Neubig, 2022: Malmi et al., 2019; Kasner & Dušek, 2020; Zhang et al., 2020b), alterations to short subsequences (Schick al., 2023), or even rewrites of the entire sequence (Agrawal & Carpuat, 2022; Shu al., 2024). A challenge for constructing editing models is the need for supervised training data. Many edit- ing models are trained on sequences of edits from Wikipedia pages (Schick et al., 2023; Malmi et al., 2019; Reid & Neu- big, 2022), as it is an easily accessible repository of edited text. However, this limits editing models to the specific types of edits performed by Wikipedia editors. To avoid this limitation, Zhang et al. (2020b) use an MCTS approach that instead guides the edits with a variety of constraints. Our approach has the same advantages and also offers means to drastically speed up inference by learning qo-
Controllable generation Autoregressive decoding is favored strategy in controllable text generation. Prior to the advent of instruction -unedd I.Mss, a discriminator model was often used to guide decoding (Dathathri et al., 2020; Yang & Klein, 2021). The left-to-right nature of decoding, however, means that the discriminator operates with little information early in the sequence, which limits the influence has early in the process. Our approach addresses this shortcoming by following sequence-level text generation objective, providing a notion of control that depends the entire sequence and can therefore incorporate sequence- level scores as feedback in the generative process. Other works perform exploration in continuous latent space, with the goal finding solutions that maximize the desired score. To that end, variational autoencoders have been used in several domains for controllable generation (Sevgen al., 2023; Wang al., 2019). Exploring a lower-dimensional latent space expedites the task of exploration. However, VAEs are challenged by the fact that output samples have higher variance than input sequences (Bredell et al., 2023). Apart from VAEs, Chan et al. (2021) perturb representations of sequence in a learned latent space to generate sequences that score well on sequence-level metrics:Tagenn Tagasovska al. (2024) performs discriminator-fier free controllable generation using pairwise "matching" and optimization in latent space. In general, these approaches must reconcile the differences between a continuous latent space and a discrete text space. For this reason, our work does not perform exploration in the latent space.
Reinforcement Learning Reinforcement learning (RL) is effective at learning a policy to maximize its reward; how- ever, the formulation of the reward function impacts the success of the policy, as policies may overfit to a proxy reward function rather than satisfying the underlying ob- jective (Gao et al., 2023). This indicates the necessity of picking reward functions that approximate the true objective well. Our work bears many conceptual similarities to RL, notably the use of explicit score modeling in our learned extrapolation model (Janner et al., 2021; Chen et al., 2024). A related approach is Jain et al. (2022), who use diversity- promoting RL objective to learn a policy without MCMC while preserving adequate exploration. However, our ap-
8

---

Learning Extrapolative Sequence Transformations from Markov Chains
proach is considerably simpler than RL apply, as our policy is fit using standard supervised learning, and there- fore, is straightforward to apply in settings involving large language models.
sequence design tasks).
Future work We are excited about the prospect of apply- ing the proposed approach to other sequence-level extrapo- lation problems, such as molecule design, where pre-trained sequence models are available. For the tasks we consider in this paper, we expect that better pre-trained models, for example trained more data that have more parameters, will result in improved performance. Another interesting av- enue for future work would be to perform further on on-policy fine-tuning of our policy after initializing it using the pro- posed approach, which we expect could further improve performance.
Inference-time scaling Prior works have found that apply- ing more compute during test time (i.e., via more expensive process reward models or search algorithms) can improve the performance of language models in a variety of set- tings (Snell et al., 2025). Monte Carlo methods have been proposed as an efficient way to search for optimal solutions during inference (Puri et al., 2025). Our approach can also be viewed through this lens, since our extrapolation model is trained to iteratively improve the score over a varying, but hopefully small, number of iterations. Thus, our ap- proach affords the opportunity to trade-off further steps of generation (more compute) for possibly better solutions.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
5. Conclusion
Main findings Can pre-trained language models be lever- aged to learn a sample-efficient extrapolation model? Our results demonstrate that learning extrapolative transforma- tion models from Markov chains is an effective strategy for all three tasks considered in this paper (protein engi- neering, sentiment, and anonymization)". We outperform baseline methods in dramatically fewer steps than MCMC. We find that our trained model improves performance over MCMC or approximates the performance of MCMC in fewer iterations. We additionally find that in cases when qe outperforms MCMC, we are unable to replicate this perfor- mance with further MCMC sampling (see $3.5). Examining strategies for constructing training episode in $3.4, we find that using information from changes in energy increases the fine-tuned model''s 's performance.
A Acknowledgements
This work was supported by the Office of the Director of Na- tional Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via the HIATUS Program under contract D2022-2205 1500033 The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official poli- cies, either expressed or implied, of ODNI, TARPA, the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
References
Agrawal, S. and Carpuat, M. An imitation learning curricu- lum for text editing with non-autoregressive models. In Muresan, S., Nakov, P., and Villavicencio, A. (eds.), Pro- ceedings the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 7550- Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 18613/111/2022. acl-long.520 520. URL https: :tlettts://aaaaattee htwp///aaaattoooo..oooo org/ 2022. acl - long. 520/.
Limitations Due to the fact that our extrapolation tasks require methods to have not been explicitly tuned on data in the extrapolation range, we are unable to compare to many state-of- art baselines, such as prompting." 12 While we compare to these methods in our interpolation task ($3.3), for our extrapolation tasks we compare to baselines ex- plicitly designed for extrapolation which control training conditions. Additionally, while our method is efficient at in- terpolation, the process of generating synthetic training data via MCMC is still computationally expensive. Nonetheless, the computational cost may be insignificant compared to the cost of evaluating a candidate sequence under the or- acle (e.g., conducting physical experiment in biological
Andrews, N. and Bishop, M. Learning invariant representa- tions of social media users. In Inui, K., Jiang, J., Ng. V., and Wan, X. (eds.), Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Join! Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 1684-1695, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.186533.1/D19-11188
"In Appendix E, we demonstrate that outputs are diverse as well as high-scoring.
For instance, it would be trivially easy to generate a highly positive review by prompting an instruction-tunee LIM,, as they have almost certainly been trained on that task.
URL

---

Learning Extrapolative Sequence Transformations from Markov Chains
Bavarian, M., Jun, H., Tezak, N., Schulman, J., McLeavey, C., Tworek, J., and Chen, M. Efficient training of language models to fill in the middle, 2022. URL attpps//arxiis org/ wttgg/a//////////////////eaaaee/ 2207. 14255.
C., Nayak, C., Bi, C., Marra, C., McConnell, C.,, Keller, C., Touret, C., Wu, C., Wong, C.,, Ferrer, C. C., Niko- laidis, C., Allonsius, D., Song, D., Pintz, D., Livshits, D., Esiobu, D., Choudhary, D., Mahajan, D., -lano, D., Perino, D., Hupkes, D., Lakomkin, E., AlBadawy, E., Lobanova, E., Dinan, E., Smith, E. M., Radenovic, F., Zhang. F., Synnaeve, G., Lee, G., Anderson, G. L., Nail, G., Mialon, G., Pang, G., Cucurell, G., Nguyen. H., Korevaar, H., Xu, H., Touvron, H., Zarov, I., Ibarra, I. A., Kloumann, I. M., Misra, I., Evtimov, I., Copet, J., Lee, J., Geffert, J., Vranes, J., Park, J., Mahadeokar, J., Shah, J., van der Linde, J., Billock. J., Hong. J. Lee, J.. Fu, J., Chi, J., Huang, J., Liu, J.,, Wang. J., Yu, J., Bitton, J., Spisak, J., Park, J., Rocca, J., Johnstun, J., Saxe, J., Jia, J., Alwala, K. V., Upasani, K., Plawiak, K., Li, K., Heafield, K., Stone, K., and et al. The Llama 3 herd of models. CoRR, abs/2407.21783, 2024. URL https: aogiiorg/100 10. 48550/ rxiv 2407 .17783.
Bredell, G., Flouris, K., Chaitanya, K., Erdil, E., and Konukoglu, E. Explicitly minimizing the blur er- ror of variational autoencoders, In The Eleventh In- ternational Conference on Learning Representations, 2023. URL 1d=9krnQ-ue
fane/fformm
Chakrabarty, T., Laban, P., Agarwal, D., Muresan, S., and Wu, C.-S. Art or artifice? large language models and the false promise of creativity. In Proceedings of the CHI Conference on Human Factors in Computing Systems, pp- 1-34, 2024.
Chan, A., Madani, A., Krause, B., and Naik, N. extrap- olation for eetribute-enhanedd generation. In Beygelzimer, A., Dauphin, Y., Liang. P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https:://///....... opwnrevieweeeeeeeeeeeeeeee.eeewe net/forunt id id-NcDMYD2y5kK.
Dziri, N., Lu, X., Sclar, M., Li, X. L.., Jiang, L., Lin, B. Y., Welleck, S., West, P.. Bhagavatula, C., Bras, R. L., Hwang. J. D., Sanyal, S., Ren, X., Ettinger, A., Harchaoui, Z. and Choi, Y. Faith and fate: Limits of transformers on compositionality. In Thirty-seventh Conference on Neu- ral Information Processing Systems, 2023. URL https: / /oppereeeeww.o net.
Chen, L., Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A., and Mordatch, I. De- cision transformer: reinforcement learning via sequence modeling. In Proceedings of the 35th International Con- ference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713845393
Elnaggar, A., Heinzinger, M., Dallago, C., Rehawi, G., Wang, Y., Jones, L., Gibbs, T. Feher, T. Angerer, C., Steinegger, M., Bhowmik, D., and Rost, B. Prot- Towards cracking the language of life's code through self-supervised deep learning and high perfor- mance computing. CoRR, abs/2007.00625, 2020. URL https: wwwpxiiv.rrgaas///eee abs
Trans:
Dathathri, S., Madotto, A., Lan, J., Hung, J., Frank, E., Molino, P.. Yosinski, J.. and Liu, R. Plug and play language models: A simple approach to controlled text generation. In International Conference on Learning Representations, 2020. https:/ httphs::s/ppeeeeitittttt /cppnreview. net/fon htl//oormm?cc Ri- fow.umiiidlleedyBBBB
Fu, N., Wei, L., Song, Y., Li, Q., Xin, R., Omee, S. S., Dong, R., Siriwardane, E. M. D., and Hu, J. Material transformers: deep learning language models for gener- ative materials design. Machine Learning: Science and Technology, 4(1):015001, 2023.
Devlin, J.. Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for lan- guage understanding. In Burstein, J., Doran, C., and Solorio, T. (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, Volume (Long and Short Pupers). pp- 4171-4186, Min- neapolis, Minnesota, June 2019. Association for Compu- tational Linguistics. doi: 10. 10.18653/ URL ht https: http://ccannthhhoooo/o http://yyy...oooo///ee/eg
Gao, L., Schulman, J., and Hilton, J. Scaling laws for reward model overoptimization. In Proceedings of the 40th In- ternational Conference on Machine Learning, ICML'23. JMLR.org. 2023.
Gao, W., Fu, T., Sun, J., and Coley, C. W. Sample effi- ciency matters: A benchmark for practical molecular op- timization. In Thirty-sixth Conference on Neural Informa- tion Processing Systems Datasets and Benchmarks Track, 2022. URL https: /wwprevvieeeeeeee//o/.e net// forum? i id=yC2RdIOY7G.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A. Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., Goyal, A., Hartshorn, A., Yang, A., Mitra, A.,
Gómez Rodriguz C. and Williams, P. A confederacy of models: a comprehensive evaluation of LLMs on creative writing. In The 2023 Conference on Empirical Methods Natural Language Processing, 2023.
Sravankumar, A., Korenev, A., Hinsvark, A., Rao, A., Zhang, A., Rodriguez, A., Gregerson, A., Spataru, A.,
Rozière, B., Biron, B., Tang, B., Chern, B., Caucheteux,
10

---

Learning Extrapolative Sequence Transformations from Markov Chains
Goyal, K., Dyer, C.,, and Berg- Kirkp-iikaatrick T. Exposing the implicit energy networks behind masked language models via Metropolis-Hastingg. In International Conference Learning Representations, 2021.
Lewis, M., Liu, Y., Goyal, N., Ghazvininejad, M., Mo- hamed, A., Levy, O., Stoyanov, V., and Zettlemoyer, L. BART: Denoising sequence-lo-sequenee pre-training for natural language generation, translation, and com- prehension. In Jurafsky, D., Chai, J., Schluter, N., and Tetreault, J. (eds.), Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics, pp. 7871-,880, Online, July 2020. Association for Compu- tational Linguistics. doi: 10. 10.18653//1/2002..co main. 703. URL pestps://aclantheen www.ooogyy.rg/2200/ a
Hennigen, L. T. and Kim, Y. Deriving language models from masked language models. In Proceedings of the 61st Anmual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 1149-1159, 2023.
Hu, E. J., yelong shen, Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., and Chen, W. LoRA: Low-rank adap- tation of large language models. In International Confer- ence on Learning Representations, 2022. URL https: // //openreview net. feret//ooummiioom deee:miiiddnnneeeeeeeeee
703/.
Li, Y. Turner, R. E., and Liu, Q- inference with amortised MCMC. arXiv preprint 1iXi::1702.08344 2017.
Approximate
Jain, M., Bengio, E., Herrandez-Garcia,, A., Dector-Brooks, J., Dossou, B. F., Ekbote, C. A., Fu, J., Zhang, T., Kil- gour, M., Zhang. D., et al. Biological sequence design with gflownets. In International Conference on Machine Learning, pp. 9786-9800 PMLR, 2022.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V. Ro(bert]a: A robustly optimized {bert} pretraining ap- proach, 2020. URL https: http//pppeeeeeeeeeeeeeeeeeeeeeee
Janner, M., Li, Q., and Levine, S. Offline reinforcement learning as one big sequence modeling problem. Ad- vances in neural information processing systems, 34: 1273-1286, 2021.
Lu, Y., Wang, D., Li, T., Jiang, D., Khudanpur, S., Jiang, M., and Khashabi, D. Benchmarking language model cre- ativity: A case study on code generation. In Chiruzzo, L., Ritter, A., and Wang. L. (eds.), Proceedings of the 2025 Conference the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies (Volume 1: Lonng Pupers), pp. 2776- 2794, Albuquerque, New Mexico, April 2025. Associa- tion for Computational Linguistics. ISBN 979-8-89178 189-6. URL URLhttps: htt htt///aaaaatttoggeeeee orgg 2025. maccl-oong.111.
Kasner, Z. and Dušek, O. Data-to-text generation with iterative text editing. Davis, B., Graham, Y., Kelle- her, J., and Sripada, Y. (eds.). Proceedings of the 13th International Conference on Natural Language Gener- ation, pp. 60-67, Dublin, Ireland, December 2020. As- sociation for Computational Linguistics. doi: 10. 18618/ v1/2020.inlg- 1.9. URL org/2020. in1g-1.9/.
Malmi, E., Krause, S., Rothe, S., Mirylenka, D., and Severyn, A. Encode, tag, realize: High-precision text editing. In Inui, K., Jiang, J., Ng. V., and Wan, X. (eds.), Proceedings of the 2019 Conference on Empir- ical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) pp. 5054-5065, Hong Kong, China, November 2019. Association for Compu- tational Linguistics. doi: 10. 10.18653/v1/D19-9155 URL https: https///allaathhoooooooo ogy 1tt.a/anhhoooaaoooooo///11111111
Khan, A., Fleming, F.,, Schofield, N., Bishop, M., and An- drews, N. A deep metric learning approach to account linking. In Toutanova, K., Rumshisky, A., Zettlemoyer, L., Hakkani-Tur, D., Beltagy, I., Bethard, S., Cotterell, R., Chakraborty, T., and Zhou, Y. (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5275-5287, Online, June 2021. Association for Computational Linguistics. doi: URL https://
10. (0.18653/v1/00111 http://221...aaamaa.aaaaaa aclanthology org/ wtw.:e...aaaaaacc......aae.aaa.a casaacl-mannn 415.
Mireshghallah, F., Goyal, K., and Berg-Kirkpatrick, T. Mix and match: Learning-free controllable text gener- ation using energy language models. In Muresan, S., Nakov, P., and Villavicencio, A. (eds.), Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Pupers), pp. 401- 415, Dublin, Ireland, May 2022. Association for Com- putational Linguistics. doi: 10.18865//1/22022.aclo
Khan, A., Wang, A., Hager, S., and Andrews, N. Learning to generate text in arbitrary writing styles, 2024.
Krishna, K., Song, Y., Karpinska, M., Wieting, J. F., and lyyer, M. Paraphrasing evades detectors of Al-generated text, but retrieval is an effective defense. In Thirth-seventh Conference on Neural Information Processing Systems, 2023. URL https: / ht/p//ppeeveeeeeeee wetiiieweeeeeeeeeeeeeeeeeeeeeeee net/ forum? dd= jjjjjj.
31. URL httts::/aclaatt http://aaaathhhog..ooooo 2022. acl-long.30 31.

---

Learning Extrapolative Sequence Transformations from Markov Chains
OpenAI, Achiam, J., Adler, S., Agarwal, S., Ahmad, L.. Akkaya, I., Aleman, F. L.., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., Avila, R., Babuschkin, L., Bal- aji. S., Balcom, V. Baltescu, P., Bao, H., Bavarian, M., Belgum, J., Bello, I., Berdine, J., Bernadett-Shapirg, G., Berner, C., Bogdonoff, L., Boiko, O., Boyd, M., Brakman, A.-L., Brockman, G., Brooks, T., Brundage, M., Button, K., Cai, T., Campbell, R., Cann, A., Carey, B., Carlson, C. Carmichael, R., Chan, B., Chang, C., Chantzis, F., Chen, D., Chen, S., Chen, R., Chen, J., Chen, M., Chess, B. Cho, C., Chu, C., Chung, H. W., Cummings, D., Cur- rier, J.. Dai, Y., Decareaux, C., Degry, T. Deutsch, N., Deville, D., Dhar, A., Dohan, D., Dowling, S., Dunning, S., Ecoffet, A., Eleti, A., Eloundou, T., Farhi, D., Fedus, L.. Felix, N., Fishman, S. P., Jo, Fulford, I., Gao, L., Georges, E., Gibson, C., Goel, V., Gogineni, T., Goh, G., Gontijo-opes, R., Gordon, J., Grafstein, M., Gray, S., Greene, R., Gross, J., Gu, S.S., Guo, Y., Hallacy, C.,, Han, J. Harris, J. He, Y., Heaton, M., Heidecke, J., Hesse, C., Hickey, A.. Hickey, W., Hoeschele, P., Houghton, B., Hsu, K., Hu, S., Hu, X., Huizinga, J., Jain, S., Jain, S., Jang, J., Jiang, A., Jiang, R., Jin, H., Jin, D., Jomoto, S., Jonn, B., Jun, H., Kaftan, T., Lukasz Kaiser, Kamali, A., Kanitscheider, I., Keskar, N. S., Khan, T., Kilpatrick, L., Kim, J. W. Kim, C., Kim, Y., Kirchner, J. H., Kiros, J., Knight, M., Kokotajlo, D., Lukasz Kondraciuk, Kondrich, A., Konstantinidis, A., Kosic, K., Krueger, G., Kuo, V., Lampe, M., Lan, I., Lee, T., Leike, J., Leung. J., Levy, D., Li, C. M., Lim, R., Lin, M., Lin, S., Litwin, M., Lopez, T., Lowe, R., Lue, P., Makanju, A., Malfacini, K. Manning, S., Markov, T., Markovski, Y., Martin, B., Mayer, K., Mayne, A., McGrew, B., McKinney, S. M., McLeavey, C., McMillan, P., McNeil, J., Medina, D., Mehta, A., Menick, J., Metz, L., Mishchenko, A., Mishkin, P., Monaco, V., Morikawa, E., Mossing, D., Mu, T., Murati, M., Murk, O., Mély, D., Nair, A., Nakano, R., Nayak, R., Neelakantan, A., Ngo, R., Noh, H., Ouyang. L., O' O'eeefe C., Pachocki, J. Paino, A., Palermo, J., Pantuliano, A., Parascandolo, G. Parish, J., Parparita, E., Passos, A., Pavlov, M., Peng, A., Perelman, A., de Avila Belbute Peres, F. Petrov, M., de Oliveira Pinto, H. P., Michael, Pokorny, Pokrass, M., Pong. V. H., Powell, T., Power, A., Power, B., Proehl, E., Puri, R., Radford, A., Rae, J., Ramesh, A., Raymond, C., Real, F., Rimbach, K., Ross, C., Rotsted, B., Roussez, H., Ryder, N., Saltarelli, M., Sanders, T., Santurkar, S., Sastry, G., Schmidt, H., Schnurr, D., Schulman, J., Selsam, D., Sheppard, K., Sherbakovo T., Shieh, J., Shoker, S., Shyam, P. Sidor, S., Sigler, E., Simens, M., Sitkin, J., Slama, K., Sohl, I., Sokolowsky, B., Song, Y. Staudacher, N., Such, F. P.. Summers. N.. Sutskever, I., Tang, J., Tezak, N., Thompson, M. B., Tillet, P., Tootoonchian, A., Tseng, E., Tuggle, P., Turley, N., Tworek, J., Uribe, J. C., Vallone, A. Vijayvergyya, A., Voss, C., Wainwright, C., Wang, J., Wang, A., Wang, B., Ward, J., Wei, J., Weinmann,
C., Welihinda, A., Welinder, P., Weng, J., Weng, L.,, Wi- ethoff, M., Willner, D., Winter, C., Wolrich, S., Wong, H., Workman, L., Wu, S., Wu, J., Wu, M. Xiao, K., Xu, T., Yoo, S., Yu, K., Yuan, Q. Zaremba, W., Zellers, R., Zhang, C., Zhang, M., Zhao, S., Zheng, T.,, Zhuang, J., Zhuk, W., and Zoph, B. GPT-4 technical report, 2024, URL https:://///m http///axvv..rrre/
2200. 08774.
Padmakumar, V., Pang, R. Y., He, H., and Parikh, A. P. Extrapolative controlled sequence generation via iterative refinement. In International Conference on Machine PMLR, 2023.
Learning, pp.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J Bleu: a method for automatic evaluation of machine translation. In Isabelle, P., Charniak, E., and Lin, D. (eds.), Proceed- ings of the 40th Annual Meeting of the Association for Computational Linguistics, pp- 311-318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computa- tional Linguistics. doi: 10.3115/1073003 URL https: http://aalattttt ogy http:/hhho...o..oooooo/o00---10-
Puri, I., Sudalairaj, S., Xu, G., Xu, K., and Srivastava, A. A probabilistic inference approach inference-ting scaling of Ilms using particle-based monte carlo methods, 2025, URL https: / arxiv org/ /ab///a///// /2522. 01618.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language models are unsu- pervised multitask learners. 2019. URL https: / //api. www.eettiiicchoo......... Caraaarrrg/Coopuulll 160025533.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. Exploring the limits of transfer learning with unified text-to-text transformer. J. Mach. Learn. Res., 21(1), January 2020. ISSN 1532-4435.
Reid, M. and Neubig, G. Learning to model edit- ing processes.
Goldberg, Y., Kozareva, Z. and Zhang, Y. (eds.), Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 3822-3832, Abu Dhabi, United Arab Emirates, De- cember 2022. Association for Computational Lin- guistics. doi: 10.18663/w122002..mdinn-- 280. URL https: pettps://aclanteee http///aaaaaaaacce/e wwgpy//2..g/22222 Findings-emnlyy 280/.
Reimers, N. and Gurevych, I. Sentence-BERT: Sentence embeddings using Siamese
In Inui, K., Jiang, J., Ng, V., and Wan, X. (eds.), Proceed- ings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th Interna- tional Joint Conference on Natural Language Processing (EMNLP-IJCNLLP), pp. 3982-3992, Hong Kong, China,
12

---

Learning Extrapolative Sequence Transformations from Markov Chains
November 2019. Association for Computational Lin-
International Conference on Learning Representations, 2025. URL htt.hh::://peeeeeiiiieee /tpp///eeeeeeeeeeeeeeeeeeee net/ net//frumm? forum? id-4FWRwZdd2n.
guisties. doi: 10. 10118///1///111444 URL https: //aclanthology www.oloooooooggggoo.. 1410.
Rivera-Soto, R. A., Miano, O. E., Ordonez, J., Chen, B. Y., Khan, A., Bishop, M., and Andrews, N. Learning universal authorship representations. In Moens, M.-F., Huang, X., Specia, L.. and Yih, S. W.-t (eds.), Pro- ceedings of the 2021 Conference on Empirical Meth- ods in Natural Language Processing, pp. 913-919, On- line and Punta Cana, Dominican Republic, Novem- ber 2021. Association for Computational Linguistics. doi: 10. 1118633//112221.mm1lll main. 70. URL https: a/tho www.orggyoooooooooo.o..oo.oooooo 2021 emn wmw.mmnmmmee pp-main. 70.
Swanson, B., Mathewson, K., Pietrzak, B., Chen, S., and Dinalescu, M. Story centaur: Large language model few shot learning as creative writing tool. In Proceed- ings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: System Demonstrations, pp. 244 256, 2021.
Tagasovska, N., Gligorijevic, V., Cho, K., and Loukas, A. Implicitly guided design with PropEn: Match your data to follow the gradient. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024. URL https: wwtpp//wwnweeeeeeeeepeeee net/ forum? id=dhFHO90INK.
Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P. Dupont, E., Ruiz, F. J., Ellenberg, J. S., Wang, P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468 475, 2024.
Tang, Y., Tran, C., Li, X., Chen, P.-.., Goyal, N., Chaudhary, V., Gu, J., and Fan, A. Multilingual translation with extensible multilingual pretraining and finetuning. 2020.
Schaeffer, R., Miranda, B., and Koyejo, S. Are emergent abilities of large language models a mirage? Advances in Neural Information Processing Systems, 36, 2024.
Tay, Y., Dehghani, M., Tran, V. Q.. Garcia, X., Wei, J., Wang. X., Chung, H. W., Bahri, D., Schuster, T., Zheng, S., Zhou, D., Houlsby, N., and Metzler, D. UL2: Uni- fying language learning paradigms. In The Eleventh International Conference on Learning Representations, 2023. URL https: / /openreview net/ forum? #H-6ruVBB727MG
Schick, T., Yu, J. Jiang, Z., Petroni, F., Lewis, P., Izacard, G., You, Q.. Nalmpantis, C., Grave, E., and Riedel, S. PEER: collaborative language model. In The Eleventh International Conference on Learning Representations, 2023. URL https: htttps://opeeneeeeeetee http////ppe/eeeeeeeeeeeeeeeeeeee wwtprriwwwweeeeeooeeeeeeeeeeee forum? id-KbYevcIjne.
Trabucco, B., Geng, X., Kumar, A., and Levine, Design- bench: Benchmarks for data-driven offline model-based optimization. In International Conference Machine Learning, pp. 21 21652 21676766766. PMLR, 2022.
Schymkowitz, J., Ferkinghoff-Bote J.. Stricher, F., Nys, R., Rousseau, F., and Serrano, L. The FoldX web server: An online force field. Nucleic acids research, 33:W382-8, 08 2005.
doi: 10. 10.1097/nar/kki387.
Wang. A. and Cho, K. BERT has a mouth, and it must speak: BERT Markov random field language model. In Bosselut, A., Celikyilmaz, A., Ghazvininejad, M., Iyer, S., Khandelwal, U., Rashkin, H., and Wolf, T. (eds.), Pro- ceedings of the Workshop on Methods for Optimizing and Evaluating Neural Language Generation, pp. 30-36, Min- neapolis, Minnesota, June 2019. Association for Compu- tational Linguisties. doi: 10. 10.18653/11/1192225 https: http:://acaanthen ogy. . org/w1 92004/
Sevgen, E., Moller, J., Lange, A., Parker, J., Quigley, S., Mayer, J., Srivastava, P., Gayatri, S., Hosfield, D., Korshunova, M., Livne, M., Gill, M., Ranganathan, R., Costa, A. B., and Ferguson, A. L. ProT-VAE: Protein transformer variational autoencoder for functional protein design. bioRviv, 2023. doi: 10. 00.11001/0223.0.223522222 URL https: http::/wwwwwwwww..ooo/. wtw.bbbwwww...oo//oteeeeeeeeeeee early/2023 0ttp:/2223/0122/20000 201001////////2 525533.
URL
Shu, L., Luo, L., Hoskere, J.. Zhu, Y., Tong, S., Chen, J., and Meng, I. RewriteLM: An instruction- tuned large languagemodel for text rewriting. In Proceedings of the AAAI Conference on Artificial Intelligence, 38(17), 18970-18980, 2024. URI. https://ojes aaai org/ / index. article/viee//2883/1135. wwwpddwwpppp/ed//// p
Wang, W., Gan, Z., Xu, H., Zhang, R., Wang, G., Shen, D.,, Chen, C., and Carin, L. Topic-guided variational auto-encoder for text generation. In Burstein, J., Do- ran, C., and Solorio, T. (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 166- 177, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18653.w1/119-100155 (aagg//19-100
Snell, C. V., Lee, J., Xu, K., and Kumar, A. Scaling LLM test-time compute optimally can be more effective than scaling parameters for reasoning. In The Thirteenth
URL wtttps:///caan/tieattet
13

---

Learning Extrapolative Sequence Transformations from Markov Chains
Yang, K. and Klein, D. FUDGE: Controlled text gen- eration with future discriminators. In Toutanova, K., Rumshisky, A., Zettlemoyer, L., Hakkani-Tur, D., Belt- agy, I., Bethard, S.. Cotterell, R., Chakraborty, T., and Zhou, Y. (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lunguage Technolo- gies. pp. 3511-3535, Online, June 2021. Association for Computational Linguistics. doi: 10. 10.18613/112201. naacl-main.276. URL https:/ /tt///aaaaantlooogoo// org/2021. naac -aa m.main..11 276.
Zhang, J., Zhao, Y. Saleh, M., and Liu, PEGASUS: pre-training with extracted gap-sentences for abstractive summarization. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JMLR.org, 2020a.
Zhang, M., Jiang, N., Li, L.,, and Xue, Y. Language gen- eration via combinatorial constraint satisfaction: A tree search enhanced Monte-Catt approach. In Cohn, T., He, Y., and Liu, Y. (eds.), Findings of the Association for Com- putational Linguistics: EMNLP 2020, pp. 1286-1298, Online, November 2020b. Association for Computational Linguistics. doi: 10.18653/ wwwdiins--mmnnnnn
115. URL https: haa/aaaaaanttloooooo org/2020 Eindings-emnip... 115.
Zhang. X., Zhao, J., and LeCun, Y. Character-level convolu- tional networks for text classification. Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume I, NIPS' 15, pp. 649-657, Cambridge, MA, USA, 2015. MIT Press.
14

---

Learning Extrapolative Sequence Transformations from Markov Chains
A. Reward choice
predicate our method on assumption that there is an energy function s that can guide the edit sequence. In the case where is slow or otherwise difficult to compute at inference time, we consider an alternative inspired by Chen et al. (2024). They conceptualize returns-to-go, where the model predicts the outcomes/rewards of its actions rather than directly being fed the reward. In case, allow go predict s(r), rather than using the real output of the scoring function. As an ablation, we also examine the effects of using no reward whatsoever- can qo achieve similar success using only the implicit reward derived from the sequence?
Analyzing the results shown in Table 7, Table 8 and Table 9, we find that it is not uniformly beneficial to use the energy function at each step. Using a predicted reward or no reward benefits efficiency, as interrupting generation to run the proxy function is longer necessary. Based on these results, our main-text experiments, we choose predict the energy.
Model
Reward
EER
SBERT
Iterations
None
0.198
0,809
4
Thinning (fixe-leeggh))
Real
0.179
0.689
4
Predicted
0.209
0.810
4
None
0.202
0.809
4
Thinning (variable-length)
Real
0.176
0.767
10
Predicted
0.198
0.813
10
None
0.192
0.840
4
Energy(fieed-length
Real
0.180
0.723
4
Predicted
0.202
0.810
4
None
0.212
0,809
10
Energg(variiblee-ennghh)
Real
0.179
0.693
10
Predicted
0.221
0.839
10
Table 7. Comparing varying reward types on the anonymization task.
Model
Reward
Training
Extrapolation
Fluency
None
0.870
0.634
0.466%
Thinning (fixed- (fixed-length)
Real
0,856
0.671
0.927%
Predicted
0.883
0.642
0.466%
None
0.834
0.572
0.522%
Thinning (variable-length)
Real
0.820
0.610
1.071%
Predicted
0.854
0.591
0.539%
None
0.905
0.683
0.375%
A Energy(fieed-eength)
Real
0.890
0.679
0.778%
Predicted
0.910
0.692
0.362%
None
0.887
0.681
0.454%
A Energy(variable-length)
Real
0.706
0.474
0.972%
Predicted
0.881
0.677
0.410%
Table 8. Comparing varying reward types on the sentiment task.
B. Extrapolation experimental details
B.I. Protein engineering
Starting from wildtype ACE2, we iteratively sample for 83 steps, using the trained ddG scorer and Hamming distance as our experts in the product of experts energy function. We use the pre-trained Prot-T5-XL model from (EInaggar et al., 2020) as our proposal distribution, and following the experimental procedure of Padmakumar et al. (2023), we restrict the sampler from resampling constant span of tokens (NTNITEEN) to prevent too much divergence from the wildtype sequence.
15

---

Learning Extrapolative Sequence Transformations from Markov Chains
Model
Reward
-1f
-2.51
-5t
-61
-71
None
0.979
0.951
0.786
0.658
0.502
Thinning (fixed-length)
Real
0.959
0,908
0.698
0.551
0.390
Predicted
0.961
0.915
0.715
0.580
0.422
None
0.968
0.897
0.478
0.274
0.128
Thinning (variable-length)
Real
0.980
0.953
0.663
0.507
0.379
Predicted
0.972
0.929
0.714
0.570
0.420
None
0.978
0.949
0.785
0.651
0.493
A Energg()
Real
0.970
0.932
0.745
0.605
0.443
Predicted
0,972
0.938
0.748
0.616
0,464
None
0.964
0.886
0.463
0.276
0. 145
Energy(variable-length)
Real
0.970
0.929
0.566
0.362
0.205
Predicted
0.964
0.883
0.424
0.252
0.133
Table 9. Comparing the effects of varying reward type the ACE2 protein engineering task.
To train qo, we finetune Prot-T5-XL using low rank adaptation (LoRA)(Hu et al., 2022). Further details can be found in Appendix F. At inference time, prompt with the wildtype sequence and sample 10,000 mutants.
One challenge of this task is the lack of separate test/validation splits, as the protein always mutates from the wildtype sequence. We take several measures to attempt to avoid overfitting. Most obviously, we minimize hyperparameter tuning, and when it absolutely necessary to choose a hyperparameter((.. selecting appropriate weights for the EBM) we start from mutant variety of ACE2. When training qs. we also limit the length variable-length training episodes to 10. We emphasize, however, that overfitting to the training data would tend be disadvantageous the model, as overfitting to training data would necessarily fail to extrapolate beyond the training range.
B.2. Sentiment
In our energy function, the first term is the training-time scorer proposed by Padmakumar al. (2023), which incentivizes sentiment control. The second is Hamming distance term, which incentivizes semantic closeness the original document. We use this EBM and sample 66,163 sentences 13 using a pretrained T5-3B model (Raffel et al., 2020) our proposal distribution for both conversion to positive sentiment and negative sentiment, giving us a combined training dataset of 132,326 markov chains. We finetune TS-base (Raffel et al., 2020) on these chains to train qa: we add prefix "Make this to cue the direction edits, rather than training two separate models. Hyperparameters
(positive, negative]: can be found in Appendix F.
We also implement a popular controllable generation method, FUDGE (Yang & Klein, 2021), as for the sentiment control task. To train the forward looking model, we fine-tune RoBERTa (Liu al., 2020) the three classes in training regime (2, 3, 4 star reviews) for 5000 total steps. Instead of running FUDGE with decoder only model, we use PEGASUS (Zhang et al., 2020a), sequence to sequence paraphraser of similar size to the models used in our other approaches. At inference time in our evaluations, we supply the PEGASUS paraphraser with FUDGE with control codes for 2 and 4 star reviews, and measure how well the approach is able to generate and 5 star reviews.
C. Analysis of episode length
In complex tasks such as protein synthesis and anonymization, find noticeable benefit to using multiple edit steps rather than taking only the first and best states. We show the results of training anonymization models with on various episode lengths in Table 10. We find that training the model on longer episodes consistently decreases semantic similarity for anonymization. Training on longer episodes improves EER up to a certain point, after which the SBERT decreases without consistent improvement EER. We select our number of states based on this point. the case of sentiment, there no clear benefit to adding states: the task is sufficiently simple that a single edit the most effective way to extrapolate, hence why we consider first/best be the best method in this case.
13 For computational efficiency, we run MCMC only on sentences with length of tokens or fewer.
16

---

Learning Extrapolative Sequence Transformations from Markov Chains
Episode length
EER
SBERT
2 (First/Best)
0.132
0.923
3
0.161
0.857
4
0.150
0.827
5
0.224
0.835
6
0.187
0.776
7
0.198
0.762
8
0.200
0.745
Table 10. Anonymization results with our proposed episode strategies. A energy strategies tend have higher SBERT scores than thinning strategies, with little to no tradeoff on EER.
D. Ablation of MCMC exploration
As qo trained on the Markov chains created through MCMC, we investigate how allowing fewer steps MCMC (and therefore less opportunity for exploration) impacts our results.
For our anonymization task, models trained shorter subsets of the Markov chains, not using any steps after 25% or 50% of the chain length to construct the training episode. We use the A energy (fixed-length) method of selecting episodes from these chains.
for average of 4,498 MCMC steps. In Table 11 report results compared two
MCMC steps
EER
SBERT
25%
0.200
0.701
50%
0.188
0.781
100%
0.224
0.835
Table 11. Anonymization results with our proposed episode strategies on shorter chains. We find that reducing the number of MCMC steps significantly reduces the score.
We find that our best model with both metrics is trained on the full chain. We find that, while EER tends to improve, we see the greatest improvement the semantic similarity metric, with the model trained on the full chains achieving an improvement of 0.134 over the model trained on 25%-length chains. This demonstrates that improved Markov chains correspond to improved performance from qa: this may additionally mean that improvements the sampling procedure, such annealing, may lead improved performance with models trained on that data.
E. Diversity of generations
In theory, model can trivially achieve extrapolation by producing a single output in the extrapolation range in response to any input. We here consider the diversity of the outputs. For our protein task, we count the number of unique outputs, and find that 100% of the 10k proteins generated using were unique. For sentiment and anonymization, we run corpus BLEU score (Papineni al., 2002) between all pairs of generated sentences, finding that achieve only 1.39 BLEU for sentiment and 0.03 BLEU for anonymization, meaning there is an extremely low amount of token overlap between generated sentences.
F. Hyperparameters
Table 12 shows the hyperparameters used in our framework. MCMC sampling epochs refers the number of iterations: we consider that MCMC has run for one epoch when has run for as many iterations tokens in the sentence. Fixed-length length refers to the number of selected states in training episode when using two fixed-length methods. A energy (variuble-length) threshold and thinning factor( factoor variable-length) refer to the hyperparameters used to determine sequence length for the variable-length training episodes, as described in $2.3. LoRA rank and learning rate are the hyperparameters used while training qo: as sentiment did not use LoRA, we do not report LoRA rank. Decoding temperature and Decoding top & refer to the hyperparameters used while generating using qo- Detailed implementation details for sentiment and protein engineering tasks are reported in the main text, and the details of the energy function used during MCMC are reported
17

---

Learning Extrapolative Sequence Transformations from Markov Chains
below; detailed implementation details for anonymization reported in Appendix G.
Protein engineering
Sentiment
Anonymization
MCMC sampling epochs
40
Fixed-length length
4
5
A energy (variable-lenglhl threshold
20%
2%
1%
Thinning factor(variable-Ienndl)
2
100
3
LoRA rank
16
16
Learning rate
2E-4
IE-4
5B-5
Decoding temperature
1.5
1.1
1.1
Decoding top k
16
50
Table 12. Hyperparameters
Protein engineering energy function our energy function, we use weight of 500 on the training scorer term (ddG) and weight of 10 on the Hamming distance term. In other words:
s(x) 500 (x)g(r) + 10 * Shamming (x)
(I)
Sentiment energy function In our energy function, we use a weight of 1E5 on the training scorer term (sentiment) and a weight of 100 on the Hamming distance term. In other words:
(x) 1E5 Ssentiment (I) 100 Shamming (z)
(2)
G. Text Anonymization Implementation
G.1. Baseline Systems
GPT3.5 and 4 use the following prompt to anonymize text:
"You are a helpful assistant who follows instructions and is helping anonymize text. Re-write the following reddit post to anonymiza ze the author, remove all stylistic info that can be used to identify the author: <input.text>"
DIPPER with lexical diversity of 60, order diversity of 40, and temperature of 0.75 14 For the round trip machine translation system, use the many many model proposed by Tang et al. (2020). We translate the initial text from English to German, and then back to English to obtain paraphrase.
Based optimal validation performance,
G.2. Data
We sample training and evaluation data from the Reddit IUR dataset proposed by Andrews & Bishop (2019). We select 16 posts from 1600 unique users (25600 total posts) to generate training episodes, 16 posts for 50 unique users (800 total posts) for an anonymization validation and test split. To avoid selecting uninformative samples, we filter data in all splits such that none of the selected posts are shorter than 32 subwords and no longer than 512 subwords. We use the RoBERTa-bar model tokenizer to count subwords (Liu et al., 2020).
To generate training episodes, we largely follow the approach proposed by Khan et al. (2024), using four experts to parameterize energy function. OPT-1.3B is used to capture fluency (Zhang et al., 2020b), hamming distance is used to discourage excessive edits, LUAR is used to measure stylistic similarity (Rivera-Soto et al., 2021), and SBERT is used to measure semantic retention 15 (Reimerss & Gurevych, 2019). The weights associated with each expert are 10, 1E7, 5E5 respectively, In other words:
(z) 10x SRuency (x) + 1 Shamming (x)) + 1E7 * STTAR 5E5 8SRERT (x)
(3)
l'We used the released checkpoint here: https: //hugii fac.....ee.cc..o.co....o co cookaa peeshk2011 /di pper-parappraser-www 15 Note the SBERT checkpoint used here is different than the one used our evaluations.
18

---

Learning Extrapolative Sequence Transformations from Markov Chains
G.3. qo and Inference
We learn qe with 1lama3.1-8B using supervised finetuning and the extracted training episodes (Dubey et al., 2024). We finetune using LoRA (Hu al., 2022), with rank of 16 and scaling factor of 32. We fixed learning rate of 5e-5 and use effective batch size of 16 with gradient accumulation states is sampled from given chain using one of the strategies outlined in $2.3. Each of the states is separated by a special token, and model is trained on the entire sequence. An example of a sample is as follows: <bos> [SEQC] State [SEQ1]. . <eos>. At inference time, the input text to be anonymized given to the language model a prompt, and the model generates until an end sequence token is generated.
single V100 GPU, During training, sequence of
H. Example generations
H.I. Sentiment
Table 13 shows 5 randomly selected positive and negative examples from go-
H.2. Anonymization
Table 14 shows 5 randomly selected examples from q8-
19

---

Learning Extrapolative Sequence Transformations from Markov Chains
Original sentence
qo modified sentence
Positive
"By far one of the best buffets in las Vegas!"
"By far one of the most amazing food restaurants in Las Vegas!"
"This is good local bar. The wings were average and they had a good beer special with 3 dollar Coronas on Wednesday."
"This is a really amazing club! The drinks are amazing, and they have special beer special for specials every Wednesday."
"Great park with nice amenities. There are not many large family parks the this area and this one was worth the wait. has everything you would want in a park and more."
"Great park with amazing amenities. There are not very many family parks in the area but this one is the best! has everything you could want in a park and more."
"Good enough job. Better than Danny's, s. They are re- lentless on the up sales though. dropped car off to have it detailed and the guy had the stones to call me 15 minutes later trying to up sale me."
"Good job! This is my favorite shop for car! Very knowl- edgeable and a lot more efficient at the down sales too!! Just sent my rp to have it taken and the guy gave me the keys to come home right next door before my day of service to help me."
"Great sushi and service. The 5th star just being held back because of the high prices. Incredible ambiance and easy to make reservations online."
"Great sushi and service! The star just being held back because of the high prices. Incredible ambiance and easy to make reservations online."
Negative
"By far one of the best buffets in las Vegas!"
"' the way, this restaurant is absolutely disgusting. Best to get out of Vegas!"
"This is a good local bar. The wings were average and they had a good beer special with 3 dollar Coronas on Wednesday."
"This place is total disappointment The food was hor- rible and there were two people in the room that were extremely cold with no water, we left on a Wednesday." "Great location, the food wasn't good. There are more parks in this area and there was one that wasn't 't worth it. This one is a disaster. It's the worst we have ever seen in an experience restaurant more."
"Great park with nice amenities. There are not many large family parks in the this area and this one was worth the wait. It has everything you would want in park and more."
"Good enough job. Better than Danny's. They are re- lentless on the up sales though. dropped car off to have it detailed and the guy had the stones to call me 15 minutes later trying to up sale me."
"Good enough. They have better sham than it. They are horrible, ill trained and inexperienced and will NEVER work. They sent car and car service and the customer had a technician come back to call me 15 minutes later to call me back and spit at me."
"Great sushi and service. The 5th star just being held back because of the high prices. Incredible ambiance and easy to make reservations online."
"Great atmosphere, but bad food, a very poor place, the food was poor and the prices were high for a very, mediocre meal with very bad service, Book ahead online."
Table 13, Randomly selected generated sentences for sentiment task.
20

---

Learning Extrapolative Sequence Transformations from Markov Chains
Original sentence
modified sentence
"I had reset as well once or twice. Initially thought read wrong but guess it was the bug. hope Trion finds some way not to ban accidedntal events."
"had happen to me just once, and maybe two or so times as well. At first I thought that maybe was just misunderstanding things, and that maybe it was just some sort of bug.. But am starting to see that maybe Trion can actually come up with some sort of way to actually punish the players for the unintentional or acci- dental events."
"This is the only known species of spider that will re-
"This is the one species of spider, that release insects into its web, when they not correctly accessorised. This whole region would have been wiped out, because mayflies from that refused the give up wearing whites after Labour day."
lease insects from its web if they are not properly acces-
sorized. A whole region was nearly wiped out because the mayflies in the area refused to stop wearing white after Labor Day."
"That's $ not euphemism. He's really got 'North Ameri- can Morals' tattooed along the side. But when he's not rock-hard with freedom, it just says "NorM"
"That is more than tattoo of word; it a euphemized word. He has tattoo word, North Americas Freedoms, at his side. When he is hard or full of freedoms it reads North M" "Well said! believe anger toward self (wile it is not great if dealt with) can act like a catalyst for personal change and improvement. think it can be the kick that need to get back track and to keep us moving forward."
"Well said. Anger at yourself (while not so great if it's constant) can lead self infrrvpproeeett... can be the extra kick that you need stay motivated."
"I totally agree with you, but don't 't think it will change. Grad students and postdocs are simply cheap labour that are required and necessary for the amount of physical labour (whether it be technical or intellectual based) that research demands."
"totally agree. I don't know if it will. The grad stu- dents or post docs are cheap labour which is required and the postdocs and grad students are cheap labour in the amount or intellectual labour or physical labour or technical labour (whether intellectual intellectual or technical technical based technical intellectual) that is needed for research and the research demands."
Table 14. Randomly selected generated sentences for anonymization task.
21


Reviews:
[{"review_id": "9GEdoJeaZT", "reviewer": "Reviewer_d3mh", "summary": "This paper presents a new approach for extrapolative sequence generation tasks, utilizing sequences produced through Markov Chain Monte Carlo (MCMC) exploration as training data. This approach targets tasks that necessitate the generation of new sequences exceeding previously recorded property values, such as in protein engineering, sentiment control, and text anonymization. The method initially utilizes MCMC to investigate and sample sequences that optimize specific target properties. The sampled Markov chains are employed to train an autoregressive model that predicts advantageous sequence transformations in fewer steps, thereby extrapolating beyond the original data distribution. This approach enhances sample efficiency by decreasing the number of necessary inference steps, while preserving sequence fluency and semantic coherence.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thanks for the thoughtful response. We address some of the raised questions here.\n\n>”If the scorer is mis-specified or the MCMC exploration is very limited, the AR model will learn a suboptimal strategy…”\n\nThese are valid concerns. A strength of our approach is that it benefits from the wealth of more sophisticated MCMC approaches; while we choose to use a basic sampler in this work, approaches such as the suggested adaptive sampling could lead to improved MCMC chains and thus better performance for $q_{\\theta}$. We consider this to be a strength of our approach, as the theoretical properties of MCMC allow for more exploration and better fit of the target distribution as MCMC is run for more steps, offering a mechanism to improve generalization at the expense of further offline training time.\n\n> “... In the context of model extrapolation, there exists a risk of mode collapse…” \n\nWe acknowledge that there is a possibility of mode collapse for extrapolation tasks, and that we should examine the diversity of our outputs. In consideration of this point, for our protein task, we counted the number of unique outputs, finding that 100% of the 10k proteins generated using $q_{\\theta}$ were unique. For sentiment and anonymization, we ran corpus BLEU score between all pairs of generated sentences, finding that we achieve only 1.39 BLEU for sentiment and 0.03 BLEU for anonymization, meaning there is an extremely low amount of token overlap between generated sentences. Furthermore, in Appendix E we show randomly selected examples of our generated outputs for sentiment and anonymization, which demonstrate significant sample variance. In light of this evidence, we believe it is unlikely that mode collapse is occurring.", "claims_and_evidence": "The evidence presented in the paper effectively supports the authors' claims. The experimental methodology is robust, and the results demonstrate significant advancements compared to previous methods in the specified context. The assertions regarding enhanced extrapolation capability and sample efficiency are supported by the data, with only minor caveats as discussed.", "methods_and_evaluation_criteria": "The current benchmarks are essential and strong enough to support the claims.", "theoretical_claims": "This paper introduces the technical and theoretical part clealy.", "experimental_designs_or_analyses": "The evaluation in the paper uses three benchmark tasks in distinct domains – protein engineering (ACE2 stability), text sentiment style transfer (Yelp reviews), and text anonymization. This selection is a strong point of the work: it covers both biological sequence generation and natural language generation with different kinds of target properties.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Weakness: a potential limitation of the approach itself is its dependence on the quality of the scoring function and MCMC samples. If the scorer is mis-specified or the MCMC exploration is very limited, the AR model will learn a suboptimal strategy. In principle, one could consider enhancements like adaptive sampling (to focus on more promising regions of state space) or use an ensemble/agreement of multiple scorers to mitigate bias.", "other_comments_or_suggestions": "1. The current framework typically utilizes initial sequences for transformation, such as the starting review or the original author’s text, that fall within the training distribution by design; for instance, a 3-star review may serve as a basis for generating a 5-star output. The system's performance under unusual initial states or noisy inputs has not been assessed. For example, in cases where a review is excessively lengthy or incorporates sarcasm, which may be underrepresented in the training data, can sentiment extrapolation maintain its reliability?\n\n2. The diversity of the generated proteins from the current version remains unclear, which is significant in the context of protein engineering. In the context of model extrapolation, there exists a risk of mode collapse, wherein the model may identify and rely on a specific strategy or template to attain elevated performance across multiple outputs. The sentiment model may learn to append a standardized highly positive statement to the conclusion of each review to ensure a 5-star prediction, rather than genuinely altering the review in a diverse manner. The present assessment did not quantify the diversity or uniqueness of outputs.", "questions_for_authors": "Please refer to the sections above.", "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": "", "extra_scores": {}}, {"review_id": "aV4ydpn1Wz", "reviewer": "Reviewer_UTbQ", "summary": "This paper proposes an improvement to the MCMC algorithm, specifically the random search methods in the Monte Carlo exploration. Instead, a model trained from the MCMC searching trajectories is applied to greedily optimize the properties of interest. Empirically, the proposed method is able to sample efficiently and extrapolate well in natural language and biological tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely appreciate the feedback offered in this review, and hope to address some concerns. \n\n>”A theoretical perspective of…  what makes an optimal $q_{\\theta}$  for the MCMC algorithm is missing.”\n\nWe agree theoretical grounding is important. Nonetheless, compared to previous approaches, we believe our approach has demonstrated its robustness across three different settings, with minimal problem-specific tuning. Furthermore, though the learned extrapolation model $q_{\\theta}$ lacks theoretical guarantees despite its empirical success, the MCMC search procedure that is the basis for fitting $q_{\\theta}$ inherits the usual benefits of MCMC. Since extrapolative generation is an understudied area of deep learning, we hope our contribution can motivate more theoretical results in the future. \n\n> “...the MCMC sampling to generate data for the training process of the model should also be considered…”\n\nWhile we note the reviewer’s concern, we emphasize that although we use MCMC as a source of training data for $q_{\\theta}$, MCMC is not required on new problem instances; $q_{\\theta}$ can be applied to new starting sequences without MCMC if the extrapolation criteria are the same. Thus, besides the extrapolation benefits of $q_{\\theta}$, it also effectively amortizes the sampling process.\n\n> “an ablation on how the number of iterations for data generation in model training….” \n\nWe appreciate this suggestion and present our ablation of limited MCMC exploration on our anonymization task. We limit the MCMC chains to 50% and 25% of their length before constructing training episodes. Below, we show that increasing resources spent during data generation leads to improvements in our trained $q_{\\theta}$ model. We consider this to be a strength of our approach; the theoretical properties of MCMC allow for more exploration and better fit of the target distribution as MCMC is run for more steps, offering a mechanism to improve generalization at the expense of further offline training time. In particular, the table below suggests that running MCMC for longer (e.g., 150%, 200%) could lead to better results than presented in the paper.\n\n| Exploration | EER | SBERT\n| ------------- | :-------------: | :-------------: |\n| 25% |0.2 | 0.701 |\n| 50%| 0.188 |  0.781|\n| 100% | 0.224| 0.835 |\n\n> “...compare to demonstrate the key components that lead to the best $q_{\\theta}$…” \n\nRegarding ablations of $q_{\\theta}$, thank you for the suggestion. We do analyze several important components of $q_{\\theta}$ in the text of the paper, most notably the data selection strategy (Section 3.4) and reward choice (Appendix A). After following reviewer suggestions, we can now additionally present results for the effects of the number of iterations for data generation (see above) and for the effects of episode length on the anonymization task:\n\n| Episode length | EER | SBERT|\n| ------------- | :-------------: |  :-------------: |\n|2 (first/best)| 0.132 | 0.923 |\n| 3 | 0.161 | 0.857 |\n| 4| 0.15 | 0.827|\n| 5 | 0.224 | 0.835 |\n| 6 | 0.187 | 0.776 |\n| 7 | 0.198 | 0.762 |\n| 8 | 0.2 | 0.745 |\n\nWe find that additional edits improve EER at the expense of decreasing semantic similarity; this is only true up to a certain point, after which the SBERT decreases without consistent improvement in EER, demonstrating the importance of this component in $q_{\\theta}$. Multiple iterations are similarly useful for protein synthesis.\n\nWe are happy to discuss additional factors should there be further concerns. For example, the paper as it stands focuses on a basic autoregressive architecture for $q_{\\theta}$. However, it is likely that our results could be improved, for example by initializing from larger pre-trained models for $q_{\\theta}$ or employing different training strategies.\n\nRegarding comparisons to further baselines, we agree this would strengthen the work. To our knowledge, our comparisons include SOTA extrapolative baselines for the challenging extrapolation tasks we consider, but of course there are many other tasks to consider, such as the design of cell-type-specific promoters for gene delivery considered in [1]. However, the complex approach described in [1] involves a very application-specific pipeline involving 5 different steps which would be hard to adapt to our more general setting. On the other hand, our approach is largely application-agnostic provided a suitable pre-trained LM is available. \n\nRegarding comparisons to RL-based methods such as [1], our approach may be viewed as performing off-policy reinforcement learning, even though we do not explicitly cast it that way (see e.g. https://arxiv.org/pdf/2106.02039). We considered using a more overt framing of the work as RL, but felt the additional notational baggage made it harder to understand the main idea. We view our contribution as a first effort to adapt off-policy RL to extrapolation settings by bridging RL and MCMC. More discussion of this point will be included in the paper.", "claims_and_evidence": "Most claims in the submission are supported by convincing evidence. However, there are several gaps in the proposed method and experiments to support the novelty and performance of this paper. For more comments, please refer to details in \"Methods and Evaluation Criteria\" and \"Experimental Designs or Analyses\" sections.", "methods_and_evaluation_criteria": "Most parts of the proposed methods and evaluation make some sense. However, there remain several issues:\n\n- A theoretical perspective of why $q_{\\theta}$ leads to more efficient sampling and what makes an optimal $q_{\\theta}$ for the MCMC algorithm is missing.\n- Although the proposed method effectively reduce the sampling iterations, the MCMC sampling to generate data for the training process of the model should also be considered, and an ablation on how the number of iterations for data generation in model training affect the model performance would be helpful.", "theoretical_claims": "There are no theoretical claims in this paper.", "experimental_designs_or_analyses": "- It would be helpful to add an ablation of the model performance with different $q_{\\theta}$ and compare to demonstrate the key components that lead to the best $q_{\\theta}$.\n- The paper does not compare to model based optimization methods in reinforcement learning, for example,, [1].\n\n[1] Designing Cell-Type-Specific Promoter Sequences Using Conservative Model-Based Optimization. NeurIPS 2024.", "relation_to_broader_scientific_literature": "The paper is related to guided sampling and optimization methods, as well as applications in both natural language and biological domains.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The paper proposes an interesting method that utilizes a learned policy to replace stochastic exploration approaches. More theoretical perspectives on sampling efficiency and discussions on the method's extrapolation capability would strengthen the paper.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "", "extra_scores": {}}, {"review_id": "IvZUzNFiN1", "reviewer": "Reviewer_6dee", "summary": "The authors propose a method to efficiently perform extrapolative generation, optimizing a property of interest.\nSpecifically, they train an autoregressive model to predict new sequences or states that enhance the desired property, using training samples obtained from MCMC. They evaluate their approach across three domains: sentiment optimization, protein engineering, and text anonymization.\nTo investigate whether the autoregressive model benefits from intermediate states, the authors conduct an ablation study on training episode design. They compare single-step training episodes with multi-step episodes, exploring different selection strategies — uniformly sampled states versus transitions that yield high relative improvement.\n\n## Update after rebuttal\nIn the rebuttal, my questions have been adequately addressed. I still think this work as an interesting and valuable contribution to the conference, and I find this opinion to be somewhat supported by the other reviewers. Therefore, I will maintain my original score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We appreciate the detailed and thoughtful feedback, and aim to address remaining questions and concerns here. \n\n> “While intermediate state generation improves performance in the protein domain, its impact on anonymization and sentiment tasks remains unclear.”\n\nIn the case of our sentiment task, there is no clear benefit to adding states: the task is sufficiently simple that a single edit is the most effective way to extrapolate, hence why we consider first/best to be the best method in this case. In more complex tasks we find it to be more important to have additional steps as there can be a generalization benefit, as in protein synthesis and anonymization. Additional edits consistently decrease semantic similarity for anonymization but improve EER up to a certain point, after which the SBERT decreases without consistent improvement in EER. We select our number of states based on this point.\n\n\n| Episode length | EER | SBERT|\n| ------------- | :-------------: |  :-------------: |\n|2 (first/best)| 0.132 | 0.923 |\n| 3 | 0.161 | 0.857 |\n| 4| 0.15 | 0.827|\n| 5 | 0.224 | 0.835 |\n| 6 | 0.187 | 0.776 |\n| 7 | 0.198 | 0.762 |\n| 8 | 0.2 | 0.745 |\n\n\n\n\n> Missing information on computational burden: While this may be a minor issue, it would have been helpful to include more details on the additional computational cost associated with model training and inference.\n\nThanks for the suggestion! Indeed, the computational burden reported in our tables is purely inference-time computation. We recognize that our model has the additional computational burden of generating training data and fine-tuning a model on that data. However, this is a single fixed cost at training time. $q_{\\theta}$ takes seconds for each inference example where MCMC takes ten minutes or longer for a single batch at inference time. The number of iterations in our tables are meant to provide an understanding of the scale of the ongoing computational cost at inference time, and does not account for the fixed (“offline”) training cost. We will be sure to include more details on the offline training costs in our revisions.", "claims_and_evidence": "Yes, the claims made are well supported by convincing evidence.\n\nMain claim/conclusion:\n> We find that the autoregressive model can extrapolate as well or better than MCMC, but with the additional benefit of significantly higher sample efficiency.\n\nThe main conclusion is well supported by Table 1, Table 2, and Table 3. This is especially convincing due to the fact that the authors' approach has been evaluated on three different domains.", "methods_and_evaluation_criteria": "Experiments have been performed for the three different domains mentioned above. Experimental setups seem reasonable.", "theoretical_claims": "--", "experimental_designs_or_analyses": "* The experiments comparing the proposed approach to MCMC appear well-motivated and relevant.\n* Autoregressive refinement: The results in this section seem a bit inconclusive. While intermediate state generation improves performance in the protein domain, its impact on anonymization and sentiment tasks remains unclear. Could the authors provide an intuition — or ideally, a deeper analysis — on when and why autoregressive refinement is beneficial in different scenarios? Additionally, when constructing training episodes, how should the hyperparameter controlling the number of included states be set or adjusted for different tasks?", "relation_to_broader_scientific_literature": "The authors' work builds on [1]. Because of their relevant experimental setup and their good results, I think the authors provide a significant contribution to the community.\n\n[1] Padmakumar, Vishakh, et al. \"Extrapolative controlled sequence generation via iterative refinement.\" International Conference on Machine Learning. PMLR, 2023.", "essential_references_not_discussed": "--", "other_strengths_and_weaknesses": "### Other Strengths:\n- Clarity: The paper is very-well written with a clear scope. Figure 1 and the toy example help ease the reader into the paper. The authors provide their rationale whenever needed to understand their assumptions and hypotheses.\n\n### Other Weaknesses:\n- Missing information on computational burden: While this may be a minor issue, it would have been helpful to include more details on the additional computational cost associated with model training and inference. If negligible, the reported differences in the needed iterations indeed should be a strong argument for the efficiency of the proposed method.", "other_comments_or_suggestions": "--", "questions_for_authors": "See above.", "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": "", "extra_scores": {}}, {"review_id": "uEZ6xkbdb7", "reviewer": "Reviewer_qZh3", "summary": "The authors consider the task of maximizing a function s(X), like sentiment or predicted protein activity, in a discrete space, which is a challenging task. Te baseline they consider is (annealed?) MCMC with proposals from a pre-trained model. Instead, they suggest running MCMC for some amount of time and then training a language model on these chains so that it can learn the features of sequences that tend to lower s(X).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your careful and detailed review of our paper. We are grateful for the feedback, and address your main points below:\n\n> “In section 2, you suggest your model can be useful even if you only have an approximation of s. Could you demonstrate this?”\n\nIn our extrapolation settings (sentiment and protein design), we intentionally train imperfect approximations of the true property we are attempting to optimize; the extrapolation setting assumes that we do not have data outside a certain range, and that we can train a scorer to approximate the oracle, but that that scorer will not be reliable outside of the range of values it was trained on; therefore reviews outside the training region are OOD for our guide, which may return unreliable predictions in this extrapolation range (see e.g. https://arxiv.org/abs/2006.10108).  Specifically, the sentiment scorer is trained on reviews between 2 and 4 stars, and the protein scorer is trained with values above -5, despite the objective being to generate reviews or proteins beyond that range . We therefore believe that our results demonstrate that our model is useful even with an imperfect approximation of s. \n\n>Could you compare to this paper that also trains on improving pairs of data?\n\nThank you for the reference; this is a very interesting approach that we will include in our discussion. The key difference with our work is that PropEn performs optimization in latent space and subsequently decodes from that latent space. However, latent space models such as VAE's are well-known to suffer from posterior collapse when using highly flexible generative models such as the large language models we use in our experiments. To sidestep this issue, we perform both search (MCMC) and optimization ($q_{\\theta}$) in discrete space.\nAs such, we compare with other pair-learning based methods that operate in discrete space. Our primary baseline is ICE, which also trains on improving pairs of data and is state-of-the-art for the tasks we consider. Additionally, PropEn focuses on single-property enhancement, while our tasks as implemented require multi-attribute optimization: protein stability and similarity to original protein for protein engineering, fluency and sentiment for the sentiment task, and EER and semantic similarity for anonymization.\n\n>Why don't you compare with other discrete optimization methods? Ex. https://openreview.net/forum?id=ZMP0Bki9aK\n\nWhile in principle this approach is complementary to ours, since we could benefit from these same proposals to improve the efficiency of our MCMC step, in practice it would not be straightforward to apply this approach to the language modeling applications we consider here, due to the size of the vocabulary and sequence lengths. Generally speaking, we view improvements to MH for language models as a promising area for future work, which is complementary to our direction here about learning efficient extrapolation models $q_{\\theta}$ on the basis of the Markov chains from MH. We expect that more efficient exploration will lead to a more efficient exploration step and a more effective $q_{\\theta}$ for the same amount of compute.\n\n> Why did you not anneal in your MCMC?\n\nWe employ MCMC to explore sequence transformations that improve the objective, and then use our learned $q_{\\theta}$ to greedily maximize this objective. While annealing MCMC could help it attain a better local optima, this could actually be counterproductive to the goal of exploring productive sequence-to-sequence transformations. Compared to other works such as https://openreview.net/forum?id=ZMP0Bki9aK above, we seek to efficiently optimize using $q_\\theta$ in as few steps as possible, while annealing would require a much larger number of steps.\n\n> “One could spend the compute training $q_{\\theta}$ on running more MCMC.”\n\nWhile it is true that the time spent training $q_{\\theta}$ could be used to run MCMC for longer, the training cost is a fixed cost that occurs offline, while running further iterations of MCMC is an online cost which would add more computational expense for each inference example. We emphasize that once $q_{\\theta}$ is trained, it can be applied to new instances without further MCMC steps. Training $q_{\\theta}$ allows for rapid inference on unseen examples, while MCMC requires an expensive sampling process for each inference example.", "claims_and_evidence": "see summary.", "methods_and_evaluation_criteria": "see summary.", "theoretical_claims": "see summary.", "experimental_designs_or_analyses": "see summary.", "relation_to_broader_scientific_literature": "See Summary.", "essential_references_not_discussed": "None I know of.", "other_strengths_and_weaknesses": "**Strengths:**\n\n* I really appreciated the toy example in section 2.\n\n**Weaknesses / questions:**\n\n* Could you compare to this paper that also trains on improving pairs of data? https://arxiv.org/pdf/2405.18075\n\n* Why did you not anneal in your MCMC?\n\n* Why don't you compare with other discrete optimization methods? Ex. https://openreview.net/forum?id=ZMP0Bki9aK\n\n* One could spend the compute training q_\\theta on running more MCMC. Is this better? Could you describe how you accounted for this in your experiments (it seems to me you did not)?\n\n* In section 2, you suggest your model can be useful even if you only have an approximation of s. Could you demonstrate this?Typically in these cases, especially protein design, one performs iterative design, iteratively making measurements and improving the approximation of s. Would your method work well here? Can you demonstrate that?", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers agree with the acceptance. It has a solid contribtion.
Decision: Accept (poster)