No Simple Answer to Data Complexity: An Examination of Instance-Level Complexity Metrics for Classification Tasks (2025)

Abstract: Natural Language Processing research has become increasingly concerned with understanding data quality and complexity at the instance level. Instance-level complexity scores can be used for tasks such as filtering out noisy observations and subsampling informative examples. However, there exists a diverse taxonomy of complexity metrics that can be used for a classification task, making metric selection itself a difficult task. We empirically examine the relationship between these metrics and find that simply storing training loss provides similar complexity rankings as other more computationally intensive techniques. Metric similarity allows us to subsample data with higher aggregate complexity along several metrics using a single a priori available meta-feature. Further, this choice of complexity metric does not impact demographic fairness, even in downstream predictions. Researchers should consider metric availability and similarity, as using the wrong metric or sampling strategy may hurt performance.

## introduction understanding data complexity at the instancelevel has become increasingly important in natural language processing (nlp) and machine learning @xcite . recent work has shown that model performance can be improved through dataset curation, curriculum learning, and in-context learning techniques @xcite @xcite . to perform these techniques, researchers need some measurement of data complexity taken at the instance-level to logically filter or order data observations. nlp tasks are particularly well-suited for studying this area due to the complexity of language and its impact on classification results @xcite @xcite . indeed, these complexity-based techniques are increasingly being used for data filtering and re-weighting in nlp tasks including text classification, text generation, and question answering @xcite @xcite . due to its close connection to misclassification rate, instance complexity also has important implications for how we think about bias and fairness @xcite . prediction differences across subgroups have the potential to increase harm for underprivileged groups in certain systems (e.g., hiring decisions and facial recognition, @xcite . bias can exist in data, algorithms, and prediction outputs; addressing fairness across the ml pipeline can mitigate harm @xcite . any technique that alters the training data risks amplifying algorithmic bias @xcite . if a selected complexity metric disproportionately removes data from certain protected subgroups, this under-representation bias will be captured by the model. within the current large language model (llm) paradigm, the addition of complexity-based techniques risks exacerbating existing data biases from pretraining data content @xcite , human annotation @xcite , and user feedback @xcite . prior work proposed a taxonomy of data complexity for classification tasks @xcite . however, it is not always clear to researchers which metric they should use to leverage instance-level complexity in their experimental design @xcite . metrics are available at different points of the learning process (e.g., data preprocessing, embedding, training, etc.) and require varying amounts of computation. to address this gap, we seek to understand how different instance-level complexity metrics relate to one another and if there is any overlap in their measurement. we train a pool of text classifiers, compute a diverse set of complexity metrics, and examine how these complexity metrics correlate across different classification tasks. we also apply a naive a priori subsampling strategy using a complexity metric available before model training to examine whether including more complex observations might improve performance. our contributions in this work are: (i) an extended taxonomy of complexity, as well as a complexity analysis of various techniques; (ii) an empirical examination of the relationships between different complexity metrics across models and dependent variables; (iii) an examination of the combination of complexity and fairness when considering data complexity split by demographic groups. 1 the rest of the paper is organized as follows. section 2 reviews work related to instance-level complexity and the taxonomy we extend. we explain these updates in section 3 along with the representative metrics used in our experiments in section 4. we discuss findings in section 5 before offering concluding remarks in section 6 and limitations in section 7. ## related work research has long sought to quantify the complexity of text sequences using linguistic measures such as syntactic dependence and semantic entropy (gib-1 code and data available at https://github.com/ nd-hal/instance-complexity-metrics . @xcite . instance-level complexity has remained an nlp problem with the rise of computational techniques concerned with which text sequences are harder to learn @xcite @xcite . in this section, we begin with a broad view of complexity in ml and refine our focus to nlp applications and an applicable taxonomy of complexity for these tasks. ## instance complexity revisited next, we describe our literature search and the corresponding updates to the taxonomy of @xcite . we explain each metric from the updated taxonomy used in our experiment. ## experiment having defined our metrics, we empirically examined their relationships through a text classification task. we trained 220 models on 2 different subsampled train sets across 5 dependent variables, computing and storing all aforementioned complexity metrics. we then analyzed metric correlation as well as model performance and fairness on a held out set to determine patterns and differences. a roadmap of the experimental procedure can be found in figure 2 . we consider "metric availability" to be a binary indication of whether a metric can be computed before or after model training begins. we note that equations for added computational cost indicate the additional runtime needed to generate each metric on top of the standard training pipeline. ## conclusion we computed various complexity metrics for text classification and analyzed their correlation across dependent variables. these findings supported updates to the current taxonomy on classification complexity to consider metric availability and computational efficiency. we found that simply storing training loss captured similar complexity of computationally intensive model-based metrics such as irt difficulty and instance hardness. further, sampling on a single a priori available meta-feature created datasets that were complex across separate metrics. we only found one difference in upstream fairness and no downstream impact from employing these complexity metrics in a sampling strategy.