Papers by Tim Vieira
A Formal Perspective on Byte-Pair Encoding (2023.findings-acl)
Copied to clipboard
| Challenge: | Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data in NLP, but the underlying optimization problem that BPE seeks to solve has not yet been laid down. |
| Approach: | They propose an algorithm which is a 1/sigma*(1-e(-sigma))-approximation of an optimal merge sequence. |
| Outcome: | The proposed algorithm improves the runtime complexity from O(NM) to O(N log M) and the lower bound of the approximation is approx0.37. |
On Finding the K-best Non-projective Dependency Trees (2021.acl-long)
Copied to clipboard
| Challenge: | Existing work on finding the one-best dependency tree has not extended this to finding the K-best tree. |
| Approach: | They propose to simplify the K-best spanning tree algorithm by decoding the K best dependency trees with a root constraint. |
| Outcome: | The proposed algorithm can be used to find the K-best dependency trees without root constraint. |
Syntactic Control of Language Models by Posterior Inference (2025.findings-acl)
Copied to clipboard
| Challenge: | Syntactic control of generated text is crucial for many domain-specific applications of language models, where structural constraints, such as formality, grammatical correctness, or adherence to a given template, can significantly affect usability and readability. |
| Approach: | They propose to use posterior inference to enforce target constituency structure by sampling from a proposal distribution with a syntactic tagger to ensure that each generated token aligns with the desired syntakic structure. |
| Outcome: | The proposed method increases the F1 score from 12.31 (GPT2-large) and 35.33 (Llama3-8B) to about 93 in both cases without compromising the language model’s fluency. |
If beam search is the answer, what was the question? (2020.emnlp-main)
Copied to clipboard
| Challenge: | surprisingly, beam search results on language generation tasks are low-quality . despite its high error rate, beam searches can be used to decode models with high probability . |
| Approach: | They frame beam search as the exact solution to a different decoding objective . they propose a set of decoding objectives that explicitly enforce this property . |
| Outcome: | The proposed method enforces uniform information density in text, a property motivated by cognitive science. |
Searching for More Efficient Dynamic Programs (2021.findings-emnlp)
Copied to clipboard
| Challenge: | a combinatorial model of human language often involves dynamic programming. |
| Approach: | They propose to search for a sequence of semantics-preserving transformations to improve the initial program's running time. |
| Outcome: | The proposed algorithm can find speed-ups in the initial program, and it can be used to improve it. |
Please Mind the Root: Decoding Arborescences for Dependency Parsing (2020.emnlp-main)
Copied to clipboard
| Challenge: | a dependency tree has a root constraint, but only one edge may emanate from the root node. |
| Approach: | They propose an algorithm which enforces a root constraint without compromising the original runtime. |
| Outcome: | The proposed algorithm satisfies the constraint without compromising the original runtime. |
Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs (2022.emnlp-main)
Copied to clipboard
| Challenge: | Weighted finite-state automata (WSFAs) are common formalisms in NLP. |
| Approach: | They propose an algorithm for semiring-weighted WFSAs with av-erage out symbol fractions . |
| Outcome: | The proposed algorithms are faster than the standard methods for weighted finite-state automata. |
Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages (2023.emnlp-main)
Copied to clipboard
| Challenge: | a class of tree-adjoining languages can be characterized by various two-level formalisms controlled by semiring-weighted CFGs and PDAs. |
| Approach: | They propose semiring-weighted versions of controllable CFGs and PDAs . they also introduce a WPDA normal form that is analogous to Chomsky's normal form for CFG . |
| Outcome: | The proposed algorithms are more time-efficient than the previous ones for LIG, PAA, and EPDA. |
Prefix Parsing is Just Parsing (2026.acl-short)
Copied to clipboard
| Challenge: | Existing prefix parsers are typically tied to particular parsing algorithms. |
| Approach: | They propose a prefix grammar transformation that reduces prefix parsing to ordinary parsers . they propose enabling prediction of the next token by computing the next-token weight vector . |
| Outcome: | The proposed method reduces prefix parsing to ordinary parsers without modification . the transformed grammar is only a small factor larger than the input . |
Best-First Beam Search (2020.tacl-1)
Copied to clipboard
| Challenge: | Currently, beam search is the default for decoding structured predictors . however, little work has been done to speed up beam search itself . |
| Approach: | They propose a beam search algorithm that prunes the scoring function to a monotonic sequence length, which allows for safe pruning of hypotheses that cannot be in the final set of hypothecies. |
| Outcome: | The proposed method can be implemented up to 10x faster in practice. |
On the Intersection of Context-Free and Regular Languages (2023.eacl-main)
Copied to clipboard
| Challenge: | We generalize the Bar-Hillel intersection construction so that the given WFSA may contain -arcs. |
| Approach: | They propose a construction that generalizes the Bar- Hillel in the case the desired automaton has -arcs and generalize the weighted extension so that the given WFSA may contain arcs. |
| Outcome: | The proposed construction can encode the structure of both the input automaton and grammar while retaining the asymptotic size of the original construction. |
Exact Paired-Permutation Testing for Structured Test Statistics (2022.naacl-main)
Copied to clipboard
| Challenge: | Existing methods to evaluate test statistic are Monte Carlo approximations which use a summation over all 2 N possible swaps. |
| Approach: | They propose an exact algorithm for the paired-permutation test for a family of structured test statistics. |
| Outcome: | The proposed algorithm is 10x faster than the Monte Carlo approximation with 20000 samples on a common dataset. |
On the Proper Treatment of Tokenization in Psycholinguistics (2024.emnlp-main)
Copied to clipboard
| Challenge: | Language models are used in computational psycholinguistics to test theories that relate the surprisal of a region of interest to its cognitive cost experienced by readers. |
| Approach: | They propose to marginalize token-level language models into character-level ones before they are used in psycholinguistic studies. |
| Outcome: | The proposed model over token strings is better than character-level model, the authors show . the proposed model marginalizes token-level models into character-based models before they are used in psycholinguistic studies. |
Efficient Sampling of Dependency Structure (2021.emnlp-main)
Copied to clipboard
| Challenge: | Spanning trees are a fundamental model of dependency structure in natural language processing, syntactic dependency trees. |
| Approach: | They propose to use a spanning tree sampling algorithm to faithfully sample dependency trees from a graph subject to a root constraint. |
| Outcome: | The proposed sampling algorithm can sample K trees without replacement in O(K N3 + K2 N) time. |
On the Proper Treatment of Units in Surprisal Theory (2026.acl-long)
Copied to clipboard
| Challenge: | empirical work often leaves the notion of a unit underspecified . empirical work has sought to characterize the processing difficulty comprehenders experience . |
| Approach: | They propose a framework for reasoning about surprisal over arbitrary unit inventories . they argue that surprises should be explicit and treat tokenization as implementation detail . |
| Outcome: | The proposed framework disentangles the models' definitions and the regions of interest and treats tokenization as an implementation detail rather than a scientific primitive. |
Efficient Computation of Expectations under Spanning Tree Distributions (2021.tacl-1)
Copied to clipboard
| Challenge: | a general framework for inference in spanning tree models is presented . a spanning-tree model is a combinatorial structure that is important for natural language processing . |
| Approach: | They propose a general framework for inference in spanning tree models . they exploit a connection between expectations and gradients, which allows efficient algorithms . |
| Outcome: | The proposed framework is up to 15 times faster than existing algorithms and reduces runtime complexity by a factor of the sentence length. |
Direct Preference Optimization with an Offset (2024.findings-acl)
Copied to clipboard
| Challenge: | Direct preference optimization (DPO) fine-tunes language models with human preferences . but not all preference pairs are equal; sometimes, the preferred response is only slightly better than the dispreferred one. |
| Approach: | They propose a generalization of direct preference optimization that does not treat every preference pair equally during fine-tuning. |
| Outcome: | The proposed algorithm outperforms DPO on tasks with limited preference pairs . it requires the difference between likelihood of preferred and dispreferred response to be greater than offset value . |
Conditional Poisson Stochastic Beams (2021.emnlp-main)
Copied to clipboard
| Challenge: | Existing methods for beam search are based on a deterministic approach, but the results are not as accurate as those used in SBS. |
| Approach: | They propose a method that turns beam search into a stochastic process by using conditional Poisson sampling design instead of taking the maximizing set at each iteration. |
| Outcome: | The proposed method produces lower variance and more efficient estimators than SBS, even showing improvements in high entropy settings. |
An Exploration of Left-Corner Transformations (2023.emnlp-main)
Copied to clipboard
| Challenge: | Fig. 1 shows how left-corner transformations remove left recursion from context-free grammars . a common use case is to remove left-recursed grammars, which is necessary for top-down parsing . |
| Approach: | They generalize left-corner transformations to support semiring-weighted production rules . they also provide finer-grained control over which left corners may be moved . |
| Outcome: | The proposed transformation removes left recursion from context-free grammars . it also provides finer-grained control over which left corners may be moved . |
Higher-order Derivatives of Weighted Finite-state Machines (2021.acl-short)
Copied to clipboard
| Challenge: | Weighted finite-state machines (WFSMs) have a storied role in NLP . e.g., conditional random fields for part-of-speech tagging are considered special cases of WFSM. |
| Approach: | They propose an algorithm for evaluating derivatives of all orders that is faster than prior algorithms . they also find that it is faster for computing second-order expectations . |
| Outcome: | The proposed algorithm is faster than prior algorithms and can compute second-order expectations. |
Efficient Semiring-Weighted Earley Parsing (2023.acl-long)
Copied to clipboard
| Challenge: | Using Earley's context-free parsing algorithm, we show that the speed-ups are effective in practice. |
| Approach: | They propose a context-free parsing algorithm with various known and new speed-ups that improve Earley's (1970) O(N3|G||R|) They also propose 'a binarized version' that achieves runtime of O(M| |G| when the grammar is represented compactly as a single finite-state automaton M. |
| Outcome: | The proposed algorithm can be used to reduce the complexity of CKY on a binarized version of the grammar G. |
Algorithms for Weighted Pushdown Automata (2022.emnlp-main)
Copied to clipboard
| Challenge: | Existing dynamic programming algorithms for PDAs often resort to a PDA-to-CFG conversion. |
| Approach: | They propose to use a pushdown automaton to reduce the space requirements by a factor of |Gamma| or the runtime by reducing the number of states. |
| Outcome: | The proposed algorithms reduce the space requirements by a factor of |Gamma| or reduce the runtime by fewer states. |
The Universal Decompositional Semantics Dataset and Decomp Toolkit (2020.lrec-1)
Copied to clipboard
Aaron Steven White, Elias Stengel-Eskin, Siddharth Vashishtha, Venkata Subrahmanyan Govindarajan, Dee Ann Reisinger, Tim Vieira, Keisuke Sakaguchi, Sheng Zhang, Francis Ferraro, Rachel Rudinger, Kyle Rawlins, Benjamin Van Durme
| Challenge: | Decompositional semantics is a method of crowd-sourcing semantic annotations while retaining high interannotator agreement. |
| Approach: | They present the Universal Decompositional Semantics dataset (v1.0) they propose a decomposition-aligned approach to semantic annotation that uses simple questions to answer . |
| Outcome: | The dataset is bundled with the Decomp toolkit (v0.1) both datasets are publicly available at http://decomp.io. |