Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents methods for query completion that includes prefix correction, and some engineering details to meet particular latency requirements on a CPU.  Regarding the latter methods: what is described in the paper sounds like competent engineering details that those performing such a task for launch in a real service would figure out how to accomplish, and the specific reported details may or may not represent the 'right' way to go about this versus other choices that might be made.  The final threshold for 'successful' speedups feels somewhat arbitrary -- why 16ms in particular?  In any case, these methods are useful to document, but derive their value mainly from the fact that they allow the use of the completion/correction methods that are the primary contribution of the paper.  

While the idea of integrating the spelling error probability into the search for completions is a sound one, the specific details of the model being pursued feel very ad hoc, which diminishes the ultimate impact of these results.  Specifically, estimating the log probability to be proportional to the number of edits in the Levenshtein distance is really not the right thing to do at all.  Under such an approach, the unedited string receives probability one, which doesn't leave much additional probability mass for the other candidates -- not to mention that the number of possible misspellings would require some aggressive normalization.  Even under the assumption that a normalized edit probability is not particularly critical (an issue that was not raised at all in the paper, let alone assessed), the fact is that the assumptions of independent errors and a single substitution cost are grossly invalid in natural language.  For example, the probability p_1 of 'pkoe' versus p_2 of 'zoze' as likely versions of 'poke' (as, say, the prefix of pokemon, as in your example) should be such that p_1 >>> p_2, not equal as they are in your model.  Probabilistic models of string distance have been common since Ristad and Yianlios in the late 90s, and there are proper probabilistic models that would work with your same dynamic programming algorithm, as well as improved models with some modest state splitting.  And even with very simple assumptions some unsupervised training could be used to yield at least a properly normalized model.  It may very well end up that your very simple model does as well as a well estimated model, but that is something to establish in your paper, not assume.  That such shortcomings are not noted in the paper is troublesome, particularly for a conference like ICLR that is focused on learned models, which this is not.  As the primary contribution of the paper is this method for combining correction with completion, this shortcoming in the paper is pretty serious.

Some other comments:

Your presentation of completion cost versus edit cost separation in section 3.3 is not particularly clear, partly since the methods are discussed prior to this point as extension of (possibly corrected) prefixes.  In fact, it seems that your completion model also includes extension of words with end point prior to the end of the prefix -- which doesn't match your prior notation, or, frankly, the way in which the experimental results are described.  

The notation that you use is a bit sloppy and not everything is introduced in a clear way.  For example, the s_0:m notation is introduced before indicating that s_i would be the symbol in the i_th position (which you use in section 3.3).  Also, you claim that s_0 is the empty string, but isn't it more correct to model this symbol as the beginning of string symbol?  If not, what is the difference between s_0:m and s_1:m?  If s_0 is start of string, the s_0:m is of length m+1 not length m.

You spend too much time on common, well-known information, such as the LSTM equations.  (you don't need them, but also why number if you never refer to them later?)  Also the dynamic programming for Levenshtein is foundational, not required to present that algorithm in detail, unless there is something specific that you need to point out there (which your section 3.3 modification really doesn't require to make that point).

Is there a specific use scenario for the prefix splitting, other than for the evaluation of unseen prefixes?  This doesn't strike me as the most effective way to try to assess the seen/unseen distinction, since, as I understand the procedure, you will end up with very common prefixes alongside less common prefixes in your validation set, which doesn't really correspond to true 'unseen' scenarios.  I think another way of teasing apart such results would be recommended.

You never explicitly mention what your training loss is in section 5.1.

Overall, while this is an interesting and important problem, and the engineering details are interesting and reasonably well-motivated, the main contribution of the paper is based on a pretty flawed approach to modeling correction probability, which would limit the ultimate applicability of the methods.
review_title: Solid engineering but poorly motivated modeling choices for query correction.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper focuses on solving query completion problem with error correction which is a very practical and important problem. The idea is character based. And in order to achieve three important targets which are auto completion, auto error correction and real time, the authors first adopt the character-level RNN-based modeling which can be easily combined with error correction, and then carefully optimize the inference part to make it real time.

Pros:
(1) the paper is very well organized and easy to read.
(2) the proposed method is nicely designed to solve the specific real problem. For example, the edit distance is modified to be more consistent with the task.
(3) detailed information are provided about the experiments, such as data, model and inference.

Cons:
(1) No direct comparisons with other methods are provided. I am not familiar with the state-of-the-art methods in this field. If the performance (hit rate or coverage) of this paper is near stoa methods, then such experimental results will make this paper much more solid.
review_title: This paper proposes a practical algorithm to solve query completion problem with error correction. The paper is very well written and easy to understand. Experiments show that the algorithm can run in real time on CPU.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors describe a method for performing query completion with error correction using a neural network that can achieve real-time performance. The method described uses a character-level LSTM, and modifies the beam search procedure with a an edit distance-based probability to handle cases where the prefix may contain errors. Details are also given on how the authors are able to achieve realtime completion.

Overall, it’s nice a nice study of the query completion application. The paper is well explained, and it’s also nice that the runtime is shown for each of the algorithm blocks. Could imagine this work giving nice guidelines for others who also want to run query completion using neural networks. The final dataset is also a good size (36M search queries).

My major concerns are perhaps the fit of the paper for ICLR as well as the thoroughness of the final experiments. Much of the paper provides background on LSTMs and edit distance, which granted, are helpful for explaining the ideas. But much of the realtime completion section is also standard practice, e.g. maintaining previous hidden states and grouping together the different gates. So the paper feels directed to an audience with less background in neural net LMs.

Secondly, the experiments could have more thorough/stronger baselines. I don’t really see why we would try stochastic search. And expected to see more analysis of how performance was impacted as the number of errors increased, even if errors were introduced artificially, and expected analysis of how different systems scale with varying amounts of data. The fact that 256 hidden dimension worked best while 512 overfit was also surprising, as character language models on datasets such as Penn Treebank with only 1 million words use hidden states far larger than that for 2 layers. More regularization required?
review_title: Nicely explained, could use more thorough experiments

Meta-review: This paper has some interesting ideas that have been implemented in a rather ad hoc way; the presentation focuses perhaps too much on engineering aspects.
Decision: Reject