Papers by William Merrill
The Parallelism Tradeoff: Limitations of Log-Precision Transformers (2023.tacl-1)
Copied to clipboard
| Challenge: | Existing work on transformers established their Turing completeness, albeit with assumptions like infinite precision and arbitrarily powerful feedforward subnets. |
| Approach: | They propose to simulate transformers whose arithmetic precision is logarithmic in the number of input tokens by constant-depth logspace-uniform threshold circuits. |
| Outcome: | The proposed model emerges from the transformer architecture’s high parallelizability, suggesting a potential inherent weakness of the scaling paradigm. |
A Formal Hierarchy of RNN Architectures (2020.acl-main)
Copied to clipboard
| Challenge: | Existing theories of expressive power of RNNs are limited. |
| Approach: | They propose a formal hierarchy of the expressive capacity of RNN architectures based on two formal properties: space complexity and rational recurrence. |
| Outcome: | The proposed model is based on the theory of “saturated” RNNs and shows that it obeys a similar hierarchy to unsaturated RNN models. |
End-to-End Graph-Based TAG Parsing with Neural Networks (N18-1)
Copied to clipboard
| Challenge: | Using BiLSTMs, highway connections, and character-level CNNs, we propose a graph-based Tree Adjoining Grammar (TAG) parser. |
| Approach: | They propose a graph-based Tree Adjoining Grammar parser that uses BiLSTMs, highway connections, and character-level CNNs. |
| Outcome: | The proposed parser outperforms the previously reported best by more than 2.2 LAS and UAS points. |
Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent (2021.emnlp-main)
Copied to clipboard
| Challenge: | Evidence is emerging that neural networks learn due to inductive bias in the training routine, typically a variant of gradient descent (GD). |
| Approach: | They propose to characterize GD as an inductive bias in transformer training . they document norm growth in transformer language models and show they are saturated . |
| Outcome: | Empirically, we document norm growth in the training of transformer language models . the results suggest saturation is a new characterization of an inductive bias implicit in GD . |
ReCLIP: A Strong Zero-Shot Baseline for Referring Expression Comprehension (2022.acl-long)
Copied to clipboard
| Challenge: | Visual referring expression comprehension (ReC) models can be trained for a domain, but it remains unclear if they can be applied in a zero-shot manner to more complex tasks like ReC. |
| Approach: | They propose a method that repurposes CLIP, a state-of-the-art large-scale model, for training a referring expression comprehension model for a new visual domain. |
| Outcome: | The proposed model reduces the gap between zero-shot baselines from prior work and supervised models by as much as 29% on RefCOCOg, and on ReFGTA (video game imagery), and its relative improvement over supervised ReC models is 8%. |
Evaluating n-Gram Novelty of Language Models Using Rusty-DAWG (2024.emnlp-main)
Copied to clipboard
| Challenge: | a new study examines how novel language models generate training text . large LMs and constrained decoding strategies both decrease novelty . |
| Approach: | They develop a novel search tool inspired by genomic data to find n-grams in training data. |
| Outcome: | The proposed tool can search for n-grams over a corpus in constant time w.r.t. large LMs and more constrained decoding strategies both decrease novelty. |
Saturated Transformers are Constant-Depth Threshold Circuits (2022.tacl-1)
Copied to clipboard
| Challenge: | Recent work shows that transformers with hard attention are limited in power, but hard attention is a strong assumption. |
| Approach: | They propose a generalization of hard attention that captures attention patterns in transformers with saturated attention. |
| Outcome: | The proposed generalization of hard attention more closely captures the attention patterns learnable in practical transformers. |
Can You Learn Semantics Through Next-Word Prediction? The Case of Entailment (2024.findings-acl)
Copied to clipboard
| Challenge: | et al. argued that sentence co-occurrence probabilities should reflect entailment . but it is unclear whether probabilities predicted by neural LMs encode enanglement based on their theory . |
| Approach: | They propose a test that decodes entailment relations between natural sentences . they argue that the test that predicts a flipped test does not account for redundancy . |
| Outcome: | The proposed test can decode entailment relations between natural sentences, but not perfectly. |
Competency Problems: On Finding and Removing Artifacts in Language Data (2021.emnlp-main)
Copied to clipboard
Matt Gardner, William Merrill, Jesse Dodge, Matthew Peters, Alexis Ross, Sameer Singh, Noah A. Smith
| Challenge: | Recent work in NLP has documented dataset artifacts, bias, and spurious correlations . how to tell which features have spurious instead of legitimate correlations is typically left unspecified . |
| Approach: | They propose a class of competency problems to formalize this notion into a classification . they show that realistic datasets will increasingly deviate from competency problems . |
| Outcome: | The proposed model can be used to show that models are inappropriately affected by these less extreme biases. |
Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases (2025.acl-long)
Copied to clipboard
| Challenge: | Pretraining language models on formal language can improve their acquisition of natural language, but it is computationally limited. |
| Approach: | They hypothesize that effective transfer occurs when the formal language captures hierarchical dependencies present in natural language and remains within the computational limitations of the model architecture. |
| Outcome: | The proposed model can achieve lower loss on natural language and better generalization with a 33% smaller token budget than training on a matched amount of natural language. |
Transparency Helps Reveal When Language Models Learn Meaning (2023.tacl-1)
Copied to clipboard
| Challenge: | Existing language models are trained to optimize unsupervised objectives on text . despite their centrality, current models do not represent natural language semantics well . |
| Approach: | They show that autoregressive and masked language models learn to emulate semantic relations between expressions when context-dependent . they argue that a learner that has access to all Java code can never learn execution . |
| Outcome: | a new study shows that language models fail to represent natural language semantics well . the authors show that the model learning fails when denotations are changed to be context-dependent . |
Provable Limitations of Acquiring Meaning from Ungrounded Form: What Will Future Language Models Understand? (2021.tacl-1)
Copied to clipboard
| Challenge: | Language models trained on billions of tokens have recently led to unprecedented results on many NLP tasks. |
| Approach: | They examine whether assertions enable a system to emulate representations preserving semantic relations like equivalence. |
| Outcome: | The proposed model can emulate representations preserving semantic relations like equivalence, but it can become uncomputable for classes of languages where expressions can take different values in different contexts. |