Cheap, Unbiased Fitness for Evolving Readability Ensembles

Automated readability assessment means predicting how hard a sentence is for a human to read, for example on the six-level CEFR scale from A1 to C2. Its main open failure is the "domain bubble": a model trained on Wikipedia or news text breaks when it meets legal, medical, or colloquial sentences. Ensembles of diverse predictors are the standard defense. The best way to build an ensemble whose members fail in different places is to search for members that help the group, not members that look good alone. Evolutionary search does this, but every new candidate member has to be scored on a large validation set. When the candidates are prompts to a large language model, that means one model call per sentence per candidate per generation, and the cost becomes prohibitive.

This note proposes a way to score each candidate on only a small, well-chosen fraction of the validation sentences while keeping the fitness estimate unbiased. A readability ensemble that averages graded scores has a useful property: a new member's contribution to the ensemble's squared error splits exactly into a sum of per-sentence terms. Each term depends only on the ensemble's current residual and the candidate's residual on that sentence. In evolutionary search we can also predict the candidate's residuals well before we see them, because a mutated prompt behaves much like its parent, and the parent's residuals are already known on every sentence. Cheap linguistic descriptors of each sentence add further signal. We use that prediction as a control variate: score the prediction on all sentences, then correct it with a small importance-weighted sample of real model calls. A surrogate model then cuts cost without becoming something the search can exploit.

Core Claim

For ensemble-aware evolution of readability predictors, a parent-informed, linguistically conditioned control-variate estimator of each candidate's marginal ensemble gain can match full-validation fitness rankings at a fraction of the model calls. It can also produce ensembles that generalize better to unseen domains than both uniform subsampling and plain surrogate filtering under the same call budget.

The estimator works as follows. Let the current ensemble average $M$ members' numeric scores, and let $e_i$ be its residual (prediction minus gold label) on validation sentence $i$, out of $N$ sentences. Let $r_i$ be the candidate's residual. The change in squared error from adding the candidate is

$$\Delta_i = \left(\frac{M e_i + r_i}{M+1}\right)^2 - e_i^2 .$$

We define the candidate's fitness as $F = \frac{1}{N}\sum_i \Delta_i$, where lower is better. Let $\hat\Delta_i$ be a surrogate prediction of $\Delta_i$ formed by plugging in a predicted residual $\hat r_i$. We then draw a small set $S$ of $n$ sentences with probabilities $q_i$, query the model only on those sentences, and estimate

$$\hat F = \frac{1}{N}\sum_{i=1}^{N} \hat\Delta_i + \frac{1}{N n}\sum_{j \in S} \frac{\Delta_j - \hat\Delta_j}{q_j}.$$

This estimate is unbiased for any surrogate. Its variance shrinks with the surrogate's residual error, as in standard difference estimators. Sampling probabilities $q_i$ proportional to the predicted magnitude $|\hat\Delta_i|$ concentrate calls where the candidate can actually move the ensemble: sentences where the ensemble is wrong or sits near a level boundary. Squared error stands in for quadratic weighted kappa, which is not decomposable but is closely tied to squared error on ordinal scales. Final reporting uses the true metrics.

Prior Work and Positioning

Three lines of work supply the pieces, and none combines them. C-Evolve evolves groups of prompts whose fitness is their contribution to consensus accuracy. Its ablation shows that grouping the best individual prompts from AlphaEvolve gave only 41.15%, below consensus-evolved groups. This motivates ensemble-aware fitness. C-Evolve evaluates candidates on full validation queries, smooths noise with a moving average, has no cost-reduction mechanism, and was never applied to graded regression or readability.

SA-P3-GOMEA uses a support-vector-regression surrogate to filter partition-based ensemble candidates on tabular data. Its lessons constrain our design. It found that surrogate estimates must never be compared directly with real fitness values, and that deterministic surrogates degrade under noisy evaluations. Our estimator removes the need for that separation, because every reported fitness is an unbiased estimate of the real one rather than a surrogate guess. DivE² builds diverse ensembles by matching data to models, but only in vision, and with its own combinatorial cost.

On the readability side, !MSA at BAREC 2025 won the Arabic shared task by hand-composing four transformers trained with three losses and weighting them by confidence. This shows that diverse members matter, but its design came from manual trial and error. Hybrid Models for Sentence Readability Assessment stacks XGBoost on transformer predictions and linguistic features. ReadMe++ documents the domain bubble and reports two things this proposal relies on: diversity in prompt exemplars matters more than the number of exemplars, and fine-tuned mT5-Large beats general-purpose models in correlation with human labels.

The tension between Linguistic Features for Readability Assessment and FPT also shapes the design. The first finds hand-crafted features redundant once data is plentiful; the second finds them essential in few-shot settings. We use linguistic features only as covariates for predicting where a candidate will err, never as ensemble inputs. Even if they add nothing to accuracy, they can still lower the variance of the fitness estimate.

Research Program

The ensemble members are language-model prompts for sentence readability. Each prompt combines an instruction with a set of graded exemplars. Ensembles are built in two forms: prompts only, and prompts alongside a fixed fine-tuned mT5-Large anchor. Mutations rewrite instructions and swap exemplars across domains, following the ReadMe++ finding that exemplar diversity drives in-context accuracy. The search uses C-Evolve's island structure and its warm-up and voting stages, so that the only thing that changes is how fitness is computed.

The surrogate predicts a child's residual $\hat r_i$ from four sources: the parent's known residual on sentence $i$, lingfeat descriptors (dependency distance, part-of-speech density, lexical diversity), surface formulas such as Flesch-Kincaid, and a domain identifier. It is a small gradient-boosted or ridge model, refit online after each generation on all real calls made so far.

We will measure three things. The first is how well estimated fitness ranks candidates compared with full-validation fitness, as a function of calls per candidate. The second is the total calls needed to reach a given ensemble quality. The third is the ensemble's held-out-domain performance. A secondary analysis asks whether linguistic covariates add estimator efficiency beyond parent residuals, and whether that gain is larger for sentence-level, morphologically rich Arabic data. This would be a variance-reduction counterpart of the scarcity-versus-redundancy debate about linguistic features.

Baselines

The naive reference is a single best prompt found by the same evolutionary loop with individual fitness and full evaluation. Next to it sits fine-tuned mT5-Large alone. ReadMe++ identifies it as the strongest task-specific model, but no reported numeric result was found on Lacuna for mT5-Large's Spearman correlation or F1 on ReadMe++, so we will reproduce it ourselves under our splits.

The strongest existing ensemble method is C-Evolve with full-validation voting fitness. It is the closest system and the one whose overhead we target. We run it with identical islands, mutation operators, base model, and seeds, and we hand it a call budget several times larger than ours. Beating it means matching its held-out-domain quality with substantially fewer calls, or exceeding it at equal calls.

The strongest hand-designed ensemble is the !MSA recipe of diverse architectures and losses with confidence weighting. Its reported score is 87.5% quadratic weighted kappa at the sentence level on BAREC's strict track (!MSA). On BAREC we treat that as the external bar. We do not claim a prompt ensemble will beat it. The question is whether adding an evolved prompt group to fine-tuned members improves on it.

Three ablations isolate the key ingredient, each at equal calls. The first uses uniform random subsampling with no surrogate. The second uses the surrogate prediction alone with no correction, which is classic biased surrogate filtering in the SA-P3-GOMEA style. The third uses the full estimator with linguistic covariates removed, leaving parent residuals only.

Why not just…?

Why not just score candidates on a small random subset of sentences? This is the obvious cost cut, and it is unbiased too. Its variance, however, is dominated by the many sentences where adding one member cannot change the ensemble's grade. That waste grows as the ensemble improves and as the residuals $e_i$ shrink. The uniform-subsampling ablation at matched calls settles the question. If it ranks candidates as well as our estimator, the proposal collapses to "subsample," and we will report that.

Why not just train a large pool of prompts once and select an ensemble greedily from cached predictions? This is a real threat. Once predictions are cached, every subset is free to evaluate, and greedy forward selection is simple and strong. Its weakness is that the pool is generated without knowing what the ensemble lacks, while C-Evolve's ablation shows that individually strong members combine poorly. We run greedy selection over a pool built with exactly our total call budget. If it matches evolved ensembles, the conclusion is that targeted generation is not worth it for readability. Our estimator still applies to deciding which pool members deserve full evaluation.

Why not just use a surrogate to filter candidates, as surrogate-assisted evolution already does? SA-P3-GOMEA had to separate real and surrogate fitness to avoid divergence, and it reports degradation under noisy evaluations. Sampled language-model scoring is exactly such a noisy evaluation. The surrogate-only ablation will show whether the search drifts toward candidates that fool the surrogate. We expect evidence of this drift as a gap between estimated and true held-out fitness that widens over generations.

Why not just fine-tune one strong model, or ensemble fine-tuned models, and skip prompts? On BAREC, fine-tuned ensembles are the incumbent, and we expect to lose to them on in-domain data. The case for prompts is the cross-domain setting, where ReadMe++ reports that domain diversity in exemplars matters. Our leave-domains-out comparison against mT5-Large, and against mT5-Large plus an evolved prompt group, decides whether prompts add anything.

Proposed Experiments

The main testbed is ReadMe++, evaluated by Spearman correlation and F1 on six CEFR levels. We use leave-domains-out splits: evolve on some domains, validate within them, and test on unseen domains. BAREC sentence-level quadratic weighted kappa is the second testbed. WSJ, where the hybrid model reached 0.729 accuracy (Hybrid Models), serves as a small English sanity check.

The first decisive check is ranking agreement. Using a full-evaluation C-Evolve run as ground truth, we measure Kendall correlation between estimated and true candidate fitness at 5%, 10%, and 20% of sentences, comparing uniform sampling, surrogate-only, and the full estimator. The second check plots total model calls against held-out-domain Spearman correlation for every method. The proposal succeeds if our curve dominates both full-evaluation C-Evolve and uniform subsampling, and if it is not dominated by greedy pool selection. The third check measures how much the variance of the fitness estimate shrinks when linguistic covariates are added on top of parent residuals, separately for English and Arabic.

A negative result is informative either way. If parent residuals alone carry all the gain, the linguistic side of readability matters only as an evaluation domain. If the gain disappears for greedy pool selection, ensemble-aware evolution is unnecessary for this task.