# Sensitivity as a Complexity Measure for Sequence Classification Tasks

arXiv: https://arxiv.org/abs/2104.10343 · HTML: https://mlsanity.com/paper/2104.10343/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 73 references that are in the map.
- First posted on arXiv 21 Apr 2021.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [SuperGLUE: A Stickier Benchmark for General-Purpose Language Understanding Systems](https://mlsanity.com/paper/1905.00537/) (2019)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [Convolutional Neural Networks for Sentence Classification](https://mlsanity.com/paper/1408.5882/) (2014)
- [SemEval-2017 Task 1: Semantic Textual Similarity - Multilingual and Cross-lingual Focused Evaluation](https://mlsanity.com/paper/1708.00055/) (2017)
- [Neural Network Acceptability Judgments](https://mlsanity.com/paper/1805.12471/) (2018)
- [Stanza: A Python Natural Language Processing Toolkit for Many Human Languages](https://mlsanity.com/paper/2003.07082/) (2020)
- [Annotation Artifacts in Natural Language Inference Data](https://mlsanity.com/paper/1803.02324/) (2018)
- [Adversarial Examples for Evaluating Reading Comprehension Systems](https://mlsanity.com/paper/1707.07328/) (2017)
- [Learning the Difference that Makes a Difference with Counterfactually-Augmented Data](https://mlsanity.com/paper/1909.12434/) (2019)
- [Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies](https://mlsanity.com/paper/1611.01368/) (2016)
- [One Billion Word Benchmark for Measuring Progress in Statistical Language Modeling](https://mlsanity.com/paper/1312.3005/) (2013)
- [Hypothesis Only Baselines in Natural Language Inference](https://mlsanity.com/paper/1805.01042/) (2018)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Targeted Syntactic Evaluation of Language Models](https://mlsanity.com/paper/1808.09031/) (2018)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Training behavior of deep neural network in frequency domain](https://mlsanity.com/paper/1807.01251/) (2018)
- [Towards Understanding the Spectral Bias of Deep Learning](https://mlsanity.com/paper/1912.01198/) (2019)
- [Neural Language Models as Psycholinguistic Subjects: Representations of Syntactic State](https://mlsanity.com/paper/1903.03260/) (2019)
- [How Much Reading Does Reading Comprehension Require? A Critical Investigation of Popular Benchmarks](https://mlsanity.com/paper/1808.04926/) (2018)

## Built on by (most cited first, 28 of 28)

- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [On the Relation between Sensitivity and Accuracy in In-context Learning](https://mlsanity.com/paper/2209.07661/) (2022)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [How Linguistics Learned to Stop Worrying and Love the Language Models](https://mlsanity.com/paper/2501.17047/) (2025)
- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)
- [How are Prompts Different in Terms of Sensitivity?](https://mlsanity.com/paper/2311.07230/) (2023)
- [Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiability](https://mlsanity.com/paper/2112.09054/) (2021)
- [Do We Always Need the Simplicity Bias? Looking for Optimal Inductive Biases in the Wild](https://mlsanity.com/paper/2503.10065/) (2025)
- [The Mystery of the Pathological Path-star Task for Language Models](https://mlsanity.com/paper/2410.13779/) (2024)
- [MLRegTest: A Benchmark for the Machine Learning of Regular Languages](https://mlsanity.com/paper/2304.07687/) (2023)
- [On Measuring the Intrinsic Few-Shot Hardness of Datasets](https://mlsanity.com/paper/2211.09113/) (2022)
- [Identifying Task Groupings for Multi-Task Learning Using Pointwise V-Usable Information](https://mlsanity.com/paper/2410.12774/) (2024)
- [Thrust: Adaptively Propels Large Language Models with External Knowledge](https://mlsanity.com/paper/2307.10442/) (2023)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Can Transformers Really Do It All? On the Compatibility of Inductive Biases Across Tasks](https://mlsanity.com/paper/2607.17624/) (2026)
- [Empirical Analysis of the Inductive Bias of Recurrent Neural Networks by Discrete Fourier Transform of Output Sequences](https://mlsanity.com/paper/2305.09178/) (2023)
- [Measuring Pointwise V-Usable Information In-Context-ly](https://mlsanity.com/paper/2310.12300/) (2023)
- [TEL'M: Test and Evaluation of Language Models](https://mlsanity.com/paper/2404.10200/) (2024)
- [textitGeoHard: Towards Measuring Class-wise Hardness through Modelling Class Semantics](https://mlsanity.com/paper/2407.12512/) (2024)
- [SMAB: MAB based word Sensitivity Estimation Framework and its Applications in Adversarial Text Generation](https://mlsanity.com/paper/2502.07101/) (2025)
- [Language models as tools for investigating the distinction between possible and impossible natural languages](https://mlsanity.com/paper/2512.09394/) (2025)
- [Large language models have learned to use language](https://mlsanity.com/paper/2512.12447/) (2025)
- [Large language models are not about natural language](https://mlsanity.com/paper/2512.13441/) (2025)
- [Linguists should learn to love speech-based deep learning models](https://mlsanity.com/paper/2512.14506/) (2025)
- [Are Language Models Models?](https://mlsanity.com/paper/2601.10421/) (2026)
- [Across the Levels of Analysis: Explaining Predictive Processing in Humans Requires More Than Machine-Estimated Probabilities](https://mlsanity.com/paper/2604.09466/) (2026)
- [You Can't Fight in Here! This is BBS!](https://mlsanity.com/paper/2604.09501/) (2026)
- [Not-So-Strange Love: Language Models and Generative Linguistic Theories are More Compatible than They Appear](https://mlsanity.com/paper/2605.10061/) (2026)

## Abstract (arXiv)

We introduce a theoretical framework for understanding and predicting the complexity of sequence classification tasks, using a novel extension of the theory of Boolean function sensitivity. The sensitivity of a function, given a distribution over input sequences, quantifies the number of disjoint subsets of the input sequence that can each be individually changed to change the output. We argue that standard sequence classification methods are biased towards learning low-sensitivity functions, so that tasks requiring high sensitivity are more difficult. To that end, we show analytically that simple lexical classifiers can only express functions of bounded sensitivity, and we show empirically that low-sensitivity functions are easier to learn for LSTMs. We then estimate sensitivity on 15 NLP tasks, finding that sensitivity is higher on challenging tasks collected in GLUE than on simple text classification tasks, and that sensitivity predicts the performance both of simple lexical classifiers and of vanilla BiLSTMs without pretrained contextualized embeddings. Within a task, sensitivity predicts which inputs are hard for such simple models. Our results suggest that the success of massively pretrained contextual representations stems in part because they provide representations from which information can be extracted by low-sensitivity decoders.