# Beyond Flesch-Kincaid: Prompt-based Metrics Improve
Difficulty Classification of Educational Texts

Donya Rooein1, Paul Röttger1, Anastassia Shaitarova2, Dirk Hovy1

1Bocconi University, 2University of Zurich
{donya.rooein, paul.rottger<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Using large language models (LLMs) for educational applications like dialogue-
based teaching is a hot topic. Effective teaching, however, requires teachers
to adapt the difficulty of content and explanations to the education level of
their students. Even the best LLMs today struggles to do this well. If we want
to improve LLMs on this adaptation task, we need to be able to measure
adaptation success reliably. However, current Static metrics for text
difficulty, like the Flesch-Kincaid Reading Ease score, are known to be crude
and brittle. We, therefore, introduce and evaluate a new set of Prompt-based
metrics for text difficulty. Based on a user study, we create Prompt-based
metrics as inputs for LLMs. They leverage LLM’s general language understanding
capabilities to capture more abstract and complex features than Static
metrics. Regression experiments show that adding our Prompt-based metrics
significantly improves text difficulty classification over Static metrics
alone. Our results demonstrate the promise of using LLMs to evaluate text
adaptations to different education levels.

Beyond Flesch-Kincaid: Prompt-based Metrics Improve
Difficulty Classification of Educational Texts

Donya Rooein1, Paul Röttger1, Anastassia Shaitarova2, Dirk Hovy1 1Bocconi
University, 2University of Zurich {donya.rooein, paul.rottger,
<EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Large language models (LLMs) today can answer wide-ranging questions and
explain complex concepts with high accuracy (Chung et al., 2022; OpenAI,
2023). This development has motivated explorations into their uses for
education, ranging from automated student assessment and personalised content
to dialogue-based teaching Upadhyay et al. (2023); Sallam (2023); Yan et al.
(2023); Hosseini et al. (2023).

Figure 1: Schematic overview of our approach to text difficulty
classification. We calculate relevant Static and Prompt-based metrics for a
given input text. Either or both metrics are then fed into a regression
classifier that makes a final classification.

Effective teaching requires that the difficulty of content and explanations is
tailored to the education level of the students. Human teachers are trained to
do this, and adjust their material and style without much prompting. However,
this adaptation is not just the adjustment of one variable. It is a complex
undertaking, touching upon lexicon, syntax, pragmatics, and semantics.
Improving the ability of LLMs to adapt their outputs to different levels of
education is therefore crucial to unlocking their usefulness for education.
One of the most basic requirements to achieve this goal is a way to measure
adaptation success.

Measuring whether a given output is appropriate for a given level of
education, however, is a very difficult task. Existing Static metrics, like
the Flesch-Kincaid Reading Ease score (Flesch, 1948), are based on simple
formulas, heuristics, and word counts. They share the brittleness of all
heuristic approaches and are known to be noisy measures of text difficulty at
best. Also, these metrics were developed for longer-form explanations, like
those found in textbooks, rather than dialogue-style teaching. Due to their
reliance on counts, their estimates are unreliable in shorter formats. We need
better metrics to make improvements on the adaptability of LLMs to education
levels measurable. Only when we can measure improvements can we make tangible
progress in leveraging LLMs for educational applications.111Similarly, metrics
like BLEU Papineni et al. (2002), ROUGE Lin (2004), and BLANC Recasens and
Hovy (2011), among others, kickstarted and sustained the development of
automated approaches to machine translation, summarization, and coreference
resolution, respectively.

As an alternative to Static metrics, we can use classifiers to predict the
educational level of a given text. They generalize better and can be applied
to texts of varying lengths. However, these classifiers are expensive to train
and require more training data than we usually have for a niche domain like
educational purposes. Similarly, human assessment of difficulty may provide a
gold standard, but it is expensive to collect and, like all annotation tasks,
suffers from disagreement.

In this paper, we introduce and evaluate a new set of Prompt-based metrics for
text difficulty as complements to existing Static metrics. Prompt-based
metrics are LLM prompts that exploit the general language understanding
capabilities of LLMs to capture more abstract features of educational texts
than Static metrics. For example, LLMs can flexibly classify the topic of a
text, which is one adaptation technique used by teachers to adjust the content
which called curriculum compacting in pedagogy Stamps (2004). This would be
difficult to do with Static approaches.

We develop our selection of Prompt-based metrics based on a user study, where
we ask a group of university students to 1) assess the difficulty of
educational texts and explain their reasoning, and 2) come up with prompts for
an LLM to change the difficulty of a given text. We then translate the
qualitative findings from both parts of the study into concrete LLM prompts
that serve as Prompt-based metrics. We incorporate prompts from other studies
to manage text readability with LLMs (Imperial and Madabushi, 2023; Gobara et
al., 2024). We evaluate the ability of our new Prompt-based metrics to measure
text appropriateness for different education levels with a series of
regression experiments.

While Prompt-based metrics perform on par or better than zero-shot and few-
shot LLM classifiers, they are less useful for text difficulty classification
by themselves than Static metrics. However, combining Prompt-based and Static
metrics significantly improves performance. This suggests that Prompt-based
metrics capture relevant signals beyond those captured by the large number of
Static metrics.

A combination of Static and Prompt-based metrics also provides a deeper
understanding of the key metrics or features that influence complexity than
classifiers could. Additionally, the factors that contribute to complexity in
a scientific text differ from those in a medical or a legal document. By
considering a range of metrics, we can develop more accurate domain-specific
measures. Our multifaceted approach allows us to break down complexity into
its basic components, such as its appropriateness for different education
levels, lexical or syntactic complexity, thematic topics, and text
readability.

Overall, Prompt-based metrics empower educators to develop more effective
content development strategies with LLMs to engage learners of all levels and
backgrounds. We could have directly trained classifiers; however, this
approach would not have enabled us to identify the most relevant metrics.

#### Contributions

  1. 1.

We conduct a user study to motivate the creation of novel Prompt-based metrics
of text difficulty for educational texts (§2).

  2. 2.

We show in a series of regression experiments that these Prompt-based metrics
hold additional value for text difficulty classification beyond what Static
metrics can capture (§4.3).

  3. 3.

By leveraging the interpretability of our regressions, we highlight the
relative importance of individual Static and Prompt-based metrics (§4.5).

##  2 User Study

Our Prompt-based metrics for text difficulty are prompts based on the results
of a one-day user study we ran with a group of university students in November
2023.

###  2.1 Study Design

The user study consisted of two main parts.

In the first part of our study, we asked participants to review 60 educational
texts randomly sampled from the ScienceQA dataset Lu et al. (2022). Each text
consists of a question (e.g., “What is the mass of a dinner fork?”) with
answer choices (“70 grams or 70 kilograms”) and a longer-form explanation of
the solution. All texts we select here are authentic educational materials
from the social, natural, or language sciences in schools. Participants were
tasked with a) labeling the education level of each text as appropriate for
either elementary school, middle school, or high school and b) explaining the
reasoning behind their choice in a short, free-text answer.

In the second part of our study, we asked participants to rewrite scientific
text explanations, also sampled from ScienceQA, to be appropriate for
different education levels, with the help of an LLM – in this case, ChatGPT.
For example, participants were asked to rewrite a middle school explanation of
thermal energy at the elementary and high school levels with the help of
prompts. We recorded the prompts they used to get ChatGPT to accomplish the
adaptation for them. Thus, we collected prompts that are used both for text
simplification and for text complexification.

###  2.2 Study Participants

We ran our study as part of a hackathon at the University of Zurich. There
were seven participants aged between 21 and 31 years. Four participants were
female, three male. All participants were students at Department of
Computational Linguistics from University of Zurich, enrolled at the time in
programs specializing in computational linguistics, computer science, and AI.
Five were studying for a bachelor’s degree and two for a master’s degree. The
participants held prior educational degrees from school systems across five
different countries. Their native languages include English, Italian, German,
Greek, and Ukrainian. They self-reported their English language proficiency at
C1 and C2 levels. Participants were compensated in study credits that could be
counted towards completing their program.

###  2.3 Study Results

The first task of our study yielded 276 classification labels together with
their corresponding descriptive justifications. These include 120 label-
explanation pairs for middle school texts, 89 for high school, and 67 for
elementary school texts. In the second task of our study, we collected 103
prompts for text simplification and complexification. We share illustrative
examples of classifications, explanations, and prompts in Appendix A.

In the next section, we use the qualitative results from our study to motivate
the construction of novel Prompt-based metrics for text appropriateness for
various education levels.

##  3 Metrics for Text Difficulty

###  3.1 Prompt-based Metrics

Since the metrics we introduce are based on the prompts of language models
rather than discrete heuristics, we refer to them as ‘Prompt-based’ to
distinguish them. The goal of the Prompt-based metrics we develop is to
capture more abstract features of educational texts than would be possible
with Static metrics, which typically focus on individual words and their
statistics.

Figure 2: An illustrative example of the Prompt-based metric process. The
green box contains the education text from the ScienceQA dataset. The blue box
shows the predicted educational level and the explanation. The red box
contains the Prompt-based metrics based on the sample. Figure 3: High-level
view of the derivation process for the Prompt-based metrics using n-gram
frequencies. Function words are excluded.

We derive our Prompt-based metrics from the results of our user study. Figure
2 shows an illustrative example of our derivation process. We consider users’
explanations for why they consider a specific educational text to be of
elementary, middle, or high school level difficulty. Then, we identify
recurring attributes and other explanation features that several users mention
to reflect them in Prompt-based metrics. We examine the distributions of
unigrams, bigrams, and trigrams across all three labels, excluding function
words (see Figure 3). Some of the most frequent unigrams for the elementary
level include simple, basic, elementary; for the high school level, high,
complex, concepts; and for the middle school level, explicit, explanation,
middle.

We qualitatively assessed the n-gram distributions, considering both
frequencies and topic appropriateness, before finalizing the query
construction. Each Prompt-based metric is a simple yes-no question, which we
use to prompt the LLMs. These metrics encompass the most frequent unigrams and
less common bigrams and trigrams derived from the findings of our study.

While, Gobara et al. (2024) demonstrate a correlation between readability
scores of LLM-generated texts in education and human assessments, Imperial and
Madabushi (2023) indicate challenges in LLMs effectively adjusting the
readability of text. We construct 63 Prompt-based metrics using this process.
Each Prompt-based metric relates to either education level (30 metrics),
lexical or syntactic complexity (8 metrics), and the topic of the text at hand
(10 metrics). In addition, we include metrics about the text’s readability
score (15 metrics) based on the work by Imperial and Madabushi (2023). The
complete list of all our Prompt-based metrics is in Appendix C.

###  3.2 Existing Static Metrics

Static metrics are the baseline we want to improve on. All Static metrics are
based on simple formulas, heuristics, or counts of words and other textual
features. These properties make them simple to apply but limit the conceptual
complexity of what they can reasonably measure. In total, we include 46 Static
metrics, selected from those compiled in prior work (Flekova et al., 2016;
Yaneva et al., 2019; Xue et al., 2020; Baldwin et al., 2021).

These metrics encompass a variety of linguistic characteristics, spanning from
basic text-level measures like vocabulary size and word frequency to sentence-
level attributes such as sentence length and syntactic complexity.
Additionally, they take into account the question-answering structure within
the input text. In the ScienceQA dataset, each question is paired with its
respective solution and corresponding lecture. This segmentation of
information across educational levels facilitates the computation of Static
features for each section of the question-answer solution and lecture
independently. For the complete list of 46 Static metrics, see Appendix C.

##  4 Experiments

We conduct a series of classification experiments to evaluate the usefulness
of our novel Prompt-based metrics for measuring text difficulty. We use a
subset of the ScienceQA dataset, which contains question-answer pairs across
several topics and education levels. Specifically, we run multinomial logistic
regressions based on Static metrics, Prompt-based metrics, and the combination
of the two to evaluate the marginal benefits of our new Prompt-based metrics.
We also compare these regression approaches to using an LLM for zero-shot and
few-shot classification.

###  4.1 Dataset

All our experiments are based on the ScienceQA dataset Lu et al. (2022). There
are 21,208 texts in ScienceQA. Each text consists of a question with answer
choices, and a longer-form explanation of the solution. Texts in ScienceQA are
classified according to their grade level using the K12 system from the US
education system. We simplify this classification by collapsing the 12-grade
levels into just three: elementary school (grades 1 to 5), middle school
(grades 6 to 8), and high school (grades 9 to
12).222https://usahello.org/education/children/grade-levels/ From the 21,208
texts in ScienceQA, we sample only those that do not use images in questions
or explanations. We then deduplicate and sample 1,516 texts for each education
level to create a balanced dataset of 4,548 texts. Of these 4,548 texts, we
use 3,638 (80%) for training and 910 (20%) for evaluation. To our knowledge,
ours is the first use of the ScienceQA dataset for training and evaluating
text difficulty classifiers.

###  4.2 LLMs for Prompt-based Metrics

We use LLMs to compute the 63 Prompt-based metrics described in Section 3.1.
In principle, any LLM can serve this purpose. With 63 metrics for 4,548 texts,
we get 286,524 prompts from each LLM. This amount is prohibitively expensive
for paid services like GPT4. Hence, we concentrate on state-of-the-art open
LLMs, which we can execute at a low cost: Llama2 (Touvron et al., 2023),
Mistral (Jiang et al., 2023), and Gemma (Google, 2024). Llama2, launched in
July 2023, comprises both pre-trained and fine-tuned LLMs, ranging in size
from 7 billion to 70 billion parameters. It has been reported to outperform
other open-access LLMs and exhibits capabilities comparable to ChatGPT across
various tasks. In this paper, we use Llama2-7b and Llama2-13b. The next model
is Mistral-7B, released in September 2023, another open LLM surpassing
similar-sized open LLMs. We use Mistral-7b-Instruct-v0.2, which was published
in December 2023.

The last model we use is Gemma7b-it, based on the Gemma base model and trained
on open-source mathematics datasets.

We set the model temperature to zero to make responses deterministic. The
maximum response length is 256 tokens. Otherwise, we use standard generation
parameters from the Hugging Face transformers library. We collected all
responses in February 2024.

###  4.3 Multinomial Logistic Regression

We use simple multinomial logistic regression to classify the difficulty level
of texts. The task is to predict the difficulty level $C_{i}$ of a given
educational text $S_{i}$. $C_{i}$ can take three ordinal values: elementary,
middle, or high school difficulty. Instead of including $S_{i}$ directly, we
include sets of Static and Prompt-based metrics $\textbf{M}_{i}$ that are
computed based on $S_{i}$. We regress $\textbf{M}_{i}$ on $C_{i}$ on the 3,638
training texts and then evaluate on the 910 test education texts.

We vary which metrics we include across experimental setups to evaluate the
marginal benefits of different metrics. There are three main setups of
interest: 1) Prompt-based metrics only, 2) Static metrics only, 3) the
combination of the two, which we refer to as Combo.

###  4.4 Baseline: Zero- and Few-Shot Classification

We exploit the general language capabilities of LLMs to compute Prompt-based
metrics, which we then use as inputs to a logistic classifier for text
difficulty. A natural follow-up question is whether LLMs could directly
predict text difficulty related to education levels. Therefore, we incorporate
a baseline for zero-shot and few-shot text classification. We test zero-shot
and few-shot classification with the same LLMs that we use for calculating our
Prompt-based metrics. As an additional comparison point, we test GPT-4 Turbo.

Note that while the logistic classifier is fitted to our training data, the
zero-shot LLM has not seen any examples at inference time. In the few-shot
setting, we provide two examples for each education level and prompt the model
to assign one of the desired labels without explanations.

To investigate the effect of different prompting styles, we test five distinct
prompt templates in our zero-shot setup, each consisting of 25-30 words.
Additionally, each prompt contains a textual segment describing the text of
the science question answering for educational-level classification. We
compare performance across the five prompt templates to determine the most
effective prompt, i.e., the strongest baseline for our experiments. We
evaluate the models’ responses on a subset of randomly selected samples
(n=100). The lowest performance stands at 29%, while the highest achievement
reaches 42%. We proceed with our experiments under zero-shot and few-shot
setups, using the best performance style as our baselines. The selected prompt
for zero-shot experiments is: “Your task is to predict the education level
corresponding to a given text. You are provided with three labels to choose
from: 1) elementary school 2) middle school 3) high school. Text: [text]
Educational level: ”

We instructed LLMs to return one of the education levels. Due to the
difficulty of LLMs in directly predicting the levels and complexity of the
text, we have responses without the desired educational level. In this case,
we assigned a default level to this invalid response, which is the “elementary
level”. For example, Llama2-13b has 2.86% invalid in zero-shot and 4.07% in
few-shot. The most-predicted class is elementary school level, with 75.93% in
zero-shot and 80% in few-shot. The number of invalid responses for other
models is available in the Appendix D.

###  4.5 Results

#### Overall Performance

Table 1 reports the overall results of our different logistic classifier
setups along with the Zero-shot and Few-shot LLM classification baselines. We
use Gemma-7b, Mistral-7b, Llama2-7b, and Llama2-13b across all referenced
classification methods. GPT-4 is exclusively used in the baseline due to the
high cost of experiments.

Method | Gemma-7b | Mistral-7b | Llama2-7b | Llama2-13b | GPT-4
---|---|---|---|---|---
Prompt-based Reg. | 0.73 | 0.54 | 0.45 | 0.77 | -
Static Reg. | 0.81 | 0.81 | 0.81 | 0.81 | -
Combo Reg. | 0.95 | 0.82 | 0.81 | 0.88 | -
Zero-shot LLM | 0.35 | 0.34 | 0.35 | 0.35 | 0.51
Few-shot LLM | 0.37 | 0.37 | 0.45 | 0.47 | 0.65
Table 1: Macro-F1 for difficulty classification on test. Prompt-based metrics,
zero-shot, and few-shot (two examples) performance are specific to each LLM.
Static metrics are the same across models. Zero-shot and few-shot
classification use GPT4. Best performance per model in bold.

The findings highlight the consistent superiority of the Combo approach in
achieving the highest macro-F1 score, surpassing all other models.
Specifically, while the Llama2-7b model exhibits comparatively lower
performance when employing the Prompt-based method, the Llama2-13b model
demonstrates the best performance across Prompt-based metrics. Notably, the
Gemma-7b model stands out as the best-performing model when using the Combo
metric. In terms of Prompt-based regression, the average macro-F1 score across
all models stands at 0.62, with all Prompt-based metrics obtained directly
through LLMs’ binary classification prompts. The best performance overall is
achieved by Combo, which combines both sets of metrics, resulting in a
macro-F1 score of 0.86.

Nearly all models encounter difficulty in predicting the educational level
across both Zero-shot and Few-shot methodologies. However, in these
experiments, the Few-shot approach notably enhances the macro-F1 score.
Additionally, Table 1 highlights that the best performance among baseline
approaches is achieved by GPT-4, attaining a macro-F1 score of 0.63 in the
Few-shot setting.

#### Performance by Education Level

To delve into the performance more comprehensively, we split out the results
for each regression setup by label, i.e., education level, in Table 2. Here,
we display only the top-performing model based on the Prompt-based metric and
provide the details of the other models in Appendix D.

| Level | Precision | Recall | F1-Score
---|---|---|---|---
Prompt | Elem. | $0.84$ | $0.82$ | $0.83$
Middle | $0.84$ | $0.64$ | $0.73$
High | $0.68$ | $0.84$ | $0.75$
Static | Elem. | $0.86$ | $0.85$ | $0.86$
Middle | $0.75$ | $0.71$ | $0.73$
High | 0.84 | $0.88$ | $0.84$
Combo | Elem. |  0.95* |  0.93* |  0.94*
Middle |  0.89* |  0.77* |  0.83*
High | $0.82$ |  0.93* |  0.87*
Table 2: Difficulty classification performance on test. $*=$ statistically
significant improvements of Combo over Static at $p=0.05$ (bootstrap). Prompt-
based metrics use Llama2-13b. Best performance per level in bold.

The overall picture of Prompt-based regression shows that it faces difficulty
in the classification of educational level, while Static performs much better,
and Combo performs best, which indicates that there is an additional benefit
to including the Prompt-based metrics.

We collect 1,000 bootstrap samples to train and test the logistic regression
models for each approach. This method helps in understanding the variability
and reliability of the model performance. We use t-tests to determine if the
observed differences in accuracies are statistically significant over Combo
vs. Static. Results in Table 2 indicate a statistically significant
improvement.

#### Feature Importance

One big benefit of our regression approach over, for example, classification
with an LLM, is that we can easily measure the feature importance of each
metric that goes into the classification result. For this purpose, we
calculate univariate F-tests between each metric and the difficulty level
variable. Table 3 shows the top-five most important features, each among the
Prompt-based and the Static metrics, based on these F-tests for Llama2-13b
model.

| Rank | Metric | F
---|---|---|---
Prompt Metrics | 1 | Based on the ARI, is this text suitable for ES readers? | 251.77*
2 | Is this text relevant to curriculum topics for ES students? | 249.07*
3 | Is this text about math? | 248.17*
4 | Is this text about natural science? | 240.07*
5 | Does this text contain simple examples? | 235.96*
Static Metrics | 1 | Gunning Fog (measures readability) | 817.86*
2 | Coleman-Liau index (measures readability) | 785.60*
3 | Flesch-Kincaid Reading Ease (measures readability) | 725.15*
4 | Automated Readability Index (measures Readability) | 686.87*
5 | Number of unique Words (measures lexical diversity) | 613.89*
Table 3:  Five most important features for Prompt-based and Static metrics in
Llama2-13b. Feature importance is measured using univariate F-tests. Larger F
indicates higher feature importance. (ES: Elementary School, ARI: Automated
Readability Index) * indicates significance at >99.999% confidence.

Most notably, the Prompt-based metrics are generally less important than the
Static metrics. On average, the top five most important Static metrics are at
least twice as significant as the top five Prompt-based metrics. The Static
metrics mainly focus on readability and lexical diversity, while Prompt-based
metrics capture topic relevancy and the inclusion of simple examples. Although
they may not carry the same weight, all of the top metrics are highly
statistically significant.

##  5 Discussion

###  5.1 The Value of Prompt-based Metrics

Prompt-based metrics by themselves may not be a good-enough basis for
classifying text difficulty (Table 1). Static metrics are much more effective
by comparison. However, our results also show that Prompt-based metrics do
indeed capture relevant features of the text that are not captured by Static
metrics since models that combine both kinds of metrics clearly perform best
overall. This is despite the fact that the Static metrics we include are many
and highly diverse.

The practical usefulness of the particular Prompt-based metrics outlined in
this paper is evident. Moreover, the broader application of Prompt-based
metrics holds promise for evaluating text complexity. Our experiments indicate
that the Combo approach outperforms other models consistently. Notably, most
models exhibit superior macro-F1 scores in predicting elementary-level texts,
suggesting that distinguishing science questions at the elementary level is
more discernible compared to other educational levels.

Furthermore, we present the feature importance of Prompt-based metrics, noting
that the primary Prompt-based metrics pertain to readability,
understandability, and suitability of text for particular educational levels.
Additionally, topic relevance (e.g., math or natural science) emerges as a
significant feature. In top 5 best features of Static metrics are summarized
through readability scores ranging from the Gunning Fog Index to the Flesch-
Kincaid Index, along with a metric evaluating the lexical diversity of the
text.

Better Prompt-based metrics identified in future work may be even more
effective complements to Static metrics.

###  5.2 Limitations

#### Limited Scope of User Study

The user study we conducted provides a clear empirical motivation for the
Prompt-based metrics we selected. This in itself is a core contribution of our
work. However, due to resource and time constraints, the sample of
participants in the study is fairly small and of limited diversity. Future
work could improve on our approach by conducting larger studies or recruiting
participants from even more relevant professions (e.g. teachers) to motivate
the selection of even better Prompt-based metrics.

#### Limited Availability of Relevant Data

Our experiments are mostly constrained by the availability of relevant data
for text difficulty classification. The ScienceQA dataset that we use is, to
our knowledge, the only dataset that fits our experimental setup in terms of
size and detail on education level. Therefore, we cannot make any strong
claims about the generalisability of our results. Future work could invest
into building new datasets and testing cross-domain performance of both Static
and Prompt-based metrics, which would give useful insights into which text
features are most generally indicate of text difficulty.

##  6 Related Work

###  6.1 Question Answering Datasets in Education

The review study by AlKhuzaey et al. (2023) about the literature on item
difficulty classification reveals a significant shortage of publicly
accessible datasets with items that are labeled according to their difficulty
levels. For example, Hsu et al. (2018) gathered their dataset from national
standardized entrance tests that often concentrate on the medical and language
fields, annotated with the performance data of 270,000 examinees. This study
includes the necessity for a publicly accessible collection of standardized
datasets and the need for further exploration into alternative methods for
feature elicitation and classification modeling. The lack of publicly
available datasets for measuring difficulty has led researchers toward the
domain of Automatic Question Generation (AQG) in recent years. Typically,
questions generated by AQG tend to be more straightforward in structure and
cognitive demand than questions written by humans.

Most of these automatically generated questions are basic, primarily
addressing only the first level of Bloom’s taxonomy, which is focused on
recall Leo et al. (2019). Another source of educational datasets is retrieved
from online learning platforms or websites specific to the study’s domain. An
example includes the collection of 1,657 programming problems from
LeetCode333https://leetcode.com, labeled with the number of solutions
submitted and the pass rate for each problem. Additionally, fewer datasets are
from domain-specific textbooks and preparation books, particularly prevalent
in the language domain for their role in training students for language
proficiency exams. Domain experts developed the remaining sources to meet
specific study goals, and according to AlKhuzaey et al. (2023), only 7% from
school or university-level assessments.

The Stanford Question Answering Dataset (SQuAD), developed by Rajpurkar et al.
(2016), features 150,000 questions in the form of paragraph-answer pairs
sourced from Wikipedia articles. This dataset was utilized by Bi et al. (2021)
to develop and test their models for predicting the difficulty of reading
comprehension questions. Lu et al. (2022) created a multimodal science
question-answering datasets, which includes 21,000 English passages from
school reading exams, each accompanied by four multiple-choice questions. The
ScienceQA dataset provides metadata fields for each question, including
extensive solutions and general explanations which made it suitable for this
study Lu et al. (2022).

###  6.2 Automatic Evaluation of Educational Content

The difficulty level classification of questions presented to students is
crucial for facilitating more effective and efficient learning. Pérez et al.
(2012) shows teachers usually fail to identify the correct difficulty level of
the questions according to their students’ answers and final scores. The
student’s perception of the difficulty also changes across grades and
subjects. AlKhuzaey et al. (2023) discovers that linguistic features
significantly influence the determination of question difficulty levels in
educational assessments. They have explored various syntactic and semantic
aspects to understand the complexity of these questions. Crossley et al.
(2019) shows the value of using crowdsourcing methods to gather human
assessments of text comprehension, coupled with linguistic attributes derived
from advanced readability metrics. This approach aids in creating models that
explain how humans understand and process text, as well as factors influencing
reading speed. Crossley et al. (2023) examined the effectiveness of new
readability formulas developed on the CommonLit Ease of Readability (CLEAR)
corpus using more efficient sentence-embedding models and comparing them to
traditional readability formulas. They did not test LLMs directly for the
difficulty classification task. In their respective studies, Imperial and
Madabushi (2023), Rooein et al. (2023), and Gobara et al. (2024) leverage
Large Language Models (LLMs) for content generation, focusing specifically on
controlling readability scores. Their research illuminates the inherent
challenges and limitations encountered when attempting to effectively adapt
LLMs for this purpose.

##  7 Conclusion

Good teachers succeed in making the material understandable for their
respective audiences. This adaptation is a complex process that goes well
beyond replacing individual words and phrases. However, existing Static
metrics for text difficulty, like the Flesch-Kincaid Reading Ease score, still
focus on precisely those elements. As a result, these metrics are crude and
brittle, failing to adapt to new domains and working mainly on long-form
documents.

Our experiments reveal the promising potential of LLMs in predicting
educational difficulty through using the Prompt-based metrics rather than
prompting the model directly. These metrics were derived from a small-scale
user study involving students. Empirically, we demonstrate that when combined
with traditional static metrics, these Prompt-based metrics enhance text
difficulty classification.

Our study paves the way for novel applications of LLMs in educational
contexts. By involving more educational stakeholders, such as teachers, we can
gather more representative Prompt-based metrics, facilitating future
advancements in difficulty classification.

## Ethical Considerations

The participants in the user study we used in our paper were student
volunteers for a course on related topics. They could leave the study at any
point and were compensated in course credits that could be counted towards
their study program. The study was conducted in accordance with the rules of
the host university and passed its ethics assessment. The risk for harm to the
participants in this setting was assessed as minimal.

## Acknowledgements

Donya Rooein and Dirk Hovy were supported by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation program
(grant agreement No. 949944, INTEGRATOR). Paul Röttger was supported by a MUR
FARE 2020 initiative under grant agreement Prot. R20YSMBZ8S (INDOMITA). They
are members of the MilaNLP group and the Data and Marketing Insights Unit of
the Bocconi Institute for Data Science and Analysis (BIDSA). Anastassia
Shaitarova was supported by the National Centre of Competence in Research
“Evolving Language”, Swiss National Science Foundation (SNSF) Agreement 51NF40
180888.

## References

  * AlKhuzaey et al. (2023) Samah AlKhuzaey, Floriana Grasso, Terry R Payne, and Valentina Tamma. 2023.  Text-based question difficulty prediction: A systematic review of automatic approaches.  _International Journal of Artificial Intelligence in Education_ , pages 1–53.
  * Baldwin et al. (2021) Peter Baldwin, Victoria Yaneva, Janet Mee, Brian E Clauser, and Le An Ha. 2021.  Using natural language processing to predict item response times and improve test construction.  _Journal of Educational Measurement_ , 58(1):4–30.
  * Bi et al. (2021) Sheng Bi, Xiya Cheng, Yuan-Fang Li, Lizhen Qu, Shirong Shen, Guilin Qi, Lu Pan, and Yinlin Jiang. 2021.  Simple or complex? complexity-controllable question generation with soft templates and deep mixture of experts model.  _arXiv preprint arXiv:2110.06560_.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. 2022.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_.
  * Crossley et al. (2023) Scott Crossley, Joon Suh Choi, Yanisa Scherber, and Mathis Lucka. 2023.  Using large language models to develop readability formulas for educational settings.  In _International Conference on Artificial Intelligence in Education_ , pages 422–427. Springer.
  * Crossley et al. (2019) Scott A Crossley, Stephen Skalicky, and Mihai Dascalu. 2019.  Moving beyond classic readability formulas: New methods and new models.  _Journal of Research in Reading_ , 42(3-4):541–561.
  * Flekova et al. (2016) Lucie Flekova, Daniel Preoţiuc-Pietro, and Lyle Ungar. 2016.  Exploring stylistic variation with age and income on twitter.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 313–319.
  * Flesch (1948) Rudolph Flesch. 1948.  A new readability yardstick.  _Journal of applied psychology_ , 32(3):221.
  * Gobara et al. (2024) Seiji Gobara, Hidetaka Kamigaito, and Taro Watanabe. 2024.  Do llms implicitly determine the suitable text difficulty for users?  _arXiv preprint arXiv:2402.14453_.
  * Google (2024) Google. 2024.  Responsible Generative AI Toolk, GemmaTechnical Report.  https://ai.google.dev/gemma/docs.  Accessed: March 6, 2024.
  * Hosseini et al. (2023) Mohammad Hosseini, Catherine A Gao, David M Liebovitz, Alexandre M Carvalho, Faraz S Ahmad, Yuan Luo, Ngan MacDonald, Kristi L Holmes, and Abel Kho. 2023.  An exploratory survey about using chatgpt in education, healthcare, and research.  _medRxiv_ , pages 2023–03.
  * Hsu et al. (2018) Fu-Yuan Hsu, Hahn-Ming Lee, Tao-Hsing Chang, and Yao-Ting Sung. 2018.  Automated estimation of item difficulty for multiple-choice tests: An application of word embedding techniques.  _Information Processing & Management_, 54(6):969–984.
  * Imperial and Madabushi (2023) Joseph Marvin Imperial and Harish Tayyar Madabushi. 2023.  Flesch or fumble? evaluating readability standard alignment of instruction-tuned language models.  _arXiv preprint arXiv:2309.05454_.
  * Jiang et al. (2023) Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_.
  * Leo et al. (2019) Jared Leo, Ghader Kurdi, Nicolas Matentzoglu, Bijan Parsia, Ulrike Sattler, Sophie Forge, Gina Donato, and Will Dowling. 2019.  Ontology-based generation of medical, multi-term mcqs.  _International Journal of Artificial Intelligence in Education_ , 29:145–188.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Lu et al. (2022) Pan Lu, Swaroop Mishra, Tanglin Xia, Liang Qiu, Kai-Wei Chang, Song-Chun Zhu, Oyvind Tafjord, Peter Clark, and Ashwin Kalyan. 2022.  Learn to explain: Multimodal reasoning via thought chains for science question answering.  _Advances in Neural Information Processing Systems_ , 35:2507–2521.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Pérez et al. (2012) Elena Verdú Pérez, Luisa M Regueras Santos, María Jesús Verdú Pérez, Juan Pablo de Castro Fernández, and Ricardo García Martín. 2012.  Automatic classification of question difficulty level: Teachers’ estimation vs. students’ perception.  In _2012 Frontiers in Education Conference Proceedings_ , pages 1–5. IEEE.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  _arXiv preprint arXiv:1606.05250_.
  * Recasens and Hovy (2011) Marta Recasens and Eduard Hovy. 2011.  Blanc: Implementing the rand index for coreference evaluation.  _Natural language engineering_ , 17(4):485–510.
  * Rooein et al. (2023) Donya Rooein, Amanda Cercas Curry, and Dirk Hovy. 2023.  Know your audience: Do llms adapt to different age and education levels?  _arXiv preprint arXiv:2312.02065_.
  * Sallam (2023) Malik Sallam. 2023.  Chatgpt utility in healthcare education, research, and practice: Systematic review on the promising perspectives and valid concerns.  _Healthcare_ , 11(6).
  * Stamps (2004) Lisa S Stamps. 2004.  The effectiveness of curriculum compacting in first grade classrooms.  _Roeper Review_ , 27(1):31–41.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_.
  * Upadhyay et al. (2023) Shriyash Upadhyay, Etan Ginsberg, and Chris Callison-Burch. 2023.  Improving mathematics tutoring with a code scratchpad.  In _Proceedings of the 18th Workshop on Innovative Use of NLP for Building Educational Applications (BEA 2023)_ , pages 20–28.
  * Xue et al. (2020) Kang Xue, Victoria Yaneva, Christopher Runyon, and Peter Baldwin. 2020.  Predicting the difficulty and response time of multiple choice questions using transfer learning.  In _Proceedings of the Fifteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 193–197.
  * Yan et al. (2023) Lixiang Yan, Lele Sha, Linxuan Zhao, Yuheng Li, Roberto Martinez-Maldonado, Guanliang Chen, Xinyu Li, Yueqiao Jin, and Dragan Gašević. 2023.  Practical and ethical challenges of large language models in education: A systematic literature review.  _arXiv preprint arXiv:2303.13379_.
  * Yaneva et al. (2019) Victoria Yaneva, Peter Baldwin, Janet Mee, et al. 2019.  Predicting the difficulty of multiple choice questions in a high-stakes medical exam.  In _Proceedings of the Fourteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 11–20.

##  Appendix A Selected Prompts from the User Study

We collect the top prompts of the students from the chat history with
analytical, manual, and AI Assistant (ChatGPT).

###  A.1 Elementary School:

\- Simplify a text for elementary school, using simple language for 6-12 years
olds. \- Create an elementary version of a high school lecture text. \-
Simplify a high school text for elementary school. \- Explain in a way an
8-year-old would understand. \- This is a text meant for high school students.
Can you help me make an appropriate version for elementary school students
with very simple language and comprehensive, easy-to-understand examples?

###  A.2 Middle School:

\- Give examples from middle school lectures. \- Adapt a high school text for
middle school, using less advanced language. \- Be more textbook-like and more
to the point for the level of middle school. \- Adapt content for a student in
middle school. \- Simplify a lecture text for middle school using illustrative
examples.

###  A.3 High School:

\- Enhance scientific accuracy and add comprehensive examples for the high
school level. \- Adapt a middle school text for high school, using advanced
language. \- Increase difficulty for high school, with advanced vocabulary and
scientific concepts. \- Can you make it more scientific and less story-
telling-like? \- Increase the difficulty level with comprehensive examples.

##  Appendix B Parameter settings

The Static metrics are collected by Python packages such as nltk(3.8.1),
pandas(2.2.0), textstat(0.7.3, spacy(3.7.4). We use nltk.download to get data
for ‘stopwords’, ‘cmudict’, ‘wordnet’, and ‘averaged_perceptron_tagger’.

We performed 8-bit quantization for collecting prompt-based metrics and
baselines, with a maximum input length of 2048 tokens and a maximum output
length of 256 tokens. This process was restricted to a single run due to our
utilization of pre-trained models readily accessible in HuggingFace
Transformers.

For Regression model, we use scikit-learn package and SelectKBest with
f_classif score function.

##  Appendix C List of Metrics

###  C.1 Static Metrics

Table 4 shows all static metrics.

Table 4: List of Static metrics Feature | Description
---|---
n_words_q | Number of words in the question
n_words_a_solution | Number of words in the solution of an answer
n_words_a_lecture | Number of words in the lecture
Text_Length | Length of the text
Word_Count | Total word count
Nouns | Number of nouns
Verbs | Number of verbs
Adjectives | Number of adjectives
Adverbs | Number of adverbs
Num_Numbers | Number of numeric characters
Num_Commas | Number of commas
Num_Complex_Words | Number of complex words
Num_Unique_Words | Number of unique words
Num_Content_Words | Number of content words
Num_Content_Words_No_Stopwords | Number of content words excluding stopwords
Word_Length_Syllables | Average word length in syllables
Avg_Sentence_Length | Average sentence length
Num_Prepositional_Phrases | Number of prepositional phrases
Num_Negated_Words_Stem | Number of negated words stemmed
Num_Negated_Words_Lead_In | Number of negated words leading in
Num_Main_Noun_Phrases | Number of main noun phrases
Avg_Main_NP_Length | Average length of main noun phrases
Num_Verb_Phrases | Number of verb phrases
Prop_Active_Voice_Verbs | Proportion of active voice verbs
Prop_Passive_Voice_Verbs | Proportion of passive voice verbs
Ratio_Active_to_Passive_Verbs | Ratio of active to passive voice verbs
Num_Words_Before_Main_Verb | Number of words before the main verb
Num_Agentless_Passive_Constructions | Number of agentless passive constructions
Word_Length_Std_Dev | Standard deviation of word lengths
Num_Polysemic_Words | Number of polysemic words
Num_Word_Senses | Number of word senses
Num_Word_Senses_For_Content_Words | Number of word senses for content words
Num_Word_Senses_For_Nouns | Number of word senses for nouns
Num_Word_Senses_For_Verbs | Number of word senses for verbs
Num_Word_Senses_For_Non_Auxiliary_Verbs | Number of word senses for non-auxiliary verbs
Num_Word_Senses_For_Adjectives | Number of word senses for adjectives
Num_Word_Senses_For_Adverbs | Number of word senses for adverbs
Distance_To_Root_Nouns | Distance to root for nouns
Distance_To_Root_Verbs | Distance to root for verbs
flesch_kincaid_grade | Flesch-Kincaid grade level
flesch_kincaid_ease | Flesch-Kincaid ease score
coleman_liau_index | Coleman-Liau index
automated_readability_index | Automated Readability Index
smog_index | SMOG index
gunning_fog | Gunning Fog index
traenkle_bailer_index | Traenkle-Bailer index

###  C.2 Prompt-based Metrics

Is this text readable for an elementary school student?, Is this text suitable
for an elementary school student?, Is this text easy to understand for
elementary school students?, Is this text relevant to curriculum topics for
elementary school students?, Is this text relevant to the knowledge and
experiences of elementary school students?, Could an average elementary school
student engage with the content of this task?, Could most elementary school
students complete this task without significant difficulty?, Is this text
appropriate for the skills and knowledges of elementary school students?, Is
the length of this text suitable for elementary school students?, Would the
vocabulary in this text be comprehensible to elementary school students?, Is
this text readable for a middle school student?, Is this text suitable for a
middle school student?, Is this text easy to understand for middle school
students?, Is this text relevant to curriculum topics for middle school
students?, Is this text relevant to the knowledge and experiences of middle
school students?, Could an average middle school student engage with the
content of this task?, Could most middle school students complete this task
without significant difficulty?, Is this text appropriate for the skills and
knowledges of middle school students?, Is the length of this text suitable for
middle school students?, Would the vocabulary in this text be comprehensible
to middle school students?, Is this text readable for a high school student?,
Is this text suitable for a high school student?, Is this text easy to
understand for high school students?, Is this text relevant to curriculum
topics for high school students?, Is this text relevant to the knowledge and
experiences of high school students?, Could an average high school school
student engage with the content of this task?, Could most high school students
complete this task without significant difficulty?, Is this text appropriate
for the skills and knowledges of high school students?, Is the length of this
text suitable for high school students?, Would the vocabulary in this text be
comprehensible to high school students?, Does this text contain metaphors
and/or figurative language?, Does this text use complex language?, Does this
text use simple language?, Does this text contain technical jargon?, Is this
text about science?, Is this text about language science?, Is this text about
natural science?, Is this text about social science?, Is this text about
math?, Is this text about physics?, Is this text about chemistry?, Is this
text about earth science?, Is this text about world history?, Is this text
about geography?, Based on the Flesch-Kincaid reading-ease score, is this text
suitable for elementary school readers?, Based on the Flesch-Kincaid reading-
ease score, is this text suitable for middle school readers?, Based on the
Flesch-Kincaid reading-ease score, is this text suitable for high school
readers?, Based on the Gunning Fog Index, is this text suitable for elementary
school readers?, Based on the Gunning Fog Index, is this text suitable for
middle school readers?, Based on the Gunning Fog Index, is this text suitable
for high school readers?, Based on the Coleman-Liau Index, is this text
suitable for elementary school readers?, Based on the Coleman-Liau Index, is
this text suitable for middle school readers?, Based on the Coleman-Liau
Index, is this text suitable for high school readers?, Based on the Automated
Readability Index (ARI), is this text suitable for elementary school readers?,
Based on the Automated Readability Index (ARI), is this text suitable for
middle school readers?, Based on the Automated Readability Index (ARI), is
this text suitable for high school readers?, Based on the SMOG Index, is this
text suitable for elementary school readers?, Based on the SMOG Index, is this
text suitable for middle school readers?, Based on the SMOG Index, is this
text suitable for high school readers?, Does this text contain basic concepts
that are easy to comprehend?, Does this text cover multiple concepts?, Does
this text provide a very explicit explanation?, Does this text contain simple
examples?

##  Appendix D Details over Gemma-7B, Mistral-7B, and Llama2-7B

We describe the performance of these models in detail. Gemma7b has 10.33%
invalid response in zero-shot and 9.56% over few-shot. The majority of the
predicted class is high school level 73.41% in zero-shot and 72.75% in few-
shot. Mistral7b has 15.49% invalid response in zero-shot and 6.37% invalid in
few-shot and with majority of classification for high school level with 66.04%
in zero-shot and 42.31% for elemetary school in few-shot. Llama2-7b has 13.08%
invalid in zero-shot and 5.49% in few-shot and the majority of elementary
school classification with 66.26% in zero-shot and also 76.04% in few-shot.
Gpt-4 has only 5.93% invalid in zero-shot and 0.77% in few-shot. Gpt-4
predicted also the high school level as the highest classification with 41.54%
in zero-shot and 40.22% in few-shot.

| Level | Precision | Recall | F1-Score
---|---|---|---|---
Prompt | Elem. | $0.83$ | $0.81$ | $0.82$
Middle | $0.75$ | $0.57$ | $0.65$
High | $0.66$ | $0.81$ | $0.65$
Static | Elem. | $0.86$ | $0.85$ | $0.86$
Middle | $0.75$ | $0.71$ | $0.73$
High | $0.84$ | $0.88$ | $0.86$
Combo | Elem. |  0.98* |  0.98* |  0.98*
Middle |  0.98* |  0.91* |  0.95*
High |  0.91* |  0.97* |  0.94*
Table 5: Difficulty classification performance on test. $*=$ statistically significant improvements of Combo over Static at $p=0.05$ (bootstrap). Prompt-based metrics use Gemma-7b. Best performance per level in bold.  | Level | Precision | Recall | F1-Score
---|---|---|---|---
Prompt | Elem. | $0.46$ | $0.86$ | $0.60$
Middle | 0.92 | $0.83$ | 0.88
High | $0.34$ | $0.10$ | $0.16$
Static | Elem. | 0.86 | $0.85$ | $0.86$
Middle | $0.75$ | $0.71$ | $0.73$
High | $0.84$ | 0.88 | 0.86
Combo | Elem. | $0.76$ |  0.95* |  0.84*
Middle | $0.85$ |  0.90* |  0.88*
High |  0.89 * | $0.64$ | $0.75$
Table 6: Difficulty classification performance on test. $*=$ statistically significant improvements of Combo over Static at $p=0.05$ (bootstrap). Prompt-based metrics use Mistral-7b. Best performance per level in bold.  | Level | Precision | Recall | F1-Score
---|---|---|---|---
Prompt | Elem. | $0.44$ | $0.47$ | $0.45$
Middle | $0.62$ | $0.61$ | $0.62$
High | $0.29$ | $0.28$ | $0.28$
Static | Elem. | $0.86$ | $0.85$ | $0.86$
Middle | 0.75 | $0.71$ | 0.73
High | 0.84 | 0.88 | 0.86
Combo | Elem. |  0.88* |  0.97* |  0.93*
Middle | $0.72$ |  0.74* |  0.73*
High | $0.83$ | $0.73$ | $0.78$
Table 7: Difficulty classification performance on test. $*=$ statistically significant improvements of Combo over Static at $p=0.05$ (bootstrap). Prompt-based metrics use Llama2-7b. Best performance per level in bold.  | Rank | Metric | F
---|---|---|---
Prompt | 1 | Based on the Coleman-Liau Index, is the text suitable for MS readers? | 105.09*
2 | Is this text readable for a MS student? | 104.42*
3 | Based on the SMOG Index, is this text suitable for MS readers? | 103.53*
4 | Is this text suitable for a MS student? | 94.21*
5 | Based on the Gunning Fog Index, is this text suitable for MS readers? | 92.35*
Static Metrics | 1 | Gunning Fog (measures text readability) | 817.86*
2 | Coleman-Liau index (measures text readability) | 785.60*
3 | Flesch-Kincaid Reading Ease (measures readability) | 725.15*
4 | Automated Readability Index (measures lexical diversity) | 686.87*
5 | Number of unique Words (measures lexical diversity) | 613.89*
Table 8:  Top five most important features among the Prompt-based and Static metrics. Feature importance is measured using univariate F-tests. Larger F indicates higher feature importance. (MS: Middle School) Prompt-based metrics use the Gemma-7B model. * indicates significance at >99.999% confidence.  | Rank | Metric | F
---|---|---|---
Prompt | 1 | Based on the Gunning Fog Index, is this text suitable for ES readers? | 209.84*
2 | Is this text easy to understand for ES students?? | 193.22*
3 | Is this text Suitable for ES students | 190.61*
4 | Is this text about math? | 175.72*
5 | Is this text relevant to curriculum topics for ES students? | 175.08*
Static Metrics | 1 | Gunning Fog (measures text readability) | 817.86*
2 | Coleman-Liau index (measures text readability) | 785.60*
3 | Flesch-Kincaid Reading Ease (measures readability) | 725.15*
4 | Automated Readability Index (measures Readability) | 686.87*
5 | Number of unique Words (measures lexical diversity) | 613.89*
Table 9:  Top five most important features among the Prompt-based and Static metrics. Feature importance is measured using univariate F-tests. Larger F indicates higher feature importance. (ES: Elementary School) Prompt-based metrics use the Mistral-7B model. * indicates significance at >99.999% confidence.  | Rank | Metric | F
---|---|---|---
Prompt-based Metrics | 1 | Is this text relevant to curriculum topics for ES students? | 139.66*
2 | Is this text suitable for an ES student? | 136.97*
3 | Is this text readable for an ES student | 132.89*
4 | Based on the Gunning Fog Index, is this text suitable for MS readers?" | 125.51*
5 | Is this text about natural science? | 124.52*
Static Metrics | 1 | Gunning Fog (measures text readability) | 817.86*
2 | Coleman-Liau index (measures text readability) | 785.60*
3 | Flesch-Kincaid Reading Ease (measures readability) | 725.15*
4 | Automated Readability Index (measures Readability) | 686.87*
5 | Number of unique Words (measures lexical diversity) | 613.89*
Table 10:  Top five most important features among the Prompt-based and Static
metrics. Feature importance is measured using univariate F-tests. Larger F
indicates higher feature importance.(ES: Elementary School, MS: Middle School)
Prompt-based metrics use the Llamma2-7B model. * indicates significance at
>99.999% confidence.


# A Refined Approximation for
Euclidean k-Means

Fabrizio Grandoni111IDSIA, USI-SUPSI Rafail Ostrovsky222UCLA Yuval
Rabani333The Hebrew University of Jerusalem Leonard J. Schulman444Caltech
Rakesh Venkat555IIT Hyderabad

###### Abstract

In the Euclidean $k$-Means problem we are given a collection of $n$ points
${\cal D}$ in an Euclidean space and a positive integer $k$. Our goal is to
identify a collection of $k$ points in the same space (centers) so as to
minimize the sum of the squared Euclidean distances between each point in
${\cal D}$ and the closest center. This problem is known to be APX-hard and
the current best approximation ratio is a primal-dual $6.357$ approximation
based on a standard LP for the problem [Ahmadian et al. FOCS’17, SICOMP’20].

In this note we show how a minor modification of Ahmadian et al.’s analysis
leads to a slightly improved $6.12903$ approximation. As a related result, we
also show that the mentioned LP has integrality gap at least
$\frac{16+\sqrt{5}}{15}>1.2157$.

##  1 Introduction

Clustering is a central problem in Computer Science, with many applications in
data science, machine learning etc. One of the most famous and best-studied
problems in this area is Euclidean $k$-Means: given a set ${\cal D}$ of $n$
points (or _demands_) in $\mathbb{R}^{\ell}$ and an integer $k\in[1,n]$,
select $k$ points $S$ (_centers_) so as to minimize $\sum_{j\in{\cal
D}}d^{2}(j,S)$. Here $d(j,i)$ is the Euclidean distance between points $j$ and
$i$ and for a set of points $I$, $d(j,I)=\min_{i\in I}d(j,i)$. In other words,
we wish to select $k$ centers so as to minimize the sum of the squared
Euclidean distances between each demand and the closest center. Equivalently,
a feasible solution is given by a partition of the demands into $k$ subsets
(_clusters_). The cost $w_{C}$ of a cluster $C\subset{\cal D}$ is $\sum_{j\in
C}d^{2}(c,\mu)$, where $\mu$ is the center of mass of $C$. We recall that
$w_{C}$ can also be expressed as $\frac{1}{2|C|}\sum_{j\in
C}\sum_{j^{\prime}\in C}d^{2}(j,j^{\prime})$. Our goal is to minimize the
total cost of these clusters.

Euclidean $k$-Means is well-studied in terms of approximation algorithms. It
is known to be APX-hard. More precisely, it is hard to approximate $k$-Means
below a factor $1.0013$ in polynomial time unless $P=NP$ [6, 16]. The hardness
was improved to $1.07$ under the Unique Games Conjecture [9]. Some heuristics
are known to perform very well in practice, however their approximation factor
is $O(\log k)$ or worse on general instances [3, 4, 17, 21]. Constant
approximation algorithms are known. A local-search algorithm by Kanugo et al.
[15] provides a $9+\varepsilon$ approximation666Throughout this paper by
$\varepsilon$ we mean an arbitrarily small positive constant. W.l.o.g. we
assume $\varepsilon\leq 1$.. The authors also show that natural local-search
based algorithms cannot perform better than this. This ratio was improved to
$6.357$ by Ahmadian et al. [1, 2] using a primal-dual approach. They also
prove a $9+\varepsilon$ approximation for general (possibly non-Euclidean)
metrics. Better approximation factors are known under reasonable restrictions
on the input [5, 7, 10, 20]. A PTAS is known for constant $k$ [19] or for
constant dimension $\ell$ [10, 12]. Notice that $\ell$ can be always assumed
to be $O(\log n)$ by a standard application of the Johnson-Lindenstrauss
transform [14]. This was recently improved to $O(\log k+\log\log n)$ [8] and
finally to $O(\log k)$ [18].

In this paper we describe a simple modification of the analysis of Ahmadian et
al. [2] which leads to a slightly improved approximation for Euclidean
$k$-Means (see Section 2).

######  Theorem 1.

There exists a deterministic polynomial-time algorithm for Euclidean $k$-Means
with approximation ratio $\rho+\varepsilon$ for any positive constant
$\varepsilon>0$, where

$\rho:=\left(1+\sqrt{\frac{1}{2}(2+\sqrt[3]{3-2\sqrt{2}}+\sqrt[3]{3+2\sqrt{2}})}\right)^{2}<6.12903.$

The above approximation ratio is w.r.t. the optimal fractional solution to a
standard LP relaxation $LP_{\text{k-Means}}$ for the problem (defined later).
As a side result (see Section 3), we prove a lower bound on the integrality
gap of this relaxation (we are not aware of any explicit such lower bound in
the literature).

######  Theorem 2.

The integrality gap of $LP_{\text{k-Means}}$, even in the Euclidean plane
(i.e., for $\ell=2$), is at least $\frac{16+\sqrt{5}}{15}>1.2157$.

###  1.1 Preliminaries

As mentioned earlier, one can formulate Euclidean $k$-Means in term of the
selection of $k$ centers. In this case, it is convenient to discretize the
possible choices for the centers, hence obtaining a polynomial-size set ${\cal
F}$ of candidate centers, at the cost of an extra factor $1+\varepsilon$ in
the approximation ratio (we will neglect this factor in the approximation
ratios since it is absorbed by analogous factors in the rest of the analysis).
In particular we will use the construction in [11] (Lemma 24) that chooses as
${\cal F}$ the centers of mass of any collection of up to $16/\varepsilon^{2}$
points with repetitions. In particular $|{\cal F}|=O(n^{16/\varepsilon^{2}})$
in this case.

Let $c(j,i)$ be an abbreviation for $d^{2}(j,i)$. Then a standard LP-
relaxation for $k$-Means is as follows:

$\displaystyle\min$ $\displaystyle\sum_{i\in{\cal F},j\in{\cal D}}x_{ij}\cdot
c(j,i)$ $\displaystyle LP_{\text{k-Means}}$ $\displaystyle s.t.$
$\displaystyle\sum_{i\in{\cal F}}x_{ij}\geq 1$ $\displaystyle\forall j\in{\cal
D}$ $\displaystyle x_{ij}\leq y_{i}$ $\displaystyle\forall j\in{\cal
D},\forall i\in{\cal F}$ $\displaystyle\sum_{i\in{\cal F}}y_{i}\leq k$
$\displaystyle\forall j\in{\cal D},\forall i\in{\cal F}$ $\displaystyle
x_{ij},y_{i}\geq 0$ $\displaystyle\forall j\in{\cal D},\forall i\in{\cal F}$

In an integral solution, we interpret $y_{i}=1$ as $i$ being a selected center
in $S$ ($i$ is _open_), and $x_{ij}=1$ as demand $j$ being _assigned_ to
center $i$777Technically each demand is automatically assigned to the closest
open center. However it is convenient to allow also sub-optimal assignments in
the LP relaxation.. The first family of constraints states that each demand
has to be assigned to some center, the second one that a demand can only be
assigned to an open center, and the third one that we can open at most $k$
centers.

For any parameter $\lambda>0$ (_Lagrangian multiplier_), the _Lagrangian
relaxation_ $LP(\lambda)$ of $LP_{\text{k-Means}}$ (w.r.t. the last matrix
constraint) and its dual $DP(\lambda)$ are as follows:

$\displaystyle\min$ $\displaystyle\sum_{i\in{\cal F},j\in{\cal D}}x_{ij}\cdot
c(j,i)+\lambda\cdot\sum_{i\in{\cal F}}y_{i}-\lambda\,k$ $\displaystyle
LP(\lambda)$ $\displaystyle s.t.$ $\displaystyle\sum_{i\in{\cal F}}x_{ij}\geq
1$ $\displaystyle\forall j\in{\cal D}$ $\displaystyle x_{ij}\leq y_{i}$
$\displaystyle\forall j\in{\cal D},\forall i\in{\cal F}$ $\displaystyle
x_{ij},y_{i}\geq 0$ $\displaystyle\forall j\in{\cal D},\forall i\in{\cal F}$
$\displaystyle\max$ $\displaystyle\sum_{j\in{\cal D}}\alpha_{j}-\lambda k$
$\displaystyle DP(\lambda)$ $\displaystyle s.t.$ $\displaystyle\sum_{j\in{\cal
D}}\max\\{0,\alpha_{j}-c(j,i)\\}\leq\lambda$ $\displaystyle\forall i\in{\cal
F}$ (1) $\displaystyle\alpha_{j}\geq 0$ $\displaystyle\forall j\in{\cal D}$

Above $\max\\{0,\alpha_{j}-c(j,i)\\}$ replaces the dual variable $\beta_{ij}$
corresponding to the second constraint in the primal in the standard
formulation of the dual LP. Notice that, by removing the fixed term $-\lambda
k$ in the objective functions of $LP(\lambda)$ and $DP(\lambda)$, one obtains
the standard LP relaxation $LP_{FL}(\lambda)$ for the Facility Location
problem (FL) with uniform facility cost $\lambda$ and its dual
$DP_{FL}(\lambda)$.

We say that a $\rho$-approximation algorithm for a FL instance of the above
type is _Lagrangian Multiplier Preserving_ (LMP) if it returns a set of
facilities $S$ that satisfies:

$\sum_{j\in{\cal D}}c(j,S)\leq\rho(OPT(\lambda)-\lambda|S|),$

where $OPT(\lambda)$ is the value of the optimal solution to
$LP_{FL}(\lambda)$.

##  2 A Refined Approximation for Euclidean $k$-Means

In this section we present our refined approximation for Euclidean $k$-Means.
We start by presenting the LMP approximation algorithm for the FL instances
arising from $k$-Means described in [2] in Section 2.1. We then present the
analysis of that algorithm as in [2] in Section 2.2. In Section 2.3 we
describe our refined analysis of the same algorithm. Finally, in Section 2.4
we sketch how to use this to approximate $k$-Means.

###  2.1 A Primal-Dual LMP Algorithm for Euclidean Facility Location

We consider an instance of Euclidean FL induced by a $k$-Means instance in the
mentioned way, for a given Lagrangian multiplier $\lambda>0$.

We consider exactly the same Lagrangian Multiplier Preserving (LMP) primal-
dual algorithm $JV(\delta)$ as in [2]. In more detail, let $\delta\geq 2$ be a
parameter to be fixed later. The algorithm consists of a dual-growth phase and
a pruning phase. The dual-growth phase is exactly as in the classical primal-
dual algorithm JV by Jain and Vazirani [13]. We start with all the dual
variables set to $0$ and an empty set ${\cal O}_{t}$ of tentatively open
facilities. The clients such that $\alpha_{j}\geq c(j,i)$ for some $i\in
F^{\prime}$ are frozen, and the other clients are active. We grow the dual
variables of active clients at uniform rate until one of the following two
events happens. The first event is that some constraint of type (1) becomes
tight. At that point the corresponding facility $i$ is added to ${\cal O}_{t}$
and all clients $j$ with $\alpha_{j}\geq c(j,i)$ are set to frozen. The second
event is that $\alpha_{j}=c(j,i)$ for some some $i\in{\cal O}_{t}$. In that
case $j$ is set to frozen. In any case, the facility $w(j)$ that causes $j$ to
become frozen is called the witness of $j$. The phase halts when all clients
are frozen.

In the pruning phase we will close some facilities in ${\cal O}_{t}$, hence
obtaining the final set of open facilities $IS$. Here $JV(\delta)$ deviates
from $JV$. For each client $j\in{\cal D}$, let $N(j)=\\{i\in{\cal
F}:\alpha_{j}>c(j,i)\\}$ be the set of facilities $i$ such that $j$
contributed with a positive amount to the opening of $i$. Symmetrically, for
$i\in{\cal F}$, let $N(i)=\\{j\in{\cal D}:\alpha_{j}>c(j,i)\\}$ be the clients
that contributed with a positive amount to the opening of $i$. For $i\in{\cal
O}_{t}$, we let $t_{i}=\max_{j\in N(i)}\alpha_{j}$, where the values
$\alpha_{j}$ are considered at the end of the dual-growth phase. We set
conventionally $t_{i}=0$ for $N(i)=\emptyset$. Intuitively, $t_{i}$ is the
“time” when facility $i$ is tentatively open (at which point all the dual
variables of contributing clients stop growing). We define a conflict graph
$H$ over tentatively open facilities as follows. The node set of $H$ is ${\cal
O}_{t}$. We place an edge between $i,i^{\prime}\in{\cal O}_{t}$ iff the
following two conditions hold: (1) for some client $j$, $j\in N(i)\cap
N(i^{\prime})$ (in words, $j$ contributes to the opening of both $i$ and
$i^{\prime}$) and (2) one has
$c(i,i^{\prime})\leq\delta\cdot\min\\{t_{i},t_{i^{\prime}}\\}$. In this graph
we compute a maximal independent set $IS$, which provides the desired solution
to the facility location problem (where each client is assigned to the closest
facility in $IS$).

We remark that the pruning phase of $JV$ differs from the one of $JV(\delta)$
only in the definition of $H$, where condition (2) is not required to hold
(or, equivalently, $JV$ behaves like $JV(+\infty)$ for $\lambda>0$).

###  2.2 The Analysis in [2]

The general goal is to show that

$\sum_{j\in{\cal D}}c(j,IS)\leq\rho(\sum_{j\in{\cal
D}}\alpha_{j}-\lambda|IS|),$

for some $\rho\geq 1$ as small as possible. This shows that the algorithm is
an LMP $\rho$-approximation for the problem. It is sufficient to prove that,
for each client $j$, one has

$\frac{c(j,IS)}{\rho}\leq\alpha_{j}-\sum_{i\in N(j)\cap
IS}(\alpha_{j}-c(j,i))=\alpha_{j}-\sum_{i\in
IS}\max\\{0,\alpha_{j}-c(j,i)\\}.$

Let $S=N(j)\cap IS$ and $s=|S|$. We distinguish $3$ cases depending on the
value of $s$:

#### Case A: $s=1$.

Let $S=\\{i^{*}\\}$. Then for any $\rho\geq 1$,

$\frac{c(j,IS)}{\rho}\leq
c(j,IS)=c(j,i^{*})=\alpha_{j}-(\alpha_{j}-c(j,i^{*})).$

#### Case B: $s>1$.

Here we use the properties of Euclidean metrics. The sum $\sum_{i\in S}c(j,i)$
is the sum of the squared distances from $j$ to the facilities in $S$. This
quantity is lower bounded by the sum of the squared distances from $S$ to the
centroid $\mu$ of $S$. Recall that $\sum_{i\in
S}c(\mu,i)=\frac{1}{2s}\sum_{i\in S}\sum_{i^{\prime}\in S}c(i,i^{\prime})$. We
also observe that, by construction, for any two distinct $i,i^{\prime}\in IS$
one has

$c(i,i^{\prime})>\delta\cdot\min\\{t_{i},t_{i^{\prime}}\\}\geq\delta\cdot\alpha_{j},$

where the last inequality follows from the fact that $j$ is contributing to
the opening of both $i$ and $i^{\prime}$. Altogether one obtains

$\sum_{i\in S}c(j,i)\geq\sum_{i\in S}c(\mu,i)=\frac{1}{2s}\sum_{i\in
S}\sum_{i^{\prime}\in S}c(i,i^{\prime})\geq\frac{(s-1)\delta\alpha_{j}}{2}.$

Thus

$\sum_{i\in
S}(\alpha_{j}-c(j,i))\leq(s-\frac{\delta(s-1)}{2})\alpha_{j}=(s(1-\frac{\delta}{2})+\frac{\delta}{2})\alpha_{j}\overset{\delta\geq
2,s\geq 2}{\leq}(2-\frac{\delta}{2})\alpha_{j}.$

Using the fact that $\alpha_{j}>c(j,i)$ for all $i\in S$, hence
$\alpha_{j}>c(j,IS)$, one gets

$(\frac{\delta}{2}-1)c(j,IS)\overset{\delta\geq
2}{\leq}(\frac{\delta}{2}-1)\alpha_{j}.$

We conclude that

$\sum_{i\in
S}(\alpha_{j}-c(j,i))+(\frac{\delta}{2}-1)c(j,IS)\leq(2-\frac{\delta}{2})\alpha_{j}+(\frac{\delta}{2}-1)\alpha_{j}=\alpha_{j}.$

This gives the desired inequality assuming that
$\rho\geq\frac{1}{\delta/2-1}$.

#### Case C: $s=0$.

Consider the witness $i=w(j)$ of $j$. Notice that $\alpha_{j}\geq t_{i}$ and
$\alpha_{j}\geq c(j,i)=d^{2}(j,i)$. Hence

$d(j,i)+\sqrt{\delta t_{i}}\leq(1+\sqrt{\delta})\sqrt{\alpha_{j}}.$

If $i\in IS$, then $d(j,IS)\geq d(j,i)$. Otherwise there exists $i^{\prime}\in
IS$ such that
$d^{2}(i,i^{\prime})\leq\delta\min\\{t_{i},t_{i^{\prime}}\\}\leq\delta t_{i}$.
Thus $d(j,IS)\leq d(j,i)+d(i,i^{\prime})\leq d(j,i)+\sqrt{\delta t_{i}}.$ In
both cases one has $d(j,IS)\leq(1+\sqrt{\delta})\sqrt{\alpha_{j}},$ hence

$c(j,IS)\leq(1+\sqrt{\delta})^{2}\alpha_{j}.$

This gives the desired inequality for $\rho\geq(1+\sqrt{\delta})^{2}$.

#### Fixing $\delta$.

Altogether we can set
$\rho=\max\\{\frac{1}{\delta/2-1},(1+\sqrt{\delta})^{2}\\}$. The best choice
for $\delta$ (namely, the one that minimizes $\rho$) is the solution of
$\frac{1}{\delta/2-1}=(1+\sqrt{\delta})^{2}$. This is achieved for
$\delta\simeq 2.3146$ and gives $\rho\simeq 6.3574$.

###  2.3 A Refined Analysis

We refine the analysis in Case B as follows. Let $\Delta=\sum_{i\in S}c(j,i)$.
We already proved that, for $\delta\geq 2$, $\alpha_{j}-\sum_{i\in
S}(\alpha_{j}-c(j,i))\geq 0$. Hence it is sufficient to upper bound

$\frac{c(j,S)}{\alpha_{j}-\sum_{i\in
S}(\alpha_{j}-c(j,i))}=\frac{c(j,S)}{\sum_{i\in
S}c(j,i)-(s-1)\alpha_{j}}=\frac{c(j,S)}{\Delta-(s-1)\alpha_{j}}.$

Instead of using the upper bound $c(j,S)\leq\alpha_{j}$ we use the average

$c(j,S)\leq\frac{1}{s}\sum_{i\in S}c(j,i)=\frac{\Delta}{s}.$

Then it is sufficient to upper bound

$\frac{1}{s}\frac{\Delta}{\Delta-(s-1)\alpha_{j}}.$

The derivative in $\Delta$ of the above function is
$\frac{1}{s}\frac{-(s-1)\alpha_{j}}{(\Delta-(s-1)\alpha_{j})^{2}}<0$. Hence
the maximum is achieved for the smallest possible value of $\Delta$. Recall
that we already showed that $\Delta\geq\frac{(s-1)\delta\alpha_{j}}{2}$. Hence
a valid upper bound is

$\frac{1}{s}\frac{\frac{(s-1)\delta\alpha_{j}}{2}}{\frac{(s-1)\delta\alpha_{j}}{2}-(s-1)\alpha_{j}}=\frac{1}{s}\frac{\delta/2}{\delta/2-1}\overset{s\geq
2}{\leq}\frac{\delta/4}{\delta/2-1}.$

This imposes $\rho\geq\frac{\delta/4}{\delta/2-1}$ rather than
$\rho\geq\frac{1}{\delta/2-1}$ in Case B. Notice that this is an improvement
for $\delta<4$. The best choice of $\delta$ is now obtained by imposing
$\frac{\delta/4}{\delta/2-1}=(1+\sqrt{\delta})^{2}$. This gives
$\delta=\frac{1}{2}(2+\sqrt[3]{3-2\sqrt{2}}+\sqrt[3]{3+2\sqrt{2}})\simeq
2.1777$ and
$\rho=\left(1+\sqrt{\frac{1}{2}(2+\sqrt[3]{3-2\sqrt{2}}+\sqrt[3]{3+2\sqrt{2}})}\right)^{2}<6.12903$.

###  2.4 From Facility Location to k-Means

We can use the refined
$\rho:=\left(1+\sqrt{\frac{1}{2}(2+\sqrt[3]{3-2\sqrt{2}}+\sqrt[3]{3+2\sqrt{2}})}\right)^{2}$
approximation for Euclidean Facility Location from previous section to derive
a $\rho+\varepsilon$ approximation for Euclidean k-Means, for any constant
$\varepsilon>0$. Here we follow the approach of [2] with only minor changes.
In more detail, the authors consider a variant of the FL algorithm described
before, whose approximation factor is $\rho+\varepsilon$ rather than $\rho$. A
careful use of this algorithm leads to a solution opening precisely $k$
facilities, which leads to the desired approximation factor. In their analysis
the authors use slight modifications of the inequality
$(1+\sqrt{\delta})\sqrt{\alpha_{j}}\geq d(j,i)+\sqrt{\delta t_{i}}$ (coming
from Case C, which is the same in their and our analysis). The goal is to
prove that the modified algorithm is $\rho+\varepsilon$ approximate. Here
$\delta$ and $\rho$ are used as parameters. Therefore it is sufficient to
replace their values of these parameters with the ones coming from our refined
analysis. The rest is identical.

##  3 Lower Bound on the Integrality Gap

In this section we describe our lower bound instance for the integrality gap
of $LP_{\text{k-Means}}$. It is convenient to consider first the following
slightly different relaxation, based on clusters (with $w_{C}$ as defined in
Section 1):

$\displaystyle\min$ $\displaystyle\sum_{C\in{\cal C}}w_{C}x_{C}$
$\displaystyle LP^{\prime}_{\text{k-Means}}$ $\displaystyle s.t.$
$\displaystyle\sum_{C\in{\cal C}:j\in C}x_{C}\geq 1$ $\displaystyle\forall
j\in{\cal D}$ $\displaystyle\sum_{C\in{\cal C}}x_{C}\leq k$ $\displaystyle
x_{C}\geq 0$ $\displaystyle\forall C\in{\cal C}$

Here ${\cal C}$ denotes the set of possible clusters, i.e. the possible
subsets of points. In an integral solution $x_{C}=1$ means that cluster $C$ is
part of our solution.

Our instance is on the Euclidean plane, and its points are the (10) vertices
of two regular pentagons of side length $1$. These pentagons are placed so
that any two vertices of distinct pentagons are at large enough distance $M$
to be fixed later. Here $k=5$. We remark that our argument can be easily
extended to an arbitrary number of points by taking $2h$ such pentagons for
any integer $h\geq 1$ so that the pairwise distance between vertices of
distinct pentagons is at least $M$, and setting $k=5h$.

A feasible fractional solution is obtained by setting $x_{C}=0.5$ for every
$C$ consisting of a pair of consecutive vertices in the same pentagon (so we
are considering $10$ fractional clusters in total). Obviously this solution is
feasible. The cost $w_{C}$ of each such cluster $C$ is $2(0.5)^{2}=0.5$. Hence
the cost of this fractional solution is $10\cdot 0.5\cdot 0.5=\frac{5}{2}$.

Next consider the optimal integral solution, consisting of $5$ clusters.
Recall that the radius of each pentagon (i.e. the distance from a vertex to
its center) is $r=\sqrt{\frac{2}{5-\sqrt{5}}}\simeq 0.851$ and the distance
between two non-consecutive vertices in the same pentagon is
$d=\frac{\sqrt{5}+1}{2}\simeq 1.618$. A solution with two clusters consisting
of the vertices of each pentagon costs $10r^{2}$. Any cluster involving
vertices of distinct pentagons costs at least $M^{2}/2$, hence for $M$ large
enough the optimal solution forms clusters only with vertices of the same
pentagon. In more detail the optimal solution consists of $x\in\\{1,2,3,4\\}$
clusters containing the vertices of one pentagon and $5-x$ clusters containing
the vertices of the remaining pentagon. Let $w(x)$ be the minimum cost
associated with one pentagon assuming that we form $x$ clusters with its
vertices. Clearly $w(1)=5r^{2}=\frac{10}{5-\sqrt{5}}$. Regarding $w(4)$, it is
obviously convenient to choose two consecutive vertices in the unique cluster
of size $2$. Thus $w(4)=1/2$. For $x\in\\{2,3\\}$, we note, as is easy to
verify, that clusters with consecutive vertices are less expensive than the
alternatives. For $w(2)$, one might form one cluster of size $1$ and one of
size $4$. This would cost $\frac{3(1+d^{2})}{4}=\frac{15+3\sqrt{5}}{8}$.
Alternatively, one might form one cluster of size $2$ and one of size $3$, at
smaller cost $\frac{1}{2}+\frac{2+d^{2}}{3}=\frac{10+\sqrt{5}}{6}$. Thus
$w(2)=\frac{10+\sqrt{5}}{6}$. For $x=3$, one might form two clusters of size
$1$ and one of size $3$, or two clusters of size $2$ and one of size $1$. The
associated cost in the two cases is $\frac{2+d^{2}}{3}>1$ and
$2\cdot\frac{1}{2}=1$, resp. Hence $w(3)=1$. So the overall cost of the
optimal integral solution is
$\min\\{w(1)+w(4),w(2)+w(3)\\}=w(2)+w(3)=\frac{16+\sqrt{5}}{6}$. Thus the
integrality gap of $LP^{\prime}_{\text{k-Means}}$ is at least
$\frac{16+\sqrt{5}}{6}\cdot\frac{2}{5}=\frac{16+\sqrt{5}}{15}$.

Consider next $LP_{\text{k-Means}}$. Here a technical complication comes from
the definition of ${\cal F}$ which is not part of the input instance of
$k$-Means. The same construction as above works if we let ${\cal F}$ contain
the centers of mass of any set of $2$ or $3$ points. Notice that this is
automatically guaranteed by the construction in [11] for
$16/\varepsilon^{2}\geq 3$. In this case the optimal integral solutions to
$LP_{\text{k-Means}}$ and $LP^{\prime}_{\text{k-Means}}$ are the same in the
considered example. Furthermore one obtains a feasible fractional solution to
$LP_{\text{k-Means}}$ of cost $5/2$ by setting $y_{i}=0.5$ for the centers of
mass of any two consecutive vertices of the same pentagon, and setting
$x_{ij}=0.5$ for each point $i$ and the two closest centers $j$ with positive
$y_{j}$. This concludes the proof of Theorem 2.

## Acknowledgments

Work supported in part by the NSF grant 1909972 and the SNF Excellence Grant
200020B_182865/1.

## References

  * [1] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.  Better guarantees for k-means and Euclidean k-median by primal-dual algorithms.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 61–72. IEEE Computer Society, 2017.
  * [2] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.  Better guarantees for k-means and Euclidean k-median by primal-dual algorithms.  SIAM J. Comput., 49(4), 2020.
  * [3] David Arthur and Sergei Vassilvitskii.  How slow is the _k_ -means method?  In Nina Amenta and Otfried Cheong, editors, Proceedings of the 22nd ACM Symposium on Computational Geometry, Sedona, Arizona, USA, June 5-7, 2006, pages 144–153. ACM, 2006.
  * [4] David Arthur and Sergei Vassilvitskii.  k-means++: the advantages of careful seeding.  In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027–1035. SIAM, 2007.
  * [5] Pranjal Awasthi, Avrim Blum, and Or Sheffet.  Stability yields a PTAS for k-median and k-means clustering.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 309–318. IEEE Computer Society, 2010.
  * [6] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop.  The hardness of approximation of Euclidean k-means.  In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 754–767. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2015.
  * [7] Maria-Florina Balcan, Avrim Blum, and Anupam Gupta.  Approximate clustering without the approximation.  In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 1068–1077. SIAM, 2009.
  * [8] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn.  Oblivious dimension reduction for _k_ -means: beyond subspaces and the Johnson-Lindenstrauss lemma.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1039–1050. ACM, 2019.
  * [9] Vincent Cohen-Addad and Karthik C. S.  Inapproximability of clustering in $l_{p}$ metrics.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 519–539. IEEE Computer Society, 2019.
  * [10] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu.  Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics.  SIAM J. Comput., 48(2):644–667, 2019.
  * [11] Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani.  Approximation schemes for clustering problems.  In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 50–58. ACM, 2003.
  * [12] Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour.  Local search yields a PTAS for k-means in doubling metrics.  SIAM J. Comput., 48(2):452–480, 2019.
  * [13] Kamal Jain and Vijay V. Vazirani.  Approximation algorithms for metric facility location and _k_ -median problems using the primal-dual schema and Lagrangian relaxation.  J. ACM, 48(2):274–296, 2001.
  * [14] William B. Johnson and Joram Lindenstrauss.  Extensions of Lipschitz mappings into a Hilbert space.  Contemporary Mathematics, 26:189–206, 1984.
  * [15] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu.  A local search approximation algorithm for k-means clustering.  Comput. Geom., 28(2-3):89–112, 2004.
  * [16] Euiwoong Lee, Melanie Schmidt, and John Wright.  Improved and simplified inapproximability for k-means.  Inf. Process. Lett., 120:40–43, 2017.
  * [17] Stuart P. Lloyd.  Least squares quantization in PCM.  IEEE Trans. Inf. Theory, 28(2):129–136, 1982.
  * [18] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Performance of Johnson-Lindenstrauss transform for _k_ -means and _k_ -medians clustering.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1027–1038. ACM, 2019.
  * [19] Jirí Matousek.  On approximate geometric k-clustering.  Discrete Comput. Geom., 24(1):61–84, 2000.
  * [20] Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy.  The effectiveness of Lloyd-type methods for the k-means problem.  J. ACM, 59(6):28:1–28:22, 2012.
  * [21] Andrea Vattani.  _k_ -means requires exponentially many iterations even in the plane.  Discrete Comput. Geom., 45(4):596–616, 2011.