Generating complex and realistic benchmarks through evolutionary data degradation

1Introduction

A model that reads operational documents is usually tested on documents easier than the ones it will meet. Public extraction benchmarks are collected, cleaned and labelled before anyone measures anything: the scanned receipt competition at ICDAR 2019, for instance, released 1,000 whole scanned receipt images with annotations [1Huang, Z., Chen, K., He, J., et al. (2019). ICDAR2019 Competition on Scanned Receipt OCR and Information Extraction. Proceedings of ICDAR 2019, IEEE; arXiv:2103.10213.]. Consider an illustrative case from Gulf distribution. A delivery note is printed in English and Arabic; a quantity is struck through and rewritten by hand when a carton is short; the note is photographed and sent to a WhatsApp group; and the customer's confirmation of the next order arrives in the same group in a mix of Arabic, English and ArabiziArabic written in Latin letters, with digits standing for sounds Latin lacks: 3 for ع, 7 for ح, 2 for the glottal stop.. A test set of clean documents says little about how a model will read that.

Noise of this kind is known to matter. Across six downstream tasks, van Strien et al. found that OCR errors had a consistent effect, with some tasks harmed far more than others [2van Strien, D., Beelen, K., Coll Ardanuy, M., et al. (2020). Assessing the Impact of OCR Quality on Downstream NLP Tasks. Proceedings of ICAART 2020, Volume 1: ARTIDIGH, SciTePress.]. OHRBench, 8,561 document images with questions over them, separates OCR noise into semantic and formatting noise and traces both into retrieval-augmented generation [3Zhang, J., Zhang, Q., Wang, B., et al. (2024). OCR Hinders RAG: Evaluating the Cascading Impact of OCR on Retrieval-Augmented Generation. arXiv:2412.02592 (ICCV 2025).]. Character-level noise, synthetic or natural, breaks neural translation of text that people read without trouble [4Belinkov, Y. and Bisk, Y. (2018). Synthetic and Natural Noise Both Break Neural Machine Translation. Proceedings of ICLR 2018; arXiv:1711.02173.]. Arabic adds failure modes of its own. Almost half its letters share a base shape, or rasmThe skeleton of an Arabic letter without its dots. ب, ت and ث share one rasm and differ only in the number and position of their dots., and are told apart only by dots [5Al-Shaibani, M. S. and Ahmad, I. (2025). Dotless Arabic Text for Natural Language Processing. Computational Linguistics 51(2), 557-598.]; in a test of four Arabic OCR systems on 240 text images, characters without dots were recognised significantly better than characters with one, two or three [6Alghamdi, M. and Teahan, W. (2017). Experimental evaluation of Arabic OCR systems. PSU Research Review 1(3), 229-241.].

Collecting and labelling degraded documents by hand is slow, and it yields one level of difficulty, fixed when the documents were gathered. A fixed test set also ages: once its items reach training data, a high score may reflect memory rather than skill, the problem known as benchmark contaminationTest items, or their answers, appearing in a model's training data, so that a score measures recall of the item rather than the ability the benchmark was built to test. [7Sainz, O., Campos, J., García-Ferrero, I., et al. (2023). NLP Evaluation in trouble: On the Need to Measure LLM Data Contamination for each Benchmark. Findings of the Association for Computational Linguistics: EMNLP 2023., 8Jacovi, A., Caciularu, A., Goldman, O., et al. (2023). Stop Uploading Test Data in Plain Text: Practical Strategies for Mitigating Data Contamination by Evaluation Benchmarks. Proceedings of EMNLP 2023.]. A generator with a seed can produce fresh variants whenever they are needed, at the difficulty asked for, with the answer known.

This paper builds such a generator and studies how it behaves. Its contributions are:

• A degradation model for Gulf business documents: eleven operators in four families, from OCR confusions between Arabic letters that differ only by dots to Arabizi, code-switching and handwritten corrections, applied to documents held as typed fields so that their structure survives for measurement.
• A recoverability validator: a rule-based reference parser whose reading is aligned field by field with the ground truth, so that every variant kept still has a correct answer for its item, quantity, unit, price and date.
• An evolutionary search with a quality-diversity archive that produces, for each document, a ladder of variants from lightly to heavily degraded, compared with random degradation at the same cost.
• Code and output that reproduce every number in this paper from a fixed seed.

What this paper does not do is evaluate a model. It shows that the generator produces harder documents that can still be answered; whether models find them harder is the next experiment, set out under Limitations.

2Background and related work

Making evaluation data harder on purpose

Several lines of work make data harder by rewriting it. Evol-Instruct uses a language model to rewrite instructions step by step into more complex ones, deepening or broadening each, and discards evolutions that fail [9Xu, C., Sun, Q., Zheng, K., et al. (2023). WizardLM: Empowering Large Pre-Trained Language Models to Follow Complex Instructions. arXiv:2304.12244 (ICLR 2024).]. Dynabench puts people in the loop: annotators write examples that a target model gets wrong but another person would not [10Kiela, D., Bartolo, M., Nie, Y., et al. (2021). Dynabench: Rethinking Benchmarking in NLP. Proceedings of NAACL-HLT 2021.]. GSM-Symbolic generates variants of grade-school mathematics questions from symbolic templates, and reports that accuracy falls when only the numbers change, and by up to 65% when a single clause that seems relevant, but does not change the answer, is added [11Mirzadeh, I., Alizadeh, K., Shahrokhi, H., et al. (2024). GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models. arXiv:2410.05229.]. Our setting differs in two ways: the rewriting is a search over defects rather than a rewrite by a model, and the difficulty is bounded by a constraint, checked by code, that the answer must survive.

Perturbation and behavioural testing

CheckList organises behavioural tests by capability and test type and generates large numbers of test cases from templates [12Ribeiro, M. T., Wu, T., Guestrin, C., et al. (2020). Beyond Accuracy: Behavioral Testing of NLP Models with CheckList. Proceedings of ACL 2020.]. NL-Augmenter collects an initial set of 117 transformations and 23 filters contributed by a large community, several of them perturbations of the kind used here [13Dhole, K. D., Gangal, V., Gehrmann, S., et al. (2021). NL-Augmenter: A Framework for Task-Sensitive Natural Language Augmentation. arXiv:2112.02721.]. Belinkov and Bisk's synthetic noise includes keyboard typos, a letter replaced by a neighbouring key, which our typo operator follows [4Belinkov, Y. and Bisk, Y. (2018). Synthetic and Natural Noise Both Break Neural Machine Translation. Proceedings of ICLR 2018; arXiv:1711.02173.]. These libraries apply one perturbation, or a fixed mix, at a set rate. We compose many, search over their combinations, and keep only the variants that can still be answered.

OCR error, Arabic script and Arabizi

Post-OCR correction for Arabic has a long history, including the correction of character segments with the help of language models [14Magdy, W. and Darwish, K. (2006). Arabic OCR Error Correction Using Character Segment Correction, Language Modeling, and Shallow Morphology. Proceedings of EMNLP 2006.], and dots are among the main sources of the errors such correction meets [6Alghamdi, M. and Teahan, W. (2017). Experimental evaluation of Arabic OCR systems. PSU Research Review 1(3), 229-241.]. Arabizi is a different problem, of transcription rather than recognition: Arabic typed in Latin letters, with numerals for the letters that have no Latin equivalent, which Darwish detects and converts back to Arabic script [15Darwish, K. (2014). Arabizi Detection and Conversion to Arabic. Proceedings of the EMNLP 2014 Workshop on Arabic Natural Language Processing (ANLP).]. To measure damage we use the character error rate (CERCharacter error rate: the number of characters that must be inserted, deleted or substituted to turn the degraded text back into the clean one, divided by the length of the clean text.), computed with Myers' bit-vector algorithm for edit distance [16Myers, G. (1999). A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM 46(3), 395-415.]. Standard CER first turns a page into a single string, so a block read in the wrong order is counted as many character errors; Clausner et al. proposed a flexible measure for that reason [17Clausner, C., Pletschacher, S. and Antonacopoulos, A. (2020). Flexible character accuracy measure for reading-order-independent evaluation. Pattern Recognition Letters 131, 390-397.]. We take a simpler route, described in the next section.

Search with populations and archives

Genetic algorithms evolve a population of candidates by selection, recombination and mutation [18Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press (first published 1975, University of Michigan Press)., 19Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.]. A search that maximises one score tends to converge on one kind of answer. MAP-Elites, a quality-diversityA family of search methods that keep many good candidates spread across features the user chooses, rather than a single best candidate. method, divides a space of features into cells and keeps the best candidate found in each, so the search returns a map of candidates that are both strong and different [20Mouret, J.-B. and Clune, J. (2015). Illuminating search spaces by mapping elites. arXiv:1504.04909.]. Rainbow Teaming applied the idea to evaluation, casting the generation of adversarial prompts as a quality-diversity problem with an archive built on MAP-Elites [21Samvelyan, M., Raparthy, S. C., Lupu, A., et al. (2024). Rainbow Teaming: Open-Ended Generation of Diverse Adversarial Prompts. Advances in Neural Information Processing Systems 37 (NeurIPS 2024); arXiv:2402.16822.]. Our archive's features are the family of defects that dominates a variant and how many defects it carries.

Fresh test data

Contamination is now a central concern of benchmark design. Sainz et al. argue for measuring it benchmark by benchmark [7Sainz, O., Campos, J., García-Ferrero, I., et al. (2023). NLP Evaluation in trouble: On the Need to Measure LLM Data Contamination for each Benchmark. Findings of the Association for Computational Linguistics: EMNLP 2023.]; Jacovi et al. propose encrypting public test data and asking model providers for controls that keep it out of training [8Jacovi, A., Caciularu, A., Goldman, O., et al. (2023). Stop Uploading Test Data in Plain Text: Practical Strategies for Mitigating Data Contamination by Evaluation Benchmarks. Proceedings of EMNLP 2023.]; LiveBench adds and updates its questions every month [22White, C., Dooley, S., Roberts, M., et al. (2024). LiveBench: A Challenging, Contamination-Limited LLM Benchmark. arXiv:2406.19314 (ICLR 2025).]. A seeded generator is one more answer: the published code fixes the method, while private templates and a private seed can produce variants that have never been online.

3Method

Documents

The script writes 48 synthetic documents from three templates in turn, a delivery note, a purchase order and a WhatsApp-style order confirmation, so 16 of each. A country is drawn for each document (13 came out Omani, 22 Saudi and 13 Emirati) and with it the place names (Sohar, Nizwa, Jeddah, Dammam, Jebel Ali, Fujairah and others), the currency and its decimals (OMR to three places, SAR and AED to two) and, on purchase orders, the VAT rate. Each document lists three to five items, 3.9 on average, drawn from a catalogue of twenty food and industrial items, each with an English name, an Arabic name, an Arabizi spelling and a SKU. Delivery notes and purchase orders give each item in both languages; a WhatsApp confirmation gives it once, in one language, line by line, sometimes with Arabic-Indic digits. Every document has exactly one date, in one of several formats. The clean documents average 341 characters.

Every party, number and code in the documents is synthetic, and every example in this paper is illustrative. The Arabic strings were written by us and have not yet been reviewed by a native Gulf reader. Each document keeps its ground truth: the date and, for each line, the item, quantity, unit and price.

Eleven operators

An operator applies one defect to one field, one line or the line order. The eleven fall into four families: visual defects that come from paper and cameras, script defects that come from writing Arabic and English with the tools at hand, including code-switchingMoving between two languages inside one message or one sentence; here, Arabic and English., human defects of typing and shorthand, and layout defects of reading order and missing fields. The table gives each with an illustrative example and, from the run itself, how often it alone left a document unrecoverable.

The validator

A variant is useful as a test item only if its answer is still in it. The validator is a rule-based reference parser that reads the degraded text as a careful deterministic extractor would. It drops values marked as struck through, folds Arabic-Indic digits into Western ones, strips stray marks, normalises Arabic letter variants (the hamza seats on alif, ta marbuta and alif maqsura), repairs O and l to 0 and 1 inside numbers, and finds each item by fuzzy match against an alias table built from the generator's catalogue: the English, Arabic and Arabizi names and the SKU, with an edit tolerance that grows with the length of the name. On each item's line it reads the unit, the quantity beside it and the price, and it reads the one date in the text.

The parser's reading is then aligned with the ground truth field by field. A variant is recoverable if the same items come back with the same quantity, unit and price, and the same date; otherwise it is rejected. All 48 clean documents pass. Separate plausibility bounds reject a variant whose length falls outside 0.75 to 1.5 times the clean length, whose stray marks exceed 4% of the clean length, or which holds more than three handwritten corrections or three inserted phrases.

Difficulty

Fitness is a difficulty proxy: CER plus half the structural damage. We compute CER line by line, each degraded line against its own clean line, summed and divided by the length of the clean text. A line that moved is then not also counted as rewritten, the problem Clausner et al. describe for whole-page measures [17Clausner, C., Pletschacher, S. and Antonacopoulos, A. (2020). Flexible character accuracy measure for reading-order-independent evaluation. Pattern Recognition Letters 131, 390-397.]; the move is counted once, in structural damage. Structural damage is the mean of three shares: how far the line order is from the original, as a normalised Kendall tau distanceThe share of pairs of lines that appear in the opposite order to the original: 0 for the original order, 1 for the order fully reversed., the share of fields deleted, and the share of key fields whose surface form no longer matches the clean text. We also report whole-text CER.

Search

Each document evolves on its own for 16 generations, starting from the clean document as generation 0. Each generation makes 24 children. A parent is drawn, half the time uniformly from the archive and otherwise by a tournament of three among the eight hardest variants found so far; with probability 0.2 it is crossed with a second parent, each line coming from one or the other; then one, two or three operators (with probabilities 0.5, 0.3 and 0.2), each drawn uniformly from the eleven, are applied. A variant may carry at most twelve operator applications. When a mutation would exceed that budget, one damaged line, or the line order, is first restored to its clean state, so that the search keeps moving at the budget; this happened 8,752 times.

Children that pass the validator and the bounds, and are not copies of an earlier variant, compete for the archive. Its cells cross the dominant operator family (four values) with the number of operator applications (1 to 3, 4 to 6, 7 to 9, 10 to 12), sixteen cells per document, and each cell keeps its hardest variant. The parents of the following generation are the archive's variants and the eight hardest found so far. That is 384 evaluations per document and 18,432 children in all.

A random baseline

To ask whether the search adds anything, each document also gets 384 random variants, the same number of evaluations: 32 at each level from one to twelve operators, drawn uniformly, applied to the clean document and checked by the same validator and bounds.

The script uses only the Python 3 standard library and draws every random number from generators seeded with 20261014. Two runs under different hash seeds wrote byte-identical output, and a run takes about a minute and a half on a laptop.

4Results

Difficulty rises and answers survive

The mean CER of the hardest variant per document rose from 7.0% in generation 1 to 35.0% in generation 16, and the mean over the whole archive from 4.5% to 18.1% (median 4.0% to 16.4%). The rise slows from about generation 6, when the hardest variants reach the budget: the eight hardest per document carried 11.4 operator applications on average in generation 6 and 11.9 in generation 16, so later gains come from choosing which twelve defects to keep, not from adding more. Throughout, between 86.5% and 90.3% of each generation's children stayed recoverable, 16,329 of 18,432 in all (88.6%); 15,945 (86.5%) also passed the plausibility bounds and were not copies of an earlier variant.

Evolution against random degradation

At the same 384 evaluations per document, the hardest evolved variant had a mean CER of 35.0% and the hardest random one 24.0%. The evolved variant was the harder of the two in 47 of 48 documents by CER, and in all 48 by the fitness the search optimised.

Random degradation also shows why a validator is needed. With one random operator, 93.1% of variants stayed recoverable; with twelve, 43.4%. A benchmark built by applying a dozen random defects and keeping the original labels would, at that level, hold an answer the text no longer supports in more than half its items. The search avoids this by building each variant one validated step at a time: its children stayed recoverable close to nine times in ten in every generation, including the late ones, in which the hardest variants carried close to the full budget of twelve defects.

What selection kept

Operators were proposed uniformly: each accounts for between 8.8% and 9.3% of the 31,313 applications made during the search. Selection changed the mix. In the final archive, handwritten corrections account for 19.9% of operator applications, code-switching for 15.3% and Arabizi for 13.2%, while Latin and digit OCR confusions (3.7%), keyboard typos (4.2%), Arabic dot confusions (4.4%) and stray marks (4.5%) fell well below their share of the proposal. In the hardest variant of each document the skew is stronger: code-switching, corrections and Arabizi make up 60.9% of applications, and typos, dot confusions, stray marks and Latin OCR confusions between 1.0% and 2.3% each.

Part of this is the proxy, and we read it that way. Rewriting a whole field in another script, or inserting a phrase, changes many characters in one application, where a dot confusion changes one; a correction adds a struck value several characters long and costs the parser nothing. CER rewards whatever changes characters, and the search found the cheapest ways to change them. Whether a model finds a struck quantity harder than a missing dot is a question for the next experiment, and the answer may invert this ranking: one dot can turn one word into another, and a reader of the photograph sees a strike that a transcript can only mark. What the archive does guarantee is coverage: 767 of its 768 cells were filled, so for almost every document the benchmark can be sliced by the kind of defect as well as by how much.

What breaks a document

Some operators are far more likely than others to destroy an answer. Counting only children where one operator was applied, field deletion left the document unrecoverable 36.7% of the time (310 of 844), Latin and digit OCR confusions 19.1% (162 of 847) and keyboard typos 10.8% (87 of 805), followed by Arabizi at 5.1%, Arabic dot confusions at 3.8% and abbreviations at 3.7%. Digit script swaps, line reordering and handwritten corrections never did, because the parser folds digits, ignores line order and drops struck values.

Of the 2,103 children rejected as unrecoverable, the price was lost in 33.0%, the quantity in 20.7%, the unit in 19.9%, the date in 15.3% and the item in 14.6%; a child can lose more than one. Prices are fragile because every character in them counts: one misread digit, one stray point, or trailing zeros dropped from a price that has no currency beside it is enough.

A ladder of difficulty

Because the archive is divided by the number of operator applications, it holds a graded series for every document. Mean CER in the final archive was 6.5% at one to three applications, 14.1% at four to six, 21.8% at seven to nine and 29.8% at ten to twelve. This ladder, more than the single hardest variant, is what a model evaluation needs: accuracy measured on each rung shows where a model starts to fail.

Messages degrade further than forms

The hardest WhatsApp confirmations reached a mean CER of 46.4%, against 28.2% for delivery notes and 30.4% for purchase orders. Messages are shorter, 229 characters on average against 422 and 370, so each defect weighs more. Whole-text CER, which counts a moved line as rewritten, was 30.0% over the archive against 18.1% line by line, and 46.9% against 35.0% for the hardest variants: measured over the whole text, reading order alone would overstate the damage by between a third and two thirds.

Clean
[10:37] Dubai sales: Hello, الطلب مؤكد
UHT milk 12 cartons @ 46.50 AED
white sugar 5 bags @ 29.00 AED
2 cartons tomato paste, 52.00 AED
basmati rice 9 bags @ 40.75 AED
[10:39] Dubai sales: التوصيل 16 أكتوبر 2026 إلى سوبرماركت الشارقة

Hardest variant after 16 generations
[10:37] Dubai مبيعات: Hello, 
UHT milk 12 cartons @ 46.50 AED
white sugar مثل المرة الماضية -6- 5 bags @ ۲۹٫۰۰ AED
2 cartons tomato paste, 5̶8̶.̶0̶0̶ 52.00 AED
أرز بسمتي 9 مثل المرة الماضية bags @ ۴۰٫۷۵ AED
[10:39] Dubai sales: al tawseel 1̶3̶ ̶أ̶ك̶ت̶و̶ب̶ر̶ ̶2̶0̶2̶6̶ 16 أكتوبر 2026 إلى سوبرماركت al shariqa

One document, generation by generation

The widget follows one illustrative document, a synthetic Emirati delivery note, along the line of ancestors of its hardest final variant. In generation 1 a line moved, a dot changed in أسمنت and the total was struck and rewritten; by generation 7 two Arabic labels were in Arabizi, two item names were gone and the date carried a struck correction; by generation 16 the CER was 0.371, with every key field still recoverable. The budget forced restorations along the way, which is why the moved line returns to its place and some defects appear and later disappear.

5Implications for deployment

For a Gulf company putting a model to work on its documents, the lesson is that the test set should look like the documents, at several levels of damage, with answers known to be right. Three practices follow.

• Start from the company's own templates and past cases. The generator here is synthetic. In a deployment, the clean documents and their ground truth come from the company's own records, so the defects land on its item names, its units and the way its customers write.
• Validate every generated item. Random degradation at twelve defects left fewer than half the variants answerable. A test item whose answer is no longer in the text measures noise, not the model.
• Report accuracy by level and by family. One average hides where a model fails. A ladder shows the level of damage at which accuracy drops, and that is where a threshold belongs: below it the agent proceeds, above it a person checks.

This is how we approach evaluation at Qantara. Each agent is run on the customer's past cases before it goes live, with their team marking what good looks like, and the work arrives in Arabic and English on the same document and the same message. Degraded variants of those past cases could extend that test to documents that have not arrived yet, and the thresholds the customer sets, above which a person approves, can be placed with the ladder in hand. Because the record and its log are kept in the customer's country, the variants can be generated where the record already lives.

6Limitations

This paper does not evaluate any model on the benchmark. It shows that the search produces variants that are harder by a character-level proxy and still answerable by a rule-based parser. It does not show that models find them harder, or which defects hurt models most. The next step is to measure model accuracy against degradation level: run extraction models, from rule-based parsers to small and frontier language models, on every rung of the ladder and every family, and report where accuracy falls.

• Text, not images. The operators act on transcribed text, and OCR confusions are simulated character by character. A fuller pipeline would render each document, damage the image and run an OCR engine, whose errors are correlated in ways ours are not.
• Hand-written operators, uncalibrated rates. The operators, their probabilities, the budget of twelve applications and the plausibility bounds are our choices. None is calibrated against how often each defect occurs in real Gulf documents, which we have not measured.
• A gameable proxy. CER rewards defects that change many characters, and the search exploited that with code-switching and inserted phrases. A proxy closer to model difficulty, or model accuracy itself, would change what the search keeps.
• One validator. Recoverable means recoverable by our parser. A person might recover fields the parser cannot, or be misled where it is not, and the currency, fixed by the country, is not checked.
• Small and synthetic. 48 documents from three templates and twenty items, one seed and one run. The Arabic was written by us and has not been reviewed by a native Gulf reader.

7Conclusion

Evolutionary degradation under a recoverability constraint does what a benchmark generator needs. In sixteen generations it made synthetic Gulf business documents much harder by character error rate, harder than random degradation at the same cost, while keeping close to nine children in ten answerable and filling a ladder of difficulty for every document. The search also showed what a character-level proxy rewards, which is not necessarily what makes a document hard for a model.

The generator and its output are published with this paper. The next step is to put models on the ladder and measure where each one starts to fail.