TL;DR
This paper introduces sensitivity—a concept borrowed from Boolean function theory—as a formal measure of complexity for natural language tasks. The authors demonstrate that tasks requiring high sensitivity (where many different parts of the input can independently flip the output label) are fundamentally harder for simple models to learn, explaining why massive pretraining is essential for complex reasoning but unnecessary for basic sentiment analysis.
What Problem Does This Paper Address?
In NLP, we intuitively know that some tasks are "harder" than others. Sentiment analysis can often be solved by a simple bag-of-words model, while Natural Language Inference (NLI) seems to require massive Transformers like RoBERTa. However, we lack a unified theoretical framework to quantify this difficulty.
Existing metrics fall short: the Chomsky Hierarchy describes asymptotic complexity but doesn't account for real-world data distributions; Kolmogorov complexity is uncomputable; and psycholinguistic metrics like surprisal focus on the input's form rather than the specific task being performed. This paper fills that gap by proposing sensitivity as a practical, computable measure of task complexity.
Methods
The authors generalize the "sensitivity" of Boolean functions to natural language sequences.
- Block Sensitivity: In this context, sensitivity measures how many disjoint subsets (blocks) of an input sequence can be changed to flip the model's prediction.
- Low Sensitivity: The output is predictable from redundant information (e.g., a movie review with many positive adjectives).
- High Sensitivity: Small changes in many different places can change the meaning (e.g., changing "all" to "some" or "not" in a logic-heavy sentence).
- Theoretical Bounds: The authors prove that simple lexical classifiers (like n-gram models or bag-of-embeddings) have a mathematical "ceiling" on the sensitivity they can express.
- Estimation: To calculate sensitivity on real data, they use a strong "oracle" model (RoBERTa) to provide labels and a masked language model (XLNet) to generate plausible word substitutions that stay within the natural language distribution.
- Human Validation: They conducted experiments where humans were asked to find as many disjoint word changes as possible that would flip a sentence's label, verifying that their automated metric aligns with human intuition.
Datasets
The study evaluates sensitivity across 15 diverse NLP tasks:
- Standard Text Classification: MR (movie reviews), SUBJ (subjectivity), CR (customer reviews), and MPQA (opinion polarity).
- GLUE Benchmark: MNLI, MRPC, QNLI, QQP, STS-B, RTE, CoLA, and SST-2.
- Syntactic Tasks: POS tagging, dependency labeling, and head identification.
- SyntaxGym: Targeted syntactic evaluations (anaphor licensing).
Key Insights and Ideas
- Sensitivity as Nonlinearity: Sensitivity essentially measures the "wiggliness" or nonlinearity of a task's decision boundary. High-sensitivity tasks have complex boundaries where many different input features interact non-linearly.
- The LSTM Bias: While LSTMs are theoretically capable of representing high-sensitivity functions (like the Parity function), the authors found they have a strong inductive bias toward learning low-sensitivity functions. This explains why vanilla LSTMs struggle with reasoning tasks even when they have enough parameters.
- Why Pretraining Works: The results suggest that massive pretraining (like BERT/RoBERTa) works because it creates a representation space where complex, high-sensitivity information is "unpacked." This allows a simple, low-sensitivity linear head to extract the correct answer easily.
- Redundancy vs. Reasoning: Text classification tasks (like sentiment) are low-sensitivity because they are highly redundant—you can change many words without flipping the label. Reasoning tasks (like RTE) are high-sensitivity because the logic is fragile; changing a single quantifier or entity often flips the entire meaning.
Key Results
- Predictive Power: Sensitivity is a strong predictor of model performance. There is a high negative correlation ($R \approx -0.8$) between a task's sensitivity and how well simple models (Bag-of-Embeddings or vanilla BiLSTMs) perform on it.
- Task Hierarchy: GLUE tasks, particularly those involving inference (RTE, MRPC, WSC), show significantly higher sensitivity than standard sentiment or subjectivity tasks.
- Constituent Dispersion: In sentiment analysis, the authors found that "high sensitivity" inputs are typically those where different parts of the sentence have conflicting sentiments (e.g., a "mixed" review), creating a more complex decision for the model.
Limitations and Future Work
- Oracle Dependence: The method relies on having a "strong" model (like RoBERTa) to act as a proxy for the true function. If the model has its own biases or "brittleness," the sensitivity estimate might reflect the model's flaws rather than the task's inherent difficulty.
- Computational Cost: Estimating block sensitivity is computationally expensive, as it requires sampling many substitutions from a language model for every possible subset of the input.
- Future Directions: The authors suggest applying this framework to other domains, such as computer vision, or using sensitivity to guide "curriculum learning," where a model starts with low-sensitivity examples and gradually moves to high-sensitivity ones.
Summary updated