Papers by Anej Svete
Unique Hard Attention: A Tale of Two Sides (2025.acl-short)
Copied to clipboard
| Challenge: | Understanding the expressive power of transformers has attracted attention . many studies analyze unique hard attention transformers, where attention selects a single position that maximizes the attention scores. |
| Approach: | They propose to use unique hard attention to select a single position that maximizes attention scores . they show that models with leftmost-hard attention are equivalent to soft attention . |
| Outcome: | The proposed models with leftmost-hard attention are equivalent to soft attention, suggesting they may better approximate real-world transformers than right-attention models. |
An L* Algorithm for Deterministic Weighted Regular Languages (2024.emnlp-main)
Copied to clipboard
| Challenge: | Angluin (1987) introduced the active learning scheme L , where the learner interacts with an oracle by asking it queries. |
| Approach: | They propose a weighted variant of Angluin's (1987) L* algorithm for learning finite state automatas from black-box models. |
| Outcome: | The proposed algorithm learns aminimal automaton for the target language. |
Lower Bounds on the Expressivity of Recurrent Neural Language Models (2024.naacl-long)
Copied to clipboard
| Challenge: | Recent studies of the representational capacity of neural LMs have focused on their ability to recognize formal languages. |
| Approach: | They propose to connect recurrent neural networks (RNNs) as classifiers to finite-state automatas (FSAs) and a probabilistic FSA to characterize their representational capacity. |
| Outcome: | The proposed models can express arbitrary regular LMs with linearly bounded precision. |
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. |
Information Locality as an Inductive Bias for Neural Language Models (2025.acl-long)
Copied to clipboard
| Challenge: | Inductive biases are inherent in every machine learning system, argues a new study . m-local entropy measures how well symbols disambiguate the next symbol . |
| Approach: | They propose a framework that captures local uncertainty of a language by quantifying how effectively preceding symbols disambiguate the next symbol. |
| Outcome: | The proposed framework captures the local uncertainty of a language by quantifying how effectively symbols disambiguate the next symbol. |
Can Transformers Learn n-gram Language Models? (2024.emnlp-main)
Copied to clipboard
| Challenge: | Existing work has tested transformers' ability to represent formal languages, but language models are not classifiers of strings but rather distributions over them. |
| Approach: | They relate transformers' ability to learn random n-gram language models to ngram language model (LM) they find add- smoothing outperforms transformers on the former, while transformers perform better on the latter . |
| Outcome: | The proposed models outperform classical methods designed to learn n-gram LMs, while transformers perform better on the latter. |
On Efficiently Representing Regular Languages as RNNs (2024.findings-acl)
Copied to clipboard
| Challenge: | Recent work by Hewitt et al. (2020) provides an interpretation of the empirical success of recurrent neural networks (RNNs) as language models (LMs). |
| Approach: | They generalize their construction and show that RNNs can efficiently represent a larger class of LMs than previously claimed. |
| Outcome: | The results suggest that RNNs can represent a larger class of LMs than previously claimed . |
On the Representational Capacity of Recurrent Neural Language Models (2023.emnlp-main)
Copied to clipboard
| Challenge: | Existing studies have focused on LMs as formal languages, but they do not consider language membership. |
| Approach: | They extend the Turing completeness result to the probabilistic case . they show that a rationally weighted RLM can simulate any deterministic Turing machine . |
| Outcome: | The proposed model can simulate any deterministic Turing machine with rationally weighted transitions . the proposed model is based on recurrent neural networks with a rational weighting over strings . |
A Probability–Quality Trade-off in Aligned Language Models and its Relation to Sampling Adaptors (2024.emnlp-main)
Copied to clipboard
| Challenge: | a relationship exists between the quality of a string and its probability, p(y), under a language model, and the quality and quality of the string. |
| Approach: | They examine the probability-quality relationship in language models aligned to human preferences through reinforcement learning through human feedback. |
| Outcome: | The proposed method improves the quality of text sampled from a language model by skewing the model towards high-probability strings. |
Transformers Can Represent n-gram Language Models (2024.naacl-long)
Copied to clipboard
| Challenge: | Existing work studies the transformer architecture in terms of language acceptance . n-gram LMs can represent any ngram lm, giving a concrete lower bound on their probabilistic representational capacity. |
| Approach: | They propose to use transformer LMs to represent n-gram LM, a class of language models . they show transformer lms can exactly represent any ngram lmm, giving them a lower bound . |
| Outcome: | The proposed model can represent any n-gram LM, giving a lower bound on their probabilistic representational capacity. |
The Role of n-gram Smoothing in the Age of Neural Networks (2024.naacl-long)
Copied to clipboard
| Challenge: | n-gram smoothing techniques were used to overcome overfitting problems in neural language models for decades. |
| Approach: | They propose to convert any n-gram smoothing technique into a regularizer compatible with neural language models. |
| Outcome: | The proposed regularizers outperform label smoothing on language modeling and machine translation. |
Computational Expressivity of Neural Language Models (2024.acl-tutorials)
Copied to clipboard
| Challenge: | Language models (LMs) are at the forefront of NLP research due to their versatility across diverse tasks. |
| Approach: | This tutorial will provide a framework for formal analysis of modern language models using tools from formal language theory. |
| Outcome: | This tutorial will provide a framework for formal analysis of modern language models using tools from formal language theory (FLT). |
On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning (2024.acl-long)
Copied to clipboard
| Challenge: | Existing theoretical treatments have shed light on some aspects of CoT, but we are still far from a concrete understanding of the concept. |
| Approach: | They propose to formalize CoT reasoning in a probabilistic setting to bridge this gap . they show that LMs can represent the same family of distributions over strings as probabilistic Turing machines. |
| Outcome: | The proposed model can represent the same family of distributions over strings as Turing machines. |
Recurrent Neural Language Models as Probabilistic Finite-state Automata (2023.emnlp-main)
Copied to clipboard
| Challenge: | Existing studies have focused on the expressive power of recurrent neural network LMs to recognize unweighted formal languages. |
| Approach: | They propose to model a strict subset of probabilistic finite-state automata with RNNs . they show that an RNN requires left(N ||right) neurons to represent an LM . |
| Outcome: | The proposed language models can represent a strict subset of probabilistic distributions expressed by finite-state models. |