Abstract
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.
Introduction
In natural language processing (NLP), the intuitive notion that some tasks are "harder" than others is widely accepted. For instance, sentiment analysis is often solvable with simple bag-of-words models, whereas Natural Language Inference (NLI) requires sophisticated architectures like Transformers. However, a unified theoretical framework to quantify this difficulty has been missing. Existing metrics like the Chomsky Hierarchy or Kolmogorov complexity often fail to account for real-world data distributions or are uncomputable. This paper proposes sensitivity—a concept from Boolean function theory—as a practical measure of task complexity. Sensitivity quantifies how many disjoint parts of an input can independently flip a model's prediction, providing a formal lens through which to view task difficulty.
Methodology: Quantifying Sensitivity
The authors generalize the "sensitivity" of Boolean functions to natural language. Block Sensitivity measures how many disjoint subsets (blocks) of an input sequence can be modified to change the output label. In low-sensitivity tasks, the output is predictable from redundant information (e.g., multiple positive adjectives in a review). In high-sensitivity tasks, small changes in many different locations can flip the meaning (e.g., changing a single quantifier in a logic-heavy sentence).
To estimate sensitivity on real data, the study uses a strong "oracle" model (RoBERTa) to provide labels and a masked language model (XLNet) to generate plausible word substitutions. This ensures that the sensitivity measure reflects the natural language distribution. Theoretical analysis further proves that simple lexical classifiers have a mathematical ceiling on the sensitivity they can express, suggesting an inherent limitation in their reasoning capabilities.
Key Insights: The LSTM Bias and Pretraining
A critical finding is the LSTM Bias. While LSTMs can theoretically represent high-sensitivity functions, they possess a strong inductive bias toward learning low-sensitivity ones. This explains why vanilla LSTMs struggle with complex reasoning tasks even with sufficient parameters. Conversely, the success of massive pretraining (e.g., BERT, RoBERTa) can be attributed to its ability to "unpack" high-sensitivity information into a representation space where it can be extracted by simple, low-sensitivity linear decoders.
Results: A Hierarchy of Task Difficulty
The study evaluated sensitivity across 15 tasks, including standard text classification (MR, SUBJ, CR, MPQA), the GLUE benchmark, and various syntactic tasks.
Key results include:
- Predictive Power: Sensitivity strongly predicts model performance, with a high negative correlation ($R \approx -0.8$) between a task's sensitivity and the performance of simple models like vanilla BiLSTMs.
- Task Hierarchy: GLUE tasks involving inference (e.g., RTE, MRPC) show significantly higher sensitivity than sentiment or subjectivity tasks.
- Redundancy vs. Reasoning: Sentiment tasks are low-sensitivity due to high redundancy. Reasoning tasks are high-sensitivity because their underlying logic is fragile; a single word change often flips the entire label.
Conclusion and Future Directions
The primary limitation of this framework is its dependence on an "oracle" model (RoBERTa). If the oracle is brittle, the sensitivity estimate may reflect model flaws rather than inherent task difficulty. Additionally, the computational cost of estimating block sensitivity is high due to the required sampling. Future work could extend this framework to other domains like computer vision or use sensitivity to guide curriculum learning, starting models on low-sensitivity examples before progressing to more complex ones.
Summary updated