Structured Voronoi Sampling
Authors: Afra Amini
Li Du
Ryan Cotterell
Venue: NeurIPS 2023 poster (2023)
Keywords: Natural Language Processing
Text Generation
Controlled Generation
MCMC
HMC
Langevin Dynamics

Abstract: Gradient-based sampling algorithms have demonstrated their effectiveness in text generation, especially in the context of controlled text generation. However, there exists a lack of theoretically grounded and principled approaches for this task. In this paper, we take an important step toward building a principled approach for sampling from language models with gradient-based methods. We use discrete distributions given by language models to define densities and develop an algorithm based on Hamiltonian Monte Carlo to sample from them. We name our gradient-based technique Structured Voronoi Sampling (SVS). In an experimental setup where the reference distribution is known, we show that the empirical distribution of SVS samples is closer to the reference distribution compared to alternative sampling schemes. Furthermore, in a controlled generation task, SVS is able to generate fluent and diverse samples while following the control targets significantly better than other methods.

Structured Voronoi Sampling
Afra Amini'
Li Du
Ryan Cotterell'
'ETH Zürich amini,
Johns Hopkins University ryan. cotterell @innf ethz.ch leoduêcs. j.u, edu
Abstract
Gradient-basce sampling algorithms have demonstrated their effectiveness in text generation, especially in the context of controlled text generation. However, there exists a lack of theoretically grounded and principled approaches for this task. In this paper, take important step toward building principled approach for sampling from language models with gradient-basee methods. We use discrete distributions given by language models to define densities and develop algorithm based on Hamiltonian Monte Carlo to sample from them. We name our maseed technique Structured Voronoi Sampling (SVS). In experimental setup where the reference distribution is known, we show that the empirical distribution of SVS samples is closer the reference distribution compared alternative sampling schemes. Furthermore. in controlled generation task, sVs is able to generate fluent and diverse samples while following the control targets significantly better than other methods.
Introduction
Gradient-based sampling algorithms such as Hamiltonian Monte Carlo [HMC; [32 and Langevin dynamics [46] are widely used in Bayesian inference due to their efficiency in drawing samples from high-dimensional space [4]. Such algorithms construct Markov Chain that has the desired distribution as its stationary distribution and use the gradient information of this distribution to efficiently navigate the state space. Additionally, gradient-based sampling schemes have recently been deployed in computer vision to generate high-quality images from state-of-the-ar models [13] 43)
and are popular choice for tasks such image synthesis and image-to-image translation
40
In natural language processing, there have been several attempts to apply gradient-based sampling techniques sampling text from neural language models [2 23 38 The motivation behind this approach to text generation is to sample from emergy-based probabilistic models, where the normaliza- tion factor is not tractable. One such case is in controlled text generation, where energy functions usually defined as a linear combination of LM probabilities and the probability of satisfying a set of
predefined constraints 21 23 38 In contrast computer vision, however, applying radient-based
sampling schemes to text generation is nuanced as text, in contrast to images, is discrete.
Upon closer inspection, none of the proposed algorithms actually defines a valid Markov Chain Monte Carlo [MCMC: 12] 29) scheme that will draw samples from the model in the limit. For instance, Qin al. 13 relax the language model from distribution over strings distribution over logits. While the relaxation does transform the language model into continuous distribution, introduces bias. Kumar al. [MUCoLA: 21 take different approach. They derive constrained gradient- based
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

sampler where the constraint is enforced through projection. However, the projection invalidates the MCMC procedures, leading to an algorithm without guarantees
We derive principled Hamiltonian Monte Carlo scheme for generating text from language models, which we call structured Voronoi sampler. Our scheme consists of two steps. First, we give a recipe for encoding discrete distributions as densities over R2; we term the resulting encoding Voronoi measures Second, we derive a refractive Hamiltonian Monte Carlo algorithm [30] for sampling from an arbitrary Voronoi measure. In our thcoretical analysis, show that, despite the presence of discontinuities, we are able to give proof that our sampler satisfies the detailed balance condition and, thus, is correct MCMC scheme.
To empirically evaluate the performance of structured Voronoi sampling, we begin by applying it to toy example where the exact reference probability distribution is known. We compare the empirical distribution of drawn samples with the reference distribution and show Voromoi sampler's distribution is closer to the reference distribution than MUCOLA or unconstrained HMC. Furthermore, we use our sampling scheme for controlled generation, where the goal is to use GPT-2 to generate restaurant reviews for target type of food, e.g.. Italian, Fast food, Japanese, and separately to generate text with a positive sentiment. We find that structured Voronoi sampling outperforms FUDGE [88,, MUCOLA, and Langevin Dynamics algorithms in terms of adhering to the control target. Additionally, the samples generated by structured Voronoi sampling are comparably fluent and diverse to those produced by the other methods.
2 Language Models
Let Σ be an alphabet, a finite, non-empty set. By E' - we denote the Kleene closure of > probability distribution over D' is called language model (LM). The elements of may be characters, subword pieces, words; the choice lies with the modeler. Language models can be factored autoregressively by means of the chain rule of probability, i.e., for any string W1 Wy E Σ", we can write
p(w) = p(BOS) w) II p(wn wen):
where FOS & Σ is distinguished end-of-sequenee token and Wen is the prefix of length (n 1) of the string w. We define Σ dh U [EOS}, and require the conditional distributions p(- wen) to be defined over While all language models can factored autoregressively. not all conditionals p(- w.en) can be assembled into a language model. In some cases, probability mass must be placed on infinite sequences (6). In this work, we assume working with tight language models, i.c., that they indeed define valid probability distributions over Σ*
2.1 Language Modeling with Embeddings
Most neural language models make of embeddings. Moreover, in most language models, the weights are shared between the language model head and the embedding layer. Such an embedding-bars based language model is defined as follows
exp Vw, enc (w)))
p(
W
kn)
def
Emer exp V.. eno(w
where V E IRd is the embedding of u and enc Σ - R a real-valued encoding of the context. Notably, the context embedding enc(w E Rd is obtained by inputting the context w wen into the language model, converting to embeddings Vw.., passing it through neural network layers, and extracting the encoding from the model at position
1.
'In fact, similar projection step is often applied in computer vision applications, which motivated Lou and Ermon 26 to develop a principled approach that avoids projection.
"e call the measures structured Voronoi samplers when the state face is larger and factored.
We define 2 def (e).

---

Interestingly, one lift embedding-based language model be distribution the set of base embeddings: B = {v E 2}. Specifically,
associate sequence of embeddings = [Vi...., V to any string w = w1 W.. Substituting each w with the corresponding V we can rewrite Eq.
p (V) p(vos
VV II
p(vn Ven).
This transformation encodes language model distribution over real-valued vectors. However, p(V) only places a positive probability on a countable set, and is zero everywhere else.
2.2 Controlled Language Modeling with Embeddings
In controlled generation task, we are interested in a subset of strings w that have a target property Therefore, we want to model and sample from conditional distribution p(w (), e.g., sample sentence given topic. Following Bayes' rule, one can write p(w () p(l w)) p(w). Previous papers model p(L w) with an embedding-augmentt
classifier. Such a classifier receives embeddings
V associated with and predicts the probability of the target I. Notably, if the classifier and the LM share the same base embeddings B, the controlled LM can also be lifted as a distribution over the base embeddings
1
p(V (t) = Z p(t p P()),
where Z, Ev p(t V) (V) is an intractable normalization factor, that sums over the embeddings of all possible strings Identically to p( p(V). p(V t) only places positive probability on countable set.
3 Voronoi Measures
In this section, we demonstrate how encode embedding-basee language model density that places positive probability on a set with a measure greater than zero. Such encoding allows us derive a principled gradient-based sampling approach to generate samples in $6 We start with some definitions.
Definition 1. An auggmente probability distribution over the first M positive integers [M] is an array p ..,,..., ,,.. such that pm. 2 0 and >m= Pm = 1 where we assume that there vealevalued embedding JM C Rd associated with each E [M].
Embedding- augmeett distributions can be viewed as densities over Rd using the following simple encoding
Pms if Vm 0.
p(x)
(5)
otherwise.
Eq. (5) however, yields a density that is 0 almost everywhere (with respect to the standard Lebesgue measure) and its gradient with respect to Pm is also zero almost everywhere. Thus, Eq. (5) is not amenable gradient- -ased sampling, and to derive a meaningful gradient-based sampling we require a more nuanced encoding.
To provide such an encoding, we introduce the Voronoi measure. Given an embedding--agmeente 1M distribution p [pi..... : PMJ with embeddings [ and compact set K. ER that covers the embeddings, i.c., {vm LM C. K. we define the Voronoi cell for the m item with respect to the compact set K. as follows
C. = XXX vm ||x
Ven Vm' o m).
(6)
Now, using the definition of Voronoi cell C'm given in Eq. (6). we can define density that is not zero almost everywhere as follows. The strategy is to spread out the probability mass pm over the entirety of the set Cm. To do so, we assume access set of base measures { J.d J that give us a reference for how to judge the probability mass in each C.,. We make this encoding formal in the following definition.
WWe will discuss in $ 5.2 how gradient-basee sampling can help to sample from this distribution without the need to compute Zt.

---

Definition 2. Let p p be an embeeddingauugnenteed distribution with embeddings JM C. IR, and let K. be a compact set such that [Vm]m=) be set of base measures over R that are absolutely continuous with respect to the standard Lebesgue measure À over R&, i.e. pm < Define the (K, 11) -Vroooi measure as follows
) K. Furthermore, let }
(n) dpm (x), E
(v(x) del
Mm (m)) dA
0,
otherwise
where we define projection
m" (x) argmin ||x - Vnall me(M]
(8)
with ties broken arbitrurily
In the following proposition, we make precise the sense in which a Voronoi measure encodes the original embedding- augmented distribution.
[rrll 2at
reflect
Let p [pi..... .PM) be an embedding-aute augmented distribution with embed- dings {vm Immi C IR", and let pv be the cor- responding Voronoi measure Eq. 7 Then, (Cm) Pm where Cm is defined in Eq. 1 See App. [.r proof.
Proposition 1.
p(v2) 0.02
0.56 p(v,)
C2
refract
G
0.8
|r.1 >
0.4
p(v.) = 0.11
p(v,) = 0.34
C2
Example 1. Suppose p = (p........ is cate- gorical distribution, and there are embeddings in ?R associated with each ps, namely:
X
Figure 1: The example shows how Voronoi Sam- pling navigates through the space to sample one embedding in R22 Each Voronoi is annotated with the probability its center, i.e., Voronoi measure of the cell.
[1,1]. V2 = [_-1_ll.v = [-.-
= 2- probability
[1.1]. Given the K. [-2,] and the distribution p. Eq. (7) defines Voronoi measure over this space, where the Voronoi
cells are visualized in Fig. 7
We will discuss in $6 how Voronoi sampling navigates this space.
3.1 Structured Voronoi Measures
To encode language models as densities more naturally, we introduce a generalization the Voronoi measure, which we term a structured Voronoi measure. Now, rather than distribution over M elements, we assume to have sequence length N. Each token in the sequence takes value in
[M]. Let m = [m.....,ma, m,x] E [M] We define structured Voronoi cell as Cm = II C.... where] II denotes the Cartesian product and we define the individual Voronoi cell as
Cm. = xx K., Vm, 1 < | Vm
Vm' * mn
(9)
Proposition Let p be a measure on Rd. Then, we have the product measure space as p(Cmm
II p(Cm..). See App. C.2 for proof.
Definition 3. Let p be an enbeeddng-augmented augmented distribution over [M] For m E [M]N we denote m 's probability as Pms and m embedding as Vn E xd, Let K. be a compact set that covers the embeddings V m and let & X be base measure absolutely continuous with respect to the Lebesgue measure X. We define the (K. p))sstuuctured Voronoi measure as follows
Pm) dp (x),
E
(x))
(m
(10)
0,
otherwise
where we define the structured projection
N V m. 112.
m
(x)
argmin me
Xn
(11)
M
n=1 'The of that induces tie is set of measure under the Lebesgue measure.

---

4 Application to Text Generation
Def. [ gives us the flexibility to use any probability distribution over sequences of embeddings define a structured Voronoi measure. For example, one can substitute (x) with an embedding-augmmented LM, i.e. Eq. (3). to encode a language model as a structured Voronoi measure. Another example is encode controlled LM as structured Voronoi measure by substituting (x) with Eq.
Base Measure. We have explained how to encode our desired distribution as a structured Voronoi measure. However, in order to actually implement gradient-based sampler, we need to specify the base probability measures [PmJm= Given an umbedding-auggmenter probability p(V) it natural to follow the gradient of log p( with respect to the word embedding, i.e., gm Vy log p( V).
Thus, we want follow direction similar to gm. one natural choice for ş is Gaussian measure centered at the gradient gm restricted to Voronoi cell C. [ we define:
((A) -
J Js- (((m) A-Cm
exp (-2lBm xx13 dA(x).
(12)
The normalizer ensures the measure is a probability measure. Furthermore, we have that jts Radon-Noe Nikkodym derivative with respect the Lebesgue measure is given by
dp
((C exp (-ållgm - (2), x C..
def
(13)
0,
otherwise
Eq. 13
should be recognizable as the standard Gaussian density, albeit one that is truncated to the
Voronoi cell Cr 277
Proposition 3. Eq.
13
absolutely continuous with respect to the Lebesgue measure See
App. C33 for proof.
Proposition 4. The gradient of the log of the Voronoi measure pv is given by
8m x, undefined, 0,
if int(Cm)) if d0m otherwise
Vx Po
(14)
where the first two blocks in the case statement apply if there exists some such that E int (Cm) or x E 00m- See App. C.4 for proof.
Gradient-Based Sampling
In this section, we first review gradient-based sampling methods, namely IMC and Langevin dynamics. Then we discuss how they have been used in previous papers on text generation. This will set the stage for algorithm in $o which based on HMC.
5.1 Hamiltonian Monte Carlo
The goal of HMC, originally proposed by Duane et al. 77. is to design a better proposal distribution in the standard Setropolis-Hasting MCMC by taking advantage of the gradient information in principled way. Concretely, to sample from a given distribution p(x) where x E Rd, IMC treats the coordinates of the particles in some fictitious physical system. It then introduces auxiliary momentum variable E Ie associated with each coordinate and defines a Hamiltonian function (x, Here, the Hamiltonian H has the intuitive physical interpretation of the total energy of some conservative system, and. in classical mechanics, decomposes into the potential energy U (xx) and the kinetic energy (r), i.c.. rx U (x) + K(r). This formulation convenient in part because (x.x) in energy-based models, then
we define the joint distribution p(x, r)
p(x, r) x U(x) ((r).
(15)
'Please refer to App. B for discussion the reasoning behind choosing the Gaussian measure.
5

---

which means so that x has the marginal of the target distribution. It is also common practice to set (r) = r' 1/2 so that the momentum variable has Gaussian distribution. Here, M E gddd is called the mass matrix and commonly set identity
treat and independent variables. Naturally, we can let (x) = - (x)
The Hamiltonian determines the equations of motion in physical system, given by the Hamiltonian equations, which is also known as Hamiltonian dynamics,
Algorithm 1 HMC
Input: x": current sample, U: potential energy function, E: step size, L: number of leapfrog steps Output: next sample: xf xf+1
dx dt dr
OH dr
OH 0x
(16)
de
We now ready to give high-level descrip-
1: r ~ 1O.
tion of how HMC generates a single sample (see Algorithm D: First sample a momentum from
2: H' Uxx') + K(r)
3: x x t
a Gaussian (line I. then evolve the system us- ing the Hamiltonian equations Eq. (T6) for some predetermined amount of time (lines 4 to 7). and finally accept the new state with the Metropolis- Hastings acceptance criterion (lines to 13). Note that the Hamiltonian equations often admit no closed-forn solution in practice, and hence one needs to use numerical integrators for ap- proximation. In particular, the leapfrog inte- grator, corresponding to lines 5 to almost
4: for I = L..... L:
5:
r +tt r ---VUG -UU(((+))) (1)
6:
xt+1 - x +er
7:
r r- (VUU(x+)
8: He+1 (- (xx(+11 (((r)
9: AH H H
10: if ((, 1) <<<
<e e-AH:
11: return x+1
12: else
13: return x 4- x!
always used in HMC.
Ingeniously designed by Duane et al. 77). the efficiency of this elegant procedure is a result of several favorable properties of Hamiltonian mechanies-namely volume preservation, reversibility, and conservation. Upon exact simulation of the Hamiltonian dynamics, these properties will lead to the acceptance probability of one, i.e., every proposed move will be accepted. In App- [ will give intuition about these properties. Since the method developed later in $6 will subsume HMC as special case, we delay the proof of correctness until then.
Langevin Dynamics. Langevin dynamics is simplification of HMC, where only one leapfrog step is performed. Furthermore, what is usually referred to as Langevin dynamics is in fact the uncorrected Langevin dynamics, where the acceptance criterion is ignored, i.e., every proposed sample is accepted; see Algorithm 2] While uncorrected Langevin dynamics is guaranteed to converge when the energy function is smooth [31] $5.3), there is such guarantee with the presence of discontinuity in the energy function. Nevertheless, due to its simplicity, Langevin dynamics is the only gradient-based sampling method that has been applied for text generation applications.
5.2 Applications to Controlled Generation
One of the primary advantages of using gradient-based based techniques for controlled generation is that it provides a means to sample from the conditional distribution Eq. (4) without having to calculate the normalization factor Z,. For example in HMC algorithm (Algorithm [T). all we need to calculate regarding the potential energy U(V) = - log p( V t) is two terms: (I) the gradient of U with respect to V: VU, and (2) the difference between the potential energy of two points AU for the Metropolis criterion. Fortunately, both terms are independent of Z,, and we can sample from the conditional distribution without the need to compute Zt-
MUCOLA. As defined in Eq. P(V t)) is 1dd-vlledd so it is tempting to apply gradient- based sampling technique to sample from it. And, indeed, Kumar et al. (21) have proposed such scheme based on Langevin dynamics. They define the potential energy of the embeddings as
"There exist sophisticated methods [1] to tune the mass matrix, but given that LM gradients are expensive compute, will not attempt such methods in this paper.

---

U(V) def
VV 1) and apply Langevin dynamics out of the box; see Algorithm However, since UVV is zero for any vector other than vectors in B (defined in $2.1 they modify the sampling process and project the proposed sample to the base embeddings set each step of the sampling process (line of the algorithm). The added projection step, however, is neither volume-preserrvin nor time-reversible. Hence, this sampling procedure does not sample from the intended distribution and is not a valid MCMC algorithm.
COLD and other schemes. Alternative approaches have been proposed in the literature to reformu- late a language model as potential energy over the logit [COLD; (38 or simplex space [4. 20 How- ever, these formulations not suitable for principled gradient-base based sampling. COLD only employs a hcuristic energy function to select among the candidate generations obtained via top-k sampling, and the simplex-based approach requires an extra constraint ensure the sample stays on the simplex.
6 Structured Voronoi Sampling
Given structured Voronoi measure PV, one can apply HMC sample from it. In this section, we take one step further and propose a variation of HMC that is more suitable to sample from pv- Importantly, Pv contains discontinuities whereas the generic leapfrog integrator does not account for such sudden jumps in the potential function. In other words, even if the leapfrog integrator itself is volume preserving and time-reversible, the sudden jumps in potential can lead to large deviations in the Hamiltonian value, causing a low acceptance rate. We therefore would like to find an alternative to leapfrog in such situations.
Physical Analogy. classical mechanics, discontinuity with smooth boundary in the potential function occurs naturally, c.g., in collision dynamics slab magnetic field, and is referred to as potential barrier (or interface). Upon encountering a potential barrier, a particle will either be reflected from or transmitted through the barrier surface, depending to overcome the potential jump (e.g.. [8, $4.6.2 Such behavior is similar to reflection reftrictnorrroiionn phenomenon in optics. The key insight here is that, in both cases, the Hamiltonian is conserved.
whether it has enough kinetic energy
Reflection and Refraction. To give a precise mechanical description of this behavior, suppose a particle encounters potential barrier at position x with momentum momentum as T + where r is normal to the barrier and rij parallel to Let AU be the signed potential energy difference between the two sides of the barrier. If ||r_| > 2AU, then the particle has enough kinetic energy to overcome the barrier, and its momentum's 's normal component will instantancously become r'1 / [ril 2AU |[r_l after being transmitted through the barrier (refraction). Otherwise, if ||r < 2AU, the particle will be reflected from the barrier and the normal component will instantaneously become r'1 -r We show in App. E. that Hamiltonian is conserved in either case. The reflect-refract process is summarized in Algorithm 5
We can decompose
6.1 A Sampling Algorithm
Noting that the discontinuity surfaces of pv are all piecewise smooth, we can build on the above and develop a sampling algorithm for pv to handle discontinuity in a principled and effective way. In fact, we only need to make one change to the generic IICC, which is updates (x, r) according to the mechanical description given above. Concretely, we need to replace step 2 in the HMC outline in I..I; When single step of leapfrog encounters no discontinuity, point as in HMC; however, when there is discontinuity, a full leapfrog step is taken, we need to proceed by repeatedly computing where the discontinuity is encountered, taking smaller step up to the discontinuity and refraating-reflecting based on the potential energy difference. This process is continued until we have exhausted the step size. Since effracting-reflectiin Hamiltonian (App. I..I) this process yields a better acceptance rate in the presence of a discontinuity, See Algorithm 4 for the details of this sampling procedure, and App. F. for how efficiently find discontinuities. We will supply proof of correctness in App. E.2
may advance to the next
conserves
A note on calculating the base measure. To adjust the momentum, one needs to compute AU, which implies computing the difference between two base measures, as defined in Eq. {2). How- ever, computing such an integral in a high diseeiimeniional space is not practical. Therefore, make an
7

---

Sampling Method
MuCol
Langota
JS Divergence
Sampling
Matata
Voranoi Sampling
Axcedd
Perplexity
Figure 3: Perplexity of 100 samples taken with different gradient- algorithms, compared to 1000 samples taken with the ancestral sampling (in green). While LANGEVIN, SVS, and MUCOLA are com- parably close to the ancestral samples' dis- tribution, SVS models the tail of the distri- bution better.
0.25
0.5
0.75
1.5
Temperature
Reference Distribation
Figure 2: Left: JS divergence between the refer- probability and empirical probability distribu- tion. Voronoi Sampling clearly outperforms others in low temperatures. Right: reference probability distribution annealed with 3 temperatures: 0.25 (peaked), and 2 (close to uniform).
assumption that the base measures of Voronoi cells are equal, and thus do not have effect AU. However, such an assumption might not hold. See App. A for limitations.
Experiments
We empirically assess the performance of Voronoi sampling in a series of experiments. In each experiment, we perform a grid search to find the best set of hyperparameters, these experimental details can be found in App. H Our open-source implementation will be available upon publication.
7.1 Toy Example
We first apply our Voronoi sampling method on the toy example discussed earlier in Example [ where the reference probability distribution is tractable and known p(x). The potential energy is then set (xx
methood
log pv (x). Importantly, the toy experiment is intentionally designed such that the base measure of all of the Voronoi cells is equal, therefore, we can safely ignore calculating the base measure and arrive at exact sampling methods.
We compare Voronoi sampling to MUCOLA and HMC. To make a fair comparison, we add the Metropolis criterior to the MUCOLA algorithm and only do one leapfrog step in all algorithms. Furthermore, to see the effect of the reference distribution on the performance of the sampling algorithm, we anneal this distribution with 6 temperatures, where the lower temperatures lead to peaky distributions and the higher temperatures to uniform-like distributions.
We take 200 samples after 500 burn-in iterations, and compare the empirical distributions of samples to the reference by measuring the -haennon (JS) divergence between the two. As results in Fig. show, the JS divergence between the reference distribution and the empirical distribution of Voronoi samples is the smallest. The difference between the methods is more pronounced at lower temperatures, the change in potential energy greater, resulting in errors in the leapfrog integrator. In App. [p. we provide more empirical support that Voronoi sampling converges faster to the reference distribution, especially when we increase the dimensionality of the sampling space.
7.2 Sampling from Language Models
Next, we apply our method to sample from a language model. The underlying L.M is finetuned GPT-1
E2E dataset (4)) see App. G for dataset statistics. As opposed to the previous
*Note that in the case of the toy experiment, embedding. To highlight this point, use Voronoi sampling instead structured Voronoi sampling refer our algorithm in this section.
not sampling sequence of text, but rather single
We accept transitioning from x to x+1 with probability "1" -1++1
We use gpt2 checkpoint from the Huggingface library 47

---

experiment, the reference distribution of the LM is not tractable. Therefore, we use the empirical distribution of ancestral samples as an unbiased estimate of the reference distribution. Note that ancestral sampling incrementally draws samples from a language model, where at each step of the generation a token Wx is sampled with the probability given by the LM: p(w,, wen). Therefore, the process can give unbiased estimates of the reference distribution.
We follow $4 to define a structured Voronoi measure pv using the LM probability. We then implement SVS, where the potential energy is set to loog pv. To empirically measure the benefit of reflection innectioon-efraattinn step in svs, we compare it to applying Langevin dynamics directly to pv. We implement MUCOLA as baseline, which writes the potential energy using an embedding-augmmetee LM, i.e., Eq. (3)
We show the distribution of samples' perplexity in Fig. 3 The green trace is the empirical distribution of 1000 ancestral samples. While all the sampling methods result in distributions comparably close to ancestral samples' distribution, observe that SVS manages to model the tail of the distribution better. On the other hand, MUCOLA and LANGEVIN tend to take samples from the mode of the distribution more often.
7.3 Controlled Generation
Finally, we apply our structured Voronoi sampling 2 controlled generation task. The goal of the first task is to generate restaurant reviews for target food type i, e.g. Italian, Fast food, Japanese, etc. The goal of the second task is to control the sentiment of the generations to enforce positive sentiment. We train classifiers to predict the target t (food type or positive sentiment) from the input sequence p(t w)
11
We implement two baselines:
FUDGE. Yang and Klein [48] offer heuristic approach to sample from the conditional distribution. They incrementally sample tokens under the language model. At each sampling step, they adjust the probabilities given by the LM, by feeding each candidate prefix to a classifier and obtain the probability of that prefix following the control target.
MUCOLA. Kumar et al. 21 treat p(V f). Eq. 44, as a distribution Rd and apply Langevin dynamics directly to sample sequence of embeddings V. The potential energy is defined as log p(V t). When rewriting this potential energy with Bayes' rule, has been shown empirically, that adding a hyperparameter yy is helpful to keep the balance between the classifier and LMM Therefore, the final potential energy defined as:
U(V)
log log V).
(17)
As mentioned earlier, p( t) only places a positive probability on a countable set. We, therefore, use Def. 3 to define structured Voronoi measures and set the potential energy to
U (xx def
log (x) 7 log x).
(18)
We then apply Langevin dynamics and svs to sample according to this potential energy.
Evaluation. We sample 120 sentences of length 2012 and evaluate the generations on three metries:
Success: defined as the percentage of generations that adhere to the control target. To determine
whether a generation conforms to the specified target we use evaluator classifter.
Fluency: is measured by the mean and standard deviation perplexity under the language model.
Diversity: is measured by the mean number of distinct n-grams (n 1, 3) in a set of samples, normalized by the length of the sequence.
As results in Table show FUDGE tends to achieve the highest diversity, however, it fails to follow the control target. MUCOLA either generates fluent results without paying enough attention to the control, or sacrifices fluency in favor of following the control target; thus, the high variance in success rates. Both LANGEVIN and SVS result in high success rate and maintain fluency and diversity, and SVS is effective in maintaining a balance between various metrics and producing fluent sentences that adhere to control targets.
See App. H for more experimental details about classifiers.
12 sample sentences per control target.
13 Please refer Fig 7 to see visualization of the topic control results, and to Table 6 for results per target type.

---

Topic Control
Sentiment Centrol
Success(1)
PPL(U)
Dist-1(1)
Dist-((1)
Dist-3(1)
Success(1)
PPL(4)
Dist-((1)
Dist-2(1)
Dist-3(1)
GPT2
0.12 0.10
5.10 + 2.06
0.40
0.36
0.67
0.55 = 0.49
21.33 27.17
0.40
0.00
0.71
0.12
5.50
0.57
MUCOLA
0.58 0.23
33.09 1: 36.32
0.26
0.40
0.51
0.06 = 0.47
85.74 1: 152.18
0.28
0.42
0.53
LANGEVIN
0.91 + 0.12
14.26 + 2.55
0.24
0.39
0.51
0.52 0.38
26.76 14.42
0.16
0.30
0.41
13.9 2.04
0.37
0.81
Table I: Evaluation of different sampling methods on controlled generation, using three criteria:
success in following the control target (measured by the evaluator classifier), fluency (measured by perplexity), and diversity.
Related Work
Controlled Generation. Numerous approaches have been proposed to enforce controls during the infer alia). For example, weighted decoding [10] 17 scores each candidate token with weighted of its score under the language model and its adherence control targets, subsequently selecting candidates with the highest scores. FUDGE method adopts a similar scoring function, resembling Bayesian formulation for p(w t). After making simplifying assumptions and factorizing p( ww t). FUDGE samples tokens autoregressively based on their scores. More recently, line of research attempts directly sample from p(w t) by reformulating it an energy-based model and sampling from it using efficient gradient- based sampling algorithms. As discussed in $5.2 COLD reformulates p(w t) an energy-based model on the logit space and uses that to select samples with high energy from a number of candidate generations. MUCOLA offers sampling algorithm motivated by Langevin Dynamics that operates in the embedding space.
text generation process 19 24 41
Gradient-based Sampling. Our work is closely related to the line of research that makes use of
gradient information to sample from complex distributions 7 31 46). Gradient-based samplers
15 32 are shown to be highly effective when sampling from continuous distributions 33 37].
However, it is difficult problem adapt gradient-based samplers discrete settings [36 50 More
recently, several papers proposed promising gradient-bases MCMC for discrete distribution that are reversible chains (11 49]. Our work instead formulates irreversible Markov chain based
HMC. We leave it to future work to explore the utility of these recent papers on text generation.
Conclusion
In this work, propose structured Voronoi sampling, principled gradient-based sampling method for text generation. To formulate the energy function used in SVS, we define structured Voronoi measures on the embedding space and show how such measures can encode language models. In a controlled generation task. svS outperformed other sampling methods in following the control target while producing comparably fluent and diverse samples.
Broader Impacts
It has been repeatedly shown that LMs can generate harmful, toxic, or non-factual content 9 35 42
In fact, an application of the controlled generation scheme discussed this paper could to mitigate such issues. However, the same method could be used to generate misinformation, or toxic content intentionally.
Acknowledgements
We thank Tim Vieira, Tiago Pimentel, and Clara Meister for their feedback on this work. We also thank the anonymous reviewers for their constructive feedback during the review process. Afra Amini is supported by ETH AI Center doctoral fellowship.
10

---

References
[1] Luigi Ambrosio. 2008. Transport Equation and Cauchy Problem for Non-Smooth Vector Fields pages 1-41. Springer Berlin Heidelberg, Berlin, Heidelberg.
[2] V. I. Arnold. 1989. Mathematical Methods of Classical Mechanics Springer, New York, NY.
[3] Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D. Goodman. 2018. Pyro: Deep universal probabilistic programming. Journal of Machine Learning Research.
[4] Bob Carpenter, Andrew Gelman, Matthew D Hoffman, Daniel Lee, Ben Goodrich, Michael Betancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. 2017. Staan: A probabilisticc programming language Journal of statistical software, 76(1).
[5] Prafulla Dhariwal and Alexander Nichol. 2021. Diffusion models beat gans on image synthesis In Advances Neural Information Processing Systems, volume 34, pages 8780 8794. Curran Associates, Inc.
[6] Li Du, Lucas Torroba Hennigen, Tiago Pimentel. Clara Meister, Jason Eisner, and Ryan Cotterell. 2022. A mewsure--heeoreeeeee characterization tight language models.
[7] Simon Duane, A. D. Kennedy, Brian J. Pendleton, and Duncan Roweth. 1987. Hybrid Monte Carlo Physics Letters B, 195(2):216-222.
[8] Michael. Finn. 2010. Jones and Bartlett Publishers, Sudbury, MA. [link
[9] Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. 2020. RealToxicityyroopts Evaluating neural toxic degeneration in language models. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3356-3369, Online. Association for Computational Linguistics.
[10] Marjan Ghazvininejad, Xing Shi, Jay Priyadarshi, and Kevin Knight. 2017. Hafez: an interactive poetry generation system, In Proceedings of ACI. 2017, System Demonstrations, pages 43-48, Vancouver, Canada. Association for Computational Linguistics.
[11] Will Grathwohl. Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. 2021. Oops took a gradient: Scalable sampling for discrete distributions, In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3831-3841. PMLR.
[12] W. K. Hastings. 1970. Monte Carlo sampling methods using Markov chains and their applica- Biometrika, 57( (7(1):97-109
tions
[13] Jonathan Ho, Ajay Jain, and Pieter Abbeel. 2020. Denoising diffusion probabilistic models In Advances Neural Information Processing Systems, volume 33, pages 6840-6851 Curran Associates, Inc.
[14] Cong Duy Vu Hoang, Gholamreza Haffari, and Trevor Cohn. 2017. Towards decoding as continuous optimisation in neural machine translation In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 146-156, Copenhagen, Denmark. Association for Computational Linguistics.
[15] Matthew D. Hoffman and Andrew Gelman. 2014. The No-U-Turn sampler: Adaptively setting lengths in Hamiltonian Monte Carlo Journal of Machine Learning Research, 15(47):1593
1623.
[16] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration In Proceedings of the 8th International Conference on Learning Representations.

---

[17] Ari Holtzman, Jan Buys, Maxwell Forbes, Antoine Bosselut, David Golub, and Yejin Choi. 2018. Learning to write with cooperative discriminators, In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1638-1649, Melbourne, Australia. Association for Computational Linguistics.
[18] Shi Jin and Xin Wen. 2005. Hammltonian-preservviii schemes for the Liouville equation with discontinuous potentials Communications in Mathematical Sciences, 3(3):285 -315.
[19] Ben Krause, Akhilesh Deepak Gotmare, Bryan McCann, Nitish Shirish Keskar, Shafiq Joty. Richard Socher, and Nazneen Fatema Rajani. 2021. GeDi: Generative discriminator guided sequence generation In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 4929-4952, Punta Cana, Dominican Republic. Association for Computational Linguistics.
[20] Sachin Kumar, Eric Malmi, Aliaksei Severyn, and Yulia Tsvetkov. 2021. Controlled text gener ation as continuous optimization with multiple constraints In Advances in Neural Information Processing Systems.
[21] Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. 2022. Constrained sampling from language models via langevin dynamies in embedding spaces) In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguisties.
[22] Cornelius Lanczos. 1949. The Variational Principles of Mechanicy Mathematical Expositions, No. 4. University of Toronto Press, Toronto.
[23] Xiang Lisa Li, John Thickstun, Ishaan Guirajani, Percy Liang, and Tatsunori Hashimoto. 2022. Diffusion-LM improves controllable text generation Processing Systems.
In Advances in Neural Information
[24] Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula. Noah A. Smith, and Yejin Choi. 2021. DExperts: Decoding- -imeing--tmme-o controlled text generation with experts and anti- anti-experts, In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 Ith International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 6691-6706, Online. Association for Computational Linguistics.
[25] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2020. RoBERTa: A robustly optimized BERT pretraining approach.
[26] Aaron Lou and Stefano Ermon. 2023, Reflected difffusion models In Proceedings of the 40th International Conference on International Conference on Machine Learning.
[27] Hassan Maatouk and Xavier Bay. 2016. A new rejection sampling method for truncated multivariate Gaussian random variables restricted to convex sets In Monte Carlo and Quasi- Monte Carlo Methods, pages 521-530) Cham. Springer International Publishing.
[28) Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. 2022. Locally typical sampling Transactions of the Association for Computational Linguistics.
[29] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. 1953. Equation of state calculations by fast computing machines) The Journal of Chemical Physics, 2106):1877-102.
[30] Hadi Mohasel Afshar and Justin Domke. 2015. Reflection, refraction, and Hamiltonian monte carlo In Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc.
[31] Radford M. Neal. 1993. Probabilistic inference using Markov chain Monte Carlo methods Department of Computer Science, University of Toronto Toronto, ON, Canada.
12

---

[32] Radford M. Neal. 2011. MCMC using Hamiltonian dynamies) In Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng, editors, Handbook of Markov Chain Monte Carlo, chapter 5. Chapman and Hall/CRC.
[33] Akihiko Nishimura, David B. Dunson, and Jianfeng Lu. 2020. Discontinuous Hamiltonian Monte Carlo for discrete parameters and discontinuous likelihoods Biometrika, 107(2):35 380.
[34] Jekaterina Novikova, Ondiej Dušck, and Verena Rieser. 2017. The E2E dataset: New challenges for end-to-end generation In Proceedings of the 18th Annual SIGdial Meeting on Discourse and Dialogue, pages 201-2066 Saarbrücken, Germany. Association for Computational Linguistics.
[35] Artidoro Pagnoni, Vidhisha Balachandran, and Yulia Tsvetkov. 2021. Understanding factuality in abstractive summarization with FRANK: A benchmark for factuality metrics] In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 3812-489, Online. Association for Com- putational Linguistics.
[36] Ari Pakman and Liam Paninski. 2013. Auxiliary-variable exact hamiltonian monte carlo samplers for binary distributions, In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc.
[37] Du Phan, Neeraj Pradhan, and Martin Jankowiak. 2019. Composable effects for flexible and accelerated probabilistic programming in numpyro. arXiv preprint arXiv:
[38] Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. 2022. COLD decoding: Energy
based constrained text generation with Langevin dynamics In Advances Neural Information Processing Systems.
[39] Benjamin Rhodes and Michael U. Gutmann. 2022. Enhanced gradient-based MCMC in discrete spaces Transactions Machine Learning Research.
[40] Chitwan Saharia, William Chan, Huiwen Chang, Chris Lee, Jonathan Ho, Tim Salimans, David Fleet, and Mohammad Norouzi. 2022. Palette: Image-to-image diffusion models, In ACM SIGGRAPH 2022 Conference Proceedings, New York, NY, USA. Association for Computing Machinery.
[41] Timo Schick, Sahana Udupa, and Hinrich Schütze. 2021. Self-Diagnosis and Self-Debiasing Proposal for Reducing Corpus-Based Bias in NLP. Transuctions of the Association for Computational Linguistics, 1424-444.
[42] Emily Sheng, Kai- Chang, Prem Natarajan, and Nanyun Peng. 2021. Societal biases in language generation: Progress and challenges) In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 1tth International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4275-4293, Online. Association for Computational Linguistics.
[43] Yang Song and Stefano Ermon. 2020. Improved techniques for training score-based generative models In Advances in Neural Information Processing Systems, volume 33, pages 12438 12448. Curran Associates, Inc.
[44] Molei Tao and Shi Jin. 2022. Accurate and efficient simulations of hamiltonian mechanical systems with discontinuous potentials Journal of Computational Physics, 450: 10846.
[45] Sean Welleck, Ili Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. 2020. Neural text generation with unlikelihood training. In International Conference on Learning Representations.
[46] Max Welling and Yee Whye Teh. 2011. Bayesian learning via stochastic gradient Langevin dynamics, In Proceedings of the 28th International Conference on International Conference on Machine Learning, page 68 1-688, Madison, WI, USA. Omnipress.
13

---

[47] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma. Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020. Transformers: State- of-the-art natural language processing In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38-45, Online. Association for Computational Linguistics.
[48] Kevin Yang and Dan Klein. 2021. FUDGE: Controlled text generation with future discriminators In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 351 15135,,3, Online. Association for Computational Linguistics.
[49] Ruqi Zhang, Xingchao Liu, and Qiang Liu. 2022.
Langevin-like sampler for discrete distributions In Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages
PMLR.
[50] Yichuan Zhang, Zoubin Ghahramani, Amos J. Storkey, and Charles Sutton. 2012. Continuous relaxations for discrete hamiltonian monte carlo In Advances in Neural Information Processing Systems, volume 25.
14

---

A Limitations
Approximating the base measure. this work, we go one step closer implementing principled approach for text generation. However, in our text generation experiments, we follow the previous work using uncorrected Langevin dynamics. Moreover, when implementing SVS for text generation, we assume all Voronoi cells to have an equal base measure, which might not hold.
Efficiency. As reported App. H all gradient-based samplers are considerably slower than ancestral sampling and heuristics such as FUDGE. Further efforts are needed to make gradient-based methods faster.
Text Quality. As shown in previous work, sequences with high probability under the LM can be repetitive, dull, or degenerate [16]. Therefore, as with any other sampling method, SVS might sample degenerate sentences, and the quality of the samples depends on the LM probability distribution. This an active area of research with various proposals from changing the loss function during training 45 to modifying the decoding objective [28
B A Note on the Choice of the Gaussian Measure
We thank the reviewers and the meta reviewer for their careful assessment of this work and their thoughtful feedback. As response to an important point raised by the meta reviewer, here we explain the reasoning behind using Gaussian measure in Eq. (12). The gradient gm is only defined Voronoi centers and the goal is to follow direction similar to gm when we are in the vicinity of the Voronoi center, i... in the Voronoi cell. We note that this direction needs be adjusted depending on the position in the Voronoi cell x. A natural choice for this would be to use truncated Gaussian
that is centered gm which implies that the gradient in should be gm x, follow similar direction gm at the center of the Voronoi.
C Proofs
C.1 Proof of Proposition 1
Proposition 1. Let p [pi,.... .PM] be umbeedding-augmeenii distribution with embeddings
{vm) C. Rd. and let py be the corresponding Voronoi measure Eq. 77). Then, pv (CC) = Pm where Cm defined as Eq. (6). See App. C.1 for proof.
Proof.
pv(Cm) / pv(x)d
(19a)
Pm dp
C.m ((Cm) dX (x)dA
(19b)
Pm [
dp
(x)dd
(19c)
((Cm) Jcm dA
Pm pu(Cm)) Pm
(19d)
(CCm)
C.2 Proof of Proposition 2
Proposition 2. Let be measure on Rd. Then, we have the product measure space as (uCmm)
Il ((Cm..). See App. C.2 for proof.
15

---

Proof.
Let m 1 mx] [MJ. We have
N
pa
II Crenn
(20a)
N
II p(Cmm)
(20b)
mm
C.3 Proof of Proposition
Proposition 3. Eq. App. C.3 for proof.
13 is absolutely continuous with respect to the Lebesgue measure X. See
Proof. Choose E E BRR) such that A(E) = 14 Note that E = (EV/)UUM
where
u(E \ K)) = 0 by Eq. (3). Since the Gaussian measure over I2 itself is absolutely continuous with respect to we can also conclude that μ C. 0 for any m. Hence, ((E) s p(E) (K)
Em p E E Cm) = 0 which means μu( E) = 0. So << X.
C.4 Proof of Proposition
Proposition 4. The gradient of the log of the Voronoi measure is given by
undefined, 8m -x
if E (nm
Vx (x)))
if E 80m otherwise
(14)
where the first two blocks in the case statement apply if there exists some m such that int (Cm) or x E 00m- See App. C.4 for proof.
Proof. We have three cases. Suppose x E int(Cm) for some m E [M]. Then, by Observation we have that pv (x), and, thus, log (x) is differentiable. Direct computation reveals:
Vx lxg = Vx log
Pm c((m))
+
+V log dl
(21a)
=0
1
V logexp
gm -x112
Vx log (CCm)
=0
x|1
(21b)
gm
(21c)
Next, suppose x & have that x E ac,. for some m. Then, by the next Observation (Observation T). we have that py discontinuous, so the derivative is not defined.
U Cm- Then, the measure is zero, so the gradient is well. Finally,
Observation 1. (K., 1)- Voronoi measure pv differentiable with respect to Pm on the set UM iint (Cm),, and discontinuous on the set K. \ U (Cm). i.e., the union of the Voronoi cells' boundaries UM 00
WW use 3(.) denote the standard Borel o-algebra.
16

---

D Properties of Hamiltonian Dynamies
Preservation of Measure. First of all, the Hamiltonian equations are volume- or measure- preserving. Intuitively, this means that if we move a region in the phase space along the dynamics for an arbitrary amount of time, the volume of the region would stay unchanged Concretely, we can define a function
g' (x(0), r(0)) (x()),r())
(22)
as moving every point in the phase space along the Hamiltonian equations for some time 16 Then, using g as change of variable would leave the underlying probability measure unchanged.
Time Reversibility. Next, the Hamiltonian equations are time reversible, meaning that if the equations can move rx,r) to (x', r'), then it would also take -r') to (x. Due to our choice of distribution of r always symmetric, these properties simplify the acceptance probability to be only the energy difference, i.e., we can ignore the conditional probabilities in the standard Metropolis- Hastings acceptance probability.
Conservation of Hamiltonian. by the Hamiltonian dynamies
Finally, we can quickly verify that the Hamiltonian is conserved
dH
ÖH dx;
HH dr, Ör, dl
(23)
0x; dt
ÖH 0H
0H 0H
(definition in Eq. (6
(24)
0x: Ōr;
Ør, 0x:
OH 0H
0H OH
(symmetry)
(25)
0x; Ōr;
Ox; Ör,
(26)
This shows that the acceptance probability will be exactly the Hamiltonian equations integrated exactly. In practice, numerical errors will lead to fluctuations in H. The Metropolis-Hastings acceptance probability ensures detailed balance.
E Details of Voronoi Sampling
E.1
Conservation of Hamiltonian in Refraction-Reflection
Proposition 5. A single step of refraction-reflectioon conserves the Hamiltonian.
Suppose instantaneous refraction-reflection takes (x, r) to (x', r'). In other words, (x, r) the particle's coordinate and momentum at the boundary prior to the defraction-reflcctionn and (x', r') is the particle's 's coordinate and momentum after the refraction instantancous changes in its potential energy and momentum. Recall the refraction-reflectioon equation
Proof.
which includes
12 2AU
(refraction when ||rμ > 2AU
r/
[
(27a)
F1
(reflection when ||r_l|3 S 2AU)
15This result known as Liouville's theorem in classical mechanics 2 $16]. Upon noticing that Hamiltonian dynamics is divergenceless, one can interpret it as a simple application of the (higher-dimenssional) divergence theorem, which itself is consequence of the generalized Stokes" theorem.
We say transformation taking (x, r) to (x', (x','', r') conserves Hamiltonian if H r) = H(x', r').
This function is called the Hamiltonian phase flow, simply Hamiltonian flow ( $16). Flow is general and important notion in the study of differential equations and related subjects, in which some additive group acts (IR, +). In the case smooth Hamiltonian {g' hIRR can seen a one-parameter group of diffeomorphisms over 2d
17

---

where r1 Flj is the normal decomposition of and r' =rr rf. Then,
H(x', r') = Ux')== +
2 |
(27b)
U(x)= + r''s + +
(27c)
2
1
(x')
|| 11 (IL.TT)
(27d)
2
U(X) 2
1
11 |
((ri)r)) = (27e)
(U(x) + AU + (1
113 2AU) +
1
(refraction)
(27l)
(U(x) + - 1 1
(reflection)
(U(x) +
AU
(refraction) (reflection)
(27g)
(U(x) + 11
(xx) + 2 1
(27h)
(x,
(27
E.2 Proof of Correctness
In this section, we give a proof of correctness of our sampler by establishing its detailed balance. We
will first prove several useful properties of the sampler in E.2. to E.2.3 and then combine them to prove the detailed balance in App. E.2.4.
E.2.1 Measure Preservation in Leapfrog
First all, we note that the two leapfrog steps are measure-preserving. since they are composed of a series of shear transformations.
Proposition 6. The leapfrog steps measure-presservng.
Proof. Recall that the two leapfrog steps used in HMC (algorithm) I are (x, r) + (r. 2 VU())) and (x, (x r)
By the change-of-variate formula, to show a transformation measure-preserrvngg it suffices to show that its Jacobian has determinant 1. The leapfrog step (x, - (x, (VU(x)) function has the Jacobian
0(x, r - 1aar-gVU(() vx(())
I (- 9)
(28)
0(x,r)
where (x) denotes the Hessian of U. This Jacobian 28 has determinant and hence the leapfrog transformation (x, 1) to (x, - & (x))) is measure preserving. Similarly, the other leapfrog step (x,r) + (x + er, r) has Jacobian
0 +(x+,r,)) (xx,r)
( 7
(29)
which also has determinant
E.2.2 Measure Preservation in Refraction-Reflectoo
The computation for showing that refraction and reflection steps are measure preserving is slightly more involved than the leapfrog case. Our proof below largely follows the one found in Mohasel Afshar and Domke (30, where we simplified and corrected some details.
Proposition 7. The refraction step is measure-preservingg
18

---

individually below. Again, without loss of generality, suppose Xı S 0 and x 2 0. Let AU be the function of the signed potential difference as changes from negative to positive, defined only when x = O. Let = (0, Y2...... ..a)) ya) be the point Proof. We consider single step of refraction-reflection with total step size e and with only one discontinuity. Note that, without loss of generality, we may only consider the discontinuity surface to be the hyperplane X1 since it is equivalent any tangent hyperplane of the discontinuity (hyper)surface through an affine transformation. Then, normal vector the hyperplane X1 0 e1 (1,0, .......0)) 0) and
function 7 that takes (x, (x'; r')
= (ri, .......)) 0) and F|| = (0,
(30)
In this case,
vi = and x = tr, since Fij is not affected by refraction-reelection. Therefore,
(31)
ox or =1 A 1123 2, θx òr.
(32)
and
0x 0x 0r 0r 0.
4 i 2nd j *
(by Eq.
(33)
0xj Ör,
0x, Ör,
Eq.
32
and Eq.
33
shows that the absolute determinant of the Jacobian of y is the same as
0x
ax
0x' θr
Oxi òr
det Vol = det
Drj
(34)
0r1
0ri
0x Ōri
Ōri 0x
8x.
Dr1
We analyze all four quantities in Eq. (4)
where the discontinuity is encountered. In other words, the particle begins x, moved past y and arrived at x'.
Refraction.
In the case of refraction, rî > (y) and
r 1 (yU
(35)
Let ò be the step size it takes to reach y. Then
x1
(36)
ri
x (E 8)r(
X1
(37)
ri
and
X1
x br = x
-
r.
(38)
r1
Then,
0x!
X1
E
rí
(Eq. 37
(39a)
0x
θx1
rı
Or'
Xi ari
r +
(product rule)
(39b)
0x1
r1
ri
0x1
X1
0ri
+ rí
$ +
(product rule),
(39c)
ri
0xi
ri
0x
0
E +
X
r
(Eq. 37
(40a)
dr
dr1
ri
0r
+
+
(40b)
ri
r
dr
19

---

0ri
d 0v (y)
(by Eq. 35
(41a)
0x1
Ox1
0(1 2AU(y))
(chain rule)
(41b)
2/17 - yy
0x1
1 (AU(y)
(41c)
rí 8x1
and
or
0V yyU(y)
(by Eq. 35
(42a)
gr1
dr1
a(r (y)(y))
(chain rule)
(42b)
2 2 r.
(y
ir1
r1
1 (yU(y)
(42c)
r rí
Ør1
Then,
0x Ør
0x| θr rri 0x1
det 4
(Eq.
0x1 δr
(43a)
x1
ar4
ri
Ori
+ x1
8r4
dri
E
E+
(Eq. 39 and
40
r1
0x1
ri
Øri
rî
Ii
Ør,
0x1
(43b)
r
④r
(43c)
ri
rr
ri
0xi
())(y)
X1 1 ay
(Eq.
and
42
r1
r
ri
dr,
ri r 0x1
(43d)
1
(yAU(y)
+ aaU(y)
(43e)
r1
where
(AU(y) X1 (yU(y)
(44a)
dri
ri 0xi
Σ
dyU(y) θy:
+
X1 Σ
(y oy:
(chain rule)
(44b)
Ty: θr1
Ty: θx1
(yU xir; ri
X1 Σ
(yU r
(Eq. 38
(44c)
Oy:
Ty:
(44d)
Hence, Eq. 43 and Eq.
together imply that det Vyl = 1.
implly
(45)
So is measure-preserringg in the case of refraction. Reflection. In the case of reflection, rf < (y) and As in the case refraction, let the step size takes to reach y. Then
r = -1i-
(46)
X1
(47)
r
X1 (-r()
x = (E 5)r
c
-er
-11-
(48)
r
20

---

We then directly calculate
Ox
0x -E,
11
(Eq. 48
(49a)
0x1
0x1
0x1
0,
(Eq. 46
(49b)
0x1
8x1
Hence,
del V>l = -(())((-1)))) (-+) -1.
(50)
So is measure preserving in the case of reflection as well.
E.2.3 Time Reversibility
Proposition 8. The reffaction-rellcction step is time-reversible
Proof. A refraction-reflectio step is time-reversible means that, if a single step of refraction- reflection procedure takes (x, r) to (x', ,'), then it would also take (x') (x, -r). We can show this by considering each cases:
Reflection: When reflection happens, ||rll 2AU, and hence || - - 11 -
1r1113 < 2AU, meaning that the reverse trajectory would be reflected well: Refraction: If AU > O, then the reverse trajectory is crossing the boundary from the other side, seeing a sudden decrease in potential, and hence would be refracted and regain the magnitude of momentum lost the forward step. AU < O, then - r' 113 > 2 and
hence the reverse trajectory would also be refracted, ending in the original momentum with the sign reversed.
Proposition 8 combined with time reversibility of leapfrog step as in basic HMCC, shows that Voronoi sampling is time reversible. Hence only need to use the Hamiltonian difference in the Metropolis- Hastings acceptance probability.
E.2.4 Detailed Balance
Theorem 1. step of Structured Voronoi Sampling (Algorithm 4 satisfies the detailed balance.
Proof Sketch. From measure preservation (App. E.2. and App. E.2.2) the change of variable as introduced by integrating Hamiltonian equations have Jacobian with absolute determinant and hence can be omitted. From time reversibility (App. E.2.3), we only need to use the Hamiltonian difference in the Metropolis Hastings acceptance probability. And, finally, by using a Metropolis Hastings accepting step (lines & to 13
ensure the detailed balance.
E.3 Related Work
Such an integrator scheme appears to be well-known in the computational physics community, dating back early Jin and Wen [8], and quite possibly even earlier. Integration algorithms based on this idea continue to receive active research [44].
The first usage of such integrator with discrete stepin the context of MCMC appeared in Mohasel Afshar and Domke (30
[8 Mohasel Afshar and Domke (30 primarily based their motivation on the analogy. We note that, in fact, Hamiltonian mechanics originated from Hamilton's 's formulation of geometrical optics (or Hamiltonian optics) 22 VVI.7.. This connection, important to modern physics, should be interpreted with care in our context since momentum isn' 't natural quantity in optical rays.
optical reflection-refractin
In an earlier work, Pakman and Paninski 36 used the same idea but solved the trajectory exactly for simpler systems instead of using discrete steps.
21

---

Later, Nishimura et al.
35 provided derivation of this integrator from the first principles of the
calculus variations T. importantly, it should be noted that, due to the potential function being discontinuous, Eq. (T6) loses its well-posedness as a system of differential equations, hence the necessity of justification based on non-smooth analysis.
Algorithms
Algorithm 2 Langevin Dynamics
Input: x": current sample, U: potential energy function, Et step size Output: next sample: x x++
I: r IO.
2: r 1i-r-gVUG (x)
3: x <- +er
4: return x
Algorithm 3 MUCOLA
Input: V current sample, U: potential energy function, 6: step size Output: next sample: VH+1
1: r I).
2: r r (V()
3: V +- Proja( V +ar)
4: return V++1
Algorithm Structured Voronoi Sampling
Input: x': current embeddings, U: potential function, step size
Output: next sample: +++
I: ~ (O,
2: H UVV (xt) K(r)
3:
VU(V (xt))
4: x4+1 -FINDDISC(x",n
5: < r VV m (x--1))
6: H,11 t -U(x++1) + K(r)
7: AH < -H++ H
8: if's ~ U(,,) 1) < e -AH;
Metropolis criterion
9: return f+1
10: else
return x [+1 x
Algorithm 5 REFRACTREFLECT
Input: r²: current momentum, b normal vector of the boundary, AU: difference in potential energy Output: next momentum: ++1
I: rf
6T.' bl
2: ri +rr -r
3: if [|]|11 2AU
4:
r1t2
r 1
2AU
b refract
F
5: else
6:
f- -r
reflect
7: [+1
+- r rij
8: return r++
22

---

Split
Chinese
English
Fast food
French
Indian
Italian
Japanese
Total
train 2929
4100
5891
5889
4412
5909
5996
42061
valid 1489
1780
4672
test 492
613
632
639
497
608
638
4693
Table 2: Number of restaurant reviews in each split and food type. Note that some reviews do not represent any specific food type, therefore, the total count is bigger than the sum count of reviews in each food category.
E1 Efficiently Finding Discontinuities
As explained in X the key insight in SVS is to adjust the momentum when facing discontinuity in the potential function. Therefore, we first need to find discontinuities efficiently and then reflect/refract the boundary of the discontinuity. Remember that each leapfrog step, move from xf to x x² + er. To find discontinuities along this trajectory, we divide each leapfrog step into fractions of step and check for discontinuity. Concretely, we only advance the embedding by a fraction a, i.c. x' = X + aer (line in Algorithm 66. Then, we check for discontinuity by looking the difference between the potential energies. If we don't observe any changes in the potential function, we take the next fraction of step. Otherwise, we find the boundary and adjust the momentum (line 10 Algorithm o). Note that SVs, finding the boundary straightforward, and is a hyperplane characterized by the normal vector, as the line goes through the two Voronoi centers on each side of the hyperplane.
Algorithm 6 Find Discontinuity
Input: x²: current embeddings, current momentum, U: potential function, 6: step size, az discontinuity step size Output: next sample: x+1
1: T -++ 0
2: x
3: while T < 1
4: x' X aer
5:
AÚ + (()m)(xx) UV (V(
6:
AA =0:
b there is no discontinuity
7:
X x
8:
T + ++a
9:
else
10:
b, +- FINDB x')
Returns the intersection o' and the normal vector of the boundary
11:
x x xx++a' a'er
T+
13:
r+ REFRACTREFLECTTE. AU)
return x( +x x
G Dataset Statistics
This dataset is made available under the CC BY-SA 4.0 license. Our of this dataset is for fine-tuning GPT-22, and ii) training classifiers for topic control, which clearly matches the intended of this dataset mentioned by the creators end-to-end training and generating text with content selection. A summary of dataset statistics can be found in Table 2
H Experimental Details
Sampling algorithms. Hyperparameters for each experiment reported in Table Following prior work [46], in algorithms based on Langevin dynamics, we apply an exponential decay to the step size by decreasing it 0.05 after 500 steps. In all settings, take 500 burn-in steps.
23

---

Toy Example
LM Sampling
Controlled Generation
E
a
VS
0.1
0.1
SVS
0.1
0.1
1.
0.4
1.5
0.3
1.5
HMC
0.1
0.1
LANGEVIN
1.
1.5
1.5
MUCOLA
0.1
0.1
1.
1.
2.
Table 4: Hyperparameters used in sampling algorithms.
Food Classifiers We train 3 classifiers. First, for exper- iments with FUDGE, we follow the experimental detail as in the original paper [48] and train a 3-layered BILSTM classifier with 0.5 dropout. The hidden dimension is set to 300, and the embedding layer trained from scratch. Second, in experiments with MUCOLA, LANGEVIN, and svs, to make the setup as close as to FUDGE, we train a 3-layered B BILSTM classifier with 0.5 dropout. However, this time the BILSTM trained on top of fruzen GPT-2 representations, thus sharing the embedding layer that is necessary for these methods to work. Finally, to evaluate the success of the methods in following the control targets, we finetune a ROBERTA 25 base model. The accuracy of all the classifiers and the number of trained parameters reported in Table 5 We train all the models single gtx_1080_t_ ti GPU with approximately 2 hours of total computational budget.
Table 3: Inference time for different
methods on the controlled generation experiments. All experiments are done on single A100-40GB GPU.
method
sec/batch
FUDGE
10
MUCOLA
30
LANGEVIN (ours)
31
SVS (ours)
84
Inference times. We report inference times based on sec/batch. The number of decoded sentences
batch depends on the GPU memory and the size of the model. As depicted in table 3 using Voronoi measures does not increase the inference time (compare MUCOLA and LANGEVIN). We observe that SVS inference time is longer, because of the extra momentum adjustment steps. However, one can reduce the inference time by increasing a.
model
f1-score
precision
recall
# params
BILSTM BILSTMPROBE
0.87
0.87
0.87
17M
0.84
0.84
0.84
37M
ROBERTA 0.90
0.91
0.90
124M
BILSTMPROBE
0.90
0.90
0.90
878M
Table Performance of food classifiers, and their number of learnable parameters, used controlled generation experiment. All classifiers are trained and tested on E2E dataset.
I More Experiments on The Toy Model
To better understand the advantages of Voronoi sampling over HMC MUCOLA, further look at the JS divergence between the reference distribution and the distribution of samples when increasing the number of iterations. As depicted Fig. while the divergence decreases with more iterations across all sampling methods, Voronoi sampling converges to the reference distribution with fewer iterations. We then look the distribution of sampled elements in Fig- [5] We observe that with 100 iterations, MUCOLA undersamples the element with the maximum probability while oversampling other elements. Finally, we extend toy model from 4 squared cells in IR² to 2* hypercube cells in R (Fig. 6). As the dimensionality increases, the divergence between the samples' distribution and the reference distribution also increases in all sampling methods. Importantly, Voronoi sampling consistently converges faster across different values for k.

---

Sampling Method
0.07
Sampling Method
--- Mutola
0.15
Vironoi Sampling
Varoaed Sampling
Divergnnce
HMU Sampling
Divergence
0.05
IMC Sampling
0.04
0.03
0.05
0.02
0.1
0.5
1.5
Temperauure
Temperature
(a) 500 iterations
(b) 1000 iterations
1.4
Sampling Method
1.2
MuCoLa
Veronoi Sampling
JS Divergence
HMC Sampling
0.8
0.6
0.4
0.2
0.5
1.5
Temperature
(c) 100 iterations
Figure 4: Comparing JS divergence of methods using different numbers of iterations. In general, Voronoi sampling converge to the true distribution faster compared to HMC and MUCOLA. As the number of iterations increases, the divergence between the samples' distribution and the true distribution decreases across all sampling methods.
J Controlled Generation Results
Table 6 Fig. 7 show the performance of sampling methods on different metrics. We show a sample of generations for each control target in Table 7
PUDGE
MUCOLA
LANGENEN
Sacucia
Dia-1
Dia-2
DILL3
FPL
Sacosa
Chinc
0.30
5.31
03.08
01.53
0.851
(1:31
IIL.9)
0.21
03.35
0.44
1.00
16.21
01.33
12.42
01:22
[1:30
English
0.15
8.83
[1:11
0..72
0.87
0..55
17:10
0.226
0.330
0.40
6.70
13.92
11.27
11.43
11.35
0.85
10.00
08.25
[1:01
(USS
Fast roed
0.25
6.04
0:41
0.57
0.08
0.86
3.39
0.26
0.38
0.47
1.80
10.09
01:9
1.00
11.41
0.53
0.28
0.50
0.55
8.52
0:00
0.35
0.40
0.51
17.67
0.95
halbas 0.31
5.19
0.37
0.50
0.61
0.50
18.10
0.37
0:42
0.33
6:95
11.39
01:5
0.41
0.51
0.89
15:17
0.96
0.11
0.50
Aapazcie
0.30
0.44
0.42
0.56
0.66
0.76
58.37
0.27
0.42
0.54
1.00
12.50
0.21
0.36
01.47
0.35
12.43
0.18
0.50
0.46
Table 6: Evaluation of different sampling methods on controlled generation, using three criteria:
success in following the control target (measured by the evaluator classifier), fluency (measured by perplexity), and diversity.
25

---

MuCola Sampling
MuCola
HMC Sumpling
Verensi Sempling
0.8
Veronot Sampling
Probability
Probability
0.6
Item
Item
(a) 500 iterations
(b) 1000 iterations
MuCol.a
HMC Sampling
0.8
Veronoi Sampling
Reference
Probability
0.6
Item
(c) 100 iterations
Figure 5: Comparing the distribution of sampled elements temperature 0.25. With 100 iterations, MUCOLA undersamples the element with the highest probability while oversampling other elements.
0.4
Sampling Method
0.35
MuCoLa
0.3
Voronoi Sampling
JS Divergence
HMC Sampling
0.25
0.2
0.15
0.05
3
4
5
6
k
Figure Comparing the distribution of sampled elements with the true distribution after 100 iterations, at temperature 0.5. There are 2 Voronoi cells with equal base measures in R where elements to sample from are located at the center cach Voronoi cell. Voronoi sampling converges faster to the true distribution across all & values. As the dimensionality of the sample space increases, the divergence of all methods increases.
26

---

FUDGE
MuCoLa
Langevin
SVS
Cog MacEes
Trench
2632
Deread 320000
AJCOMS
gol-mean
2812
pol-mea
Figure 7: Evaluation of different sampling methods on restaurant review generation, along axes: mean and standard deviation of negative perplexity"":ppp) -mean 1 -ppl-std 1), the percentage of generated sentences adhering to the control target (success 1), and diversity metrics (dist-1 f. dist-2 t, dist-3 t). For most control targets, SVS achieves the highest success rate, with relatively low perplexity.
27

---

Chinese
FUDGE
In the city centre near Yippee Noodle Bur Chinese. is Alimentum. It has moderate prices and and has I out of 5. It has food and high customer rating. The Rice Boat is It serves Chinese food with low customer rating. The fast food and restaurant The Golden Curry It has low customer rating and price. The highly rated Chinese restaurant The Phoenix has high
MUCOLA
LANGEVIN
SVS
English
FUDGE
It has an average customer Rating. Bibimbup House has English food the riverside area neur and has a low customer rating. The Golden Curry children friendly, serving English food, with It low rating and located near to city centre. The Phoenix a English food Alimentum the city centre near moderate price range. serves English food. is
MUCOLA
LANGEVIN
SVS
Fast food
FUDGE
A fast food, coffee shop, Strada has low customer rating, has price range of over E30. It is and is family friendly and serves fast food. The Wrestlers is fast food coffee shop in the It is located near the riverside, is cheap family friendly fast food restaurant, and is called It is located near the river. The Mill is a cheap. fast food and coffee shop near the
MUCOLA
LANGEVIN
SVS
French
It has low-priced Inn French fond. is near Café Rouge. The Alimentum kid friendly fast food The French restaurant The Waterman is located in the city centre. The price range than It restaurant located in the riverside, restaurant, offers French fond with price It family restaurant that serves French food with a price range and has low customer rating.
MUCOLA
LANGEVIN
Indian
FUDGE
The Phoenix Indian restaurant has moderate prices with a 3 out of 5 rating. Located on the It is in the city and has low customer rating. The Waterman is a low priced
MUCOLA LANGEVIN
It is not child friendly and it is near the river. It serves Indian foud and a customer rating It is located in the city centre near The Portland Arms Indian food and has a low customer rating.
SVS
Italian
FUDGE
It has family Italian food and has low moderate price range. The Rice Boat has average is high priced Italian food restaurant with customer rating of average. The Phoenix high It located in the city centre, it not family friendly and is coffee shop serving Italian It located in the the city centre near The Portland Arms. The Eagle is an Italian restaurant.
MUCOLA
LANGEVIN
SVS
Japanese
FUDGE
Japanese food. Its customer rating 3 out 5.T Phoenix is Japanese in the city centre for Japanese food is located the city centre. It has a low customer rating. The Golden It located in the riverside. It is a Japanese food. is a pub restaurant It is located in the riverside. It a low rated Japanese restaurant, and coffee shop.
MUCOLA
LANGEVIN
SVS
Table 7: Examples of sampled sentences from different control food targets.
28


Reviews:
[{"review_id": "Sx8HAj9P4v", "reviewer": "Reviewer_tTqL", "summary": "Gradient-based sampling for text generation is an important challenge, as it allows for sampling from energy-based models, such as one defined by a mixture of experts as found in classifier-guided sampling. The main challenges in gradient-based sampling for discrete distributions are encoding the discrete distribution into $R^d$ and dealing with inevitable discontinuities that arise in the encoding. The paper proposes a method that addresses these two challenges with Voronoi measures and an application of refract+reflect HMC respectively.\n\nThe method is validated in three settings: First, sampling from a non-structured and tractable discrete distribution with 4 classes and associated embeddings. Second, sampling from a language model. Third, sampling from a language model with additional constraints. In all settings, the method improves upon baselines, namely Fudge, MuCoLa, and Langevin dynamics (without reflection).", "questions": "1. How is the method related to Gibbs with gradients methods, such as [1] and [2]? SVS takes advantage of embedding geometry and I believe GwG does not, which would plausibly lead to improvements.\n2. It would have been nice to see comparisons to non-principled gradient-based sampling, such as COLD. A lack of rigorous justification for an existing method should not be enough to discount its (potential) effectiveness.\n3. Why is the constrained text generation task different from the tasks studied in MuCoLa?\n4. There are quite a few references to lines of algorithms in the Appendix.\n5. Are the small gains from reflection due to the length of the chains? Would the difference between Langevin and SVS be larger if the computational budget was smaller?\n\n[1] Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D.K., & Maddison, C.J. Oops I Took A Gradient: Scalable Sampling for Discrete Distributions. ICML 2021.\n\n[2] Zhang, R., Liu, X., & Liu, Q. (2022). A Langevin-like Sampler for Discrete Distributions. ICML 2022.", "limitations": "The limitations were adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The approach is well-motivated and interesting. \n* The writing is clear and easy to follow.\n* In text generation, unconstrained and constrained, the method does show improvements over the MuCoLa baseline. However, the gains from reflection and refraction seem quite small.", "weaknesses": "Experiment baselines: The paper only compares to MuCoLa and Fudge as text generation baselines, but other methods for controllable text-generation exist such as diffusion-LMs and other Gibbs with gradient (GwG) methods [2]. Since the claim is principled gradient-based methods for text-generation, not having a comparison to diffusion-LMs seems reasonable. However, I believe other GwG methods should be compared (see questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for bringing up the Gibbs with gradient methods. We will ensure their discussion in the related works section of the final manuscript. However, in terms of empirical evidence, [1] doesn't feature any experiments on language generation. We believe that applying this approach to sample a text sequence would be impractical without further improvements. The primary reason is that both [1] and [2] operate within the logits domain. In the context of language generation, this entails sampling each element from a vocabulary of approximately 50,000 items (as in the case of GPT-2 small). This vocabulary size is significantly larger compared to MuCoLa or SVS, which function in the embedding space $\\mathbb{R}^{768}$. While [2] does present an experiment on the infilling task, it only samples 25% of tokens within sentences. This setup is computationally less demanding than the generation settings outlined in our paper. To the best of our knowledge, the code for the infilling experiment hasn't been released. Consequently, additional research and implementation are necessary to scale these methods for sampling sequences of length 20 or more.\n\n**Questions**\n1. The benefit of Gibbs with gradient methods is that they provide bounds for convergence. However, as stated by the reviewer, they do not benefit from the similarity of the word embeddings when navigating the state space. As mentioned above, such approaches are considerably more expensive, which limits their applicability in real-world text generation settings. \n2. We’ve attempted to adapt COLD for the controlled generation experiment. Unfortunately and even after increasing the control term’s weight, the outcomes closely resembled those of the uncontrolled GPT-2, resulting in very low success rates. We plan to persist in our efforts to improve COLD results by experimenting with varying hyperparameters. If we observe any improvement, we will include the updated results in the final manuscript.\n3. Unfortunately, there is no widely used benchmark for controlled generation. Even when two papers use the same benchmark, the exact prompts that are used could be different, which limits the reproducibility and fairness of the results. In this paper, we followed the experimental setup in [3]. To address your comment, we added a new experiment on a task that is studied in MuCoLa and other prior works, please refer to the general response to the reviewers for further details. \n4. We will move Algorithm 1. to the main body of text in the final manuscript. \n5. Yes, that could very well be the case. However, it is hard to empirically test this hypothesis on the language generation experiments, since the ground truth distribution is unknown. To answer this, we added more experiments on the toy model (please see Figure 5) that supports this hypothesis. We observe that SVS has the lowest JS divergence compared to HMC on the Voronoi measure, and the difference is more pronounced when doing fewer iterations. \n\n[3] ​​Xiang Lisa Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori Hashimoto. Diffusion-LM improves controllable text generation. In NeurIPS 2022.\n"}, {"review_id": "XrmxTbjIAg", "reviewer": "Reviewer_v2AJ", "summary": "This paper proposes Structured Voronoi Sampling: a new gradient-based algorithm to sample from a distribution (i.e. a language model). The proposed approach leads to comparably fluent text whilst being able to better follow constraints (e.g. a topic) for the desired generation.", "questions": "1. some of the key algorithms and results are reported in the appendix. It would be good to include them in the main text upon acceptance\n2. in eq (2), enc(context) is a single vector. This is not the case with current models (e.g. GPT-2) which have a vector per input token. Can you comment on how this affects the formulation of LM with Embeddings?\n3. in eq (3), the conditioning on V_{<n} seems wrong, as `n` is only defined in the Cartesian product", "limitations": "yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. a new sampling method that is a correct MCMC scheme (unlike previous gradient-based samplers)\n2. evaluation on a synthetic task shows that the proposed approach better models the tail of the true distribution\n3. evaluation on constrained language modeling shows that the proposed approach achieves good fluency and diversity, whist being able to follow the control target", "weaknesses": "1. while the writing is generally great, it would help to have an introduction of gradient-based sampling before Section 3\n2. it is not clear how the proposed approximation of the (costly!) base measure affects the correctness of the proposed method", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. \n\nRegarding the suggestion on the presentation of gradient-based sampling, we will try to motivate gradient-based sampling further before going to the details in the final manuscript.\n> it is not clear how the proposed approximation of the (costly!) base measure affects the correctness of the proposed method\n\nWe do not apply any approximation in our experiments. As stated in the paper, our approach offers an exact sampling algorithm, up to the computation of the difference in base measures. This paves the way for future works on potential strategies to approximate the difference in base measures. Our empirical findings indicate that SVS exhibits a strong performance when compared to MuCoLa.\n\n**Questions**\n1. We will move Algorithm 1 to the main body in the final manuscript. \n2. $\\mathrm{enc}(w_{<n})$ is a single vector and can be the output of current LMs (like GPT-2). Concretely, to compute this vector with GPT-2, we pass the context $w_{<n}$ to GPT-2, and look at the last layer representation of GPT-2 **at position $n$**. We will make sure to clarify this further in the final version of the manuscript.\n3. Thank you for catching the typo, the conditioning should be on V. We will fix this in the final manuscript."}, {"review_id": "09Rldy0Rla", "reviewer": "Reviewer_BCGv", "summary": "The paper proposes a new gradient-based sampling approach called Structured Voronoi Sampling (SVS) for controlled text generation. The key idea is to extend the discrete point distribution over word embeddings given by language models into a continuous density that spreads out probability over their corresponding Voronoi cells. A Hamiltonian Monte Carlo scheme is then devised to efficiently sample from that density, handling discontinuities between cells through a volume-preserving refraction/reflection trick. Empirical results on a toy problem and a more realistic controlled text generation problem show SVS can better match target distributions and control constraints compared to baselines. \n", "questions": "1. More exposition could be provided to unpack eq. (2) which may be confusing to a typical neurips reader. in particular, I think many practitioners are more familiar writing the final layer as a softmax applied to a linear transformation, i.e. something like $P(w_n | w_{<n}) = softmax(v * f(w_{<n}))$ where $v$ is the full embedding matrix). Some readers may also have forgotten that GPT2 used the same embedding matrix at the initial and final layers (other implementation use a separate fully-connected layer here), so it may be worth a gentle reminder to avoid confusion. \n\n2. Similarly, some additional clarification could be given to interpret the denominator in Def. 2 and 3 as is essentially normalizing by the ‘volume’ of the cell (with the measure giving a suitable notion of volume). This will be obvious to those versed in measure theory but could help other ML researchers with less mathematical background. \n\n3. I was trying to think through the precise relationship to other approaches based on nearest-neighbor smoothing (e.g. Khandelwal [et](http://U.et) al, 2019. “*Generalization through memorization: Nearest neighbor language models*.” or Khandelwal et al, 2020. “*Nearest neighbor machine translation”;* El-Kishky et al, 2023. “*kNN-Embed: Locally Smoothed Embedding Mixtures for Multi-interest Candidate Retrieval”*). These approaches have a very similar flavor to the voronoi embedding, which on the surface appears to be equivalent to some kind of importance sampling based on nearest-neighbors. Does the voronoi sampler reduce to something like this as a special case? \n\n4. very minor: It was a bit confusing to have Alg. 1 prominently referred to in the main text (down to giving line numbers) but not be able to find it until I was later going through the supplemental. if it is important, it may be worth trying to fit into the main text.\n\n5. very minor: the abstract uses the acronym SVS but it doesn’t reappear until Fig. 3, at which point I was very confused (pragmatically, it’s confusing that it’s referred to as ‘voronoi sampling’ in Fig. 2, right next to it, which implies that SVS is something different?)\n\n6. very minor: is it worth pointing out in section 7.2 that there is no reason to actually prefer voronoi over regular ancestral sampling, given that ancestral sampling is already very efficient and provably matches the target distribution? And that we’re just doing this exercise (Fig. 3) as validation that the voronoi sampler is pretty close to the ‘gold standard’?", "limitations": "See above.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Developing provably sound sampling methods for text generation remains an important open problem for language models, especially for controlled generation. The proposed  method is well-motivated from first principles and provides formal guarantees unavailable with prior heuristic approaches, with rigorous mathematical derivations provided in appendices.\n\nA number of innovative steps are taken to get the core Voronoi idea to work, including (i) lifting the discrete token distribution to the embedding space, (ii) smoothing the measure-zero discrete distribution to a continuous density with the Voronoi transformation, and (iii) handling discontinuities in sampling with the refraction/reflection trick. These moves are independently interesting in their own right and a large segment of the NeurIPS community will likely find at least one of them to be novel and potentially applicable in future work.\n\nRelated methods like MuCoLa and Fudge are discussed and compared in the experiments. The toy domain is pedagogically useful for exposing the limitations of existing approaches, while the scaled-up controlled generation results are promising, showing competitive fidelity and control.\n\nThe paper is well-written and structured overall, and the writing systematically builds up the relevant concepts for a typical NeurIPS reader to understand the significance. The key generalizable ideas are appropriately emphasized.", "weaknesses": "(1) The most significant issue limiting the applicability of SVS as currently posed is the problem of calculating the base measure $\\mu$ in a high-dimensional space. This problem in some sense puts us back where we started, as the original problem motivating SVS in the first place is that the integral in the normalizing constant of the energy function is not tractable. Computing the exact integral for the base measure in SVS is obviously also not tractable (as noted up-front as a limitation the paper, which I appreciated). The assumption in 6.1 that all cells have equal base measure is a very strong assumption, given that this clearly does not hold in practice, and somewhat undermines the very careful and rigorous progression of proofs of correctness.\n\nI see a couple way to strengthen this part of the paper, and would strongly recommend doing something to close this gap for the paper to be maximally impactful. One possibility is to provide some analysis of the consequences of violating this ‘equal base measures’ assumption: is there a bound on how bad violations can get? how badly is this assumption violated in the controlled generation task being reported? Intuitively, ignoring real diff them would result in over- or under-representing certain regions. A second possibility would be to take a first step toward some approximate method to account for base measure differences. For example, just taking distances to the first k nearest neighbors of a point could efficiently put a bound on how big the cell could be? Or some kind of Monte Carlo approximation? Clearly a full resolution of this problem is a task for another paper, and I do not expect this problem to be fully solved, but charting a course (even if that course is a bit inefficient) would go a long way.\n\n(2) More analysis could be provided on the toy example with known reference distribution; for example, what do the sampled distributions actually look like? In what way is MuCoLa off when temperature is low? How does this scale with the size of the space (e.g. if instead of a 2x2 square, it were a 2^k hypercube in k dimensions)? Does MuCoLa just take longer to burn in? or gets stuck sampling {0,1,2}? I would have liked to understand these failure modes a bit better to better motivate how the proposed method overcomes them.\n\n(3) The controlled generation task could also be strengthened: the results are from a single fairly bespoke 'food' task and classifier, which limits generalizability. It would be more compelling to evaluate on a more systematic suite of controlled language generation benchmarks to better pinpoint where the benefits of Voronoi sampling are most pronounced. Additionally, since controlled generation is highly dependent on the (trained) classifier being used to guide sampling, it would be helpful to test lower or higher capacity classifiers with different uncertainty levels. I worry that using the same classifier for both generation and evaluation (the ‘success’ column of Table 1) means we may just be measuring the sampler’s ability to overfit to a bad classifier (it is quite a bit more ‘faithful’ to this classifier than MuCoLa or Fudge, which is not necessarily a good thing if it is just ‘hacking’ a bad classifier).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful analysis of our work and your valuable suggestions.  \n(1) Regarding the assumption on base measures and approximations:\nthank you for your suggestions on how to strengthen the paper. Perhaps the way that is more practical to do it to approximate base measures is through importance sampling. \n\nAn integration of importance sampling with SVS can look like this: at each reflection/refraction step (line 3 in Alg. 5), we need to compute the difference in the potential energy of two points:\n- If these points belong to the same Voronoi cell, then the base measures are equal. \n- If not, let’s suppose they belong to cells $C_m$ and $C_{m’}$. We take a number of samples from a Gaussian distribution with the mean set to the center of the corresponding Voronoi cells (let's call them $m$ and $m'$). \nWe then approximate $\\int_{C_m} \\mathrm{exp}(-\\frac{1}{2}  \\| g_m^t - x \\|^2) = \\int_{C_m} f(x) $ with $\\frac{1}{N} \\sum_{n=1}^N \\frac{f(x)}{q(x)}$ where $q \\sim \\mathcal{N}(m, \\varepsilon I)$. Ideally, one needs to use truncated Gaussian distribution as $q$, however, we might use the Gaussian distribution as an approximation.\n\n\nAs the reviewer stated, analyzing and improving this approximation can be the subject of a separate project that we defer to future work.  \n(2) Regarding extending the analysis on the toy experiment: thank you for this suggestion. We added more experiments on the toy model. Here is a summary of what we found:\n- In Figure 5, we vary the number of iterations. We observe that the difference between sampling methods is more pronounced with fewer iterations. \n- As suggested, we then look into the distribution of sampled elements at temperature 0.25 after 100 iterations. We observe that MuCoLa is sampling the highest probability element less frequently than Voronoi sampling or the reference distribution, while sampling {0, 1, 2} more often than needed. \n- Finally, we extend the toy model to hypercubes in k dimensions (figure 7). Generally speaking, as the dimensionality increases, the divergence between the samples’ distribution and the true distribution also increases in all sampling methods. Furthermore, Voronoi sampling consistently converges faster across different values for k.  \n\n(3) Regarding the choice of the controlled generation task and classifiers: we added another experiment on a common task, please refer to the general answer to all reviewers for further details. \n\nIndeed, the classifier’s accuracy and certainty have a significant role in the generation quality. To ensure fairness as much as possible, we use the exact same classifier for the gradient-based algorithms, and a similar architecture for FUDGE. \n\nWe also need to clear a misunderstanding here: the success measures reported in Table 1, are **not** evaluated by the same classifier used for controlling the generations. We train a separate and arguably more accurate “evaluator” classifier. Please refer to Table 5 for comparing the accuracies of classifiers.\n\n**Questions**\n\nThank you for your suggestions, we will add the suggested clarifications and move Algorithm 1. to the main body of text in the final version of the manuscript. \n\n> I was trying to think through the precise relationship to other approaches based on nearest-neighbor smoothing (e.g. Khandelwal et al, 2019. “Generalization through memorization: Nearest neighbor language models.” or Khandelwal et al, 2020. “Nearest neighbor machine translation”; El-Kishky et al, 2023. “kNN-Embed: Locally Smoothed Embedding Mixtures for Multi-interest Candidate Retrieval”). These approaches have a very similar flavor to the voronoi embedding, which on the surface appears to be equivalent to some kind of importance sampling based on nearest-neighbors. Does the voronoi sampler reduce to something like this as a special case?\n\nWe agree with the reviewer that on the surface these approaches might seem similar, however, there are major differences between Voronoi sampling and kNN-LMs that makes us believe that none is a special case of another. First, in kNN-LMs, a training dataset (or a set of examples) is cached, which will be then used during the generation. However, in this work, the centers of Voronoi cells are simply the words in the vocabulary. Second, sampling a new word in kNN-LM is still autoregressive and the underlying probability distribution is an interpolation between the LM probability and the distance to the cached exemplars. However, in Voronoi sampling, we sample the whole sequence at once, and the probability of sampling a sequence is an unaltered LM probability.\n\n> very minor: the abstract uses the acronym SVS but it doesn’t reappear until Fig. 3, at which point I was very confused (pragmatically, it’s confusing that it’s referred to as ‘voronoi sampling’ in Fig. 2, right next to it, which implies that SVS is something different?)\n\nWe intentionally use different terms in these two figures. In the toy experiment, only one embedding is sampled, which is different from the text generation experiments where a sequence of embeddings is sampled. Therefore, we call the former Voronoi sampling and the latter structured Voronoi sampling to highlight this difference. We will clarify this further in the final version of the manuscript. \n"}, {"review_id": "4cmzat9PJo", "reviewer": "Reviewer_qwXS", "summary": "The authors present Structured Voronoi Sampling, which is a gradient-based sampling approach. To be specific, the authors map the discrete distribution by a language model and defines densities; the density is then used to sample, which the process is based on hamiltonian monte carlo. The novelty of this paper comes from the theoretical analysis, but the core weakness is the empirical result; not much performance gain is seen across the experiments.", "questions": "Q1. Is there any particular reason why the authors did not test on popular controllable text generation task?", "limitations": "Please refer to summary and weakness section", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and structured. The flow of the paper is easy to follow, and the authors explain the introduced concept step-by-step.\n\n- The paper proposes a novel gradient-based sampling method that caters for controlled generation tasks.", "weaknesses": "- Weak/wrong claims: i.e. Line 65-66. Not all language models share input and output embeddings. Authors should rephrase the sentence to avoid possible misunderstanding\n\n- The empirical result is weak. There is not much of difference compared to Langevin in success and ppl score in Table 1. The same applies in Figure 3. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. \n> i.e. Line 65-66. Not all language models share input and output embeddings. Authors should rephrase the sentence to avoid possible misunderstanding\n\nWe will rephrase this as:  *_in **most** language models, the weights are shared between the language model head and the embedding layer_* in the final version of the manuscript.\n\n>The empirical result is weak. There is not much of difference compared to Langevin in success and ppl score in Table 1. The same applies in Figure 3.\n\nWe need to clear a misunderstanding here: both Langevin and SVS methods in Table 1 operate on the Voronoi measure that is introduced in this paper, thus are contributions of this paper. Regarding the advantage of SVS over applying Langevin Dynamics directly on the Voronoi measure, we must note that it depends on the task and computational budget. Based on the insights gained from the Toy experiment, the difference is more pronounced when the underlying distribution is more peaky. \n\n> Is there any particular reason why the authors did not test on popular controllable text generation task?\n\nUnfortunately, there is no established and popular benchmark for controlled generation. We chose the same setup as used in [1]. To address your comment, we added a new experiment on a sentiment control task. Please refer to the general response to reviewers for more details.\n\n[1] ​​Xiang Lisa Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori Hashimoto. Diffusion-LM improves controllable text generation. In NeurIPS 2022."}, {"review_id": "CzuP9FuksU", "reviewer": "Reviewer_p6Uf", "summary": "Authors have proposed a novel framework for gradient-based sampling from neural autoregressive LMs named Structured Voronoi Sampling. The core idea of the proposed approach is to map LM distribution to the embedding based version of it and then use newly proposed structured voronoi cells to perform sampling based on HMC. Authors carefully described each step along transformations and why it is theoretically sound. They discussed the conneciton of the proposed approach to related work such as COLD decoding and MuCoLa. They have done experiments in both toy task and controlled text generation to show the effectiveness and superiority of their approach.   ", "questions": "General comment: I believe this is very strong theoretical work here which has rather weak experimental setting because of poor choice of the initial model (GPT-2) for fine-tuning and the task setting. I think this could become a much stronger submission upon stronger experiments are done,\n\nQuestions:\n\nsec 7.2 lines 293 - 299. Its unclear what do you mean by reference distribution here and how LM is related to it? IIUC you are saying that ancestral sampled from GPT-2 finetuned on E2E dataset resembles the unknown reference/data distribution? I think that is a very rough approximation. I think ancestral samples from GPT-2 gives unbiased estimates of sequence level distribution induced by GPT-2, thats it. The underlying connection between finetuned GPT-2 and reference distribution is unknown but likely not that strong given the samples you shown in the appendix.\n\nTable 1: in the text you claim SVS outperforms everything else given metrics, but is it? It goes very close to Langevin per success and PPL (~ same given std), and diversity is lower than FUDGE / MuCoLa. Moreover, I think diversity should be compared to values computed over the data distribution, could you report that as well? ", "limitations": "Authors included broader impact section and discussed how their framework could help to alleviate negative implications of large LMs as well as being a generator of intentionally toxic content.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "# Originality\n\nthis work proposes a very coherent way of treating discrete neural based LMs using continuous densities. Opposed to prior work, their method uses less approximations and heuristics.\n\n# Significance \n\nResearch problems around decoding strategies including sampling based decoding is essential given the wide spread of large scale language models. This work performs an important step towards better understanding of the gradient-based sampling methods and how to apply it to LMs parameterizing discrete/categorical distributions.", "weaknesses": "# Experiments\n\n* Authors included samples from their methods and related work they have re-implemented, and these samples look pretty bad. Their proposed method repeats the same tokens right after each other making the sample look very unrealistic w.r.t. unknown data distribution e.g. \"It is located in *the the* city centre near The Portland Arms.The Eagle is an Italian restaurant\". This makes samples based results evaluations in the main text to be much less convincing. I tend to believe that the reason behind this is a poorly finetuned model: authors used GPT2 model which is quite out-dated while much better alternatives exist. Given that authors used modern GPUs (A100 40gb), they had all opportunities for choosing a stronger initial model.\n\n* Authors used only 1000 samples to analyze empirical distributions which is quite limited considering the vocabulary size and avg sentence length. Using much more samples and a better trained model could reveal more interesting observations.\n\n# Efficiency\n\nThe proposed approach is very slow even compared to Langevin dynamics. It would help to address this in the main text and not in the Appendix. Also it would help to put usual ancestral sampling time to see the gap between gradient based sampling and ancestral sampling in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful assessment and feedback. \n\n**Experiments** \n\n> Authors included samples from their methods and related work they have re-implemented, and these samples look pretty bad. Their proposed method repeats the same tokens right after each other making the sample look very unrealistic w.r.t. unknown data distribution e.g. \"It is located in the the city centre near The Portland Arms.The Eagle is an Italian restaurant\". This makes samples based results evaluations in the main text to be much less convincing. I tend to believe that the reason behind this is a poorly finetuned model: authors used GPT2 model which is quite out-dated while much better alternatives exist. Given that authors used modern GPUs (A100 40gb), they had all opportunities for choosing a stronger initial model.\n\nFirst, we should quickly clarify two points: \n- We must first note that we put a hard limit of only generating sequences of certain lengths, therefore, one must look at these generations as incomplete, the example that is mentioned in this review can take a complete form as: \"It is located in the the city centre near The Portland Arms. The Eagle is an Italian restaurant with a customer rating of 1 out of 5.\" \n- Another important point to mention is the unavoidable trade-off between success and perplexity, which also impacts larger models. \n\nBesides the two points mentioned, we agree with the reviewer that using a larger model can help to have more fluent generations. To address this comment we added another experiment with GPT2-large, please refer to the response to all reviewers for further details. \n\n> Authors used only 1000 samples to analyze empirical distributions which is quite limited considering the vocabulary size and avg sentence length. Using much more samples and a better trained model could reveal more interesting observations.\n\nIn general and in the absence of access to ground truth distribution, it is hard to know whether a certain number of samples is enough or not. We follow prior work, e.g., MuCoLa, in terms of choosing the number of generations.\n\n**Efficiency**\n\nWe will consider moving the efficiency analysis to the main body. Comparing inference times to ancestral sampling, however, can be misleading since with ancestral sampling one can not enforce any constraints. In other words, there is a certain extra computation overhead that will be introduced (not only with gradient-based sampling but with any other method, e.g., FUDGE) if one needs to control an aspect in the generations.  \n\n**Questions**\n\n> sec 7.2 lines 293 - 299. Its unclear what do you mean by reference distribution here and how LM is related to it? IIUC you are saying that ancestral sampled from GPT-2 finetuned on E2E dataset resembles the unknown reference/data distribution? I think that is a very rough approximation. I think ancestral samples from GPT-2 gives unbiased estimates of sequence level distribution induced by GPT-2, thats it. The underlying connection between finetuned GPT-2 and reference distribution is unknown but likely not that strong given the samples you shown in the appendix.\n\nThe ground-truth distribution in that experiment is set to be the finetuned LM distribution. As the reviewer stated, ancestral samples give unbiased estimates of this distribution. Therefore, comparing the distribution of drawn samples with ancestral samples distribution can be helpful in understanding which sampling algorithms are less biased. Also, please note that the samples shown in the appendix are from the controlled generation setup and not ancestral samples of the fine-tuned model. \n\n> Table 1: in the text you claim SVS outperforms everything else given metrics, but is it? It goes very close to Langevin per success and PPL (~ same given std), and diversity is lower than FUDGE / MuCoLa. Moreover, I think diversity should be compared to values computed over the data distribution, could you report that as well?\n\nWe do not claim that SVS significantly outperforms everything. Contributions of this paper result in two methods: Langevin (which operates on Voronoi measure) and SVS, and as mentioned in section 7.3 “both Langevin and SVS result in a high success rate and maintain fluency and diversity, and SVS is effective in maintaining a balance between various metrics and producing fluent sentences that adhere to control targets.” As we also highlight in that section, FUDGE gives more diverse samples but this comes at the cost of significantly lower success rates. \n\nThank you for your suggestion on adding the ancestral samples results, we added that as the first row (GPT-2) in Table 8. in the additional uploaded PDF."}, {"review_id": "SvgIRkXqnW", "reviewer": "Reviewer_iTvg", "summary": "The paper pushes the frontier for gradient based sampling for auto regressive models. The paper lays clear theoretical issues to apply such techniques and address two issues: 1) the major contribution of the paper consists in proposing to construct voronoi like probability space over the output token embeddings to enable gradient based sampling process 2) the SVS algorithm also contains the novelty to deal with the non-continuity at the voronoi border by proposing a novel sampling algorithm.\n\nThe authors test the proposed algorithm at a toy setting, confirming their theoretical superiority transfers to this toy dataset over gradient sampling baselines. The authors also test their algorithm at generation and conditional generation tasks where the algorithm shows good performance in terms of success, perplexity and diversity. ", "questions": "In Table 1, all gradient sampling algorithms have a relatively high perplexity, which is reflected also in the examples in the appendix. Do the authors think it is an inherent limitation of this class of algorithms?", "limitations": "I appreciate the authors discuss the broader impact as well as transparently give insightful limitations. \n\nThe text quality issue is largely mitigated in modern large language models such as GPT-4 etc. This might inspire the authors might to rethink ways to improve on the quality aspect. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has made good contributions in making the gradient based sampling more practical to tackle real problems. The theoretical contribution of constructing voronoi distribution based on embeddings to perform HMS sampling is a significant one; furthermore, the paper addresses some practical issues via a novel sampling algorithm. The theoretical layout is also quite clear, well highlighting the solved issues. \n\nThe paper confirms their theoretical findings empirically as well as testing on two concrete NLP problems where the paper shows better than some existing NLP popular sampling techniques FUDGE. ", "weaknesses": "My major problem for the paper is its presentation. The paper proposes a novel algorithm for sampling, however, all the algorithms have to be found in Appendix (minorly, these are not clearly indicated that it is in appendix for example for line 189). Note that the paper itself should be self contained and the appendix is really for interested readers to learn further details. \n\nAnother minor point for presentation is that the empirical part for this paper is relatively short and doesn't contain very detailed analysis. While the theoretical explanations is key for this paper, the similarity between eq(3) and eq(1) or eq(7) and eq(10) makes me think that the theoretical part can be shortened while maintaining the readability. \n\nFinally, sampling is certainly not the only way (and arguably not the SOTA) way to perform conditional generation, RLHF used in InstructGPT or related techniques such as DPG (Khalifa et al. 2021) should be mentioned or in the best case compared to better situate the current work on its empirical aspect. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We will make sure to move Algorithm 1. to the main body of the text. The reviewer suggested shortening the theoretical part to make space for experiments. We will make sure to add the additional experiments and contextualize them with the main text in the final manuscript. Since the main contribution is to offer a novel and principled way to apply gradient sampling for text generation, we devoted enough space to clearly explain our method. To this end, we need to systematically build up the knowledge that is not necessarily assumed to be known by all, which in fact is appreciated by the reviewers. We fear that shortening the theory part even further might confuse readers. \n\n> sampling is certainly not the only way (and arguably not the SOTA) way to perform conditional generation, RLHF used in InstructGPT or related techniques such as DPG (Khalifa et al. 2021) should be mentioned or in the best case compared to better situate the current work on its empirical aspect.\n\nIn this work, we focus on vanilla language models. We agree with the reviewer that RLHF and instruction-finetuning change the probability distribution of the underlying LM, and can definitely impact the controllability of language models. Analyzing and adapting such models for controlled generation, however, needs further analysis which we leave as future work. We will discuss this point further in the Limitations section of the final manuscript.\n\n> In Table 1, all gradient sampling algorithms have a relatively high perplexity, which is reflected also in the examples in the appendix. Do the authors think it is an inherent limitation of this class of algorithms?\n\nImposing a certain control on the generation process can introduce a trade-off between the success rate (in following the control) and fluency (that might be measured with perplexity). Such a trade-off exists not only for gradient-based sampling methods but also for other types of controlled generation methods (see Table 1. in [1]). Therefore, we do not believe that this is a particular limitation of gradient-based sampling methods.\n\n[1]  Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula, Noah A. Smith, and Yejin Choi. DExperts: Decoding-time controlled text generation with experts and anti-experts. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics.\n"}]

Author rebuttal:
We thank the reviewers for providing valuable and constructive feedback. We first provide responses to a shared concern raised by multiple reviewers. Responses to individual reviewers are provided below. We report the results of new experiments in an additional PDF. 

Multiple reviewers were concerned that we could have picked a more popular task for the controlled generation experiment. To address this concern, we added a new experiment on a more popular sentiment control task, which many of the prior works also experimented with [1, 2, 3]. The goal of the task is to control the sentiment of the generations. 

We use the same 15 prompts used in [1, 2] and generate 10 samples per prompt using **GPT2-Large**. Similar to prior work, we train classifiers on SST-2 dataset for sentiment classification. We use this classifier to enforce a positive sentiment in the generations. Results are shown in Table 8. of the additional PDF. We observe the following:
- FUDGE mostly fails in following the control, while providing more fluent and diverse outputs. 
- MuCoLa achieves a higher success rate compared to FUDGE, but significantly lower success rates compared to Langevin or SVS, with a high variance in perplexity and success rate. 
- Both SVS and Langevin Dynamics on the Voronoi measure perform quite well in terms of following the control, and SVS achieves the best overall success rate.   

These results are more or less in line with the topic control experiment, i.e., Table 1.


[1] Plug and play language models: A simple approach to controlled text generation. In International Conference on Learning Representations (ICLR), 2019.

[2] Sachin Kumar, Biswajit Paria, and Yulia Tsvetkov. Constrained sampling from language models via Langevin dynamics in embedding spaces. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP).

[3] Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula, Noah A. Smith, and Yejin Choi. DExperts: Decoding-time controlled text generation with experts and anti-experts. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics.


Meta-review: Throughout the review, the reviewers acknowledge the innovative method using Voronoi measure and reflection-refraction treatment to allow a gradient-based MCMC for sampling discrete variables, and the empirical benefits on various discrete conditional generation tasks. The reviewers are also concerned about comparison with recent alternative methods, the assumption of equal base measure over cells, and the application to more interested language models, for which the authors seem to have satisfyingly addressed in the rebuttal.

Nevertheless, I found a theoretical inconsistency in the methodology part. In implementing the method in Section 4, the proposed base measure in Eq. (12) requires the gradient $g_m := \nabla_V \log p(V)$. But the definition of this gradient is confusing: according to the words under Eq. (3), "$p(V)$ only places a positive probability on a countable set", and in Section 2.2., "importantly and similar to $p(V)$, $p(V \mid t)$ only places a positive probability on a countable set", hence $p(V)$ and $p(V \mid t)$ are not absolutely continuous w.r.t the Lebesgue measure and does not even have a valid density function. Such an explanation is also mentioned in Section 5.2 as the limitation of the MuCoLa method. If the gradient is to be understood as the gradient w.r.t each $v_w$ of Eq. (2), then the contribution is made less clear since one can directly apply LD and HMC using this $\nabla_V \log p(V)$.
Moreover, I do not think it is "natural" to target $x$ __towards__ $g_m$, but to let $x$ __follow__ $g_m$. In other words, I think it is more natural to take the gradient as $g_m$ in Eq. (14) instead of $g_m - x$.
A further minor issue is that, as the central idea of the method is to extend the measure on a finite (or at least countable) set of points to the continuous space, comparison to alternative well-established approaches to do this is expected, e.g., the Gumbel-Softmax trick [https://openreview.net/pdf?id=rkE3y85ee].

I posted these concerns to all the reviewers and called for discussions. I got feedback that $g_m - x$ in Eq. (14) is indeed unnatural from one reviewer. But two reviewers expressed the opinion that the innovation and empirical results could outweigh the technical flaws, which can be fixed by revising the writing. I hence give an accept following these opinions. But the authors must revise the paper to clearly address the two technical problems, by e.g., redefining $g_m$ by introducing a distribution variant that spreads density over the entire embedding space, and use $g_m$ instead of $g_m - x$ in Eq. (14).
Decision: Accept (poster)