Search

Maintaining legacy software requires many software and systems engineering hours. Assembly code programs, which demand low-level control over the computer machine state and have no variable names, are particularly difficult for humans to analyze. Existing conventional program translators guarantee correctness, but are hand-engineered for the source and target programming languages in question. Learned transpilation, i.e. automatic translation of code, offers an alternative to manual re-writing and engineering efforts. Automated symbolic program translation approaches guarantee correctness but struggle to scale to longer programs due to the exponentially large search space. Their rigid rule-based systems also limit their expressivity, so they can only reason about a reduced space of programs. Probabilistic neural language models (LMs) produce plausible outputs for every input, but do so at the cost of guaranteed correctness. In this work, we leverage the strengths of LMs and symbolic solvers in a neurosymbolic approach to learned transpilation for assembly code. Assembly code is an appropriate setting for a neurosymbolic approach, since assembly code can be divided into shorter non-branching basic blocks amenable to the use of symbolic methods. Guess & Sketch extracts alignment and confidence information from features of the LM then passes it to a symbolic solver to resolve semantic equivalence of the transpilation input and output. We test Guess & Sketch on three different test sets of assembly transpilation tasks, varying in difficulty, and show that it successfully transpiles 57.6% more examples than GPT-4 and 39.6% more examples than an engineered transpiler. We also share a training and evaluation dataset for this task.

Let $(\Sigma_T,\sigma)$ be a subshift of finite type with primitive adjacency matrix $T$, $\psi:\Sigma_T \rightarrow \mathbb{R}$ a H\"older continuous potential, and $\mathcal{A}:\Sigma_T \rightarrow \mathrm{GL}_d(\mathbb{R})$ a 1-typical, one-step cocycle. For $t \in \mathbb{R}$ consider the sequences of potentials $\Phi_t=(\varphi_{t,n})_{n \in \mathbb{N}}$ defined by $$\varphi_{t,n}(x):=S_n \psi(x) + t\log \|\mathcal{A}^n(x)\|, \: \forall n \in \mathbb{N}.$$ Using the family of transfer operators defined in this setting by Park and Piraino, for all $t<0$ sufficiently close to 0 we prove the existence of Gibbs-type measures for the superadditive sequences of potentials $\Phi_t$. This extends the results of the well-understood subadditive case where $t \geq 0$. Prior to this, Gibbs-type measures were only known to exist for $t<0$ in the conformal, the reducible, the positive, or the dominated, planar settings, in which case they are Gibbs measures in the classical sense. We further prove that the topological pressure function $t \mapsto P_{\mathrm{top}}(\Phi_t,\sigma)$ is analytic in an open neighbourhood of 0 and has derivative given by the Lyapunov exponents of these Gibbs-type measures., Comment: Final version following revisions. Some structural changes, numerous typos fixed, and some other minor changes, but results unchanged. Thanks to those who gave comments and suggestions (see updated acknowledgements). To appear in Commun. Math. Phys

We present a number of rigidity results concerning holomorphic dynamical systems admitting rotation quasicircles. Firstly, we show the absence of line fields on the Julia set of any rational map that is geometrically finite away from a number of rotation quasicircles with bounded type rotation number. As an application, we prove combinatorial rigidity associated to the problem of degeneration of Herman rings of the simplest configuration. Secondly, we extend a result of de Faria and de Melo on the $C^{1+\alpha}$ rigidity of critical circle maps with bounded type rotation number to a larger class of dynamical objects, namely critical quasicircle maps. Unlike critical circle maps, critical quasicircle maps may have imbalanced inner and outer criticalities. As a consequence, we prove dynamical universality and exponential convergence of renormalization towards a horseshoe attractor., Comment: 58 pages, 11 figures. in the new version, the abstract is rewritten and more references are added

Recurrent neural network-based reinforcement learning systems are capable of complex motor control tasks such as locomotion and manipulation, however, much of their underlying mechanisms still remain difficult to interpret. Our aim is to leverage computational neuroscience methodologies to understanding the population-level activity of robust robot locomotion controllers. Our investigation begins by analyzing topological structure, discovering that fragile controllers have a higher number of fixed points with unstable directions, resulting in poorer balance when instructed to stand in place. Next, we analyze the forced response of the system by applying targeted neural perturbations along directions of dominant population-level activity. We find evidence that recurrent state dynamics are structured and low-dimensional during walking, which aligns with primate studies. Additionally, when recurrent states are perturbed to zero, fragile agents continue to walk, which is indicative of a stronger reliance on sensory input and weaker recurrence.

Large multimodal models trained on natural documents, which interleave images and text, outperform models trained on image-text pairs on various multimodal benchmarks. However, the datasets used to train these models have not been released, and the collection process has not been fully specified. We introduce the OBELICS dataset, an open web-scale filtered dataset of interleaved image-text documents comprising 141 million web pages extracted from Common Crawl, 353 million associated images, and 115 billion text tokens. We describe the dataset creation process, present comprehensive filtering rules, and provide an analysis of the dataset's content. To show the viability of OBELICS, we train vision and language models of 9 and 80 billion parameters named IDEFICS, and obtain competitive performance on different multimodal benchmarks. We release our dataset, models and code.

Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications in a variety of scenarios, but in both the centralized and federated settings there remain instances where either MF cannot be easily applied, or other algorithms provide better tradeoffs (typically, as $\epsilon$ becomes small). In this work, we show how MF can subsume prior state-of-the-art algorithms in both federated and centralized training settings, across all privacy budgets. The key technique throughout is the construction of MF mechanisms with banded matrices (lower-triangular matrices with at most $\hat{b}$ nonzero bands including the main diagonal). For cross-device federated learning (FL), this enables multiple-participations with a relaxed device participation schema compatible with practical FL infrastructure (as demonstrated by a production deployment). In the centralized setting, we prove that banded matrices enjoy the same privacy amplification results as the ubiquitous DP-SGD algorithm, but can provide strictly better performance in most scenarios -- this lets us always at least match DP-SGD, and often outperform it., Comment: 34 pages, 13 figures

The current trend of scaling language models involves increasing both parameter count and training dataset size. Extrapolating this trend suggests that training dataset size may soon be limited by the amount of text data available on the internet. Motivated by this limit, we investigate scaling language models in data-constrained regimes. Specifically, we run a large set of experiments varying the extent of data repetition and compute budget, ranging up to 900 billion training tokens and 9 billion parameter models. We find that with constrained data for a fixed compute budget, training with up to 4 epochs of repeated data yields negligible changes to loss compared to having unique data. However, with more repetition, the value of adding compute eventually decays to zero. We propose and empirically validate a scaling law for compute optimality that accounts for the decreasing value of repeated tokens and excess parameters. Finally, we experiment with approaches mitigating data scarcity, including augmenting the training dataset with code data or removing commonly used filters. Models and datasets from our 400 training runs are freely available at https://github.com/huggingface/datablations., Comment: 50 pages (9 main), 39 figures, 15 tables

Abductive reasoning aims to find plausible explanations for an event. This style of reasoning is critical for commonsense tasks where there are often multiple plausible explanations. Existing approaches for abductive reasoning in natural language processing (NLP) often rely on manually generated annotations for supervision; however, such annotations can be subjective and biased. Instead of using direct supervision, this work proposes an approach for abductive commonsense reasoning that exploits the fact that only a subset of explanations is correct for a given context. The method uses posterior regularization to enforce a mutual exclusion constraint, encouraging the model to learn the distinction between fluent explanations and plausible ones. We evaluate our approach on a diverse set of abductive reasoning datasets; experimental results show that our approach outperforms or is comparable to directly applying pretrained language models in a zero-shot manner and other knowledge-augmented zero-shot methods., Comment: accepted at ACL'23

Explainable multi-hop question answering (QA) not only predicts answers but also identifies rationales, i. e. subsets of input sentences used to derive the answers. This problem has been extensively studied under the supervised setting, where both answer and rationale annotations are given. Because rationale annotations are expensive to collect and not always available, recent efforts have been devoted to developing methods that do not rely on supervision for rationales. However, such methods have limited capacities in modeling interactions between sentences, let alone reasoning across multiple documents. This work proposes a principled, probabilistic approach for training explainable multi-hop QA systems without rationale supervision. Our approach performs multi-hop reasoning by explicitly modeling rationales as sets, enabling the model to capture interactions between documents and sentences within a document. Experimental results show that our approach is more accurate at selecting rationales than the previous methods, while maintaining similar accuracy in predicting answers.

In motor neuroscience, artificial recurrent neural networks models often complement animal studies. However, most modeling efforts are limited to data-fitting, and the few that examine virtual embodied agents in a reinforcement learning context, do not draw direct comparisons to their biological counterparts. Our study addressing this gap, by uncovering structured neural activity of a virtual robot performing legged locomotion that directly support experimental findings of primate walking and cycling. We find that embodied agents trained to walk exhibit smooth dynamics that avoid tangling -- or opposing neural trajectories in neighboring neural space -- a core principle in computational neuroscience. Specifically, across a wide suite of gaits, the agent displays neural trajectories in the recurrent layers are less tangled than those in the input-driven actuation layers. To better interpret the neural separation of these elliptical-shaped trajectories, we identify speed axes that maximizes variance of mean activity across different forward, lateral, and rotational speed conditions.

While no known asteroid poses a threat to Earth for at least the next century, the catalog of near-Earth asteroids is incomplete for objects whose impacts would produce regional devastation. Several approaches have been proposed to potentially prevent an asteroid impact with Earth by deflecting or disrupting an asteroid. A test of kinetic impact technology was identified as the highest priority space mission related to asteroid mitigation. NASA's Double Asteroid Redirection Test (DART) mission is the first full-scale test of kinetic impact technology. The mission's target asteroid was Dimorphos, the secondary member of the S-type binary near-Earth asteroid (65803) Didymos. This binary asteroid system was chosen to enable ground-based telescopes to quantify the asteroid deflection caused by DART's impact. While past missions have utilized impactors to investigate the properties of small bodies those earlier missions were not intended to deflect their targets and did not achieve measurable deflections. Here we report the DART spacecraft's autonomous kinetic impact into Dimorphos and reconstruct the impact event, including the timeline leading to impact, the location and nature of the DART impact site, and the size and shape of Dimorphos. The successful impact of the DART spacecraft with Dimorphos and the resulting change in Dimorphos's orbit demonstrates that kinetic impactor technology is a viable technique to potentially defend Earth if necessary., Comment: Accepted by Nature

The Double Asteroid Redirection Test (DART) spacecraft successfully performed the first test of a kinetic impactor for asteroid deflection by impacting Dimorphos, the secondary of near-Earth binary asteroid (65803) Didymos, and changing the orbital period of Dimorphos. A change in orbital period of approximately 7 minutes was expected if the incident momentum from the DART spacecraft was directly transferred to the asteroid target in a perfectly inelastic collision, but studies of the probable impact conditions and asteroid properties indicated that a considerable momentum enhancement ($\beta$) was possible. In the years prior to impact, we used lightcurve observations to accurately determine the pre-impact orbit parameters of Dimorphos with respect to Didymos. Here we report the change in the orbital period of Dimorphos as a result of the DART kinetic impact to be -33.0 +/- 1.0 (3$\sigma$) minutes. Using new Earth-based lightcurve and radar observations, two independent approaches determined identical values for the change in the orbital period. This large orbit period change suggests that ejecta contributed a significant amount of momentum to the asteroid beyond what the DART spacecraft carried., Comment: Accepted by Nature

By adapting the near-degenerate regime designed by Kahn, Lyubich, and D. Dudko, we prove that the boundaries of Herman rings with bounded type rotation number and of the simplest configuration are quasicircles with dilatation depending only on the degree and the rotation number. As a consequence, we show that these Herman rings always degenerate to a Herman curve, i.e. an invariant Jordan curve that is not contained in the closure of a rotation domain and on which the map is conjugate to a rigid rotation. This process enables us to construct the first general examples of rational maps having Herman curves of bounded type with arbitrary degree and combinatorics. In particular, they do not come from Blaschke products. We also demonstrate the existence of Renormalization Theory for Herman curves by constructing rescaled limits of the first return maps in the unicritical case., Comment: 58 pages, 18 figures. In the previous version, there was a missing case (peripheral lamination) in section 7. In the new version, section 7 is rewritten to include this missing case and to improve the exposition of the main ideas

We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise linearly correlated over iterations. We propose a simplified setting that distills key facets of these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multiple important special cases exactly (including anticorrelated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically.