Advancing planning and reasoning capabilities of Large Language Models (LLMs) is one of the key prerequisites towards unlocking their potential for performing reliably in complex and impactful domains. In this paper, we aim to demonstrate this across board games (Chess, Fischer Random / Chess960, Connect Four, and Hex), and we show that search-based planning can yield significant improvements in LLM game-playing strength. We introduce, compare and contrast two major approaches: In external search, the model guides Monte Carlo Tree Search (MCTS) rollouts and evaluations without calls to an external game engine, and in internal search, the model is trained to generate in-context a linearized tree of search and a resulting final choice. Both build on a language model pre-trained on relevant domain knowledge, reliably capturing the transition and value functions in the respective environments, with minimal hallucinations. We evaluate our LLM search implementations against game-specific state-of-the-art engines, showcasing substantial improvements in strength over the base model, and reaching Grandmaster-level performance in chess while operating closer to the human search budget. Our proposed approach, combining search with domain knowledge, is not specific to board games, hinting at more general future applications.

In the evolving landscape of scientific publishing, it is important to understand the drivers of high-impact research, to equip scientists with actionable strategies to enhance the reach of their work, and to understand trends in the use of modern scientific publishing tools to inform their further development. Here, based on a dataset of over 0.5 million publications in computer science and physics, we study trends in the use of early preprint publications and revisions on ArXiv and the use of X (formerly Twitter) for promotion of such papers. We find that early submissions to ArXiv and promotion on X have soared in recent years. Estimating the effect that the use of each of these modern affordances has on the number of citations of scientific publications, we find that peer-reviewed conference papers in computer science that are submitted early to ArXiv gain on average 21.1 ± 17.4 more citations, revised on ArXiv gain 18.4 ± 17.6 more citations, and promoted on X gain 44.4 ± 8 more citations in the first 5 years from an initial publication. In contrast, journal articles in physics experience comparatively lower boosts in citation counts, with increases of 3.9 ± 1.1, 4.3 ± 0.9, and 6.9 ± 3.5 citations respectively for the same interventions. Our results show that promoting one's work on ArXiv or X has a large impact on the number of citations, as well as the number of influential citations computed by Semantic Scholar, and thereby on the career of researchers. These effects are present also for publications in physics, but they are relatively smaller. The larger relative effect sizes, effects of promotion accumulating over time, and elevated unpredictability of the number of citations in computer science than in physics suggest a greater role of world-of-mouth spreading in computer science than in physics. We discuss the far-reaching implications of these findings for future scientific publishing systems and measures of scientific impact.

Giorgos Vernikos, Arthur Brazinskas, Jakub Adamek, Jonathan Mallinson, Aliaksei Severyn, Eric Malmi. Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Text-editing models have recently become a prominent alternative to seq2seq models for monolingual text-generation tasks such as grammatical error correction, simplification, and style transfer. These tasks share a common trait -- they exhibit a large amount of textual overlap between the source and target texts. Text-editing models take advantage of this observation and learn to generate the output by predicting edit operations applied to the source sequence. In contrast, seq2seq models generate outputs word-by-word from scratch thus making them slow at inference time. Text-editing models provide several benefits over seq2seq models including faster inference speed, higher sample efficiency, and better control and explainability of the outputs. This tutorial provides a comprehensive overview of text-editing models and discusses how they can be used to mitigate hallucination and bias, both pressing challenges in the field of text generation. Finally, we discuss how to optimize latency of large language models via distillation to text-editing models and other means.

As large-scale language model pretraining pushes the state-of-the-art in text generation, recent work has turned to controlling attributes of the text such models generate. While modifying the pretrained models via fine-tuning remains the popular approach, it incurs a significant computational cost and can be infeasible due to a lack of appropriate data. As an alternative, we propose \textsc{MuCoCO}---a flexible and modular algorithm for controllable inference from pretrained models. We formulate the decoding process as an optimization problem that allows for multiple attributes we aim to control to be easily incorporated as differentiable constraints. By relaxing this discrete optimization to a continuous one, we make use of Lagrangian multipliers and gradient-descent-based techniques to generate the desired text. We evaluate our approach on controllable machine translation and style transfer with multiple sentence-level attributes and observe significant improvements over baselines.

We propose MASKER, an unsupervised textediting method for style transfer.To tackle cases when no parallel source-target pairs are available, we train masked language models (MLMs) for both the source and the target domain.Then we find the text spans where the two models disagree the most in terms of likelihood.This allows us to identify the source tokens to delete to transform the source text to match the style of the target domain.The deleted tokens are replaced with the target MLM, and by using a padded MLM variant, we avoid having to predetermine the number of inserted tokens.Our experiments on sentence fusion and sentiment transfer demonstrate that MASKER performs competitively in a fully unsupervised setting.Moreover, in lowresource settings, it improves supervised methods' accuracy by over 10 percentage points when pre-training them on silver training data generated by MASKER.

The ability to combine symbols to generate language is a defining characteristic of human intelligence, particularly in the context of artistic story-telling through lyrics.We develop a method for synthesizing a rap verse based on the content of any text (e.g., a news article), or for augmenting pre-existing rap lyrics.Our method, called RAPFORMER, is based on training a Transformer-based denoising autoencoder to reconstruct rap lyrics from content words extracted from the lyrics, trying to preserve the essential meaning, while matching the target style.RAPFORMER features a novel BERT-based paraphrasing scheme for rhyme enhancement which increases the average rhyme density of output lyrics by 10%.Experimental results on three diverse input domains show that RAPFORMER is capable of generating technically fluent verses that offer a good trade-off between content preservation and style transfer.Furthermore, a Turingtest-like experiment reveals that RAPFORMER fools human lyrics experts 25% of the time. 1

Eric Malmi, Sebastian Krause, Sascha Rothe, Daniil Mirylenka, Aliaksei Severyn. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Genealogical networks, also known as family trees or population pedigrees, are commonly studied by genealogists wanting to know about their ancestry, but they also provide a valuable resource for disciplines such as digital demography, genetics, and computational social science. These networks are typically constructed by hand through a very time-consuming process, which requires comparing large numbers of historical records manually. We develop computational methods for automatically inferring large-scale genealogical networks. A comparison with human-constructed networks attests to the accuracy of the proposed methods. To demonstrate the applicability of the inferred large-scale genealogical networks, we present a longitudinal analysis on the mating patterns observed in a network. This analysis shows a consistent tendency of people choosing a spouse with a similar socioeconomic status, a phenomenon known as assortative mating. Interestingly, we do not observe this tendency to consistently decrease (nor increase) over our study period of 150 years.

Network alignment is the problem of matching the nodes of two graphs, maximizing the similarity of the matched nodes and the edges between them. This problem is encountered in a wide array of applications---from biological networks to social networks to ontologies---where multiple networked data sources need to be integrated. Due to the difficulty of the task, an accurate alignment can rarely be found without human assistance. Thus, it is of great practical importance to develop network alignment algorithms that can optimally leverage experts who are able to provide the correct alignment for a small number of nodes. Yet, only a handful of existing works address this active network alignment setting.

Conversational agents offer users a naturallanguage interface to accomplish tasks, entertain themselves, or access information.Informational dialogue is particularly challenging in that the agent has to hold a conversation on an open topic, and to achieve a reasonable coverage it generally needs to digest and present unstructured information from textual sources.Making responses based on such sources sound natural and fit appropriately into the conversation context is a topic of ongoing research, one of the key issues of which is preventing the agent's responses from sounding repetitive.Targeting this issue, we propose a new task, known as redundancy localization, which aims to pinpoint semantic overlap between text passages.To help address it systematically, we formalize the task, prepare a public dataset with fine-grained redundancy labels, and propose a model utilizing a weak training signal defined over the results of a passage-retrieval system on web texts.The proposed model demonstrates superior performance compared to a state-of-the-art entailment model and yields encouraging results when applied to a real-world dialogue. * Work performed during an internship at Google.User: What is Malaria?Agent: A disease caused by a plasmodium parasite, transmitted by the bite of infected mosquitoes.User: Is it a virus?Agent: Malaria is a parasitic infection spread by Anopheles mosquitoes.The Plasmodium parasite that causes Malaria is neither a virus nor a bacterium -it is a single-celled parasite that multiplies in red blood cells of humans as well as in the mosquito intestine.

Writing rap lyrics requires both creativity to construct a meaningful, interesting story and lyrical skills to produce complex rhyme patterns, which form the cornerstone of good flow. We present a rap lyrics generation method that captures both of these aspects. First, we develop a prediction model to identify the next line of existing lyrics from a set of candidate next lines. This model is based on two machine-learning techniques: the RankSVM algorithm and a deep neural network model with a novel structure. Results show that the prediction model can identify the true next line among 299 randomly selected lines with an accuracy of 17%, i.e., over 50 times more likely than by random. Second, we employ the prediction model to combine lines from existing songs, producing lyrics with rhyme and a meaning. An evaluation of the produced lyrics shows that in terms of quantitative rhyme density, the method outperforms the best human rappers by 21%. The rap lyrics generator has been deployed as an online tool called DeepBeat, and the performance of the tool has been assessed by analyzing its usage logs. This analysis shows that machine-learned rankings correlate with user preferences.

Abstract—We study a novel type of a semi-supervised anomaly detection problem where the anomalies occur collectively among a background of normal data. Such problem arises in experimental high energy physics when one is trying to discover deviations from known Standard Model physics. We solve the problem by first fitting a mixture of Gaussians to a labeled background sample. We then fit a mixture of this background model and a number of additional Gaussians to an unlabeled sample containing both background and anomalies. This way we not only detect but also perform pattern recognition of anomalies. Such mixture model allows us to perform classification of anomalies vs. background, estimate the proportion of anomalies in the sample and study the statistical significance of the anomalous contribution. We first verify the performance of the method using artificial data and then demonstrate its real-life applicability using a data set related to the search of the Higgs boson at the Tevatron collider. Index Terms—Anomaly detection, semi-supervised learning, EM algorithm, Gaussian mixture models, high energy physics

Studies on human mobility are built on two fundamentally different data sources: manual check-in data that originates from location-based social networks and automatic check-in data that can be automatically collected through various smartphone sensors. In this paper, we analyze the differences and similarities of manual check-ins from Foursquare and automatic check-ins from Nokia's Mobile Data Challenge. Several new findings follow from our analysis: (1) While automatic checking-in overall results in more visits than manual checking-in, the check-in levels are comparable when visiting new places. (2) Daily and weekly check-in activity patterns are similar for both systems except for Saturdays -- when manual check-ins are relatively more probable. (3) A recently proposed rank distribution to describe human mobility, so far validated on manual check-in data, also holds for automatic check-in data given a slight modification to the definition of rank. (4) The patterns described by automatic check-ins are in general more predictable. We also address the question of whether it is possible to find matching places across the two check-in systems. Our analysis shows that while this is challenging in areas such as city centers, our method achieves an accuracy of 51% for places that are not homes of phone users.