Predictive Querying for Autoregressive Neural Sequence Models
Authors: Alex James Boyd
Sam Showalter
Stephan Mandt
Padhraic Smyth
Venue: NeurIPS 2022 Accept (2022)
Keywords: probabilistic querying
neural sequence models
recurrent neural networks

Abstract: In reasoning about sequential events it is natural to pose probabilistic queries such as “when will event A occur next” or “what is the probability of A occurring before B”, with applications in areas such as user modeling, language models, medicine, and finance. These types of queries are complex to answer compared to next-event prediction, particularly for neural autoregressive models such as recurrent neural networks and transformers. This is in part due to the fact that future querying involves marginalization over large path spaces, which is not straightforward to do efficiently in such  models. In this paper we introduce a general typology for predictive queries in neural autoregressive sequence models and show that such queries can be systematically represented by sets of elementary building blocks. We leverage this typology to develop new query estimation methods based on beam search, importance sampling, and hybrids. Across four large-scale sequence datasets from different application domains, as well as for the GPT-2 language model, we demonstrate the ability to make query answering tractable for arbitrary queries in exponentially-large predictive path-spaces, and find clear differences in cost-accuracy tradeoffs between search and sampling methods.

Predictive Querying for Autoregressive Neural Sequence Models
Alex Boyd*
Sam Showalter* 2
Stephan Mandt
Padhraic Smyth
Department of Statistics
DDeartmennt of Computer Science
University of California, Irvine
(alexjb, shovalte mandt, ,p smyth) edu
Abstract
In reasoning about sequential events it is natural pose probabilistic queries such as "when will event A occur next" or "what the probability of A occurring before B," with applications in areas such as modeling, language models, medicine, and finance. These types of queries are complex to answer compared to next-event prediction, particularly for neural autoregressive models such as recurrent neural networks and transformers. This is in part due to the fact that future querying involves marginalization over large path spaces, which is not straightforward do efficiently in such models. In this paper we introduce a general typology for predictive queries neural autoregressive sequence models and show that such queries can be systematically represented by sets of elementary building blocks. We leverage this typology to develop new query estimation methods based on beam search, importance sampling, and hybrids. Across four large-scale sequence datasets from different application domains, as well as for the GPT-2 language model, we demonstrate the ability to make query answering tractable for arbitrary queries in exponentially-large predictive path-spaces, and find clear differences cost-accuracy tradeoff' between search and sampling methods.
Introduction
One of the major successes machine learning in recent years has been the development of neural sequence models for categorical sequences, particularly in natural language applications but also in other areas such automatic code generation and program synthesis [Shin al., 2019. Chen et al., 2021], computer security [Brown et al., 2018), 8J, recommender systems [Wu et al., 2017], genomics [Shin al., 2021, Amin et al., 2021], and survival analysis [Lee et al., 2019]. Many of the models (although not all) rely on autoregressive training and prediction, allowing for the sequential generation of sequence completions in a recursive manner conditioned on sequence history.
natural question in this context is how to compute answers to predictive queries that go beyond traditional one-step-ahead predictions. Examples of such queries are "how likely is event A occur before event B?" and "how likely is event C to occur (once or more) within the next K steps of the sequence?" These types of queries are very natural across a wide variety of application contexts, for example, the probability that an individual will finish speaking or writing a sentence within the next K words, or that user will use one app before another. See Fig. and Appendix G for examples.
In this paper we develop a general framework for answering such predictive queries in the context of autoregressive (AR) neural sequence models. This amounts to computing conditional probabilities of propositional statements about future events, conditioned on the history of the sequence as summarized by the current hidden state representation. We focus in partieular how perform near
Authors contributed equally
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

History H
K X-1 Unknown Tokens, O(V Poessbilites
Query Event
Token:
In
opinion
???
!??
???
???
<EO>>
Inder:
"In my opinion"
"Hi, my name is'
0.33
0.00
"Oace upon
Wheere
0.000
0.823
016
1o Steps into Sequence
20
10
20 Steps inso Sequennee K
K
Figure I: (top) Illustration of query for the probability of given sentence "In my opinion... ending in K steps. (bottom) GPT-2 query estimates across prefixes with V 50, 257, K - 30. Importance sampling query estimates maintain 6x reduction in variance relative to naive model sampling for the same computation budget. Open-ended prefixes (top-left) generally possess longer-taile tailed distributions relative to simple prefixes. Additional details provided in Sections 4, 5, and Appendix H.5.
real-time computation of such queries, motivated by use-cases such as answering human-generater queries and utilizing query estimates within the optimization loop of training a model. Somewhat surprisingly, although there has been extensive prior work on multivariate probabilistic querying in areas such as graphical models and database querying, well for restricted types of queries for traditional sequence models such as Markov models, querying for neural sequence models appears to be unexplored. One possible reason is that the problem is computationally intractable in the general case (as we discuss later in Section 3), typically scaling as O (VVK- k-) or worse for predictions K K-steps ahead, given sequence model with V-ary alphabet (e.g. compared (KV)) for Markov chains).
Our contributions are three-fold:
1. We introduce and develop the problem of predictive querying in neural sequence models by reducing complex queries to building blocks im the form of elementary queries. These elementary queries define restricted path spaces over future event sequences.
2. We show that the underlying autoregressive model can always be constrained to the restricted path space satisfying given query. This gives rise to a novel proposal distribution that can be used for importance sampling, beam search, new hybrid approach.
3. We evaluate these methods across three user behavior datasets and two language datasets. While all three methods significantly improve over naive forward simulation, the hybrid approach further improves over importance sampling and beam search. We furthermore explore how the performance of all methods relates the model entropy.
Code for this work is available at http://giihubbcomm/bboo/////ppp queries.
2 Related Work
Research on efficient computation of probabilistic queries has a long history in machine learning and AI, going back to work on exact inference in multivariate graphical models [Pearl, 1988, Koller and Friedman, 2009]. Queries this context are typically two types. The first conditional probability queries, which are the focus of our attention here: computing probabilities defined for subset X of variables of interest, conditioned on a second subset Y y observed variable values, and marginalizing over the set Z of all other variables. The second type of queries can broadly be referred to as assignment queries, seeking the most likely (highest conditional probability) assignment of values for X, again conditioned on Y y and marginalizing over the set Z. Assignment queries are also referred to as most probable explanation (MPE) queries, or as maximum a posteriori (MAP) queries when Z is the empty set [Koller et al., 2007].

---

V= (a,b,c)
Q (a)3)((a) 3) (b,c) x (b,c) x {a}
Figure 2: (left) Tree diagram of the complete sequence space for vocabulary V {a, b, of and the corresponding query space Q (right) for when the first appearance of a occurs on the third step (i.e., r(a) 3), defined the set product of restricted domains listed below the figure.
For models that can be characterized with sparse Markov dependence structure, there is significant body of work on efficient inference algorithms that can leverage such structure [Koller and Friedman, 2009], in particular for sequential models where recursive computation can be effectively leveraged [Bilmes, 2010]. However, autoregressive neural sequence models are inherently non-Markov since the real-valued current hidden state is function of the entire history of the sequence. Each hidden state vector induces tree containing VK unique future trajectories with Mate-dependent probabilities for each path of length K. Techniques such as dynamic programming (used effectively in Markov- structured sequence models) are not applicable in this context, and both assignment queries and conditional probability queries are NP-hard in general Chen et al. [2018].
For assignment-Vv type queries there has been considerable work in natural language processing with neural sequence models, particularly for the MAP problem of generating high -uighhuulttyhhighhao protibb-rrbbbbiityy sequences conditioned on sequence history or other conditioning information. variety of heuristic decoding methods have been developed and found to be useful in practice, including beam search [Sutskever et al., 2014], best-first search [Xu and Durrett, 2021], sampling methods [Holtzman et al., 2019], and hybrid variants [Shaham and Levy, 2022]. However, for conditional probability queries with neural sequence models (the focus of this paper), there has been no prior work in general on this problem to our knowledge. While decoding techniques such as beam search can also be useful in the context conditional probability queries, as we will see later Section 4, such techniques have significant limitations in this context, since by definition they produce lower-bounds on the probabilities of interest and, hence, are biased estimators.
3 Probabilistic Queries
XN] be sequence of random variables with arbitrary length N. Additionally, let T1:N == [21, [2,, T2,...,... [IN] be their respective observed values where each d; takes values from fixed vocabulary V == {1...., V). Examples of these sequences include sentences where each letter or word is a single value, or streams of discrete events generated by some process user. We will refer individual variable-value pairs in the sequence events.
Notation Let XI.N :=
We consider an autoregressive model po (X1.)) N trained on a given dataset of M independent draws from a ground truth distribution TP ((()::). We assume that this model can be conditioned the indices of subsequent random variables to start at the first position?. We abbreviate conditioning on a history by an asterisk i.e., (+) = P(-[H) and p-(-) == (-(-)
(o(X X1:i-1), parameterized by 0 and
subsequence, termed the history H. We will remap
Defining Probabilistic Queries Given specific history of events H. there are variety of different questions one could ask about the future continuing where the history left off: (Q1) What event likely to happen next? (Q2) Which events are likely to occur K > steps from now? (Q3) What is the distribution of when the next instance of a E V occurs? (Q4) How likely is it that we will see event E V occur before b E V? (Q5) How likely is it for E V to occur times in the next K steps?
For example, if [M] = 3 then P(X,(H) is the distribution of the 7 value in a sequence after conditioning the first 3 values in the sequence.
3

---

Question
Probabilistic Query
Cost (K 1Q]
Q1 Next event?
1))
Q2 Event K steps from now?
(T(Xx)
O(VK-1)
Q3 Next instance of a?
PT(T(a)= = Pā(T(a) T(6))
((V-1))-1
Q4 Will happen before 6?
O(V- ))
Q5 How many instances of a in K steps? p7 (K) = =n)
(V
Table I: List of example questions, corresponding probabilistic queries, and associated costs of exact computation computation with an autoregressive model. The cost of accommodating a history H. is assumed to be additive constant for all queries. While Q4 extends to infinite time, the cost reported for computing a lower bound up to steps.
We define a common framework for such queries by defining probabilistic queries to be of the form (5 I:K Q) with Q yk_ This be extended to the infinite setting (i.e., Pō ([Xx] Q)
where Q C Voc). Exact computation of an arbitrary query is straightforward to represent:
K II px, =x| Iek). (1)
Po(XI:K E Q)
Σ x = z1:K)= =1,k) FL
Σ E0
Depending on |2) performing this calculation can quickly become intractable, motivating lower bounds or approximations (developed in more detail in Section 4). In this context it is helpful to impose structure on the query Q make subsequent estimation easier, in particular by breaking Q into the following structured partition:
Q = U where ((i) n Q(5) for j and ((1) 1(()
(2)
x ((( where v c V for ......K.
(3)
In words. this means a given query Q be broken into a partition of simpler queries 2 which take the form of a set cross product between restricted domains () one domain for each token X An illustration of an example query set be seen in Fig. 2. natural consequence of this is that:
P E 2)= -0=Erā
E 2 E (XI:
Σ pe (NEE E 2)
which lends itself to more easily estimating each term in the sum. This will be discussed in Section 4.
Queries of Interest All of the queries posed earlier in this section can be represented under the framework detailed in Eq. (2) and Eq. (3), as illustrated in Table 1.
Q1 & Q2 The queries p (X = a) and Pã(Xx a) for some V can be represented with Q = [a} and Q = 4k-1 {a} respectively.
Q3 The probability of the next instance of V occurring some point in time K
(a()(a)= = K) where 7(-) is the hitting time, can be represented as Q = (V (at)K-1 x {a}. This can be adapted for set A C / by replacing {a} in with A.
Q4 The probability of a E occurring before b V, P)(T(a) < 7(b)), is represented as @ = , g(0 where ( = (V \ (a,b))*- x {a}. Lower bounds to this can be computed by limiting i < /' Like Q3, this also be extended to disjoint sets A, B C V.
Q5 The probability of
occurring n times the next K steps, P5 (K) n), is represented ")),)) ((t), where N, N.(K)
( is random variable for the number of occurrences of events of type from steps 1 to K and Qit''s are defined to cover all unique permutations of orders of products composed of: {a}" and (V) {a)) K-n, Like above, this can easily be extended for C V.
Q -
Ideallyy the partitioning chosen to have the smallest number of (60's needed.

---

Query Complexity From Eq. (1), exact computation of query involves computing K conditional distributions (e.g.. (xxXx [x =<+)) an autoregressive manner. Under the struc-
[Q]
tured representation, the number of conditional distributions needed is equivalently E. E.Il 1
Non-attention based neural sequence models often define px{X&| = x<x) := (ha where h4 RNN RN 11- As such, the computation complexity for any individual conditional distribution remains constant with respect to sequence length. We will refer to the complexity of this atomic action being (11). Naturally, the actual complexity depends and has a multiplicative scaling on the cost of computing a query. The number of atomic operations needed to exactly compute Q1-Q5 for this class of models can be found in Table 1. Should po be an attention-basee
the model architecture
model (e.g., a transformer [Vaswani et al., 2017]) then the time complexity of computing single one-step-ahead distribution becomes ( further exacerbating the exponential growth of many queries. Note that with some particular parametric forms of pa. query computation can be more efficient, e.g., see Appendix C for discussion on query complexity for Markov models.
4 Query Estimation Methods
Since exact query computation can scale exponentially in K it is natural to consider approximation methods. In particular we focus on importance sampling, beam search, and a hybrid of both methods. All methods will be based on novel proposal distribution, discussed below.
4.1 Proposal Distribution
For various estimation methods which will be discussed later, it is beneficial to have a proposal distribution q(11, = II:KK whose domain matches that of the query Q. For importance sampling, we will need this distribution as a proposal distribution, while we use it as our base model for selecting high-probability sequences in beam search. We would like the proposal distribution to resemble our original model while also respecting the query. One thought is to have (X1.x = x1.k) (X Z1.k X1.K Q). However, computing this probability involves normalizing over p5 (X E Q) which is exactly what we are trying to estimate in the first place. Instead of restricting the joins distribution the query, we can instead restrict every conditional distribution to the query's 's restricted domain. To see this, we first partition Q = U U,Q()) and define an autoregressive
proposal distribution for each ((+) = I ( as follows:
K
1 (XI: = TI.K) = II Pe (x = 2/ 2x Xek = sck: Xa E VV!0)
(4)
k=1
K pt (Xx = 2x xx*
= x<c) 1 T E E
k=1 Everte Pb x F(ck)
where 1(-) is the indicator function. That is, we constrain the outcomes of each conditional prob- ability to the restricted domains ( and renormalize them accordingly. To evaluate the proposal distribution's 's probability, we multiply all conditional probabilities according to the chain rule. Since the entire distribution is computed for a single model call P (Xx = x x<c)), is possible to both sample a K K-length sequence and compute its likelihood under (0) with only model calls. Thus, we can efficiently sample sequences from a distribution that is both informed by the underlying model pe and that respects the given domain Q. As discussed in the next section, this proposal will be used for importance sampling and for the base distribution which beam search is conducted.
4.2 Estimation Techniques
Sampling One can naively sample any arbitrary probability value using Monte Carlo samples to estimate (xx E Q) = >Epp (X < 2] however, this typically will have high variance. This can be substantially improved upon by exclusively drawing sequences from the query space Q. Arbitrary queries can be written as a sum of probabilities of individual sequences, as seen in Eq. (1). This summation can be equivalently written as an expected value.
(X E +Q) = Σ
Pō = FI.K) = [인] Ez Po = I1KK)],
ZiKER
5

---

where U/ is uniform distribution. It is common for p to concentrate most of the available probability mass on a small subset of the total possible space yk Should [ be large, then [2] p = x1:k)
will have very large variance for 21:K ())). One way to mitigate this is to use importance sampling with our proposal distribution q (Section 4.1):
Po(XIx = TI.K)
(X E 2) = =Q] Ex)xx(((()) [X = x1Ix)] = BriKKig
q(XI:K = =IIK)
M M m=1
Pa
XI:X = 11:K
(m)
(1) for 11K
(Md) iid "1:K
9 [1IKK = =1.KK (m)
q.
It is worth noting that this estimator could be further improved by augmenting the sampling process to produce samples without replacement from q (e.g., [Meister et al., 2021, Kool et al., 2019, Shi et al., 2020]): in this paper we restrict the focus to sampling with replacement.
Search
An alternative to estimating a query by sampling is to instead produce a lower bound,
XXLK E Q)
Σ P5(X = FL.K >
Σ Po(X x1.K),
where B C Q. In many situations, only a small subset of sequences 21.K in Q have non- oonnegligiible probability of occurring due to the vastness of the total path space VK As such, it is possible for
[ <<< Q while still having minimal gap between the lower bound and the actual query value.
One way to produce a set B C Q is through beam search. To ensure that beam search only explores the query space, instead of searching with Pe, we utilize q for ranking beams. Since beam search is greedy algorithm and for given conditional (Xx, = a xx) x (X = al xx) for a E Vs, the rankings will both respect the domain and be otherwise identical to using pe to rank. Typically, the goal of beam search is to find the most likely completion of a sequence without having to explore the entire space of possible sequences. This is accomplished by greedily selecting the top- B most likely next step continuations, or beams, at each step into the future. Rather than finding a few high-likelihood beams, are more interested in accumulating significant amount of probability mass and less interested in the specific quantity of beams collected.
Traditional beam search has fixed beam size B; however, this is not ideal for accumulating probability mass. As an alternative we develop roverage-based beam search where at each step in a sequence we restrict the set of beams being considered not to the top-B but rather to the smallest set of beams that collectively exceed a predetermined probability mass a, referred to as the "coverage". 4 More specifically, let B& C {T | E Q) be set containing [Bx| beams for subsequences of length k. For brevity, we will assume that Q = V1 x ... x Vx. B&+1 is a subset of B₃ x Vk+1 and is selected specifically minimize [Bx+1| such that 1(1::4+1 E BB+1) 2 a. It can be shown that P (X1.K E Q) p& (X1.K E Bx) < 1 - g(X..K E Bx) (and is often significantly less). See Appendix B for a proof.
There is one slight problem with having a be constant throughout the search. Since we are pruning based on the joint probability of the entire sequence, any further continuations of B, will reduce the probability ( E 12+1). This may lead to situations in which every possible candidate sequence is kept in order maintain minimal joint probability coverage. This can be avoided by filtering by ag where 01 > ... > ag- = e.g., the geometric series = k/K
A Hybrid Approach Importance sampling produces an unbiased estimate, but can still expe- rience large variance in spite of a good proposal distribution when Pa is a heavy tailed distri- bution. Conversely, the beam search lower bound can be seen as a biased estimate with zero variance. We can remedy the limitations of both methods by recognizing that since P5(X1:K E Q) En, & BBg (x: = xι:x) + Ex, EQUB, P (Xx: = Z1.k). ). where Bx is the of sequences resulting from beam search, we can use importance sampling on the latter summation. The only caveat to this is that the proposal distribution must match the same domain of the summation: Q |BK
"This is similar the distinction between top-K and top-p/ / nucleus sampling commonly used for natural language generation [Holtzman et al., 2019].
'f Q requires partitioning into multiple (()ss apply beam search to each sub query (x(xI (()).

---

The proposal distribution we use to accomplish this is q(X1xX = -i:k T1:K|XI.K [X1: & Bx) ) (see Eq. 4). This is implemented by storing all intermediate distributions (both original Po and proposal q) found during beam search and arranging them into a tree structure. All leaf nodes that are associated with 21:K E Bxx have their transition probability zeroed out and then the effect of restriction and normalization is propagated up the tree to their ancestor nodes (details provided in Appendix D and E). Sampling from this new proposal distribution involves sampling from this normalized tree until we reach either an existing K K-depth leaf node, in which case we are done, or a < K K-depth leaf node in which case we complete the rest of the sequence by sampling from q in Eq. (4) as usual.
Lastly, since our ultimate goal is to sample from the long tail of pe, targeting specific coverage during beam search is no longer effective since achieving meaningfully large coverage bounds for non-trivial path spaces is generally intractable. Instead, we propose tail- mail-splitring beam search to better
(5) match our goals. Let w(() (X 1+++ x1:4+1 for Fisk+1 E B& VK+1 such that w
(8)
(8) Z wk
(5) if
i < In this regime, B = ( f
1 where B arg ming a (())))) + oww ( (b+1:188 x Ve+ell).
(w (ue))))) is the empirical variance of w for = u, ..... This can be seen performing 2-means
clustering on the wp 's and taking the cluster with the higher cumulative probability.
4.3 Saving Computation on Multiple Queries
Should multiple queries need to be performed, such as (T = k) for multiple values of k. then there is potential to be more efficient in computing estimates for all of them. The feasibility of reusing intermediate computations consider two base queries Q = 111
dependent on the set of queries considered. For simplicity, we will Vx and Q' = V
Vx where K < K'. Due to the autoregressive nature of pe, if V. = Vi for i = 1,..., K 1 then all of the distributions and sequences needed for estimating p5 (X1,K 1:K Q) are guaranteed to be intermediate results found when estimating P5( ( XI:K* E )²) To be explicit, when estimating the latter query with beam search the intermediate 3& is the same what would be directly computed for the former query. Likewise, for importance sampling if 11.K' ~ (({1xx)) using Eq. (4) then the subsequence T1:K ~ (X1:x) This does not apply when the sample path domain further restricted, such with the hybrid approach, in which case we cannot directly use intermediate results to compute other queries for "free."
5 Experiments and Results
Experimental Setting We investigate the quality of estimates of hitting time queries across various datasets, comparing beam search, importance sampling, and the hybrid method. We find that hybrid systematically outperforms both pure search and sampling given comparable computation budget across queries and datasets. We also investigate the dependence of all three methods on the model entropy.
It is worth noting that we focus almost exclusively on hitting time queries in our primary experiments, as more complex queries often decompose into operations over individual hitting times. For example. consider the following decomposition of the "A before B" query (Q4):
(ā(T(a) < <b)) Σ = k(,() k)
x ( (a,b))=-1)
Decompositions of other queries and their impact on approximation error are found in Appendix A.
Datasets We evaluate our query estimation methods on three user behavior and two language sequence datasets. Reviews contains sequences of Amazon customer reviews for products belonging to one of V 29 categories [Ni al., 2019]; Mobile Apps consists of app usage records over V= 88 unique applications [A [Aliannejadi et al., 2021]; MOOCs consists of student interaction with online course resources over V = 98 actions [Kumar et al., 2019]. We also use the works of William Shakespeare [Shakespeare] by modeling the occurrence of V = 67 unique ASCII characters. Lastly, we examine WikiText [Merity et al., 2017] to explore word-level sequence modeling applications with GPT-2, a large-scale language model with vocabulary of V = 50257 word word-pieces [Radford et al., 2019, Wu et al., 2016). After preprocessing, none of the datasets contain personal identifiable information.
7

---

Median Retauive Abs. Etror
Reviews
MOOCs
Shalesprare
Mobile Apgs
Iappettaac Stappiigg Searci
Bylost
0.4
Figure 3: Median relative absolute error (RAE) between estimated probability and (surrogate) ground truth for (T+) K) for importance sampling, beam search, and the hybrid method. As query path space grows with K, beam search quickly fails to bound ground truth while sampling remains robust, with the hybrid consistently outperforming all other methods, especially for large values of K. Ground truth values used to determine error are exact for K < 4 and approximated otherwise.
Base Models While our proposed methods are amenable to autoregressive models of arbitrary structure, we focus our analysis specifically on recurrent neural networks. For all datasets except WikiText, we train Long-short Term Memory (LSTM) networks until convergence. To explore modern applications of sequence modeling with WikiText, we utilize GPT-2 with pre-trained weights from HuggingFace [Wolf et al., 2020]. Model training and experimentation utilized roughly 200 NVIDIA GeForce 2080ti GPU hours. Please refer to Appendix F for additional details.
trade-offs between 3 estimation methods (beam search, importance sampling, and the hybrid) across all datasets. Query histories H are defined by randomly sampling N 1000 sequences from the test split for all datasets except Wiki'eex,, from which we sample only N = 100 sequences due to computational limitations. For each query history and method, we compute the hitting time query estimate Pă (T()) = K') over K =....., 11, with determined by the T symbol of the ground truth sequence.
Experimental Methods We investigate computation-accunt
To ensure an even comparison of query estimators, we fix the computation budget per query in terms of model calls (ha) to be equal across all methods, repeating experiments for different budget magnitudes roughly corresponding to O(10), O(10²), O11*)) model calls (see Appendix H for full details). We intentionally select relatively small computation budgets per query support systematic large-scale experiments over multiple queries up to relatively large values of K. Results for queries with GPT-2 are further restricted because of computational limits and are reported separately below.
To evaluate the accuracy of the estimates for each query and method, we compute the true probability of K using exact computation for small values of K < 4. For larger values of K, sampling with a large number of samples S, where is adapted per query to ensure the resulting unbiased estimate has empirical variance less than << 1 (see Appendix F.3). This computationally- expensive estimate is then used as a surrogate for ground truth in error calculations.
importance
Coverage-basse based beam search is not included in our results: we found that it experiences exponential growth with respect to K and does not scale efficiently due to its probability coverage guarantees. Additional details are provided in Appendix H.3.
Results: Accuracy and Query Horizon Using the methodology described above, for each query, we compute the relative absolute error (RAF) Ip pl/p. where is the estimated query probability generated by a particular method and p is the ground truth probability or the surrogate estimate using importance sampling. For each dataset, for each of the 3 levels of computation budget, for each value of K, this yields N 1000 errors for the N queries for each method.
Fig. 3 shows the median RAE of the N queries, per method, as a function of K, for each dataset, using the medium computation budget in terms of model calls. Across the datasets the error increases systematically as K increases. However, beam search is significantly less robust than the other methods for of the datasets: the error rate increases rapidly compared importance sampling and hybrid. Beam search is also the most variable across datasets relative to other methods. The hybrid method systematically outperforms importance sampling along across all datasets and for all values of K. In Appendix H we provide additional results; for the lowest and highest levels of computational
8

---

Reviows
MOOCS
Metkal
Belasbve
Median Relnttiv Abe. Itroe
Inpertano Stcpling
Biar Seuch
Abs
1.4
Shakespeure
Mjabae Apps
Redative Abs
Netted
12
0.3
Iaeportazac Sampping
Boien Seard.
1.50
Restricted Entrogy
Restaicted Entroggy
Temperatune (b)
(4)
Figure 4: (left) RAE vs restricted entropy per query (with best linear fits), (right) Median RAE versus model temperature T for Mobile App data. All errors computed using the same queries as in Fig. 3. Beam search errors correlate highly with model entropy even with the low-entropy Mobile Apps dataset, where increasing temperature T directly induces this failure mode.
Reviews
MOOCs
Shakespeare
Mobile Appe
25
Meddia Eilidescy
32-
16-
K
Figure 5: Median relative efficiency (over 1000 query histories and all vocabulary terms) of impor- tance sampling estimation of the K-step marginal distributions for each dataset. The gray, dotted line represents 100% relative efficiency defined by naive query estimation. Relative efficiency is docu- 15 to highlight the regime where ground truth cannot be tractably computed.
mented for 4 < K <
budget, for mean (instead of median) RAEs, and scatter plots for specific values of K with more detailed error information. The qualitative conclusions are consistent across experiments.
The Effect of Model Entropy We conjecture that the entropy of the proposal distribution q conditioned on a given history H; (X1:x) = - q (X1:K x1:x)), which we refer to as restricted entropy, is major factor in the performance of the estimation methods. Fig. 4(a) shows the RAE per query (with a linear fit) as a function of estimated restricted entropy for importance sampling and beam search. The results clearly show that entropy is driving the query error in general and that the performance of beam search is much more sensitive to entropy than sampling. The difference in entropy characteristics across datasets explains the differences in errors we see in Fig. 3. In particular, the Mobile Apps dataset is in a much lower entropy regime than the other three datasets.
Results:
To further investigate the effect of entropy, we alter each model by applying a temperature T >> 0 to every conditional factor: pe, Pe.r(Xx|X<2 & pe (Xx =x effectively changing the entropy ranges for the models. Fig. 4(b) shows the median RAE, for query P/ r (r(-) 4), function of model temperature for the Mobile Apps data. As predicted from Fig. 4(a), the increase in T, and corresponding increase in entropy, causes beam search's error to converge to 1, while the sampling error goes to 0. As 7' increases, each individual sequence will approach having 1/ mass, thus needing many more beams to have adequate coverage. Results for other queries and the other three datasets (in Appendix H) further confirm the fundamental bifurcation of error between search and sampling (that we see in Fig. 4(b)) as a function of entropy.
Results: Relative Efficiency of Proposal Distribution over Naive Query Estimation We also examine the relative efficiency improvements of our proposal distribution against naive Monte Carlo sampling:
pg (X E Q) Ernxe [[ILK 2)

---

Our relative efficiency calculations in Fig. 5 represent the variance ratio of naive query estimates and estimates from our query proposal distribution. As shown, all datasets witness improvement over naive sampling efficiency and often by significant margin. We also observe that relative efficiency largest for shorter query horizons, approaching naive sampling efficiency as K increases.
Results: Queries with Large Language Model We further explore entropy's 's effect query estimation with GPT-2 and the WikiText dataset for N = 100, K = 3, 4, across 3 computation budgets. With vocabulary 500x larger than the other models, GPT-2 allows to examine queries relevant to NLP applications. The resulting high entropy causes beam search to fail to match surrogate ground truth given the computation budgets (consistent with earlier experiments), with a median RAE of 82% (for K = 4 and a budget of (110)).. By contrast, importance sampling's 's median RAE under the same setting is 13%, 6x reduction. Additional results are in Appendix H.5.
Discussion
This work provides starting point for multiple different research directions beyond the scope of this paper. One such direction is exploring more powerful search and sampling methods for query estimation. This includes methods for sampling without replacement, such as the Gumbel-max method [Huijben et al., 2022, to appear], sampling importance-resampiing (SIR) [Skare et al., 2003], as well new heuristics for automatically trading off search and sampling per-query basis. Another direction for exploration is amortized methods, such as learning models before queries are issued, that are specifically designed help answer queries. Learning models that include queries as part of regularization terms in objective functions can also build on this work, c.g., learning models that don't only rely on one-step-ahead losses [Meister and Cotterell, 2021]. The work in this paper has also recently been broadened to continuous-ting models for marked temporal point processes (requiring marginalization over time as well as event types) [Boyd et al., 2022].
Future Directions:
Limitations: Our results rely on only four datasets with single autoregressive neural sequence model trained for each, naturally limiting the breadth of conclusions that we can draw. However, given that the results are consistent and validated by ggorithm-inddpendeee analyses, we believe these findings have general validity and provide a useful starting point for others interested in the problem of querying neural sequence models. Another potential limitation is that our four datasets have relatively small vocabularies (V O(10²). small by NLP standards at least); this choice was largely driven by computational limitations in terms of being able to conduct conclusive experiments (e.g. averaging over many event histories). Our (limited) results with GPT-2 provide clues what may be achievable with much larger vocabularies: systematic analysis of querying for such models is a natural target for future work. Our work also does not address the issue of model inaccuracy: our results are entirely focused on computing query estimates in terms of model's distribution instead of the data-generating process. Exploring the effect of miscalibration errors in autoregressive models on k-step-aheea query estimates is a promising avenue for future work.
entropy and efficiency
Since the focus of this work is making predictions with data that is typically generated by individuals (language, online activity), there is naturally a potential for abuse of such methods. For example, if the underlying model in system is miscalibrated, decisions could be made that negatively impact individuals, e.g., recommending a student be dropped from an online course if the model incorrectly predicts they will not participate in future course modules. Even if the underlying model is well-calibrated, predictive queries could potentially be used in a proactive manner to bias decisions against individuals whose event sequences are atypical, e.g., in chatbot context, inaccurately predicting future language patterns for certain individuals, leading to interruption and generation of an inappropriate response.
Potential Negative Societal Impacts:
Acknovledgements: We thank the NeurIPS reviewers for their suggestions on improving the original version of this paper. This work was supported by National Science Foundation Graduate Research Fellowship grant DGE-1839288 1839285 (AB and SS), by an NSF CAREER Award (SM), by the National Science Foundation under award numbers 1900644 (PS). 2003237 (SM), and 2007719 (SM), by the National Institute of Health under awards 801-AG005330-0023 and R01-LM01332 the Department of Energy under grant DE-SC0022331 (SM), by the HPI Research Center in Machine Learning and Data Science at UC Irvine (SS), and by Qualcomm Faculty awards (PS and SM).
(PS), by
10

---

References
Mohammad Aliannejadi, Hamed Zamani, Fabio Crestani, and W. Bruce Croft. Context-aware target apps selection and recommendation for enhancing personal mobile assistants. ACM Trans. Inf. Syst, 39(3):1 - -30, May 2021.
Alan Amin, Eli N Weinstein, and Debora Marks. A generative nonparametric Bayesian model for whole genomes. Advances in Neural Information Processing Systems, 34:27798-27812,220 2021.
Jeff Bilmes. Dynamic graphical models. IEEE Signal Processing Magazine, 27(6):29 42, 2010.
Alex Boyd, Yuxin Chang, Stephan Mandt, and Padhraic Smyth. Probabilistic querying of continuous- time event sequences. arXiv preprint wrxiv:2211.084455 2022.
Andy Brown, Aaron Tuor, Brian Hutchinson, and Nicole Nichols. Recurrent neural network attention mechanisms for interpretable system log anomaly detection. In Proceedings of the First Workshop Machine Learning for Computing Systems, pages 1-8, 2018.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 2021.
Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. Recurrent neural networks as weighted language recognizers. NAACI-HILT, pages 2261 2261-2271, 01 2018. doi: 10.18653/v 1/N18-1205.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2019.
Iris AM Huijben, Wouter Kool, Max Benedikt Paulus, and Ruud JG Van Sloun. A review of the Gumbel-max trick and its extensions for discrete stochasticity in machine learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, appear.
John Kemeny and J Laurie Snell. Finite Markov Chains. Springer, 3rd edition, 1983.
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA, 2009.
Daphne Koller, Nir Friedman, Lise Getoor, and Ben Taskar. Graphical models in a nutshell. In Introduction Statistical Relational Learning. MIT Press, Cambridge, MA, 2007.
Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where to find them: The Gumbel-top-k trick for sampling sequences without replacement. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3499-3508. PMLR. 09-15 Jun 2019, URL https: sstts::/pprceedinggg mlr wwwpp//ee9//// /Tros//97//ool19a.. html.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1269-1278. ACM, 2019.
Changhee Lee, Jinsung Yoon, and Mihaela Van Der Schaar. Dynamic-deephit. A deep learning approach for dynamic survival analysis with competing risks based longitudinal data. IEEE Transactions on Biomedical Engineering, 671)::22-133,, 2019.
Clara Meister and Ryan Cotterell. Language model evaluation beyond perplexity. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th In- ternational Joint Conference Natural Language Processing (Volume I: Long Papers), pages 5328 5328-5339, 2021.
Clara Isabel Meister, Afra Amini, Tim Vieira, and Ryan Cotterell. Conditional Poisson stochastic beams. Proceedings of the 2021 Conference on Empirical Methods Natural Language Processing, pages 664-681. Association for Computational Linguistics, 2021.

---

Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. Arxiv Preprint, arXiv:1609.07843, 2017.
Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly-labeled reviews and fine-grate ime-grained aspects. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP- -JCCLP)) pages 188-197, Hong Kong, China, November 2019. Association for Computational Linguisties.
Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Lan- guage models are unsupervised multitask learners. 2019. URL http::tt///opanaicooom com/booo// better- Lantuar- models/.
Uri Shaham and Omer Levy. What do you get when you cross heam search with nucleus sampling? arXiv preprint arXiv:2107.09729, 2022.
William Shakespeare. The Complete Works of William Shakespeare: Project Gutenberg. https: // ocw.mit htt.a///www.....oo///ee/ee/eeeee wwwpeesss..ssaaaeeeeee..ee txt. Ac- cessed: 2020-04-11.
Kensen Shi, David Bieber, and Charles Sutton. Incremental sampling without replacement for sequence models. In International Conference Machine Learning, pages 8785-8795. PMLR, 2020.
Eui Chul Shin, Miltiadis Allamanis, Mare Brockschmidt, and Oleksandr Polozov. Program synthesis and semantic parsing with learned code idioms. In Proceedings of the 33rd International Confer- ence on Neural Information Processing Systems, pages 10825-10835, Red Hook, NY, USA, 2019. Curran Associates Inc.
Jung-Eun Shin, Adam Riesselman, Aaron W Kollasch, Conor McMahon, Elana Simon, Chris Sander, Aashish Manglik, Andrew C Kruse, and Debora S Marks. Protein design and variant prediction using autoregressive generative models. Nature Communications, 12(1):1-11, 2021.
Øivind Skare, Erik Bølviken, and Lars Holden. Improved sampling-importance resampling and reduced bias importance sampling. Scandinavian Journal of Statistics, 30(4):719-737, 2003.
Ilya Sutskever, Oriol Vinyals, and Quoe Le. Sequence to sequence learning with neural networks. Advances in Neural Information Processing Systems, 27:3104 - 3112, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 1266000-6010 2017.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac. Tim Rault, Rémi 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 M. Rush. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing: System Demonstrations, pages 38 45, Online, 2020. Association for Computational Linguistics. URL https::///// http://wwwwwwww.w.////:... aclweb. org/ anthologh /200 mamlp-demoss 6.
Chao- Yuao-Yuan Wu, Amr Ahmed, Alex Beutel, Alexander Smola, and How Jing. Recurrent recom- mender networks. In Proceedings of the tenth ACM international conference on web search and data mining, pages 495-503, 2017.
Yonghui Wu, Mike Schuster, Z. Chen, Quoe V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason R. Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Gregory S. Corrado, Macduff Hughes, and Jeffrey Dean. Google's neural machine translation system: Bridging the gap between human and machine translation. ArXiv Preprint arXiv: 00100,008444.... abs/1609.00 08 144, 2016.
12

---

Jiacheng Xu and Greg Durrett. -assive-scale decoding for text generation using lattices. arXiv preprint orXiv2212.006660 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We mention computational resources, PII considerations, and other ethical factors in our paper directly.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
4
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material URL)? [Yes] Included in supplement as a .zip file
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] We gather data for multiple query histories and report median results for a given experimental setting.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section 5.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite all public datasets utilized.
(b) Did you mention the license of the assets? [Yes] Datasets used are all publicly available and the specific license is noted in the Appendix for each.
(c) Did you include any new assets either in the supplemental material as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] Datasets are publicly available.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes] See Section 5.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "lxrnbZzzMaN", "reviewer": "Reviewer_6x57", "summary": "The paper aims at solving a task called predictive querying, which aims at producing the probability that probabilistic queries such as “when will event A occur next” or “what is the probability of A occurring before B,” happens in an autoregressive (RNN/Transformer) model. The paper categorizes the probabilistic queries into five categories, and in principle, most of them are intractable with a nearly O(V^K) complexity, where V is the vocabulary size and K is the step size. The paper proposes two approaches to estimate the predictive querying, one is importance sampling, and the other is approximation within beam search. On empirical evaluation, a hybrid of these two techniques works the best on three user behavior and two language sequence datasets.\n", "questions": "1. Given the five probabilistic query categories, the paper only investigates the hitting time queries. Is the proposed method able to generalize to the other categories?\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The paper is the first work that studies predictive querying on modern autoregressive models, and provides effective estimation techniques including importance sampling and approximation in beam search to estimate the probability of these queries, with proven convergence.\n\n2. On several datasets across different domains, the paper shows that the proposed hybrid method achieves the best relative errors compared to the baseline methods.\n\n3. The paper shows that in general, the hybrid method is the best, but in lower entropy regimes such as Mobile Apps, the beam search approximation can outperform the importance sampling and hybrid method. Such a result is informative and may inspire further research.\n\nWeaknesses\n\n1. It is a bit unclear to me what queries and data the paper actually uses in the experiments. It would be better to demonstrate with a few text examples for each dataset.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "f1JYoo78VIm", "reviewer": "Reviewer_6TXq", "summary": "The paper introduces the problem of predictive querying in neural autoregressive models, where we answer probabilistic queries such as hitting time of an event wrt the model (not some ground truth). They propose an importance-sampling based framework and proposal distribution for estimating these queries, and also combine it with beam search for better results. The provide some understanding of the failures of beam search for predictive querying, including the correlation of beam search's error with the conditional entropy of the model.    ", "questions": "- The paper discusses coverage-based and tail splitting beam search (and perhaps claims it as a contribution?) but doesn't show its results, saying that it did not do well. Perhaps this is an extraneous part of the paper?  \n- While hitting time is a component of other queries, it could be interesting to see how the error compounds with multiple related queries. \n- One limitation is that the evaluation method requires an expensive computation of the true probabilities. Is there a different way to verify the performance of the query estimation on longer horizons? While it's clear that the IS approach is better than beam search, it's unclear how far it can go. One possibility is to sample sequences from the models where an event actually occurs, truncating this sequence K steps before the event occurs, and then evaluating the likelihood that the event occurs under the predictive query from the past (and average over many sequences).", "limitations": "They discuss the potential biases of using forecasting models for decision making, especially on data like student interactions as used in the paper. They also preprocess the datasets to not contain personally identifiable information.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper raises an important question about how to answer probabilistic queries about future steps, which could be applied to decision making systems that require some forecasting. They also provide a framework, baselines, and an improved hybrid method, as well as some understanding of why beam search approaches are worse. The paper is well written overall, though the explanation/motivation of the proposal distribution could be made clearer.\n- On originality, while the setup seems new for neural autoregressive models, the family of problems is well studied in the stochastic processes literature, survival analysis, etc, but as far as I know they usually assume some parametric form for the underlying probabilistic model / hazard function / etc. that is easier to work with. For neural models there is less structure to work with. \n- The paper shows a nice opposite behavior for beam search and Importance sampling methods, and proposes a hybrid approach that nicely combines the two for mutual benefits, using importance sampling to estimate the gap between the beam search lower bound and the true probability.\n- The paper considers a variety of sequences (text, interactions, usage records) and models (LSTMs, GPT2 (which one?) ).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CI0_J1iZaL", "reviewer": "Reviewer_yqp6", "summary": "This paper proposes a new problem for neural autoregressive sequence models: How do we query the model about probabilistic questions like \"what is the probability of A occurring before B\". Given a pretrained sequence model, it is usually intractable to query the model to answer those questions, so the paper proposes 2 estimation methods: importance sampling and beam search. The paper also tries to combine those 2 methods and finds that the combination of them achieves the best results.", "questions": "1. Given the sequence space can be large and the importance sampling has non-negligible variances, it is helpful to show the effective sampling size.\n2. How do you think of ISR (importance sampling resampling)? Resampling can significantly improve the coverage of the importance sampling and is unbiased, which can be a surrogate of the beam search.\n3. How do you balance importance sampling and beam search in the hybrid method? I wonder about the ratio of their sequences and possibly their contributions to the resulting probability (i.e. L202).", "limitations": "The societal impacts of this work are already discussed by the authors and I don't have further concerns.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem raised by this paper is interesting and was thought intractable before. The problem of token counting or the ordering of some tokens can be potentially useful for many real applications, e.g. finance and NLP.\n\nAlthough the methods in this paper are existing ones, certain tricks are applied to each of them, for example, coverage-based beam-search and tail-splitting search. The hybrid method combines the advantage of sampling and beam search, which yields the best results.\n\nThe paper is well-motivated and well-written and can be valuable for many other fields. However, it does come with certain drawbacks:\n\n1. The 2 methods used in the paper are existing ones and lack novelty. Applying them to the estimation of sequences is natural but less non-trivial.\n2. The definition of \"probabilistic queries\" is big and only parts of them are discussed in the paper. When the Q space gets larger, the estimation gets harder under the framework of this work. For example, the Q5 cannot be easily handled when C(K, n) gets large. In fact, only hitting time (Q3) is tested in section 5.\n3. Furthermore, the experiments are not sufficient and the actual metric relies on the sampling (L266). No baselines are available, which makes it hard to judge the contribution of this paper. A suggestion would be training a supervised model for each K to predict the hitting time.\n4. I have a few methodological concerns that are listed in the question section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept